Schnorr non-interactive ZKP

전에 OV-net분석할때(https://steemit.com/ethereum/@sigmoid/ov-net)
나왔던 기법인데, 요즘 비트코인 쪽에서 조금 관심을 받는가 보다.

기본 알고리즘의 구현은 다음과 같은데,
나중에 논문이랑 비교해가며 보강할 필요가 있겠다.
https://tools.ietf.org/html/rfc8235

Schnorr non-interactive ZKP

x: 개인키
xG(_x,_y): 공개키
v: random nonce for zkp, [0, q-1]
w: random nonce for 1outof2 zkp
r, d: 1 or 2, random nonce for 1outof2 zkp
(p, q: 큰 소수인 q 와 p를 가정하고 q는 p-1로 나누어짐)

createZKP (x, v, xG) return result
    1. xG 유효성 확인: curve위에 있는지 확인, 고정된 필드사이즈 값(pp) 사용
    2. GeneratorG의 basepoint Gx(uint),Gy(uint)를 설정한 후, g^v을 구하기 위해
    v와 G를 곱하여 vG(uint[3])에 넣는다.
    3. ECCMath 이용하여 vG를 Z1좌표로 변환 (zacobian, x,y,z -> x', y' ,1)
    4. 해시값 c를 생성한다. 보낸사람주소, 타원곡선의 기준점 2개, 공개키, vG)
    c = sha256(sender address, Gx, Gy, xG, vG)
    5. xc = mulmod(x,c,nn) 해시값에 개인키를 곱하고 개인키의 크기로 modulo한다
    6. r = submod(v,xc); v-xc를 뺀후 개인키의 크기로 modulo한다
    result = {r, vG[0], vG[1], vG[2]}

계산이 끝나면, 투표참여자는 계약의 register(xG, vG, r)를 호출하여
자신의 공개키와 영지식을 등록합니다.

verifyZKP(xG, r, vG) return true/false
    1. GeneratorG의 basepoint Gx(uint),Gy(uint)를 설정한후, xG와 vG가 모두 유효한 퍼블릭 키인지 확인
    2. 해시값을 하나 생성한다
    c = sha256(sender address, Gx, Gy, xG, vG)
    3. rG = r * G
    4. xcG = c * xG
    5. rGxcG = rg + xcG
    6. ECCMath를 이용, rGxcG를 Z1으로 (zacobian, x,y,z -> x', y' ,1)
    rGxcG[0,1] == vG[0,1] 이면 참이다.

이게 무슨 의미냐면,
어떤 Public key에 대한 private key를 안다는 것을 증명하기 위해,
public key와 zkproof 만을 전송하여 증명이 가능하며,
수신자는 zkproof를 통해 아무것도 배울수 없다는 의미이다.