전에 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를 통해 아무것도 배울수 없다는 의미이다.