[영지식증명] Chapter 1. Security
ZKProof Community Reference. Ver 0.2. 한국어 번역.
1.1 Introduction
1.1.1 ) Zero-knowledge proof (ZKP) 란 무엇인가?
ZKP는 비밀정보의 기밀성을 유지하면서도 어떤 statement가 사실임을 증명할 수 있도록 하는 기술이다[GMR89]. ZKP는 어떤 statement의 사실여부는 그 자체로는 알 수 없지만 증명자가 이에 관련된 비밀 정보를 알고있을 때 (또는 super-computation ability와 같은 어떤 능력을 가지고 있을 때) 증명을 생성 할 수 있게 한다. 다음과 같이 다양한 용도로 ZKP를 사용할 수 있다.
- 생년월일을 직접 알려주지 않지만, 성인임을 인증한다.
- 계좌 정보를 모두 알려주지 않지만, 지불능력을 증명한다.
- 과거 거래기록을 공개하지 않지만, 자산의 소유여부 또는 명의를 증명한다.
- 체스 게임상의 모든 이동내역을 보여주지 않지만, 게임 결과의 정당성을 증명한다.
- 수학적인 증명을 보여주지 않지만, theorem의 진실여부를 인증한다.
이러한 statement들 (증명자와 검증자 모두에게 공유된다)은 비밀정보 witness (증명자만 알고있고, 증명 과정에서 정보가 새지 않는다) 와, witness와의 관계성을 위한 매개체로서 instance (증명자와 검증자 모두가 알고 있다)의 두 개념으로 구성된다. 예를 들어, 암호화되고 인증된 은행기록들 (instance) 의 사실 여부 (statement) 의 증명을 위해 증명자는 복호화 키와 평문과 같은 비밀 정보들 (witness)을 알고있어야 하고, 이 때 검증자는 witness에 대한 어떠한 정보도 유출될 수 없다는 사실을 안다.
즉, Zero-knowledge proof 시스템은 증명자가 검증자로 하여금 그 statement가 사실임을 믿게 하기 위해 그 두사람이 어떤 대화를 하는지에 대한 구체적인 명세이다. 이 증명 시스템은 completeness, soundness, zero-knowledge의 세 속성을 필요로 한다.
- Completeness : statement가 사실이고 증명자와 검증자가 모두 프로토콜을 잘 따랐다면, 검증자는 accept한다.
- Soundness : statement가 거짓이고 검증자가 프로토콜을 잘 따른다면, 검증자는 속지 않는다.
- Zero-knowledge : statement가 참이고 증명자가 프로토콜을 잘 따른다면, 검증자는 증명자와의 대화로부터 그 statement가 참이라는 사실 외에 비밀 정보에 대한 어떠한 정보도 얻을 수 없다.
Proofs vs. Arguments.
ZKP 이론에서 proof와 argument는 증명자와 검증자의 계산능력과 관련하여 구분되는 개념이다. Proof는 계산능력에 제한이 없는 증명자 (computationally unbounded provers)에 대하여 sound해야 하는 반면, Argument는 계산능력에 제한이 있는 증명자 (대개 probabilistic polynomial time algorithms로 정의됨) 에 대하여 sound하다고 여겨지면 된다.
1.2 Terminology
- Instance : 증명자 (P) 와 검증자 (V) 모두에게 공유된 입력으로, 증명되어야 하는 statement가 “무엇"인지를 정하기 위해 사용된다. Notation은 x.
- Witness : 증명자에게 주어진 프라이빗 인풋. Notation은 w.
- Relation : instance와 witness사이의 구체적인 관계. relation은 (instance, witness) 모양의 모든 가능한 쌍들의 집합. Notation은 R.
- Language : R에 속하는 가능한 한 쌍(instance, witness)에서 나타날 수 있는 모든 instance들의 집합. Notation은 L.
- Statement : instance와 relation으로 정의된다. 해당 instance가 relation 에 속하는 witness를 가진다는 주장 (참일 수도, 거짓일 수도 있다) Notation은 x ∈ L.
- Security parameter : 원하는 보안 수준을 나타내는 양의 정수 (예. 128 또는 256 등). security parameter가 클 수록 보안 수준이 높다. 대부분의 construction에서 distinction은 computational security parameter 또는statistical security parameter 로 만들어진다. Notation은 k (computational) 또는 s (statistical).
- Setup : 증명자 (P) 와 검증자 (V) 에게 주어지는 instance x와 witness w를 제외한 입력들. 각각의 주체들의 setup은 private component (“PrivateSetup_P” , “PrivateSetup_V”) 와 common component “CommonSetup = CRS” (P와 V 모두가 안다)로 나뉠 수 있다. 이 때 CRS는 “common reference string”의 줄임말로 몇몇의 zero-knowledge proof systems에서 필요하다. Notation은 setup_P = (PrivateSetup_P, CRS) and setup_V = (PrivateSetup_V, CRS).
1.3 Specifying Statements for ZK
이 문서는 instance x와 witness w 사이의 관계 R에 의해 정의되는 statement들의 유형을 고려한다. Relation R은 (x, w) 쌍이 서로 관계가 있는지, 그렇지 않은지를 구체화해준다. Relation은 R 안에서 witness w를 가지는 instance x들로 구성된 matching language L을 정의한다.
Relation R은 (x, w)의 쌍으로 구성되는 집합의 형태이고, Language L은 참이 될 수 있는, 즉 witness가 존재하는 statement x들로만 구성된 집합이라고 이해하면 된다.
하나의 statement는 “x ∈ L (x는 Language L에 속한다, 즉 Relation을 만족시키는 witness w가 존재한다는 의미)” 형태의 membership에 대한 주장일 수 있고, 또는 “relation R의 범위 안에서, 나는 instance x에 대한 하나의 witness를 알고 있다"는 형태의 knowledge에 대한 주장일 수 있다. 몇몇의 케이스에서, statement의 knowledge와 membership의 유형은 “informally” 서로 교환가능한 것으로 간주되기도 하지만, 사실은 이 두 개념이 구분되어야 하는기술적인 이유가 있다. 특히, statement of knowledge가 statement of membership으로 변환 될 수 없는 시나리오들이 존재하고, 그 반대 역시 그렇다. 이 케이스에 대해서 1.4 섹션에서 다룬다. 또한, 본 문서에서 다루는 많은 예시들은 종종 statement of knowledge에 기반한다.
Relation R은 하나의 프로그램(C나 Java와 같은 언어로 작성된)으로 정의될 수 있다. 이 프로그램은 x 와 w를 입력으로 받고 acceptance를 결정하는 프로그램으로, 이 때 accept한다는 것은 (x, w) ∈ R 을 의미하고, reject 한다는 것은 입력된 w이 x ∈ L의 witness가 아니라는 것을 의미한다. Relation들은 random access memory(RAM) program이나, Boolean 또는 Arithmetic circuit으로 정의될 수 있다.
1.3.1 ) Circuit representation
Circuit은 node들과 node들을 위한 label들로 이루어진 directed acyclic graph (DAG)로서, 다음의 조건들을 만족시킨다.
- 입력으로부터 0번째 degree의 Node들은 input nodes이고, 입력 변수명(예: v1, v2, …) 또는 상수 (예: 0, 1, …) 로 label이 붙는다.
- 출력으로부터 0번째 degree에는 단 한개의 Node가 있고, 이것은 output node이다.
- 그 사이의 node들은 gate nodes로서, 해당 node에서 행해지는 computation을 나타낸다.
Parameters. TBC.
References
[ZKProof] ZKProof Community Reference. Version 0.2. Ed. by D. Benarroch, L. T. A. N. Brandão, E. Tromer. Pub. by zkproof.org. Dec. 2019. Updated versions at https://zkproof.org
[GMR89] S. Goldwasser, S. Micali, and C. Rackoff. “The Knowledge Complexity of Interactive Proof Systems”. In: SIAM Journal on Computing 18.1 (1989), pp. 186–208. doi: 10.1137/0218012.
