Skip to main content
4 of 8
Explain why it works. Detail what happens for the last hash.
fgrieu
  • 145.4k
  • 12
  • 319
  • 611

A Hash Tree is meant for that. In your case, a binary tree seems fit.

For example, with SHA-256 (256-bits output, 512-bit block)

  1. Choose a superblock size that is a n>0 times 512 bits, say 8192 bits (1kB, for n=16); n=1 works, but a higher value improves computing efficiency markedly.

  2. Pad the file by adding a 1 bit, just enough 0 bits, and the initial file length on 64 bits, so that the new end of file falls on a 512-bit block (or as a variant, superblock) boundary.

  3. Distribute (or more realistically generate locally) the file truncated in segments falling on superblock boundaries, with indication of the starting position of each segment in superblock unit, starting with 0 for the first superblock. The number of superblocks m must be distributed too.

  4. Each party hashes each superblock, with a SHA-256 variant not including padding, doing 2n SHA-256 rounds (or less for the last superblock); the result is assigned the number of the superblock hashed.

  5. Each party hashes, with a SHA-256 variant not including padding, any two hashes in its possession with number differing by the low-order bit (the hash with the lower number is hashed first); one SHA-256 round is needed; the result is assigned the lower number of the two hashes re-hashed. The hash of the last superblock is either hashed (if m is even), or moved up to the next step unchanged.

  6. This is repeated for hashes of hashes and the second low-order bit, leaving the highest-numbered hash unchanged if its number differs from m in the second low_oder bit. Then again as deep as possible in the binary tree, testing increasingly higher-order bits.

  7. Each party returns its partial results, which will include at most Ceil(Log2(m+1)) hashes if it handles m consecutive superblocks. If the communication is centralized, the central point finishes the calculation, again hashing according to a binary tree. With decentralized communication, it is advantageous to aggregate partial results with a peer handling a segment of the file just before or after, which might allow to perform slightly more of the work.

Note: the final hash obtained at the bottom of the tree depends on the file content and length, and the parameter n controlling superblock size; but not on how the file was chopped in segments at step 2. This is because the computation performed is according to the same tree regardless of the chopping.

Note: steps 1 to 6 can be interleaved to reduce storage requirements.

Note: the number of SHA-256 rounds at step 2) is the same as in SHA-256. The number of extra rounds is less than 21-n times that.

fgrieu
  • 145.4k
  • 12
  • 319
  • 611