영지식 증명으로 이더리움 블록체인 에서 스도쿠(sudoku) 퍼즐을 풀어보자
안녕하세요 철학자(정순형)입니다.
이더리움의 커뮤니티 파워는 이더리움을 측면 지원하는 다양한 라이브러리와 개발 툴킷에서 시작됩니다. 이번 글에서는 강력한 영지식 도구인 zokrates를 이용해서 이더리움 블록체인 위에서 스도쿠 퍼즐을 풀어보도록 하겠습니다. 매우 쉬운 예제이기 때문에, 영지식 증명의 구현 및 응용에 관한 튜토리얼로도 활용하시면 좋을 것 같습니다.
프로그래밍이 익숙하지 않은 분들께서는 <(1)스도쿠 퍼즐과 포맷 정의 >, <(2)증명자와 검증자 그리고 영지식> 부분만 읽으셔도 무방합니다.
(1) 스도쿠 퍼즐과 포맷 정의
가장 많이 알려진 기본적인 형태의 스도쿠(数独)는 가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 채워 넣는 숫자 퍼즐입니다. 스도쿠 퍼즐의 같은 줄에는 1에서 9까지의 숫자를 한 번만 넣고, 3x3칸의 작은 격자 또한 1에서 9까지의 숫자가 겹치지 않게 들어가야 합니다.
9x9스도쿠 이외에도 다양한 형태의 스도쿠가 있고, 이 글에서는 로직의 단순함을 위해 9x9스도쿠가 아닌 4x4 크기의 미니 수도쿠를 사용하도록 하겠습니다. 규칙은 동일합니다.
- 넷 2x2 칸에 숫자가 1부터 4까지 하나씩만 들어가야 한다.
- 넷 가로줄에 숫자가 1부터 4까지 하나씩만 들어가야 한다.
- 넷 세로줄에 숫자가 1부터 4까지 하나씩만 들어가야 한다.
4*4스도쿠의 각 구역에 식별자를 부여한 형태는 다음과 같습니다.
여기서 분홍색으로 표시된 구역은 공개된 숫자입니다(a22, b11, b22, c11, c22, d21). 즉 문제죠. 예를 들어 다음과 같습니다.
문제를 푸는 사람(solver)는 해당 빈칸에 숫자를 채워넣어 스도쿠 퍼즐을 완성해야 합니다. 중요한 점은 내가 “답을 보여주지 않고, 문제를 풀었음을 증명(proof)"해야 합니다. 영지식(zero-knowledge)이죠.
그럼 블록체인에서 문제는 푸는 사람은 누구이고, 문제가 맞았음을 증명해주는 사람은 누구일까요?
(2) 증명자(prover)와 검증자(verifier) 그리고 영지식
증명자(prover), 검증자(verifier)라는 용어는 매우 익숙해질 필요가 있습니다. 증명자는 본인이 문제를 풀었음을 증명하는 사람이고, 검증자는 이렇게 풀린 문제가 맞았음을 확인해주는 사람입니다.
여기서 검증자는 꼭 사람일 필요는 없습니다. 컴퓨터가 이를 확인해주는 것도 가능하죠. 특히 블록체인 컴퓨터인 이더리움의 스마트 컨트랙트가 검증자의 역할을 수행하는 것도 가능합니다.
문제를 검증(verify)하기 위해 제일 쉬운 방법은 내가 풀어낸 답 자체를 블록체인에 제출(기록)하는 겁니다. 그런데 만약 내 답을 다른 사람에게 보여주지 않고, 내가 맞았음을 확인받고자 한다면 어떻게 할까요? 이때 영지식 증명이 사용됩니다. 영지식 증명의 마법은 문제의 종류와 상관없이, 단 다섯개의 숫자만 알려주면 내가 문제를 정확하게 풀었는지 아닌지를 판정해주죠.
중요한 점은 영지식 증거(Proof)를 통해서 내가 가지고 있는 해답을 전혀 유추할 수 없다는 겁니다. 스도쿠를 풀었다는 증거는 블록체인에 다음과 같은 값만 기록되죠.
[179426333, 181327921, 198492781, 533001793, 334216237]
위의 값을 통해 해답을 유추하는것은 불가능합니다.
zokrates는 이더리움 블록체인에 i)검증자(verifier)역할을 하는 컨트랙트와 ii)풀이에 대한 증거를 만들어주는 도구입니다. 스도쿠와 같은 다양한 문제를 정의하기 위해 zokrates 랭귀지라는 자체적인 프로그래밍 언어를 갖추고 있습니다.
이제 앞에서 정의한 4x4 스도쿠를 zokrates랭귀지를 통해서 정의해보도록 하겠습니다.
(3) 4x4 스도쿠 zokrates로 정의하기
코드를 바로 보는게 제일 좋습니다.
스도쿠 코드는 3개의 함수로 구성되어 있습니다.
- checkEquality( )
- validateInput( )
- main( )
line11::checkEquality()함수는 인풋변수 4개가 다르면 0을, 그렇지 않으면 0이 아닌 값을 리턴합니다.
line21::validityInput() 함수는 인풋값이 1~4범위 내에 있으면 0을 리턴하고 그렇지 않으면 다른 값을 리턴합니다.
line25::main()함수는 6개의 공개 변수(a22, b11, b22, c11, c22, d21)와 10개의 프라이빗 변수로 이루어져 있고, 스도쿠 퍼즐이 해결되었다면 1을 리턴하고 그렇지 않으면 assert(오류)를 냅니다.
line27–46::메인 함수로 들어온 16개의 값들에 대해서 1~4범위 내에 있는지 확인합니다.
line52–56:: 각 존(a,b,c,d)에 있는 값들이 모두 다른값인지 확인합니다
line58–63:: 각 행이 모두 다른 값인지 확인합니다
line65–70:: 각 열이 모두 다른 값인지 확인합니다
(4) 테스트
Requirement : Docker, Truffle, Ganachi-cli
로컬 환경에 도커, 트러플, 가니쉬를 이용해 테스트를 할 수 있습니다.
zokrates 도커 컨테이너 생성 및 셋업
$ docker run — name zokrates -v $(pwd)/zk-related:/home/zokrates/zk-related -ti zokrates/zokrates:latest /bin/bash$ cp ./examples/sudokuchecker.code zk-related/ && cd /home/zokrates/zk-related$ ../zokrates compile -i sudokuchecker.code #out, out.code생성$ ../zokrates setup — proving-scheme pghr13 #vefirication.key, prooving.key생성$ ../zokrates compute-witness -a 3 3 1 2 4 2 4 1 2 2 4 3 1 1 4 3 #witness파일 생성$ ../zokrates generate-proof --proving-scheme pghr13 #proof.json파일 생성## **proof.json파일의 input 값들 모두 스트링으로 바꾸기## 스마트 컨트랙트 생성$ ../zokrates export-verifier --proving-scheme pghr13 #verifier.sol파일 생성$ cd .. #상위 디렉토리로 이동
Truffle Setting
$ ganachil-cli # 별도의 터미널에서 작업$ truffle init && cp zk-related/verifier.sol contracts/## 트러플 네트워크에 다음 값 설정, truffle-config.js 파일## development: {## host: "127.0.0.1", // Localhost (default: none)## port: 8545, // Standard Ethereum port (default: none)## network_id: "*", // Any network (default: none)## }
## migrations디렉토리에 다음 2_deploy_contract.js파일 생성## 2_deploy_contract.js 파일에 아래의 내용 내용 입력
var verifier = artifacts.require("./verifier.sol");module.exports = function(deployer) {deployer.deploy(verifier);};
## 테스트 파일 작성## test디렉토리에 다음 파일 verifyTxTest.js 생성
테스트파일(Truffle)
const verifier = artifacts.require("verifier");const fs = require('fs');const BN = require('bn.js');//TODO : Delete All 00...0 in proof.input and convert to String and add "0x"contract('verifier', function(accounts) {it('verifyTx', async function() {//Read Prooflet proofJson = fs.readFileSync('./zk-related/proof.json', 'utf8');proofJson = JSON.parse(proofJson);console.log(proofJson)const proof = proofJson.proof;const input = proofJson.input;const _proof = [];Object.keys(proof).forEach(key => _proof.push(proof[key]));_proof.push(input)let instance = await verifier.deployed();console.log('calling verifyTx with proof', _proof);const success = await instance.verifyTx(..._proof);assert(success);console.log("success", success);})})
(5) 한계 및 응용분야
연산 부담 : 레이어2 솔루션의 필요성
영지식은 4x4 규모의 간단한 스도쿠 서킷임에도 불구하고 검증과정에서 이더리움 체인 상에 190만 가스를 소모(gas used)했습니다(일부러 잘못된 증거(proof)를 검증하는 테스트 때에는 600만이 넘는 가스를 사용했습니다). 이더리움 메인체인의 블록 가스 한계가 800만임을 감안하면, 실행은 가능하지만 원활하지는 않습니다.
그렇기때문에 영지식증명을 이더리움 퍼블릭 블록체인에서 활용하기 위해서는 (1)연산의 신뢰를 잃지 않으면서도, (2)이더리움 메인체인과 상호호환성을 유지하고, (3)튜링 완전성을 지원하는 레이어2솔루션이 필요합니다.
특히나 레이어2 솔루션 중에서도 플라즈마(Plasma) 계통에 속하는 기술은 데이터의 안정성(Security)이 부모체인인 이더리움에 의해 확보하면서도(그렇기 때문에 별도의 합의 알고리즘이 필요 없고), 부모체인과 강력한 상호 호환성을 확보하고 있으며, 구현에 따라 완전한 튜링 완전함을 특징으로 하기 때문에 영지식을 활용하기에 유리합니다.
초기 셋업 : MPC(Multi Party Computation) 혹은 Stark 필요
Zokrates는 SNARK를 기반으로 만들어졌기때문에, 초기 서킷의 검증키와 증명키를 만드는 과정에서 Toxic Waste라고 불리는 랜덤값이 만들어져 사용됩니다. 중요한점은 이 값들은 영영 사라져야 한다는 점 입니다(심지어 이걸 만든 사람조차 그 존재를 몰라야 합니다).
따라서 Toxic Waste가 만들어지는 과정에 필요한 Trusted Third Party를 분산시키기 위해 MPC(Multi Party Computation)이 활용될 수 있습니다. 대표적으로 Snark기반의 프라이버시 코인을 만드는 z-cash팀은 MPC를 적극적으로 활용해 이 세레모니를 수행했습니다.
대안으로 STARK와 같은 다른 영지식 알고리즘을 사용하는 것도 가능하지만, SNARK의 증명 시간이 연산의 종류와 관계없이 일정하다는 강력한 장점은 SNARK를 포기하지 못하게 만듭니다.
활용분야
더불어 이러한 영지식은 “프라이버시를 보장하는 트랜잭션”을 만들어 냄으로써, 마이너 혹은 주변 네트워크 참여자가 데이터 내용 자체를 알 수 없으면서도 데이터의 안정성은 유지되는 다양한 분야에 활용될 수 있습니다.
예를들어 토큰 전송 과정에서 토큰의 전송 내역을 숨기면서도 토큰을 안정적으로 보내거나, 신분증명(KYC) 등의 과정에서 해당 과정에 참여하는 사람 누구도 일체의 신원을 전혀 드러내지 않고 본인의 신분을 증명하는 과정 등에서 활용 가능합니다. 또한 개인정보를 드러내지 않고, 개인정보를 거래할 수도 있습니다. 다만, 이러한 과정들을 수행하기 위해서 정교한 서킷 설계가 필요합니다.
(6) 레이어2(토카막 네트워크) 배포 테스트
(추후 내용이 업데이트될 예정입니다)
스도쿠는 영지식증명을 이해하는 가장 직관적이고 단순한 예제임과 동시에 실제로 구현되어 동작 가능하기 때문에 영지식의 특징과 기능을 이해하는데 많은 도움이 되리라 생각합니다. 이 글을 통해서 많은 개발자분들께서 영지식을 활용한 참신한 탈중앙화 어플리케이션이 만들어질 수 있는 환경을 제공하는 계기가 되기를 바라며 글을 마칩니다.
감사합니다.
This post is powered by Tokamak Network.
