Bench-ZK

The BatchMerkleCircuit verifies the final Merkle root by simulating the entire process of updating a Merkle tree based on a batch of transactions within the circuit: Inside circuit, it updates leaf states by applying B transactions and computes the new Merkle root from all N leaves.

// BatchMerkleCircuit verifies a batch of up to 32 transactions updating a Merkle tree.
type BatchMerkleCircuit struct {
        // Public inputs
        OldRoot      frontend.Variable `gnark:"oldRoot,public"`
        NewRoot      frontend.Variable `gnark:"newRoot,public"`
        Transactions [B]struct {
                LeafIndex     frontend.Variable `gnark:"leafIndex"`
                DepositAmount frontend.Variable `gnark:"depositAmount"`
        } `gnark:",public"`

        // Private inputs
        InitialLeaves [N]struct {
                Name frontend.Variable `gnark:"name"`
                Ben  frontend.Variable `gnark:"ben"`
        }
}

1. Initial State Verification:

   Computes the initial Merkle root from the provided initial leaves using the MiMC hash function. Ensures this matches the provided OldRoot.

2. Transaction Processing:

   For each transaction, updates the corresponding leaf balance by accumulating deposits.

3. Final State Verification:

   Applies accumulated deposits to initial leaf balances to compute the final leaf states. Calculates the final Merkle root from these updated leaves using MiMC. Then asserts that the computed final root equals the provided NewRoot.

The ProofMerkleCircuit verifies a batch of B2 transactions that update user states in a Merkle tree with N2 = \(2^{D2}\) leaves, where D2 is the tree depth. Each leaf represents a user's state (name and balance). The circuit ensures that the Merkle root transitions correctly from an initial oldRoot to a final newRoot after processing all transactions, leveraging Merkle proofs for efficiency. Computations are split between off-circuit preparation and in-circuit verification.

// ProofMerkleCircuit verifies a batch of transactions updating a Merkle tree sequentially.
type ProofMerkleCircuit struct {
      // Public inputs
      OldRoot frontend.Variable `gnark:"oldRoot,public"`
      NewRoot frontend.Variable `gnark:"newRoot,public"`

        // Private inputs: B2 transactions
        Transactions [B2]struct {
                OldName    frontend.Variable     `gnark:"oldName"`
                OldBalance frontend.Variable     `gnark:"oldBalance"`
                NewName    frontend.Variable     `gnark:"newName"`
                NewBalance frontend.Variable     `gnark:"newBalance"`
                Siblings   [D2]frontend.Variable `gnark:"siblings"`
                PathBits   [D2]frontend.Variable `gnark:"pathBits"`
        }
}

Requires \(O(N)\) MiMC hashes in the circuit, where \(N\) is the number of leaves, which grows linearly with the number of leaves.

Proof generation time is dominated by \(O(N)\) MiMC hashes, with a minor contribution from \(O(B)\) batches operations.

Requires \(O(B \times D)\) MiMC hashes in the circuit, where \( D = \log N \). This is \(O(B \times \log N)\) complexity, far better than \(O(N)\) for large N2, though proof time grows with larger B2.

This table shows proof generation times when the Merkle tree has a fixed number of leaves (1024) and the batch size varies from 32 to 256.

This table presents proof generation times with a fixed batch size of 64, while the number of leaves varies from 16 to 32,768.

• For small leaf sizes (e.g., 16), BatchMerkleCircuit (0.040s) is significantly faster than ProofMerkleCircuit (0.524s).
• For larger leaf sizes (e.g., 4096), ProofMerkleCircuit (1.392s) outperforms BatchMerkleCircuit (6.027s).

• Effect of N:

  Time scales with \(O(N)\) due to the \(O(N)\) MiMC hashes required to compute leaf hashes and the Merkle root.

  For \(B=64\), as N increases from 16 to 4096 (256x increase), time rises from 0.040s to 6.027s (150x increase), roughly aligning with linear scaling, adjusted by constant factors and overheads.

• Effect of B:

  Time is largely independent of B in terms of MiMC hashes \((O(N))\), but \(O(N \times B)\) simple operations add overhead.

  For \(N=1024\), as B increases from 32 to 256 (8x), time grows from 1.586s to 2.374s (1.5x), indicating that the \(O(N \times B)\) term has a minor but noticeable impact.

• Observation: The dominant cost is \(O(N)\) MiMC hashes, making this circuit sensitive to leaf size but relatively insensitive to batch size.

• Effect of N:

  Time scales with \(\log N\) for fixed B.

  For \(B=64\), as N goes from 16 \((\log N = 4)\) to 4096 (\(\log N = 12\), a 3x increase), time increases from 0.524s to 1.392s (2.7x), roughly matching the logarithmic trend.

• Effect of B:

  Time scales linearly with B for fixed N.

  For \(N=1024 (\log N = 10)\), as B doubles from 32 to 64, time increases from 0.521s to 0.933s (1.8x); from 64 to 128, 0.933s to 1.840s (2x); and from 128 to 256, 1.840s to 3.562s (1.9x), confirming linear scaling with B.

• Observation: The \(O(B \times \log N)\) complexity makes this circuit sensitive to both batch size and tree depth, but the logarithmic dependence on N keeps growth slow as N increases.

• Small N, Large B: BatchMerkleCircuit outperforms.

  For example, for \(N=16\), \(B=64\), it takes 0.040s vs. 0.524s for ProofMerkleCircuit, as \(O(N)\) (16 hashes) is much less than \(O(B \times \log N)\) (64 * 4 = 256 hashes).

• Large N, Small B: ProofMerkleCircuit excels.

  For example, for \(N=4096\), \(B=64\), it takes 1.392s vs. 6.027s, since \(O(B \times \log N)\) (64 * 12 = 768 hashes) is far less than \(O(N)\) (4096 hashes).

• Crossover Point: ProofMerkleCircuit becomes slower when \(B \times \log N > N\)

  For \(N=1024\), \(\log N = 10\), crossover at \(B = 102\). Data shows at \(B=128\), ProofMerkleCircuit (1.840s) exceeds BatchMerkleCircuit (1.658s), aligning with this threshold.