원문 작성자: Fox Tech CEO Kang Shuiyue, Fox Tech 수석 과학자 Meng Xuanji

서문: 암호 작성자가 Tensor Product와 다항식 값 사이의 연결을 발견하지 못하면 다항식 커밋 프로토콜 Brakedown이 나타나기 어렵고 Brakedown 기반 Orion 및 FOAKS.Fast 알고리즘과 같은 새로운 프로토콜을 생성할 수 없습니다.

다항식 약속에 의존하는 많은 영지식 증명 시스템에서는 서로 다른 약속 프로토콜이 사용됩니다. 2022년 8월 "Measuring SNARK performance: Frontends, backends, and the future" 기사에서 a16z의 Justin Thaler의 평가에 따르면 Brakedown은 증명 크기가 더 크지만 의심할 여지 없이 현재 가장 빠른 다항식 커밋 프로토콜입니다.

FRI, KZG, Bulletproof는 보다 일반적인 다항식 커밋 프로토콜이지만 속도가 병목 현상입니다. zkSync에서 사용하는 Plonky, Polygon zkEVM에서 사용하는 Plonky 2, Scroll에서 사용하는 Ultra-Plonk와 같은 알고리즘은 모두 KZG를 기반으로 하는 다항식 확약입니다. Prover는 다항식 및 커밋을 생성하는 다수의 FFT 계산 및 MSM 작업을 포함하며, 둘 다 큰 계산 부담을 부과합니다. MSM은 다중 스레드 가속을 실행할 수 있는 잠재력이 있지만 많은 메모리가 필요하고 높은 병렬 처리에서도 느리며 대규모 FFT는 알고리즘이 실행될 때 데이터의 빈번한 셔플링에 크게 의존하여 로드하기 어렵습니다. 분산 가속을 통해 컴퓨팅 클러스터 전반에 걸쳐

이러한 작업의 복잡성이 크게 줄어든 것은 더 빠른 다항식 커밋 프로토콜 Brakedown 때문입니다.

FOAKS(Fast Objective Argument of Knowledges)는 Fox Tech에서 제안한 Brakedown 기반 영지식 증명 시스템 프레임워크입니다. FOAKS는 Orion을 기반으로 FFT 연산을 더욱 줄여주며, 궁극적으로 FFT를 없애는 것이 목표입니다. 또한 FOAKS는 증명 크기를 줄이기 위해 새롭고 매우 우아한 증명 재귀 방법을 설계했습니다. FOAKS 프레임워크의 장점은 zkRollup 시나리오에 매우 적합한 선형 증명 시간의 실현을 기반으로 작은 증명 크기를 갖는다는 것입니다.

아래에서는 FOAKS에서 사용하는 다항식 커밋 프로토콜 Brakedown을 자세히 소개합니다.

암호학에서 커밋(Commitment) 프로토콜은 증명자(Prover)가 특정 비밀 값을 커밋하고, 바인딩 및 숨기기(Hiding)가 있는 공개 커밋 값을 생성한 다음 제출합니다. 검증자는 이 약속을 열고 전송해야 합니다. 약속과 메시지 사이의 일치를 확인하기 위해 검증자에게 메시지를 보냅니다. 이로 인해 커밋 프로토콜과 해시 함수는 공통점이 많지만 커밋 프로토콜은 종종 공개 키 암호화 분야의 수학적 구조에 의존합니다. 다항식 약정(Polynomial Commitment)은 다항식에 대한 약정 체계의 한 유형, 즉 약속된 값이 다항식입니다. 동시에 다항식 커밋 프로토콜에는 주어진 지점에서 값을 얻고 증명을 제공하는 알고리즘도 포함되어 있어 다항식 커밋 프로토콜 자체가 암호화 프로토콜의 중요한 클래스이자 많은 영지식 증명 시스템의 핵심 부분이 됩니다. .

암호학 분야의 최근 연구에서 텐서 곱(Tensor Product)과 다항식의 값과의 연관성 발견으로 관련 다항식 커밋 프로토콜 시리즈가 탄생했으며, 브레이크다운(Brakedown)이 대표적인 프로토콜 중 하나다. . .

Brakedown 프로토콜의 세부 사항을 자세히 소개하기 전에 몇 가지 기본 사항을 이해해야 합니다. 선형 코드, 충돌 방지 해시 함수, 머클 트리, 텐서 제품 및 다항식 값의 텐서 제품 표현의 작동을 이해해야 합니다.

첫 번째는 선형 코드(Linear Code)입니다. 메시지 길이가 k이고 코드 워드 길이가 n인 선형 코드는 선형 부분 공간입니다.

C ∈ Fn, 그래서 메시지에서 EC: Fk→C로 표시되는 인코딩이라고 하는 코드 단어로의 주입이 있습니다. 코드워드의 모든 선형 조합은 여전히 ​​코드워드입니다. 두 코드워드 u와 v 사이의 거리는 △(u, v)로 표시되는 해밍 거리입니다.

최단 거리는 d=minu, v△(u, v)입니다. 이러한 코드는 [n, k, d] 선형 코드로 표시되며 d /n은 코드의 상대적인 거리를 나타냅니다.

충돌 방지 해시 함수(Hash Function)와 머클 트리(Merkle Tree)가 뒤따릅니다.

H: { 0, 1 } 2 λ → { 0, 1 } λ를 사용하여 해시 함수를 나타냅니다. 머클 트리는 2d 메시지의 약속을 실현하고, 해시 값 h를 생성하고, 메시지를 열 때 d+ 1 해시 값을 요구할 수 있는 특별한 데이터 구조입니다.

Merkle 트리는 깊이가 d인 이진 트리로 나타낼 수 있으며, 여기서 L 메시지 요소 m1, m2,..., ml는 각각 트리의 리프에 해당합니다. 트리의 각 내부 노드는 두 개의 하위 노드에서 해시됩니다. 메시지 mi를 열 때 mi에서 루트 노드까지의 경로를 공개해야 합니다.

이미지 설명

1. h←Merkle.Commit(m1 ,..., ml)

2. (mi,πi)←Merkle.Open(m, i)

3. { 0, 1 }←Merkle.Verify(πi, mi, h)

그림 1: 머클 트리

이미지 설명

그림 2: 벡터와 행렬의 Tensor 곱 연산

다음으로 다항식 값의 텐서 곱 표현을 알아야 합니다.

[GLS+]에서 언급했듯이 다항식의 값은 텐서 곱의 형태로 표현될 수 있습니다. 여기서 우리는 다선형 다항식 약속을 고려합니다.

특히 다항식이 주어지면 벡터 x0 , x1 ,..., xlogN-1의 값은 다음과 같이 쓸 수 있습니다.

다중선형성의 정의에 따르면 각 변수의 차수는 0 또는 1이므로 N개의 단항식과 계수, 그리고 logN개의 변수가 있습니다. 만들다

, 여기서 i0 i1 ...ilogN-1은 i의 이진 표현입니다. w는 다항식 계수를 나타내고,

마찬가지로 정의

만들다

. 따라서 X=r0⊗r1입니다.

따라서 다항식 값은 텐서 곱의 형태로 표현할 수 있습니다. ϕ(x0 , x1 ,..., xlogN-1 )=。

마지막으로 FOAKS 및 Orion [XZS 22 ]에서 사용되는 브레이크다운 프로세스를 살펴보겠습니다.

먼저 PC.Commit은 다항식 계수 w를 k×k 행렬 형태로 나누어 인코딩하고("Preliminary Knowledge"의 선형 코드 참조) C2로 표시합니다. 그런 다음 C2의 각 컬럼 C2 [:, i]에 Commitment를 하여 Merkle Tree를 구축하고, 각 컬럼이 형성한 Merkle Tree의 Root에 대한 또 다른 Merkle Tree를 최종 Commitment로 구축한다.

가치 증명의 계산에서 두 가지 점을 증명해야 하는데 하나는 근접성(Proximity)이고 다른 하나는 일관성(Consistency)입니다. 근사화는 커밋된 행렬이 실제로 인코딩된 코드워드에 충분히 가깝다는 것을 보장합니다. 일관성 보장 y=。

근접성 테스트: 근접성 테스트는 두 단계로 구성됩니다. 먼저 검증자는 확률 벡터 0을 증명자에게 보내고 증명자는 Y0과 C1의 내적, 즉 C1의 행과 Y0의 성분을 계수로 선형 결합을 계산합니다. 선형 코드의 특성으로 인해 Cy 0은 Yy 0의 코드워드입니다. 그 후 증명자는 Cy 0이 실제로 커밋된 코드워드에서 계산되었음을 증명합니다. 이를 증명하기 위해 검증자는 임의로 t개의 열을 선택하고, 증명자는 해당 열을 열어 Merkle 트리 증명을 제공합니다. 검증자는 이러한 열과 Y0의 내적이 Cy 0의 해당 위치와 같은지 확인합니다. [BCG 20]은 사용된 선형 코드가 일정한 상대 거리를 가지면 커밋된 행렬이 압도적 확률로 코드워드에 가깝다는 것을 증명합니다(압도적 확률이란 명제의 부정 명제가 참일 확률을 의미합니다. 무시됨). .

일관성 검사: 일관성 검사와 근접성 검사 프로세스는 완전히 유사합니다. 차이점은 확률 벡터 Y0를 사용하지 않고 r0을 직접 사용하여 선형 결합 부분을 완성한다는 것입니다. 마찬가지로 c1은 메시지 y1에 대한 선형 코드이기도 하며 다음을 갖습니다.

ϕ(x)=. 커밋된 행렬이 코드워드에 가까우면 일관성 검사에 의해 y=φ(x)가 압도적 확률로 유지된다는 것이 [BCG 20]에 나와 있습니다.

의사 코드 형식으로 Brakedown 프로토콜의 흐름을 제공합니다.

Public input：The evaluation point X，parsed as a tensor product X=r0 ⊗r1 ;

Private input：The polynomial ϕ ，the coefficient of is denoted by w.

Let C be the [n, k, d]-limear code，EC：FkFn be the encoding function，N=k×k. If N is not a perfect square，we can pad it to the next perfect square. We use a python style notationmat[:, i] to select the i-th column of a matrix mat。

1. function PC. Commit(ϕ)：

2. Parse w as a k×k matrix. The prover locally computes the tensor code encoding C1 ，C2  ，C1 is a k×n matrix，C2 is a n×n matrix.

3. for i∈ [n] do

4. Compute the Merkle tree root Roott=Merkle.Commit(C2 [:, i])

5. Compute a Merkle tree root R=Merkle.Commit([Root0 ,......Rootn-1 ]), and output R as the commitment.

6. function PC. Prover(ϕ, X, R)

7. The prover receives a random vector Y0 ∈Fk from the verifier

8. Proximity 

   

9. Consistency  

   

10. Prover sends C1 , y1 , C0 , y0  to the verifier.

11. Verifier randomly samples t[n] as an array Î and send it to prover

12. for idx∈Î do

13. Prover sends C1  [:, idx] and the Merkle tree proof of Rootidx for C2  [:, idx] under R to verifier

14. function PC. VERIFY_EVAL(πX, X, y=ϕ(X), R)

15. Proximity: ∀idx∈Î, CY 0 [idx]==and EC(Yy 0 )==CY 0 

16. Consistency:∀idx∈Î, C1 [idx]==and EC(Y1 )==C1 

17. y==

18. ∀idx∈Î, EC(C1 [:, idx]) is consistent with ROOTidx, and ROOTidx’s Merkle tree proof is valid.

19. Output accept if all conditions above holds. Otherwise output reject.

참조

참조

1. [GLS+]:Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad S. Wahby. Brakedown: Linear-time and post-quantum snarks for r 1 cs. Cryptology ePrint Archive. https://ia.cr/2021/1043.

2. [XZS 22 ]:Xie T, Zhang Y, Song D. Orion: Zero knowledge proof with linear prover time[C]//Advances in Cryptology–CRYPTO 2022: 42 nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15 – 18, 2022, Proceedings, Part IV. Cham: Springer Nature Switzerland, 2022: 299-328.https://eprint.iacr.org/2022/1010 

3. [BCG 20 ]:Bootle, Jonathan, Alessandro Chiesa, and Jens Groth. "Linear-time arguments with sublinear verification from tensor codes." Theory of Cryptography: 18 th International Conference, TCC 2020, Durham, NC, USA, November 16 – 19, 2020, Proceedings, Part II 18. Springer International Publishing, 2020.

4. Justin Thaler from A16z crypto, Measuring SNARK performance: Frontends, backends, and the future https://a16z crypto.com/measuring-snark-performance-frontends-backends-and-the-future/

5. 텐서 제품 소개: https://blog.csdn.net/chenxy_bwave/article/details/127288938