Zero Knowledge Proof - ZK SNARK
reference : https://arxiv.org/pdf/1906.07221.pdf
Polynomial
Polynomial Basic
$c_nx^n + ... + c_1x^1 + c_0x^0$
polynomial이 있을때 prover가 자신이 특정 polynomial(d degree)를 들고 있다는 것을 증명하려면, d+1개의 점을 verifier가 check하면 충분하다.
- 최대 d개의 점만 일치하고 다르던가 아예 똑같거나 ("d차 polynomial = d차 polynomial" 해의 개수 < d)
Basic Claim
$p(x) = t(x)h(x)$
t : target polynomial, prover claim : “I know polynomial with degree d with $t(x)$
- verifier가 sample value s 를 생성, $t=t(s)$ 를 계산함
- verifier는 s를 prover에게 전달함.
- prover가 받은 s로 $p=p(s)$과 $h=h(s)$을 계산해서 다시 verifier에게 넘겨줌
- verifier는 t랑 받은 h를 곱해서 받은 p가 나오는지 확인하면 됨
Problem
- $p(x)$ 를 몰라도(즉, $h(x)$ 도 모름) $t=t(s)$ 랑 random $a$ 를 곱해서 $a$ 랑 $ta$를 주면 됨 (s을 결국 verifier가 알려주니까 t값을 암)
- degree가 정해져 있음. prover는 higher degree polynomial로 거짓말을 칠 수 있다.
→ s를 안알려 주고 verify를 할 수 있을까?