Merkle (Patricia) proof interface and implementation

[slowli]

Merkle (Patricia) tree proofs essentially prove that a certain element (or several elements) belongs to a certain data collection (list in the case of Merkle trees; map in the case of MPTs). Essentially, a MTs and MPTs are views of lists or maps, in which some elements are unknown. So, it could be logical to implement them as such.

Interface

Thus, it could be logical to have the following interface for MTs and MPTs:

• constructor(json): creates an MT or MPT based on JSON retrieved from the server. Verifies the internal structure of the tree (see below) and throws TypeError if the provided JSON is invalid
• hash(): returns the hash of the collection, calculated as per the current algorithm
• [MT only?] length (read-only property): returns the length of the underlying collection
• get(index): gets the element at the specified index (integer for MTs, Hash in the case of MPTs). Returns undefined if the element was not in the provided JSON
• has(index): returns true if the requested index is in the collection view, false otherwise
• [MPT only?] maybeHas(index): returns true if the specified index may be present in the collection (not necessarily in the current view). Hence, the proof of absence for index is !view.maybeHas(index).
• Symbol.iterator and entries(): returns the iterator for [index, value] pairs in the view, like the JS Map (maybe, pull other methods from Map too, e.g., forEach, keys and values).

Internal construction

Merkle tree

Recursive definition:

MT<ItemType> = oneOf({
  stub: Hash, // "collapsed" part of the tree
  branch: { left: MT<ItemType>, right: MT<ItemType> },
  sprout: { child: MT<ItemType> }, // a non-branching intermediate node 
  val: ItemType, // value
});

ListView<ItemType> = {
  root: MT<ItemType>,
  length: Uint64
};

Consistency checks:

• All values are at the depth expected by length
• All stubs are at the depth not exceeding the same depth
• The left child in any branch cannot be a sprout
• (optional) The tree must be non-redundant, e.g., a branch cannot have both stub children

Methods:

• get(index) can be implemented by traversing the tree from the root
• hash() can be implemented by traversing the tree from the leaves

Merkle Patricia tree

Recursive definition:

MPT<ItemType> = {
  bits: BitSlice, // key bits connecting the node to its parent
  node: oneOf({
    stub: Hash, // "collapsed" part of the tree
    branch: { left: MPT<ItemType>, right: MPT<ItemType> },
    val: ItemType // value
  })
};

MapView<ItemType> = MPT<ItemType>;

bits may be woven into all type variants if deemed necessary.

Consistency checks:

• bits may be empty only for the root node
• For branches, left.bits must start with 0 and right.bits with 1
• Key length of all values must be as expected (256 bits)
• Key length of all stubs must not exceed 256 bits
• (optional) The tree must be non-redundant, e.g., a branch cannot have both stub children

Methods:

• get(index) and maybeHas(index) can be implemented by traversing the tree from the root
• hash() can be implemented by traversing the tree from the leaves

[slowli]

@boguslavsky @defuz @gisochre Are you OK with this interface? Maybe, ListView or MapView need to have other methods? As for JSON for constructors, I see it slightly more verbose than it is currently, in order to be parseable within generic Exonum type spec:

ListView (3 items, proofs for 1st and 3rd):

{
  "root": {
    "@type": "branch",
    "left": {
      "@type": "branch",
      "left": {
        "val": ...
      },
      "right": {
        "stub": "abcdef..."
      }
    },
    "right": {
      "@type": "sprout",
      "child": {
        "val": ...
      }
    }
  },
  "length": 3
}

MapView (proof for key 01101...; the bits field is embedded into variants):

{
  "@type": "branch",
  "bits": "",
  "left": {
    "@type": "branch",
    "bits": "0",
    "left": {
      "stub": {
        "bits": "01",
        "hash": "..."
      }
    },
    "right": {
      "val": {
        "bits": "1101...",
        "item": ...
      }
    }
  },
  "right": {
    "stub": {
      "bits": "1",
      "hash": "..."
    }
  }
}

This assumes that oneOf can be encoded either as {<tag>: <value>} or {"@type": <tag>, ...<value>}.

As for implementation, it could be first implemented with custom JSON parsing logic, and then integrated into the Exonum type system.

[slowli]

I've implemented a PoC for type defs, which includes possibility of tree implementation, among other things. Very rough, but you probably get the general idea.