Nullifiers & Commitments

Every time a user performs a transaction using Hinkal, the browser wallet computes a Zero Knowledge Proof (ZKP) and creates (or nullifies) a commitment.

A commitment is a cryptographic primitive that allows a user to commit to a chosen value while keeping it hidden to others, with the ability to reveal the committed value later. Commitments are created and spent after deposits, transfers, and swaps.

A nullifier is the result of a one way hash function of a commitment and a shielded private key, when making a transaction a commitment is nullified and written on chain.

This mechanism is used so that commitments cannot be reused.

Merkle Tree and Removable Merkle Tree Implementations

The Merkle tree data structure is a crucial part of the protocol, enabling commitment to a set of elements and supporting membership proofs that can be verified using only the tree's root hash. The protocol implements a modified version of the standard Merkle tree to allow for dynamic insertions and deletions. New leaves are always inserted at the end of the leaf list, filling the tree from left to right.

The MerkleBase.sol contract provides a shared interface for Merkle tree structures. A key function in this interface is rootHashExists(), which is widely used within the protocol. To prevent denial-of-service attacks from frontrunners (who might try to constantly change the Merkle tree root to invalidate transactions), the Merkle tree maintains the last MAX_ROOT_NUMBER roots (default is 25).

The Merkle.sol contract implements the MerkleBase interface with a dynamic, write-only Merkle tree. It does not store the entire tree in memory but instead keeps a mapping of the "right frontier" node values. The tree's root is computed recursively: for any internal node, the hash is calculated as:

• Poseidon(left, right) if both left and right children exist.

• Poseidon(left, 0) if there is no right child, with the hash "bubbling up" the tree using zero as a placeholder for the missing child.

The MerkleRemovable.sol contract offers another implementation of MerkleBase, this time supporting deletions. As a result, the full tree mapping (including internal nodes) must be stored, unlike the write-only tree. The tree structure uses a binary-heap style mapping, where:

• The root is stored at index 0.

• For any node at index i, its left child is stored at 2*i, and its right child at 2*i + 1.

Leaf nodes are inserted from left to right, starting at a predefined minimum index (MINIMUM_INDEX), which corresponds to the leftmost leaf. When inserting a new leaf, the tree is updated from the inserted node upwards, until it reaches the depth necessary to accommodate the tree’s structure. This depth is determined by the next integer value of the base-2 logarithm of the number of leaves.

ZKP UTXOs, Commitments, and Nullifiers

Hinkal uses a UTXO (Unspent Transaction Output) model, where each UTXO contains the following elements:

• erc20Address: The address of the token represented by the UTXO.

• amount: The token amount within the UTXO.

• stealthAddress: The stealth address that owns the UTXO.

• timestamp: The creation time of the UTXO.

• tokenId: A unique internal token identifier used by Hinkal contracts.

For each UTXO, a cryptographic commitment is generated either off-chain or on-chain (for example, during swaps involving outgoing UTXOs). This commitment is a Poseidon hash of the UTXO's attributes, which include the token amount, erc20Address, the public key of the stealth address, and the timestamp.

The nullifier, which ensures that a UTXO can only be spent once, is another Poseidon hash derived from the nullifier signature and the commitment. The signature is computed as the Poseidon hash of the shielded private key and the commitment.

When a user wants to spend a UTXO, they must produce a zero-knowledge proof (ZKP) showing that they own the shielded private key tied to a commitment stored in Hinkal’s Merkle tree. Additionally, they need to provide the correct nullifier for the commitment. The protocol, using Circom and Solidity, enforces checks to verify that the amounts spent are accurate. In Solidity, nullifiers are recorded in a data structure to prevent the same commitment from being spent twice.