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)$

1. verifier가 sample value s 를 생성, $t=t(s)$ 를 계산함
2. verifier는 s를 prover에게 전달함.
3. prover가 받은 s로 $p=p(s)$과 $h=h(s)$을 계산해서 다시 verifier에게 넘겨줌
4. verifier는 t랑 받은 h를 곱해서 받은 p가 나오는지 확인하면 됨

Problem

1. $p(x)$ 를 몰라도(즉, $h(x)$ 도 모름)  $t=t(s)$ 랑 random $a$ 를 곱해서 $a$ 랑 $ta$를 주면 됨 (s을 결국 verifier가 알려주니까 t값을 암)
2. degree가 정해져 있음. prover는 higher degree polynomial로 거짓말을 칠 수 있다.

→ s를 안알려 주고 verify를 할 수 있을까?