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 $P_{1,j-1},P_{2,j-1},\dots ,P_{n,j-1};P_{+,j-1}$.

Participant generates $r\stackrel{R}{\leftarrow }\mathbb{F}\_p^{\ast }$, and publishes $P_{1,j},P_{2,j},\dots ;P_{+,j}$. This should satisfy:

$$\begin{array}{rl}{P}_{1,j}& =r\cdot P_{1,j-1}\\ P_{2,j}& =r^2\cdot P_{2,j-1}\\ & ⋮\\ P_{+,j}& =r\cdot P_{+,j-1}\end{array}$$

The following properties need to be proved:

1. The prover knows $r$
2. The prover correctly used $r$, or at least, $P_{i,j}$ consist of a valid powers of tau setup, assuming the $P_{i,j-1}$ did.
3. $r\ne 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:

$$\begin{array}{rl}& \{(A,B,G;a,b)|\\ cr& a\cdot G=A\\ & b\cdot G=B\\ & b=a^2\\ & \}\end{array}$$

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

One way around this is to tweak the relation slightly:

$$\begin{array}{rl}& \{(A,B,G;a,b)|\\ cr& a\cdot G=A\\ & a\cdot A=B\\ & b\cdot G=B\\ & \}\end{array}$$

Because $b=a^2$, we have $a\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:

$$\phi (a,b):=(a\cdot G,a\cdot A,b\cdot G)$$

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

We can extend this to the degree $3$ case as well:

$$\begin{array}{rl}& \{(A,B,C,G;a,b,c)|\\ cr& a\cdot G=A\\ & b\cdot G=B\\ & c\cdot G=C\\ & b=a^2\\ & c=a^3\\ & \}\end{array}$$

this time, we use the homomorphism:

$$\phi (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)$.

Tau Proof

The relation you want to prove is:

$$\{(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 $\mathbf{r}$ such that ${\mathbf{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 $\mathbf{R}:=\mathbf{r}\cdot G$, and then create a proof for the following relation:

$$\begin{array}{rl}& \{(P_{i,j},P_{i,j-1},\mathbf{R};\mathbf{r})|\\ cr& \forall i\in [n-1].{\mathbf{r}}_1\cdot {\mathbf{R}}_i={\mathbf{R}}_{i+1}\\ & \forall i\in [n].{\mathbf{r}}_i\cdot G={\mathbf{R}}_i\\ & \forall i\in [n].{\mathbf{r}}_i\cdot P_{i,j-1}=P_{i,j}\\ & \}\end{array}$$

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

$$\phi (\mathbf{r}):=([\mathbf{r}\_i\cdot \mathbf{R}\_i],[\mathbf{r}\_i\cdot P\_i,j-1])$$

With the expected output being:

$$(\mathbf{R}\_i\ge 2,[P\_i,j])$$

The vector $\mathbf{r}$ has to be initialized to the powers of $r$.