# ZKPs, not zkSNARKs

_Epistemic status_
- _Incomplete but would like to get feedback._
- _Likely contain soundness and zk errors, not yet formally analyzed._
- _Hope this write-up will set a general direction._

There are several ways to prove the knowledge of a private key that corresponds to a public key that is in a particular set of public keys, in zero-knowledge re: the private key and the public key.

zkSNARKs are one of them, but what zkSANRKs do is: make the verification really cheap, and as a byproduct (of pairings) obtain zero knowledge. Newer proving systems that don't involve pairings like STARKs/Plonky2 don't support zero-knowledge in vanilla mode, and even in proving systems like Halo, you don’t necessarily need to implement e.g. [zero-knowledge opening](https://eprint.iacr.org/2019/1021.pdf#page=9).
However, in privacy applications, we want to prioritize the ease of proving, and not necessarily succinctness (we can obtain succinctness on the server side). We don’t need to require users to make the zero-knowledge proofs succinct.
We can also have a framing that zkSNARKs can make an arbitraly computation zk and succinct, but that generalization icur a cost to the prover, hence zkSNARKs are not ideal for privacy applications.

## Using Schnorr’s protocol to prove the knowledge of discrete log

Given the following equation of [our setup](https://hackmd.io/XLu3oFIVRZuxF2Nfj1D50w),
$$s (r^{−1}R) − mr^{−1}G = Qa$$

we define
- $T = r^{−1}R$
- $U = mr^{−1}G$

We can use [Schnorr’s protocol](https://crypto.stanford.edu/cs355/19sp/lec5.pdf) to prove the knowledge of $s$.

**Prover**
$$
l \stackrel{$}{\leftarrow} \mathbb{Z_p} \\
W = lT\\
c = hash(T, p, Qa - U, W) \\
z = l + s * c
$$

**Verifier**
$$
c \stackrel{?}{=} hash(T, p, Qa, W) \\
zT \stackrel{?}{=} W + c(Qa - U)
$$

since
$$
zT = W + c(Qa - U) \\
\to (l + s * c)T = lT + c(Qa - U) \\
\to lT + c * sT = lT+ c(Qa - U) \\
$$

### Hiding $Qa$
However, not only do we want to prove the knowledge of $s$ in zk, but we also want to keep $Qa$ a secret, and prove that $Qa$ is in the set
$$M = \{Qa_0, Qa_1,.., Qa_n\}$$

Firstly, we hide $Qa$ by using a secret blinding factor $b$.
$$Qa_b = b * Qa$$
And then the ECDSA verification equation becomes
$$b * sT = b(Qa - U)$$

and Schnorr's protocol verification becomes
$$zT \stackrel{?}{=} W + c(Qa_b - U_b)$$
where now $z$ is
$$z = l + sb * c$$

### Proving membership
When using zkSNARKs, we could prove the membership $Qa \in M$ using a Merkle Proof, but since we're not using zkSNARKs, we need an alternative approach.

We could prove that we know a discrete log between $Qa_{ib}$ and one of $Qa_i$, without revealing which $Qa_i$ it is. I still haven't figured out a way to do this, but I think we can use something from [ring signatures](https://link.springer.com/content/pdf/10.1007/3-540-45682-1_32.pdf).

## About Keccak
I don't think this scheme can support Keccak, but there are ways to bypass Keccak in practice, considering that you only need to publish your public key once. For example, publishing your public key can simply be a part of signing up to Heyanon (although there needs to be an anonymity pool queue that users need to wait through before they submit their first message).
But in short, I feel we can come up with a way to bypass Keccak at the app level.