The Blockchain as a Data Structure

Overview

In the previous lessons, we considered the blockchain as a suite of technologies in order to outline its basic behavior. This lesson will introduces the blockchain as a data structure to comprehend the cryptographic background. We’ll show how transactions are collected and integrated into blocks. Furthermore, we’ll show the structure of blocks that serve as basic elements of the blockchain. We’ll then show how these blocks are linked together to form a chain that guarantees a chronological order of transactions. As we shall see, hash functions and Merkle trees play a key role in the construction of blockchain-based systems, as their change-sensitive behavior results in a structure that immediately detects any manipulations of transaction data, as we’ll show in this section (Daniel Drescher (2017)Daniel Drescher. Blockchain Basics: A Non-Technical Introduction in 25 Steps. Berkely, CA, 2017. Apress.).

Aggregating transactions

Until this step, we’ve seen that each node is able to aggregate transactions and place them in groups called blocks, but we did not describe how this is done. A naive approach could be to store the incoming transactions in a list and to include them in a block then. But this approach has many disadvantages, i.e., it would be computationally expensive to verify if a transaction is stored in the corresponding block. There is also the need to store the transactions in a change-sensitive manner, so any change in the transaction data can be detected instantly and easily, even if only a single transaction has been changed.

Therefore, the transactions are stored in a Merkle tree, as introduced in this lesson. Figure 1 shows four transactions that are stored in a Merkle tree of depth two. As we can see, the leaves $n_{00}, n_{01}, n_{10}$, and $n_{01}$ are computed directly as hashes of the corresponding transactions. Any node further up in the binary tree is then computed by concatenating and hashing its respective children, for example, $n_{0}=H\left(n_{00} \| n_{01}\right)$. The procedure is repeated until the root $r$ of the tree is computed, which is a single hash reference of the whole transaction data.

Figure 1