# Merkle Trees

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 *a _{i},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 a

_{10}.In a Merkle tree, the intermediate nodes are computed as the hash of their respective child nodes; namely a

_{i+1},j

*= H(a*, a

_{ij2}j_{ii2j}-

_{+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, a

_{30}is referred to as the Merkle root and commits to all leaf elements U

_{0},

*..., U*To prove the membership of element U

_{7}._{3 }(highlighted in Figure 3.1) in the root a

_{30}, intermediate nodes

*a*a

_{02},_{10}, and

*a*(highlighted in ovals in Figure 3.1) are needed. We say that these nodes form the sibling path of U

_{21 }_{3}. 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*.

n_{M} ^ Prove_{M} (X, x). Given a set X and element *x e X*, this algorithm outputs a proof of membership n_{M} asserting that x e X. n_{M} consists of the sibling path of x in the modified Merkle tree and the root *a _{e},_{0}.*

Verify_{M}(S, x, n_{M}). 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

*a*

_{e},_{0}.# ECDSA

Bitcoin currently relies on the Elliptic Curve Digital Signature Algorithm (ECDSA) with the secp256k1 curve [3]. 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 [3].