Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
