Merkle Trees
Notation
Orientation
A tree is always visualised as a "triangle" with its point at the top (the root) and its base at the bottom (the leaves). Like this: .
Hopefully this gives a clear intuition whenever the terms "left", "right", "up", "down", "above", "below" are used when describing trees.
Arity
Trees in Aztec are currently all binary Merkle trees (2-ary).
Height
The height
of a tree with leaves is .
Layers
The layers
of a tree are an enumerated from 0
. The leaves are at layer 0
; the root is at layer height
.
Levels
Synonymous with layers.
Rows
Synonymous with layers and levels.
Leaf Index
The leaves of a tree are indexed from 0
. The first, left-most leaf is at leaf_index = 0
.
Node Index
All nodes of the tree (including the leaves) can be indexed. The method of indexing might depend on the algorithm being applied to the tree.
Path
The path from (or "of") a particular node is a vector of that node's ancestors. That is, the node's parent, then its parent's parent, and so on, all the way up to and including the root.
Sibling Path
The sibling path of a particular node is, loosely, a vector of the siblings of the nodes in its path, except it also includes the node's sibling, and excludes the root (which has no sibling). The first element in the sibling path is the node's sibling. Then, the node's parent's sibling, then its parent's parent's sibling, and so on.
Membership Witness
The membership witness for a particular leaf, is the minimum data needed to prove that leaf value's existence in the tree. That is:
- The leaf's leaf index
- The leaf's sibling path
(and the leaf value itself, of course, but we don't include that in this "membership witness" definition).
Hashing
Used for computing the parent nodes of all merkle trees.
enum TreeId {
Archive,
NoteHash,
Nullifier,
PrivateFunction,
L1ToL2Msgs,
PublicData
}
fn merkle_crh(
tree_id: TreeId,
layer: u64,
left: Field,
right: Field
) -> Field {
let tree_id_domain_separator: string = match tree_id {
TreeId::Archive => "archive",
TreeId::NoteHash => "note_hash",
TreeId::Nullifier => "nullifier",
TreeId::PrivateFunction => "private_function",
TreeId::L2ToL2Msgs => "l1_to_l2_msgs",
TreeId::PublicData => "public_data",
};
let merkle_domain_separator: string = "az_merkle" + tree_id_domain_separator;
let parent = poseidon2(
be_string_to_field(merkle_domain_separator),
int_to_field(layer),
left,
right
);
parent
}
tree_id
reflects the various trees in the protocol. ThePrivateFunction
tree is discussed in the contract classes section.layer
is the layer of theleft
andright
children being hashed. For example, when hashing two leaves,layer = 0
.
- Q: Do we need the domain separator "az_merkle" + tree_id, for each of the trees?
- Q: do we need domain separation between different layers of the tree?
- Q: Can we optimise the two domain separators to take up 1 Field, instead of 2, or does squashing them together add too many constraints?
- Note: if it helps with optimisation, we can reduce the bit-length of the domain separator strings.
- Q: Can we specify the arguments to Poseidon as Fields, or do we need to specify them as bit-sequences?
Append-only Merkle Tree
TODO
Indexed Merkle Tree
TODO