2
$\begingroup$

Alice split a long string P into two segments A and B. A is relatively short and B is long.

H = sha256(A + B)

Bob does not know P, but knows H.

Is it possible for Alice to prove to Bob that A is the prefix of P, but only needs to provide additional information much shorter than B?

$\endgroup$
7
  • 1
    $\begingroup$ Welcome to Cryptography.SE. What is the origin of this question? What are the sizes of $A$ and $B$. $\endgroup$
    – kelalaka
    Jun 12, 2021 at 10:52
  • $\begingroup$ Thanks, this is a question I think of when I am exploring the delivery of Bitcoin tx. I hope that without telling all the tx, I can prove to others which is the first utxo spent by this tx. so A is about 40 Bytes, B may more than 1000 KB. $\endgroup$
    – jiedo
    Jun 12, 2021 at 11:53
  • $\begingroup$ Well, that is input the SHA256 so if you can't find a collision then you need to tell all. $\endgroup$
    – kelalaka
    Jun 12, 2021 at 11:58
  • $\begingroup$ Got it. If A is long and B is short, it is possible to prove that B is the suffix of P with content shorter than A. But the reverse seems to be really impossible. $\endgroup$
    – jiedo
    Jun 12, 2021 at 12:13
  • $\begingroup$ If B is short then Bob can brute force it $\endgroup$
    – kelalaka
    Jun 12, 2021 at 12:21

2 Answers 2

4
$\begingroup$

Because of the way SHA2 works, no.

SHA2 splits the message up into blocks, then uses a compression function to compress each block into the state. The final state is the hash value.

Merkle-Damgard Hashing

This means that the only way to "connect" the intermediate state after A has been processed with the final value is to hash all the blocks for the B part, requiring the entirety of B. It's impossible to use fewer bits.

Merkle trees

If you want to verify sub-strings quickly, the standard solution is to use a Merkle tree.

Merkle tree

Any node in the tree can be calculated using its children, so we can avoid sending all the content and just supply the nodes necessary to move up the tree to the root node.

If L1 and L2 were the A string and L3 and L4 were the B string, Alice could supply A along with Hash 1 and Bob does not need to know the L3 and L4 blocks to calculate the root hash. Alice can prune the tree to include only what's necessary.

$\endgroup$
0
$\begingroup$

To prove anything relating to P, Bob would need to know P to begin with, so in that sense you cannot prove within the calculation of a single hash that any particular data is hidden in that hash, without knowing P. You cannot prove a segment of a sha256 hash belongs to anything, you can only prove that you are the signer of a transaction.

One approach though, which may or may not be sufficient for what you want to do is to just prove that the UTXO's in a transaction are members of a series, meaning that you can prove that they are associated with the same sender, and you can also obfuscate this so that only one person is provided that evidence.

To do this you could take the previous transaction ID from some input, like input #1 in your transaction bundle, and then take the previous transaction ID from another transaction, lets say input #2 in your transaction bundle, and XOR those two values together to get a third hash that is the result of an XOR of the two transaction IDs that you want to associate with eachother. Now take that result of the XOR operation and place it in the scriptsig or even the coinbase transaction field in one of the outputs so that it is saved and visible on the chain once sent.

Now Alice can tell Bob to look at the scriptsig (or memo field where people often store OP_RETURN data) of the output that holds the XOR'd value, and with that just perform another XOR operation using the stored hash XOR'd again with the output's previous transaction ID, and the result of that XOR operation will be the previous transaction ID of the first input.

It sounds like that may not be exactly what you would like to do, but if associating the transactions together is all that is needed, as opposed to a full cryptographic proof or revealing any keys, you can take advantage of the commutative property of XOR to store some info.

And so taking this XOR operation:

transaction_id_A ^ transaction_id_B = transaction_id_X

Also means that

transaction_id_X ^ transaction_id_B = transaction_id_A

As well as:

transaction_id_A ^ transaction_id_X = transaction_id_B

And so with that method you can prove that the outputs are related or associated with the same person making the transaction, or prove that they were done at the same time, but there is no possible way to prove a substring of a hash digest belongs to any particular input given to sha256.

Any time that any data is fed in to SHA256 it will return a totally random new hash that is not in any order or predictable pattern, but you can use the scriptsig/OP_RETURN fields to save references to other outputs or transactions, as those do not require any key to view on the block explorer, so interlocking those fields may be the closest we can get for that type of proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.