Module curdleproofs::curdleproofs

The Curdleproofs shuffle argument

The aim of Curdleproofs is to build a shuffle argument of group elements. More precisely, given a public set of group elements $\bm{R} = ( R_1 , \ldots, R_\ell )$ and $\bm{S} = ( S_1 , \ldots, S_{\ell} )$ a shuffler computes a second set of group elements $\bm{T} = ( T_1, \ldots, T_\ell )$ and $\bm{U} = ( U_1, \ldots, U_{\ell} )$ and proves in zero knowledge that there exists a permutation \[ \sigma: [1, \ell] \mapsto [1,\ell] \] and a field element $k \in F$ such that for all $1 \leq i \leq \ell$ \[ T_{i} = k R_{\sigma(i)} \ \land \ U_i = k S_{\sigma(i)} \enspace . \] The permutation $\sigma()$ is committed to in $M \in G$ under some randomness $\bm{r}_M \in F^{n_{bl}}$.

Note that by the $\ell$-$ddh$ assumption it is difficult to distinguish the randomised ciphertexts from truly random values.

In other words we define a zero-knowledge proof for the relation

\[ R_{shuffle} = \left\{ \begin{array}{l l|l} (\bm{R}, \bm{S}, \bm{T}, \bm{U}, M); & \sigma & \bm{T} = \sigma ( k \bm{R} ) \\ & k \in F & \bm{U} = \sigma ( k \bm{S} ) \\ & \bm{r}_M\in F^{n_{bl}} & M = \sigma(1, \ldots, \ell) \times \bm{g} + \bm{r}_M \times \bm{h} \end{array} \right\} \]

Subarguments

Curdleproofs uses multiple subarguments to achieve its goals. A graphical depiction of the proof’s flow can be seen below.

Protocol

A formal description of the curdleproofs argument is provided in the figure below:

Protocol Informal Overview

Let $\ell>1$. The prover will take as input the $\bm{R}, \bm{S}, \bm{T}, \bm{U}, M$ and aims to prove knowledge of $\sigma(), k$ such that:

• $M = \sigma(1,2, \ldots, \ell) \times \bm{g}$ is a commitment to $\sigma()$
• $\bm{T} = \sigma(k \bm{R}) $ is a randomised permutation of $\bm{R}$
• $\bm{U}= \sigma(k \bm{S}) $ is a randomised permutation of $\bm{S}$

Initially all the public inputs are hashed to get a vector $\bm{a}$ of challenges. Then the prover computes values $A = \sigma(\bm{a}) \times \bm{g}$, $T = \bm{a} \times k\bm{R}$, and $U = \bm{a} \times k \bm{S}$ which it sends to the verifier. As part of our full construction we require zero-knowledge algorithms for proving and verifying three additional relations: a same permutation relation, a same scalar relation, and a same multiscalar relation.

The prover runs the following arguments:

• SamePerm argument to demonstrate that $A$ is a commitment to $\sigma(\bm{a})$ for $\sigma()$ the permutation committed to with $M$.
• SameMultiScalar argument to show the existence of some $\bm{x}$ such that $A = \bm{x} \times \bm{g}$, $T = \bm{x} \times \bm{T}$ and $U = \bm{x} \times \bm{U}$. Where $A = \sigma( \bm{a}) \times \bm{g} = \bm{x} \times \bm{g}$ this gives us that $T = \sigma(\bm{a}) \times \bm{T}$ and $U = \sigma(\bm{a}) \times \bm{U}$.
• SameScalar argument to show the existence of $k$ such that $T = k (\bm{a} \times \bm{R})$ and $U = k (\bm{a} \times \bm{S})$.

Together this means that

$T = k (\bm{a} \times \bm{R}) = \sigma(\bm{a}) \times \bm{T}$ and $U = \sigma(\bm{a}) \times \bm{U} = k (\bm{a} \times \bm{S})$

Where $\bm{a}$ is random this means that $k R_{\sigma(i)} = T_i $ for all $i$ except with negligible probability.

Note that the full protocol has some additional masking values that are included to ensure zero-knowledge. For simplicity we have ignored these terms in this overview.

Full Zero Knowledge Construction

Here we describe the additional steps required to achieve zero-knowledge.

Step 1

In the first step the prover and verifier both hash the instance to get a random vector of field elements $\bm{a} \in F^{\ell}$. There are no secrets involved in this step. The verifier parses all inputs to check that they are group or field elements.

Step 2

In the second step the prover computes a commitment $A$ to the permuted $\sigma(\bm{a})$. The vector $\sigma(\bm{a})$ is private because it reveals information about the secret permutation $\sigma()$. The prover therefore chooses a random blinding vector $\bm{r}_{A} \in \bm{F}^{n_{bl} - 2}$.

Looking forward, the same-permutation argument is only zero-knowledge provided $|\bm{r}_{A}| \geq 2$, thus we choose $n_{bl} \geq 4$.

The prover outputs $A$ together with a proof $\pi_{sameperm}$ demonstrating that $A$ is a blinded commitment to $\sigma(\bm{a})$ for $\sigma()$ committed to in the blinded commitment $M$. The verifier simply checks that this proof verifies.

Step 3

In the third step, the prover computes $R = \bm{a} \times \bm{R}$ and $S = \bm{a} \times \bm{S}$ and the verifier checks that $R$ and $S$ have been computed correctly.

The prover then computes commitments $com_T = (r_T G_T, T + r_T H)$, $com_U = (r_U G_U, U + r_U H )$ to $T = k R$ and $U = k S$ respectively. The commitments are blinded with the masking values $r_T$ and $r_U$. The prover then outputs $com_T, com_U$ together with a proof $\pi_{samescalar}$ demonstrating that $com_T$ and $com_U$ open to $(T,U)$ such that $T = k R$ and $U = k S$ for the same scalar $k$.

Step 4

In the fourth and final step, the prover and verifier first extend $ A’ = A + r_T G_T + r_U G_U$ such that $A’$ includes the blinders $r_T$ and $r_U$.

They also extend the basis $\bm{G}$ such that $A’$ is a commitment to $\bm{x} = (\sigma(\bm{a} \ || \ \bm{r}_A \ || \ r_T \ || \ r_U))$ under the basis $\bm{G}$.

Now if $\bm{T}’ = (\bm{T} \ || \ \bm{0} \ || \ H \ || 0 )$ for $\bm{0}$ a vector of length $n_{bl} - 2$ with every element equal to the identity element then \[ com_{T,2} = k R + r_T H = \bm{x} \times \bm{T}’ = \sigma( \bm{a} ) \times \bm{T} + r_T H \] then we have that $k R = \sigma(\bm{a}) \times \bm{T}$ as required. A similar argument shows that $k S = \sigma(\bm{a}) \times \bm{U}$.

Thus the prover outputs a proof $\pi_{samemultiscalar}$ demonstrating that $com_{T}$ and $com_{U}$ contain $\sigma( \bm{a} ) \times \bm{T}$ and $\sigma( \bm{a} ) \times \bm{U}$ respectively.

Outcome

The prover returns the proof \[ \pi_{shuffle} = (A, com_T, com_U, R, S, \pi_{sameperm}, \pi_{samescalar}, \pi_{samemultiscalar}). \] The verifier returns $1$ if and only if all checks pass.

Malicious randomizer attack

The prover might attempt to trick the verifier by using a randomizer $k=0$. This results in all output ciphertexts vanishing, while the proof is still considered valid (since inputs were shuffled and a randomizer was applied). To defend against this attack, the verifier must make sure that at least the first ciphertext is not the point at infinity.

Structs

CurdleproofsCrs

The Curdleproofs CRS

CurdleproofsProof

A Curdleproofs proof object

Functions

generate_crs

Generate a randomly generated CRS