PSE ZK core program의 4주차 학습 내용인 Plonk에 대해서 공부한 내용들을 정리해보았습니다. plonk paper와 여러 글들을 참조하여 작성하였으며, 최대한 쉽게 풀어보고자 합니다.
//아직은 정제되지 않은 글입니다...
1. PLONK란 무엇인가?
PLONK는 Permutation Argument for LOgarithmic-size Non-interactive Knowledge의 약자로, zk-SNARK(Zero-Knowledge Succinct Non-interactive Argument of Knowledge) 프로토콜의 일종이다.
PLONK는 기존의 zk-SNARK 시스템처럼 개별 회로마다 trusted setup이 필요 없다. 범용적이고 업데이트 가능한 신뢰 설정(Structured Reference String, SRS)를 사용한다는 중요한 특징이 있다. 이로 인해 회로마다 새로운 신뢰 설정을 하지 않아도 되므로, 여러 애플리케이션에 재사용할 수 있다.
/*PLONK가 왜 나왔냐?
PLONK는 범용적이고 완전 간결한 zk-SNARK를 제공하기 위해 탄생
범용성: 동일한 SRS로 모든 회로에서 사용할 수 있으며, 이를 업데이트할 수 있음.
완전 간결성: 검증 시간이 회로의 크기와 상관없이 매우 빠르고, 증명의 길이가 매우 짧음.*/
2. PLONK의 핵심 구조와 개념
2.1 회로 산술화 (Arithmetization)
PLONK는 계산을 다항식 시스템으로 변환합니다. 이를 회로 산술화라고 하는데, 주어진 회로를 산술적 표현으로 변환하는 과정입니다. PLONK는 단항 다항식을 사용하여 이 과정을 단순화하고 효율적으로 수행합니다.
2.2 순열 논증 (Permutation Argument)
PLONK의 순열 논증은 Bayer와 Groth의 [BG12] 논문에서 소개된 기술을 기반으로 합니다. 이 논증은 계산 과정에서 변수를 올바르게 매핑했는지를 확인하기 위한 절차입니다. 구체적으로, PLONK는 Lagrange 기반을 사용하여 다항식의 특정 지점에서의 값을 확인하는 방식으로 이를 간단하게 만듭니다.
2.3 SRS와 증명 구조
PLONK는 업데이트 가능한 신뢰 설정(SRS)을 사용합니다. SRS는 계산의 보안을 보장하는 데 필요한 데이터로, 모든 회로에서 동일하게 사용할 수 있습니다. 이는 기존 zk-SNARK 시스템에서 각 회로마다 새로운 신뢰 설정을 필요로 했던 점과 비교했을 때 큰 장점입니다.
4. PLONK의 증명 생성 과정
PLONK의 증명 생성 과정은 크게 순열 논증과 회로 산술화의 두 단계로 나누어집니다. 증명 생성 과정에서 중요한 개념은 다항식 커밋먼트(Polynomial Commitment)입니다. 증명자는 다항식을 커밋하고, 검증자는 그 커밋된 다항식이 올바른지 확인합니다.
4.1 순열 논증 과정
PLONK의 순열 논증은 다음과 같은 단계로 이루어집니다:
난수 선택: 검증자는 난수 𝛽와 𝛾를 선택합니다.
다항식 변형: 증명자는 난수에 따라 다항식을 변형하고, 각 다항식의 특정 지점에서의 값을 계산합니다.
다항식 체크: 증명자는 이러한 값을 이용해 순열 관계를 증명합니다.
이 과정에서, PLONK는 다항식 계산을 이용해 모든 회로에서 동일한 방식으로 증명을 수행할 수 있습니다.
