Crypto

In this section, we’re going to discuss hash pointers​ and their applications. A hash pointer is a data
structure that turns out to be useful in many of the systems that we will talk about. A hash pointer is
simply a pointer to where some information is stored together with a cryptographic hash of the
information. Whereas a regular pointer gives you a way to retrieve the information, a hash pointer
also gives you a way to verify that the information hasn’t changed.

Block chain

​ In Figure 1.5, we built a linked list using hash pointers. We’re going to call this data
structure a block chain​. Whereas as in a regular linked list where you have a series of blocks, each
block has data as well as a pointer to the previous block in the list, in a block chain the previous block
pointer will be replaced with a hash pointer. So each block not only tells us where the value of the
previous block was, but it also contains a digest of that value that allows us to verify that the value
hasn’t changed. We store the head of the list, which is just a regular hash-pointer that points to the
most recent data block
Another useful data structure that we can build using hash pointers is a binary tree. A
binary tree with hash pointers is known as a Merkle tree​, after its inventor Ralph Merkle. Suppose we
have a number of blocks containing data. These blocks comprise the leaves of our tree. We group
these data blocks into pairs of two, and then for each pair, we build a data structure that has two hash
pointers, one to each of these blocks. These data structures make the next level up of the tree. We in
turn group these into groups of two, and for each pair, create a new data structure that contains the
hash of each. We continue doing this until we reach a single block, the root of the tree