1. 영지식 증명이란?

영지식 증명(Zero-knowledge Proof, ZKP)은 일종의 Proof System이며, 1980년대 MIT의 Shafi Goldwasser, Silvio Micali, Charles Rackoff가 처음 제안한 기술입니다. 초기의 Proof System에서는 증명자와 검증자가 있을때 검증자는 기본적으로 신뢰할 수 있는 주체이고 증명자는 그렇지 않을 수 있다는 가정하에 다양한 상황에 안정적으로 대응할 수 있는 기술을 만드는 것에 초점을 맞추었습니다. 하지만 검증자도 정직하지 않을 수 있고 그러한 가정하에 나온 것이 영지식 증명입니다. 즉, 증명을 위해서 증명자가 제공한 정보를 검증자가 다른 방식으로 악용할 수 있기 때문에 증명을 위해서 사용되는 데이터에 원천적으로 어떤 의미론적인 데이터도 포함되지 않도록 만들자는 것이 영지식 증명이라고 할 수 있습니다.

이처럼 영지식 증명은 증명자(Prover)가 검증자(Verifier)에게 자신의 주장(Statement)이 사실임을 증명하는데 사용되는 암호화 기술이라고 할 수 있으며, 증명자는 자신의 주장을 증명하기 위해서 검증자에게 자신의 주장에 관한 어떤 정보도 제공(유출)하지 않으며, 검증자는 증명자의 주장에 대한 어떤 정보도 알지 못한 상태에서 검증을 수행하게 수행하게 됩니다.

예를 들어, A는 B에게 자신이 천만원이 있다고 증명하고 싶다고 가정해 보겠습니다. 가장 쉬운 방법은 A가 B에게 천만원이라는 돈을 실제로 보여주거나, 자신의 통장 잔고 증명서를 보여주는 것입니다. 하지만 이는 영지식 증명이 아닙니다. A의 주장을 뒷받침하는 명확한 정보를 B에게 전달하기 때문입니다. 영지식 증명에서 A는 자신이 가지고 있는 돈과 관련된 정보를 전혀 제공하지 않은 상태에서 증명을 할 수 있어야 하고, B 또한 A가 가지고 있는 돈과 관련된 어떤 정보도 없이 A의 주장이 사실인지 검증할 수 있어야 합니다.

또 다른 예를 들면, A는 편의점에서 담배나 술을 사려고 합니다. 편의점 판매원 B는 A가 성인인지 의심스럽다면 A가 성인인지 여부를 확인해야 합니다. 일반적으로 B는 A에게 주민등록증과 같은 신분증을 요구하게 됩니다.즉, B는 신분증을 보고 A가 담배나 술을 살 수 있는 권한이 있는지 확인하는 것입니다. 이때, A는 신분증을 보여주지 않고 자신이 성인인지를 증명할 수는 없을까요? 이와 같은 경우에 영지식 증명을 사용한다면 A는 신분증을 보여주지 않고 자신이 성인이라는 것을 증명할 수 있습니다.

블록체인에 대한 예를 들면, A가 B에게 가상 자산을 보내려고 합니다. 가상 자산이 전달되는 트랜잭션에 영지식 증명을 적용한다면 가상 자산을 송신하는 A와 그것을 수신하는 B의 프라이버시를 보호하면서 트랜잭션이 정당하다는 것을 증명할 수 있습니다.

이처럼 영지식 증명에서는 증명자가 자신의 주장과 관련된 정보 노출을 배제시키면서 자신의 주장을 증명할 수 있기 때문에 사용자의 프라이버시가 중요한 부분에 사용될 수 있습니다.

영지식 증명이 무엇이고 어떻게 가능한지를 설명할 때 가장 흔하게 볼 수 있는 예가 알리바바의 동굴(Ali Baba Cave) 문제입니다. 즉, 앨리스(Alice)와 밥(Bob)이 있을때, 밥은 자신이 동굴 안에 있는 문을 열 수 있는 열쇠가 있다는 것을 증명하고 싶습니다. 증명 과정은 다음과 같은 과정으로 진행됩니다.

이때 중요한 부분은, 밥은 자신이 열쇠가 있다는 사실을 증명하기 위해서 앨리스에게 열쇠를 보여 주지 않고 증명 과정이 수행된다는 것입니다.

1.1 영지식 증명의 구성 요소

영지식 증명(이후 부터는 ZKP와 혼용해서 사용)은 다음과 같은 세 가지 구성 요소로 이루어집니다.

• 증명자(Prover) : 자신의 주장이나 진술을 증명하고자 하는 주체
• 검증자(Verifier) : 증명자의 주장이나 진술이 맞는지 검증하는 주체
• 주장 또는 진술(Statement) : 증명자가 검증자에게 증명하고자하는 내용

1.2 영지식 증명의 필요 조건

• Completeness : 주장이나 진술이 참이면 증명자는 그것이 참이라는 것을 검증자에게 확신시킬 수 있어야 합니다.
• Soundness : 거짓된 증명자(Cheating Prover)는 자신의 거짓된 주장이나 진술(Fake Statement)로 검증자에게 증명할 수 없어야 합니다.(운에 기대어 검증을 통과할 수 없어야 합니다.)
• Zero-Knowledge : 증명과 검증 과정에서는 주장이나 진술과 관련된 어떤 정보도 전달되어서는 안됩니다. 따라서 검증자는 증명자의 주장이나 진술에 대한 어떤 정보도 추출할 수 없어야 하며, 검증자는 증명자의 주장이나 진술이 참인지 거짓인지 만을 판단합니다.

Completeness와 Soundness는 일반적인 Proof System의 필요 조건이라고 할 수 있으며 이 두 가지 조건에 Zero-Knowledge 조건이 추가된 것이 영지식 증명이라고 할 수 있습니다.

1.3 영지식 증명은 어떤 경우에 사용할 수 있을까?

영지식 증명은 다양한 경우에 사용될 수 있으며, 적용할 수 있는 몇 가지 예를 들면 다음과 같습니다.

• 인증(로그인) : 어떤 사이트나 시스템에 대한 인증(로그인)이 필요할때 인증 정보(패스워드)를 입력하지 않고 해당 인증 정보(패스워드)를 소유하고 있다는 것을 증명함으로써 인증을 수행할 수 있습니다.
• 온라인 투표 : 영지식 증명은 온라인 비밀 투표에서 사용할 수 있습니다.(영지식 증명을 이용한 블록체인 기반의 온라인 비밀 투표 시스템인 zkVoting인 CES 2023에서 기술 혁신상을 수상하기도 하였습니다.)
• 자격 증명 : 영지식 증명을 통해서 어떤 정보도 노출하지 않고 단지 자격이 있는지를 검증할 수 있습니다.
• 블록체인 : 블록체인의 트랜잭션 데이터에 영지식 증명을 적용하면 트랜잭션에 포함되는 민감 정보를 은닉(Hiding)시킬 수 있습니다. 즉, 프라이버시를 위해서 거래(트랜잭션)의 익명성을 제공(shielded/confidential transaction)할 수 있고 블록체인에 저장되는 데이터의 용량을 줄일 수 있습니다. 또한, 블록체인의 Scalability 향상을 위한 목적으로 많이 사용(zk-Rollup)되고 있습니다.
• 데이터 프라이버시 : 사용자의 민감 정보(개인 정보, 금융 정보 등)를 노출하지 않고 증명할 수 있는 용도로 사용될 수 있습니다.
• 지식에 대한 증명 : 어떤 문제의 답을 알고 있다고 증명하거나, 어떤 정보를 알고 있거나 어떤 데이터를 가지고 있다고 증명하는데 사용될 수 있습니다.

1.4 Interactive ZKP vs. Non-Interactive ZKP

영지식 증명은 증명이 수행되는 형태에 따라서 크게 두 가지로 구분할 수 있습니다.

1.4.1 Interactive ZKP(대화형 영지식 증명)

증명자와 검증자 간의 상호 작용(Interaction, Communication)을 통해서 증명자가 검증자에게 제시하는 증명 데이터(Proof)가 만들어지고 그것을 이용해서 증명자의 주장이 검증되는 방식입니다. 앞서 예로든 “알리바바의 동굴 문제”가 대표적인 Interactive ZKP라고 할 수 있습니다.

이 방식은 다음과 같은 특징을 가지고 있습니다.

• 증명자와 검증자 간의 커뮤니케이션 비용이 든다.
• 증명이 이루어지는 동안 증명자와 검증자가 모두 온라인 상태에 있어야한다.
• 증명을 위한 커뮤니케이션 당사자(검증자)만 검증을 수행할 수 있다.
• 증명자와 검증자가 결탁할 가능성이 있다.
• 주로 특정 검증자에게 증명이 필요할 때 사용할 수 있다.
• 여러 검증자에게 동시에 증명해야 할 때는 비효율적이다.
• 증명 데이터는 재사용 불가하다.(즉, 증명에 사용된 증명 데이터를 다른 검증자의 검증 과정에 사용할 수 없다.)
• 동기화 방식

1.4.2 Non-Interactive ZKP(비대화형 영지식 증명)

증명자와 검증자의 상호 작용없이 증명자가 만들어서 제시한 증명 데이터(Proof)를 검증자가 바로 검증하는 방식입니다. (증명자와 검증자는 사전에 셋업(Setup) 과정을 수행하는 경우와 그렇지 않은 경우가 있습니다.) Fiat-Shamir Heuristic을 Non-Interactive ZKP라고 할 수 있습니다.

이 방식은 다음과 같은 특징을 가지고 있습니다.

• 증명자와 검증자 간의 커뮤니케이션 비용을 최소화(단 한번의 증명 데이터 전달만 필요)시킨다.
• 증명자와 검증자는 독립적으로 동작할 수 있다.
• 증명자와 검증자가 모두 온라인 상태에 있어야하는 제약과 시간적인 제약이 없다.(즉, 증명자가 증명 데이터를 보내고 연결이 끊어지더라도 증명 데이터를 검증자가 접근 가능한 곳(예 : 블록체인)에 저장해 놓으면 이후에 검증자는 해당 증명 데이터를 이용해서 검증을 수행할 수 있다.)
• 여러 검증자에게 동시에 증명할 수 있다.
• 증명 데이터는 재사용 가능하다.
• 비동기 방식이 가능하다.

2. 영지식 증명이 이루어지는 과정

영지식 증명은 다음과 같은 함수 f가 있을때, 증명자는 함수의 결과를 true로 만드는 입력 값을 가지고 있다는 것을 증명하는 것이고 검증자는 증명자의 입력 값에 의해서 만들어지는 함수의 결과가 true인지 false인지 판단하는 것이라고 정의할 수 있습니다.

f(x, w) = true/false

함수 f에 입력되는 x는 public input이고 w는 private입니다. 이해를 돕기 위해서, 증명자는 자신의 은행 잔고가 1000원 보다 많다(사실, 증명자의 은행 잔고는 2000원 입니다)는 사실을 자신의 은행 잔고를 노출시키지 않고 검증자에게 증명하고 싶다고 가정해 보겠습니다. 이를 함수 f로 표현하면,

f(1000,2000) = true

이때, 1000은 public input인 x가 되고, 2000은 private input인 w가 됩니다. 2000은 검증자에게 노출되어서는 안되는 입력 값이기 때문에 private input이라고 부르며 또 다른 용어로는 witness라고도 합니다. 결국, 증명자는 x가 주어졌을 때 함수 f의 결과를 true로 만드는 w를 알고 있다는 것을 증명하는 과정이라고 할 수 있습니다.

함수 f를 프로그래밍 코드로 표현하면 다음과 같습니다.

function f(x, w) {

return (x < w);

}

영지식 증명 과정을 논리적인 관점에서 보면 크게 3 단계로 이루어집니다.

2.1 1단계 : 키 생성 단계

키 생성(Key Generation)은 다음과 같이 정의된 함수 G에 의해서 수행된다고 정의할 수 있습니다.

G(f, λ) = (pk, vk)

f : program code / circuit

λ : random secret parameter

pk : proving key

vk : verification key

함수 G는 검증자가 수행하며, 함수 G의 결과로 만들어진 pk는 증명자에게 공유해줍니다. 기본적으로 키 생성은 주어진 f에 대해서 한번만 수행되어야 합니다.

2.2 2단계 : 증명 데이터 생성 단계

증명 데이터(Proof) 생성은 다음과 같이 정의된 함수 P에 의해서 수행된다고 정의할 수 있습니다.

P(pk, x, w) = proof

pk : proving key

x : public input

w : private input (witness)

proof : proof data

함수 P는 증명자가 수행하며, 키 생성 단계에서 만들어진 pk와 x, w를 이용해서 증명 데이터(proof)를 생성합니다. 그리고 함수 P의 결과로 만들어진 증명 데이터는 검증자에게 전달됩니다.

2.3 3단계 : 검증 단계

증명 데이터(Proof)를 검증하는 것은 다음과 같이 정의된 함수 V에 의해서 수행된다고 정의할 수 있습니다.

V(vk, x, proof) = true/false

vk : verification key

x : public input

proof : proof data

함수 V는 검증자가 수행하며, 증명자가 전달한 증명 데이터(proof)를 이용해서 함수 V의 결과가 true인지 false인지 확인하는 것입니다. 즉, 검증자는 증명자만 알고 있는 w를 모른 상태에서 검증을 수행하는 것입니다. 만일, 결과가 true라면 f(x,w)의 결과가 true라는 의미가 되고 검증자는 증명자의 주장이 맞다고 확신할 수 있습니다.

⚠️λ

키 생성 단계에서 사용되는 λ는 증명자에게 노출되어서는 안됩니다. 만일, 증명자가 λ를 알게되면 fake proof를 만들수도 있습니다. 즉, 증명자는 w를 모른 상태에서 V(vk, x, proof)이 true가 되는 fake proof를 만드는 것이 가능해 지는 것입니다. 이런 관점에서 λ를 “toxic”라고하며 키 생성를 수행한 후에는 제거하는 것(이 과정을 “toxic waste”라고도 합니다)이 안전합니다.

지금까지는 영지식 증명의 과정을 하이레벨의 관점에서 간단히 살펴보았습니다. 이제는 실제로 가장 많이 사용되는 영지식 증명 Scheme인 zk-SNARK를 기준으로 영지식 증명이 구체적으로 어떻게 수행되는지 알아보겠습니다.

블록체인 기반의 영지식 증명을 구현할 때 영지식 증명은 각 단계는 다음과 같이 될 것입니다.

1. G (키 생성 단계) : off-chain
2. P (증명 데이터 생성 단계) : off-chain
3. V (검증 단계) : on-chain (스마트 컨트랙트에 의해서 검증이 수행됨)

3. zk-SNARK

zk-SNARK는 “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge”의 약자이며, 이름에서 유추할 수 있듯이 Non-Interactive ZKP를 위한 Scheme이며 증명 데이터가 간결(Succinct)하다는 것이 특징입니다. 일반적으로 증명해야하는 주장이나 진술의 복잡도가 높을 수록 증명 데이터의 크기도 증가하지만 zk-SNARK를 이용해서 만들어지는 증명 데이터는 크기는 일정하거나 선형적인 관계를 제공합니다. 검증자에게 전달되는 증명 데이터의 크기가 작으면 검증을 위한 계산량이 작아져서 빠르게 검증을 수행할 수 있는 장점을 가집니다. 또한, 증명 데이터를 저장할 필요가 있는 경우에도 증명 데이터의 크기가 작으면 그 만큼 필요한 저장 공간의 크기도 작아지게 됩니다.

zk-SNARK를 위해서 2013년에 Pinocchio 프로토콜이 발표되었고, 2016년에는 Pinocchio의 성능을 개선한 Groth16이 발표되었다. 이후 2020년에 Plonk가 발표되었습니다. 이들은 모두 영지식 증명을 위한 전반적인 수행 로직은 비슷하지만 좀더 빠르고 효과적으로 증명과 검증 과정이 수행되도록 진화하고 있습니다.

zk-SNARK는 내부적으로 다음과 같은 과정을 거쳐서 영지식 증명을 수행하게 됩니다.

이제 부터는 zk-SNARK의 각 단계가 무엇을 의미하고 어떻게 수행되는지 자세히 살펴 보겠습니다.

3.1 문제 정의

zk-SNARK에 대해서 살펴보기에 앞서, 증명자는 다음과 같은 문제의 정답을 알고 있다는 사실을 검증자에게 증명하고 싶다고 가정해 보겠습니다.

x2 + x + 1 = 13 ---------------- 식(1)

위 식을 만족하는 x 값은 3(-4는 제외)이며, 증명자는 위 식을 만족하는 (x값을 전달하지 않고) x값을 알고 있다는 것을 증명하고 싶은 것입니다. 그리고 검증자의 입장에서는 증명자가 증명하려는 것이 진짜 식(1)을 만족하는 x값을 증명하는 것인지 확신할 수 있어야 합니다. 이를 위해서 다음에 설명하는 과정을 거치게 됩니다.

3.2 Algebraic Circuit

먼저 위 문제(식(1))를 수학적으로 표현하기 위해서 먼저 algebraic circuit으로 표현합니다. 위 식(1)을 의사코드(Pseudo Code)로 표현하면 다음과 같습니다.

function f(x) {

y = x * x;

return (y+x + 1);

}

3.2.1 Flattening

작성된 코드를 심볼 변수를 이용해서 Flattening하면 다음과 같습니다.

(x : 입력, out : 출력, sym1, sym2 : 중간값을 의미)

sym1 = x * x

sym2 = sym1 + x

out = sym2 + 1

3.2.2 Algebraic Circuit

Flattening된 코드를 algebraic circuit으로 표현하면 다음과 같이 세 개의 gate로 구성된 circuit이 만들어집니다.

sym1 = x * x ---------------- gate1

sym2 = sym1 + x ---------------- gate2

out = sym2 + 1 ---------------- gate3

다음 단계는 algebraic circuit을 벡터 스페이스로 변환하는 것입니다.

3.3 R1CS(Rank-1 Constraint System)

R1CS는 Rank-1 Constraint System을 의미하며, R1CS는 세 개의 constraint 벡터 a, b, c와 solution 벡터 s로 구성되며(각 벡터들의 rank는 1), sa * sb - sc = 0의 관계를 만족하는 시스템입니다. ( : dot product)

algebraic circuit을 R1CS로 변환하기 위해서 각 gate는 a* b = c (즉, a* b -c = 0)형태가 되어야 합니다.

sym1 = x * x ---------------- gate1

sym2 = (sym1 + x)*1 ---------------- gate2

out = (sym2 + 1) *1 ---------------- gate3

그리고 각 gate의 a항과 b항, c항에 해당하는 부분이 어떤 심볼 변수로 구성이 되어있는지를 벡터로 표현합니다.

• gate1의 심볼 변수 구성 벡터

심볼 변수 : 1 x out sym1 sym2

a : [0, 1, 0, 0, 0] : x

b : [0, 1, 0, 0, 0] : x

c : [0, 0, 0, 1, 0] : sym1

• gate2의 심볼 변수 구성 벡터

심볼 변수 : 1 x out sym1 sym2

a : [0, 1, 0, 1, 0] : sym1 + x

b : [1, 0, 0, 0, 0] : 1

c : [0, 0, 0, 0, 1] : sym2

• gate3의 심볼 변수 구성 벡터

심볼 변수 : 1 x out sym1 sym2

a : [1, 0, 0, 0, 1] : sym2 + 1

b : [1, 0, 0, 0, 0] : 1

c : [0, 0, 1, 0, 0] : out

• solution 벡터

(solution 벡터는 증명자만 알고 있는 답인 x=3을 circuit에 입력했을 때의 각 심볼 변수의 값으로 구성됩니다. 따라서 solution 벡터는 증명자만이 아는 벡터입니다. solution 벡터를 witness라고도 합니다.)

심볼 변수 : 1 x out sym1 sym2

s : 1, 3, 13, 9, 12

각 gage를 a* b = c 형태의 벡터로 표현한 상태에서는 a* b = c 연산이 성립하지 않습니다. 왜냐하면 벡터 a, b, c에는 gate가 어떤 심볼 변수로 구성되었는지에 대한 의미만을 포함하고 있기 때문입니다. 따라서 실제 답(x=3)이 적용된 심볼 변수(solution 벡터)가 gate에 적용되어야 합니다. 즉, 벡터 a에 solution 벡터를 적용(sa), 벡터 b에 solution 벡터를 적용(sb), 벡터 c에 solution 벡터를 적용(sc)해야만 합니다.

실제로 sa * sb - sc = 0를 만족하는지 확인해 보기 위해서 각 gate의 a, b, c, s 벡터를 이용해서 계산해 보면 다음과 같습니다.

• gate1

[1, 3, 13, 9, 12] • [0, 1, 0, 0, 0] * [1, 3, 13, 9, 12] • [0, 1, 0, 0, 0] - [1, 3, 13, 9, 12] • [0, 0, 0, 1, 0] = 3 * 3 - 9 = 0

• gate2

[1, 3, 13, 9, 12] • [0, 1, 0, 1, 0] * [1, 3, 13, 9, 12] • [1, 0, 0, 0, 0] - [1, 3, 13, 9, 12] • [0, 0, 0, 0, 1] = 12 * 1 - 12 = 0

• gate3

1, 3, 13, 9, 12[1, 0, 0, 0, 1] * [1, 3, 13, 9, 12][1, 0, 0, 0, 0] - [1, 3, 13, 9, 12][0, 0, 1, 0, 0] = 13 * 1 - 13 = 0

또한, 각 gate에 solution 벡터의 값을 직접 적용해도 등식이 성립함을 알 수 있습니다.

sym1 = x * x ---------------- 9 = 3 * 3

sym2 = (sym1 + x)*1 ---------------- 12 = (9 + 3) * 1

out = (sym2 + 1) *1 ---------------- 13 = (12 + 1) * 1

종합적으로 보면,

(3 * 12 * 13) * (3 * 1 * 1) - (9 * 12 * 13) = 0 (이 연산 방식 이외에 Hadamard Product를 이용할 수도 있습니다.)

즉, sA * sB - sC = 0이 됨을 알 수 있습니다.

결국, 원래 문제의 답(해)을 구하는 것이 solution 벡터 s를 알아내는 문제로 변환된 것입니다.

3.4 QAP(Quadratic Arithmetic Program)

지금까지, 문제를 정의하고 그것을 Algebraic Circuit으로 만들어서 R1CS로 변환하였습니다. 즉, 증명자는 증명하고자 하는 문제의 내부 로직을 로직 gate로 변환하여 벡터 형태로 표현하였습니다.(문제를 벡터로 변환)

다음 단계는 R1CS를 QAP(Quadratic Arithmetic Program)로 변환하는 것입니다. 이는 벡터로 변환된 문제를 다항식(Polynomial)으로 변환하는 것이라고 할 수 있습니다. 좀더 엄밀하게 말하면, QAP는 증명하고자하는 주장이나 진술(statement)를 다항식으로 변환(표현)하고 검증하는 방법을 제공합니다.

각 gate의 a항을 표현하는 벡터를 모아놓은 행렬 A는 다음과 같습니다.

행렬 A의 파란 박스의 값 0, 1, 0, 0, 0은 다음과 같은 의미를 갖습니다.

• 0 : gate1을 a* b = c 로 표현한 수식에서 a항의 첫 번째 심볼 변수 1에 해당하며 1의 계수(coefficient)가 0이라는 의미
• 1 : gate1을 a* b = c 로 표현한 수식에서 a항의 두 번째 심볼 변수 x에 해당하며 x의 계수(coefficient)가 1이라는 의미
• 0 : gate1을 a* b = c 로 표현한 수식에서 a항의 세 번째 심볼 변수 out에 해당하며 out의 계수(coefficient)가 0이라는 의미
• 0 : gate1을 a* b = c 로 표현한 수식에서 a항의 네 번째 심볼 변수 sym1에 해당하며 sym1의 계수(coefficient)가 0이라는 의미
• 0 : gate1을 a* b = c 로 표현한 수식에서 a항의 다섯 번째 심볼 변수 sym2에 해당하며 sym2의 계수(coefficient)가 0이라는 의미

행렬 A의 붉은 박스의 값 1, 1, 0은 각각 다음과 같은 의미를 갖습니다.

• 1 : gate1을 a* b = c 로 표현한 수식에서 a항의 두 번째 심볼 변수 x에 해당하며 x의 계수(coefficient)가 1이라는 의미
• 1 : gate2를 a* b = c 로 표현한 수식에서 a항의 두 번째 심볼 변수 x에 해당하며 x의 계수(coefficient)가 1이라는 의미
• 0 : gate3을 a* b = c 로 표현한 수식에서 a항의 두 번째 심볼 변수 x에 해당하며 x의 계수(coefficient)가 0이라는 의미

행렬의 각 열을 구성하는 값들의 의미를 기반으로 다항식을 만들 수 있습니다. 행렬의 두 번째 열의 값(1, 1, 0)에서 다음과 같이 gate의 번호, 계수 값 쌍을 만들 수 있습니다.

(1, 1) : gate1, 계수 1

(2, 1) : gate2, 계수 1

(3, 0) : gate3, 계수 0

(1, 1), (2, 1), (3, 0)을 2차원 공간의 세 점이라고 정의한다면, 이 세개의 점을 지나는 다항식을 계산할 수 있습니다. 특정한 점을 지나는 다항식을 구하는 방법으로는 Lagrange Interpolation이나 Fast Fourier Transform(FFT)을 이용할 수 있습니다.

이렇게 구한 다항식 f(x)는 gate1, 2, 3의 a항 중에서 심볼 변수 x에 대한 다항식 표현이라고 할 수 있습니다. 그리고 다항식 f(x)의 입력 변수 x에 의해서 gate가 구별됩니다. 즉, f(1)은 gate1에 대한 심볼 변수의 계수를 나타내고 f(2)는 gate2에 대한 심볼 변수의 계수를, f(3)은 gate3에 대한 심볼 변수의 계수를 나타냅니다.

행렬 A, B, C의 모든 열 벡터를 다항식으로 변환하고 그렇게 구한 각 다항식의 계수를 행렬로 표현하면 다음과 같습니다.

위 행렬을 의미적으로 표현하면 다음과 같습니다.

A[x], B[x], C[x]를 계수가 아닌 다항식으로 표현하면 다음과 같습니다.

A[x] B[x] C[x]

따라서, A[x]에서 x=1을 적용한 A[1]은 gate1의 a항의 심볼 변수들의 계수(행렬 A의 첫 번째 행의 값과 일치)를 의미하고, A[2]는 gate2의 a항의 심볼 변수들의 계수(행렬 A의 두 번째 행의 값과 일치)를 의미하고, A[3]은 gate3의 a항의 심볼 변수들의 계수(행렬 A의 세 번째 행의 값과 일치)를 의미합니다. 이처럼 B[1], B[2], B[3], C[1], C[2], C[3]의 경우도 각각 gate1,2,3의 b, c항의 심볼 변수의 계수를 의미합니다.

QAP로 변환된 다항식이라고 하더라도 솔루션 벡터를 적용하면 sA * sB - sC=0 관계가 유지되어야 합니다.

그리고 x=1, 2, 3을 적용한다는 의미는 각각 gate1, 2, 3에 대한 R1CS 검증을 수행한다는 의미가 되기 때문에 다음이 성립해야 합니다.

A(1)* B(1)-C(1)=0

A(2)* B(2)-C(2)=0

A(3)* B(3)-C(3)=0

다항식 행렬 A[x], B[x], C[x]는 문제를 알면 누구만 만들 수 있습니다. 하지만 A(x), B(x), C(x)는 solution 벡터를 알고 있는 증명자만 만들 수 있습니다.

A(x)* B(x)-C(x)를 하나의 다항식 P(x)라고 한다면, P(x)는 x가 1, 2, 3일때 그 결과 값이 0이라는 의미가 됩니다. 이는 다항식 P(x)의 해 중에는 x=1, 2, 3이 반드시 포함된다는 의미가 됩니다. 따라서 다항식 P(x)는 반드시 (x-1)(x-2)(x-3)을 포함해야하며 이것으로 (나머지 없이) 나누어 떨어지는 다항식이어야 합니다.

(x-1)(x-2)(x-3)을 T(x)라고 한다면, P(x)는 다음과 같이 표현할 수 있습니다.

P(x) = A(x)* B(x)-C(x)= T(x)*H(x)

(H(x)는 P(x)를 T(x)로 나누었을 때의 몫에 해당하는 임의의 다항식 입니다. 반대로, T(x)는 P(x)를 H(x)로 나누었을 때의 몫에 해당합니다.)

따라서 H(x)는 P(x)/T(x)로 구할 수 있습니다.

p(x)를 실제로 그려보면 x=1,2,3에서 결과 값이 실제로 0이 된다는 것을 확인할 수 있다.

T(x)의 차수(degree)가 d라면, T(x)의 차수(== T(x)의 해의 개수)는 algebraic circuit의 gate 수와 일치한다.

P(x)의 차수 : 최대 2(d-1)

A(x), B(x), C(x)의 차수 : 최대 d-1

H(x)의 차수 : 최대 d-2

정리해보면, 증명자가 답을 알고 있다고 주장하는 문제를 F(x)라고 할때, P(x)는 증명자가 답을 알고 있다고 증명할 수 있는 solution 벡터 s가 적용된 다항식입니다. 따라서 QAP는 대수 방정식(문제, F(x))의 해(x=3)를 안다는 것과 동일한 의미의 다항식(P(x))으로 변환하는 과정이라고 할 수 있습니다.

F(x) => P(x) = A(x)* B(x)-C(x)= T(x)*H(x)

결국, 증명의 대상이 “어떤 문제의 답을 알고 있다.”에서 “어떤 특정 다항식을 알고 있다.”로 변경된 것입니다. 그리고 어떤 특정 다항식을 알고 있다는 말은 “해당 다항식의 계수(coefficient)를 알고 있다.”는 말과 동일하다고 할 수 있습니다.

증명자의 입장에서는 자신의 주장이나 진술을 입증하는 solution 벡터(witness)를 알고 있다는 것을 (solution 벡터를 제시하지 않고) 증명해야 합니다. 증명자가 H(x)를 계산할 수 있다는 것은 증명자가 solution 벡트를 알고 있다는 얘기가 됩니다. 따라서 증명자가 올바른 P(x)와 H(x)를 검증자에게 전달한다면 (T(x)를 알고 있는) 검증자는 증명자가 올바른 solution 벡터를 알고 있다고 판단할 수 있을 것입니다. 만일, 증명자가 witness를 모르거나 조작한다면 H(x)= P(x)/T(x) 관계가 성립하지 않기 때문에 검증자는 그것을 금방 알아차릴 수 있습니다.

지금까지 증명하고자 하는 문제를 최종적으로 검증 가능한 다항식으로 표현하였습니다. 즉, QAP를 이용하여 검증 가능한 2차 다항식(H(x))을 도출하였습니다. 지금 단계에서는 이해를 돕기 위해서 P(x)와 H(x)를 증명 데이터(proof)라고 생각해도 됩니다.

그런데 증명자가 제시하는 증명 데이터(P(x),H(x))를 기반으로 검증자는 어떤 유의미한 데이터를 추출(P(x)와 H(x)의 계수를 통해서)할 가능성이 있습니다. 따라서 영지식 증명의 중요한 요건 중 하나인 영지식성이 추가되어야 합니다. 영지식성을 추가하기 위해서 가장 먼저 직관적으로 생각할 수 있는 방법이 바로 암호화입니다. 하지만 증명 데이터를 일반적인(전통적인) 방식으로 암호화해서 전달하면 검증자는 복호화를 수행하지 않는한 검증을 수행하지 못할 것입니다. 따라서 암호화된 상태에서의 검증이 가능하도록 특별한 형태의 암호화 방법이 필요하며, 이를 위해서 타원 곡선 암호화(Elliptic Curve Cryptography)와 동형 암호화(Homomorphic Encryption) 속성, 그리고 타원 곡선 페어링(Elliptic Curve Pairing)이라는 개념이 사용됩니다.

또한, QAP로 산출한 P(x)와 H(x)만으로는 정직하지 않은 증명자가 H(x)= P(x)/T(x)가 성립하는 다항식을 solution 벡터를 모른 상태에서 인위적으로 만드는 것을 방지하기 힘듧니다.

결국, QAP는 영지식 증명의 Completeness는 지원하지만 Soundness와 Zero-Knowledge는 지원하지 못합니다. 문제가되는 Soundness와 Zero-Knowledge 지원을 위해서는 타원 곡선 암호화와 타원 곡선 페어링이 적용되어야 합니다. 따라서 타원 곡선 암호화와 타원 곡선 페어링이 무엇이고 어떻게 적용되는지 살펴볼 차례있니다. 하지만 그 전에 동형 암호화와 생성자, 다항식의 암호화, CRS에 대해서 먼저 살펴볼 필요가 있습니다.

3.5 동형 암호화(Homomorphic Encryption)

동형 암호화는 암호화된 상태에서 연산을 수행할 수 있게 해주는 암호화 알고리즘입니다. 즉,

a+b => Enc(a) + Enc(b) = Enc(a+b), Dec(Enc(a+b) = a+b

그리고 동형 암호화 알고리즘은 다음과 같이 세 가지로 나눌 수 있습니다.

• Partially Homomorphic Encryption : 암호화된 상태의 데이터를 특정 연산에 대해서 무한대로 수행할 수 있는 알고리즘
• Somewhat Homomorphic Encryption : 암호화된 상태의 데이터를 연산의 종류에 상관없이 제한된 수 만큼만 수행할 수 있는 알고리즘
• Fully Homomorphic Encryption : 암호화된 상태의 데이터를 연산의 종류에 상관없이 무한대로 수행할 수 있는 알고리즘

E(x)를 동형 암호화를 지원하는 함수라고 정의했을때, 다음과 같은 형태의 과정을 거치면 영지식 증명 과정에서 어떤 정보도 유출되지 않도록 만들 수 있을 것입니다.

(전제 조건) 검증자는 T(x)를 알고 있다.

1. 증명자는 E(A(x)), E(B(x)), E(C(x)), E(H(x))를 계산해서 검증자에게 전달한다.
2. 검증자는 E(A(x)*B(x) - C(x)) == E(T(x)*H(x)) 인지 확인한다.

이 과정은 핵심은, 증명자는 증명 데이터를 암호화해서 보내고 검증자는 암호화된 증명 데이트를 이용해서 검증을 수행한다는 것입니다.

이를 위해서 사용되는 암호화가 타원 곡선 암호화이며, 암호화된 상태의 검증을 위해서 암호화된 상태의 연산이 지원되는 동형 암호화 속성이 지원되어야 합니다. 또한 E(z) = E(x*y)인지 검증을 할 수 있어야 하기 때문에 타원 곡선 페어링이 사용되는 것입니다.

동형 암호화에 대한 이야기로 다시 돌아가서, 암호화 함수 E(x) := gx라고 정의하겠습니다.

만일, g가 5라면 x = 3에 대한 암호화 값은 53= 125가 됩니다. 그리고 이 암호화 함수에 대한 연산을 다음과 같이 정의할 수 있습니다.

그런데 만일, gx에서 g가 공개된 값이라고 한다면 암호화된 값의 크기를 보면 원래 x값의 크기를 유추할 수도 있습니다. 이런 문제점을 보완하기 위해서 모듈러 연산(modular arithmetic)을 적용합니다.

모듈러 연산을 적용하게 되면 특정 범위의 수(finite field)만 만들어지게 되어서 원래 x값의 크기를 유추하기 힘들어지고, g의 값을 알고 있다고 하더라도 원래의 x값을 알아내는 것 또한 쉽지 않게 됩니다. 즉, 53 mod 6 = 5일때, g의 값인 5를 알고 있고 암호화된 값인 5를 알고 있다고 하더라도 원래의 x값을 알아내는 것은 쉽지 않습니다. 왜냐하면, 5를 암호화된 값으로 만들 수 있는 x값이 많아지기 때문입니다.

…

(1, 3, 5, … 중에서 어느 것이 원래의 x값인지 판단할 수 없음)

이제는 모듈러 연산을 적용해서 암호화 함수를 E(x) := gx mod n이라고 재정의할 수 있습니다.(이후의 암호화 결과에서는 수식을 간단히 표현하기 위해서 mod n을 생략할 것입니다.)

이 암호화 함수는 다음과 같은 한계점도 존재합니다.

• 암호화된 값 자체에 지수승(exponential)을 하고 싶을 때 : E(x)y = E(xy)가 되기 때문에 원래의 의도인 E(x)에 대한 y 지수승과는 다른 의미를 갖습니다.
• 암호화된 값 두 개를 곱하고 싶을 때 : E(x)*E(y)= E(x+y)가 되기 때문에 원래의 의도와는 다른 의미를 갖습니다.

3.6 생성자(Generator)

앞에서 암호화 함수 E(x) := gx mod n을 정의 했는데, g 값에 대해서는 별도로 설명하지 않았습니다. 결론적으로 말하는 g는 생성자(generator)를 의미합니다. 생성자를 설명하기에 앞서 Group과 Field에 대해서 알아볼 필요가 있습니다. (엄밀히 말하면, 타원 곡선의 generator point)

3.6.1 Group & Field

• Group

Group은 더하기 연산에 대해서 다음과 같은 성질을 지원하는 원소들의 집합을 의미합니다.(예 : 정수, 유리수, 실수)

만일, Commutativity까지 지원한다면 그것을 특별히 Abelian Group이라고 합니다.

• Field

Field는 더하기와 곱하기 연산에 대해서 다음과 같은 성질을 지원하는 원소들의 집합을 의미합니다.(예 : 유리수, 실수)

• Group vs. Field

Field의 성질을 만족한다면 Group의 성질도 만족하기 때문에 모든 Field는 Group에 속한다고 말할 수 있습니다. Group과 Field에 속하는 원소간의 연산에 모듈러 연산을 적용하면 유한한 개수를 가진 Finite Group과 Finite Field를 만들 수 있습니다. 예를 들며, 정수를 Z라고 표기했을 때 정수에 mod 5를 적용하게 되면 유한한 정수 집합인 {0, 1, 2, 3, 4}가 만들어 집니다. 이를 Z5라고 표기하며 Z5는 Finite Group이며 동시에 Finite Field가 됩니다.

• Finite Field

Field를 구성하는 원소들의 수(field order)가 소수(prime number)이거나 power of prime으로 한정된 Field를 Finite Field라고 합니다. 일반적으로 Finite Field를 Galois Field(GF)라고도 부릅니다. (Galois Field는 엄밀히 말하면 field order가 power of prime인 Finite Field임)

• order가 p인 Finite Field : Fp 또는 GF(p) (p : prime number), |Fp| = |GF(p)| = pFp= {0, 1, 2, ..., p-1}
• order가 pn인 Finite Field : Fpn 또는 GF(pn)

그리고 Finite Field를 구성하는 원소간의 더하기, 곱하기 연산은 모듈러 연산(mod p)이 적용됩니다. 따라서 Finite Field의 원소간의 더하기, 곱하기 연산의 결과 또한 Finite Field에 속한 요소의 값이 됩니다.

GF(7) = {0, 1, 2, 3, 4, 5, 6}

4+5=9, 9 mod 7 = 2, 2는 GF(7)의 구성 요소

3.6.2 생성자(Generator)

Finite Field (또는 Finite Group)의 구성 요소로 지수 연산을 했을때 모든 구성 요소를 생성할 수 있는 값을 특별히 생성자(generator g)라고 부릅니다. 즉, 생성자 g를 이용하면 모든 구성 요소를 g 형태로 표현할 수 있습니다.

또한 g가 Finite Field GF(p)의 생성자라면 다음을 만족해야 합니다.

g(p-1) 1 (mod p)

GF(7)의 구성 요소 중에서 2가 생성자가 될 수 있는지 확인해 보겠습니다.

20 1 (mod 7)

21 2 (mod 7)

22 4 (mod 7)

23 1 (mod 7)

…

2는 {1, 2, 4}만 만들어내기 때문에 생성자가 될 수 없습니다.

30 1 (mod 7)

31 3 (mod 7)

32 2 (mod 7)

33 6 (mod 7)

34 4 (mod 7)

35 5 (mod 7)

36 1 (mod 7)

…

3은 GF(7)의 모든 구성 요소인 {0, 1, 2, 3, 4, 5, 6}(0은 additive identity)을 만들어내기 때문에 GF(7)의 생성자라고 할 수 있습니다. (생성자에 대한 지수 연산을 지속적으로 수행하면 GF(7)의 구성 요소를 반복적으로 만들어내게 됩니다. 이를 cyclic 속성이라고 합니다.) 또한, g(p-1) 1 (mod p)를 만족(g6 1 (mod 7))합니다.

생성자가 중요한 이유는, Finite Field를 구성하는 요소로 지수 연산을 수행하면 연산 결과로 해당 Finite Field의 모든 구성 요소가 만들어진다는 특징이 있기 때문입니다. 만일 생성자를 이용하지 않는다면 일정 범위의 수 중에서 일부만 이용될 수 있기 때문에 문제(유추의 가능성)가 될 수 있습니다.

이와 같은 이유 때문에 암호화에 Finite Field가 많이 사용되며 생성자 g가 중요한 역할을 담당합니다.

Zp* :

• =Fp*
• 구성 요소 : {aFp | a0} 즉, {1, 2, ..., p-1} (p : prime number)
• order : |Zp*| = p-1
• 곱하기 연산에 대한 Closure : {a, b Zp* | (a*b) mod p Zp*}
• 생성자가 g이고 {0, 1, ..., p-2} 일때, g mod p의 구성 요소 : {1, 2, ..., p-1}
• 각각의 값에 대해서 g mod p의 값은 Zp*의 구성 요소({1, 2, ..., p-1})에 1:1 매핑된다.

3.7 다항식의 암호화

앞서, 증명자가 제시하는 P(x),H(x)(증명 데이터)의 계수를 통해서 검증자는 어떤 유의미한 정보를 추출할 가능성이 있다고 언급하였습니다. 이를 방지하기 위해서 P(x)와 H(x)를 암호화해서 전달하는 방법을 생각할 수 있습니다.

예를 들어, 다항식 P(x) = x2 -2x + 3을 암호화 한다고 가정해 보겠습니다.

E(P(x)) =g(x2 -2x + 3)

= gx2*g-2x*g3

=(gx2)1*(gx1)-2*(gx0)3

=E(x2)1*E(x1)-2*E(x0)3 (<= 1, -2, 3은 다항식의 계수)

결국, E(xi)와 다항식의 계수를 알면 다항식에 대한 암호화를 수행할 수 있습니다.

그리고 x 대신 임의로 선택된 s에 대한 E(P(s))는 E(s2)1*E(s1)-2*E(s0)3가 됩니다. 만일, 증명자와 검증자가 모두 s 값을 모르고 E(si) ( i{0,1,2})(즉, gs2, gs1, gs0) 값을 안다고 가정한다면, 증명자는 P(x)의 계수를 알고 있기 때문에 E(P(s))를 계산할 수 있습니다. 즉, 증명자는 P(x)에 알지 못하는 값인 s를 적용해서 암호화를 수행할 수 있습니다. 그리고 그 계산 결과를 검증자에게 전달할 수 있을 것입니다. 물론, H(x)의 경우도 마찬가지 입니다. 또한, 검증자는 E(T(s))를 계산할 수 있어서 다음과 같이 검증을 수행할 수 있을 것입니다. 그리고 검증자에 의한 검증을 통과한다면 증명자가 다항식 P(x)의 계수를 제대로 알고 있다고 판단할 수 있을 것입니다.

E(P(s))= i=0dgsici (d : degree of polynomial)

E(P(s))= E(T(s)*H(s))

이때, 증명자와 검증자는 s 값은 모르고 gsi 값만 알고 있는 상태입니다, 그렇다면, g를 알고 있다고 하더라도 si를 알아내는 것은 거의 불가능합니다. 이유는, 이산 로그(대수) 문제이기 때문입니다.

• 이산 로그 문제 : p가 충분히 큰 수라면 특정한 h값에 대해서, g = h (mod p)를 만족하는 값을 알아내는 것은 매우 어렵다. ({0, 1, ..., p-2})

이 방식을 이용하면 증명자는 P(x)의 계수를 노출하지 않고 검증자가 검증을 수행할 수 있는 방법을 제공하게 되는 것입니다.

이 방식은 엄밀히 말하면 다항식을 암호화해서 전달하는 것은 아닙니다. 왜냐하면 임의의 s를 다항식에 적용한 그 결과 값을 암호화해서 보내기 때문 입니다. 이는 다항식을 암호화하는 것에 비해서 장점을 가지고 있습니다. 다항식에 s를 적용한다는 말은 다항식의 특정 좌표에 대한 값을 산출한다는 의미가 되고, 특정 좌표 하나의 값 만을 암호화해서 전달한다면 증명 데이터의 간결성(succinctness)을 확보할 수 있기 때문입니다. 그리고 다항식의 한 좌표의 값만으로 해당 다항식을 대표할 수 있는지에 대한 의문이 생길 수 있습니다. 하지만, 두 개의 다항식이 있을 때, 두 다항식이 다르다면 임의로 선택한 좌표의 값이 같을 확률은 0에 수렴(negligible)한다고 할 수 있고, 반대로 두 다항식이 같다면 임의로 선택한 좌표의 값은 반드시 같게 되기 때문입니다.

그런데, 이 방법에도 한 가지 문제점이 있습니다. 그것은 증명자가 E(si)를 이용하지 않고 E(P(s))= E(T(s)*H(s)) 조건을 만족시키는 P(s)와 H(s)를 인위적으로 찾아내서 그것을 검증자에게 전달할 가능성이 있다는 것입니다. (증명자가 E(P(s))를 계산할 수 있다고 해서 검증자에게 그것을 그대로 전달한다는 것을 보장하는 것은 아니기 때문입니다.) 이는 증명자가 원래의 P(s)를 이용하지 않을 수도 있다는 의미가 됩니다. 즉, 검증자는 증명자가 보낸 값이 진짜 E(P(s))를 계산한 것인지 확인할 수 있어야 합니다. 따라서 검증자는 자신과 증명자가 동일한 E(si)를 사용하는지 확인해야 합니다.

이를 위해서 다음과 같은 상황 조건이 추가되어야 합니다.

1. 어떤 임의의 값 가 있고 증명자와 검증자는 모두 값을 모른다. (를 shifted value 라고 함)
2. 증명자와 검증자는 E(si) ( i{0,1,2})(즉, gs2, gs1, gs0) 값을 안다.
3. 검증자만 E() 즉, g 값을 안다.

이 조건하에서 증명자는 E(P(s))와 E(P(s)), E(H(s))를 계산해서 검증자에게 전달합니다.

E(P(s))= i=0dgsici

그리고 검증자는 다음 조건을 검사해서 증명자가 검증자와 동일한 E(si)를 사용한 것인지 (증명자가 원래의 P(s)를 이용한 것인지) 확인할 수 있습니다. 증명자는 g 값을 모르기 때문에 E(P(s))를 인위적으로 조작할 수 없기 때문입니다.

E(P(s)) = (E(P(s)))

이제, 증명자가 거짓 증명 데이터로 검증자의 검증을 통과할 수 없어야 한다는 Soundness 조건이 만족 되었습니다.

남은 것은 Zero-Knowledge 조건을 만족시키는 것입니다. 앞에서 검증자가 증명 데이터에서 유의미한 정보를 추출하지 못하게 만들기 위해서 다항식을 암호화하는 방법을 적용했습니다. 그럼에도 불구하고 (정보의 가치를 떠나서) P(s)와 H(s), T(s)의 관계가 유지되고 직접적으로 그 관계를 검증하게 됩니다.

이런 점을 보완하기 위해서 증명자는 임의의 값 를 선택해서 전달되는 증명 데이터를 추가적으로 난독화할 수 있습니다.

E(P(s))=> E(P(s)), (gp(s))=> (gp(s))

E(P(s))=> E(P(s)), (gp(s))=> (gp(s))

E(H(s))=> E(H(s)), (gh(s))=> (gh(s))

검증 :

(gp(s))= ((gh(s)))t(s)

(gp(s))=((gp(s)))

3.8 CRS(Common Reference String)

다항식 암호화를 통한 증명과 검증 과정에서는 다음과 같은 상황 조건을 전제로 설명하였습니다.

1. 증명자와 검증자는 모두 임의의 값 s와 를 모른다.
2. 증명자와 검증자는 모두 E(si)와 E(si) 값을 안다.
3. 검증자만 E() 값을 안다.

그렇다면 s와 , E(si)와 E(si), E()를 누가 계산하고 증명자와 검증자에게 E(si)와 E(si) 또는 E()를 전달해주는 것일까요?

• CRS

s, , E(si), E(si), E()를 setup parameter 또는 CRS(common reference string)라고 하며, CRS은 별도의 Trusted Party(TP)가 만들어서 필요한 데이터를 증명자와 검증자에게 공유해줍니다.

• Trusted Setup

TP가 CRS을 생성하고 증명자와 검증자에게 공유해주는 작업을 Trusted Setup이라고 부릅니다. 그리고 증명자와 검증자 간의 영지식 증명 과정이 수행되기 위해서는 사전에 Trusted Setup이 수행되어야 합니다.(Trusted Setup을 parameter generation ceremony라고도 합니다.)

Trusted Setup은 앞서 설명한 “영지식 증명이 이루어지는 과정"의 1단계인 키 생성 단계에 해당됩니다. 키 생성 단계에서 언급되었던 λ, pk, vk는 다음과 같이 매칭이 된다고 볼 수 있습니다.

• λ (random secret parameter) : s, (sFp, sFp*, s,0)
• pk (proving key) : E(si), E(si)
• vk (verification key) : E(), E(t(s))

즉, TP는 secret parameter를 생성해서 pk와 vk를 만들고, pk는 증명자에게 공유하고, vk는 검증자에게 공유하는 것입니다. 이때 중요한 점은, 공유 과정을 수행한 후에 TP는 반드시 secret parameter인 s, 를 제거해야 한다는 것입니다. 그렇지 않으면, 앞에서도 언급했듯이, fake proof를 만들어질 수 있다는 위험이 있습니다.

Trusted Setup 과정과 관련해서는, TP에 대한 신뢰 문제와 TP가 진짜로 secret parameter를 제거했는가에 대한 검증 문제가 발생할 수 있습니다.

이런 문제의 대안으로서 Trusted Setup 과정을 MPC(Multi-Party Computation)로 수행하는 것을 고려할 수 있습니다. MPC로 Trusted Setup 과정을 수행하면 어떤 Party도 secret parameter 값을 알 수 없기 때문에 모든 Party가 담합하지 않는 이상 secret parameter의 유출이나 제거 문제를 해결할 수 있습니다. 물론, MPC를 적용할 때에도 고려해야할 사항이 여러 가지 있습니다. MPC를 수행할 수 있는 최소한의 Party들이 동시에 온라인 상태가 되어야 하고, 어느 한 Party라도 CRS를 만드는 과정에 사용되는 정보를 제거해야하며, 어느 한 Party의 계산 결과가 다른 Party가 전달한 값을 이용한 것이지 검증되어야 하고, 맨 마지막 Party가 최종적으로 만들어낸 CRS가 이전에 다른 Party에서 계산한 결과를 무시하고 임의로 만든 것이 아닌지도 검증해야 합니다.

또 다른 대안으로 TEE(Trusted Execution Environment)를 이용하는 것도 고려할 수 있습니다.

3.9 타원 곡선 암호화(Elliptic Curve Cryptography, ECC)

앞에서 생성자 g를 설명할 때, g는 엄밀히 말하면 타원 곡선의 생성자 포인트(G)라고 언급하였습니다. 이는 암호화 과정에 사용되는 값들이 타원 곡선의 포인트에 매핑되어 수행되기 때문입니다. 일반적으로 말하면, 증명 데이터 생성과 검증 과정이 타원 곡선 상의 포인트 연산에 의해서 실행된다고 할 수 있습니다. 따라서 타원 곡선에 대해서 간단히 살펴볼 필요가 있습니다.

3.9.1 타원 곡선

타원 곡선은 다음과 같이 정의된 함수이며, a와 b 값에 따라서 그 모양이 결정됩니다.

{(x,y) R2 | y2= x3+ ax + b, 4a3+27b20} {0}

a=-1, b=1일 때의 타원 곡선(y2= x3-x + 1)의 모양은 다음과 같습니다.

이는 실수에 대한 타원 곡선을 나타낸 것이며, Finite Field Fp에 대한 타원 곡선은 다음과 같이 정의됩니다.

{(x,y) (Fp)2 | y2 x3+ ax + b (mod p), 4a3+27b20 (mod p)} {0} (p : prime number)

즉, x Fp => y2=x3+ax+b (mod p)=> (x, y) E

E : Elliptic Curve

a=-1, b=1일 때의 Finite Field F13에 대한 타원 곡선(y2= x3-x + 1 (mod 13))의 모양은 다음과 같습니다.

타원 곡선 암호화에서는 Cyclic Finite Field에 대한 타원 곡선을 사용합니다. 타원 곡선은 암호화 뿐만 아니라 Signature Scheme에서도 많이 사용됩니다. 그렇다고해서 아무런 타원 곡선이나 사용되는 것은 아닙니다. 왜냐하면 타원 곡선을 구성하는 파라미터(a, b, p, G 등) 값에 따라서 타원 곡선의 보안 강도와 암호 알고리즘을 수행하는 효율성이 달라지기 때문입니다. 따라서 암호 학자들은 어떤 파라미터를 갖는 타원 곡선이 보안 시스템에 적합한지 연구하였습니다. 그 대표적인 것이 Secp256k1(y2= x3+7) 입니다. 이 외에도 NIST P-256, Edwards 25519라는 타원 곡선이 있으며, 타원 곡선 페어링에 효과적인 BN(Barreto-Naehrig), BLS(Barreto-Lynn-Scott), BLS12–381 등도 있습니다.

타원 곡선 암호화에서는 Cyclic Finite Field에 대한 타원 곡선을 사용하기 때문에 다음과 같은 속성을 가집니다.

• 타원 곡선상의 포인트의 더하기 연산에 대한 Closure, Associativity, Commutativity, Identity, Inverse를 지원한다.
• 타원 곡선 상의 임의의 포인트를 n번 만큼 더하면 O(point of infinity : 더하기 연산에 대한 identity)이 된다. (이때의 n을 타원 곡선의 order라고 함)
• order가 prime number이면 O을 제외한 타원 곡선 상의 모든 포인트가 생성자(generator)가 될 수 있다.

그리고 타원 곡선 암호화는 타원 곡선 상에 있는 포인트에 대한 연산을 다음과 같이 정의합니다.

• 타원 곡선 상에 있는 서로 다른 두 포인트의 더하기(Point Addition)

P + Q + R = 0

P + Q = -R

타원 곡선 상에 있는 서로 다른 두 포인트 P와 Q를

더한 결과는 포인트 -R이 됩니다.

• 타원 곡선 상에 있는 동일한 포인트의 더하기(Point Doubling)

P + P + R = 0

2P = -R

타원 곡선 상에 있는 동일한 포인트 P를 서로

더한 결과는 포인트 -R이 됩니다.

• 타원 곡선 상에 있는 포인트에 대한 스칼라 곱(Scalar Multiplication) : Point Addition과 Point Doubling을 이용하면 포인트에 대한 스칼라 곱 연산을 수행할 수 있습니다.

ex) 3P = P + 2P

(참고로, nP = 0 (n이 order인 경우)

3.9.2 타원 곡선 암호화

기존에 정의한 암호화 함수 E(x) := gx mod p는 Fp의 생성자 g에 대한 지수 연산이라고 말할 수 있으며, 이는 타원 곡선 상에 있는 포인트에 대한 스칼라 곱셈 연산으로 매핑됩니다. 즉, 타원 곡선 상에서는 암호화 함수가 E(x) := xG mod p가 되고, 이는 타원 곡선의 생성자 포인트 G에 대한 스칼라 곱셈 연산이라고 말할 수 있습니다. (즉, 생성자 포인트 G를 x번 더해서 나오는 어떤 포인트가 x에 대한 암호화 값이 됩니다.)

생성자 포인트 G에 대한 스칼라 곱셈 연산이 암호화 함수로서 유효한 이유는 타원 곡선에 대한 이산 로그 문제 때문입니다. 타원 곡선에서의 이산 로그 문제는 kP = R일때, P와 Q를 알고 있는 상태에서 k 값을 알아내는 것입니다. kP = R이 일방향 함수이기 때문에 k 값이 충분히 큰 수라면 그 값을 알아내는 것은 매우 어렵습니다. (이는 앞에서도 언급했듯이, y=gx mod p에서 y, g, p를 안다고 하더라도 x를 알아내는 것이 힘들다는 것과 동일한 원리입니다.) 결국, 타원 곡선 암호화는 타원 곡선 상의 포인트를 이용해서 정보를 은닉하는 것이라고 간단히 말할 수 있습니다.

또한 타원 곡선 암호화는 선형(Linear) 연산을 지원합니다.

E(x+y) = E(x) + E(y)

xE(y) = E(xy)

결국, 증명 데이터에 대한 암호화가 타원 곡선 암호화이며, 검증자 또한 타원 곡선 암호화를 이용해서 검증을 수행하게 됩니다.

3.10 타원 곡선 페어링(Elliptic Curve Pairing)

앞에서 암호화 함수를 설명할 때 지금까지 언급한 암호화 함수는 암호화된 값 자체에 대한 지수 연산과 암호화된 값끼리의 곱하기 연산이 지원되지 않는다(ga*gb는 gab가 아니라 g(a+b)임)고 언급하였습니다. 그런데 검증을 위해서는 E(P(s))가 E(T(s)*H(s))와 같은지를 확인할 수 있어야 합니다. 즉, 곱하기 연산이 지원되는 동형 암호화가 필요하다고 말할 수 있습니다.

타원 곡선 페어링이 바로 E(P(s))= E(T(s)*H(s))에 대한 검증을 수행하기 위해서 사용되는 것입니다.

예를 들어서,

e라는 함수가 있고, 함수에 암호화된 값 aG와 bG가 입력되었을때,

e(aG, bG)= e(G, G)ab 라는 관계를 만족한다면 함수 e를 이용해서 E(P(s))= E(T(s)*H(s))을 검증할 수 있을 것입니다.

즉, 함수 e는 암호화된 입력 값 두 개를 e(G, G)ab로 매핑시키는 함수라고 할 수 있습니다.

e(aG, bG)= e(bG, aG) = e(abG, G) = e(G, abG) =e (G, aG)b =e(G, G)ab

e 함수의 경우처럼 두 개의 값을 하나의 값으로 매핑시키는 함수를 Bilinear 페어링 함수라고 합니다. Bilinear 페어링 함수는 일방향 함수라는 특징을 가지고 있습니다. 따라서 해시 함수나 벡터의 dot product는 Bilinear 페어링 함수의 예가 됩니다.

그리고 타원 곡선 상으로의 매핑을 수행하는 함수를 Bilinear 타원 곡선 페어링 함수라고 합니다. 결국, 타원 곡선 페어링 함수는 암호화된 두 개의 값을 타원 곡선 상의 두 포인트라고 가정해서 두 포인트의 곱하기 결과를 타원 곡선 상의 특정 포인트로 매핑시키는 역할을 합니다. 예를 들어서, 암호화된 값 aG와 bG를 타원 곡선 상의 두 포인트라고 취급하고 두 포인트의 곱을 생성자 포인트 G를 (a*b) 번 더해서 (또는, G에 대한 (a*b) 스칼라 곱셈)산출된 포인트라고 정의합니다.

따라서 검증자는 다음과 같이 shifted value와 E(P(s))= E(T(s)*H(s))을 검증하게 됩니다.

e(P(s)G, G) = e(P(s)G, G)

e(G, G)P(s)=e(G,G)P(s)

e(P(s)G, G) = e(T(s)G, H(s)G)

e(G, G)P(s)= e(G, G)T(s)H(s)

Zero-Knowledge 속성을 부여하기 위해서 임의의 값 을 적용한 증명 데이터의 경우도 이와 동일한 방식으로 검증하게 됩니다.

이와 같은 검증을 타원 곡선 영역이 아닌 정수 영역에서 수행(Integer Pairing)할 수도 있습니다. 하지만 정수 영역에서 수행되는 페어링 함수는 분석 가능성을 내포(진정한 일방향 함수라고 할 수 없음)하기 때문에 타원 곡선 영역에서 수행하게 됩니다.

타원 곡선 페어링을 구현하는 방식은 다양하게 연구되어 왔습니다. 그리고 구현 방식에 따라서 여러 개의 생성자 포인트가 사용되기도 합니다. 예를 들면, Weil Pairing, Tate Pairing, Tate Pairing, Ate Pairing 그리고 성능을 최적화한 Optimistic Ate Pairing 등이 있습니다.

3.11 정리

지금까지 zk-SNARK에 의해서 영지식 증명이 수행되는 일련의 과정을 일반적인 관점에서 살펴 보았습니다. 물론, zk-SNARK 프로토콜 마다 간 단계에서 수행되는 내부 로직이 다를 수 있습니다.

정리 차원에서, 다음 그림은 영지식 증명이 수행되는 과정과 증명자가 증명하려는 내용이 영지식 증명의 각 단계를 수행하면서 어떻게 변화되는지 간단히 보여주고 있습니다.

윤근용 | Blockchain Platform (Tech Lead)

새로운 유형의 모빌리티 경험을 제공하기 위한 블록체인 플랫폼을 개발하고 있습니다.

Reference

[1] Shafi Goldwasser, Silvio Micali, Charles Rackoff, "The Knowledge Complexity of Interactive Proof Systems"

[2] Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer, "From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again"

[3] Oded Goldreich, Silvio Micali, Avi Wigderson, "How to Prove All NP Statements in Zero-Knowledge and a Methodology of Cryptographic Protocol Design"

[4] Manuel Blum, Paul Feldman, Silvio Micali, "Non-Interactive Zero-Knowledge and Its Applications"

[5] Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, Madars Virza, "SNARKs for C : Verifying Program Executions Succinctly and in Zero Knowledge"

[6] Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza, "Scalable Zero Knowledge via Cycles of Elliptic Curves"

[7] Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza, "Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture"

[8] Benedikt B¨unz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, Greg Maxwell, "Bulletproofs: Short Proofs for Confidential Transactions and More"

[9] Bryan Parno, Jon Howell, Craig Gentry, Mariana Raykova, "Pinocchio: Nearly Practical Verifiable Computation"

[10] Anca Nitulescu, "zk-SNARKs: A Gentle Introduction"

[11] Christian Reitwießner, "zkSNARKs in a Nutshell"

[12] Rosario Gennaro, Craig Gentry, Bryan Parno, Mariana Raykova, "Quadratic Span Programs and Succinct NIZKs without PCPs"

[13] Jens Groth, "On the Size of Pairing-based Non-interactive Arguments"

[14] Eli Ben-Sasson, Alessandro Chiesa, Matthew Green, Eran Tromer, Madars Virza, "Secure Sampling of Public Parameters for Succinct Zero Knowledge Proofs"

[15] Oded Goldreich, Silvio Micali, Avi Wigderson, "Proofs that Yield Nothing But Their Validity All Languages in NP Have Zero-Knowledge Proof Systems"

[16] Sean Bowe, Jack Grigg, Daira Hopwood, "Recursive Proof Composition without a Trusted Setup"

[17] Ariel Gabizon, Zachary J. Williamson, Oana Ciobotaru, "PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge"

[18] Alfred Menezes, Palash Sarkar, Shashank Singh, "Challenges with Assessing the Impact of NFS Advances on the Security of Pairing-based Cryptography"

[19] Diego F. Aranha, Laura Fuentes-Casta˜neda, Edward Knapp, Alfred Menezes, Francisco Rodrıguez-Henrıquez, "Implementing Pairings at the 192-bit Security Level"

[20] Certicom Research, "SEC 2: Recommended Elliptic Curve Domain Parameters"

[21] Sean Bowe, Ariel Gabizon, Matthew D. Green, "A multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK"

[22] Sean Bowe, Ariel Gabizon, "Scalable Multi-party Computation for zk-SNARK Parameters in the Random Beacon Model"

[23] Ahmed Kosba, Zhichao Zhao, Andrew Miller, Yi Qian, T-H. Hubert Chan, Charalampos Papamanthou, Rafael Pass, abhi shelat, Elaine Shi, "A Framework for Building Composable Zero-Knowledge Proofs"

[24] Robert P. Gallant, Robert J. Lambert, Scott A. Vanstone, "Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms"

[25] Thomas Chen, Hui Lu, Teeramet Kunpittaya, Alan Luo, "A Review of zk-SNARKs"

[26] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev, "Scalable, transparent, and post-quantum secure computational integrity"

[27] Hunter Ripsom-Gardiner, "Zero-Knowledge Proofs for Puzzles"

[28] Carsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan, "Algebraic methods for interactive proof systems"

[29] Ivan Damgard, "On Σ-protocols"

[30] Dan Boneh, Matthew Franklin, "Identity-Based Encryption from the Weil Pairing"

[31] Benedikt B¨unz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, Greg Maxwell, "Bulletproofs: Short Proofs for Confidential Transactions and More"

[32] Dimitris Mouris, Nektarios Georgios Tsoutsos, "Zilch: A Framework for Deploying Transparent Zero-Knowledge Proofs"

[33] Jacob Eberhardt, Stefan Tai, "ZoKrates - Scalable Privacy-Preserving Off-Chain Computations"