블록체인에서의 개인정보보호 기술, zk-SNARK (1)

Seonghwa Yun
Oct 8, 2018 · 7 min read

안녕하세요. AIN Team의 Software Developer 윤성화 입니다.

AI Network는 블록체인을 통해 전 세계의 AI 연구자들이 그들의 모델과 데이터, 그리고 컴퓨팅 파워를 서로 공유하며 효율적으로 활용하고, 그에 따른 적절한 비용과 보상을 제공하는 플랫폼을 만들고자 노력하고 있습니다. 이러한 환경에서 모델과 데이터 자체의 보안만큼, 플랫폼에서 활동하는 참여자들의 개인정보보호 역시도 중요한 요소로 작용합니다.

Zero-Knowledge Proof (ZKP, 영지식 증명)는 최근 블록체인 시스템에서의 개인정보보호 및 보안 강화 측면으로 활발하게 연구되고 있는 주제입니다. ZKP의 개념 자체는 1985년 Goldwasser, Micali, Rackoff의 논문 “The Knowledge Complexity of Interactive Proof Systems”[1]에서 처음 등장했으며, 그 내용을 간단히 요약해 보자면 다음과 같습니다:

“ZKP는 증명자(Prover)가 검증자(Verifier)에게 임의의 명제를 증명하고자 할때, ‘해당 명제의 참/거짓 여부’ 이외의 다른 정보를 노출하지 않는 증명 방식이다.

zk-SNARK는 “Zero-Knowledge Succinct Non-interactive ARgument of Knowledge”의 약자로, 기존의 ZKP를 좀 더 간결하고(Succinct) 비간섭적인 환경(Non-interactive)에서 적용 가능하도록 변형한 형태입니다. 이 개념은 2012년의 논문[2]에서 처음 제안되었으며, 그 특성들로 인해 블록체인 환경에서 ZKP를 구현할 수 있게 되었죠. zk-SNARK를 활용한 블록체인 트랜잭션의 경우, 수신자, 송신자, 전송 금액 등의 정보를 노출하지 않으면서 해당 트랜잭션의 유효성을 송수신 노드 외의 다른 노드들에게 알릴 수 있습니다. zk-SNARK를 최초로 적용한 사례로는 ZCash가 있으며, 이더리움의 비잔티움 하드포크에도 관련 내용이 적용되었습니다.

zk-SNARK는 크게 두가지 파트로 나눠지는데, 하나는 증명하고자 하는 문제를 특정 형태로 변환하는 과정이고, 다른 하나는 변환된 문제를 사용해서 실제 증명을 진행하는 과정입니다. 이 글에서는 간단한 예시를 통해 증명하고자 하는 문제를 zk-SNARK 적용을 위한 특정 형태로 변환하는 과정에 대해 설명합니다. 아래에서 사용할 예시는 ZCash 블로그 글[3]의 예시를 참고했습니다.


zk-SNARK를 위해서는 다음의 과정을 거쳐 어플리케이션의 validity function을 같은 의미를 지니는 다항식으로 표현해야 합니다:

Computation -> Arithmetic Circuit -> R1CS -> QAP

변환 과정의 가장 첫 단계는, validity function의 계산과정을 연산 회로(Arithmetic Circuit)로 표현하는 것인데, 연산 회로란 주어진 수식을 사칙연산 단위로 풀어서 쓴 형태이며, 논리 회로의 AND / OR 등의 논리 게이트들이 사칙연산 게이트로 변경된 형태입니다. 예를 들어, 수식 (a + b) * (b * c)는 다음과 같은 연산 회로로 표현됩니다:

[그림 1] (a + b) * (b * c)의 연산 회로

다음은 이렇게 사칙연산 게이트 단위로 표현된 연산 회로를 R1CS (Rank 1 Constraint System) 형태로 변환하는 과정입니다. R1CS 형태에서는, 연산 회로를 구성하는 각각의 게이트에 대해 주어진 입출력 값이 유효한지 확인할 수 있으며, 이 과정은 검증하고자 하는 해의 벡터 표현과 게이트에 대한 벡터 표현들의 연산으로 이루어집니다. 이러한, R1CS 표현방식의 경우 전체 수식에 대한 유효성을 검증하기 위해, 각각의 게이트 별 제약사항(constraint)의 유효성을 일일이 검사해야 하므로, 검증자의 입장에서 많은 검증 횟수를 필요로 한다는 단점이 있습니다. 위의 예시 회로에 대해서는 아래와 같이, 총 3개 게이트에 대한 유효성 체크를 완료해야 전체 수식의 유효성 체크가 완료됩니다.

[그림 2]

이러한 R1CS 형태의 단점을 극복하기 위해, 2012년의 한 논문[4]에서 제안된 QAP (Quadratic Arithmetic Program) 라는 개념이 도입됩니다. 위에서 언급한 각 게이트별 제약사항을 임의의 게이트 변수를 통해 하나의 다항식 형태로 표현하는 방법인데, 조금 더 자세히 얘기해 보자면 임의의 게이트 값을 변수에 대입하면 해당 게이트 값에 해당하는 게이트의 R1CS 형태가 나오는 다항식으로 표현됩니다. 위의 그림을 예로 들어 간단히 설명해 보자면, 게이트 변수를 각 게이트의 번호라고 했을 때, 임의의 QAP P(x)가 정의되었다면, 아래 그림처럼 P(1)은 GATE 1에 대한 유효성 검증 식이 나오며, P(2)는 GATE 2, 그리고 P(3)는 GATE 3에 대한 검증식이 나오는 형태의 다항식입니다.

[그림 3] QAP P(x)의 의미

QAP 형태의 또다른 특징은 제약의 유효성을 검증하는 과정에서 다항식 자체를 활용 가능하다는 점 입니다. 유효한 QAP P가 구성된 경우, 모든 게이트 변수가 해당 방정식의 해가 되어야 함을 알 수 있고, 이를 통해 목표 다항식 (target polynomials) T를 정의할 수 있으며, 이 두가지 다항식을 사용해서 PT로 나누어 떨어짐을 보이면 유효성 검증을 완료할 수 있습니다. 위의 예시 그림에서의 목표 다항식 T는 다음과 같은 형태를 가지게 됩니다: T(x) = (x — 1)(x — 2)(x — 3)

이렇게 다항식 형태로 문제가 변형된 후, 실제 증명 과정은 이 다항식의 비교로 이루어집니다. 두 다항식을 비교하는 작업은 ‘서로 다른 다항식은 거의 대부분의 점에서 다르다’라는 Schwartz-Zippel Lemma에 따라 임의의 점 s에 대해서 두개의 다항식이 같은 값을 가진다는 것을 보임으로써 (높은 확률로) 두 다항식이 같다는 것을 보일 수 있습니다, 그렇기 때문에, QAP 형태로 문제가 변형되면, 증명 과정에 있어서 문제 전체가 필요하지 않고 특정 포인트 s에 대입한 값만 비교하면 되기 때문에, 기존 증명과정에 비해 훨씬 간결해(succinct)지게 됩니다.


실제 zk-SNARK 어플리케이션들에서는 곱셈 게이트들에 대해서만 QAP를 구성한다든지, 실제 QAP 다항식 P는 L, R, O와 같은 세가지 다항식의 조합으로 이루어져 있다든지 하는 자세한 내용들이 있지만, 이 글에서는 다루지 않았으며, 관련해서는 ZCash의 글[5]을 참고하면 더 자세한 내용을 확인 가능합니다. QAP 변환 이후, 두 다항식을 비교하는 과정에서 영지식과 비간섭적 특성을 위해 Homomorphic Hidings이나 Pairings on Elliptic Curves 등의 기법을 사용하는데, 관련 내용은 다음 글에서 다룰 예정입니다.



카카오톡(한국): https://open.kakao.com/o/gEt7PtS

텔레그램(영어): https://t.me/ainetwork_en

공식 이메일: channel@ainetwork.ai

공식 홈페이지: http://ainetwork.ai/

페이스북: https://www.facebook.com/AINETWORK0/

AI Network_KR

AI를 위한 글로벌 컴퓨터 네트워크 구축

Seonghwa Yun

Written by

AI Network_KR

AI를 위한 글로벌 컴퓨터 네트워크 구축

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade