Sumcheck protocol

수학 공부를 하면서 느끼는 거지만 수학은 항상 영어로 되어있어서 이해하기 더 힘든 것 같다..

 

그래서 이번에 힘들게 공부한 sumcheck protocol을 한국어 설명으로 남겨보려고 한다

---

먼저 sumcheck protocol을 이해하기 위해선 Schwartz-Zippel의 lemma를 알아야 한다.

 

Lemma. P ∈ F는 총 차수가 d이고 0이 아닌 다항식이라고 하자. 그럼 P가 0이 되는 해는 d개 이하임

https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma

Schwartz–Zippel lemma - Wikipedia

을 참고하면 되는데 단순하게 말하면 P에 랜덤요소를 대입해서 P가 0이 될 확률은 d/|S|라는 것임

검정색 바둑알 3개랑 흰색 바둑알 2개 중에서 흰색을 뽑을 확률이 2/5인 것과 같은데 |S|개에서 P가 0이 되는 해는 d개 이기 때문에 확률이 d/|S|가 된다는 것임

 

즉 이 lemma는 두 개의 다른 다항식은 아주 작은 확률로 일치할 수 있다는 것을 암시하고 뒤에 보일 soundness에서 쓰임

 

Sumcheck protocol's object

를 계산하는 것임

 

직관적으로 이걸 계산하려면 얼마의 computation이 필요할까? 생각해보면 2^v가 걸릴 것인데 이건 검증자가 허용할 수 없는 큰 runtime임  -> sumcheck protocol을 사용해서 runtime을 줄이는 것이 목표가 됨

 

이 계산을 verifier가 아닌 powerful한 device를 가지고 있는 prover에게 대신 시키는 것이 바로 sumcheck protocol임

 

verifier의 목표: sum을 계산하는 것/prover가 보낸 값을 신뢰하는 것

prover의 목표: 자기가 계산한 sum을 verifier에게 검증하는 것

 

1. Prover는 연산한 값을 verifier에게 보냄 (=y)

 

2. Prover는 f(x1,x2,...,xv)에서 x1만을 변수로 남기고 다른 변수들은 실제 0/1을 대입한 f_1(x1)식을 verifier에게 보냄

 

3. verifier는 먼저 f_1의 차수가 처음 정의된 함수에서의 각 변수들의 차수를 넘어가지 않는 것을 확인하고, prover가 보낸 식 f_1에 가능한 값을 대입해 처음 prover가 주장한 y값과 같은지 check함

 

4. 문제가 없다면 field에서 랜덤 값 r1을 뽑아 prover에게 보냄

 

5. prover는 x1자리를 r1으로 대체하고 x2 변수를 남기고 x3~xv까지 0/1을 대입한 f_2(x2)식을 verifier에게 보냄

 

6. verifier는 3번과 동일하게 f_2의 차수를 확인하고, f_1(r1) = f_2(x)인지 check함

 

7. 문제가 없다면 또 랜덤 값 r2를 뽑아 prover에게 보냄

 

2~7번의 과정이 반복됨

 

last round(v번째). f_v(x)의 차수 확인/f_v(x) = f_v-1(rv-1)인지 check -> 맞다면 처음 식 f에 여태까지 보낸 모든 랜덤 값(r1~rv)을 대입한 f(r1,...,rv) = f_v(rv)인지 check -> 맞다면 accept, 아니면 reject함

 

Completeness: 만족함(크게 설명은 x)

 

Soundness: vd/|F|가 됨

설명: dihonest한 prover가 중간에 원래 식 f(x)에서 파생된 식(=f_i(xi))이 아닌 다른 다항식 f'_i(xi) 썼다고 가정하자.

그때 verifier가 뽑은 랜덤 값 ri에 대해서 f_i(ri) = f'_i(ri)가 된다는 말이기 때문에 이 말은 즉 f_i(xi) = f'_i(xi)일 확률과 같고 앞서 본  Schwartz-Zippel lemma에 의해 d/|F|가 된다.

-> 다항식을 v round까지 쪼갤 수 있기 때문에 vd/|F|가 됨(이 부분은 식을 보면 바로 이해가 됨)

 

Complexity

P: O(d*2^v)

V: O(vd)(=각 라운드에서 받은 polynomial과 이전 라운드에서 받은 polynomial을 이용해 검증할 때 그 degree에 비례하는 정도의 대입연산 필요) + O(f)(=마지막에서 평가하는 데 드는 비용) 

communication: O(vd)

 

verifier의 연산량이 exponential에서 크게 준 것을 확인할 수 있다.

 

---

sumcheck protocol은 아주아주 중요하고 후의 GKR에서도 필요한 내용이기 때문에 잘 숙지하고 있어야 함!