# Caulk and Schnorr signature for semaphore schema.

### 1. Caulk

Caulk is zk protocol help us proving we know a few element in set S.

For prove single element(from caulk paper: https://eprint.iacr.org/2022/621.pdf):


We have `cm` is Pedersen commitment for each proof.

### 2. Schnorr signature

We will follow the Schnorr signature define in bip340.
https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#design

#### 2.1 Key prefixing

Define a pairprivate/public key is $(x, X)$ s.t $X = g^x$.
- Sign message $m$ we random $r$ from $Z_p$. We compute $R = g^r, c = Hash(X, R, m)$ and $s = r + xc$. $(R, s)$ is signature.
- Verify message $m$ we check $g^s = RX^c$.

## Basic idea

We construct caulk protocol with element in set is product of random value $h \in G$ and public key X gen by Schnorr genkey algorithm. We can proving we know "one element" in public set(S).

We can sign message by Schnorr signature. The problem here is we need verify signature without revealing public key.

With Schnorr verify we will check:

$$
\begin{equation}
sG = R + cX \\
\Leftrightarrow shG = hR + cX \quad(1)
\end{equation}
$$

The goal is verify (1) is true without revealing $X$ or $hX$ $h$ and $R$.

Denote $[.]$ is Pedersen commitment. Prover need sent $[R], [hX], [h], s, c, [g^s h^c]$ to verifier.

We can use a build block from Hyrax paper(https://eprint.iacr.org/2017/1132.pdf#page17).


For more details, If we have 3 values $X, Y, Z$ we can prove:

- Proof of equality X = Y, and without know X, Y only through commiment $[X], [Y]$
- Proof of product: X * Y = Z without know Z, Y and Z only throuht commitment $[X], [Y], [Z]$

From caulk proof for $e$ belong to S we got Pedersen commitment $cm = e[g]_{1} + r[h]_{1}$.

We can compute $[h^c]$ from $[h]$, $[(hX)^c]$ from $[hX]$.
And verify Proof-of-product($[g^s],[h^c],[g^sh^c]$) and Proof-of-product($[R],[(hX)^c],[g^sh^c]$). If both checking correct then signature also pass verification.

Verifier don't know exactly value of $h$ and $R$ only know the Pederden commitment of them so this why the schema is zero knowledge.

### New Ideas:
- We can commit a public key point $X$.
- Create circuit to prove we know $X \in S$ and $Y = X^{\alpha}$ with $\alpha$ is random element pick by prover. Y is public, X, $\alpha$ is private.
- Verifier will ensure $X\in S$ and $e(g_1, sig) = e(Y, H_2(m))$ where sig is BLS signature, H_2(m) is hash function on curve g_2.

### Open problems:
- We want to compute on elliptic curve so the formula of verification will be different. On EC, a formula is: $sG = R + cX$. I not sure Pedsersen commitment work in this case. Any idea are welcome <3.
- In caulk lookup multiple element are not use Pedsersen commitment. But public key in caulk inlcude 2 elements (coordinate $x,y$ of point on curve).
- Could we apply BLS signature?

## Compare with semaphore use Merkle Tree and Snark.

- Insert cost is cheap only compute one commitment.
- After prover public key in set. We can use this commiment multiple time.
- Verify cost not benchmark now
- Schnorr signature can aggregate(need investigate more).

## Plan
- Ensure this schema is secure.
- Implementation and benchmark.