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.
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.
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)
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).
These data types are for shard storage.
Data Types
Tree
Tree.set(key: uint256, value: uint256)Tree.setWithWitness(key: uint256, value: uint256) → WitnessTree.get(key: uint256) → value: uint256Tree.delete(key: uint256)Tree.deleteWithWitness(key: uint256) → WitnessTree.proveKey(key: uint256) → WitnessTree.hash() → uint256Partial 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\])PartialTree.set(key: uint256, value: uint256) → ErrorPartialTree.delete(key: uint256) → ErrorPartialTree.verify(key: uint256, value: uint256) → ErrorPartialTree.hash() → (uint256, Error)setorverifyand 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\]) → WitnessExample Code
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)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
PartialTreeshould 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).