trident/std/crypto/merkle.tri

module std.crypto.merkle

use vm.crypto.merkle

use vm.io.io

use vm.core.assert

// Verify a Merkle path of depth 1: single step from leaf to root.
pub fn verify1(leaf: Digest, root: Digest, leaf_idx: U32) {
    let (d0, d1, d2, d3, d4) = leaf
    let (_, computed) = merkle.step(leaf_idx, d0, d1, d2, d3, d4)
    assert.digest(computed, root)
}

// Verify a Merkle path of depth 2: two steps from leaf to root.
pub fn verify2(leaf: Digest, root: Digest, leaf_idx: U32) {
    let (d0, d1, d2, d3, d4) = leaf
    let (idx1, node1) = merkle.step(leaf_idx, d0, d1, d2, d3, d4)
    let (n0, n1, n2, n3, n4) = node1
    let (_, computed) = merkle.step(idx1, n0, n1, n2, n3, n4)
    assert.digest(computed, root)
}

// Verify a Merkle path of depth 3: three steps from leaf to root.
// This is the exact depth of Neptune's transaction kernel MAST tree (8 leaves).
pub fn verify3(leaf: Digest, root: Digest, leaf_idx: U32) {
    let (d0, d1, d2, d3, d4) = leaf
    let (idx1, node1) = merkle.step(leaf_idx, d0, d1, d2, d3, d4)
    let (n0, n1, n2, n3, n4) = node1
    let (idx2, node2) = merkle.step(idx1, n0, n1, n2, n3, n4)
    let (m0, m1, m2, m3, m4) = node2
    let (_, computed) = merkle.step(idx2, m0, m1, m2, m3, m4)
    assert.digest(computed, root)
}

// Verify a Merkle path of depth 4 (16 leaves).
pub fn verify4(leaf: Digest, root: Digest, leaf_idx: U32) {
    let (d0, d1, d2, d3, d4) = leaf
    let (idx1, node1) = merkle.step(leaf_idx, d0, d1, d2, d3, d4)
    let (n0, n1, n2, n3, n4) = node1
    let (idx2, node2) = merkle.step(idx1, n0, n1, n2, n3, n4)
    let (m0, m1, m2, m3, m4) = node2
    let (idx3, node3) = merkle.step(idx2, m0, m1, m2, m3, m4)
    let (p0, p1, p2, p3, p4) = node3
    let (_, computed) = merkle.step(idx3, p0, p1, p2, p3, p4)
    assert.digest(computed, root)
}

// Authenticate a leaf value against a known root and return the leaf digest.
// Divines the leaf hash, verifies its Merkle path (depth 3), returns the leaf.
pub fn authenticate_leaf3(root: Digest, leaf_idx: U32) -> Digest {
    let leaf: Digest = io.divine5()
    verify3(leaf, root, leaf_idx)
    leaf
}

// Verify a Merkle path of variable depth (up to 64 levels).
// Tree depth is a runtime value — the loop executes exactly `depth` steps.
pub fn verify(leaf: Digest, root: Digest, leaf_idx: U32, depth: Field) {
    let (d0, d1, d2, d3, d4) = leaf
    let mut idx: U32 = leaf_idx
    let mut n0: Field = d0
    let mut n1: Field = d1
    let mut n2: Field = d2
    let mut n3: Field = d3
    let mut n4: Field = d4
    let mut computed: Digest = leaf
    for i in 0..depth bounded 64 {
        let (new_idx, node) = merkle.step(idx, n0, n1, n2, n3, n4)
        let (m0, m1, m2, m3, m4) = node
        idx = new_idx
        n0 = m0
        n1 = m1
        n2 = m2
        n3 = m3
        n4 = m4
        computed = node
    }
    assert.digest(computed, root)
}

// Authenticate a leaf at variable depth. Divines the leaf, verifies
// its Merkle path against the root, returns the authenticated leaf.
pub fn authenticate_leaf(root: Digest, leaf_idx: U32, depth: Field) -> Digest {
    let leaf: Digest = io.divine5()
    verify(leaf, root, leaf_idx, depth)
    leaf
}