재귀적 영지식 증명 이해하기

24 min readSep 2, 2022

Author

Co-founder & ZKP Researcher at Radius
Organizer at ZK-SEL
Twitter: https://twitter.com/Hyunxukee

영지식 증명은 블록체인 확장성을 위해 꼭 필요한 도구이지만 비싼 연산 도구이다. 블록체인에 영지식 증명을 도입하기 위해서는 연산 비용을 줄이는 방법을 반드시 고안해야한다. 재귀적 영지식 증명은 이러한 니즈를 충족하기 위한 최신 연구이며 현재 영지식 증명 시장에서 가장 깊게 고민되고 있는 분야라고 해도 과언이 아니다.
블록체인 세계에서 영지식 증명을 여행하고 있다면, 재귀적 영지식 증명을 꼭 익히길 바란다.

Recursion ZKP: 영지식 증명의 효율성을 높이는 도구

영지식 증명 구성하기

블록체인의 확장성 솔루션 중 하나인 영지식 증명은 비싼 연산 도구이다. 증명을 만드는 것부터 이를 검증하는 것까지 연산 비용이 많이 발생하는데, 연산 비용이 돈으로 환산되는 블록체인의 경우 이러한 비용 발생이 유저의 사용성에 악영향을 끼친다. 영지식 증명의 기능은 이미 블록체인에서 필요한 도구이기 때문에, 기능을 유지한 채 비용을절감하는 연구가 필수적이다. 오늘 소개할 재귀적 영지식 증명(recursion ZKP)도 이를 위한 연구 항목 중 하나이다.

재귀적 영지식 증명을 알아보기 전에 영지식 증명 알고리즘을 구성하는 방법에 대하여 간단히 알아보자. 영지식 증명 알고리즘의 구성을 위한 도구는 크게 두 가지로 나눌 수 있다.

프론트엔드: 함수에 대해 산술 회로식을 만드는 과정
Sonic, Marlin, Plonk

프론트엔드는 함수에 대해서 산술회로(circuit)을 만들고 이를 산술 회로식(예: 다항식)으로 바꾸는 과정이다.

백엔드: 산술 회로에 대해 증명을 생성하는 과정
Kate pairing, DARK, FRI, IPA, Bulletproof

영지식 증명에서는 산술회로식의 유효성을 증명하기 위해 증명자가 검증자에게 식 전체를 직접 보내지 않는다. 커밋과 같은 과정을 통해서 산술 회로식을 짧은 값의 commitment로 만들고 이를 증명값으로 검증자에게 전송한다. 이 증명을 만드는 방법과 이를 검증하는 방법이 포함된 단계를 백엔드라고 부른다.

영지식 증명은 프론트엔드와 백엔드의 조합을 통해 다양한 알고리즘을 구성할 수 있다.

Plonk + Kate pairing
Plonk + FRI
Plonk + Bulletproof

또한, 프론트엔드와 백엔드 조합외에도 필요한 기능에 따라 다른 알고리즘과도 결합할 수 있다. 오늘 소개할 재귀적 영지식 증명중 하나는 효율적인 증명 생성을 위해 Halo라는 알고리즘을 추가로 결합했다.

Plonk + Kate pairing + Halo

재귀적 영지식 증명

재귀적 영지식 증명은 쉽게 말해 증명 개수를 줄여 검증 비용을 감소하는 방법이다. 일반적인 프로그래밍 언어에서 재귀(recursion)는 특정 함수가 자기 자신을 부르는 것을 의미한다. 영지식 증명에서 재귀란 영지식 증명의 생성 코드(relation) 안에 이전에 생성된 증명을 검증하는 코드를 포함하는 것을 의미한다.

레이어2에서 생성된 1000개의 트랜잭션의 유효성을 증명하기 위해서는 1000개의 증명값(proof)이 필요하며, 레이어1의 스마트 컨트랙트는 1000번의 검증을 수행해야한다. 여기서 재귀 영지식 증명을 활용하면 1000개의 증명을 한 개로 압축할 수 있고, 결과적으로 레이어1은 한 개의 증명을 검증하는 것으로 1000개의 트랜잭션을 검증할 수 있게 된다.

여러가지 구현 방법이 있는데, 그 중 하나를 소개하자면 아래와 같다.

레이어2에서 1000개의 트랜잭션을 만든다.
1번 트랜잭션에 대한 증명을 만든다.
2번 트랜잭션의 증명을 만들 때 1번 증명을 재귀적 영지식 증명 생성 코드에 입력값으로 넣는다.
재귀적 영지식 증명 생성 코드 안에는 트랜잭션의 증명을 생성하는 코드와, 또 다른 증명을 검증하는 코드가 함께 포함되어 있다. 2번째에 생성한 증명값의 검증결과가 참이라면, 1번 트랜잭션과 2번 트랜잭션과 유효하다는 것을 동시에 검증한 것이다.
한 개의 증명이 남을 때까지 3번의 과정을 반복한 후, 최종 증명을 레이어1에 전송한다.
단일 증명 값은 1000개의 트랜잭션이 유효함을 증명하는 증명이며, 이 증명이 유효하다면, 레이어1은 한 개의 증명을 검증하여 1000개의 트랜잭션의 유효성을 검증한 것이다.

재귀적 영지식 증명은 레이어1에서 발생하는 연산 비용을 크게 절감하기 때문에 블록체인 확장성 솔루션에서 주요한 연구과제 중 하나로 자리잡고있다.

Polygon Zero의 재귀적 증명

출처: https://ko.0xzx.com/20211211241167.html

현재 재귀적 영지식 증명을 활발히 연구하고 있는 팀 중 하나는 Polygon Zero이며, Plonky와 Plonky2가 이 프로젝트의 대표적인 재귀적 영지식 증명 알고리즘이다.

Polygon은 21년 12월 Polygon은 zkverse 구축을 발표하며, 영지식 증명 팀 4개를 인수하겠다고 발표했다. 4개의 팀 중에서는 영지식 증명 기반의 블록체인을 개발하던 Mir protocol이 포함되어 있었으며, Mir protocol은 Polyon으로 인수되며 우리가 알고있는 Polygon Zero로 이름을 바꿨다.

Mir protocol은 영지식 증명을 기반으로 블록 공간을 줄여 더 많은 노드가 참여할 수 있는 가벼운 블록체인을 만드는 것을 목표로 하였다. Mir는 각 노드들의 트랜잭션 검증 비용을 줄이기 위한 재귀적 증명을 연구했으며, 그 결과 상태의 크기를 1000x 줄일 수 있는 Plonky를 발표했다.

Mir는 Polygon에 인수된 이후, 확장성 솔루션을 위해 기존의 Plonky보다 훨씬 개선된 재귀적 영지식 증명인 Plonky2를 발표했다. 두 개의 알고리즘은 Plonk라는 알고리즘을 사용했다는 공통점이 있지만, 빠른 증명 생성을 위해 Plonk에 결합하는 알고리즘의 종류가 다르다는 차이점이 있다.

Plonky가 기존 블록체인 시스템보다 약 1000배의 상태 크기를 줄였다면, Plonky2의 경우 증명 생성시간을 170ms로 축소했다고 발표하여 주목을 받았다. 재귀적 영지식 증명의 경우 직관적으로 검증에 필요한 연산은 줄일 수 있어도, 증명 생성 시간을 효율화 하는 게 어렵다는 것은 알 수 있다. Plonky2의 경우 검증 연산 뿐만 아니라 증명 생성 시간도 단축하여 주목을 받았다.

Plonky

Plonky는 Plonk, Kate pairing 그리고 Halo의 조합으로 만들어진 재귀적 영지식 증명이다. Plonk는 프론트엔드 영지식 증명 중에서 가장 작은 크기의 다항식을 갖는다. 영지식 증명의 크기는 다항식의 크기에 영향을 받기 때문에, 다항식 크기가 작다면 효율적인 증명 생성 도구로 여겨진다. Plonk를 백엔드 중 하나인 Kate pairing과 결합하면 증명의 크기와 검증 시간이 충분히 작아 구현에 효율적이다. 하지만 trusted setup이 필요하여 중앙화 이슈가 생긴다.

재귀적 영지식 증명이 기존의 영지식 증명과 가장 다른 점은 증명생성 코드안에 검증 코드가 포함되어 있다는 것이다. 기존의 영지식 증명 시스템에서 검증 연산은 레이어1의 스마트 컨트랙트가 수행했는데, 이 검증 코드가 증명 생성 코드의 일부가 된다는 것은 그 연산량과 방법이 증명 생성을 위한 연산에 큰 영향을 미칠 것이라는 걸 쉽게 예상할 수 있다.

백엔드로 Kate pairing을 사용한 경우, 타원곡선 페어링 연산을 수행해야하는데, 이 연산을 그대로 영지식 증명 생성 코드 안에서 수행하면 연산의 복잡성이 더 커지게 되어 실질적인 구현을 어렵게 만든다.

Plonky는 이를 해결하기 위해 Halo 프로토콜을 접목한다. Halo는 영지식 증명 생성 코드 안에서 효율적으로 검증할 수 있도록 설계된 알고리즘이다. 간단하게 설명하자면, Halo는 모든 재귀 단계에서 검증 연산을 매번 수행하지 않고, 마지막 단계에서 한 번만 실행한다. 이를 위해 모든 단계에서 원래 검증해야했던 이전 증명을 누적(accumulate)한다. 그리고 증명 생성의 마지막 단계에서 누적 계산이 올바르게 되었는지, 그리고 누적된 증명의 검증결과가 유효한지 한 번만 확인하도록 하여 증명 생성의 연산 비용을 줄인다.

Plonky2

Plonky2는 Plonk과 FRI를 결합하여 만든 재귀적 영지식 증명이다. Plonky에서 Kate pairing 검증의 효율성을 위해 Halo를 결합하는데, 사실 Halo를 사용하면 이더리움과 호환되지 않는다는 단점이 있다. 그 이유는 Halo의 경우 검증에 IPA라는 방식을 사용하는데, 이는 이더리움의 스마트 컨트랙트에서 제공하는 연산이 아니기 때문이다. 다시 말해, Plonky는 효율적인 재귀적 증명이지만, 이더리움상에서 사용할 수 없는 영지식 증명이다.

이러한 단점 때문에, 이더리움과 호환이 가능한 Halo2가 만들어졌는데, 이에 대해서는 다른 아티클에서 다룰 예정이다.

Plonky2는 백엔드로 FRI를 선택하여 이 문제를 해결한다. FRI의 경우 검증 연산에 페어링 연산이 포함되지 않기 때문에 Halo를 사용하지 않아도 구현의 효율성이 떨어지지 않으며, 실제 검증 연산에는 keccak-256만 필요하기 때문에, 이더리움과 호환이 가능하다는 장점이 있다.

Plonky2의 검증 비용은 약 100만 gas로 추정된다. 이 비용의 대부분은 CALLDATA 비용이 차지하기 때문에, EIP-4488에서 재 조정되면, 검증 비용이 170 ~ 200k gas까지 떨어지기 때문에 가장 저렴한 검증 연산을 기대할 수 있다.

사실 FRI를 결합한 재귀적 영지식 증명의 컨셉은 Plonky2가 최초가 아니다. 20년 7월 Alessandro Chiesa et al.은 Fractal라는 이름을 가진 FRI 기반의 재귀적 영지식 증명을 구축했지만, 증명 생성 소요 사간이 몇 분 내외였다. Plonky2의 경우 몇 가지 최적화를 통해 170ms의 훨씬 더 빠른 재귀적 영지식 증명을 구축했다고 평가받는다.

Plonky 이해하기

여기서는 Plonky 알고리즘을 이해하기 위한 백그라운드를 간단히 설명한다. Plonky를 이해하기 위해서는 여기에 쓰이는 PLONK, Kate pairing, Halo 알고리즘을 이해해야하는데, 여기서는 간단히 설명하고 디테일한 정보는 다음 아티클에서 다룰 예정이다.

PLONK (+ Kate pairing)

영지식 증명 알고리즘은 어떠한 것을 증명할 수 있는 값을 만들고 이를 검증하는 과정이다. 여기서 증명하고자하는 어떠한 것을 명제(statement)라고 부른다. 이 명제를 수학적으로 표현하고 증명을 만들기 위해서는 특정한 다항식을 만들어야 한다. 앞서 Plonk가 프론트앤드 중에서는 가장 작은 크기의 다항식을 갖고 이로인해 증명 값도 작다고 언급했다. 여기서는 Plonk의 증명을 만드는 다항식을 작게 만드는 방법과, 증명 생성에 필요한 값, 그리고 검증 과정을 간단하게 다룬다.

Plonk의 명제(statement)는 5단계를 거쳐 작은 다항식으로 축소된다.

f(x)는 F상의 원소를 근으로 갖는 다항식이다.
f(x)는 Z_H(x)로 나누어 떨어진다.
f(x) = t(x)*Z_H(x) x ∈ F
여기서 Z_H(x)는 베니싱(vanishing) 함수로 H상의 원소를 근으로 갖는 다항식이다. 다시 말해, Z_H(x)은 H상의 원소를 대입하면 항상 결과값이 0이다.
f(x) = t(x)*Z_H(x) x ∈ H ⊂ F
F의 subgroup인 H상의 모든 x 원소에 대해 위 방정식을 만족한다면, F상의 모든 원소에 대해서도 이 방정식을 만족한다.
f(z) = t(z)*Z_H(z) z ← H
최종 명제로 schwartz-zippel lemma에 의거하여 H상의 한 점에서 위의 방정식이 만족하면 H상의 모든 원소에 대하여 위 방정식을 만족함을 증명할 수 있다.

1번의 명제를 증명하는 것보다 5번의 명제를 증명하는 것이 훨씬 간단하다. 마지막 명제는 f(z), t(z), Z_H(z) 3개의 값이 정해진 방정식을 만족하는지 확인하면 되기 때문이다. 증명자와 검증자가 대화형(interactive) 방식으로 5번의 명제를 통해 영지식 증명을 검증하는 과정은 다음과 같다.

검증자: H에서 상수 z를 랜덤하게 선택하여 증명자에게 전송한다.
증명자: 검증자에게 받은 z를 대입하여 f(z), t(z)를 계산하고 이를 검증자에게 전송한다.
검증자: 증명자에게 받은 값을 통해 f(z) = t(z)*Z_H(z)이 만족하는지 검증한다.

검증자는 Z_H(z)를 사전에 알고 있기 때문에(H를 알고있으면 H의 베니싱 함수인 Z_H(x)를 쉽게 찾을 수 있다), z를 선택하여 이를 미리 계산(evaluate)할 수 있다.

Plonk는 다항식을 줄이기 위해서 위 명제를 좀 더 축소하는 단계를 거쳐야한다.

증명자가 검증자에게 건내는 t(z)의 값은 사실 매우 크다. 이 값을 줄이기 위해서, Maller optimization을 사용하여 이 값을 통째로 전송할 필요가 없도록 한다.

f(x) = t(x)*Z_H(x) 방정식은 다음과 같이 바꿀 수 있다.
r(x) = f(x) — t(x) *Z_H(x)

이로 인해 변경된 증명 검증 과정은 다음과 같다.

증명자: 검증자에게 다항식 t(x)의 commitment를 만들어 검증자에게 전송한다.
검증자: H에서 상수 z를 랜덤하게 선택하여 증명자에게 전송한다.
증명자: r(z), f(z) 값을 계산해 검증자에게 전송한다. 여기서 증명자가 올바른 방정식을 계산했다면, r(z) = 0 이다.
검증자: t의 commitment와 z로 t(z)를 계산한 후, r(z) = f(z) — t(z)*Z_H(z)가 성립하는지 확인한다.

마지막 검증 과정을 보다 정확히 이야기하면, $com(r) = com(f) — com(t)*Z_H(z)$가 성립하는지 확인하는 것이다. 이를 위해 증명자는 com(r), com(f), com(t)의 검증자에게 제공해야한다. 이를 위해 각 commitment의 수식을 정의한다.

com(t) 축소하기
com(t)는 t의 commitment를 의미한다. 앞서 t(z)의 값이 매우 크다고 했는데, 사실 사전에 전송하는 com(t)도 매우 크다. 이유는 Plonk의 순열 형태의 다항식(permutation argument)가 3개의 witness 다항식(a(x), b(x), c(x))로 인해 3번의 곱 연산으로 만들어지기 때문이다. 이를 줄이기 위해 Plonk에서는 t를 작은 다항식 3개로 나누어 검증자에게 전송한다.

com(r) 정의하기

com(f) 정의하기
Plonk의 산술회로는 다항식 f(x)로 구성된다.

여기서 a(x), b(x), c(x)는 증명자가 프라이빗하게 구성하는 다항식이기 때문에, 검증자에게 전송할 때는 com(a), com(b), com(c), a(z), b(z), c(z)를 계산하여 전송한다.

또 다른 항인 q_L(x), q_R(x), q_M(x), q_O(x), q_C(x)는 selector 다항식으로 공개되어진 다항식이며, 증명자과 검증자 모두 구성가능하다.

위 과정으로 결정된 Plonk 기반의 영지식 증명의 최종 단계는 다음과 같다.

출처: https://www.cryptologie.net/article/526/maller-optimization-to-reduce-proof-size/

증명자: 검증자에게 com(a), com(b), com(c), com(t_lo), com(t_mid), com(t_hi)를 전송한다.
검증자: H에서 상수 z를 랜덤하게 선택하여 증명자에게 전송한다.
증명자: z를 대입한 a(z), b(z), c(z), r(z)를 계산하여 검증자에게 전송한다.
검증자: 증명자에게 받은 값으로 com(r)를 계산하여 아래 방정식이 성립하는지 검증한다.

Halo: 재귀적 영지식 증명을 빠르게 구현하는 방법

Plonky는 PLONK와 Kate pairing로 만들어진 영지식 증명에 Halo를 추가로 결합하여 만들어진 효율적인 재귀적 영지식 증명이다. 영지식 증명에서 백앤드로 Kate pairing을 사용한 경우, 검증 연산에 타원곡선의 페어링 연산이 필요하다. 재귀적 영지식 증명은 검증 코드를 증명 생성 코드안에서 함께 수행하는 알고리즘인데, 페어링 연산을 증명 생성 코드안에서 매 단계마다 함께 실행하면 연산의 복잡성이 매우 커져 실질적인 구현이 어려워진다.

Plonky는 검증 연산의 효율성을 위해 Halo를 추가로 결합되었다. Halo는 증명 생성 코드안에 있는 검증 페어링 연산을 코드 밖에서 수행할 수 있게 도와준다. 영지식 증명 바깥에서 수행되는 코드는 유효성이 보증되지 않기 때문에, 검증 연산의 유효성을 보증하기 위한 장치를 마련해야한다. Halo는 재귀 연산의 모든 단계에서 영지식 증명 밖의 검증 코드에 대한 누적(accumulate)연산을 수행하고, 최종 검증은 마지막 단계에서 코드 안에서 한 번만 시행하도록 한다.

Plonk에 Kate pairing을 결합한 경우, 영지식 증명 코드안에 포함되어야 하는 검증 페어링 연산은 다음과 같다. (여기서 e는 페어링 연산을 의미하는 함수이다)

Halo는 g^f(x)와 g^q(x)의 누적(accumulate) 값을 재귀 연산 단계 마다 누적 계산하고, 마지막 단계에서 페어링 연산을 통해 유효성을 체크하도록 한다.

이를 이해하기 전에 누적에 대하여 먼저 살펴보자.

각 입력 값에 대한 검증을 위해 모두 페어링 연산을 각각 시행해야한다. 누적 연산을 사용하기 위해, 오른쪽 항을 이항하면 다음과 같이 쓸 수 있다.

왼쪽 항의 G에 대한 첫 번째 연산들을 하나로 묶은 후 이를 A라고 정의한다.

오른쪽 G연산에 대한 항도 하나로 묶고, 이를 B라고 정의하자.

두 항을 묶었으니 결과적으로 “e(A, H ) = e(B, H^x)”가 성립하는지만 체크하면 두 개의 식을 모두 체크할 수 있는 누적 방식이 완성된다. 여기서 A와 B 연산은 페어링을 사용하지 않으니 전체 산술 회로 내에서 쉽게 연산을 할 수 있다.

n번째 재귀 단계의 경우 n-1번의 누적값을 계산한다.

이 누적값을 계산하는 산술 회로를 누적 산술 회로(accumulate circuit)이라고 한다.

이제 마지막 재귀 단계에서는 검증 연산에서 “e(A_n, H ) = e(B_n, H^x)” 이 성립하는지 확인하여 마지막 증명값을 만들고 이를 레이어 1에 전송하여 연산의 효율성을 높인다.

Plonky2 이해하기

Plonky2를 이해하기 위해서는 핵심이 되는 백엔드인 FRI를 이해해야한다. FRI의 목적은 검증자가 증명자에게 전달받은 다항식의 유효성을 확인(검증)하는 것이다. FRI의 특징은 그 이름에서 간략히 유추해볼 수 있다.

FastFast는 빠름을 의미하는게 아닌, Fast Fourier Transform (FFT)의 F를 따온 단어이다. FFT는 다항식을 점의 형태로 바꾸기 위해 사용하는 알고리즘이다. 즉, FRI는 FFT의 알고리즘을 차용하여 다항식 증명을 점(commitment)을 통해 효율적으로 이행하는 알고리즘이다.

Interactive Oracle Proof실제 FRI 프로토콜에서는 Prover가 Verifier에게 직접 다항식을 전송하지 않는다. FFT를 통해 다항식을 점의 형태로 바꾼 후 이를 Oracle에 퍼블리시 해놓으면, Verifier가 원하는 다항식의 값 f(a)을 Oracle에 요청해서 b를 받아오는 형태이다. Verifier가 원하는 다항식 값을 Oracle에게 직접 요청하는 형태이기 때문에 Interactive라는 명칭이 붙었다.

ProximityNIZKP는 validity 방식으로 확률에 의존하여 ture 혹은 false를 확신하지 않는다. 하지만 이 경우, 다항식의 유효성 증명을 위해 모든 다항식의 결과값을 verifier가 살펴보지 않고, 임의의 점 r에서 다항식 f가 갖는 값을 확인하고, 이를 확장하여 ture 혹은 false를 확신하기 때문에 그 결과가 근사치에 해당한다. 따라서 Proximity라는 명칭이 추가로 붙여졌다.

FRI 알고리즘

출처: https://medium.com/starkware/a-framework-for-efficient-starks-19608ba06fbe

FRI는 다항식 변수 x에 “공개된” 여러 개의 값을 할당하여 다항식 값을 여러개 구하고, 이 값들을 머클 해시 트리로 만들어서 검증자에게는 그 루트만 전달하는 방식이다. 변수 x에 대한 다항식의 값은 IOP(Interactive Oracle Proof)에 공개되며, 검증자는 임의의 x값을 선택하여 IOP에 요청해 다항식의 값을 얻을 수 있다. 이후 2개의 방정식의 연산을 통해 IOP에게 받은 다항식 값이 맞는지 확인할 수 있다.

FRI에서는 다항식의 commitment를 구하기 위해서 해시 함수만 사용한다. 해시 함수는 현재까지 양자 저항성을 가지고 있기 때문에 FRI를 백엔드로 결합한 기법은 양자 저항성을 가지게 된다. 대표적으로 STARK가 백엔드로 FRI를 채택하여 양자 저항성을 가진 zkp이다.

검증을 위해 확인해야하는 값

증명자의 목적은 자신이 가지고 있는 다항식 f(x)가 유효하다는 것을 검증자에게 검증받는 것이다. 이를 위한 가장 naive한 방법은 검증자에게 다항식 f(x)를 주고, 해당 다항식이 모든 x점 상에서 옳은 값을 갖는지 검증자가 직접 계산해서 확인하는 것이다. 다항식이 작고 x축의 값이 적으면, 이 방법이 가장 효과적일 수 있다. 하지만, 다항식이 매우 크고 x값이 매우 많다면, 이 방법은 검증 시간을 정말 많이 필요로 한다. 블록체인 특성상 유효한 증명을 위해 검증 과정을 스마트 컨트랙트(smart contract)로 구현을 하게 되는데, 검증 연산 시간이 매우 크다면 가스비가 많이 발생하기 때문에 실질적으로 활용이 불가능하다고 봐도 무방하다.

FRI는 검증 과정의 효율성을 위해 다음과 같은 방법을 사용한다.

증명자는 다항식 f(x)를 보내는 게 아니라, 모든 x 값에 대한 f(x)의 결과값 (a, f(a))을 보낸다. 이 결과값은 상수로 commitment라고 하며, 이 결과값을 만드는 과정을 polynomial commit이라고 한다.
commitment를 증명자가 검증자에게 모두 전송하는 것은 아니고, 모든 값을 미리 구해서 오라클에 퍼블리시 해놓는다.
검증자는 임의의 점 r를 선택하여 f(r) 값을 오라클에 요청해서 그 상수 값을 받는다.
검증자는 받아온 상수값으로 2개의 방정식이 만족하는지 확인하고, 모두 만족한다면 진실이라고 이야기한다.

검증자가 검증을 위해 확인하는 두 개의 방정식은 다음과 같다.

여기서 증명자가 증명하고자 하는 다항식 결과값 f(r)이외에도 Z_H(r), B(r), D(r), g(r) 그리고 g’(r)가 추가로 필요한 것을 알 수 있다. 여기서 Z_H(r), B(r), D(r)는 검증자가 직접 계산할 수 있는 값이다. 하지만 g(r), g’(r)는 증명자가 건내주어야 하는 다항식이기 때문에, f(x)와 마찬가지로 commitment를 미리 계산하여 오라클에 퍼블리시해 놓는다.

검증자는 임의의 값 r를 선택하고, 그 값에 대한 함수값을 오라클에게 요청한다. 여기서 요청하는 함수값 f(r\omega²)은 숫자이기 때문에, 검증자는 숫자의 사칙연산을 통해 방정식의 값이 맞는지 확인하는 것이다(3 = 3 인지 확인하는 거라 생각하면 된다). 만약 두 방정식이 모두 성립한다면 검증 결과는 진실이고 만약 성립하지 않는다면 거짓이다.

알고리즘 최적화

Plonky2는 몇 가지 최적화를 통해서 증명 생성 성능을 향상시켜 속도를 170ms로 줄였다. 여기서는 최적화에 대해서 간단히 다루고 구체적인 내용은 이후 Plonky2 분석 아티클에서 다룬다.

더 작은 체(field) 선택
일반적으로 증명을 생성하는 프라임 체(prime field)의 크기는 $2^{256}$이다. Plonky2는 연산 속도를 빠르게하기 위해서 더 작은 체를 선택했으며 그 크기는 $2^{64} — 2^{32} + 1$이다. 당연하게도, 마냥 작은 체를 사용하는게 좋은 것은 아닐 것이다. Plonky2의 특정 부분에서는 견고성(soundness)을 위해 더 큰 필드가 필요한 경우가 있는데, 여기서는 Fp[X]/(X2 − 7)를 사용한다.

Custom gate
Plonky2는 재귀에서 검증 코드를 실행하기 위해 custom gate 방식을 도입한다. 이 때 division gate의 경우에만 custom gate를 도입하여 검증 코드를 효율적으로 산술 회로화한다.

Zero knowledge
Kate pairing과 결합된 Plonk에서는 영지식을 달성하기 위해 Z_H(x)에도 임의의 곱을 추가한다. FRI 알고리즘을 사용하는 plonky2에서는 이러한 곱을 추가하면 다항식의 차수를 증가시키기 때문에 바람직하지 않다. 이 방법 대신 z(x)의 블라인드(blind)를 위해 “Adding zero knowledge to PLONK-Halo” 논문을 참조했다.

FRI optimization

프로토콜을 수행하는데 필요한 최소한의 머클 트리를 사용
증명 크기를 최소화하는 FRI reduction arities에 대한 철저한 검색을 수행
Oracle 데이터의 인접 블록이 함께 쿼리되는 곳마다 전체 블록을 머클 트리 잎에 배치
증명 크기의 최적화를 위해 겹치는 머클 패스를 제거 등

마치며

이번 아티클에서는 재귀적 영지식 증명의 필요성과 컨셉을 이해하고, 최근에 소개된 재귀적 영지식 증명인 Plonky2를 이해하도록 작성되었다. 다음 아티클에서는 각 항목들의 정확한 이해를 돕기 위해, Plonk, Halo, FRI, Kate pairing 등 알고리즘의 수학적 분석을 다루고, 이를 조합한 재귀적 증명 알고리즘인 Plonky와 Plonky2에 대하여 보다 구체적으로 분석한다.

Reference

ZKP

https://www.itfind.or.kr/publication/regular/weeklytrend/weekly/view.do?boardParam1=7961&boardParam2=7961