Overview

Semacaulk is a zero-knowledge set membership protocol that works on Ethereum.

Semacaulk allows a user to commit to an identity, represented by two secret values: an identity nullifier and an identity trapdoor. Next, any user who knows their secret values can generate a proof that they had previously committed to said identity, without revealing which member of the set they were. Moreover, when they submit such a proof, they can broadcast an arbitrary signal against an external nullifier, but only do so once per external nullifier. This enables applications like mixers, whistleblowing, and simple private voting systems. This is the same basic functionality as the Semaphore Protocol.

The source code for Semacaulk can be found here.

Differences from Semaphore

Semacaulk differs from Semaphore in two key ways. First, instead of accumulating identity commitments in a Merkle tree, it updates a KZG commitment. This operations involves BN254 point multiplication and addition, rather than expensive zk-friendly hash operations. Secondly, the underlying proof system is a polynomial interactive oracle proof that combines Caulk+ lookups and a multipoint opening argument.

Thanks to these techniques, on-chain insertions are far cheaper in Semacaulk (around 68k gas) while the gas cost of verification (356k gas) is comparable to that of Semaphore. Moreover, proof generation comes in two phases - a precomputation stage and a proof generation stage. The total time taken is comparable to Groth16 proof generation for a Semaphore circuit that supports the same number of insertions, but more imporantly, precomputation can be performed long in advance and efficiently updated, which imparts more flexibility which may lead to higher user-friendliness.

Motivation

We intend Semacaulk to demonstrate the use of Caulk+ techniques for membership proofs in a gas-efficient manner to enable privacy-related applications. We believe these techniques, as are other new proving systems and lookup arguments, can be highly useful, and we hope that Semacaulk shows how to practically use them.

We highly welcome and strongly encourage collaboration with projects who wish to build upon Semacaulk.

Note that the techniques used in Semacaulk do not have to involve an end-to-end custom prover such as used here. We have done this only because we wanted to experiment with improving prover efficiency further. With only small changes, the same gas-efficient membership proof construction can be used with more generic and expressive SNARK-based programs.

Security

The code base has not been audited. We do not recommend its use in production until a thorough audit has been performed.

Quick start

1. Install Rust using these instructions.

2. Install Foundry using these instructions.

3. Clone this repository.

git clone https://github.com/geometryresearch/semacaulk.git && \
cd semacaulk

4. Build the contracts

./build_contracts.sh

5. Run tests

cargo test

6. Build and run the demo:

cargo build --release && \
./target/release/demo 11 11.hex lagrangeComms_11

Note that the files 11.hex and lagrangeComms_11 support up to 2048 leaf insertions. To support a larger capacity, see the Trusted Setup - Processing the points section for instructions on how to do so.

Trusted Setup

Semacaulk requires a securely run trusted setup. Specifically, for a capacity of \(2^n\) elements, it requires \(2^n + 1\) \({g_1}^{\tau}\) points and \(2^n\) \({g_2}^{\tau}\) points where \(\tau\) is highly unlikely to be known but \({g_1}^{\tau}\) and \({g_2}^{\tau}\) can be generated via a multi-party ceremony. As long as one participant does not reveal and destroys the secret so-called toxic waste that they use, the entire ceremony is secure.

For compatibility with Ethereum, Semacaulk is built on the BN254 curve. As such, the output of the Perpetual Powers of Tau ceremony can be used. The outputs of this ceremony include up to \(2^{28}\) \({g_1}^{\tau}\) and \({g_2}^{\tau}\) points. If Semacaulk is to be used on a different elliptic curve, a different trusted setup must be used.

For the sake of convenience, we recommend the trusted setup output from Hermez Network, which consist of the 54th contribution of Perpetual Powers of Tau (PPOT) with a random beacon. These files can be downloaded from this page. (You may also use the latest contribution to PPOT, but at the time of writing, a tool to parse and convert it has not yet been written.)

Note that the Aztec Ignition ceremony output is not sufficient for Semacaulk as only provides 1 tauG2 point, while Semacaulk requires as many tauG2 points as the maximum desired capacity of the accumulator.

Processing the points

Semacaulk's demo binary requires two inputs: a .hex file containing the trusted setup outputs, and another file containing the KZG commitments to the Lagrange basis polynomials generated using said trusted setup outputs.

To produce the former, use the export-ptau-points tool. First, download Hermez Network .ptau file with at least \(2^{11}\) points. In this example, we choose \(2^{11}\) for a maximum capacity of 2048:

wget https://hermez.s3-eu-west-1.amazonaws.com/powersOfTau28_hez_final_11.ptau

In export-ptau-points, run:

npm i && npm run build && \
node build/index.js -p powersOfTau28_hez_final_11.ptau -o ./11.hex --num-g1 2049 --num-g2 2048

Build and run the setup binary from the Semacaulk repository:

cargo build --release

To produce the latter, run the setup binary:

./target/release/setup 11 ./path/to/11.hex lagrangeComms_11

You are now ready to run the demo according to the instructions in the quick start page.

Cryptographic Specification

Some of the terminology, symbols, and language has been borrowed from and inspired by the Halo2 Book and the MACI 1.0 Audit Specification.

Notation

• Accumulator: an elliptic curve point which is a commitment to \(t\) field elements.
• \(t\): the maximum capacity of the accumulator.
• Zero value: the nothing-up-my-sleeve value (see 2).
• Elliptic curve multiplication: in this specification, we use the dot operator \(\cdot\) to denote scalar multiplication of an elliptic curve point.

Cryptographic primitives

1. The BN254 curve

The current implementation of Semacaulk uses the BN254 curve which Ethereum supports in its elliptic curve addition, scalar multiplication, and pairing-check precompiles as defined in EIP-196 and EIP-197.

1.1. The BN254 scalar field

The BN254 scalar field \(\mathbb{F}_r\) is:

21888242871839275222246405745257275088548364400416034343698204186575808495617

1.2. The BN254 scalar field

The BN254 prime field \(\mathbb{F}_q\) is:

21888242871839275222246405745257275088696311157297823662689037894645226208583

1.3. The \(\mathbb{G}_1\) group

The group \(\mathbb{G}_1\) defined on BN254 has the generator point \(g_1 = (1, 2)\).

1.4. The \(\mathbb{G}_2\) point

The group \(\mathbb{G}_2\) defined on BN254 has the generator point \(g_2 = (x_0 * i + x_1, y_0 * i + y_1)\) where:

• \(x_0\) equals 11559732032986387107991004021392285783925812861821192530917403151452391805634
• \(x_1\) equals 10857046999023057135944570762232829481370756359578518086990519993285655852781
• \(y_0\) equals 4082367875863433681332203403145435568316851327593401208105741076214120093531
• \(y_1\) equals 8495653923123431417604973247489272438418190587263600148770280649306958101930

2. The nothing-up-my-sleeve value

The nothing-up-my-sleeve (NUMS) value is:

14233191614411629788649003849761857673160358990904722769695641636673172216357

It is the Keccak256 hash of the bytestring Semacaulk, modulo \(\mathbb{F}_r\). To compute it, run the following in a NodeJS console where e is an instance of Ethers.js 5.0:

(
    BigInt(e.utils.solidityKeccak256(['string'], ['Semacaulk'])) % 
    BigInt('21888242871839275222246405745257275088548364400416034343698204186575808495617')
).toString(10)

Due to the second-image resistance property of the Keccak256 hash function, anyone can be assured that no-one knows any other preimage to the NUMS value. It follows that no-one knows the MiMC7 preimage to the NUMS value.

3. The structured reference string (SRS)

Semacaulk's structured reference string (SRS) consists of an ordered list of \(2^n + 1\) \(\mathbb{G}_1\) points and \(2^n\) \(\mathbb{G}_2\) points, where the maximum capacity of the accumulator is \(2^n = t\).

We assume the existence of a secret and unknown value \(\tau\) which can be generated using a securely run trusted setup.

These points are defined as such:

• \(\mathsf{srs\_g1}\): \([g_1, g_1 \cdot {\tau}, \ldots, g_1 \cdot {\tau \cdot {t + 1}}]\)
• \(\mathsf{srs\_g2}\): \([g_2, g_2 \cdot {\tau}, \ldots, g_2 \cdot {\tau \cdot {t + 1}}]\)

Where \(g_1\) is defined in 1.3 and \(g_2\) is defined in 1.4.

4. The MiMC7 hash function

Semacaulk currently uses the MiMC7 hash function to compute identity commitments and nullifier hashes. While other possibly more secure hash functions like Poseidon are possible, we chose MiMC7 only because of its simplicity of implementation for our purposes of delivering a proof-of-concept.

The MiMC7 has function is defined here.

Our instantiation of the MiMC7 hash function for the BN254 curve uses the following constants:

• \(n = 91\)
• \(\mathsf{MIMC\_SEED} =\) mimc (the hexidecimal array [0x6d, 0x69, 0x6d, 0x63])

4.1. The MiMC7 round constants

Given the BN254 scalar field \(\mathbb{F}_r\), we first define 91 round constants (denoted as \(\mathsf{cts}\)) using the algorithm implemented in circomlibjs/src/mimc7.js and semacaulk/src/mimc7.rs.

The algorithm is as such:

• The first round constant is \(0\).
• The next round constant is the Keccak256 hash of \(\mathsf{MIMC\_SEED} =\), modulo the field order of \(\mathbb{F}_r\).
• Each subsequent round constant is the Keccak256 hash of the previous one, modulo the field order of \(\mathbb{F}_r\).

4.2. The MiMC7 hash algorithm

To hash a single field element \(x\), we use the hash() algorithm. The inputs to hash() are \(x\) and a key \(k\).

1. Compute the first round digest \(\mathsf{rd[0]} = (x + k) ^ 7\).
2. Compute the next \(n - 1\) round digests such that \(\mathsf{rd}[i] = (\mathsf{rd}[i - 1] + \mathsf{cts}[i] + k) ^ 7\)
3. Return \(\mathsf{rd}[n - 1] + k\).

4.3. The MiMC7 multi_hash algorithm

To hash multiple field elements \(x_0, \ldots, x_n\), we use the multi_hash() algorithm. The inputs to multi_hash() are the array of said field elements and a key \(k\).

1. Initialise \(r\) to equal \(k\).

2. For each \(x_i\):

   a. Set \(h_i = \mathsf{hash}(x_i, r)\).

   b. Set \(r = x_i + h_i\).

3. Return \(r\).

4.3.1 multi_hash with two field elements

It is useful to describe the multi_hash algorithm for two input elements in individual steps because the Semacaulk circuit construction (see The Circuit and Gates) makes use of its intermediate states.

Given inputs \(a\) and \(b\):

1. Set \(r\) as 0.
2. Set \(h_0 = \mathsf{hash}(a, r)\).
3. Set \(r = r + a + h_0\).
4. Set \(h_1 = \mathsf{hash}(b, r)\).
5. Return \(r + b + h_1\).

Note that in step 4, the key is \(a + h_0 = \mathsf{hash}(a, 0)\). This fact is crucial to understanding how the circuit construction works.

5. KZG commitments

Semcaulk uses the KZG commitment scheme described in KZG10.

Given an array of \(t\) values \([m_0, \ldots, m_t]\), we interpolate to derive the polynomial \(\phi\) such that \(\phi(i) = m_i\).

Knowing \(\phi\) with \(l\) coefficients \([\phi_0, \ldots, \phi_{l - 1}]\), one can use \(\mathsf{srs\_g1}\) to produce a commitment in the form of a \(\mathbb{G}_1\) point, or \(\mathsf{srs\_g2}\) to produce a commitment in the form of a \(\mathbb{G}_2\) point.

\(\mathsf{commit}(\phi, \mathsf{srs}) = \sum_{i=1}^{l} \mathsf{srs}[i] \cdot \phi_i \)

An alternative notation for \(\mathsf{commit}\) is:

• \([\phi]_1\) where the commitment is a \(\mathbb{G}_1\) point or
• \([\phi]_2\) where the commitment is a \(\mathbb{G}_2\) point.

A KZG opening proof is denoted as:

\(\mathsf{open}(\mathsf{srs}, [\phi], \phi(i))\)

6. Lagrange basis polynomials

Lagrange basis polynomials are an important concept and are used in several parts of the protocol. To understand them, we must first define roots of unity of a finite field.

6.1. Roots of unity of a finite field

The \(n\)th roots of unity of a finite field \(\mathbb{F}_p\) with prime order \(p\) are field elements where for each element \(x\), \(x^n = 1\).

For example, the 4th roots of unity of the BN254 scalar field (see 1.1) are:

0x0000000000000000000000000000000000000000000000000000000000000001
0x30644E72E131A029048B6E193FD841045CEA24F6FD736BEC231204708F703636
0x30644E72E131A029B85045B68181585D2833E84879B9709143E1F593F0000000
0x0000000000000000B3C4D79D41A91758CB49C3517C4604A520CFF123608FC9CB

Another name for the \(n\) roots of unity is the evaluation domain of size \(n\) for a given finite field. They are commonly denoted as \(\{1, \omega, \ldots, \omega^{n-1}\}\).

6.2. Lagrange basis polynomials

Given an evaluation domain of size \(n\), the Lagrange basis polynomials of this domain are the \(n\) polynomials \([L_0, \ldots, L_n]\) such that \(L_i(\omega^{i - 1} = 1)\) and \(L_i(\omega^{j} = 0)\) for all \(j \neq i - 1\). For example:

• the Lagrange basis polynomial \(L_0\) evaluates to 1 given the input \(\omega^0\).
• the Lagrange basis polynomial \(L_0\) evaluates to 0 given the input \(\omega^1\).
• the Lagrange basis polynomial \(L_1\) evaluates to 0 given the input \(\omega^0\).
• the Lagrange basis polynomial \(L_1\) evaluates to 1 given the input \(\omega^1\).

6.3. Efficient generation of commitments to Lagrange basis polynomials

To support \(t\) insertions, Semacaulk requires the KZG commitments to the Lagrange basis polynomials over the evaluation domain of size \(t\). These KZG commitments are efficiently generated using an implementation of the Feist-Khovratovich technique.

7. The accumulator

The accumulator is a single \(\mathbb{G}_1\) point that is a commitment to a vector of \(t\) \(\mathbb{F}_r\) elements where \(t\) is the maximum capacity of the instance of Semacaulk in question. These elements are ordered with the users' identity commitments followed by nothing-up-my-sleeve values.

An empty accumulator is simply a commitment to \(t\) nothing-up-my-sleeve values.

Given the vector of values \([v_0, \ldots, v_t]\), the accumulator \(C\) is computed as such:

\(\sum_{i=1}^{t} \mathsf{commit}(L_i, \mathsf{srs\_g1}) \cdot v_i\)

7.1 Updating the accumulator

To replace a value at \(w_i\) with \(v_i\) at index \(i\):

\(C_{\mathsf{new}} = C - L \cdot w_i + L \cdot v_i\)

\(= C + L \cdot (v_i - w_i)\)

where \(L = \mathsf{commit}(L_i, \mathsf{srs\_g1})\)

This can be done on-chain at a low cost because the only expensive operations required are an elliptic curve scalar multiplication and a elliptic curve addition.

8. The Keccak256 hash

The Keccak256 hash function is defined in The Keccak SHA-3 submission by Bertoni et al with the output length of 256 bits. We rely on implementations from the following sources:

• The EVM's KECCAK256 opcode denoted as 0x20.
• The Javascript Ethers.js library's ethers.utils.solidityKeccak256 function.
• The Rust tiny-keccak library's v256 function.

9. Evaluation domains

9.1. The subgroup domain

An evaluation domain with size 128. We denote this constant as \(\mathsf{SUBGROUP\_SIZE}\).

9.2. The extended coset domain

An evaluation domain with size 8 * 128. We denote this as \(\mathsf{EXTENDED\_DOMAIN\_FACTOR} * \mathsf{SUBGROUP\_SIZE} = 1024\).

9.3. The table domain

An evaluation domain with a size of at least 1024. This is the upper limit on the number of elements that the accumulator can hold.

System invariants

An invariant is a property of a system which remains unmodified even after operations or transformations are applied to it. The authors of Semacaulk intend the following to be the invariants of Semacaulk:

1. Privacy: No-one but the user who knows the value of the identity nullifier and identity trapdoor behind an identity commitment may generate a valid proof of set membership of the identity commitment in the accumulator.

2. Safe NUMS value: No-one should be able to produce a valid proof of set membership for the default nothing-up-my-sleeve value.

3. Proof non-malleability: Proofs are visible once submitted to the mempool, but no-one should be able to modify an existing proof, change it such that it is associated with a different signal, and remain valid.

4. Zero-knowledge: given a valid proof, no-one should be able to determine the index of the identity commitment the identity nullifier, or the identity trapdor associated with the proof.

Other invariants which have to do with the internal consistency and correctness of the system are:

5. All identity commitments must be less than the BN254 scalar field size.

6. Every identity commitment in the accumulator must have been added at some point in the past, except for the NUMS values.

7. Any identity commitment besides the NUMS value may be added to the accumulator, unless it is full.

8. The NUMS value cannot be added to the accumulator.

9. There can be no valid proof associated with a NUMS value as the identity commitment.

10. All nullifier hashes must be less than the BN254 scalar field size.

11. It should only be possible to generate a proof for a valid user, and impossible to generate a proof for an invalid user.

Insertion

As described in the Cryptographic Specification, insertions to the accumulator are easily achieved via an elliptic curve point multiplication and addition.

To replace a value (originally $w_i$) at index \(i\) with $v_i$:

$C_{\mathsf{new}}=C+L\cdot (v_i-w_i)$

where $$\begin{gathered} L=\mathsf{commit}(L_i,\mathsf{srs}{ \\ }_{\mathsf{g}}1) \end{gathered}$$

If only insertions are allowed, $w_i$ is by definition the nothing-up-my-sleeve value.

The Circuit and Gates

Semacaulk uses a custom Plonk-style proof system where a prover must convince a verifier that it knows of some private witness values which are the result of the correct execution of predefined logical operations upon public inputs and fixed data. In other terms, there is a circuit which represents some program. In proof systems like Groth16, circuits are represented in the form of a Rank-1 Constraint System (R1CS), and compilers like circom can be used to easily compile circuits to this format. Semacaulk, by contrast, uses a set of custom gates on a set of data columns to represent its logic.

Private inputs (witness)

• \(\mathsf{id\_nul}\): the identity nullifier.
• \(\mathsf{id\_trap}\): the identity trapdoor.
• \(i\): the index of the prover's identity commitment in the accumulator.

Public inputs

• \(\mathsf{ext\_nul}\): the extenal nullifier.
• \(\mathsf{id\_comm}\): the identity commitment, which is the MiMC7 multi_hash of \([\mathsf{id\_nul}, \mathsf{id\_trap}]\).
• \(\mathsf{nul\_hash}\): the nullifier hash, which is the MiMC7 multi_hash of \([\mathsf{id\_nul}, \mathsf{ext\_nul}]\).

Columns

Notes:

• The 0th row contains the \(\mathsf{id\_nul}\), \(\mathsf{id\_trap}\), etc values. They are not table headers.
• \(n\) is the constant (91) defined in 4.
• \(\mathsf{dummy}\) can be any value as it will not be used by any of the gates.
• \(\mathsf{q\_mimc}\) is a selector column. It is a vector starting with \(n\) 1 values followed by zeros.
• \(\mathsf{c}\) is a fixed column starting with \(n\) MiMC7 round constants.
• \(b\) are random values used to blind the columns, in order to make it computationally infeasible to brute-force their polynomial commitments.

Gates

To understand how the logic of the circuit is encoded, consider each row of the table as inputs to the linear combination of the following gates, which must evaluate to 0 for a valid proof to be generated. In effect:

\(\mathsf{gate}_0(r) + \ldots + \mathsf{gate}_n(r) = 0\) must be true.

Each and every gate must evaluate to 0. It is not possible for the prover to cheat by having some gates evaluate to some value such that the total evaluates to 0, since the prover will be forced to separate each gate with a challenge that they cannot control. Internally, the equation is actually:

\(\mathsf{gate}_0(r) \cdot v_0 + \ldots + \mathsf{gate}_n(r) \cdot v_n = 0\) must be true.

where the \(v\) values are successive powers of the hash of the public inputs. The prover would have to break a strong hash function to choose the public inputs and \(v\) values in order to cheat.

0. Mimc7RoundGate

The equation is:

\(\mathsf{q\_mimc}[i] \cdot (\mathsf{w}_0[i] + 0 + \mathsf{c}[i]) ^ 7\)

This makes each row from 1 to \(n\) contain the successive outputs of the MiMC7 round function over \(\mathsf{id\_nul}\).

The key is set to 0 for all rows.

1. Mimc7RoundGate for the identity commitment

The equation is:

\(\mathsf{q\_mimc}[i] \cdot (\mathsf{w}_1[i] + \mathsf{key}[i] + \mathsf{c}[i]) ^ 7\)

To understand this, first note that gate 4 (KeyCopyGate) and gate 3 (KeyEqualityGate) ensure that the \(\mathsf{key}\) values are all the MiMC7 hash of \(\mathsf{id\_nul}\) plus \(\mathsf{id\_nul}\).

As described in 4.3.1, this means that the key for step 4 of the multi_hash function on two inputs is the value in any row of \(key\) from 0 to \(n\). As such, this gate represents the circuit logic for step 4 of multi_hash, which brings it us closer to computing the identity commitment.

Recall from 5.1:

\(\mathsf{id\_comm} = \mathsf{multi\_hash}([\mathsf{id\_nul}, \mathsf{id\_trap}])\)

2. Mimc7RoundGate for the nullifier hash

The equation is:

\(\mathsf{q\_mimc}[i] \cdot (\mathsf{w}_2[i] + \mathsf{key}[i] + \mathsf{c}[i]) ^ 7\)

Recall that:

\(\mathsf{nul\_hash} = \mathsf{multi\_hash}([\mathsf{id\_nul}, \mathsf{ext\_nul}])\)

By the same logic behind the Mimc7RoundGate for the identity commitment, this gate brings us closer to compuing the nullifier hash.

3. KeyEqualityGate

The equation is:

\(\mathsf{q\_mimc}[i] \cdot (\mathsf{key}[i] + \mathsf{key}[n])\)

This gate ensures that every row of \(\mathsf{key}\) from 0 to \(n\) contains the same value.

4. KeyCopyGate

The equation is:

\(L_0(\omega_i) \cdot (\mathsf{key}[i] - \mathsf{w}_0[i] - \mathsf{w}_0[n])\)

This gate ensures that the first row in the \(\mathsf{key}\) column is equal to \(\mathsf{id\_nul}\) plus the \(n\)th iteration of the MiMC7 round function on \(\mathsf{id\_nul}\).

\(L_0\) is a precomputed polynomial in the multiplicative subgroup which evaluates to 1 at \(\omega_i\), and 0 at all other roots of unity. Effectively, it acts as a selector without the overhead of a selector column.

5. NullifierHashGate

The equation is:

\(L_0(\omega_i) \cdot (\mathsf{nul\_hash} - \mathsf{w}_2[n] - (2 \cdot \mathsf{key}[i]) - \mathsf{w}_2[i])\)

This gate ensures that the \(\mathsf{nul\_hash}\) public input is equal to:

\(\mathsf{w}_2[n] + (2 \cdot \mathsf{key}[0]) + \mathsf{w}_2[0])\)

To understand why, let us trace the computation of \(\mathsf{nul\_hash}\):

Given inputs \(\mathsf{id\_nul}\) and \(\mathsf{ext\_nul}\):

1. Set \(r\) as 0.
2. Set \(h_0 = \mathsf{hash}(\mathsf{id\_nul}, r)\).
3. Set \(r = r + \mathsf{id\_nul} + h_0\).
4. Set \(h_1 = \mathsf{hash}(\mathsf{ext\_nul}, r)\).
5. Return \(r + \mathsf{ext\_nul} + h_1\).

Hence, \(\mathsf{nul\_hash}\) equals:

\(r + \mathsf{ext\_nul} + h_1 =\)

\(\mathsf{id\_nul} + h_0 + \mathsf{ext\_nul} + h_1 =\)

\(\mathsf{id\_nul} + \mathsf{hash}(\mathsf{id\_nul}, 0) + \mathsf{ext\_nul} + \mathsf{hash}(\mathsf{ext\_nul}, \mathsf{id\_nul} + \mathsf{hash}(\mathsf{id\_nul}, 0))\)

Since the value \(r\) from step 3 is used as the key in step 4, the above is equal to:

\(\mathsf{key}[0] + \mathsf{ext\_nul} + \mathsf{hash}(\mathsf{ext\_nul}, \mathsf{key}[0])\)

Since \(\mathsf{hash}(x, k)\) equals \(n\) round digests of \(x\) plus \(k\), the above equals:

\(\mathsf{key}[0] + \mathsf{w}_2[0] + \mathsf{w}_2[n] + \mathsf{key}[0] =\)

\(\mathsf{w}_2[n] + (2 \cdot \mathsf{key}[0]) + \mathsf{w}_2[0])\)

6. ExternalNullifierGate

The equation is:

\(L_0(\omega_i) \cdot (\mathsf{w}_2[i] - \mathsf{ext\_nul})\)

This gate ensures that the \(\mathsf{ext\_nul}\) public input is equal to \(\mathsf{w}_2[0]\).

Precomputation and updates

Caulk employs a precomputation step in order to make the use of it sublinear in the group size. This allows neatly separating the membership proof part of Semacaulk from the nullifier computation, while allowing to blind the precomputed membership proof differently at each use.

When a group is updated, precomputation is needed again, so there are a few options as to how to avoid many precomputations in frequently updated groups. These include storing a history of valid group commitments or batching insertions and updating the precomputation after some predefined time slot. This also opens the possibility to use a centralised, but verifiable, service to compute these for them, since a unique feature of the precomputation in Caulk is that a batch can be computed even more cheaply. There are, of course, privacy implications when using a service, but these can also be mitigated using several techniques and trade-offs.

Additionally, the precomputation done in Caulk is amenable to efficient updates when the group changes, justifying a higher cost for the initial precomputation.

Precomputed data

Precomputed data consists of the following:

1. \(\mathsf{mimc\_cts}\)
2. \(\mathsf{mimc\_cts\_coset\_evals}\)
3. \(\mathsf{zh\_inverse\_coset\_evals}\)
4. \(\mathsf{q\_mimc}\)
5. \(\mathsf{q\_mimc\_coset\_evals}\)
6. \(\mathsf{l0\_coset\_evals}\)
7. \(\mathsf{w_1\_mapping}\)
8. \([{\mathsf{W}_1}^{(i)}]_2\) for all indices \(i \in I\)
9. \([{\mathsf{W}_2}^{(i)}]_2\) for all indices \(i \in I\)

The only parts of the precomputed data which rely on the secret index \(i\), which denotes the secret position of the prover's identity commitment in the accumulator, are \([{\mathsf{W}_1}^{(i)}]_2\) and \([{\mathsf{W}_2}^{(i)}]_2\).

The Caulk+ paper defines:

• \({\mathsf{W}_1}^{(i)} = (C(X) - v_i) / (X - \omega^i)\)
• \({\mathsf{W}_2}^{(i)} = Z_H(X) / (X - \omega^i)\)

Updating commitments to \(\mathsf{W}_1^{(i)}\)

For many of Semacaulk's use cases, users insert new items into the accumulator, and do not update existing items. As such, this section will only discuss how to update commitments to \(\mathsf{W}_1^{(i)}\) when the accumulator changes at an index \(j\) which is different from that of the user's entry \(i\).

We can efficiently update \([{\mathsf{W}_1}^{(i)}]_2\) using the technique described in TADBFK20, section 3.4.2, where \(i \neq j\).

When an element at \(j\) is updated and \(i \neq j\), and the new element is \(v_j = v_\mathsf{zero} + \delta\), the new accumulator is:

\(C(X) - L_j(X) \cdot v_\mathsf{zero} + L_j \cdot v_j\)

\(= C(X) - L_j(X) \cdot (v_\mathsf{zero} + v_j)\)

\(= C(X) + \delta \cdot L_j(X)\)

\({\mathsf{W{new}}_1}^{(i)}\) is therefore:

\(\frac{C(X) - v_i + \delta \cdot L_j(X)}{X - \omega^i}\) \( = {\mathsf{W}_1}^{(i)} + \delta \cdot \frac{L_j(X)}{X - \omega^i}\)

To use the homomorphic properties of KZG commitments, we need to compute \([\frac{L_j(X)}{X - \omega^i}]_2\), multiply it by \(\delta\), and add it to \([{\mathsf{W}_1}^{(i)}]_2\). Yet we must do this with lower than the \(O(n)\) cost of a full KZG \(\mathsf{commit}\) operation.

TADBFK20 section 3.4.2 describes how to do so without performing \(\mathsf{commit}\) at all. This document will be updated to elaborate on the method.

Updating commitments to \(\mathsf{W}_2^{(i)}\)

For use cases where users do not update their own entries (i.e. \(i \neq j\)), there is no need to update the precomputed commitments to \(\mathsf{W}_2^{(i)}\).

The Fiat-Shamir Transcript

A transcript is an abstraction over the Fiat-Shamir heuristic. Both the prover and verifier use the transcript to deterministically generate challenge variables based on the public inputs and proof data.

Another way to think about the transcript is as a state machine where the state is a single data buffer. Every time a challenge is requested, it hashes the buffer replaces the contents of the buffer with the hash, and returns a value derived from the hash. The transcript can also be updated with abitrary data by appending the update to the buffer.

Our transcript implements this concept with the following functions:

• new_transcript: returns a new transcript whose buffer is 32 bytes of 0 values.
• update_with_f: accepts a single \(\mathbb{F}_r\) value, converts it to a big-endian byte array, and appends it to the buffer.
• update_with_g1: accepts a single \(\mathbb{G}_1\) point, converts its \(x\) and \(y\) points to big-endian byte arrays, and appends them to the buffer in the aforementioned order.
• update_with_g2: accepts a single \(\mathbb{G}_2\) point, converts its \(x_0\), \(x_1\), \(y_0\), and \(y_1\) points into big-endian byte arrays, and appends them to the buffer in the aforementioned order.
• get_challenge: hashes the buffer with Keccak256, replaces the buffer with the hash, converts the hash into a \(\mathbb{F}_r\) element (treating it as a big-endian buffer), and returns the \(\mathbb{F}_r\) element.

Proof generation

4.6.1. Assignment Round

Given the public and private inputs, the prover generates the assignment table (see 4.3). Each column is represented as a polynomial over the multiplicative subgroup.

• \(\mathsf{w}_0\)
• \(\mathsf{w}_1\)
• \(\mathsf{w}_2\)
• \(\mathsf{key}\)

The prover then computes KZG commitments to each of the above polynomials:

• \([\mathsf{w}_0]_1\)
• \([\mathsf{w}_1]_1\)
• \([\mathsf{w}_2]_1\)
• \([\mathsf{key}]_1\)

The prover also computes:

\(A = \mathsf{w}_1 + \mathsf{w}_1(\gamma^{91}X) + 2 \cdot \mathsf{key}\)

where \(\mathsf{w}_1(\gamma^{91}X)\) is \(\mathsf{w}_1\) shifted by the \(n\)th root of unity in the subgroup domain (9.1).

Next, the prover adds the public inputs to the transcript in this order:

1. \(\mathsf{ext\_nul}\)
2. \(\mathsf{nul\_hash}\)
3. \(\mathsf{sig\_hash}\)

The prover then extracts the challenge \(v\), which is used in the next round.

4.6.2. Quotient round

The prover generates a quotient polynomial \(q\) by dividing a numerator — a powers-of-\(v\)-separated linear combination of gate polynomials — with the vanishing polynomial \(Z_H\).

\(q(X) = \mathsf{numerator} / Z_H\) where

\(\mathsf{numerator} =\)

\(\mathsf{q\_mimc}((\mathsf{w}_0 + \mathsf{cts})^7 - \mathsf{w}_0(\gamma X)) + \)

\(v \cdot \mathsf{q\_mimc}((w_1 + \mathsf{key} + \mathsf{cts})^7 - w_1(\gamma X)) +\)

\(v^2 \cdot \mathsf{q\_mimc}((\mathsf{w}_2 + \mathsf{key} + \mathsf{cts})^7 - \mathsf{w}_2(\gamma X)) +\)

\(v^3 \cdot \mathsf{q\_mimc}(\mathsf{key} - \mathsf{key}(\gamma X)) +\)

\(v^4 \cdot L_0(\mathsf{key} - \mathsf{w}_0 - \mathsf{w}_0(\gamma ^{91}X)) +\)

\(v^5 \cdot L_0(\mathsf{nul\_hash} - \mathsf{w}_2 - \mathsf{w}_2(\gamma ^{91}X) - 2 \cdot \mathsf{key}) +\)

\(v^6 \cdot L_0 \cdot (\mathsf{w}_2 - \mathsf{ext\_nul})\)

These equations correspond to the gates defined in 4.3.

\(\mathsf{w}_0(\gamma X)\) refers to \(\mathsf{w}_0\) shifted (or "rotated") forward by one.

\(\mathsf{w}_0(\gamma ^{91}X)\) refers to \(\mathsf{w}_0\) shifted forward by 91, which is the number of MiMC7 rounds defined in 4.1.

The prover then commits to \(q\) to obtain \([q]_1\).

4.6.3. First Caulk+ round

The prover computes:

• \(\mathsf{z}_i\)
• \(\mathsf{c}_i\)
• \(u'\)

and their commitments:

• \([\mathsf{z}_i]_1\)
• \([\mathsf{c}_i]_1\)
• \([u']_1\)

according to page 6 of the Caulk+ paper.

The prover then updates the transcript with \([q]_1\) and the above values, and extracts the challenge values \(\chi_1\) and \(\chi_2\), which are used in the next round. \(\chi_1\) is also used in the opening round.

4.6.4. Second Caulk+ round

The prover computes:

• \(\mathsf{h}\)
• \(\mathsf{w}\)

according to the Round 2 steps from page 6 of the Caulk+ paper, and commits to them:

• \([\mathsf{h}]_1\)
• \([\mathsf{w}]_2\)

The prover then extracts the challenge \(\alpha\), which is used in the next round.

4.6.5. Opening round

This section is a work in progress; in the meantime, see this document for the multiopen argument. Also see this document which describes the argument adapted for Semacaulk.

The prover computes:

• \(\omega\): the root of unity with index 1 (starting from zero) of the subgroup domain ((9.1)[./cryptographic_specification.html#91-the-subgroup-domain]).
• \(\omega^n\): the root of unity with index \(n\) (starting from 0) of the subgroup domain.

The prover computes the polynomials:

• \(\mathsf{p}_1\)
• \(\mathsf{p}_2\)

The commitments:

• \([\mathsf{p}_1]_1\)
• \([\mathsf{p}_2]_1\)

The openings:

• \(\mathsf{w}_0(\alpha)\)
• \(\mathsf{w}_0(\omega\alpha)\)
• \(\mathsf{w}_0(\omega^n \alpha)\)
• \(\mathsf{w}_1(\alpha)\)
• \(\mathsf{w}_1(\omega\alpha)\)
• \(\mathsf{w}_1(\omega^n \alpha)\)
• \(\mathsf{w}_2(\alpha)\)
• \(\mathsf{w}_2(\omega\alpha)\)
• \(\mathsf{w}_2(\omega^n \alpha)\)
• \(\mathsf{key}(\alpha)\)
• \(\mathsf{key}(\omega\alpha)\)
• \(\mathsf{q\_mimc}(\alpha)\)
• \(\mathsf{mimc\_cts}(\alpha)\)
• \(\mathsf{q}(\alpha)\)
• \(\mathsf{u'}_1(\alpha)\)
• \(\mathsf{p}_1(\mathsf{u'}_1(\alpha))\)
• \(\mathsf{p}_2(\alpha)\)

The prover adds the above openings to the transcript in the stated order.

4.6.6. Multiopen argument round

The steps in this are based on the Halo2 multipoint opening argument.

The prover computes the vanishing polynomials:

• \(\mathsf{z}_1 = x - \mathsf{u'}_1(\alpha)\)
• \(\mathsf{z}_2 = x - \alpha\)
• \(\mathsf{z}_3 = \mathsf{z}_2 \cdot (x - \omega\alpha)\)
• \(\mathsf{z}_4 = \mathsf{z}_3 \cdot (x - \omega^n \alpha)\)

The prover extracts the challenge values \(x_1\), \(x_2\), \(x_3\), and \(x_4\).

The prover computes the polynomials:

• \(\mathsf{q}_1 = \mathsf{p}_1\)
• \(\mathsf{q}_2 = \mathsf{q\_mimc} + \mathsf{mimc\_cts} \cdot x_1 + \mathsf{q} \cdot {x_1}^{2} + \mathsf{u'} * {x_1}^{3} + \mathsf{p}_2 \cdot {x_1}^{4}\)
• \(\mathsf{q}_3 = \mathsf{key}\)
• \(\mathsf{q}_4 = \mathsf{w}_0 + \mathsf{w}_1 \cdot x_1 + \mathsf{w}_2 \cdot {x_1} ^ 2\)
• \(\mathsf{f}_1 = \mathsf{q}_1 / \mathsf{z}_1\)
• \(\mathsf{f}_2 = \mathsf{q}_2 / \mathsf{z}_2\)
• \(\mathsf{f}_3 = \mathsf{q}_3 / \mathsf{z}_3\)
• \(\mathsf{f}_4 = \mathsf{q}_4 / \mathsf{z}_4\)
• \(\mathsf{f} = \mathsf{f}_1 + \mathsf{f}_2 \cdot x_2 + \mathsf{f}_3 \cdot {x_2}^2 + \mathsf{f}_4 \cdot {x_2}^3\)
• \(\mathsf{final} = \mathsf{f} + \mathsf{q}_1 \cdot x_4 + \mathsf{q}_2 \cdot {x_4}^2 + \mathsf{q}_3 \cdot {x_4}^3 + \mathsf{q}_4 \cdot {x_4}^4\)

The prover computes the openings:

• \(\mathsf{q}_1(x_3)\)
• \(\mathsf{q}_2(x_3)\)
• \(\mathsf{q}_3(x_3)\)
• \(\mathsf{q}_4(x_3)\)

The prover computes the commitments:

• \([\mathsf{f}]_1\)

Finally, the prover computes a KZG opening proof:

• \(\pi_\mathsf{final} = \mathsf{open}(\mathsf{srs\_g1}, \mathsf{final}, x_3)\)

4.6.7. The proof

The final proof consists of:

• The multiopen proof
  • \(\mathsf{q1\_opening}\)
  • \(\mathsf{q2\_opening}\)
  • \(\mathsf{q3\_opening}\)
  • \(\mathsf{q4\_opening}\)
  • \(\mathsf{f\_cm}\)
  • \(\mathsf{final\_\pi}\)
• The openings
  • \(\mathsf{q\_mimc}\)
  • \(\mathsf{mimc\_cts}\)
  • \(\mathsf{quotient}\)
  • \(\mathsf{u\_prime}\)
  • \(\mathsf{p1}\)
  • \(\mathsf{p2}\)
  • \(\mathsf{w0}_0\)
  • \(\mathsf{w0}_1\)
  • \(\mathsf{w0}_2\)
  • \(\mathsf{w1}_0\)
  • \(\mathsf{w1}_1\)
  • \(\mathsf{w1}_2\)
  • \(\mathsf{w2}_0\)
  • \(\mathsf{w2}_1\)
  • \(\mathsf{w2}_2\)
  • \(\mathsf{key}_0\)
  • \(\mathsf{key}_1\)
• The commitments
  • \([\mathsf{w}_0]_1\)
  • \([\mathsf{w}_1]_1\)
  • \([\mathsf{w}_2]_1\)
  • \([\mathsf{key}]_1\)
  • \([\mathsf{mimc\_cts}]_1\)
  • \([\mathsf{quotient}]_1\)
  • \([\mathsf{u\_prime}]_1\)
  • \([\mathsf{zi}]_1\)
  • \([\mathsf{ci}]_1\)
  • \([\mathsf{p1}]_1\)
  • \([\mathsf{p2}]_1\)
  • \([\mathsf{q\_mimc}]_1\)
  • \([\mathsf{h}]_1\)
  • \([\mathsf{w}]_2\)

Proof verification

At a high level, the verifier does three main steps to verify a proof (4.6.6):

4.7.1. Check the gate openings

Given the opening values which the prover claims to be evaluations of the column polynomials which correspond to the circuit, the verifier computes the linear combination of the evaluation of the openings based on each gate equations separated by the \(v\) challenge values. This linear combination must equal the product of the quotient opening and the evaluation of the vanishing polynomial, or the verifier will return false.

4.7.2. Compute the multiopen argument's final_poly and final_poly_eval values

Leveraging the homomorphic properties of KZG commitments, the verifier reconstructs a commitment to the \(\mathsf{final}_\pi\) polynomial generated in the prover's multiopen argument round.

The verifier also reconstructs \(\mathsf{final\_poly\_eval}\) which is the evaluation of \(\mathsf{final}\) at the \(x_3\) challenge.

4.7.3. Perform pairing checks

A three-part pairing product is performed and the verifier returns true only if the result is 1.

\(A * B * C == 1\)

where:

\(A = e(\mathsf{a}_1 + \mathsf{a}_2 + \mathsf{a}_3, [1]_2)\)

\(\mathsf{a}_1 = C - [\mathsf{ci}]_1\)

\(\mathsf{a}_2 = \chi_2(\mathsf{srs\_g1}[t] - [1]_1)\)

${\mathsf{a}}_3=({\pi }_{\mathsf{final}}\cdot x_3-final\_poly\_eval+[\mathsf{final}{]}_1)\cdot s$

\(B = e(-[\mathsf{zi}]_1, [\mathsf{w}]_2)\)

\(C = e(-[\mathsf{final}_\pi]_1 \cdot s, [1]_2 \cdot \tau)\)

and \(s\) is a separator challenge extracted from the transcript.

The Lagrange Basis Polynomial Commitment Tree

The Semacaulk contract's insertIdentity function requires access to a valid commitment to the Lagrange basis polynomial at the index at which an insertion is made. This commitment is prohibitively expensive to compute on-chain, so we instead have a Merkle root to the hashes of all of these commitments be set as an immutable storage variable at deployment time. The user only has to provide a Merkle path to said commitment, which the contract can cheaply verify. These commitments are deterministic and anyone can verify that the Merkle root to these values is valid.

Code

The Rust function to compute the Lagrange basis polynomial commitments is commit_to_lagrange_bases located in src/accumulator.rs. The code to compute the Merkle tree of the hashes of these commitments is also located in the same file.

Mechanism of Operation

The goal of Semacaulk is to enable users to:

1. Register their identity;
2. Prove in zero-knowledge that they are a member of the set of registered users;
3. Broadcast an arbitrary signal towards an external nullifier, without the possibility of double-signalling.

6.1. User identities

A user's identity consists of an identity nullifier \(\mathsf{id\_nul}\) and an identity trapdoor \(\mathsf{id\_trap}\). These are secret values and are elements of \(\mathbb{F}_r\) (see 1.1).

An identity commitment \(\mathsf{id\_comm}\) is the MiMC7 multi_hash (see 4.3) of \(\mathsf{id\_nul}\) and \(\mathsf{id\_trap}\):

\(\mathsf{id\_comm} = \mathsf{multi\_hash}([\mathsf{id\_nul}, \mathsf{id\_trap}])\)

6.2. External nullifiers

An external nullifier \(\mathsf{ext\_nul}\) is a \(\mathbb{F}_r\) field element which represents a topic. A signal can only be broadcast towards each external nullifier once and only once.

6.3. Nullifier hashes

A nullifier hash is the MiMC7 multi_hash of \(\mathsf{id\_nul}\) and \(\mathsf{ext\_nul}\):

\(\mathsf{nul\_hash} = \mathsf{multi\_hash}([\mathsf{id\_nul}, \mathsf{ext\_nul}])\)

6.4. Insertions

An insertion is the act of updating the on-chain accumulator with a user's identity commitment. This is done by invoking the insertIdentity() function of the Semacaulk smart contract.

6.5. Broadcasting a signal

When a user broadcasts a signal, they generate a proof that they know the secret identity nullifier and identity trapdoor behind their identity commitment, and then submit said proof to the Semacaulk smart contract's broadcastSignal() function.

Tied to this proof is the hash of a signal and the user's desired external nullifier. The contract (not the user) hashes the user-provided signal using Keccak256 and right-shifts the result by 8 bits to derive \(\mathsf{sig\_hash}\), which is used as one of the public inputs to the verifier.

6.6. Preventing double-signalling

The Semacaulk smart contract maintains a mapping of nullifier hashes. Each nullifier hash is unique to the user and an external nullifier. If the broadcastSignal() function finds that a nullifier hash has already been seen, it rejects the transaction, thus preventing double-signalling.

Ethereum contracts

Semacaulk.sol

The main Semacaulk contract which client applications should interact with or inherit. The key functions it exposes are:

insertIdentity

Functions signature: insertIdentity(uint256 _identityCommitment, uint256 _lagrangeLeafX, uint256 _lagrangeLeafY, bytes32[] memory _lagrangeMerkleProof)

_identityCommitment is the user-generated value defined in 6.1.

_lagrangeLeafX and _lagrangeLeafY are the respective X and Y coordinates of the commitment to the Lagrange basis polynomial of the index at which the user wishes to insert their identity commitment.

_lagrangeMerkleProof is the Merkle proof from the Keccak256 hash of _lagrangeLeafX and _lagrangeLeafY to the root of the Lagrange Basis Polynomial Commitment Tree.

This function first verifies the Merkle proof to ensure that _lagrangeLeafX and _lagrangeLeafY are valid. Next, it performs field and elliptic curve operations to perform an insertion to update the accumulator.

broadcastSignal

Function signature: broadcastSignal(bytes memory _signal, Types.Proof memory proof, uint256 _nullifierHash, uint256 _externalNullifier)

This function performs the following steps:

1. Revert if _nullifierHash has already been seen. This prevents double-signalling.
2. Compute the $sig\_hash$ public input by hashing _signal with Keccak256 and right-shifting the result by 8 bits.
3. Verify the proof and revert if it is invalid.
4. Store the nullifier hash.

Verifier.sol

This contract exposes a verify() function for the Semacaulk contract's broadcastSignal function to use. It performs the steps described in 4.7.

Transcript.sol

This contract abstracts over the Fiat-Shamir Heuristic by providing helper functions to the verifier to add data to the transcript and extract the challenge values it needs.

Types.sol

A helper library that defines complex Solidity types that comprise the proof.

BN254.sol

Provides functions that encapsulate elliptic curve operations over the BN254 curve.

KeccakMT.sol

Provides a helper function for the Semacaulk contract's insertIdentity function to verify a Merkle proof.

Lagrange.sol

Provides a helper function for the verifier contract to compute the evaluation of $L_0$ at a given point $\alpha$, and the evaluation of the vanishing polynomial at $\alpha$.

Constants.sol

Contains crucial constant values:

• PRIME_Q: the order of the BN254 base field.
• PRIME_R: the order of the BN254 scalar field.
• DOMAIN_SIZE_INV: the inverse of the domain size (128) over the BN254 scalar field.
• LOG2_DOMAIN_SIZE: the binary logarithm of the domain size such that 2 ^ LOG2_DOMAIN_SIZE = 128.
• OMEGA: the 1st root of unity (counting from 0) of the subgroup domain.
• OMEGA_N: the $n$th root of unity (counting from 0) of the subgroup domain.

The following constants depend on the maximum size of the accumulator, and should be changed depending on how many elements the client application wishes to support.

• SRS_G1_T_X: The X coordinate of $srs\_g1[t]$
• SRS_G1_T_Y: The Y coordinate of $srs\_g1[t]$
• SRS_G2_1_X_0: The X0 coordinate of $srs\_g2[1]$
• SRS_G2_1_X_1: The X1 coordinate of $srs\_g2[1]$
• SRS_G2_1_Y_0: The Y0 coordinate of $srs\_g2[1]$
• SRS_G2_1_Y_1: The Y1 coordinate of $srs\_g2[1]$

Gas costs

An insertion (via insertIdentity() costs around 68k gas.

broadcastSignal(), which includes proof verification, costs around 355k gas.

By contrast, a Tornado Cash deposit (which involves inserting a leaf to a Merkle tree) costs 907787 gas and a withdrawal (which involves a Groth16 verification step) costs 327188 gas.

Performance and Benchmarks

These benchmarks were performed on an Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz machine with 24 GB RAM. They represent the time taken for a native Rust binary (built for release) to perform the precomputation and proof generation steps.

To reproduce these benchamarks, run the demo binary following these instructions.

Benchmarks

Credits

Semacaulk was written by:

• Andrija Novakovic (andrija@geometry.xyz)
• Koh Wei Jie (wj@geometry.xyz)
• Kobi Gurkan (kobi@geometry.xyz)

Special thanks to these contributors for their feedback and support:

• Nicolas Mohnblatt (nico@geometry.xyz )
• Tom Walton-Pocock (tom@geometry.xyz)
• Lai Ying Tong (yingtong@geometry.xyz)

Last but not least, we would also like to thank:

• Jon Stephens from Veridise and Andy Guzman from Sempahore for sharing information about Semaphore's invariants used in their formal audit.