Merkle Interval Tree¶
Background¶
The Plasma Cashflow construction requires transactions that can efficiently reference ranges of state objects simultaneously. In order to preserve the properties of Plasma Cash, we require a Merkle tree structure that will not allow for the existence of two transactions that reference the same state object.
We provide a construction for such a tree, called a Merkle Interval Tree. This tree effectively commits to values that refer to corresponding ranges given by a start
and an end
. The tree provides the property that for any range, there can exist at most one leaf node that references the range and has a valid Merkle proof.
Tree Structure¶
The Merkle Interval Tree is a binary tree with special structures for leaf nodes and internal nodes.
Leaf Node¶
The leaf nodes in a Merkle Interval Tree represent a range and a value for that range. We describe leaf nodes as a tuple of (start, end, data)
.
In TypeScript:
interface MerkleIndexTreeLeafNode {
start: number
end: number
data: string
}
Internal Node¶
Internal nodes are a tuple of (index, hash)
.
In TypeScript:
interface MerkleIndexTreeInternalNode {
index: number
hash: string
}
Tree Generation¶
A Merkle Index tree is generated from a list of leaf nodes. Merkle Interval Tree generation also requires the use of a hash function. Any hash function is suitable, but the security properties of the hash function will impact the properties of the tree.
An algorithm for generating the tree is described below. All lists used are zero-indexed.
The algorithm takes two inputs, a list of leaf nodes and a hash function.
- If the list of leaf nodes is empty, return an empty array.
- Assert that the range described by
start
andend
of each leaf node does not intersect with the range described by any other leaf node. If any intersecting ranges exist, throw an error. - Sort the list of leaf nodes by their
start
value. - Store the list of leaf nodes as the first layer of the tree.
- Generate a corresponding sorted list of internal nodes from the leaf nodes by creating an internal for each leaf node such that:
- The
index
of the node is equal to thestart
of the leaf node. - The
hash
of the node is equal to the hash of the concatenation ofstart
,end
, anddata
of the leaf node, in that order.
- The
- Recursively generate the rest of the tree as follows:
- Store the list of internal nodes at the current height of the tree.
- If the list of internal nodes has only one element, return.
- Pair each node in the list of internal nodes such that any node where
node_index % 2 = 0
is paired with the node atnode_index + 1
. If the node atnode_index + 1
does not exist, pair the node with a new node such thatpair.index = node.index
andpair.hash = 0
. - Generate a list of parent nodes. For each pair of nodes, create a corresponding parent node such that:
parent.index = left_child.index
andparent.hash
is the hash of the concatenation ofleft_child.index
,left_child.hash
,right_child.index
,right_child.hash
, in that order.
- Repeat this process for the generated list of parent nodes.
- Return the generated tree.
Pseudocode¶
A pseudocode version of the above algorithm is given below:
def generate_tree(leaf_nodes, hash_function):
tree = []
# Empty tree
if len(leaf_nodes) == 0:
return tree
# Leaves intersect
for leaf in leaf_nodes:
for other in leaf_nodes:
if (intersects(leaf, other)):
raise Exception()
# Sort the leaves by start value
leaf_nodes.sort()
children = []
for leaf in leaf_nodes:
children.append({
'index': leaf.start,
'hash': hash_function(leaf.start + leaf.end + leaf.data)
})
def generate_internal_nodes(children, tree):
if len(children) == 1:
return tree
parents = []
for x in range(0, len(children)):
if x % 2 == 0:
left_child = chilren[x]
# Create an imaginary node if out of bounds
if x + 1 == len(children):
right_child = {
'index': left_child.index,
'hash': 0
}
else:
right_child = children[x + 1]
parents.append({
'index': left_child.index,
'hash': hash_function(left_child.index + left_child.hash + right_child.index + right_child.hash)
})
tree.append(parents)
return generate_internal_nodes(parents, tree)
Merkle Proofs¶
Our tree generation process allows us to create an efficient proof that for a given leaf node and a given Merkle Interval Tree root node such that:
- The leaf node was contained in the tree that generated the root.
- The range described by the leaf node intersects with no other ranges described by any other leaf node in the tree.
Proof Generation¶
Proofs can be generated after the full Merkle tree has been generated as per the algorithm described above. Proofs consist of a list of internal nodes within the Merkle tree.
The proof for a given leaf node is computed as follows:
- If the leaf node is not in the tree, throw an error.
- Find the internal node that corresponds to the leaf node in the bottom-most level of the tree.
- Recursively:
- If the internal node is the root node, return.
- Find the sibling of the node. If no sibling exists, set the sibling to the empty node such that
sibling.index = node.index
andsibling.hash = 0
. - Insert the sibling into the proof.
- Repeat this process with the parent of the node.
- Return the proof.
Pseudocode¶
def generate_proof(tree, leaf_node):
leaves = tree[0]
if leaf_node not in leaves:
raise Exception()
leaf_index = leaves.index(leaf_node)
return find_siblings(tree, 1, leaf_index, [])
def find_siblings(tree, height, child_index, proof):
if height == len(tree):
return proof
proof.append(get_sibling(child_index))
parent_index = get_parent_index(child_index)
return find_siblings(tree, height + 1, parent_index, proof)
Proof Verification¶
Verification of Merkle Interval Tree proofs is relatively straightforward. Given a leaf node, the index of that leaf node within the Merkle tree, a proof consisting of a list internal nodes, and the root of the tree:
- Compute the internal node that corresponds to the leaf node such that
node.index = leaf.start
andnode.hash
is the hash of the concatenation ofleaf.start
,leaf.end
, andleaf.data
, in that order. - For each element of the proof:
- Use the index of the leaf node to determine whether the element is a left or right sibling of the current internal node.
- Compute the parent of the two siblings.
- Set the current internal node to be the parent.
- Check if the current internal node is equal to the root node.
Pseudocode¶
def check_proof(leaf_node, leaf_index, proof, root_node, hash_function):
current_node = {
'index': leaf_node.start,
'hash': hash_function(leaf_node.start + leaf_node.end + leaf_node.data)
}
for x in range(0, len(proof)):
sibling = proof[x]
if is_left_sibling(leaf_index, x):
current_node = compute_parent(sibling, current_node)
else:
current_node = compute_parent(current_node, sibling)
return current_node == root_node
Tree Diagram¶
A diagram of the Merkle Interval Tree is provided below. We’ve highlighted the nodes that one would need to provide to prove inclusion of a given state update.