# The Semacaulk Specification

**This document has been incorporated into the [Semacaulk documentation](https://geometryresearch.github.io/semacaulk/proof_generation.html).**

### Proposition
Semacaulk is one example of how we can construct very efficient membership proofs based on MiMC7 hash function and slightly modified $Caulk+$ argument.

### Notation
1. $Caulk+$ will be used for parameters: $m = 1, Z_V = X - 1$,
2. $c(X)$ is polynomial which values are $Mimc$ round constants
3. $NUM\_OF\_MIMC\_ROUNDS = 91$
4. $SUBGROUP\_SIZE = 128$
5. Rows 92-128 are used for blindings

### Circuit structure
| row | $w_0$ | key | $w_1$ | $w_2$ | c | $q_{mimc}$ |
| ---------- |:-----------------------:|:-----------------:|:----------------------------:|:---------------------------:|:-------:|:----------:|
| 0 | $id\_nullifier$ | $w_0(n) + w_0(0)$ | $id\_trapdoor$ | $external\_nullifier$ | $c_0$ | 1 |
| 1 | $(w_0(0) + c(0))^7$ | $w_0(n) + w_0(0)$ | $(w_1(0) + key(0) + c(0))^7$ | $(w_2(0) + key(0) + c(0)))^7$ | $c_1$ | 1 |
| 2 | $(w_0(1) + c(1))^7$ | $w_0(n) + w_0(0)$ | $(w_1(1) + key(1) + c(1))^7$ | $(w_2(1) + key(1) + c(1))^7$ | $c_2$ | 1 |
| . | . | . | . | . | . | 1 |
| . | . | . | . | . | . | 1 |
| . | . | . | . | . | . | 1 |
| `n_rounds` | $(w_0(n-1) + c(n-1))^7$ | $w_0(n) + w_0(0)$ | $(w_1(n-1) + key(n-1) + c(n-1))^7$ | $(w_2(n-1) + key(n-1) + c(n-1))^7$ | $dummy$ | 0 |

#### Prover

Witness input
1. membership index $i$
2. $identity\_nullifier$
3. $identity\_trapdoor$

Precomputed prover input:
1. $W^{(i)}_1, W^{(i)}_2$
2. $c(X)$ evaluated over coset
3. $Z_H(X)$ evaluated over coset
4. $q_{mimc}(X)$ evaluated over coset
5. $L_0(X)$ evaluated over coset

Public input
1. $C(X)$ polynomial which evaluations are signed identity commitments
2. $[c]_1$ - vector commitment to all signed identity commitments
3. $external\_nullifier$
4. $nullifier\_hash$

$Round\ 1$:

Compute $[w_0]_1 = [w_0(X)]_1, [key]_1 = [key(X)]_1, [w_1]_1 = [w_1(X)]_1, [w_2]_1 = [w_2(X)]_1$

Output: $[w_0]_1, [key]_1, [w_1]_1, [w_2]_1$

$Round\ 2$:

Compute quotient challenge $v = H(transcript)$
Compute quotient polynomial $q(X)$:

$$
q(X) = [q_{mimc}(X)((w_0(X) + c(X))^7 - w_0(\gamma X)) + \ vq_{mimc}(X)((w_1(X) + key(X) + c(X))^7 - w_1(\gamma X)) + \ v^2q_{mimc}(X)((w_2(X) + key(X) + c(X))^7 - w_2(\gamma X)) + \ v^3q_{mimc}(X)(key(X) - key(\gamma X)) + \ v^4L_0(X)(key(X) - w_0(X) - w_0(\gamma ^{91}X)) + \ v^5L_0(X)(nullifierHash - w_2(X) - w_2(\gamma ^{91}X) - 2key(X)) +\ v^6 L_0(X)(w_2(X) - externalNullifier)] / Z_H(X)
$$

Since $SRS$ size is much bigger than $deg(q)$ we don't need to split it into chunks.

TODO: Decide on masking of $q(X)$

Compute $[q]_1 = [q(X)]_1$
Output $[q]_1$

$Round\ 3$

Run $Caulk+$ first round
Output $[z_I]_1, [c_I]_1, [u]_1$

$Round\ 4$
Compute challenges $\chi_1 = H(transcript), \chi_2 = H(transcript)$

Run $Caulk+$ second round with modification:
$H(X) = (Z_I'(U'(X)) + \chi_1 (C_I'(U'(X)) - A(X)) / Z_V(X)$
for $A(X) = w_1(X) + w_1(\gamma^{91}X) + 2*key(X)$

Output $[W]_2, [h]_1$

$Round\ 4$
Run $Caulk+$ third round with openings:
$$
U'(\alpha), P_1(v_1), P_2(\alpha) \\
w_0(\alpha), w_0(\gamma\alpha), w_0(\gamma^{91}\alpha) \\
w_1(\alpha), w_1(\gamma\alpha), w_1(\gamma^{91}\alpha) \\
w_2(\alpha), w_2(\gamma\alpha), w_2(\gamma^{91}\alpha) \\
key(\alpha), key(\gamma\alpha) \\
q_{mimc}(\alpha), c(\alpha), q(\alpha)
$$