RACE #23 Of The Secureum Bootcamp Epoch∞

This is a mirror of a Write-Up on RACE-23, Quiz of the Secureum Bootcamp (opens in a new tab) for Ethereum Smart Contract Auditors. It was designed by Secureum Mentor Jon Stephens (opens in a new tab), from Veridise (opens in a new tab).

The original version of this document can be found at https://veridise.notion.site/veridise/RACE-23-Answers-d63cb0b5373f43f0ba43612e89596547 (opens in a new tab)

Participants of this quiz had to answer 8 questions within the strict time limit of 64 minutes on Zero Knowledge, Circom, and Merkle Trees. If you’re reading this in preparation for participating yourself, it’s best to give it a try under the same time limit!

Code

tree.circom

include "circomlib/circuits/poseidon.circom";
include "circomlib/circuits/bitify.circom";


template Mux() {
    signal input in[2];
    signal input s;
    signal output out[2];


    out[0] <-- (s == 0) ? in[0] : in[1];
    out[1] <-- (s == 0) ? in[1] : in[0];
}


template ComputeTreeRoot(nLevels) {
    signal input leaf;
    signal input indices[nLevels];
    signal input siblings[nLevels];


    signal output root;


    component muxes[nLevels];
    component hashers[nLevels];


    signal hashes[nLevels + 1];
    hashes[0] <-- leaf;


    for (var i = 0; i < nLevels; i++) {
        hashers[i] = Poseidon(2);
        muxes[i] = Mux();


        muxes[i].in[0] <== hashes[i];
        muxes[i].in[1] <== siblings[i];
        muxes[i].s <== indices[i];


        hashers[i].inputs[0] <== muxes[i].out[0];
        hashers[i].inputs[1] <== muxes[i].out[1];


        hashes[i + 1] <== hashers[i].out;
    }


    hashes[0] === leaf;
    root <== hashes[nLevels];
}

// treeAdd.circom


include "circomlib/circuits/poseidon.circom";
include "circomlib/circuits/bitify.circom";
include "./tree.circom";


template MerkleTreeAdd(nLevels) {
    signal input oldVal;
    signal input amount;
    signal input index;
    signal input siblings[nLevels];


    signal input oldRoot;
    signal output newRoot;
    signal output nullifier;


    component indexBits = Num2Bits(nLevels);
    indexBits.in <== index;


    component newRootCalc = ComputeTreeRoot(nLevels);
    component oldRootCalc = ComputeTreeRoot(nLevels);
    oldRootCalc.leaf <== oldVal;
    newRootCalc.leaf <== oldVal + amount;


    for (var i = 0; i < nLevels; i++) {
        oldRootCalc.siblings[i] <== siblings[i];
        oldRootCalc.indices[i] <== indexBits.out[i];
        newRootCalc.siblings[i] <== siblings[i];
        newRootCalc.indices[i] <== indexBits.out[i];
    }


    oldRootCalc.root === oldRoot;
    newRoot <== newRootCalc.root;


    component nullifierHash = Poseidon(1);
    nullifierHash.inputs[0] <== oldVal + amount;
    nullifier <== nullifierHash.out;
}


component main {public [oldRoot, index, amount]} = MerkleTreeAdd(32);
// treeSub.circom


include "circomlib/circuits/poseidon.circom";
include "circomlib/circuits/bitify.circom";
include "./tree.circom";


template MerkleTreeSub(nLevels) {
    signal input oldVal;
    signal input amount;
    signal input index;
    signal input siblings[nLevels];


    signal input oldRoot;
    signal output newRoot;
    signal output nullifier;


    component indexBits = Num2Bits(nLevels);
    indexBits.in <== index;


    component newRootCalc = ComputeTreeRoot(nLevels);
    component oldRootCalc = ComputeTreeRoot(nLevels);
    oldRootCalc.leaf <== oldVal;
    newRootCalc.leaf <== oldVal - amount;


    for (var i = 0; i < nLevels; i++) {
        oldRootCalc.siblings[i] <== siblings[i];
        oldRootCalc.indices[i] <== indexBits.out[i];
        newRootCalc.siblings[i] <== siblings[i];
        newRootCalc.indices[i] <== indexBits.out[i];
    }


    oldRootCalc.root === oldRoot;
    newRoot <== newRootCalc.root;


    component nullifierHash = Poseidon(1);
    nullifierHash.inputs[0] <== oldVal - amount;
    nullifier <== nullifierHash.out;
}


component main {public [oldRoot, index, amount]} = MerkleTreeSub(32);

// PrivateToken.sol


// SPDX-License-Identifier: MIT
pragma solidity ^0.8.15;


// Invokes verifier generated by snarkjs
interface IVerifier {
    function verifyAdd(uint256 oldRoot, uint256 index, uint256 amount, uint256 newRoot, uint256 nullifier, uint256[8] calldata proof) external returns (bool);
    function verifySub(uint256 oldRoot, uint256 index, uint256 amount, uint256 newRoot, uint256 nullifier, uint256[8] calldata proof) external returns (bool);
}


contract PrivateToken {
    mapping(uint256 => bool) usedNullifiers;
    uint256 public root;
    IVerifier verifier;
    address minter;


    struct OperationProof {
        uint256 oldRoot;
        uint256 index;
        uint256 amount;
        uint256 newRoot;
        uint256 nullifier;
        uint256[8] proof;
    }


    event Mint(uint256 oldRoot, uint256 index, uint256 amount, uint256 newRoot, uint256 nullifier);
    event Burn(uint256 oldRoot, uint256 index, uint256 amount, uint256 newRoot, uint256 nullifier);
    event Transfer(uint256 oldRoot, uint256 from, uint256 to, uint256 amount, uint256 newRoot, uint256 fromNullifier, uint256 toNullifier);


    constructor(address v, address m) {
        // root of tree with height of 32 and 0s for each leaf
        root = 19057105225525447794058879360670244229202611178388892366137113354909512903676;
        verifier = IVerifier(v);
        minter = m;
    }


    function burn(OperationProof calldata subProof) external {
        require(!usedNullifiers[subProof.nullifier]);
        usedNullifiers[subProof.nullifier] = true;
        root = subProof.newRoot;


        require(verifier.verifySub(subProof.oldRoot, subProof.index, subProof.amount, subProof.newRoot, subProof.nullifier, subProof.proof));


        emit Burn(subProof.oldRoot, subProof.index, subProof.amount, subProof.newRoot, subProof.nullifier);
    }


    function mint(OperationProof calldata addProof) external {
        require(msg.sender == minter);
        require(!usedNullifiers[addProof.nullifier]);
        usedNullifiers[addProof.nullifier] = true;
        root = addProof.newRoot;


        require(verifier.verifyAdd(addProof.oldRoot, addProof.index, addProof.amount, addProof.newRoot, addProof.nullifier, addProof.proof));


        emit Mint(addProof.oldRoot, addProof.index, addProof.amount, addProof.newRoot, addProof.nullifier);
    }


    function transfer(OperationProof calldata addProof, OperationProof calldata subProof) external {
        require(addProof.amount == subProof.amount);
        require(!usedNullifiers[addProof.nullifier]);
        usedNullifiers[addProof.nullifier] = true;
        require(!usedNullifiers[subProof.nullifier]);
        usedNullifiers[subProof.nullifier] = true;


        require(verifier.verifyAdd(addProof.oldRoot, addProof.index, addProof.amount, addProof.newRoot, addProof.nullifier, addProof.proof));
        require(verifier.verifySub(subProof.oldRoot, subProof.index, subProof.amount, subProof.newRoot, subProof.nullifier, subProof.proof));


        require(addProof.oldRoot == subProof.newRoot || addProof.newRoot == subProof.oldRoot);
        uint256 oldRoot;
        if(addProof.oldRoot == subProof.newRoot) {
            oldRoot = subProof.oldRoot;
            root = addProof.newRoot;
        }
        else {
            oldRoot = addProof.oldRoot;
            root = subProof.newRoot;
        }


        emit Transfer(oldRoot, subProof.index, addProof.index, addProof.amount, root, subProof.nullifier, addProof.nullifier);
    }
}

Question 1 of 8

A call to PrivateToken.transfer may revert for which, if any, of the following reasons?

A. The current root does not match either addProof.oldRoot or subProof.oldRoot.
B. The amounts declared in addProof and subProof do not match.
C. A nullifier has been used in the past.
D. Either addProof or subProof does not verify.
E. None of the above

Solution

Correct Picks: B, C, D.

B, C and D all correspond to requires in burn, but there is no root check so A must be false

Question 2 of 8

Which, if any, of the following statements hold with respect to MerkleTreeAdd?

A. The MerkleTreeAdd circuit will only verify computations where MerkleTreeAdd.oldVal is in the merkle tree with root MerkleTreeAdd.oldRoot.
B. The MerkleTreeAdd circuit will only verify computations where the leaf is at the location given by MerkleTreeAdd.index in the merkle tree with root MerkleTreeAdd.oldRoot.
C. The MerkleTreeAdd circuit will only verify computations where the root calculated by ComputeTreeRoot matches MerkleTreeAdd.oldRoot.
D. The MerkleTreeAdd circuit will only verify computations where the sum of MerkleTreeAdd.oldVal and MerkleTreeAdd.amount are in the merkle tree with root MerkleTreeAdd.newRoot.
E. None of the above

Solution

Correct Picks: C.

A is not correct because of the unconstrained mux.
B is not correct for the same reason.
C is correct because of a check in MerkleTreeAdd, which ensures the root matches.
D is not correct because of the unconstrained mux.

Question 3 of 8

Which, if any, of the following statements hold with respect to a user's balance?

A. The balance associated with a user's ID is private and cannot be known after funds have been allocated to it.
B. A user must know the balance associated with an ID to spend funds from it.
C. An index in the merkle tree is tied to a specific address so the associated balance corresponds to that address's balance.
D. If the root of the tree doesn't change, a user can always show that their balance is contained in the tree.
E. None of the above

Solution

Correct Picks: D.

There are two privacy leaks that allow someone to learn a user's balance, so A is not correct. B is not correct because of the unconstrained mux. C is not correct because there is no logic that ties an address to an index. D is correct because if the root has not changed, then someone's merkle proof must remain valid.

Question 4 of 8

Which, if any, of the following statements hold with respect to how a user's balance may change?

A. Upon a burn, a user's balance will either decrease or remain the same.
B. Upon a mint, a user's balance will either increase or remain the same.
C. Upon a transfer, the sum of user balances stored in the tree is constant.
D. During a mint, burn and transfer, only the balances at the indicated indices will change.
E. None of the above

Solution

Correct Picks: E.

None of these hold since the balance values may overflow and the unconstrained mux.

Question 5 of 8

Which, if any, of the following signals are under-constrained (i.e. a signal may be assigned to at least two different values while keeping the circuit inputs constant)?

Solution

Correct Picks: A.

A is under-constrained because of the unconstrained mux. B is not under-constrained because of the === constraint at the end of the circuit. C is not underconstrained due to <==. Finally, D is not under-constrained since it is explicitly constrained to an input in MerkleTreeSub.

Question 6 of 8

Which, if any, of the following may occur during a burn?

A. A user may burn more funds than they own.
B. The new computed root will not be saved.
C. The balances stored in the merkle tree may be arbitrarily manipulated.
D. Every user can burn their entire balance.
E. None of the above

Solution

Correct Picks: A, C.

A holds due to the overflow.
B does not hold since burn does store the new root.
C holds due to the under-constrained mux.
D does not hold since the nullifier is tied to user balances, so only one user may have balance 0.

Question 7 of 8

With respect to the nullifier, which, if any, of the following statements hold?

A. The nullifier leaks information about a user's balance.
B. The nullifier will prevent users from submitting the same proof twice.
C. If a nullifier is used by some user, another user will likely not be affected.
D. The computed value of the nullifier is under-constrained.
E. None of the above

Solution

Correct Picks: A,B.

A holds because it hashes the balance directly and so if two nullifiers conflict, you have learned something about the balance of the user who used it previously.
B is correct since the same proof will result in the same balance and therefore the same nullifier.
C is not correct due to the issue identified in A.
D is not correct because the nullifier is explicitly constrained to be the hash of two input values.

Question 8 of 8

Which, if any, of the following correspond to potential attacks that can be used against the protocol?

Solution

Correct Picks: B, C, D.

As discussed in Q7, you cannot replay proofs so A is not correct.
B is correct due to the balance issue from Q6, someone can perform a Dos.
C is correct as there are under-constrained signals that impact the output of the circuit.
D is correct since since the balance add and sub may overflow.

← RACE #22 Of The Secureum Bootcamp Epoch∞RACE #24 Of The Secureum Bootcamp Epoch∞ →