**Home Edition**

# Discussion notes #6: The Turbo-PLONK program syntax for specifying SNARK programs
Presenter: Ariel Gabizon

Authors:
- Ariel Gabizon
- Zac Williamson

To be presented on 2020-05-07.

Resources:
* [Latest PDF version](https://docs.zkproof.org/pages/standards/accepted-workshop3/proposal-turbo_plonk.pdf)
* [Miro Whiteboard](https://zkproof.org/workshop3-board)
* [SoK Working Group](https://community.zkproof.org/g/WG_PLONK)
* [Additional related links](https://hackmd.io/@HtwXZr-PTFCniCs7fWFSmQ/B1AwbdI_8)

----

## Real-time notes
_Note taker:_ Michele Orrù

Before: program -> constraints -> polynomials -> proofs
More recently: program-> constraints/polynomials -> proofs

it's worthwhile to work directly with the polynomials when you're representing your program. [example](https://ethresear.ch/t/using-polynomial-commitments-to-replace-state-roots/7095)

A ranged polynomial protocol is a prover/verifier protocol with an ideal trusted party.
All that the prover does is talk to the _ideal party_, and the messages are polynomials (up to a certain degree).
There is a set of polynomials that are part of the protocol definition, together with a subset $\mathcal{H}$ of elements of the field.
At the end, the verifier accepts if some polynomial identity between the preprocessed polynomials holds over $\mathcal{H}$. This is done talking to the _ideal party_.

How do you measure the complexity of these protocols? It's something like

$d(P)$ = sum of the degree of prover's polynomials - set where the verifier is checking + the degree of the identity being checked

**example 1**: multiset equality check. We want to check that two vectors are contain the same elements
$\{a_1, b_1, c_1\} = \{a_2, b_2, c_2\}$.
You can show easily with the Schwartz-Zippel lemma that
$$
(a_1 + \gamma)(b_1 + \gamma)(c_1 + \gamma) = (a_2 + \gamma)(b_2 + \gamma)(a_3 + \gamma)
$$

Take the set $\mathcal{H}$ be a multiplicative subgroup
$\mathcal{H} = \{\alpha^1, \dots, \alpha^n\}$
It's interesting to study this set in the Lagrange basis, i.e. the set of polynomials that are indicators for elements in $\mathcal{H}$.

Checking products. Ther prover is computing a polynomial $Z$ such that $Z(\alpha) = 1$, $Z(\alpha^i) = \prod_{j < i} f(\alpha^j)/g(\alpha^j)$
Send $Z$ to the ideal party, and the verifier checks that $Z$ is really accumulating the values of $f$ over $g$:
$$
\begin{aligned}
L_1(x)(Z(x)-1 ) = 1\\
Z(x)f(x) = Z(\alpha x)g(x)
\end{aligned}
$$
where $L_1$ is the indicator for $\alpha$.
What does the measure of before look like here? $d(P) = n + 2n - |\mathcal{H}| = 2n$.

**example 2** given a polynomial $f$ of degree at most $n$, check if the evaluation $f(x), \forall x \in \mathcal{H}$ is in the range $[1\dots M]$.
Here, the prover computes a sorted version of $f$, another polynomial $s \in \mathbb{F}[x]$ such that $\deg s < n$ and
$$
s(\alpha^i)\leq s(\alpha^{i+1})
$$
Now the prover sends $s$ to the ideal party, and the verifier checks a multi-set equality between $s$ and $f$, $s(\alpha) = 1; s(\alpha^n) = M$.
Finally, it checks for each $x \in \mathcal{H}, x \neq 1$:
$$
(s(\alpha x ) - s(x))^2 = s(\alpha x) - x
$$
In this case, we have $d(P) = 3n$.

Daira: I guess $s$ must be forced to have the evaluation of $\alpha$ and $\alpha^n$ to be respectively $1, M$.

Question: can you do a protocol with the same complexity, but for $M^2$?

Izzy: in the last example, $3$ constraints per check is it really much better than generic methods?
Ariel: ??? `did he say it's independent from M`????
Daira: how general is this? what categories of proof systems besides PLONK does it apply to?
Ariel: ?? ?
Izzy: you mentioned these are examples for special cases, but aren't these also used in other works?
Ariel: in Turbo PLONK we have a protocol like this where the verifier is limited to ask for an identity that does not involve randomness, and one identity that does incorporate verifier randomness. One of these identity was the check of a permutation.
The multi-set check is part of the permutation check, but in the proposal ????
Carla: this multiset equality when you think of it as proving that one set is a permutation of the other, does not make a difference if the permutation is known publicly?
Ariel: in PLONK we check a public permutation, which describes the wiring of a circuit. Sometimes you want to check that there is a secret permutation (e.g. in this range check)
Daira: why you don't have to include $\beta$ in this?
Ariel: we have a simpler situation where we just have to prove that there is some permutation, not a specific permutation.
Carla: how successful have you been with getting people outside the crypto community involved?
Daira: it's useful anyways, also for cryptographers, to separate out the crypto part
Ariel: in Sonic it was very clear that you can look at the polynomial commitment as a separate thing, and this made much more sense. I'd like to present this to a mathy/pure CS audience .000.000.007
Daira: how did you derive the cost metric?
Ariel: In the real protocol, the prover is going to have to commit on all these polynomials. So that's where degree comes out???
Daira: is that true? If you use some commitment schemes for instance it's not linear
Ariel: i guess the question is if commiting to a bunch of these polynomials grows more of less linearly with their degree. Also, D- H is the commitment to the quotient polynomial, that you open on a bunch of random points.
I didn't include the opening costs, but it doesn't seem so terrible.
Daira: in Halo you need to pay that cost at the end
Zac: `I wasn't able to follow, sorry`

Daira: do we think there's something here worth standardizing? something general enough that people want to work on?
Izzy: it would be great if there was a spec of this whole thing so that it'd be easy to use all of this together in bigger systems??
Daira: aren't we trying to design a proof system on the fly?
Daniel: it seems there's something still to work out?
Carla: I think this framework can be really useful, but we need to test if this is really useful.
Daira: should the focus of this working group be in the initial proposal of PLONK
Dario: how much does this fit into standardizing constraint systems. here we're saying there's a wide variety of constraint systems
Daniel: pools. vote! \o/

Result: let's do Turbo PLONK, focusing on the encoding.
Carlos: R1CS -> PLONK is difficult, the reverse is pretty strightforward
Daira: maybe we need to focus on an intermediate language that can be applied to a bunch of different systems.

----
Charter Ideas

Goals:

-

Milestones:

-

----

## Discussion topics

_Suggestions welcome! Please append at the end, and the moderators will incorporate into the schedule._

~15 minutes each, by default.

1. What do you think of the ranged polynomial protocol framework? Should it be standardized?
2. Are there other similar abstractions that could be a good standard?
3. "Sequential" (state transition--based) vs "parallel" (circuit or constraint--based) abstractions for computations. (XXX: sorry, not clear this makes any sense now; was based on the content of the proposal, but was not discussed in this talk.)