# Groth16 aggregation with public input trick ## Regular Groth 16 ### CRS * Random $\tau$ chosen during trusted setup as well as $\alpha$, $\beta$ * $n$ is number of gates. * $u_i$, $v_i$ and $w_i$ are the QAP polynomials created from the R1CS circuit $SRS = \{g_1^\alpha\, g_1^\beta, g_1^\delta, \{\{ g_1^{\tau^i}\}, \{g_1^{\alpha \tau^i}\}, \{g_1^{\beta \tau^i}\}\}_{i=0}^{n-1}, \{g_1^{\beta u_i(\tau) + \alpha v_i(\tau) + w_i(\tau)}\}_{i=0}^n\}, \{g^{\frac{\tau^it(x)}{\delta}}\}_{i=0}^{n-1},\\g_2^\beta, g_2^\delta, \{g_2^{\tau ^i}\}_{i=0}^{n-1}\}$ ### Prover **Settings**: * Regular proof is $\pi = (A, B, C)$. * $l+1$ is number of public inputs (+1 as first public input is "1" in R1CS) * Vector of public inputs $\phi = (a_0, \dots, a_{l})$ **Extension**: Prover computes the regular proof and computes the following additionally * $S = g_1^{\sum_{i=0}^{l} a_i (\beta u_i(\tau) + \alpha v_i(\tau) + w_i(\tau))}$ * Derive random challenge $z = H(\phi, \pi, S)$ * Compute the three following elements. * $U = g_2^{\sum_{i=0}^l a_i ( \frac{u_i(\tau) - u_i(z)}{\tau - z})}$ * $V = g_2^{\sum_{i=0}^l a_i ( \frac{v_i(\tau) - v_i(z)}{\tau - z})}$ * $W = g_2^{\sum_{i=0}^l a_i ( \frac{w_i(\tau) - w_i(z)}{\tau - z})}$ * Proof is $(\pi, S, U , V , W)$ ### Verifier * Compute the following three elements $u_z, v_z, w_z \in \mathbb{F_r}$: * $u_z = \sum_{i=0}^l u_i(z)$ * $v_z = \sum_{i=0}^l v_i(z)$ * $w_z = \sum_{i=0}^l w_i(z)$ * Check **as usual** * $e(A,B) = e(g_1^\alpha, g_2^\beta)e(S,g2)e(C,g2^\delta)$ * Check public input construction * $e(Sg_1^{-\beta u_z -\alpha v_z -w_z},g_2) = e(g_1^{\beta \tau - \beta z}, U)e(g_1^{\alpha \tau - \alpha z},V)e(g_1^{\tau - z},W)$ * These computations are done using the CRS
Last changed by  
 
Nicolas Gailly
600

Read more

Efficient threshold BLS & Encryption

This post explains an inherent tension between threshold BLS signature and Elgamal encryption for onchain verification, and then presents a way to augment such threshold network such that a smart contract can efficiently verify a signature and decrypt/verify encryption onchain. 21/03/23, Nicolas Gailly, Cryptonet team, Protocol Labs. Introduction For encryption/decryption and signing, we (usually) require a group, i.e. a single elliptic curve. However, using pairings, we have to choose between $\mathbb{G_1}$ and $\mathbb{G_2}$ (and even $\mathbb{G_t}$), each group have their pros and cons depending on the cryptographic protocol we want to use. In practice, $\mathbb{G_1}$ is usually preferred given it is much shorter and faster to compute in it, than its counter-parties. This choice of group comes up when designing threshold networks. Indeed, there is a distributed key lying in a group $\mathbb{G}$ which could be any of the three groups aforementioned. In particular, when using pairing equipped curves, a threshold network can be used to create threshold BLS signatures but it can also be used as a decryption oracle. In the latter, users encrypts towards the threshold network and push the encryption on-chain. This posts shows the pros and cons of using $\mathbb{G_1}$ and $\mathbb{G_2}$ for each and shows there is a tension between the two. This posts then shows a simple solution to get the best of both worlds. The technique is heavily inspired by a post by Kobi Gurkan on efficient multisignature verification onchain, translated to the threshold setting.

3/21/2023
Trusted Setup: KZG and PST

KZG trusted setup First Player First player has secret $s$ and generates $$ [s]_1, [s^2]_1 ... $$ as well as the "check" point $$ [s]_2 $$

1/31/2023
DKG Share Recovery

DKG in a few lines Each node $i$: has a private polynomial $$f_i(x) = a_0 + ... + a_{t-1}x^{t-1}$$ From that get the public poly $$F_i(x) = f_i(x) * G$$ generate shares for others $$s_{i,j} = f_i(j)$$ then sum each share it receives (from QUALified participants) + its own: final share is $$s_i = \sum_j s_{j,i}$$ final public polynomial $$F(x) = \sum_i F_i(x)$$

10/27/2022
DKG in SNARK - demo day

Recap on DKG Goal: Distributed key pair $P$ amongst $n$ parties such that $n/2 \lt t \lt n$ parties are required to collaborate to reconstruct it. Set of less than $t$ parties can not learn anything about $P$ Why: Used by drand for example, other system now like Axelar How: basic version is usually $n$ instances Verifiable Secret Sharing (VSS) in parallel

2/10/2022
Read more from Nicolas Gailly
Published on HackMD