안녕하세요 SigmoiD입니다.
오늘은 zero knowledge를 사용한 익명 투표 시스템 (OV-net) 프로젝트를 분석해 보았습니다.
영지식 증명의 실 사용예를 분석함으로서 좀더 손쉽게 ZKP를 이해하는것이 저의 목적입니다.
OV-net 프로젝트: https://github.com/stonecoldpat/anonymousvoting

Open Vote Network(OV-net) Protocol

OV-net은 영 지식 증명을 활용하여 익명 투표를 가능케 한 탈중앙화된 투표 프로토콜로서, 다음의 4가지를 강조하고 있습니다.

모든 통신이 공개되어 있음
최종 계산은 시스템에서 하도록 한다.
투표자의 프라이버시를 최대화한다 (영지식증명이 두가지가 사용됩니다.)
- Schnorr non-interactive ZKP ( 투표자 암호화)
- 1 out of 2 ZKP (투표 내용 암호화)
모든 이가 투표의 모든 과정을 확인 가능하므로 결과에 대한 신뢰가 높다.

OV-net 프로토콜은 5단계를 거쳐 투표를 완료합니다.

1. SETUP

계약을 배포한 계정이 신규 투표를 생성합니다.
신규 투표 생성시 투표자 등록 기간, 투표 시작 시간, 투표 종료 시간등 각 단계에 대한 다양한 시간들을 설정할 수 있으며, 투표의 생성자는 참여할수 있는 투표자들의 주소를 white list에 등록하여야 합니다.

2. SIGNUP

투표에 참가하기 원하는 투표자들은 자신들이 투표에 사용할 공개키와 개인키를 각각 생성하고, 해당 개인키에 대한 영 지식 증명을 생성합니다.
이후, 투표 계약으로 공개키와 영 지식 증명을 전달하게 됩니다.
계약은 수신한 영 지식 증명을 검증 (전달된 공개키와 pair한지 검사)하고,
공개키를 계약의 저장소에 저장합니다.

3. COMMIT (OPTIONAL)

투표자는 투표 내용을 전달하기전, 투표의 해시값을 먼저 전달합니다.
투표 내용을 먼저 전달 한다면, 투표 중간에 현재까지의 투표결과를 확인할 수 있기 때문에, 투표의 해시를 먼저 보내어 몇 명이 투표했는지만 확인 가능하도록 합니다. 투표의 해시가 전달 되었기 때문에 다음에 전달할 투표내용은 바뀔수가 없습니다.

4. VOTE

공개키와 투표 내용을 나타내는(1인지 0인지) 영 지식 증명을 전달합니다.
계약은 영 지식 증명을 검증하고, 계약의 저장소에 공개키와 증명을 저장합니다.

5. TALLY

모든 투표가 완료되면, 최종 결과를 계산합니다.
투표로 전달된 증명을 모두 더한 값을 타원 곡선상에서 찾아 최종 투표 결과를 확인합니다.

Test Setup & Run

테스트를 실행하기 위해서는 ethereum node가 필요합니다.
저는 Private net상에서 테스트를 진행하였습니다.
(difficulty, block gas limit등을 수정하여 편하게 사용하고 있습니다.)

geth실행시 rpcport는 8545로 하면, remix와 html파일에서 별다른 설정없이 접근이 가능하기 때문에, 이왕이면 8545로 사용하세요

admin, voter1, voter2, voter3의 계정 4개를 만들고 적당히 이더를 배분합니다.
(투표를 하기 위해서 1 ether를 deposit해야합니다. 투표가 끝난후 refund됩니다.)

personal.newAccount("admin")
personal.newAccount("voter1")
personal.newAccount("voter2")
personal.newAccount("voter3")
web3.eth.defaultAccount = eth.accounts[0]
miner.start()

miner.stop()
web3.personal.unlockAccount(eth.accounts[0], "admin", 0)
web3.personal.unlockAccount(eth.accounts[1], "voter1", 0)
web3.personal.unlockAccount(eth.accounts[2], "voter2", 0)
web3.personal.unlockAccount(eth.accounts[3], "voter3", 0)


eth.getBalance(eth.accounts[0])
eth.sendTransaction({from:eth.accounts[0], to:eth.accounts[1], value: web3.toWei(2,"ether"), gas:21000})
eth.sendTransaction({from:eth.accounts[0], to:eth.accounts[2], value: web3.toWei(2,"ether"), gas:21000})
eth.sendTransaction({from:eth.accounts[0], to:eth.accounts[3], value: web3.toWei(2,"ether"), gas:21000})
miner.start()

miner.stop()

eth.getBalance(eth.accounts[0])
eth.getBalance(eth.accounts[1])
eth.getBalance(eth.accounts[2])
eth.getBalance(eth.accounts[3])

계약의 배포는 remix상에서 진행하였습니다. (컴파일러 버전 꼭 확인해주세요 저는 4.10 latest를 사용하였습니다.)

계약 배포시 AnonymousVoting.sol 파일의 코드 크기가 너무 커서 geth에 배포할수 없었습니다(EIP-170). geth code를 수정하여 크기를 늘려서 사용하였습니다.
(수정을 해도 리믹스에선 경고가 뜹니다. 무시하고 진행하시면 됩니다)

+++ b/params/protocol_params.go
@@ -62,7 +62,8 @@ const (
        MemoryGas        uint64 = 3     // Times the address of the (highest referenced byte in memory + 1). NOTE: referencing happens on read, write and in instructions such as RETURN and CALL.
        TxDataNonZeroGas uint64 = 68    // Per byte of data attached to a transaction that is not equal to zero. NOTE: Not payable on data of calls between transactions.
 
-       MaxCodeSize = 24576 // Maximum bytecode to permit for a contract
+       //MaxCodeSize = 24576 // Maximum bytecode to permit for a contract
+       MaxCodeSize = 24576*2 // Maximum bytecode to permit for a contract

AnonymousVoting 배포시, gap과 charity를 설정하게 되는데
charity는 기부할 주소이고, gap은 투표 단계별 시간입니다.
gap이 중요한데 저는 15분씩으로 했습니다(그림처럼 너무 작은숫자를 넣으면 투표를 진행하기가 어렵습니다. 900초로 수정해서 재배포 했습니다.)

배포가 끝나면 Web3/*.html파일의 contract address를 모두 수정해주세요

-var anonymousvotingAddr = anonymousvoting.at("0xa0a856ee329e7dd03891c3dc337b8178be397320");
+var anonymousvotingAddr = anonymousvoting.at("0xfCA955FBaCb4c1ae42D48A4d651A9BD65F4cCd4c")
 
-var cryptoAddr = crypto_contract.at("0x4537d53c60729171c708168d64b560e1658124d0");
+var cryptoAddr = crypto_contract.at("0x6624ff9344c1a37ed7a1127b190dc27826c8a8f9");

참고로 투표의 모든 과정은 livefeed.html을 통해 확인 하실 수 있습니다.

1. Setup

admin 페이지를 통해 계약을 생성합니다.
계약을 생성할 때 노드의 계정을 조회(eth.accounts)해서 화이트리스트(setEligible)에 등록합니다. finishEligible을 호출하여 등록을 끝내고
투표에 대한 몇 가지 설정(시간, 투표 질문, commitment 진행 여부)을 진행한 후, beginRegistration() 호출하여 signUp 단계로 진입하게 됩니다..

livefeed

2. SignUp

투표에 참석하기 위해서는 먼저 투표에 사용할 vote code를 생성해야 합니다.
친절하게 votingcodes.jar파일을 실행해서 얻을수 있습니다.

java -jar votingcodes.jar
>> voter.txt

vote code는 투표에 사용될 공개/개인키 셋을 생성한 후,
영 지식 증명 생성 및 검증에 사용될 정보인 x, _x, _y, v, w, r, d를 미리 만들어 저장해둔 것입니다. (이 값은 html에서 사용하기 위해 만들 뿐, 별 내용은 없습니다)

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로 나누어짐)

vote code 생성 후, vote 페이지를 열고 voter.txt 파일을 선택하여 html에서 사용할 변수들을 초기화 합니다. 이후 whitelist에 등록된 주소를 선택할 수 있는 창이 생기면, 원하는 주소를 선택하여 un-lock후, register를 시작하게 됩니다.

2-a. CreateZKP (Local)

먼저, vote code에서 읽은 값들을 이용하여 ZKP를 생성합니다.
createZKP (x, v, xG) return result

xG 유효성 확인: curve위에 있는지 확인, 고정된 필드사이즈 값(pp) 사용
GeneratorG의 basepoint Gx(uint),Gy(uint)를 설정한 후, g^v을 구하기 위해
v와 G를 곱하여 vG(uint[3])에 넣는다.
ECCMath 이용하여 vG를 Z1좌표로 변환 (zacobian, x,y,z -> x', y' ,1)
해시값 c를 생성한다. 보낸사람주소, 타원곡선의 기준점 2개, 공개키, vG)
c = sha256(sender address, Gx, Gy, xG, vG)
xc = mulmod(x,c,nn) 해시값에 개인키를 곱하고 개인키의 크기로 modulo한다
r = submod(v,xc); v-xc를 뺀후 개인키의 크기로 modulo한다
result = {r, vG[0], vG[1], vG[2]}
계산이 끝나면, 투표참여자는 계약의 register(xG, vG, r)를 호출하여 자신의 공개키와 영지식을 등록합니다. (내부적으로 verifyZKP 함수가 호출됩니다.)

2-b. Register (Remote)

verifyZKP(xG, r, vG) return true/false

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

투표 공개키와, 영지식증명(vG, r)만으로 검증이 끝났습니다.
zkp가 검증되었다는 의미는 영 지식 증명 제출자가 해당 public key에 대한 private key를 가지고 있다는 것을 의미합니다. 그러므로 해당 투표자를 등록리스트에 추가합니다.

2-c. Register finish (admin)

등록기간이 종료되면, admin은 commitment단계로 이동하기 위해 register finish를 호출합니다. 해당 함수에서는 투표자가 제공한 공개키와 해당 공개키를 활용해
reconstructedkey를 계산해 계약에 저장해 둡니다(yG)

3. Commitment

vote페이지에서 등록이 끝나면 질문내용과 함께 yes/no를 선택하는 화면이 나옵니다. 그중 하나를 선택하면..

getVoter 함수를 이용하여 계약으로부터 xG, yG를 얻는다.
xG: registered key
yG: reconstructedkey
zkp생성
create1outof2ZKPYesVote(xG, yG, w,r,d,x) return result
create1outof2ZKPNoVote(xG, yG, w,r,d,x) return result
cryptoAddr.commitToVote 함수를 이용하여 투표 해시를 계산합니다.
submitCommitment 함수를 통해 계정으로 해시를 전달합니다.
h1 = sha3(address, params, xG, yG, a1, b1, a2, b2)
params, y, a1, b1, a2, b2 from result

create1outof2ZKPYesVote(r1, d1)	create1outof2ZKPNoVote(r2, d2)
y = h^{x} * g	y = h^{x} * g
a1 = g^{r1} * x^{d1}	a1 = g^{w}
b1 = h^{r1} * y^{d1}	b1 = h^{w}
a2 = g^{w}	a2 = g^{r2} * x^{d2}
b2 = h^{w}	b2 = calculated
c = H(id, xG, Y, a1, b1, a2, b2), id is H(round, voter_index, voter_addr, contract_address)	c = H(voter_addr, xG, Y, a1, b1, a2, b2)
d2 = c - d1 mod q	d1 = c - d2 mod q
r2 = w - (x * d2)	r1 = w - (x * d1)

스크린샷, 2019-02-08 16-36-55.png
2개는 yes, 1개는 no를 선택하였습니다.

4. Vote

해시를 전송한후 submitVote(params, y, a1, b1, a2, b2)함수를 이용하여 최종 투표를 진행합니다.

수신한 정보를 바탕으로 해시를 계산합니다.
h2 = sha3(address, params, xG, y, a1, b1, a2, b2)
이전에 수신한h1와 계산한 h2가 같다면, zkp를 verify합니다.
verify1outof2ZKP(params, y, a1, b1, a2, b2)가 참이라면, 계약의 저장소에 다음과 같이 저장합니다.

voters[address_id].vote[0] = y[0];
voters[address_id].vote[1] = y[1];

<캡쳐를 못했네요.. 선택한 결과를 보낼껀지 묻는 창이 나옵니다 - casting>

5. Tally

투표가 끝나고 나면, admin은 computeTally함수를 호출하여 계약이 최종결과를 계산하도록 합니다.

계산방식은 저장된 vote를 누적해서 더하고(Secp256k1._addMixedM)
해당 결과와 매칭되는 커브상의 값을 찾아 총 투표수와 yes count를 얻게됩니다.

for(i=1; i<=totalregistered; i++) {
       if(temp[0] == tempG[0]) {
           finaltally[0] = i;
           finaltally[1] = totalregistered;

var yes = anonymousvotingAddr.finaltally(0);^M
var total = anonymousvotingAddr.finaltally(1);^M
var no = total - yes;

스크린샷, 2019-02-08 16-53-14.png

이렇게 투표가 종료되었습니다.

각각의 영 지식 증명의 계산을 어떻게 하는지를 아는 것은 당연히 중요하지만,
무엇을 영지식으로 처리하고 싶은지, 또 라이브러리를 이용하여 어떤 값을 암호화 할 수 있는지 파악하는 것도
개발자에게 중요하지 않을까라는 생각을 해봅니다.

블록체인 스터디 하시는데 도움이 되셨으면 좋겠습니다.

익명 투표 시스템 (OV-net) 분석 공유