Tornado Cash Protocol Documentation

A Non-Interactive Zero-Knowledge (NIZK) proof system is a zero-knowledge protocol that eliminates interaction between the Prover ($P$) and the Verifier ($V$). Instead of multiple rounds of communication, the interaction is reduced to a single message sent from the Prover to the Verifier.

This is achieved by introducing a shared string that both parties can reference. This string is known as a Common Reference String (CRS).

Key Concepts:

• Common Random String (CRS): A string generated from a uniform distribution.
• Common Reference String (CRS): A generalization of the above, where the string can be generated from any distribution. In most technical contexts, the term CRS refers to the Common Reference String.
• Common Reference String Model: A model where all parties in the protocol have access to a string generated from a specific distribution.

Security Requirements:

To be considered a valid NIZK system for a language $\mathcal{L}$, the system must satisfy:

1. Completeness: For any $x \in \mathcal{L}$, the probability that the Verifier accepts the proof is $\operatorname{Pr}[V(x, \sigma, P(x, \sigma))=1] \geq \frac{2}{3}$.
2. Soundness: For any $x \notin \mathcal{L}$ and any adversary $B$, the probability that the Verifier accepts is $\operatorname{Pr}[V(x, \sigma, B(x, \sigma))=1] \leq \frac{1}{3}$.

Note: $\sigma$ represents the Common Reference String, a random variable distributed uniformly over ${0,1}^{\operatorname{poly}(|x|)}$.

An Interactive Proof System is a proof system where a Prover ($P$) and a Verifier ($V$) interact through a series of messages. This differs from non-interactive proof systems where the Prover sends a single message to the Verifier for validation.

To formally define an interactive proof system for a language $\mathcal{L}$, the pair of machines $(P, V)$ must satisfy two properties:

1. Completeness: For any string $w \in \mathcal{L}$, the probability that the Verifier accepts the proof from the Prover is high: $$\operatorname{Pr}[\langle P,V \rangle (w) = 1 ] \ge \frac{2}{3}$$
2. Soundness: For any string $w \notin \mathcal{L}$ and any malicious Prover $P^$, the probability that the Verifier accepts is low: $$\operatorname{Pr}[\langle P^,V \rangle (w)=1 ] \le \frac{1}{3}$$

Key Constraints:

• The Verifier ($V$) must operate in polynomial time.
• The Prover ($P$ or $P^*$) has no computational limits.
• The error probability (e.g., $1/3$) can be reduced exponentially through repetition (amplification lemma) to approach perfect completeness (1) and perfect soundness (0).

In the context of split non-interactive linear proofs, an adaptive adversary might attempt to learn information from the CRS to manipulate the proof matrix $\mathit\Pi$.

A Common Reference String is considered disclosure-free if the prover cannot gain any useful information from it that would allow them to create a valid proof for an invalid statement.

Formally, a split non-interactive linear proof $(\mathrm{Setup}, \mathrm{Prove}, \mathrm{Verify})$ is disclosure-free if: $$\operatorname{Pr}\left[ \begin{array}{c} (R, z) \leftarrow \mathcal{R}\left(1^\lambda\right) ; T \leftarrow \mathcal{A}(R, z) ;\left(\boldsymbol\sigma_1, \boldsymbol\sigma_2, \boldsymbol\tau\right),\left(\boldsymbol\sigma_1^{\prime}, \boldsymbol\sigma_2^{\prime}, \boldsymbol\tau^{\prime}\right) \leftarrow \operatorname{Setup}(R): \ \boldsymbol\sigma_1 \cdot T \boldsymbol\sigma_2=0 \text { if and only if } \boldsymbol\sigma_1^{\prime} \cdot T \boldsymbol\sigma_2^{\prime}=0 \end{array} \right] \approx 1$$

This property ensures that the security (soundness) of the original linear proof is preserved when converted into a non-interactive argument using Type III pairings.

A Quadratic Arithmetic Program (QAP) is a formal way to represent an arithmetic circuit as a single polynomial equation. This allows multiple gates to be verified simultaneously using polynomial interpolation.

Mathematical Representation

An arithmetic circuit over a finite field $\mathbb{F}$ with $m$ wires can be generalized by the following equation for its gates:

$$\sum_{i=0}^m a_i u_{i} \cdot \sum_{i=0}^m a_i v_{i}=\sum_{i=0}^m a_i w_{i}$$

Where:

• $a$ represents the wire variables ($a_0 = 1, a_1, \ldots, a_m \in \mathbb{F}$).
• $u, v, w$ are constants defining the gate behavior ($u_i, v_i, w_i \in \mathbb{F}$).

Gate Specializations

• Multiplication Gate: For constants $i, j, k$, the operation $a_i \cdot a_j = a_k$ is represented by setting $u_i = v_j = w_k = 1$ and all other constants to $0$.
• Addition Gate: For constants $i, j, k$, the operation $a_i + a_j = a_k$ is represented by setting $\sum a_i u_i = a_i + a_j$, $\sum a_i v_i = 1$, and $\sum a_i w_i = a_k$.

QAP Construction via Polynomial Interpolation

To represent $n$ gates in a single equation, choose $n$ distinct elements $r_1, \ldots, r_n$ from $\mathbb{F}$. Use polynomial interpolation to find degree $n-1$ polynomials $u_i(x), v_i(x), w_i(x)$ such that for any gate $q$ and wire $i$:

$$u_i(r_q) = u_{i,q}, \quad v_i(r_q) = v_{i,q}, \quad w_i(r_q) = w_{i,q}$$

The $q$-th gate is then satisfied if:

$$\sum_{i=0}^m a_i u_i(r_q) \cdot \sum_{i=0}^m a_i v_i(r_q) = \sum_{i=0}^m a_i w_i(r_q)$$

All gates are satisfied if the following holds modulo $t(x) = \prod_{q=1}^n (x - r_q)$:

$$\sum_{i=0}^m a_i u_i(X) \cdot \sum_{i=0}^m a_i v_i(X) \equiv \sum_{i=0}^m a_i w_i(X) \pmod{t(X)}$$