merkle-tree.md

Merkle tree

Attestations for each voting round (hashes of the attested data) are assembled into a Merkle tree and only the Merkle root is used in voting. The Merkle root that is sent by the majority of attestation providers becomes the confirmed Merkle root for the round and is stored in the StateConnector contract.

For proving verifications of a specific voting round, it suffices to know whether an attestation hash of a specific attestation request has appeared (or was equivalently confirmed) in the voting round. To vote, attestation providers organize the submitted attestation hashes in a round as follows:

• They collect all the voting requests for a specific round and try to verify them.
• They exclude any requests that were not chosen in the choose phase by bit voting.
• The attestation hashes are calculated for the verified ones. No hashes are produced for the requests that are not verified.
• All verified attestation hashes are put in the list and sorted numerically, in ascending order, and duplicates are removed.
• The Merkle tree is built on those hashes as described below.

Merkle tree structure

A Merkle tree on n sorted hashes is represented by an array of length 2n - 1, which represents a complete binary tree. A complete binary tree is a binary tree in which all levels are completely filled except possibly the lowest one, which is filled from the left.

It can be easily proven by induction that a complete binary tree with 2n - 1 elements has exactly n leaves and all nodes are either leaves or have two descendants (left and right). For n = 1 there is a tree with only one element, the root and a leaf simultaneously. If two descendants are added to a single element tree, the result is a tree with 2 leaves but 3 = 2 x 2 - 1 elements. If two descendants are added to the leftmost leaf, it is converted to an internal node, effectively removing one leaf and adding two more leaves. The result is a complete binary tree that has all levels filled except maybe the last one, which is filled from the left. If nodes are enumerated from 0 starting with the root and proceeding through levels from the left to the right, then, to add a leaf to the tree, the leaf node with the lowest index needs to be expanded with two leaves, resulting in a complete binary tree with 2 more leaves and 1 more internal node.

The above-mentioned indexing enables us to represent a Merkle tree with n leaves in an array of exactly 2n - 1 length, where the last n elements are leaves. This representation of a complete binary tree is well known from classic implementation of binary heaps. It encodes the tree structure as follows:

• The Merkle root is at index 0.

• Leaves are on the last n indices, from n - 1 to 2n - 2.

• Given an index i of a node in the tree, the parent and both descendants are as follows:

  parent(i) = floor((i - 1)/2)
  left(i)   = 2*i + 1,      if 2*i + 1 < 2*n - 1
  right(i)  = 2*i + 2,      if 2*i + 2 < 2*n - 1.
  

• Since it is a complete binary tree, a sibling of the node with index i can easily be calculated with:

  sibling(i) = i + 2*(i % 2) - 1
  

Note that there are several types of Merkle trees, depending on their purpose. In general, a Merkle tree can be used to uniquely produce a representative hash for a fixed sequence of hashes or just for a set of hashes, if the order of appearance is not important.

For example, with Merkle trees for transactions in a block on the Bitcoin network the exact order of the transactions in the block is important, hence a fixed sequence Merkle tree is used. On Songbird, the order of votes (attestation hashes) is not important so a set Merkle tree is used. Namely, each successful vote is identified with a unique attestation hash (duplicates are removed). For later verification, one only needs to query whether such a hash has appeared among the hashes in the Merkle tree. On the other hand, in the Bitcoin transactions example, one needs to verify that the hash of a transaction is a leaf of the tree at a specific index.

In the case of a set of Merkle trees, additional simplification when performing hashes of pairs can be used. Such a simplification makes Merkle proofs shorter and easier to use. The hash that Songbird uses for pairs is defined as follows:

shash(data1, data2) = hash(join(sort([data1, data2])))

where hash(data) is a hash function that, given a byte sequence data, produces a 32-byte hash. sort(list) is the sorting function for a list of byte strings and join(list) is the function that concatenates byte strings to a single byte string in order of appearance.

Basically it means that given two hashes they are first sorted, then joined, and then a hash is produced.

Building a Merkle tree

Assume an attestation provider has performed all necessary verifications and obtained the necessary attestation hashes for the confirmed request m. Some requests may be duplicates, yielding duplicate verification hashes, and those can be safely removed. Hence, it can be assumed that the attestation provider has n unique attestation hashes. To build the Merkle tree, the attestation providers proceed as follows:

• n hashes are sorted in ascending order. Note that the order is unique.
• An array M with 2n - 1 elements is allocated.
• n hashes are put into the slots from n - 1 to 2n - 2, this is, M[n-1], ..., M[2n - 2].
• for i = n - 2 down to 0, calculate M[i] = shash( M[left(i)], M[right(i)])

Building a Merkle proof

A Merkle proof for a leaf is the shortest sequence of hashes in the Merkle tree on a path to the Merkle root that enables the calculation of the Merkle root from the leaf. Let M be an array representing a Merkle tree on n leaves with 2n - 1 nodes defined as above. Note that the attestation hashes appear on indices n-1 to 2n - 2 and are sorted. Hence the k-th hash appears on the index n - 1 + k. The Merkle proof for the k-th hash can be calculated by using the following pseudocode:

getProof(k) {
   if (n == 0 || k < 0 || k >= n) {
      return null;
   }
   let proof = [];
   let pos = n - 1 + k;
   while (pos > 0) {
      proof.push(M[sibling(pos)]);
      pos = parent(pos);
   }
   return proof;
}

For checking a Merkle proof, the following "standard" Open Zeppelin library can be used.

Hashing function

Given two attestation hashes a1 and a2, the Shash(a1, a2) function used in Solidity is defined as follows:

keccak256(a1 <= a2 ? abi.encode(a1, a2) : abi.encode(a2, a1));

Where variables a1 and a2 are of type bytes32.

In Java/Typescript, the following code using web3.js produces the same result:

web3.utils.soliditySha3(
    web3.eth.abi.encodeParameters(
        ["bytes32", "bytes32"],
        a1 <= a2 ? [a1, a2] : [a2, a1]
    )
);

Where a1 and a2 are 0x-prefixed hex strings representing 32-bytes.

Or with ethers.js:

const coder = ethers.AbiCoder.defaultAbiCoder();
ethers.keccak256(
    coder.encode(["bytes32", "bytes32"], a1 <= a2 ? [a1, a2] : [a2, a1])
);

Back: Voting protocol | Bit-voting | Next: Branching protocol |

Home