# In sha256, is it possible to use less information than the full preimage to prove that the prefix of the preimage is a certain string

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?

• Welcome to Cryptography.SE. What is the origin of this question? What are the sizes of $A$ and $B$. Jun 12, 2021 at 10:52
• 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. Jun 12, 2021 at 11:53
• Well, that is input the SHA256 so if you can't find a collision then you need to tell all. Jun 12, 2021 at 11:58
• 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. Jun 12, 2021 at 12:13
• If B is short then Bob can brute force it Jun 12, 2021 at 12:21

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. 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. 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.