Merkle Hash Trees

In PPSP, by design, the integrity of any given chunk of data can be verified efficiently using a cryptographic signature scheme. The hashing algorithm itself is the well-known Merkle hash tree:

merkle hash tree

By transmitting with each new datagram, a set of new chunk hashes, and the new data, a peer can verify using any already downloaded / hashed data, and the new data, if in fact, is valid (untampered with during transit) and part of the desired data, by comparing all the way up to the root hash, which was obtained outside the PPSP protocol, from a trusted endpoint.

This is a significant advantage over BitTorrent, which requires downloading in advance all required hash data, and in addition, forces seeding peers to maintain a full list of hashes for every chunk. PPSPP only needs to store sibling and uncle hashes for select nodes within the tree, and can still maintain cryptographically secure chunk distribution.

Algorithm Overview

Verification

Note that the root hash represents a significant proof of work by the bearer, that, if provided with an appropriate set of hashes further down the tree, can be used to determine even from a very small number of chunks, if the provided data is in fact a valid part of the original file / hash, and therefore if we can trust the content, and the supplying peer.

For example, given the very first chunk in a file, it will be only necessary to provide the hash of the adjacent siblings repeatedly to the top of the tree, to confirm that in fact the downloaded chunk is valid. In most cases the increased packet size to accommodate the additional hashes to verify a chunk will be very small.

Live Streaming

In the live streaming scheme, obviously, the root hash will continually shift along a sliding window. As the subsidiary or child hashes will largely remain the same, only a few additional hashes (munro hashes) will ultimately need to be re-calculated each time. By using a signed public key, the peers can be sure that the new root hash is in fact from a legitimate source, & untampered.

References

Full details are of course in the PPSPP specification.