Soundness of music

This week's puzzle is all about soundness - the requirement of a proof system that it should not be possible to prove false statements.

Here, we use a toy proof system based on BCTV14 which is unsound.

The proof system

This proof system is intended to allow a prover to show that a certain set of arithmetic constraints is satisfiable. Each constraint is of the form:

$$[a_1,\dots ,a_m]\ast [v_1,\dots ,v_m{]}^T+[a_1,\dots ,a_m]\ast [v_1,\dots ,v_m{]}^T=[c_1,\dots ,c_m]\ast [v_1,\dots ,v_m{]}^T$$

If you're familiar with the concept of rank-1 constraint systems, the format of an R1CS constraint may look similar. However, our constraints are much more limited: our kind of constraint system can only describe a very specific kind of arithmetic relations. In particular, it is not universal, since multiplication of variables is not possible. However, we can still prove statements such as 1+1+1+1=4.

Constraints to polynomials

Each variable can be represented by a pair of polynomials, one which encodes every time that variable is an input in a constraint, and one polynomial which encodes every time that variable is an output in a constraint.

First, let's fix a domain

${\omega }_1,\dots ,{\omega }_m\in \mathbb{F}$, one field element for each constraint. (In general, these will be roots of unity; for our purposes, they only need to be distinct from each other)

Then the input polynomial

$A_i$ for

$v_i$ is defined as a polynomial of degree

$n+1$ such that for all

$j\in \{1,\dots ,n\}$, if

$$A_i({\omega }_j)=a_i$$

where

$a_i$ comes from constraint

$C_j$.

We can think of this polynomial as encoding the coefficients of the variable in each constraint.

Similarly, the output polynomial

$C_i$ for each variable is defined as a polynomial of degree

$n+1$ such that for all

$j\in \{1,\dots ,n\}$

$$C_i({\omega }_j)=c_i$$

where

$c_i$ comes from constraint

$C_j$.

Together with the vanishing polynomial

$Z=(x-{\omega }_1)\cdots (x-{\omega }_n)$, defined so

$Z({\omega }_j)=0$ for all

$j$, the polynomials

$A_1,C_1,\dots ,A_m,C_m,Z$ define what we will call the "circuit" for our proving system.

Trusted setup

Our succinct proving system requires a trusted setup.

Suppose we have

$n$ constraints over

$m$ variables, with polynomials

$A_1,C_1,\dots ,A_m,C_m,Z$. We use the pairing-friendly BLS12-381 elliptic curve, with groups

${\mathbb{G}}_1,{\mathbb{G}}_2$.

Using the notation

$[x{]}_1=[x]G$ and

$[x{]}_2=[x]H$, where

$G$ is a generator in

${\mathbb{G}}_1$ and

$H$ is a generator in

${\mathbb{G}}_2$ and

$[x]G$ refers to scalar multiplication by

$x$.

Trusted setup elements
Powers of tau	$[1{]}_1,[\tau {]}_1,[{\tau }^2{]}_1,\dots ,[{\tau }^m{]}_1$
Input polynomial commitments	$[\rho A_1(\tau ){]}_1,\dots ,[\rho A_m(\tau ){]}_1$
$\alpha$ Input polynomial commitments	$[{\alpha }_I\rho A_1(\tau ){]}_1,\dots ,[{\alpha }_I\rho A_m(\tau ){]}_1$
Output polynomial commitments	$[\rho C_1(\tau ){]}_1,\dots ,[\rho C_m(\tau ){]}_1$
$\alpha$ Output polynomial commitments	$[{\alpha }_O\rho C_j(\tau ){]}_1,\dots ,[{\alpha }_O\rho C_m(\tau ){]}_1$
$K$	$\beta \rho (A_1(\tau )+C_1(\tau )){]}_1,\dots ,[\beta \rho (A_m(\tau )+C_m(\tau )){]}_1$
${\alpha }_I$	$[{\alpha }_I{]}_2$
${\alpha }_O$	$[{\alpha }_O{]}_2$
$\gamma$	$[\gamma {]}_2$
$\beta \gamma$	$[\beta \gamma {]}_2$
Vanishing polynomial	$[\rho Z(\tau ){]}_2$

This trusted setup mostly copies the BCTV14 trusted setup, with minor modifications to the constraint format. In theory, the elements of the trusted setup help the verifier check that a proof is properly constructed.

For the puzzle, there was no multi-party computation ceremony, or any other special measures taken; random values of

$\tau ,\rho ,{\alpha }_I,{\alpha }_O,\beta ,\gamma$ are taken and the trusted setup values computed directly and honestly.

Creating a proof

Suppose an assignment of values

$x_1,\dots ,x_m$ to the variables

$v_1,\dots ,v_m$ satisfies all constraints. Then equality:

$$(x_1{A}_1({\omega }_1)+\dots +x_m{A}_m({\omega }_1))+(x_1{A}_1({\omega }_1)+\dots +x_m{A}_m({\omega }_1))=x_1{C}_1({\omega }_1)+\dots +x_m{C}_m({\omega }_1)$$

must hold, because it simplifies to:

$$[a_1,\dots ,a_m]\ast [x_1,\dots ,x_m{]}^T+[a_1,\dots ,a_m]\ast [x_1,\dots ,x_m{]}^T=[c_1,\dots ,c_m]\ast [x_1,\dots ,x_m{]}^T$$

which is simply constraint 1. Therefore, the polynomial equation:

$$(x_1{A}_1(x)+\dots +x_m{A}_m(x))+(x_1{A}_1(x)+\dots +x_m{A}_m(x))=x_1{C}_1(x)+\dots +x_m{C}_m(x)$$

must hold over the entire domain

${\omega }_1,\dots ,{\omega }_n$. Further, this polynomial equation holds over the domain if and only if the assignment

$x_1,\dots ,x_m$ actually satisfies every constraint; therefore, we can simply prove that this polynomial equation holds over this domain, and then conclude the constraint system is satisfied.

Rearranging everything to the left and denoting it as

$P(x)$:

$$P(x)=(x_1{A}_1(x)+\dots +x_m{A}_m(x))+(x_1{A}_1(x)+\dots +x_m{A}_m(x))-(x_1{C}_1(x)+\dots +x_m{C}_m(x))$$

We get that

$P(x)=0$ for all

$x\in \{{\omega }_1,\dots ,{\omega }_n\}$. Therefore,

$P(x)$ is divisible by the vanishing polynomial

$Z(x)$; put another way, there exists a polynomial

$H(x)$ such that

$P(x)=H(x)\ast Z(x)$.

Therefore, if we compute a polynomial commitment

${\pi }_H=[P(\tau )/Z(\tau ){]}_1$, a verifier should be able to confirm that

$P(x)=0$ over the correct domain.

We also compute some additional proof elements, which encode the private inputs and also help the verifier verify this fact:

$${\pi }_I=\sum _{x_i\text{ is private}}{x}_i[\rho A_i(\tau )]$$

$${\pi }_I^{\prime }=\sum _{x_i\text{ is private}}{x}_i[{\alpha }_I\rho A_i(\tau )]$$

$${\pi }_O=\sum _{x_i}{x}_i[\rho C_i(\tau )]$$

$${\pi }_O^{\prime }=\sum _{x_i}{x}_i[{\alpha }_O\rho O_i(\tau )]$$

$${\pi }_K=\sum _{x_i}[\beta \rho (A_1(\tau )+C_1(\tau )){]}_1,\dots ,[\beta \rho (A_m(\tau )+C_m(\tau )){]}_1$$

The final proof is

$({\pi }_I,{\pi }_I^{\prime },{\pi }_O,{\pi }_O^{\prime },{\pi }_K,{\pi }_H)$

Verifier

The given verifier takes in the public inputs

$x_1,\dots ,x_p$. The public inputs get encoded into:

$${\pi }_{PI}=\sum _{x_i\text{ is public}}{x}_i[\rho A_i(\tau )]$$

The verifier checks, where

$e(\cdot ,\cdot )$ is the pairing operation:

$$e({\pi }_I^{\prime },H)=e({\pi }_I,[{\alpha }_I{]}_2)$$

$$e({\pi }_O^{\prime },H)=e({\pi }_O,[{\alpha }_O{]}_2)$$

$$e({\pi }_K,[\gamma {]}_2)=e({\pi }_{PI}+{\pi }_I+{\pi }_O,[\beta \gamma {]}_2)$$

$$e({\pi }_{PI}+{\pi }_I+{\pi }_{PI}+{\pi }_I-{\pi }_O)=e({\pi }_H,[\rho Z(\tau ){]}_2)$$

The final pairing effectively checks the condition that

$P(x)=H(x)Z(x)$ as required.

Soundness Bugs

The proof system in this puzzle has two soundness bugs; the verifier accepts proofs even when the constraint system is unsatisfiable with given public inputs.

Bug 1

The first bug is an implementation bug. Recall that for variable

$v_i$, the polynomials

$A_i$ and

$C_i$ were defined as a polynomial of degree

$n+1$ with certain values on a domain. In the puzzle,

$A_i$ and

$C_i$ were interpolated without regard to the resulting degree, which meant that

$A_i$ sometimes was degenerate. When this happens for a public input variable, the verifier may ignore this public input.

The correct fix is to ensure that every polynomial is actually degree

$n+1$. This can be achieved by taking the polynomial mod

$Z(x)$ and adding

$Z(x)$, since

$Z(x)$ is known to be exactly degree

$n+1$. Since zero-knowledge blinding wasn't necessary for this puzzle, this necessary step was omitted.

Bug 2

The second bug is a conceptual bug, based on the one that occurs in BCTV14. The trusted setup includes terms:

$$[{\alpha }_I\rho A_1(\tau ){]}_1,\dots ,[{\alpha }_I\rho A_p(\tau ){]}_1$$

which are not used anywhere by the prover or verifier.

However, these elements can be used to alter any valid proof for public input

$x_1,\dots ,x_p$ to work for an arbitrary public input:

$${\eta }_I={\pi }_I+\sum _{i=0}^p(x_i-x_i^{\prime })[\rho A_i(\tau ){]}_1$$

$${\eta }_I^{\prime }={\pi }_I^{\prime }+\sum _{i=0}^p(x_i-x_i^{\prime })[{\alpha }_I\rho A_i(\tau ){]}_1$$

The proof

$({\eta }_I,{\eta }_I^{\prime },{\pi }_O,{\pi }_O^{\prime },{\pi }_K,{\pi }_H)$ will verify against the arbitrarily-chosen public input

$x_1^{\prime },\dots ,x_p^{\prime }$.

The fix for this bug is to remove the unnecessary elements of the trusted setup.