# 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\\{
&
\\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.
<center>
<img width="60%" src="https://github.com/asn-d6/curdleproofs/raw/main/doc/images/curdleproofs_overview.png"></img>
</center>
## Protocol
A formal description of the *curdleproofs* argument is provided in the figure below:
<center>
<img width="100%" src="https://github.com/asn-d6/curdleproofs/raw/main/doc/images/curdleproofs_prover.png"></img>
</center>
## 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](crate::same_permutation_argument) to demonstrate that $A$ is a commitment to $\sigma(\bm{a})$ for $\sigma()$ the permutation committed to with $M$.
- [SameMultiScalar argument](crate::same_multiscalar_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](crate::same_scalar_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}$.
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.