원문 작성자: Fox Tech CEO Kang Shuiyue, Fox Tech 수석 과학자 Meng Xuanji
원문 작성자: Fox Tech CEO Kang Shuiyue, Fox Tech 수석 과학자 Meng Xuanji
비트코인, 블록체인, 스마트 컨트랙트 등의 개념이 확산되면서 Web3 분야의 활발한 발전에 주목하는 사람들이 늘고 있습니다. 기술 측면에서도 많은 개발자들이 기본 블록체인을 지원하는 암호화 프로토콜에 주목하고 있습니다. 그 중 영지식증명 프로토콜은 고유한 특성으로 빛을 발하며 개인정보 보호를 실현하고 Layer 2 성능 확장을 실현하는 zkrollup 프로젝트에서 핵심적인 역할을 합니다.
영지식증명(Zero-knowledge proof)은 알고리즘의 총칭으로, 지금까지 연구자들은 Plonk, Groth 16, zkStark, Virgo, Orion, Foaks 등 많은 프로토콜을 발명했습니다. 서로 다른 프로토콜은 서로 다른 컴퓨팅 시나리오에 적합하며 복잡성과 효율성도 다릅니다.예를 들어 Foaks는 선형 증명 시간과 짧은 증명 길이의 이점이 있습니다.
이 프로토콜은 Fox Tech에서 채택한 Foaks 증명 시스템에서도 중요한 역할을 합니다. 구체적으로 opcode의 정확성을 증명하기 위해서는 먼저 산술회로로 변환한 다음 행렬로 변환하고 최종적으로 다항식을 생성하고 다항식에 증명 시스템의 알고리즘을 적용하여 마지막으로 압축해야 한다. 그 중 증명자(Prover)와 검증자(Verifier) 사이의 상호 작용 과정도 일정한 합계를 계산하는 과정, 즉 합산 확인 프로토콜 과정으로 변환된다.
첫 번째 레벨 제목
Sum-check Protocol
보조 제목
1. 프로토콜 목표
프로토콜의 목표는 매우 간단하고 이해하기 쉽습니다.
zkRollup에서 고려한 "아웃소싱 계산" 시나리오와 유사하게 애플리케이션에서 위 수식의 계산량이 매우 클 것입니다. 계산 결과가 정확함을 증명하기 위해 검증자(Verifier)에게 보고합니다.
보조 제목
2. 프로토콜 가정
우선, 이 프로토콜에서 검증자의 기능을 명확히 할 필요가 있습니다. 우리는 검증자가 함수 g를 계산할 수 있는 오라클(Oracle)을 가지고 있다고 가정합니다. 즉, 검증자가 어떤 입력 r 1, ... , rv를 결정한 후 g(r 1, ... , rv)를 계산하는 것이 쉽습니다. 그러나 전체 결과 H를 계산하는 것은 어렵습니다.
두 번째 요점은 프로토콜의 목표와 관련하여 실제로 sum-check 프로토콜은 모든 집합 B에 대해 bBmg(b)를 계산할 수 있지만 일반성을 잃지 않고 B={0, 1}이라고 가정합니다.
보조 제목
3. 프로토콜 프로세스
계약에는 총 v 라운드가 포함됩니다. 각 라운드에서 g의 하나의 변수가 처리됩니다.
라운드 1:
증명자가 정직하다면 H=g 1( 0) + g 1( 1)이 성립해야 합니다. 검증자는 검증하고 통과하면 난수 r 1이 선택되어 인증자에게 전송됩니다. 프로토콜의 가정에 따라 증명자는 위의 검증을 완료할 수 있습니다.
다변량 다항식 p에서 i번째 변수의 차수를 나타내기 위해 degi(p)를 사용합니다. g 1(X 1)의 차수는 deg 1(g)이므로 g 1은 deg 1(g)+ 1 도메인 요소로 나타낼 수 있습니다.
라운드 j (j>1):
라운드 브이:
이미지 설명
그림 2: Foaks Sum-check 프로토콜
완전성: 증명자에게 유효한 증인이 있는 경우 검증자는 (1-negl(n)) 이상의 확률로 증명을 수락합니다.
건전성: 증명자가 유효한 증인이 없는 경우 검증자는 negl(n)보다 낮은 확률로 증명을 거부합니다.
간결함: 증명의 크기는 증인의 크기보다 훨씬 작아야 합니다.
# 여기서 negl(n)은 무시할 수 있는 함수입니다.
보조 제목
4. 프로토콜 복잡성
다음 표는 복잡성 결과를 자세히 보여줍니다. 여기서 T는 오라클(Oracle)에 액세스하는 데 필요한 오버헤드, 즉 g를 한 번 평가하는 데 필요한 오버헤드를 나타냅니다.
그림 3: 합계 검사 프로토콜의 복잡성
첫 번째 레벨 제목
섬체크 프로토콜 적용
많은 영지식 증명 알고리즘 중에서 sum-check 프로토콜이 중요한 역할을 하고 있습니다. 많은 문제의 증명은 원래 문제를 합계 검사 형식으로 변환한 다음 후속 단계를 완료하는 데 의존합니다.
예를 들어, sum-check 프로토콜은 방향이 없는 그래프에서 삼각형의 수를 세는 데 사용할 수 있습니다.
먼저 인접 행렬 A를 사용하여 방향이 없는 그래프 G를 나타내고 E를 에지 집합으로 두고 Ai, j= 1(i, j)E, 즉 포인트 i, j 사이에 에지가 있는 경우 그러면 Ai, j = 1 그렇지 않으면 0. 점 i, j, k에 대해 세 점이 삼각형을 이루는 조건은 Ai, j= 1, Ai, k= 1, Aj, k= 1 입니다.
또한 많은 증명 시스템에서 sum-check 프로토콜은 구성을 위한 기본 논리로 사용됩니다. 아래 그림은 sum-check에 기반한 다양한 변환에 기반한 다양한 증명 시스템을 보여줍니다.
그림 4: 네 가지 유형의 증명 시스템에서 Sum-check 프로토콜 적용
첫 번째 레벨 제목
발문
발문
첫 번째 레벨 제목
참조
[LFKN 92 ] Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39: 859 – 868, October 1992.
https://people.cs.georgetown.edu/jthaler/sumcheck.pdf
IOS
Android