Plonk

https://vitalik.eth.limo/general/2019/09/22/plonk.html

Plonk

[!Definition]
Permutations over Lagrange-bases for Oecumenical(unity of different areas) Non-interactive arguements of knowledge

Improvemnets

1. universal and updatable trusted setup [[Groth16 vs Plonk vs Halo2]]
   1.1 one single trusted setup for the whole scheme in any program
   1.2 multiple parties can participate in the trusted setup sequentially (참여자 모두를 미리 알필요는 없다) -> 한 명만 정직하기만 하면 secure 함

2. relies on one single standarized component "polynomial commitment"
   -> proof size, sequrity assumption -> trade off
   -> can share many tools for arithmetization

How it works

기본적으로 A를 B로 바꾸는 문제이다

A : input으로 x가 들어온 문제 P에 대해 output y를 달라
B : 방정식을 만족하는 값들을 달라

snark의 qap도 같은 방식이다.

ex) P : give me a solution to this sudoku
P를 스도쿠 검증자로 설정 + encoded initial values
Y를 1로 설정(맞다는 의미)
이를 만족시키는 입력값 X가 solution이 된다.

two constraints

• gate constraints
  equations between wires attached to the gate
• copy constraints
  이름은 다르지만 같은 와이어에 대한 equality claim

결국엔 이 두개의 constraints를 나타내는 polynomial equations가 굉장히 작은 수로 줄어야 한다.

Setup

$$ Q(Li)a{i}+ Q(Ri)b{i}+ Q(Oi)c{i}+Q(Mi)a_ib{i}+ Q_{ci}= 0$$

$a_i$ , $b_i$, $c_i$ : i번째 게이트의 왼쪽 변수, 오른쪽 변수, output (user에게 받은 변수)
각 Q는 constant이다.

addition gate : $Q_{(Li)}= 1$, $Q_{(Ri)}= 1$, $Q_{(Mi)}= 0$, $Q_{(Oi)}= 1$, $Q_{(Ci)}= 0$
multiplication gate : $Q_{(Li)}= 0$, $Q_{(Ri)}= 0$, $Q_{(Mi)}= 1$, $Q_{(Oi)}= -1$, $Q_{(Ci)}= 0$

위 식은 아직 copy constraint를 고려하지 않는다

prover가 prove(=내가 bunch of imput satisfying equations를 가지고 있다) 하고 싶은데 big problem이 있지만 structured되어 있다
=> 그래서 수학적인 방식으로 compress한다

From Linear systems to Polynomials

polynomial : 많은 values를 캡슐화 시키는 single object로 tool

우리는 polynommial을 coefficient form으로 보지만 evalutation form으로도 볼 수 있다. (y = x^3 - 5x^2 + 7x -2)
-> 좌표 (0,1,2,3)에서 각각(-2,1,0,1) evalutation을 갖는 차수 < 4 다항식이라고 생각할 수 있음

polynomial을 통해 여러 방정식을 "하나의 방정식"으로 재해석 할 수 있다.
따라서 evaluation form으로 값을 다항식으로 묶고, 라그랑주 보간법을 통해 다항식을 재구성할 수 있다.
여러 다항식 -> 하나의 다항식

minimal polynomial Z(x) : 특정한 좌표에서 0을 반환하는 다항식 -> 특정한 범위에서 다항식 값을 0으로 설정 가능
ex) 특정 좌표에서 0이 되도록 하는 다항식 정의 -> 그 좌표에서 방정식 만족

그런데 이 equation에서 x1, x2, x3 variable들이 방정식마다 다르다 왜냐하면 prover가 여러개 갖고 있기 때문
-> 그래서 constant 보다 polynomial로 가지고 있는게 다루기 편하다

$$ QL(x)a(x)+ Q_R(x)b(x)+ Q_O(x)c{i}+QM(x)a_ib{i}+ Q_c(x)= 0$$

Copy Constraint

지금까지는 도릭접인, wire에 0을 넣으면 다 만족하는 쉬운 값에 대한 여러개의 불연속 방정식이었다.
-> copy constraint를 증명하는 equation을 추가해야한다.
ex) a(5) = c(11), c(10) = c(12)

-> coordinate pair accumulator 역할을 하는 poly p(x) 디자인해야함
: 두 개의 좌표 설정, 각 좌표가 특정 점들의 집할을 대표하도록 한다
좌표가 일정한 값을 가리키고, 이 값을 accumulate한다

A(x) : accumulator

랜덤 상수를 통해 다항식을 누적할 수 있다.
-> 특정 좌표에서 일관성을 유지하여, 한 좌표에서의 값이 다음 좌표에 영향을 주도록 해서 일관성 유지

좌표의 순서가 바뀌어도, 동일한 좌표 집합이라면 accumulator를 통해 같은 값을 갖도록 한다.

총 두개의 accumulaotr를 사용하여, 하나는 원래 좌표, 다른 하나는 permutation(변환)하여 동일한 결과를 반환하면 두 좌표 집합의 copy constraint를 만족한다고 증명

복수의 와이어 세트간 copy constraint증명
a,b,c 와이어를 위한 좌표 범위를 지정하고, 좌표를 모두 모아 최종적으로 같은 값을 반환하는지 비교 -> 동일하면, copy constraint 성립

Permutation Argument

=> plonk에서는 회로를 여러 게이트로 나누는데, 입출력이 연결되어야 한다.
그래서 입출력이 연결되어야 하는 곳에서 copy constraint가 같음을 증명할 필요가 있다.
이를 위해 plonk에서는 permutation argument를 사용한다
(특정 변수들이 같은 값을 가지도록 매핑, 각 변수의 위치를 swap해도 값이 안 변하는지 확인(이것을 accumulator를 통해 확인))

회로 내 모든 게이트가 연결되고, 중간 변수들이 연산을 통해서 값이 바뀌어도 게이트간 일관성을 보장, 신뢰성, 무결성을 보장한다.

위 연산들은 정수가 아닌 소수 필드에서 일어나므로 FFT를 이용하여 w^n=1, w, w^2, .... w^(n-1) high-order root of unity 의 power를 사용한다.

정수에 비해 coordinator가 o ..n-1, 2n-1에서 w^i, g w^1, g^2 w^2 으로 바뀌기만 할 뿐이다

정리하자면

user-provided polynomial

• the wire assignments a(x), b(x), c(x)
• the coordinate accumulators $P_a(x)$, $P_b(x)$, $P_c(x)$, $P_a'(x)$, $P_b'(x)$, $P_c'(x)$
• the quotient H(x), H_1(x), ... H_6(x)

program - specific polynomials(prover, verifier가 먼저 연산해야함)

• represents the gates in the circuit $Q_L(x)$, $Q_R(x)$, $Q_O(x)$, $Q_m(x)$, $Q_c(x)$
• permutation polynomials(copy constraints) $sigma_a(x)$, $sigma_b(x)$, $sigma_c(x)$

verifier는 poly만 저장하면 된다
그러면 남은 하나의 polynomial은 Z(x) = (x-1)(x-w)...(x-w^(n-1)) -> 모든 포인트에서 0인지 검사

최적화

copy constraint와 계산 효울성 문제
1. 주기적인 문제와 constraint
특정 copy constraint가 주기적인 구조로 인해서 모든 좌표에서 성립할 수 없다.
ex) w에서 거듭제곱을 통해 원의 각 점에서 값을 정의하는데 마지막 죽의 좌표에서 다음으로 넘어가면 w^n = 1이 되어 다시 시작점으로 돌아온다. 여기에서 w^(n-1)과 1 사잉에서 원활한 연결이 되지 않아, x=w^(n-1)에서의 조항을 더해서 constraint를 강제로 만족하게 한다.
2. v1과 v2 역할 및 제약
프로토콜에서 결정되어 사용자가 후에 a(x), b(x), c(x)를 선택할 수 없도록 제한함
3. 회로 만족 조건을 단순한 다항식 문제로 변환
plonk가 복잡한 프로그램 만족 모델을 단순한 다항식 문제로 변환

그러면 어떻게 짧은 proof를 만드나? -> polynomial commitment

Polynomial commitment

비밀값s를 사용해서 G, GS, GS^2 ... 같은 점을 생성한다.
이 값들이 커밋먼ㅌ를 만드는데 필요한 정명키가 된다
s는 잃어버리고 나머지는 공개

-> 각각의 값을 poly의 coefficient와 곱해서 더하면 commitment

검증 : subtract-and-divide

x=r에서의 다항식을 검증하는 방법
$(f(x)-y) / (x- r)$
이 시기이 타원곡선의 페어링을 사용하여 검증된다.

Recap

1. circuit을 set of equations로 convert
2. 그것을 하나의 poly로 convert
3. copy constraint로 부터 permuted wire indices를 나타내는 poly로 convert
4. 모든 와이어 값 계산, 세개의 poly로 변환
5. 순열 검증을 위해 여섯개의 coordinate pair accumulator poly 계산(복잡한 순열 단순화 & copy constraint 확인)
6. 순열 검증에 필요한 cofactor H_i(x) 계산 (copy constraint 확인하는 추가 정보, 각 다항식간 관계 집합)
7. 증명 생성 (commitment생성, 무작위 지점에서 open, 검증)
8. 최종 검증(commitment와 opening으로 각 회로의 제약 조건을 만족하는지 검증)