zPass merkle tree size 8 program

// The 'zpass_merkle_8' program.
program zpass_merkle_8.aleo {
    // The ZPass record
    record ZPass {
        owner: address,
        issuer: address,
        root: field,
    }

    function get_merkle_tree(leaves_hashes: [field; 8]) -> (field, [field; 2], [field; 4]) {
        let third_level_nodes: [field; 4] = [
            Poseidon2::hash_to_field(leaves_hashes[0u8] + leaves_hashes[1u8]),
            Poseidon2::hash_to_field(leaves_hashes[2u8] + leaves_hashes[3u8]),
            Poseidon2::hash_to_field(leaves_hashes[4u8] + leaves_hashes[5u8]),
            Poseidon2::hash_to_field(leaves_hashes[6u8] + leaves_hashes[7u8]),
        ];

        let second_level_nodes: [field; 2] = [
            Poseidon2::hash_to_field(third_level_nodes[0u8] + third_level_nodes[1u8]),
            Poseidon2::hash_to_field(third_level_nodes[2u8] + third_level_nodes[3u8]),
        ];

        let root_hash: field = Poseidon2::hash_to_field(second_level_nodes[0u8] + second_level_nodes[1u8]);

        return (root_hash, second_level_nodes, third_level_nodes);
    }
    
    // External function to get the merkle tree
    transition get_merkle(leaves_hashed: [field; 8]) -> (field, [field; 2], [field; 4]) {
        return get_merkle_tree(leaves_hashed);
    }

    transition issue(
        private sig: signature,
        private leaves_hashes: [field; 8],
        private issuer: address,
    ) -> ZPass {
        // Verify the first leaf is the issuer
        assert_eq(leaves_hashes[0u8], Poseidon2::hash_to_field(issuer));

        // Get the merkle tree
        let merkle_tree: (field, [field; 2], [field; 4]) = get_merkle_tree(leaves_hashes);

        // Verify signature against root 
        assert_eq(signature::verify(sig, issuer, merkle_tree.0), true);

        // Return the ZPass record and pass the commitment to store in the mapping
        return (ZPass {
            owner: self.caller,
            issuer: issuer,
            root: merkle_tree.0,
        });
    }

    transition verify(zpass: ZPass, leaf_hash: field, merkle_proof: [field; 3]) -> bool {
        let element: field = leaf_hash;

        for i: u8 in 0u8..3u8 {
            // Order does not matter because of the commutative property of group addition
            element = Poseidon2::hash_to_field(element + merkle_proof[i]);
        }
        assert_eq(element, zpass.root);
        return true;
    }
}

Overview

This program illustrates a design where credential fields (such as issuer, subject, date of birth, or any other fields) are first hashed into an array of leaf nodes. These leaves are then used to construct a Merkle tree, whose root is stored on-chain. The steps below outline the key components and their purposes:

1. ZPass Record

   • Defines the core information of a zPass credential in this example:

     • owner: The address of the credential holder (the caller who receives the zPass).

     • issuer: The address of the entity issuing the credential.

     • root: The Merkle root representing the hashed credential data.

2. get_merkle_tree Function

   • Given an array of eight hashed leaves ([field; 8]), it constructs a small, fixed-depth Merkle tree.

   • It returns the Merkle tree root, the second-level nodes, and the third-level nodes (leaf hashes aggregated two-by-two).

3. get_merkle Transition

   • Externally callable function that returns the Merkle tree structure (root, second-level nodes, third-level nodes) for the given leaves.

   • Primarily a convenience transition for on-chain callers who need to compute or verify the Merkle tree within the same program.

4. issue Transition

   • Responsible for issuing a ZPass record.

   • It takes three parameters:

     • sig: A private signature proving the issuer’s authority.

     • leaves_hashes: An array of eight hashed fields that collectively form the credential data.

     • issuer: The address of the credential issuer.

   • Validates that:

     1. The first leaf belongs to the issuer.

     2. The issuer’s signature correctly verifies against the computed Merkle root.

   • Once validated, it generates a new ZPass record where root corresponds to the Merkle root of the hashed leaves.

5. verify Transition

   • Enables verification that a single leaf was indeed part of the Merkle tree used to create the ZPass record.

   • Takes:

     • zpass: The existing ZPass record to verify against.

     • leaf_hash: The individual hashed leaf.

     • merkle_proof: The array of sibling nodes needed to recompute the path up to the Merkle root.

   • Performs step-by-step hashing with the sibling proofs until it reconstructs and checks it against the zpass.root.

---

How It Works

1. Hashing & Leaf Construction:

   • Before calling issue, developers must hash each credential field and store the results in an 8-element array ([field; 8]).

2. Merkle Root Generation & Signature:

   • Inside issue, the program calls get_merkle_tree to derive the Merkle root.

   • The issuer signs this root off-chain, and the signature (sig) is verified on-chain to confirm authenticity.

3. ZPass Creation:

   • Upon verification, the program returns a new ZPass record containing the owner, issuer, and the computed root.

4. Verification:

   • The verify transition confirms that a specific leaf (e.g., a hashed credential field) is part of the ZPass root.

   • It reconstructs the path with the supplied merkle_proof and ensures the resulting hash matches the ZPass root.