Permission Tree

The permission tree is a SHA-256 Merkle tree that accumulates withdrawal claims from exit actions. It bridges the ZK proof (which commits the tree root) to the on-chain permission script (which verifies individual claims).

Lifecycle

flowchart LR
    subgraph Guest["ZK Guest"]
        EXIT1["Exit action 1<br/>spk₁, amount₁"]
        EXIT2["Exit action 2<br/>spk₂, amount₂"]
        BUILD["StreamingPermTreeBuilder"]
        ROOT["Permission root"]
        REDEEM["Build permission<br/>redeem script"]
        HASH["blake2b(redeem)<br/>→ spk_hash"]
        JOURNAL["Write to journal"]
    end

    subgraph OnChain["On-Chain"]
        STATE["State verification script<br/>verifies spk_hash in journal"]
        PERM_UTXO["Permission UTXO<br/>(P2SH of redeem)"]
        CLAIM["Permission script<br/>verifies Merkle proof"]
        WITHDRAW["Withdrawal output"]
    end

    EXIT1 --> BUILD
    EXIT2 --> BUILD
    BUILD --> ROOT
    ROOT --> REDEEM
    REDEEM --> HASH
    HASH --> JOURNAL
    JOURNAL --> STATE
    STATE -->|"spawns"| PERM_UTXO
    PERM_UTXO --> CLAIM
    CLAIM --> WITHDRAW

Leaf hashing

Each exit action produces one leaf:

#![allow(unused)]
fn main() {
/// Compute the hash of a permission leaf: sha256("PermLeaf" || spk_bytes || amount_le_bytes)
pub fn perm_leaf_hash(spk: &[u8], amount: u64) -> [u32; 8] {
    let mut hasher = sha2::Sha256::new_with_prefix(PERM_LEAF_DOMAIN);
    hasher.update(spk);
    hasher.update(amount.to_le_bytes());
    let result: [u8; 32] = hasher.finalize().into();
    crate::bytes_to_words(result)
}
}

The SPK is variable-length (34 or 35 bytes depending on address type). The amount is encoded as 8-byte little-endian.

Tree depth

The tree depth is variable based on the number of exits:

#![allow(unused)]
fn main() {
/// Compute the required depth for a given leaf count.
/// Returns `ceil(log2(count))`, minimum 1, maximum `PERM_MAX_DEPTH`.
pub fn required_depth(count: usize) -> usize {
    if count <= 1 {
        return 1;
    }
    let bits = usize::BITS - (count - 1).leading_zeros();
    (bits as usize).min(PERM_MAX_DEPTH)
}
}

Maximum depth is 8 (256 leaves), matching the account SMT capacity.

Padding to depth

The streaming builder produces a root whose effective depth is ceil(log2(leaf_count)). If the target depth is larger, empty subtrees are appended on the right:

#![allow(unused)]
fn main() {
/// Pad a streaming builder result up to a target depth.
///
/// The streaming builder produces a root whose effective depth is
/// `ceil(log2(leaf_count))`. If `target_depth` is larger, we need to
/// extend with empty subtrees on the right.
pub fn pad_to_depth(mut hash: [u32; 8], leaf_count: u32, target_depth: usize) -> [u32; 8] {
    if leaf_count == 0 {
        return perm_empty_subtree_hash(target_depth);
    }
    let effective_depth = required_depth(leaf_count as usize);
    for level in effective_depth..target_depth {
        hash = perm_branch_hash(&hash, &perm_empty_subtree_hash(level));
    }
    hash
}
}

Streaming builder

The permission tree uses the same StreamingMerkle<H> generic builder as the sequence commitment tree, but parameterized with SHA-256 permission-tree hash operations:

#![allow(unused)]
fn main() {
/// Permission tree proof: variable-depth array of siblings + leaf index.
///
/// Max depth is 8 (256 leaves). Siblings are stored from leaf (level 0)
/// to root (level depth-1).
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct PermProof {
    /// Sibling hashes from leaf to root
    pub siblings: [[u32; 8]; PERM_MAX_DEPTH],
    /// Number of valid siblings (= tree depth)
    pub depth: usize,
    /// Leaf index in the tree
    pub index: usize,
}

impl PermProof {
    /// Create a new proof
    pub fn new(siblings: [[u32; 8]; PERM_MAX_DEPTH], depth: usize, index: usize) -> Self {
        Self { siblings, depth, index }
    }

    /// Compute the root from a leaf hash using this proof
    pub fn compute_root(&self, leaf_hash: &[u32; 8]) -> [u32; 8] {
        let mut current = *leaf_hash;
        for level in 0..self.depth {
            let bit = (self.index >> level) & 1;
            if bit == 0 {
                current = perm_branch_hash(&current, &self.siblings[level]);
            } else {
                current = perm_branch_hash(&self.siblings[level], &current);
            }
        }
        current
    }

    /// Verify that a leaf with given hash exists at this proof's index under given root
    pub fn verify(&self, root: &[u32; 8], leaf_hash: &[u32; 8]) -> bool {
        self.compute_root(leaf_hash) == *root
    }

    /// Compute a new root after replacing the leaf at this proof's index.
    /// Uses the same siblings and index, just a different leaf hash.
    pub fn compute_new_root(&self, new_leaf_hash: &[u32; 8]) -> [u32; 8] {
        self.compute_root(new_leaf_hash)
    }
}
}

Guest builds the permission script

After all blocks are processed, if any exits occurred:

1. The host provides the expected redeem script length (private input)
2. Guest computes required_depth(perm_count)
3. Guest finalizes the streaming builder and pads to depth
4. Guest builds the entire permission redeem script in no_std (see core/src/permission_script.rs)
5. Guest asserts the script length matches the host-provided value
6. Guest computes blake2b(redeem_script) → script_hash
7. Guest writes the script hash to the journal

The host-provided length is needed because the script embeds its own length (self-referential). The guest builds the script once and asserts — it does not iterate. The host must have converged the length beforehand.

On-chain usage

The state verification script checks if CovOutCount == 2. If so, it verifies that the second covenant output’s P2SH script hash matches the journal’s permission_spk_hash. This spawns a permission UTXO that can be spent by the permission script (see Chapter 9).

The permission script embeds the root and unclaimed count. Each withdrawal claim walks the Merkle tree twice (old root verification + new root computation) and updates the embedded state.