Merkle Tree
The core of Light Protocol is a Merkle tree program, and it's pda which store merkle tree state, and the funds deposited to the protocol.
The Merkle tree is used to prove that a utxo was created before. To do this a Merkle proof is proved in a zero knowledge proof Multi Asset Pool Circuit (Zero Knowledge Proof). This achieves anonymity because the zero knowlegde proof proves that a utxo is part of the merkle tree but it does not reveal which utxo it is.
This state is accessible to multiple system verifier programs. The merkle tree program trusts the system verifiers and does not enforce checks.
Merkle Tree:
- stores commitment hashes of utxos as it's leaves to enable zk set membership proofs
- is one Solana program which can instantiate new merkle trees
- the Merkle tree state is saved in a pda
- Merkle tree root is a public input to the zero knowledge proof
- tree height 18 -> 256k leaves
- always inserts pairs of leaves
- a leaves pda stores 2 commitment hashes, the Merkle tree public key, 256 bytes (can be used to store encrypted Utxos)
- append only, no inserts
- sparse Merkle tree, the original Merkle tree is initialized with zero values, only the zero values and the latest merkle proof is stored on chain.
- a new Merkle tree will be created when the current tree is full
Authority pda:
- defines an authority pubkey which can:
- register new verifiers
- register new pool types and tokens
- initialized new Merkle trees
- set permissions for new asset pool creation
- update lock duration for Merkle tree during updating
- keeps current highest index for assets and merkle trees to enable lookups of these
Registered Verifiers:
- are trusted by the Merkle tree
- the registered verifier pda is used enforce access control to leaves, nullifier insertion and asset transfer functions.
#[account(zero_copy)]
#[derive(Eq, PartialEq, Debug)]
pub struct MerkleTree {
pub filled_subtrees: [[u8; 32]; 18],
pub current_root_index: u64,
pub next_index: u64,
pub roots: [[u8; 32]; MERKLE_TREE_HISTORY_SIZE as usize],
pub pubkey_locked: Pubkey,
pub time_locked: u64,
pub height: u64,
pub merkle_tree_nr: u64,
pub lock_duration: u64,
}
Lock Duration:
Merkle tree updates need to be atomic, in other words happen completely or not at all. Only one actor should update the Merkle tree at the same time. The lock ensures that only one update can be in process at the same time.
Time locked:
The slot number the lock was taken by an update process. The program checks whether the current Solana slot is greater than time locked + lock duration to determine whether the tree is still locked. If the slot is greater than time locked + lock duration the lock expired.
Pubkey locked:
The verifier update state publickey which is used to store the temporary state during the merkle tree update.
Merkle tree nr:
Merkle trees are indexed to reduce storage needs for encrypted utxos.
Can be conducted by the user at deposit, but in general will be conducted by a relayer.
3 Steps:
- 1.initialize update state:
- creates the temporary state pda which will store the state of the computation necessary to compute the poseidon hashes to update the merkle tree
- copies sub trees from the merkle tree pda to the temporary state pda
- copies a batch of up to 16 leaves pdas to the temporary state
#[account(zero_copy)]
#[derive(Debug)]
pub struct MerkleTreeUpdateState {
// rust
pub relayer: Pubkey,
pub merkle_tree_pda_pubkey: Pubkey,
// state of the poseidon hasher
pub state: [u8; 96],
pub current_round: u64,
pub current_round_index: u64,
// state of the update algorithm
pub node_left: [u8; 32],
pub node_right: [u8; 32],
pub leaf_left: [u8; 32],
pub leaf_right: [u8; 32],
pub current_instruction_index: u64,
pub current_index: u64,
pub current_level: u64,
pub current_level_hash: [u8; 32],
// copied leaves
pub leaves: [[[u8; 32]; 2]; 16],
pub number_of_leaves: u8,
pub insert_leaves_index: u8,
// copied state of the merkle tree being updated (synced back in root insert)
pub tmp_leaves_index: u64,
pub filled_subtrees: [[u8; 32]; MERKLE_TREE_HEIGHT as usize],
}
- 2.compute:
- computes poseidon hashes and stores temporary state in the update state
- sends at least ~30 transactions, 3 instructions per poseidon hash 18 times (the height of the Merkle tree) + additional transactions for batch insertions
- 3.insert root:
- finalizes the merkle tree update by inserting the new root
- closes every leaves pda of the batch of leaves which have been inserted into the merkle tree now
- stores the data of every leaves pda in a compressed solana account
- closes the temporary state pda
- can be fetched from instruction data of successful shielded transactions
- Leaves are first queued in a pda see layout below.
- After the Merkle tree update queued leaves pdas are closed and leaves are saved in a compressed account instead.
#[account]
pub struct TwoLeavesBytesPda {
pub node_left: [u8; 32],
pub node_right: [u8; 32],
pub merkle_tree_pubkey: Pubkey,
pub encrypted_utxos: [u8; 256],
pub left_leaf_index: u64,
}
Last modified 6mo ago