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?

  • 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

1 Answer 1


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.


Your Answer

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

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