HDS uses various kinds of Merkle trees and proofs.

There are 2 kinds of proofs used:

• Standard proofs. Consists of an array of hashes, with the flag that specifies the hashing direction (left/right)
• Hard proofs. Consists only of hashes. The hashing direction (as long as the proof length) is deduced by the Verifier automatically.

Hard proofs are used where the client is aware of the supposed Merkle tree structure and the position of the needed element. Those proofs are not only a little smaller, but also more robust - they won't allow the Attacker to include different versions of the same element.

In addition there are combinations: a proof which begins as a standard proof, whereas for the suffix the client may deduce the hashing direction. More about this later.

MMR

Stands for Merkle Mountain Range, which is a fancy term to describe a (potentially) incomplete Merkle tree.

The underlying objects that are represented by the leaf nodes are converted to hashes according to a specific scheme applicable to the specific object kind (Means - Merkle trees in HDS never contain raw objects, to prevent possible ambiguity attacks).

The hashing used is SHA-256. Non-leaf node hashes are calculated according to

Hash ( Left-Child | Right->Child )

The tree fill order is left-to-right, whereas at each height two adjacent nodes form a parent node. This forms a sequence of complete trees of decreasing height (a.k.a. Mountain Range). Then adjacent trees are grouped from right to left, and form a mutual parent node, whose children are the roots of those trees. So it's like a regular Merkle tree, except the fact that the root node of the right child is "promoted" to the height of the left tree.

Note: in our implementation this promotion doesn't involve any actions, such as hashing with itself (which is used AFAIK in some implementations). This means that the proof length may vary for different elements.

Implementation details

The core MMR implementation is in Mmr abstract class. Contains the following virtual functions:

  vir