Implement Tree, PartialTree and Witness

[meyer9]

These data types are for shard storage.

Data Types

• Tree → keeps track of a full Merkle tree
• Witness → keeps track of information needed to update a state root
• PartialTree → keeps track of updates to the tree and can calculate a state root if provided correct witnesses

Tree

• Tree.set(key: uint256, value: uint256)
  • Sets a key within the tree
• Tree.setWithWitness(key: uint256, value: uint256) → Witness
  • Sets a key within the tree and returns the witness needed to set the key given only the state root. Should be able to construct a new state root given the witness and the old root.
• Tree.get(key: uint256) → value: uint256
  • Gets a key from the tree
• Tree.delete(key: uint256)
  • Deletes a key from the tree
• Tree.deleteWithWitness(key: uint256) → Witness
  • Deletes a key from the tree and returns the witness needed to delete the key given only the state root. Should be able to construct a new state root given the witness and the old root.
• Tree.proveKey(key: uint256) → Witness
  • Generates a witness that proves that a key equals the value provided.
• Tree.hash() → uint256
  • Finds the hash of the tree.

Partial Tree

PartialTrees are not really trees. They're simply the state root and witnesses. The witnesses allow certain parts of the tree to be updated or verified.

• PartialTree.new(stateRoot: uint256, witnesses: \[Witness\])
  • Initializes a partial tree given the state root and a list of witnesses
• PartialTree.set(key: uint256, value: uint256) → Error
  • Sets a key in the merkle tree or returns an error if the witnesses provided do not provide enough information to set the key.
• PartialTree.delete(key: uint256) → Error
  • Deletes a key from the merkle tree or returns an error if the witnesses provided do not provide enough information to delete the key.
• PartialTree.verify(key: uint256, value: uint256) → Error
  • Verify a key in the merkle tree or return an error if the witnesses provided doesn't provide enough information to verify the key.
• PartialTree.hash() → (uint256, Error)
  • Calculates new hash of the Merkle tree.
  • This applies all of the updates from set or verify and calculates a new state root using the witnesses provided.

Witness

Witnesses are trees that detail certain parts of the tree. Witnesses do not have to contain the whole tree, but just certain branches needed to update information about the tree or verify information about the tree. Partial trees only contain leaf nodes (values) if the verifier needs to verify a key, but not if they just need to update the key.

• Witness.compress(witnesses: \[Witnesses\]) → Witness
  • Because some information in witnesses are duplicated, we should be able to compress witnesses by combining them. For example, a single branch would just be a list of hash values, but if two branches share 5 of the same nodes, we can compress them by including the 5 common nodes only once.

Example Code

tree = Tree()

tree.set(1, 1)
tree.set(2, 2)
tree.set(3, 3)
tree.set(4, 4)

hashTree0 = tree.hash()

witnesses = []
witnesses.append(tree.setWithWitness(1, 2))
witnesses.append(tree.setWithWitness(2, 3))
witnesses.append(tree.deleteWithWitness(3))
witnesses.append(tree.proveKey(4))

hashTree1 = tree.hash()

partialTree = PartialTree(hashTree0, witnesses)
partialTree.set(1, 2)
partialTree.set(2, 3)
partialTree.delete(3)

assert partialTree.verify(4, 4)

assert partialTree.hash() == hashTree1

partialTree.set(3, 4) # error: no witness for setting key 3
partialTree.delete(4) # error: no witness for deleting key 4
partialTree.verify(4, 5) # error: no witness proving key 4 is set to 5

Diagram

This is a diagram to explain how updating/verifying keys should work.

Currently, the tree root can be calculated by calculating: (using x = 1)

l0 = hash(x || 2)
l1 = hash(l0 || l0_sibling)
root = hash(l1 || l2_sibling)

We can prove 1 is in the root by verifying that when 1 is plugged in for x, the state root is returned.

We can also update the tree by changing 1 to another value, yielding a new state root.

The PartialTree should also keep track of changed values which should take priority over proving in the tree. Because the state root will be different after modifying the tree at all, proving will have to use the original state root. Proving a value that was not modified will obviously verify. Proving a value that was modified will verify because the modified value is cached.

In the diagram above, the yellow node is the node to update/verify and the red nodes are the witnesses needed.

The witness tree should store witnesses on the opposite branch to where they actually are in the tree. In the example above, the witnesses are all on the right branch on the tree. The witness tree should actually store them on the left branches of the tree. (Hopefully this doesn't conflict with how a CSMT is defined).