zk-SNARKs 이해하기 - 개념별 정리

zk SNARKs 개념 정리

본 글은 Z Cash의 SNARK설명 시리즈를 한국어로 보기 쉽게 정리한 결과물입니다. 특히 사용되는 개념들을 최대한 잘게 쪼개는 것에 신경써서 정리했습니다. zk SNARKs를 이해하기에는 필요한 기초개념이 수십개에 달하는데 많은 부분에서 한국어로된 자료가 부족해 이해하는 것이 쉽지 않습니다. 개념별로 더 자세한 설명들이 존재하는데 앞으로 천천히 붙여나가도록 하겠습니다.


동형 암호학

동형암호함수의 특성

동형은닉(HH) 함수 E(x) 는 다음 세 가지를 만족

  1. x = E^{-1}(y) 연산이 어렵다.
  2. x \neq y 라면 E(x) \neq E(y) 이다.
  3. E(x)E(y) 를 알고 있다면, xy 를 모르더라도 E(x)+E(y)E(x+y) 를 만들어낼 수 있다.

즉, 사용된 자세한 값들을 노출하지 않으면서도 전체 합이 0임을 증명하는 등의 제로섬 공식을 검증할 때 동형암호학을 유용하게 사용할 수 있다.

동형암호함수를 만드는 법

동형암호함수는 특정한 유한 정수군 내에서 만들어낼 수 있다.

나머지 연산

어떤 정수 n 에 대한 나머지 연산 결과는 \{0, ..., n-1\} 의 원소로 이루어진 집합을 구성한다.

>>> 0 % 3 = 0
>>> 1 % 3 = 1
>>> 2 % 3 = 2
>>> 3 % 3 = 0
>>> 4 % 3 = 1
>>> 5 % 3 = 2

덧셈의 재정의 그리고 집합 \mathbb{Z}_n

"덧셈"을 결과물에 나머지 연산을 추가하도록 재정의한다면, 그 결과물이 \{0, ..., n-1\} 에 속하도록 만들 수 있다. 이렇게 덧셈이 재정의된 집합을 \mathbb{Z}_n 이라 부를 수 있다.

2 + 3 = 2\ (mod 3)

곱셈의 재정의 그리고 집합 \mathbb{Z}_p^*

제수로 소수를 사용한다고 가정해보았을 때, \{1, ..., p-1\} 에 대해 곱셈 또한 나머지 연산을 추가해 재정의해볼 수 있다.

2 \cdot 4 = 1 \ (mod 7)

이렇게 곱셈이 재정의된 집합, 즉 \mathbb{Z}_p 에서 0을 제외한 집합을 \mathbb{Z}_p^* 라고 부른다면, \mathbb{Z}_p^*

  1. 순환군(Cyclic group)이 된다. 즉 해당집합의 모든 원소에 대해 a\in\{0, ..., p-2\}a 를 사용하여 g^a 로 표현할 수 있는 g 가 존재한다. 여기서 g 는 생성자(Generator)이며 이 또한 해당 집합의 원소이다.

  2. 역원을 찾는 것이 매우 어렵다. 따라서 이산로그 문제를 풀기 어렵다고 여길 수 있다.

    p 가 충분히 크다면 g^a = h 를 만족하는 a 값을 찾기 어려워진다.

  3. 곱셈시 지수의 덧셈이 적용된다 g^a \cdot g^b = g^{(a+b)(mod\ p-1)}

    여기서 우리가 소수를 활용하는 이유는, 인수가 여러개일 때 곱셈 결과가 0이 될 수 있기 때문이다. 예를 들면 2 \cdot 2 (mod \ 4) = 0 인 상황이 있을 수 있다.

이산로그문제와 동형암호함수

E(x) = g^x (mod \ p)

즉 위와 같은 특성을 활용하여, 덧셈을 지원하는 동형암호함수를 만들 수 있다. 예를 들어 \mathbb{Z}_{p-1} 에 속하는 x 에 대하여 E(x) = g^x 라고 정의한다면,

  1. x\neq y 라면 g^xg^y 값은 서로 다르며,
  2. 주어진 E(x)=g^x 에 대해 x 값을 찾기 어렵고,
  3. E(x+y) = g^{x + y \ mod\ p-1} = g^x \cdot g^y = E(x) \cdot E(y) 이므로,

동형암호함수의 세 가지 조건을 모두 만족하게 된다.

Blind Evaluation

Blind Evaluation of Polynomial
: 다항식의 결과값을 다항식 없이 혹은 변수 없이 구하는 방법

유한체 \mathbb{F}_p

먼저 \{0, ..., p-1\} 까지 p 개의 요소를 가지는 유한체를 \mathbb{F}_p 라고 칭하고 덧셈 및 곱셈이 나머지 연산을 통해 이루어진다고 해보자.

d 차 다항식 P

유한체 \mathbb{F}_p 에 대한 어떤 d 차 다항식 P 는 다음과 같이 표현된다.

P(X) = a_0 + a_1 \cdot X + a_2 \cdot X^2 + ... + a_d \cdot X^d

여기서 a_0, ..., a_d \in{\mathbb{F}_p} 이다.

다항식과 선형 결합

어떤 점 s\mathbb{F}_p 에 속한다 해보자. 이때 다항식은 다음과 같이 생겨야 한다.

P(s) = a_0 + a_1 \cdot s + a_2 \cdot s^2 + ... + a_d \cdot s^d

여기서 s^0, s^1, ..., s^d 를 각각 벡터로 생각한다면 다음과 같이 표현할 수 있다.

s^0 = V_0, s^1 = V_1, s^d = V_d$

그럴 경우 다항식을 다음과 같이 a_0, ..., a_d 를 가중치(Weight factor)로 사용한 가중합으로 단순 선형결합(Linear combination) 결과물로 볼 수 있다.

P(s) = a_0 \cdot V_0 + a_1 \cdot V_1 + ... + a_d \cdot V_d

동형암호함수와 선형 결합

동형암호함수또한 선형 결합을 지원한다. 즉, a, b 가 주어지고 E(x)E(y) 를 알고 있다면 우린 E(ax+by) 를 계산할 수 있다. 계산 과정은 아래와 같다.

E(ax+by) = g^{ax+by} = g^{ax}\cdot g^{by} = (g^x)^a \cdot (g^y)^b = E(x)^a \cdot E(y)^b

Blind Evaluation 상황

Alice는 d 차 다항식 P 을 구성하는 계수를 알고 있는 상황이고 Bob은 s \in \mathbb{F}_ps 를 랜덤하게 선택한 상황. 즉, Bob은 다항식 없이 본인만 알고 있는 값을 넣었을 때의 결과값을 알고 싶은 상황이며, Alice는 Bob이 선택한 값 s 를 모르는 상태로, 은닉정보들(HH)을 토대로 결과값을 만들어 줘야하는 상황.

동형암호학 없이 E(P(S)) 를 구한다면?

  1. Alice가 Bob에게 P 를 보내주고 Bob이 알아서 계산하는 방법
    : d 가 사실 2,000,000에 달할 정도로 매우 크다. 따라서 Bob에게 P 를 알려주지 않는 더 간결한(Succinct, 'Succinct’NARKs) 방법이 있는 것이 좋다. 역설적으로 Bob이 알려주어야 하는 E(s^0), E(s^1), ..., E(s^d) 또한 매우 많다는 의미인데, 고정된 s 를 사용할 경우, 시스템에 하드코딩할 수 있으므로 문제가 되지 않는다.
  2. Bob이 s 를 Alice에게 보내주고 Alice가 E(P(S)) 를 계산하기
    : Alice에게 s 를 알려주지 않을 예정이므로, 애초에 옵션이 안됨.

동형암호학과 함께 E(P(S)) 를 구하기

  1. Bob은 E(s^0), E(s^1), ..., E(s^d) 를 만들어서 Alice에게 보낸다.
  2. Alice가 계산해야 하는 값은 E(a_0 \cdot s^0 + a_1 \cdot s^1 + ... + a_d \cdot s^d) 으로 위에서의 동형암호학을 위한 선형 결합 계산방법을 사용하여 결과를 만들어 낼 수 있다.
    E(P(s)) = E(s^0)^{a_0} \cdot E(s^1)^{a_1} \cdot ... \cdot E(s^d)^{a_d}
    그리고 이 결과를 Bob에게 전송해준다.

Alice가 s를 알아낼 가능성은?

E(s) 하나의 정보만으로 s 를 유추하기는 어렵더라도 E(s^0), ..., E(s^d) 까지 s 에 대해 더 많은 정보를 가지고 있는 상황이라면 s 를 더 쉽게 구해낼 수 있는 가능성이 존재한다. 이에 대해서 우리는 d 급수에 대한 디피-헬만 가정(d-power Diffie-Hellman assumption)에 의해 해킹되기 어렵다고 본다. d 급수에 대한 디피-헬만 가정은 다양한 SNARKs 보안 증명에 사용된다.

Alice가 다른 다항식 P’을 사용한다면?

여기서 Schwartz-Zippel Lemma에 의하면, 서로 다른 다항식은 거의 모든 점이 겹치지 않는다. 즉, SNARKs에서는 잘못된 다항식이 사용되면 제출하는 증명도 왠만하면 틀릴 것이므로 올바른 다항식을 가지고 있다는 사실을 확인해야만 한다.

KC 테스트(Knowledge of Coefficient Test)

KC Test(Knowledge of Coefficient Test)
: 올바른 다항식을 사용해 은닉값을 만들었음을 증명하기 위한 테스트

곱셈을 위한 유한체 \mathbb{F}_p^*

유한체 \mathbb{F}_p^*\mathbb{Z}_p^* 와 마찬가지로 \mathbb{F}_p 에서 0을 제외한 체(field)이다.

p 개의 원소를 가지는 순환군 G

\alpha \in \mathbb{F}_p\alpha 를 사용하여 생성자 g 를 가지는 순환군 G 에 대해 곱셈순환대신 덧셈순환을 진행한다. 즉 g^a\alpha \cdot g 도 대체하여 사용한다.

\alpha

순환군 G 에 속한 두 원소들의 쌍 (a, b)\mathbb{F}_p^* 에 속하는 \alpha 에 대하여 a,b\neq 0, b = \alpha \cdot a 를 만족하면 이를 \alpha -쌍이라고 부른다.

KC 테스트

  1. Bob이 \mathbb{F}_p^* 에 속하는 \alphaG 에 속하는 a 를 각각 임의로 지정하고 이로부터 b=\alpha \cdot a 를 계산한다.
  2. Alice에게 챌린지쌍 (a,b) 를 보낸다. 여기서 (a,b)\alpha 쌍이다.
  3. 앨리스는 또다른 \alpha 쌍인 (a^\prime, b^\prime) 을 만들어 응답한다. 앨리스는 현재 \alpha 를 모르는 상황이며, 이산로그문제로 인해 앨리스가 \alpha 를 알아내기는 어렵다. 따라서, \mathbb{F}_p^* 에 속하는 \gamma 를 하나 고른 뒤, (a^\prime, b^\prime) = (\gamma \cdot a, \gamma \cdot b) 를 계산하여 내보낸다.
  4. Bob은 Alice의 응답이 \alpha 쌍일 때에만 이를 받아들인다. \alpha 쌍인 것은 b^\prime = \alpha \cdot a^\prime 을 통해 쉽게 확인할 수 있다.

즉, 위 절차를 통해 Alice가 응답하는 과정에서 aa^\prime 사이의 비율인 \gamma 를 알고 있음을 공표할 수 있도록 할 수 있다.

KC 가정(Knowledge of Coefficient Assumption)

Alice가 Bob의 챌린지 쌍 (a,b) 에 대해 올바른 \alpha(a^\prime, b^\prime) 을 응답했다면 Alice는 a^\prime = \gamma \cdot a 를 만족하는 \gamma 를 알고 있다고 가정한다.

원래는 곱셈에 대해 쓰였기 때문에 Knowledge of Exponent Assumption이었으나 우리는 덧셈 연산으로 대체하므로 Coefficient가 되었음.

추출기(Alice’s Extractor)

Alice가 Bob의 챌린지 쌍 (a,b) 에 대해 올바른 \alpha(a^\prime, b^\prime) 을 응답했다면 Alice의 추출기(extractor)는 a^\prime = \gamma \cdot a\gamma 를 내어놓는다.

Verifiable Blind Evaluation

  1. Blindness
    : Alice는 s 값을 모르고, Bob은 P 를 모른다.
  2. Verifiability
    : Alice가 d 차수의 특정 다항식 P 를 사용하지 않고 E(P(S)) 를 만들어 보냈을 때, Bob이 이를 수용하는 상황은 매우 드물다.

An Extended KCA

d 개의 계수에 대해 KC를 진행하기 위해 다음과 같이 KCA를 확장해볼 것이다. 기존에는 \alpha 쌍을 하나만 보냈지만, 이번에는 Bob이 총 d 개의 \alpha(a_1, b_1), ..., (a_d, b_d) 을 만들어서 Alice에게 보낸다.

또한 여러개의 \alpha 쌍을 받았으므로, 하나의 \gamma 만 사용하는 것이 아니라 여러 값을 사용할 수 있다. 예를 들어 c_1, c_2 \in \mathbb{F}_p^* 인 두 값을 고를 경우 (a^\prime, b^\prime) = (c_1 \cdot a_1 + c_2 \cdot a_2, c_1 \cdot b_1 + c_2 \cdot b_2) 으로 계산할 수 있다.

b^\prime = c_1 \cdot b_1 + c_2 \cdot b_2 = c_1\alpha \cdot a_1 + c_2\alpha \cdot a_2 = \alpha(c_1\cdot a_1 + c_2 \cdot a_2) = \alpha \cdot a^\prime

위 원리를 활용하여, d 개의 c_1, ..., c_d \in \mathbb{F}_p 를 고르고 (a^\prime, b^\prime) 를 다음과 계산한다.

(a^\prime, b^\prime) = (\Sigma_{i=1}^d c_ia_i, \Sigma_{i=1}^d c_ib_i)

이 프로토콜을 사용하면 Alice가 a^\prime 을 만들기 위해 사용한 c_1, ..., c_d 를 알고 있다고 가정할 수 있게 된다. 이를 확장 KCA(Extended KCA)라고 한다.

d-KCA

순환군 G에서 d급수에 대한 KC 가정(d-power Knowledge of Coefficient Assumption, d-KCA, in Group G)은 다음과 같다.

  • Bob은 \mathbb{F}_p^* 에 속하는 어떤 값 \alpha\mathbb{F}_p 에 속하는 변수값 s 를 선택한 뒤 다음과 같이 \alpha 쌍을 만들어 Alice에게 보냈다.
    • (s^0 \cdot g, \alpha s^0 \cdot g), (s^1 \cdot g, \alpha s^1 \cdot g), ..., (s^d \cdot g, \alpha s^d \cdot g)
  • Alice는 Bob에게 받은 값들을 바탕으로 새로운 \alpha 쌍을 만들어서 보낸다.
  • 그렇다면 Alice가 \Sigma_{i=0}^d c_is^i \cdot g = a^\prime 을 만족하는 c_0, ..., c_d \in \mathbb{F}_p 를 알고 있다고 볼 수 있다.

Verifiable Blind Evaluation Protocol

순환군 G 의 생성자 g 에 대한 동형암호함수 E(x) = x \cdot g 에 대하여 다음과 같이 프로토콜을 정의할 수 있다.

  1. Bob은 은닉값 s^0 \cdot g, s^1 \cdot g, ..., s^d \cdot g\alpha\alpha s^0 \cdot g, \alpha s^1 \cdot g, ..., \alpha s^d \cdot g 또한 Alice에게 보낸다.
  2. Alice는 a^\prime = P(s) \cdot gb^\prime=\alpha P(s) \cdot g\alpha(a^\prime,b^\prime) 을 만들어 Bob에게 다시 보내준다.

    다항식 P 에 대한 계수들이 주어졌을 때, P(s)\cdot g 는 그 계수들과 g, s\cdot g, ..., s^d\cdot g 의 선형결합이고 \alpha P(s)\cdot g 는 그 계수들과 \alpha g, \alpha s\cdot g, ..., \alpha s^d\cdot g 의 선형결합이다.

  3. Bob은 b=\alpha \cdot a 인지 확인한다. 그럼 d-KCA에 따라, Alice는 다항식의 계수를 모두 알고 있다고 확신할 수 있다.

조건문을 다항식들의 집합으로(QAP)

  1. 아이디어의 시작 - Lund, Fortnow, Krloff and Nisan
  2. QAP의 등장 - Gennaro, Gentry, Parno and Raykova

예시를 들어 생각해보자. Alice가 Bob에게 다음 조건문

" (c_1 \cdot c_2)\cdot(c_1 + c_3) = 7 을 만족하는 c_1, c_2, c_3 \in \mathbb{F}_p 를 알고있음"

이 '참’임을 Bob에게 증명하고자 하는 상황이라 가정해보자. 우리는 이 조건문을 다항식들의 집합으로 표현해낼 수 있다. 이렇게 표현된 다항식들의 집합을 이차산술프로그램(QAP, Quadratic Arithmetic Program) 으로 부른다.

Arithmetic Circuits 만드는 방법

덧셈과 곱셈연산을 할 수 있는 선과 게이트로 구성된 회로를 다음처럼 만들 수 있다.

Arithmetic Circuit Diagram

input wire: w_1, w_2, w_3
output wire: w_5

  1. 와이어가 하나 이상의 게이트로 들어갈 경우, 모두 동일한 하나의 와이어로 생각한다. 이 예시에서는 w_1
  2. 곱셈게이트는 반드시 두 개의 인풋 와이어를 가지고 있고 좌,우로 구분한다.
  3. 덧셈게이트에서 곱셈게이트 혹은 덧셈게이트로 이동하는 와이어는 숫자를 매기지 않는다. 이는 덧셈 게이트로 들어간 인풋이 어차피 바로 곱셈 게이트까지 연결되기 때문이다. 이 예시에서는 덧셈게이트의 인풋 와이어로 들어온 w_1,w_3 가 곱셈게이트 g_2 의 우측 인풋이 된다.

Legal assignment

Legal assignment란 라벨링된 와이어들에 할당된 값들이다. 즉, 곱셈 게이트에서 해당 인풋들의 곱셈으로 출력되어 나온 값들이다. 현재 예시상황에서 현 회로의 legal assignment(c_1, ..., c_5) 이고, 이 값들은 c_4 = c_1 \cdot c_2 그리고 c_5 = c_4 \cdot (c_1 + c_3) 를 만족한다.

즉, Alice가 증명하고 싶은 것은

" c_5=7 을 만족하는 legal assignment (c_1, ..., c_5) 를 알고 있다는 것"

이다. 이제 QAP를 통해 이 조건문을 다항식으로 변경해보자.

Circuit으로부터 QAP를 만들어 내기

준비작업

  1. 곱셈게이트의 개수에 맞춰 타겟포인트를 지정한다. 여기에선 \{1, 2\} 를 타겟 포인트로 지정한다.

  2. 모든 곱셈 게이트를 타겟포인트와 묶어준다. 여기에선 게이트 \texttt{g}_11 \in \mathbb{F}_b 과 묶고, 게이트 \texttt{g}_22 \in \mathbb{F}_b 와 묶는다.

  3. 좌측와이어 다항식은 L_1, ..., L_5 로 정의하고 우측와이어 다항식은 R_1, ..., R_5 로 아웃풋와이어는 O_1, ..., O_5 로 정의한다.

곱셈게이트마다 다항식을 만들기

곱셈 게이트마다 다항식을 만든다. 다항식을 만들 때에는 해당 게이트의 대응되는 타겟 포인트를 대입하면 값이 1이 되도록하고, 다른 타겟 포인트를 대입하면 값이 0이 될 수 있도록 만든다.

곱셈게이트 \texttt{g}_1 에서의 다항식들간의 관계

예를 들어 게이트 \texttt{g}_1 에 대하여 해당되는 타겟 포인트인 1 을 대입하면 값이 1 이 될 수 있도록 하고 다른 타겟 포인트인 게이트 \texttt{g}_2 의 타겟포인트 값 2 를 대입할 경우 결과가 0이 되도록 한다면 다항식은 2-X 가 되어야 한다. 그리고 게이트 \texttt{g}_1 의 각각 좌측, 우측, 출력 와이어인 와이어 \texttt{w}_1, \texttt{w}_2, \texttt{w}_4 에 대응되는 다항식 L_1, R_2, O4 의 값을 타겟포인트를 활용해 만든 다항식 2 - X 로 할당해준다.

L_1 = R_2 = O4 = 2 - X

곱셈게이트 \texttt{g}_2 에서의 다항식들간의 관계

마찬가지로, 게이트 \texttt{g}_2 에 대해서는 해당 타겟 포인트인 2 을 대입하면 값이 1 이 될 수 있도록 하고 다른 타겟 포인트인 게이트 \texttt{g}_1 의 타겟포인트 값 1 을 대입할 경우 결과가 0이 되도록 한다면 다항식은 X-1 이 되어야 한다. 이 상황에 대해서도 마찬가지로 게이트 \texttt{g}_2 의 각각 좌측, 우측, 출력 와이어인 와이어 \texttt{w}_4, (\texttt{w}_1, \texttt{w}_3), \texttt{w}_5 에 대응되는 다항식 L_4, R_1, R_3, O5 의 값을 X - 1 로 할당해주자.

L_4 = R_1 = R_3 = O5 = X - 1

정의되지 않은 다항식들은?

그럼 다항식 L_3 등은 정의되지 않았는데 어떻게 해야 하나? 위 과정을 통해 정의되지 않은 다항식들은 모두 값이 0이다.

좌합,우합,출력합을 이용한 최종 다항식과 Legal assignment

이제 주어진 고정된 값들인 (c_1, ..., c_5) 를 다항식들의 좌합,우합,출력합을 정의하는 것에 사용해보자.

즉,

L := \Sigma_{i=1}^5 c_i \cdot L_i, R := \Sigma_{i=1}^5 c_i \cdot R_i, O := \Sigma_{i=1}^5 c_i \cdot O_i

그리고 최종 다항식은 다음과 같이 표현한다.

P:=L\cdot R - O

의미적으로 생각해본다면, 곱셈게이트의 좌측 와이어와 우측와이어의 곱을 아웃풋 와이어로 빼 결론적으로는 값이 0을 만들기 위한 방법이다.

이 최종다항식 " P 가 모든 타겟 포인트에서 0이 된다"는 것은 " (c_1, ..., c_5) 가 해당 Circuit에 대한 Legal assignment"라는 것과 서로 필요충분조건이다.

Target point에서의 테스트

모든 좌측 다항식 L_i 들 중에서 L_11 에서 값이 0이 되지 않는다. 따라서 L(1) = c_1 \cdot L_1(1) = c_1 이 된다. 이와 마찬가지로 R(1) = c_2 이며, O(1)=c_4 이다.

따라서 P(1) = c_1 \cdot c_2 - c_4 가 되며, 같은 과정을 거치면 P(2) = c_4 \cdot(c_1+c_3) - c_5 가 된다.

즉, 모든 타겟 포인트 상에서 P를 0으로 만들기 위해서는 (c_1, ..., c_5) 가 Legal assignment 이어야만 가능하다.

주어진 값을 근으로 가지는 방정식

주어진 다항식 P 에 대하여 유한체 \mathbb{F}_p 에 속하는 점 a 가 있을 때, P(a)=0 가 되기 위해서는 반드시 다항식 PX-a 의 배수여야 한다. 다시 말해 어떤 다항식 H 가 있으면 P = (X-a) \cdot H 이다.

타겟 다항식 T(X) 만들기

위에서처럼 주어진 값을 근으로 가지는 함수를 만들어 다음과 같이 타겟 다항식으로 정의하자

T(X) := (X-1)\cdot(X-2)

즉 위 타겟 다항식은 X1 일 때와 2 일 때 모두 0이 되므로, TP 의 약수이면 (c_1, ..., c_5) 가 Legal assignment임은 서로 필요충분 조건이 된다.

QAP의 정의

  1. m 사이즈의 d 차 QAP(Quadratic Arithmetic Program) 프로그램 Q 는 다항식 L_1, ..., L_m, R_1, ..., R_m, O_1, ..., O_m 으로 구성되어 있다.
  2. L := \Sigma_{i=1}^m c_i \cdot L_i, R := \Sigma_{i=1}^m c_i \cdot R_i, O := \Sigma_{i=1}^m c_i \cdot O_i 이고 P:=L\cdot R - O 일 때, 다항식 P 에 대한 타겟 다항식 T 가 있다면 Assignment (c_1, ..., c_5)Q 를 만족한다고 표현한다.

즉 Alice에게는 주어진 QAP를 만족하며 c_5 = 7 인 할당값 (c_1,...,c_5) 을 알고 있음을 증명할 방법이 생겼다.

QAP의 검증

QAP를 만족한다면 P = H \cdot T 를 만족하는 H 가 있어야 한다. 즉, \mathbb{F}_p 에 속하는 모든 점에 대해 P(s) = H(s)\cdot T(s) 를 만족해야 한다.

잘못된 assignment (c1,...,c5) 을 사용한다면?

“잘못된 assignment 사용해 L, R, O, P 를 만든다”
\iff
" TP 를 나눌 수 없다."
\iff
" H 가 어떤 다항식이 되더라도 PL, R, O, H 는 모두 다른 다항식이다. (단, P 는 최대 2(d-1) 차 다항식이며 L,R,O 는 최대 d-1 차, H 는 최대 d-2 차 다항식이다.)"

슈바르츠-지펠 보조정리(Schwartz-Zippel Lemma)

슈바르츠-지펠 보조정리에 따르면, 최대 2d 차를 가지는 서로 다른 두 다항식은 최대 2d 개의 점 s \in \mathbb{F}_p 에서 만나게 된다. 즉, p2d 에 비해 매우 크다면 (p >> 2d) , 무작위로 s \in \mathbb{F}_p 를 뽑아서 P(s)=H(s)\cdot T(s) 를 만족하게 만들기 매우 어려워진다.

피노키오 프로토콜 - 1: QAP의 검증

  1. Alice는 최대 d 차수의 다항식 L,R,O,H 를 고른다.
  2. Bob은 \mathbb{F}_p 에 속하는 랜덤한 점 s 를 고른 뒤 E(T(s)) 를 계산한다.
  3. Alice는 각 다항식이 점$ s$ 에서 가지는 값을 계산한 뒤 은닉값들 E(L(s)), E(R(s)), E(O(s)), E(H(s)) 보낸다. 이는 위에서 설명된 Blind Evaluation을 통해 가능하다.
  4. Bob 또한 Alice가 보낸 값들로 동형계산을 진행하여 E(L(s)\cdot R(s) - O(s)) = E(T(s) \cdot H(s)) 가 맞는지 확인한다.

이 과정을 통해 Alice는 어떤 다항식을 사용하는지 Bob이 정한 임의의 s 에 대해 증명하여 알려준 상황이 되었다.

QAP에 대한 d-KCA

하지만, Alice가 P = L\cdot R - O = T \cdot H 를 만족하는 다항식 L,R,O 는 못찾더라도 위 공식을 만족하는 어떤 값들을 찾아낼 수 있다. 즉, Legal assignment를 사용하지 않고도 위 공식을 통과할 수 있다. 따라서 Alice가 넘겨주는 다항식들이 (c1,...,c_m) 으로부터 만들어짐을 강제할 필요가 있다. 우리는 여기서 d-KCA와 formal proof를 이용해 Legal assignment가 부분다항식들과 선형결합되도록 한다.

L, R, O 와 Assignment의 선형결합

F 의 정의

먼저 L, R, O 를 하나의 다항식에 녹여내기 위해 다항식 F 를 다음과 같이 정의해보자.

F = L + X^{d+1} \cdot R + X^{2(d+1)}\cdot O

F 의 특성

그럼 다음과 같은 성질이 생긴다.

  • RX^{d+1} 과 곱해주고 OX^{2(d+1)} 과 곱해줌으로써 F 를 구성하는 L, R, O 의 계수들은 서로 다른 상황이 되었다.
  • 다항식 FX 에 대한 계수들 중 1, X, ..., X^d 에 대한 계수들은 정확히 L 의 계수들이고 X^{d+1}, ..., X^{2d+1} 에 대한 계수는 정확히 R 의 계수들이다. 그리고 나머지 d+1 개의 계수들은 O 의 계수들이다.

F 의 선형 결합

QAP를 위한 다항식 구성을 위해 i \in \{1, ..., m\} 에 대해 F_i 를 만들면 다음과 같이 된다.

F_i = L_i + X^{d+1} \cdot R_i + X^{2(d+1)}\cdot O_i

두 개의 F_i 를 더하면 L_iL_i 끼리, R_iR_i 끼리 더해진다.

F_1 + F_2 = (L_1 + L_2) + X^{d+1} \cdot (R_1 + R_2) + X^{2(d+1)}\cdot (O_1 + O_2)

이 상황에서 Weight factor로 주어진 (c1, ..., c_m) 을 활용해 선형결합 값을 만들면 다음과 같이 된다.

F = \Sigma_{i=1}^m c_i \cdot F_i

같은 Assignment로 선형결합되는 L,R,O

F = \Sigma_{i=1}^m c_i \cdot F_i = \underbrace{(\Sigma_{i=1}^m c_i \cdot L_i)}_{L} + X^{d+1} \cdot \underbrace{(\Sigma_{i=1}^m c_i \cdot R_i)}_R + X^{2(d+1)} \cdot \underbrace{(\Sigma_{i=1}^m c_i \cdot O_i)}_O

즉 다항식 FF 의 선형결합에 사용된 것과 같은 (c1, ..., c_m) 로 만들어진 L_i, R_i, O_i 의 선형결합 결과 L, R, O 를 포함하게 된다.

피노키오 프로토콜 - 2: Legal assignment 선형결합 검증

  1. Bob이 \beta \in \mathbb{F}_p^* 를 고르고 Alice에게 은닉값 E(\beta \cdot F_1(s)), ..., E(\beta \cdot F_m(s)) 을 만들어 보낸다.
  2. Alice는 받은 은닉값과 보유하고 있는 (c1,...,c_m) 을 사용한 선형결합 결과물의 은닉값 E(\beta \cdot F(s)) 를 Bob에게 보낸다.
  3. Bob은 Alice에게 받은 E(L(s)), E(R(s)), E(O(s))\beta 를 활용해 E(\beta \cdot F(s)) 를 독자적으로 계산해본 뒤, 이게 Alice가 보내준 값과 값과 같은지 확인해본다.
  4. 즉 Bob은 확장 KCA를 통해 제대로된 선형결합이 진행된 것을 추가로 확인했다.

피노키오 프로토콜 논문

피노키오 프로토콜 - Parno, Howell, Gentry, Raykova

Alice의 Assignment를 유추해볼 수 있을까?

QAP를 만족하는 새로운 Assignment를 Bob이 만들어낼 경우 (c_1^\prime, ..., c_m^\prime) , 해당 Assignment를 사용해 Bob은 E(L^\prime(s)), E(R^\prime(s)), E(O^\prime(s)), E(H^\prime(s)) 를 구할 수 있다. 그리고 이 결과값이 Alice가 보내주는 값과 다르다면 적어도 Alice의 (c1,...,c_m)(c_1^\prime, ..., c_m^\prime) 와는 다르다는 것은 알 수 있다.

Assignment 은폐하기

\mathbb{F}_p^* 에 속하는 랜덤한 세 숫자 \delta_1, \delta_2, \delta_3 를 고른 다음 각각의 다항식에 랜덤티셔츠(random T -shirt)라는 이름으로 더한다.

L_z := L + \delta_1 \cdot T\\ R_z := R + \delta_2 \cdot T\\ O_z := O + \delta_3 \cdot T

여기서 L\cdot R - O = T \cdot H 를 만족하는 상황이라고 했을 때,

L_z \cdot R_z - O_z = (L + \delta_1 \cdot T) \cdot (R + \delta_2 \cdot T) - (O + \delta_3 \cdot T) \\= \underbrace{(L\cdot R - O)}_{T\cdot H} + L\cdot (\delta_2 \cdot T) + (\delta_1 \cdot T) \cdot R + \delta_1\delta_2\cdot T^2- \delta_3 \cdot T \\= T\cdot \underbrace{(H + L \cdot\delta_2 + \delta_1\cdot R + \delta_1\delta_2 \cdot T - \delta_3)}_{H_z} \\= T \cdot H_z

즉, 위와 같이 랜덤티셔츠를 더해서 보내면 Bob이 자세한 내용을 유추하는 것을 막을 수 있다.

혹시 T 가 0이 되면, 랜덤티셔츠를 무용지물로 만들 수도 있다 T(s) 는 최대 d 개 값에 대해서만 0이 될 수 있는데, 이를 제외한 값들을 선택해 T(s)\neq 0s 를 사용하도록 해야 한다.

곱셈지원 동형암호학의 필요성

Bob이 E(H(s)\cdot T(s))E(H(s))E(T(s)) 로 부터 알 수 있으려면 곱셈을 지원하는 동형암호학이 필요하다. 이를 위해 타원곡선암호학을 사용한다.

타원곡선 암호학

자세한 타원곡선 암호학은 다음 시리즈를 참조하면 좋다.

  1. Elliptic Curve Cryptography: a gentle introduction
  2. Elliptic Curve Cryptography: finite fields and discrete logarithms
  3. Elliptic Curve Cryptography: ECDH and ECDSA
  4. Elliptic Curve Cryptography: breaking security and a comparison with RSA

타원곡선을 이루는 점들

먼저, 우리가 사용할 타원곡선을 정의해보자.

4u^3 + 27v^2 \neq 0 를 만족하는 유한체에 속하는 두 수 u,v \in \mathbb{F}_p 를 선택하고 이들을 계수로 하여 타원곡선을 만들면 다음과 같다.

Y^2 = X^3 + u\cdot X + v

여기서 타원곡선 \mathcal{C} 는 위 방정식을 만족하는 점 (x,y) \in \mathbb{F}_p^2 들의 집합이다. 이 타원곡선은 특수하게 설정한 무한영점(point at infinity) \mathcal{O} 를 포함한다.

타원곡선상의 점들에 대한 덧셈 연산

타원곡선상의 점들에 대한 덧셈에 대해서 다음과 같은 기하학적 조건을 추가해보자.
"타원 곡선$ \mathcal{C} 과 어떤 직선 \mathcal{L}$ 이 만나는 점에 있는 모든 점들의 합은 무한 영점이다."

그렇다면, 직선 \mathcal{L}\mathcal{C} 와 두 점 P, Q 에서 만난다면,

P + Q = \mathcal{O}

직선 \mathcal{L}\mathcal{C} 와 세 점 P, Q, R 에서 만난다면,

P + Q + R = \mathcal{O}

이 된다.

타원곡선상의 점들에 대한 덧셈 예시

위 조건을 가지고 있을 때, 몇 가지 예시를 살펴보자.

덧셈의 역원

P+Q=0

두 점에서 만나는 상황이므로 P+Q = \mathcal{O} 이며, 이에 따라 P = - Q 이다. 이 것은 PQ 의 덧셈에 대한 역원임을 의미한다. 값은 각각 P=(x_1, y_1), Q = (x_1, -y_1) 이다.

타원 곡선상에서 서로 다른 x 값을 가지고 있는 두 점을 골랐을 때,

이 때 두 점을 P, Q 라고 하고 연장선을 그을 경우 곡선과 만나는 또 하나의 점을 R 이라 해보자.

x_1 \neq x_2 이므로 무조건 또 다른 R 이 존재한다.

이 때는 위의 조건에 따라서 P + Q + R = \mathcal{O} 가 된다. 즉 P + Q = -R 이며 -RR 의 역원에 해당한다.

P+Q 의 값을 기하학적으로 쉽고 빠르게 찾을 수 있다.

그룹 G_1

위와 같은 특성을 만족하는 타원곡선상의 점의 집합들을 \mathcal{C}(\mathbb{F_p}) 으로 표현할 수 있는데, 앞으로 편의상 이를 G_1 으로 쓴다. 그룹을 더 단순하게 만들기 위해 G_1 에 포함된 요소의 수가 총 r 개라면 rp 와는 다른 소수가 되도록 한다. 그렇다면 \mathcal{O} 를 제외하고 G_1 에 속하는 모든 요소 g \in G 는 생성자가 되어 G_1 을 만들어낼 수 있다.

Embedding degree

(p^k - 1)r 의 배수가 되도록 하는 가장 작은 k 를 이 타원곡선의 Embedding degree라고 한다. 우리는 k 가 너무 작지 않다면 (예를 들면 6 정도) 그룹 G_1 에 대해 \alpha \cdot gg 를 통해 \alpha 를 찾아내는 이산로그문제가 매우 어려운 것으로 본다.

ZCash의 BN 커브는 k 가 12

서브그룹 G_1G_2

\mathbb{F}_{p^k} 에서의 곱셈군은 r 차수의 서브그룹 G_T 를 가진다. 이에 따라 타원곡선상의 점들을 기존의 \mathbb{F_p} 의 영역에서 \mathbb{F}_{p^k} 의 영역으로 확장했을 경우, 상기의 덧셈 규칙에 따라 이 유한체에 속하는 점들 또한 당연히 무한영점 \mathcal{O} 를 포함하는 타원곡선 \mathcal{C}(\mathbb{F}_{p^k}) 를 구성하게 된다. 그리고 이 타원곡선 \mathcal{C}(\mathbb{F}_{p^k})G_1 을 반드시 포함하게 된다. G_1 과 별개로, \mathcal{C}(\mathbb{F}_{p^k}) 는 또다른 서브그룹 G_2 또한 포함하는데 그룹 G_2 의 차수 또한 r 이다.

정확히는 r 차수인 서브그룹이 r-1 개 더 존재한다.

곱셈에 대한 동형암호학: Tate reduced pairing

두 서브그룹에 대한 생성자 g \in G_1, h \in G_2 를 고정하자. 그러면 G_1 , G_2 에서의 요소를 타겟 서브 그룹 G_T 에 효과적으로 매핑할 수 있다. 이 매핑을 Tate reduced pairing으로 부른다.

즉,

  1. G_T 의 생성자인 \textbf{g}\text{Tate}(g,h) = \textbf{g} 오 같이 Tate함수를 사용해 구하자.
  2. 그럴 경우 a,b \in \mathbb{F}_r 에 대해 \text{Tate}(a\cdot g,b\cdot h) = \textbf{g}^{ab} 가 되므로 G_1 에 속한 원소와 G_2 에 속한 원소를 이용해 G_T 에 속하는 원소를 만들어낼 수 있다.

ZCash는 Tate reduced pairing 대신 Optimal Ate Pairing을 사용한다.

Tate함수는 다음과 같이 정의할 수 있다. Tate 함수의 자세한 내용은 다루지 않음:

a \in \mathbb{F}_p 에 대한 다항식$ (X-a)^r$ 은 ar 중근으로 가지며 이 근이 유일한 해다.
G_1 에 속하는 점 P \in G_1 이 있다면, 인수정리에 따라서

  1. 유한체 \mathbb{F}_p 에서의 타원곡선 상에서, P 를 유일해이며 r 중근으로 가지는 \mathcal{f}_P 가 존재
  2. 이 때, \text{Tate}(P,Q) = \mathcal{f}_P (Q)^{(p^k-1)/r}

덧셈과 곱셈을 모두 지원하는 동형암호함수 E

E_1(x):= x \cdot g, E_2(x) := x\cdot h, E(x) := x \cdot \textbf{g} ,로 정의하면 E_1(x),E_2(y) 가 주어질 경우 Tate reduced pairing을 통해 E(xy) 를 계산할 수 있다.

x, y에 대한 은닉값으로 xy의 은닉값은 계산할 수 있으나 x,y,z에 대한 은닉값만가지고 xyz의 은닉값을 계산할 수는 없다.

Non-interactive system 만들기 S"Non-interactive"ARKs

가장 Non-interactive한 시스템을 만들어본다면?

  1. Alice의 주장을 Bob이 검증하려고 할 때, Bob이 사전 통신 없이 메세지를 만들어서 이를 모두에게 공개 게시한다.
  2. Alice는 공개 메세지를 보고 증명을 만들어서 Bob에게 보낸다.
  3. Bob의 공개 메세지를 아는 모든 사람은 Alice의 주장이 맞는지 모두가 확인할 수 있다.

하지만, 계산복잡도 이론에 따라 이 방법은 현실적으로 불가능하다.

CRS(Common reference string)

증명이 만들어지기 전, 어떤 무작위적인 절차를 통해 생성되어 모든 참가자들에게 알려지는 셋업 문구(CSR)를 활용하는 시스템을 사용하면 완벽한 Non-interactive는 아니지만 어느정도 비상호교류적인 시스템을 만들 수 있다.

여기에서 중요한 가정은 CRS를 생성하는 것에 이용된 랜덤값들이 어떤 사람들에게도 알려지지 않았다는 것이다. 이 랜덤값들이 알려지면 거짓증명을 마음대로 만들어낼 수 있게 된다.

ZCash는 다자간 계산 세레모니, Powers of Tau를 통해 CRS를 만들었다.

Non-interactive evaluation protocol

Setup

Blind Evaluation에서 사용되는 은닉된 값들을 CRS로 사용한다. 이 CRS를 만들기 위해
\alpha \in \mathbb{F}_r^*, s \in \mathbb{F}_r 을 무작위적으로 뽑는다. 그 경우 CRS는
(E_1(1), E_1(s), ..., E_1(s^d), E_2(\alpha), E_2(\alpha s), ..., E_2(\alpha s^d)) 가 된다.

Proof 제작

E_1, E_2 가 각각 선형결합을 지원하므로 Alice는 공표된 값을 토대로 a = E_1(P(s)) 그리고 b = E_2(\alpha P(S)) 를 만든다.

검증하기

a=E_1(x), b = E_2(y) 를 만족하는 x,y \in \mathbb{F}_r 가 있을 경우, Bob은 Alice에게 받은 값들과 \text{Tate} 함수를 사용하여

E(\alpha x) = \text{Tate}(E_1(x), E_2(\alpha)) = \text{Tate}(a, E_2(\alpha))\\ E(y) = \text{Tate}(E_1(1), E_2(y)) = \text{Tate}(E_1(1), b)

를 계산한다. 그리고 두 값이 같은지 확인해본다.

이제 이전의 Interactive한 상황과 비교했을 때, Bob이 \alpha 값을 알기 위해 미리 Alice와 통신할 필요가 없어졌다. 따라서 첫번째 메세지를 주기위해 Alice에게 먼저 값을 받을 필요 없이 CRS에 해당 메세지를 박제해두면 된다.

요약

  1. Alice는 특정 조건(방정식)을 만족하는 해(Legal assignment)를 가지고 있으며 그 조건을 산술회로로 만들 수 있다. 또한 산술회로는 Alice와 Bob에게 모두 공유된다.

  2. 산술회로를 만들었을 때 이 산술회로에서 좌입력, 우입력, 출력 다항식 L, R, O, P 를 도출해낼 수 있고 이 다항식들의 집합을 QAP라고 한다.

  3. 여기서 다항식 P = L\cdot R - O 는 타겟다항식 T 를 인수로 가지는 특징이 있다.

  4. Bob은 임의의 숫자 s 를 정해 Alice가 이야기한 타겟다항식 T 에 대해 E(T(s)) 를 보내준 뒤, Alice에게 다음과 같이 말한다.

    “너가 정말 이 조건을 만족하는 해를 가지고 있다면, 내가 보낸 E(T(s)) 를 사용해 E(L(s)\cdot R(s) - O(s)) = E(T(s) \cdot H(s)) 를 만족하는 E(L(s)), E(R(s)), E(O(s)), E(H(s)) 값들을 계산해서 나에게 줘볼래? 너가 가지고 있는 해를 모두 활용해서 선형결합한 결과를 만들어내면 저 값들이 당연히 조건을 만족하게 될거야. 그렇다면 난 너가 올바른 해를 가지고 있다고 확신할 수 있어.”

  5. 하지만, Bob은 이내 Alice가 Legal assignment를 선형결합한 결과물이 아닌 다른 P = L\cdot R - O = T \cdot H 를 찾아내서 보낼 수 있다는 사실을 깨달았다. 그래서 선형결합을 제대로 했는지 확실하게 하기위해 추가 요청을 했다.

    “미안한데, 너가 가진 Legal assignment는 m 개로 구성되어 있지? 우리가 알고 있는 다항식들과 너가 가지고 있는 Assignment를 선형결합한 다항식 F 를 계산해서 보내줘봐. 계산은 내가 임의의 \beta 를 골라서 m 개의 부분 F 함수에 대해 은닉값들을 만들어 보낼테니 이 값들을 활용해서 만들어줘. 너가 응답해준 F(s) 의 계산 결과물이 너가 좀 전에 은닉해서 보내준 L, R, O 값을 활용해서 내가 계산한 결과와 일치한다면 너가 내게 보내준 L,R,O 가 올바르게 선형결합되었다는 것을 믿을 수 있을 것 같아”

  6. Alice는 Bob의 요구에 순순히 응하지만 정보를 누출하지 않기 위해 랜덤티셔츠를 추가한 은닉값 E(L_z(s)), E(R_z(s)), E(O_z(s)), E(H_z(s)) 와 선형결합을 보장하는 은닉값 E(\beta \cdot F(s)) 를 계산해서 Bob에게 넘겨준다.

  7. 이번에는 Bob이 동형암호화 과정에 문제가 없었는지 확인할 필요가 있다고 느끼게 되었다. 그래서 보내준 은닉값들이 임의의 \alpha 값에 대해서 동형 성질을 만족하는지 확인하기로 했다. 이에 따라 계수 테스트를 진행하기로 하였는데 Bob이 계수 테스트에 사용되는 \alpha 값을 몰라도 된다면 Interactive하게 동작해야 하는 성질을 완전히 없앨 수 있다는 사실을 알게 되었다. 이에 따라 타원곡선 상에서 Tate함수를 사용해 곱셈을 재정의하여 덧셈과 곱셈이 모두 지원하는 동형암호함수를 사용한다.

  8. Non-interactive하게 서로 값을 주고 받기 위해 ZCash의 세레모니를 통해 생성된 CRS값들을 활용한다.


Todos

zk-SNARKs를 이해하는 것에는 매우 많은 개념들을 이해해야 합니다. 이에 따라서 이 개념들에 대한 쉽고 자세한 설명의 우리말 버전을 계속 업데이트 해나가는 것이 필요합니다. 이 과정에 많은 도움을 부탁드립니다. 특히 단순 번역보다는 수학적으로 자세하게 이해한 뒤, 우리 언어로 이해하기 쉽게 옮겨야 합니다. 본 글 또한 부족한 점이 많이 있습니다. 따라서 쉽게 설명되지 않았다고 느껴지는 파트가 있다면 이해하기 쉽도록 바꿔주시면 좋겠습니다.

코멘트를 통해 남겨주시는 내용들을 지속적으로 업데이트하도록 하겠습니다.


추가 아티클

2 Likes

굿굿!! 감사히 볼게요! 고생해주셔서 감사해요!

2 Likes

zk-SNARKs에 친화적인 타원암호학 Twisted Edward Curve와 Jubjub에 관한 내용입니다.

간단하게 요약하면 아래와 같습니다.

SHA256은 zk-SNARKs에 친화적이지 못하다

  • 현재의 ZCash는 MAC 스키마, PRF, 커밋스키마에 대해 SHA256 해쉬함수에 의존하고 있음.
  • 문제는 SHA256 연산의 대부분은 boolean 연산이며 zk SNARK 써킷에 친화적이지 못함. zk-SNARKs 써킷에서 사용되는 변수는 모두 큰 값을 지닌 소수 field여야하기 때문임.
  • 이에 따라 SHA256은 수만개의 곱셈 게이트를 가져야하고 이로 인해 증명에 필요한 비용이 크게 상승함.
  • 따라서 Pedersen commitment와 같이 큰 소수값을 적극적으로 활용하는 암호학을 사용하면 훨씬 좋을 것

그래서 어떻게 줄일 수 있는데?

  • Kosba를 포함한 연구원들은 zk-SNARKs써킷 상에서 고정된 및에 대한 지수연산을 스칼라값에 대해 6개의 제약 조건을 사용해 구현했음.
  • Jubjub을 사용해 4.2개로 줄였음.

Jubjub이 더 자세하게 뭔데?

  • Jubjub은 BLS12-381 필드(field, 체)상에서의 Twisted Edwards curve이고 식은 다음과 같음.
    -x^2 + y^2 = 1 + dx^2y^2,\\ d = - (10240/10241)
  • 덧셈곱칙을 완벽하게 만족함. 따라서 산술회로에서 사용되기 편리함.
    (x_1 + y_1) + (x_2, y_2) = \Big( \frac{x_1y_2 + y_1x_2}{1 + dx_1x_2y_1y_2}, \frac{1_1y_2 + x_1x_2}{1 - dx_1x_2y_1y_2} \Big)
  • 타원곡선상에서 연장선을 활용해 덧셈을 구하는 방식을 사용하기보다는 zk-SNARKs써킷에서 Field inversion이 field multiplication 만큼이나 저렴하다는 특성을 최대한 활용
  • 또한, 특정 상수에 대한 곱셈은 마치 고정된 밑에 대한 지수함수처럼 아주 저렴함.
  • b 에 대해 알려진 점 (x_2, y_2) 을 더하는 공식을 다음 5가지 조건으로 표현할 수 있다.
    • (x_1) \times (y_1) = (\beta)
    • (1 + dx_2y_2\beta) \times (x_3) = (x_1y_2 + y_1x_2)
    • (1 - dx_2y_2\beta) \times (y_3) = (y_1y_2 + x_1x_2)
    • (b) \times (x_3 - x_1) = (x_F - x_1)
    • (b) \times (y_3 - y_1) = (y_F - y_1)
  • 스칼라의 각 비트별로 boolean 조건을 추가해야하는데 251bit 스칼라에 대해서는 1506개의 곱셈 게이트를 가지므로 비트당 약 6 constraints라고 계산할 수 있음.
  • 이것보다 더 개선할 수 있음
    • windowed exponentation은 일반적인 포인트 합에 의존해야되므로 좀 더 비쌀 것
      • (x_1) \times (y_2) = (\beta)
      • (y_1) \times (x_2) = (\gamma)
      • (y_1) \times (y_2) = (\delta)
      • (x_1) \times (x_2) = (\epsilon)
      • (\delta) \times (\epsilon) = (\tau)
      • (1+d \tau) \times (x_3) = (\beta + \gamma)
      • (1-d \tau) \times (y_3) = (\delta + \epsilon)
      • 더해서 윈도우 테이블을 찾아보는 작업 + 각 스칼라 비트별로 boolean constraint를 확인
    • 그렇기 때문에 zk SNARKs 써킷안에서 상수에 관해 윈도우테이블을 찾아보는 일을 다항식을 통해 작업하면 더 싸지지 않나?
    • 예를 들어 상수값 세트 (c_0, c_1, c_2, c_3) 와 비트값 b_0 그리고 b_1 에 대한 윈도우 테이블이 있을 경우, 우리가 특정 값 r 을 선택할 경우 다음과 같이 됨.
      • (b_0) \times (- c_0 + c_0b_1 + c_1 - c_1b_1 - c_2b_1 + c_3b_1) = (r - c_0 + c_0b_1 - c_2b_1)
    • 이 방법을 더 큰 윈도우 테이블에도 그대로 적용할 수는 있지만 하지만 곱셈을 계산할 때 계산이 지수적으로 증가하는 문제가 있음. 따라서 4일 때 가장 적당한 윈도우 테이블이 나오고 이 것으로 비트당 약 4.2개의 제약조건을 만족시킬 수 있음.

zk SNARKs 친화적인 타원곡선암호학 Jubjub!

  • 이제 SHA256 대신 Pedersen commitment를 사용할 수 있음.
  • 난수 생성기로 만든 벡터 \vec{g}^n 의 비트값의 벡터 \vec{b}^n 에 대한 CRH를 \Pi^n {g_i}^{b_i} 로 정의하면 충돌방지 해쉬함수를 조금 더 저렴하게 얻을 수 있다.