Contract 0x4621EE309EAc747425F0FEd51931dDC241A27F49 4

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

import {PoseidonT3} from "./Hashes.sol";

// Each incremental tree has certain properties and data that will
// be used to add new leaves.
struct IncrementalTreeData {
    uint256 depth; // Depth of the tree (levels - 1).
    uint256 root; // Root hash of the tree.
    uint256 numberOfLeaves; // Number of leaves of the tree.
    mapping(uint256 => uint256) zeroes; // Zero hashes used for empty nodes (level -> zero hash).
    // The nodes of the subtrees used in the last addition of a leaf (level -> [left node, right node]).
    mapping(uint256 => uint256[2]) lastSubtrees; // Caching these values is essential to efficient appends.
}

/// @title Incremental binary Merkle tree.
/// @dev The incremental tree allows to calculate the root hash each time a leaf is added, ensuring
/// the integrity of the tree.
library IncrementalBinaryTree {
    uint8 internal constant MAX_DEPTH = 32;
    uint256 internal constant SNARK_SCALAR_FIELD =
        21888242871839275222246405745257275088548364400416034343698204186575808495617;

    /// @dev Initializes a tree.
    /// @param self: Tree data.
    /// @param depth: Depth of the tree.
    /// @param zero: Zero value to be used.
    function init(
        IncrementalTreeData storage self,
        uint256 depth,
        uint256 zero
    ) public {
        require(zero < SNARK_SCALAR_FIELD, "IncrementalBinaryTree: leaf must be < SNARK_SCALAR_FIELD");
        require(depth > 0 && depth <= MAX_DEPTH, "IncrementalBinaryTree: tree depth must be between 1 and 32");

        self.depth = depth;

        for (uint8 i = 0; i < depth; ) {
            self.zeroes[i] = zero;
            zero = PoseidonT3.poseidon([zero, zero]);

            unchecked {
                ++i;
            }
        }

        self.root = zero;
    }

    /// @dev Inserts a leaf in the tree.
    /// @param self: Tree data.
    /// @param leaf: Leaf to be inserted.
    function insert(IncrementalTreeData storage self, uint256 leaf) public {
        uint256 depth = self.depth;

        require(leaf < SNARK_SCALAR_FIELD, "IncrementalBinaryTree: leaf must be < SNARK_SCALAR_FIELD");
        require(self.numberOfLeaves < 2**depth, "IncrementalBinaryTree: tree is full");

        uint256 index = self.numberOfLeaves;
        uint256 hash = leaf;

        for (uint8 i = 0; i < depth; ) {
            if (index & 1 == 0) {
                self.lastSubtrees[i] = [hash, self.zeroes[i]];
            } else {
                self.lastSubtrees[i][1] = hash;
            }

            hash = PoseidonT3.poseidon(self.lastSubtrees[i]);
            index >>= 1;

            unchecked {
                ++i;
            }
        }

        self.root = hash;
        self.numberOfLeaves += 1;
    }

    /// @dev Updates a leaf in the tree.
    /// @param self: Tree data.
    /// @param leaf: Leaf to be updated.
    /// @param newLeaf: New leaf.
    /// @param proofSiblings: Array of the sibling nodes of the proof of membership.
    /// @param proofPathIndices: Path of the proof of membership.
    function update(
        IncrementalTreeData storage self,
        uint256 leaf,
        uint256 newLeaf,
        uint256[] calldata proofSiblings,
        uint8[] calldata proofPathIndices
    ) public {
        require(newLeaf != leaf, "IncrementalBinaryTree: new leaf cannot be the same as the old one");
        require(newLeaf < SNARK_SCALAR_FIELD, "IncrementalBinaryTree: new leaf must be < SNARK_SCALAR_FIELD");
        require(
            verify(self, leaf, proofSiblings, proofPathIndices),
            "IncrementalBinaryTree: leaf is not part of the tree"
        );

        uint256 depth = self.depth;
        uint256 hash = newLeaf;
        uint256 updateIndex;

        for (uint8 i = 0; i < depth; ) {
            updateIndex |= uint256(proofPathIndices[i]) << uint256(i);

            if (proofPathIndices[i] == 0) {
                if (proofSiblings[i] == self.lastSubtrees[i][1]) {
                    self.lastSubtrees[i][0] = hash;
                }

                hash = PoseidonT3.poseidon([hash, proofSiblings[i]]);
            } else {
                if (proofSiblings[i] == self.lastSubtrees[i][0]) {
                    self.lastSubtrees[i][1] = hash;
                }

                hash = PoseidonT3.poseidon([proofSiblings[i], hash]);
            }

            unchecked {
                ++i;
            }
        }
        require(updateIndex < self.numberOfLeaves, "IncrementalBinaryTree: leaf index out of range");

        self.root = hash;
    }

    /// @dev Removes a leaf from the tree.
    /// @param self: Tree data.
    /// @param leaf: Leaf to be removed.
    /// @param proofSiblings: Array of the sibling nodes of the proof of membership.
    /// @param proofPathIndices: Path of the proof of membership.
    function remove(
        IncrementalTreeData storage self,
        uint256 leaf,
        uint256[] calldata proofSiblings,
        uint8[] calldata proofPathIndices
    ) public {
        update(self, leaf, self.zeroes[0], proofSiblings, proofPathIndices);
    }

    /// @dev Verify if the path is correct and the leaf is part of the tree.
    /// @param self: Tree data.
    /// @param leaf: Leaf to be removed.
    /// @param proofSiblings: Array of the sibling nodes of the proof of membership.
    /// @param proofPathIndices: Path of the proof of membership.
    /// @return True or false.
    function verify(
        IncrementalTreeData storage self,
        uint256 leaf,
        uint256[] calldata proofSiblings,
        uint8[] calldata proofPathIndices
    ) private view returns (bool) {
        require(leaf < SNARK_SCALAR_FIELD, "IncrementalBinaryTree: leaf must be < SNARK_SCALAR_FIELD");
        uint256 depth = self.depth;
        require(
            proofPathIndices.length == depth && proofSiblings.length == depth,
            "IncrementalBinaryTree: length of path is not correct"
        );

        uint256 hash = leaf;

        for (uint8 i = 0; i < depth; ) {
            require(
                proofSiblings[i] < SNARK_SCALAR_FIELD,
                "IncrementalBinaryTree: sibling node must be < SNARK_SCALAR_FIELD"
            );

            require(
                proofPathIndices[i] == 1 || proofPathIndices[i] == 0,
                "IncrementalBinaryTree: path index is neither 0 nor 1"
            );

            if (proofPathIndices[i] == 0) {
                hash = PoseidonT3.poseidon([hash, proofSiblings[i]]);
            } else {
                hash = PoseidonT3.poseidon([proofSiblings[i], hash]);
            }

            unchecked {
                ++i;
            }
        }

        return hash == self.root;
    }
}

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

library PoseidonT3 {
    function poseidon(uint256[2] memory) public pure returns (uint256) {}
}

library PoseidonT6 {
    function poseidon(uint256[5] memory) public pure returns (uint256) {}
}

{
  "optimizer": {
    "enabled": false,
    "runs": 200
  },
  "outputSelection": {
    "*": {
      "*": [
        "evm.bytecode",
        "evm.deployedBytecode",
        "devdoc",
        "userdoc",
        "metadata",
        "abi"
      ]
    }
  },
  "libraries": {
    "@zk-kit/incremental-merkle-tree.sol/Hashes.sol": {
      "PoseidonT3": "0xe136abacf78e05988154ed85f4ea911105302595"
    }
  }
}

[]

611d68610053600b82828239805160001a607314610046577f4e487b7100000000000000000000000000000000000000000000000000000000600052600060045260246000fd5b30600052607381538281f3fe73000000000000000000000000000000000000000030146080604052600436106100565760003560e01c80630629596f1461005b5780631095fbb414610084578063168703fa146100ad578063a5478827146100d6575b600080fd5b81801561006757600080fd5b50610082600480360381019061007d919061114d565b6100ff565b005b81801561009057600080fd5b506100ab60048036038101906100a691906111e8565b61012b565b005b8180156100b957600080fd5b506100d460048036038101906100cf9190611111565b6102cb565b005b8180156100e257600080fd5b506100fd60048036038101906100f89190611237565b610540565b005b61012386868860030160008081526020019081526020016000205487878787610540565b505050505050565b7f30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001811061018d576040517f08c379a000000000000000000000000000000000000000000000000000000000815260040161018490611629565b60405180910390fd5b6000821180156101a15750602060ff168211155b6101e0576040517f08c379a00000000000000000000000000000000000000000000000000000000081526004016101d790611689565b60405180910390fd5b81836000018190555060005b828160ff1610156102bc57818460030160008360ff1681526020019081526020016000208190555073e136abacf78e05988154ed85f4ea9111053025956329a5f2f66040518060400160405280858152602001858152506040518263ffffffff1660e01b815260040161025f9190611573565b60206040518083038186803b15801561027757600080fd5b505af415801561028b573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906102af91906112e7565b91508060010190506101ec565b50808360010181905550505050565b6000826000015490507f30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f00000018210610336576040517f08c379a000000000000000000000000000000000000000000000000000000000815260040161032d90611629565b60405180910390fd5b80600261034391906117f2565b836002015410610388576040517f08c379a000000000000000000000000000000000000000000000000000000000815260040161037f90611609565b60405180910390fd5b600083600201549050600083905060005b838160ff1610156105135760006001841614156104095760405180604001604052808381526020018760030160008460ff168152602001908152602001600020548152508660040160008360ff168152602001908152602001600020906002610403929190610fcc565b50610461565b818660040160008360ff16815260200190815260200160002060016002811061045b577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b01819055505b73e136abacf78e05988154ed85f4ea9111053025956329a5f2f68760040160008460ff1681526020019081526020016000206040518263ffffffff1660e01b81526004016104af919061158e565b60206040518083038186803b1580156104c757600080fd5b505af41580156104db573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906104ff91906112e7565b9150600183901c9250806001019050610399565b5080856001018190555060018560020160008282546105329190611749565b925050819055505050505050565b85851415610583576040517f08c379a000000000000000000000000000000000000000000000000000000000815260040161057a90611669565b60405180910390fd5b7f30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f000000185106105e5576040517f08c379a00000000000000000000000000000000000000000000000000000000081526004016105dc906115c9565b60405180910390fd5b6105f3878786868686610b20565b610632576040517f08c379a0000000000000000000000000000000000000000000000000000000008152600401610629906116a9565b60405180910390fd5b6000876000015490506000869050600080600090505b838160ff161015610ac4578060ff1686868360ff16818110610693577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b90506020020160208101906106a89190611310565b60ff16901b82179150600086868360ff168181106106ef577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b90506020020160208101906107049190611310565b60ff1614156108e5578a60040160008260ff16815260200190815260200160002060016002811061075e577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b015488888360ff1681811061079c577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b90506020020135141561080157828b60040160008360ff1681526020019081526020016000206000600281106107fb577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b01819055505b73e136abacf78e05988154ed85f4ea9111053025956329a5f2f660405180604001604052808681526020018b8b8660ff16818110610868577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b905060200201358152506040518263ffffffff1660e01b815260040161088e9190611573565b60206040518083038186803b1580156108a657600080fd5b505af41580156108ba573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906108de91906112e7565b9250610ab9565b8a60040160008260ff168152602001908152602001600020600060028110610936577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b015488888360ff16818110610974577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b9050602002013514156109d957828b60040160008360ff1681526020019081526020016000206001600281106109d3577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b01819055505b73e136abacf78e05988154ed85f4ea9111053025956329a5f2f660405180604001604052808b8b8660ff16818110610a3a577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b905060200201358152602001868152506040518263ffffffff1660e01b8152600401610a669190611573565b60206040518083038186803b158015610a7e57600080fd5b505af4158015610a92573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610ab691906112e7565b92505b806001019050610648565b5089600201548110610b0b576040517f08c379a0000000000000000000000000000000000000000000000000000000008152600401610b02906115e9565b60405180910390fd5b818a6001018190555050505050505050505050565b60007f30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f00000018610610b84576040517f08c379a0000000000000000000000000000000000000000000000000000000008152600401610b7b90611629565b60405180910390fd5b6000876000015490508084849050148015610ba157508086869050145b610be0576040517f08c379a0000000000000000000000000000000000000000000000000000000008152600401610bd7906116c9565b60405180910390fd5b600087905060005b828160ff161015610fb6577f30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f000000188888360ff16818110610c50577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b9050602002013510610c97576040517f08c379a0000000000000000000000000000000000000000000000000000000008152600401610c8e90611649565b60405180910390fd5b600186868360ff16818110610cd5577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b9050602002016020810190610cea9190611310565b60ff161480610d4c5750600086868360ff16818110610d32577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b9050602002016020810190610d479190611310565b60ff16145b610d8b576040517f08c379a0000000000000000000000000000000000000000000000000000000008152600401610d82906115a9565b60405180910390fd5b600086868360ff16818110610dc9577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b9050602002016020810190610dde9190611310565b60ff161415610ecb5773e136abacf78e05988154ed85f4ea9111053025956329a5f2f660405180604001604052808581526020018b8b8660ff16818110610e4e577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b905060200201358152506040518263ffffffff1660e01b8152600401610e749190611573565b60206040518083038186803b158015610e8c57600080fd5b505af4158015610ea0573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610ec491906112e7565b9150610fab565b73e136abacf78e05988154ed85f4ea9111053025956329a5f2f660405180604001604052808b8b8660ff16818110610f2c577f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b905060200201358152602001858152506040518263ffffffff1660e01b8152600401610f589190611573565b60206040518083038186803b158015610f7057600080fd5b505af4158015610f84573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610fa891906112e7565b91505b806001019050610be8565b5088600101548114925050509695505050505050565b8260028101928215610ffb579160200282015b82811115610ffa578251825591602001919060010190610fdf565b5b509050611008919061100c565b5090565b5b8082111561102557600081600090555060010161100d565b5090565b60008083601f84011261103b57600080fd5b8235905067ffffffffffffffff81111561105457600080fd5b60208301915083602082028301111561106c57600080fd5b9250929050565b60008083601f84011261108557600080fd5b8235905067ffffffffffffffff81111561109e57600080fd5b6020830191508360208202830111156110b657600080fd5b9250929050565b6000813590506110cc81611ced565b92915050565b6000813590506110e181611d04565b92915050565b6000815190506110f681611d04565b92915050565b60008135905061110b81611d1b565b92915050565b6000806040838503121561112457600080fd5b6000611132858286016110bd565b9250506020611143858286016110d2565b9150509250929050565b6000806000806000806080878903121561116657600080fd5b600061117489828a016110bd565b965050602061118589828a016110d2565b955050604087013567ffffffffffffffff8111156111a257600080fd5b6111ae89828a01611029565b9450945050606087013567ffffffffffffffff8111156111cd57600080fd5b6111d989828a01611073565b92509250509295509295509295565b6000806000606084860312156111fd57600080fd5b600061120b868287016110bd565b935050602061121c868287016110d2565b925050604061122d868287016110d2565b9150509250925092565b600080600080600080600060a0888a03121561125257600080fd5b60006112608a828b016110bd565b97505060206112718a828b016110d2565b96505060406112828a828b016110d2565b955050606088013567ffffffffffffffff81111561129f57600080fd5b6112ab8a828b01611029565b9450945050608088013567ffffffffffffffff8111156112ca57600080fd5b6112d68a828b01611073565b925092505092959891949750929550565b6000602082840312156112f957600080fd5b6000611307848285016110e7565b91505092915050565b60006020828403121561132257600080fd5b6000611330848285016110fc565b91505092915050565b60006113458383611564565b60208301905092915050565b61135a816116fd565b611364818461172d565b925061136f826116e9565b8060005b838110156113a05781516113878782611339565b965061139283611713565b925050600181019050611373565b505050505050565b6113b181611708565b6113bb818461172d565b92506113c6826116f3565b8060005b838110156113fe576113db82611984565b6113e58782611339565b96506113f083611720565b9250506001810190506113ca565b505050505050565b6000611413603483611738565b915061141e826119b1565b604082019050919050565b6000611436603c83611738565b915061144182611a00565b604082019050919050565b6000611459602e83611738565b915061146482611a4f565b604082019050919050565b600061147c602383611738565b915061148782611a9e565b604082019050919050565b600061149f603883611738565b91506114aa82611aed565b604082019050919050565b60006114c2604083611738565b91506114cd82611b3c565b604082019050919050565b60006114e5604183611738565b91506114f082611b8b565b606082019050919050565b6000611508603a83611738565b915061151382611c00565b604082019050919050565b600061152b603383611738565b915061153682611c4f565b604082019050919050565b600061154e603483611738565b915061155982611c9e565b604082019050919050565b61156d81611924565b82525050565b60006040820190506115886000830184611351565b92915050565b60006040820190506115a360008301846113a8565b92915050565b600060208201905081810360008301526115c281611406565b9050919050565b600060208201905081810360008301526115e281611429565b9050919050565b600060208201905081810360008301526116028161144c565b9050919050565b600060208201905081810360008301526116228161146f565b9050919050565b6000602082019050818103600083015261164281611492565b9050919050565b60006020820190508181036000830152611662816114b5565b9050919050565b60006020820190508181036000830152611682816114d8565b9050919050565b600060208201905081810360008301526116a2816114fb565b9050919050565b600060208201905081810360008301526116c28161151e565b9050919050565b600060208201905081810360008301526116e281611541565b9050919050565b6000819050919050565b6000819050919050565b600060029050919050565b600060029050919050565b6000602082019050919050565b6000600182019050919050565b600081905092915050565b600082825260208201905092915050565b600061175482611924565b915061175f83611924565b9250827fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff0382111561179457611793611955565b5b828201905092915050565b6000808291508390505b60018511156117e9578086048111156117c5576117c4611955565b5b60018516156117d45780820291505b80810290506117e2856119a4565b94506117a9565b94509492505050565b60006117fd82611924565b915061180883611924565b92506118357fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff848461183d565b905092915050565b60008261184d5760019050611909565b8161185b5760009050611909565b8160018114611871576002811461187b576118aa565b6001915050611909565b60ff84111561188d5761188c611955565b5b8360020a9150848211156118a4576118a3611955565b5b50611909565b5060208310610133831016604e8410600b84101617156118df5782820a9050838111156118da576118d9611955565b5b611909565b6118ec848484600161179f565b9250905081840481111561190357611902611955565b5b81810290505b9392505050565b6000819050919050565b6000819050919050565b6000819050919050565b600060ff82169050919050565b600061194e61194983611997565b611910565b9050919050565b7f4e487b7100000000000000000000000000000000000000000000000000000000600052601160045260246000fd5b6000611990825461193b565b9050919050565b60008160001c9050919050565b60008160011c9050919050565b7f496e6372656d656e74616c42696e617279547265653a207061746820696e646560008201527f78206973206e6569746865722030206e6f722031000000000000000000000000602082015250565b7f496e6372656d656e74616c42696e617279547265653a206e6577206c6561662060008201527f6d757374206265203c20534e41524b5f5343414c41525f4649454c4400000000602082015250565b7f496e6372656d656e74616c42696e617279547265653a206c65616620696e646560008201527f78206f7574206f662072616e6765000000000000000000000000000000000000602082015250565b7f496e6372656d656e74616c42696e617279547265653a2074726565206973206660008201527f756c6c0000000000000000000000000000000000000000000000000000000000602082015250565b7f496e6372656d656e74616c42696e617279547265653a206c656166206d75737460008201527f206265203c20534e41524b5f5343414c41525f4649454c440000000000000000602082015250565b7f496e6372656d656e74616c42696e617279547265653a207369626c696e67206e60008201527f6f6465206d757374206265203c20534e41524b5f5343414c41525f4649454c44602082015250565b7f496e6372656d656e74616c42696e617279547265653a206e6577206c6561662060008201527f63616e6e6f74206265207468652073616d6520617320746865206f6c64206f6e60208201527f6500000000000000000000000000000000000000000000000000000000000000604082015250565b7f496e6372656d656e74616c42696e617279547265653a2074726565206465707460008201527f68206d757374206265206265747765656e203120616e64203332000000000000602082015250565b7f496e6372656d656e74616c42696e617279547265653a206c656166206973206e60008201527f6f742070617274206f6620746865207472656500000000000000000000000000602082015250565b7f496e6372656d656e74616c42696e617279547265653a206c656e677468206f6660008201527f2070617468206973206e6f7420636f7272656374000000000000000000000000602082015250565b611cf68161191a565b8114611d0157600080fd5b50565b611d0d81611924565b8114611d1857600080fd5b50565b611d248161192e565b8114611d2f57600080fd5b5056fea2646970667358221220dbb8c456a5ad337a568c1e4bfdd150259f28006c1be3581e6f2b4e8119ac989864736f6c63430008040033