# Groth16 ## Metadata **Source**:: #from/zotero **Zettel**:: #zettel/fleeting **Status**:: #x **Authors**:: [[Jens Groth]] **Full Title**:: On the Size of Pairing-based Non-interactive Arguments **Category**:: #article **Date**:: [[2016-01-01]] **Created**:: [[2024-03-21]] **Document Tags**:: #bilinear-pairing #zero-knowledge-proof **URL**:: [eprint.iacr.org](https://eprint.iacr.org/2016/260) **Zotero App Link**:: [Open in Zotero](zotero://select/library/items/JUJFKVR7) **Zotero Web Link**:: [zotero.org](https://www.zotero.org/users/8290186/items/JUJFKVR7) **Topic**:: [[♯ Zero-Knowledge Proof]] ## Synopsis Notions differences comparing with [[RareSkills Authors - Groth16 Explained (Highlights)]] - What we call $\tau$ the paper calls $x$. - The paper's notation of $\tau$ is a collection of variables. You can ignore this. - The paper's notation does encrypted evaluation implicitly, since cryptographers don't need this explained. - The paper writes $\gamma$ and $\delta$ as division instead of inverse. - We write pairing as pairing(), the paper uses $[\mathbf{A}] \cdot [\mathbf{B}]$. - The paper refers to the proof tuple $([\mathbf{A}]_1, [\mathbf{B}]_2, [\mathbf{C}]_1)$ as $\pi$ - The paper refers to a collection of $G_1$ points from the trusted setup as $\sigma_1$, and $G_2$ points as $\sigma_2$. If you can read the paper's formulas without assistance at this point, that's good! You've taken your first step into a larger world! ### Setup $(\alpha, \tau) \gets \text{Setup}(\mathbb{R})$: Pick $\alpha, \beta, \gamma, \delta \gets \mathbb{Z}_p^*$. Define $\tau = (\alpha, \beta, \gamma, \delta)$ and compute $\sigma = (\sigma_1, \sigma_2)$, where $ \begin{align*} \sigma_1 &= \begin{pmatrix} \alpha, \beta, \delta, \{x^i\}_{i=0}^{n-1} \\ \{\tfrac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\gamma}\}_{i=0}^{\ell-1} \\ \{\tfrac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\delta}\}^m_{i=\ell} \\ \{\tfrac{x^i t(x)}{\delta}\}_{i=0}^{n-2} \end{pmatrix} \\ \sigma_2 &= (\beta, \gamma, \delta, \{x^i\}_{i=0}^{n-1}). \end{align*} $ ### Prove $\pi \gets \text{Prove}(\mathbb{R}, \sigma, a_1, \ldots, a_m)$: Pick $r, s \gets \mathbb{Z}_p$ and compute $\pi = ([\mathbf{A}]_1, [\mathbf{C}]_1, [\mathbf{B}]_2)$, where $ \begin{align*} \mathbf{A} &= \alpha + \sum_{i=0}^m a_iu_i(x) + r\delta\\ \mathbf{B} &= \beta + \sum_{i=0}^m a_iv_i(x) + s\delta\\ \mathbf{C} &= \sum_{i=\ell+1}^{\ell+m} a_i(\beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x)t(x) \\ &+ As + Br - rs\delta. \end{align*} $ ### Verify $0/1 \gets \text{Vfy}(\mathbb{R}, \sigma, a_1, \ldots, a_\ell, \pi)$: Parse $\pi = ([\mathbf{A}]_1, [\mathbf{C}]_1, [\mathbf{B}]_2) \in \mathbb{G}_1^2 \times \mathbb{G}_2$. Accept the proof if and only if $ \begin{align*} [\mathbf{A}]_1 \cdot [\mathbf{B}]_2 = [\alpha]_1 \cdot [\beta]_2 + \sum_{i=0}^\ell a_i \cdot \left[\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma}\right]_1 \cdot [\gamma]_2 + [\mathbf{C}]_1 \cdot [\delta]_2. \end{align*} $ ## Tips - In bn128, G1, G2 are elliptic curve extension. - When there are m constraints, use $\textrm{GF}(p^{m})$ field as coefficients, where each number in $\textrm{GF}(p^{m})$ can be represents as m - 1 degree polynomial. (See [[Finite Field#Prime Power Finite Field]])