Powers of Tau Proofs

Here's a starting point for the proofs: https://github.com/a16z/evm-powers-of-tau/blob/master/techreport/main.pdf.

You have P1,j−1,P2,j−1,…,Pn,j−1;P+,j−1P_{1, j - 1}, P_{2, j - 1}, \ldots, P_{n, j - 1}; P_{+, j - 1}.

Participant generates r←RF_p∗r \xleftarrow{R} \mathbb{F}\_p^*, and publishes P1,j,P2,j,…;P+,jP_{1, j}, P_{2, j}, \ldots; P_{+, j}. This should satisfy:

P1,j=r⋅P1,j−1P2,j=r2⋅P2,j−1 ⋮P+,j=r⋅P+,j−1\begin{aligned} P_{1, j} &= r \cdot P_{1, j - 1}\cr P_{2, j} &= r^2 \cdot P_{2, j - 1}\cr &\ \vdots\cr P_{+, j} &= r \cdot P_{+, j - 1}\cr \end{aligned}

The following properties need to be proved:

  1. The prover knows rr
  2. The prover correctly used rr, or at least, Pi,jP_{i, j} consist of a valid powers of tau setup, assuming the Pi,j−1P_{i, j-1} did.
  3. r≠0r \neq 0

The protocol above does 2. with pairings.

Using Maurer Proofs

c.f. my blog post on Maurer proofs

As a starting point, consider the following toy relation:

{(A,B,G;a,b) ∣cra⋅G=Ab⋅G=Bb=a2}\begin{aligned} &\{(A, B, G; a, b)\ |\\cr &\quad a \cdot G = A\cr &\quad b \cdot G = B\cr &\quad b = a^2\cr &\}\cr \end{aligned}

The tricky aspect is the b=a2b = a^2 part. The rest can be done with a Maurer proof.

One way around this is to tweak the relation slightly:

{(A,B,G;a,b) ∣cra⋅G=Aa⋅A=Bb⋅G=B}\begin{aligned} &\{(A, B, G; a, b)\ |\\cr &\quad a \cdot G = A\cr &\quad a \cdot A = B\cr &\quad b \cdot G = B\cr &\}\cr \end{aligned}

Because b=a2b = a^2, we have a⋅A=a2⋅G=b⋅G=Ba \cdot A = a^2 \cdot G = b \cdot G = B, so this relation is equivalent. Notice also that this relation is captured by the homomorphism:

φ(a,b):=(a⋅G,a⋅A,b⋅G)\varphi(a, b) := (a \cdot G, a \cdot A, b \cdot G)

A Maurer proof will work, wherein you check that φ(a,b)=(A,B,B)\varphi(a, b) = (A, B, B)

We can extend this to the degree 33 case as well:

{(A,B,C,G;a,b,c) ∣cra⋅G=Ab⋅G=Bc⋅G=Cb=a2c=a3}\begin{aligned} &\{(A, B, C, G; a, b, c)\ |\\cr &\quad a \cdot G = A\cr &\quad b \cdot G = B\cr &\quad c \cdot G = C\cr &\quad b = a^2\cr &\quad c = a^3\cr &\}\cr \end{aligned}

this time, we use the homomorphism:

φ(a,b,c):=(a⋅G,a⋅A,b⋅G,a⋅B,c⋅G)\varphi(a, b, c) := (a \cdot G, a \cdot A, b \cdot G, a \cdot B, c \cdot G)

with expected output (A,B,B,C,C)(A, B, B, C, C).

Tau Proof

The relation you want to prove is:

{(Pi,j,Pi,j−1;r) ∣ ri⋅Pi,j−1=Pi,j}\{(P_{i, j}, P_{i, j - 1}; r)\ |\ r^i \cdot P_{i, j - 1} = P_{i, j}\}

(taking the convention τ+=τ\tau^+ = \tau)

If you had a vector r\bold{r} such that ri=ri\bold{r}_i = r^i, then you could just use a standard Maurer proof here. The issue with that is that you need to enforce a specific relation between the vector elements.

We can use the proof we developed in the previous section to get around this restriction though.

We publish R:=r⋅G\bold{R} := \bold{r} \cdot G, and then create a proof for the following relation:

{(Pi,j,Pi,j−1,R;r) ∣cr∀i∈[n−1]. r1⋅Ri=Ri+1∀i∈[n]. ri⋅G=Ri∀i∈[n]. ri⋅Pi,j−1=Pi,j}\begin{aligned} &\{(P_{i, j}, P_{i, j - 1}, \bold{R}; \bold{r})\ |\\cr &\quad \forall i \in [n - 1].\ \bold{r}_1 \cdot \bold{R}_i = \bold{R}_{i + 1}\cr &\quad \forall i \in [n].\ \bold{r}_i \cdot G = \bold{R}_{i}\cr &\quad \forall i \in [n].\ \bold{r}_i \cdot P_{i, j - 1} = P_{i, j}\cr &\}\cr \end{aligned}

This can be done via a Maurer proof for the following homomorphism:

φ(r):=([r_i⋅R_i],[r_i⋅P_i,j−1])\varphi(\bold{r}) := ([\bold{r}\_i \cdot \bold{R}\_i], [\bold{r}\_i \cdot P\_{i, j - 1}])

With the expected output being:

(R_i≥2,[P_i,j])(\bold{R}\_{i \geq 2}, [P\_{i, j}])

The vector r\bold{r} has to be initialized to the powers of rr.