Merkle trees allow the combination of multiple input sequences in a hash tree converging into the topmost Merkle root hash. This data structure allows the compact representation of a set of transactions, such as when the tree is built up from the transaction hashes (see Figure 3.1). Merkle trees can be used to instantiate cryptographic accumulators, which answer a query whether a given candidate belongs to a set.
A Merkle tree is a binary tree in which the data is stored in the leaves. More specifically, given a tree of height t, a Merkle tree accumulates elements of a set X by assigning these to the leaf nodes (starting from position 0). Let ai,j denote a node in the tree located at the ith level and jth position. Here, the level refers to the distance (in hops) to the leaf nodes; clearly, leaf nodes are located at distance 0. On the other hand, the position within a level is computed incrementally from left to right starting from position 0; for example, the leftmost node of level 1 is denoted by a10 .In a Merkle tree, the intermediate nodes are computed as the hash of their respective child nodes; namely ai+1,j = H(aij2j, aii2j-+1), where H(X) refers to the cryptographic hash of X. Figure 3.1 depicts an example of a Merkle tree accumulating eight elements. Here, a30 is referred to as the Merkle root and commits to all leaf elements U0,..., U7. To prove the membership of element U3 (highlighted in Figure 3.1) in the root a30, intermediate nodes a02, a10, and a21 (highlighted in ovals in Figure 3.1) are needed. We say that these nodes form the sibling path of U3. Given n leaves, Merkle trees require O(n) for constructing the tree and O(log(n)) to prove membership of any element in the tree.
Formally, a Merkle tree comprises the following algorithms:
S ^ Acc(X). This algorithm accumulates the elements of a set X into a digest S. Here, S corresponds to the root node (i.e., S = a^0). This can be used to prove that the exact set X is correctly accumulated in S.
nM ^ ProveM (X, x). Given a set X and element x e X, this algorithm outputs a proof of membership nM asserting that x e X. nM consists of the sibling path of x in the modified Merkle tree and the root ae,0.
VerifyM(S, x, nM). Given S, an element x, its sibling path and the root a^0, this algorithm outputs true if and only if S = a^,0 where l is the length of the sibling path and the sibling path of x matches the root ae,0.
Bitcoin currently relies on the Elliptic Curve Digital Signature Algorithm (ECDSA) with the secp256k1 curve . ECDSA is a variant of the Digital Signature Algorithm (DSA) that uses elliptic curve cryptography. The required secp256k1 private keys have a length of 256 bits and can be transformed (deterministically) into the corresponding secp256k1 public keys. Additional details on ECDSA can be found in .