Proofs

Security Proofs #

To be added.

Definitions #

Definition 1 (Polynomial Commitment Scheme). A polynomial commitment scheme (PCS) is an interactive proof system that enables $\mathcal{P}$ to convince $\mathcal{V}$ that he knows a polynomial, without revealing the polynomial directly. $\mathcal{P}$ and $\mathcal{V}$ run the protocol in three moves: gen, com, and open. [Plonk]

Definition 2 (Polynomial IOP). Let $\mathcal{R}$ be a set of the relations among polynomials $\{P_i\}$. Let $\mathcal{C}_f$ is the commitment to $f$. Given common input $\mathcal{R}(\{P_i\})$ to $\mathcal{P}$ and $\mathcal{V}$, and private input $\{P_i\}$ to $\mathcal{P}$, they run the following protocol:

  1. $\mathcal{P}$ converts the relations into polynomials $\{Q_j\}$
  2. $\mathcal{P}$ commits to $\{P_i\}$ and $\{Q_j\}$, and sends the commitments to $\mathcal{V}$
  3. $\mathcal{V}$ sends a random challenge $\xi$
  4. $\mathcal{P}$ runs open for $\{P_i(\xi)\}$ and $\{Q_j(\xi)\}$ and outputs the result
  5. $\mathcal{V}$ checks:
    • the evaluations of $P_i(\xi)$ and $Q_j(\xi)$ are correct
    • $\{Q_j\}$ satisfy $\mathcal{R}(\{P_i\})$

At the end of the protocol, $\mathcal{V}$ outputs $\textbf{acc}$ if and only if the two conditions hold, otherwise $\textbf{rej}$.

Moreover, a Poly-IOP has to satisfy the following properties.

Definition 3 (Completeness). If each pair of $(\mathcal{C}_{P_i},P_i)$ and $(\mathcal{C}_{Q_j},Q_j)$ is valid and $\{Q_j\}$ satisfy $\mathcal{R}(\{P_i\})$, $\text{Pr}[out_{\mathcal{V}}=\textbf{acc}]=1$.

Definition 4 (Soundness). If $(\mathcal{C}_{P_i},P_i)$ or $(\mathcal{C}_{Q_j},Q_j)$ are not a valid pair, or $\{Q_j\}$ does not satisfy $\mathcal{R}(\{P_i\})$, $\text{Pr}[out_{\mathcal{V}}=\textbf{rej}]\ge{1-\text{negl}(k)}$.

Definition 5 (Zero Knowledge). For every possible set of relations $\mathcal{R}$, there exists a probabilistic polynomial time simulator $\mathcal{S}$ that can produce $\{\mathcal{C}_{P_i}^*\},\{\mathcal{C}_{Q_i}^*\}$ and the corresponding proofs making $\mathcal{V}$ output $\textbf{acc}$; the proofs generated by $\mathcal{S}$ are computationally indistinguishable from those produced by $\mathcal{P}$.