a16z: Lasso+Jolt는 어떻게 보다 효율적인 SNARK 시스템을 구현합니까?

원래 제목: Lasso, Jolt 및 SNARK 디자인의 최근 발전에 대한 기술 FAQ

원저자:Justin Thaler

원곡: Luccy, BlockBeats

편집자 주: 11월 20일 Ulvetanna의 Ben Diamond와 Jim Posen(DP)은 더 빠른 증명과 더 큰 증명을 결합한 Ligero/Brakedown 커밋 방식과 합계 검사를 기반으로 다항식 IOP를 개선하는 논문을 발표하고 이를 합계 검사 기반과 통합했습니다. Lasso와 같은 SNARK. a16z의 연구 파트너인 Justin Thaler가 해당 기술에 대한 심층적인 분석을 실시한 후, 다양한 연구자들이 기사의 내용에 대해 의문을 제기했습니다.

관련 읽기: a16z: Lasso+Jolt, 빠른 헌신에 대한 새로운 관점

이 FAQ에는 Jolt Prover 성능, DP가 Keccak 및 Grøstl 해시 기능을 선택한 이유, 해시 기반 약정 체계의 보안을 포함한 다양한 질문에 답하기 위해 13개의 질문이 통합되어 있습니다. 또한 이 답변에서는 Lasso와 Jolt 간의 기본 관계, Reed-Solomon 코드 사용의 성능 이점, FRI에 비해 Ligero/Brakedown의 장점, DP의 GF 약속에 대한 요소 경제에 대한 설명도 다루고 있습니다[2].

토론의 초점은 전체 계산의 부울 회로 구현, 특징적인 두 필드의 장점, 재귀 결합을 통한 SNARK 증명의 기술 및 비용 문제와 DP 확약 방식과 타원 곡선 기반 SNARK 결합을 포함합니다. 마지막으로 이 기사에서는 DP의 커밋 방식을 사용하는 SNARK를 Nova와 같은 폴딩 방식과 함께 사용할 수 있는지에 대한 의문도 제기합니다. 이러한 문제에 대한 심층적인 연구는 이 분야의 기술 혁신과 추가적인 개선을 촉진할 것으로 기대됩니다.

Q1: RISC-V 프로그램의 기본 실행과 관련하여 Jolt가 DP 약속을 사용하기 위해 다시 구현되면 Jolt 증명자가 얼마나 빠를 것이라고 생각하십니까?

A：대략적이고 추측적인 추정치가 여기에 제공됩니다. Jolt 증명자는 각 RISC-V CPU 단계가 32비트 데이터 유형과 곱셈 확장을 사용하여 약 800비트의 데이터를 커밋할 것으로 예상합니다. 주목해야 할 두 가지 사항: 첫째, 일부 RISC-V 명령어는 여러 의사 명령어를 통해 처리됩니다. 예를 들어, 나눗셈 명령은 증명자가 나머지를 제공하고 곱셈, 덧셈 및 부등식 검사를 통해 두 가지를 모두 검증하도록 하는 방식으로 작동합니다. 둘째, 이 숫자 추정치는 GF [2128]의 조회 테이블 분해를 분석한 후 약간 조정될 수 있습니다.

DP의 커밋 방식을 사용하고 반복이 병목 현상이 되지 않는다고 가정하면 T-step 계산에서 주요 커밋 비용은 다음과 같습니다.

먼저, 총 약 200Tbyte 규모의 데이터에 Additive FFT가 적용된다. 보다 정확하게는 Ligero/Brakedown 증명자는 길이의 O(√T) 독립 FFT를 실행하는 것보다 O(√T) 크기의 O(√T) 독립 FFT를 수행합니다(총 작업량이 적고 병렬화가 더 잘 가능함). O(T)). 둘째, 약 200테라바이트가 Keccak 또는 SHA 2와 같은 표준 해시 함수를 사용하여 해시됩니다.

경험적으로 DP는 FFT와 해싱이 증명 시간에 거의 동일하다는 것을 발견했습니다.

Keccak 해싱을 사용하면 바이트당 약 70 RISC-V 주기로 추정됩니다. 이는 이러한 작업이 입증되지 않은 RISC-V 프로그램을 실행하는 것보다 약 30,000배 느리다는 것을 나타냅니다. 즉, Jolt 증명자가 RISC-V 프로그램 Ψ를 올바르게 실행했음을 증명하려면 증명자 자체(RISC-V에서 구현됨)에는 Ψ 자체보다 최소 20,000배 더 많은 사이클이 필요합니다.

이러한 약정 비용은 증명자의 병목 현상이 전체 검사 프로토콜에서 수행하는 제한된 도메인 작업에 있을 수 있음을 시사할 만큼 충분히 빠릅니다. 심지어 작은 기능 도메인에 대한 최적화도 허용합니다. 따라서 대략적인 추정으로는 Jolt 증명자(RISC-V에서 구현됨)가 RISC-V 프로그램을 실행하는 것보다 약 50,000배 느릴 것이라고 추측합니다.

전체 계산은 약간 터무니없습니다. Jolt가 배포될 때 증명자 자체가 RISC-V에 구현될 가능성은 거의 없습니다. 하지만 이는 zkVM 증명자의 비용을 추정하는 방법에 대한 일반적인 아이디어를 제공합니다.

50,000배의 속도 저하가 엄청난 것처럼 보이지만 약 18개월 전에 낙관적으로 추정했던 100만배의 오버헤드보다 20배 빠른 속도입니다. 이러한 개선의 주된 이유는 Lasso 및 Jolt로 잠금 해제되는 약속 데이터가 더 작기 때문입니다(그리고 각 약속 값의 크기도 더 작습니다). 나머지는 더 나은 약속 방식(예: 빠른 해시 기능을 사용하고 해시 기반 SNARK에서 작은 크기의 약속 값을 활용하는 능력 향상) 때문입니다.

Q2: DP는 Keccak 및 Grøstl에 대한 빠른 SNARK를 제공합니다. 이러한 해시 함수를 선택한 이유는 무엇입니까? 이러한 기술에 적합한 다른 해시 함수는 무엇입니까? BlockBeats 참고: Grøstl은 암호화 해시 함수입니다.

A：Keccak/SHA 3은 NIST 표준, Ethereum 사전 컴파일 및 Type-1 zkEVM의 주요 병목 현상이기 때문에 확실한 선택입니다. SHA 3는 공식 NIST 표준이고 Keccak은 사전 컴파일된 Ethereum이며 SNARK 비용과 무관합니다.

DP는 Keccak의 많은 장점을 유지하면서 더 빠른 증명으로 이어질 수 있기 때문에 Grøstl을 고려했습니다. 특히, Grøstl은 NIST SHA-3 대회 최종 라운드에 진출하고 AES S-box를 사용했기 때문에 최종적으로 선정되지는 않았지만 강력한 암호 분석 조사를 견뎌냈습니다. AES 가속 지침 AES-NI 덕분에 Grøstl은 Intel 칩의 Keccak보다 훨씬 빠르게 실행됩니다.

DP의 증명자는 Keccak보다 Grøstl에 대해 더 빨라야 합니다. 왜냐하면 Grøstl은 기본적으로 GF에 기본적으로 정의되어 있기 때문입니다[28]. 이는 DP의 증명자가 Keccak보다 더 적은 도메인 요소에 커밋할 수 있음을 의미합니다. (이것이 증명자에게 어떻게 도움이 되는지에 대한 자세한 내용은 Q 9를 참조하십시오.) 전반적으로 Grøstl은 증명자와 칩 모두에서 더 빠르기 때문에 Keccak보다 (재귀) SNARK에 더 적합해야 합니다.

DP의 SNARK는 Keccak 및 Grøstl과 아무런 관련이 없습니다. 이러한 기술은 다른 많은 해시 함수에 적용 가능해야 합니다. 예를 들어 DP는 SHA 2도 Keccak만큼 우수해야 한다고 생각하지만 아직 자세히 연구하지는 않았습니다.

Q3: Lasso/Jolt가 타원곡선 기반의 Commitment 솔루션인 줄 알았는데?

A：아니요, Lasso와 Jolt는 특별히 곡선 기반 약정 제도를 대상으로 하지 않습니다. 하지만 몇 달 전의 경우에는 이전 작업에 비해 곡선 기반 Promise와 함께 사용할 때 장점이 가장 두드러졌습니다. 이는 증명자가 임의의 도메인 요소를 커밋해야 할 때 곡선 기반 약속이 특히 높은 비용을 지불하기 때문에 이를 방지하는 Lasso/Jolt의 새로운 능력은 이러한 약속이 영향을 사용할 때 가장 강력한 성능을 갖기 때문입니다.

간단히 말해서, 약속된 작은 값을 활용하기 위해 곡선 약속을 기반으로 SNARK를 설계한 사람은 아무도 없지만, 이를 활용하는 작은 필드에서 작동하는 해시 기반 약속이 어느 정도 이미 있습니다.

그러나 해시 기반 약속을 사용하더라도 Lasso와 Jolt는 두 가지 측면에서 이전 작업을 개선합니다. 첫째, DP는 해시 기반 커밋이 이전에 알려진 접근 방식보다 더 강력하게 작은 도메인 요소만 커밋함으로써 이점을 얻을 수 있음을 보여줍니다. 예를 들어, 오늘날의 커밋 체계는 32비트 값과 마찬가지로 1비트 값을 커밋하는 데 동일한 증명 비용이 발생하지만 DP의 체계는 1비트 값을 커밋하는 데 거의 32배 더 저렴합니다. 둘째, Lasso와 Jolt는 증명자가 작은 도메인 요소에만 커밋하도록 보장할 뿐만 아니라 증명자가 비합계 검사 기반 SNARK보다 더 적은 도메인 요소에 커밋하도록 보장합니다. 실제로 Jolt에서는 모든 Promise 도메인 요소의 전체 비트 복잡도를 주의 깊게 계산했으며 기존 zkVM에서 수행한 작업보다 훨씬 작은 것을 확인했습니다.

몇 달 전 Lasso/Jolt가 출시되었을 때 또 다른 기술적 문제로 인해 곡선 기반 커밋이 전면에 등장했습니다. 로그 다항식 증명 크기인 FRI를 사용하는 유일한 해시 기반 커밋 방식은 일변량 다항식을 위한 것이고 Lasso/Jolt는 다선형 다항식을 사용합니다. . FRI를 다선형 다항식에 적합한 커밋 방식에 적용하는 여러 변환이 알려져 있지만 이러한 변환은 증명 시간, 증명 크기 또는 우리가 매우 바람직하지 않다고 생각하는 두 가지 측면에서 오버헤드를 추가합니다. BaseFold는 이제 로그 다항식 증명 크기를 사용하여 직접 다중 선형 약속을 허용하지만 결과 증명은 Brakedown보다 느리고 FRI보다 큽니다.

FRI와 달리 Ligero/Brakedown 확약 방식은 다중선형 다항식에 직접 적용되며 매우 빠른 증명을 제공합니다. 그러나 이전에는 검증인이 많은 수의 해시 작업을 수행하여 재귀 비용이 많이 들었기 때문에 증명 크기를 줄이기 위해 재귀를 적용하는 것이 어려웠습니다. DP의 작업은 해시에 대해 더 빠른 SNARK를 제공함으로써 이러한 재귀 비용을 크게 줄일 것입니다.

Q4: 곡선 기반 커밋 방식이 해시 기반 방식보다 빠르다고 하지 않았나요(Laso/Jolt와 같이 작은 값만 약속하는 경우)? 이는 DP의 SNARK에 대한 귀하의 지지와 모순되지 않습니까?

A：첫째, 이전에 말했듯이 타원 곡선 그룹의 기본 도메인에서 작업하는 것이 합리적이기 때문에 해시 기반 SNARK가 최고의 성능 선택이 아닌 몇 가지 중요한 SNARK 응용 프로그램 시나리오가 있습니다. 곡선 기반 약속은 이러한 도메인을 사용할 때 더 빠릅니다. 타원 곡선 암호화 시스템에 대한 진술(블록체인 거래를 승인하는 ECDSA 디지털 서명에 대한 지식 포함)을 증명하는 것이 이 범주에 속합니다.

둘째, 작은 기능 도메인을 합리적으로 사용하는 응용 프로그램에서도 해시 기반 체계와 곡선 기반 체계의 성능 비교는 복잡합니다. 예를 들어, 해시 기반 체계에 사용되는 해시 함수의 속도에 따라 크게 달라집니다. 오늘날 많은(전부는 아님) 프로젝트에서 포세이돈과 같은 느린 해시 함수를 사용하여 재귀를 구현합니다. 이러한 해시 함수를 사용하면 해시 기반 체계는 작은 값(예: Lasso/Jolt)을 커밋할 때 곡선 기반 체계보다 훨씬 느립니다. 빠른 해시 함수를 사용하더라도 더 빠른지 여부는 확실하지 않습니다(이전 의견에서 언급했듯이).

그러나 DP는 해시 기반 확약 속도를 높여 특성 2를 가진 도메인을 사용할 때 더 효율적으로 만들고, 증명자가 FRI와 같은 기존 해시 기반 방식에 비해 작은 크기의 확약 값을 더 잘 활용할 수 있도록 합니다. 따라서 나의 현재 기대는 특성 2를 가진 도메인에서 유한 도메인에 대한 로컬 정의로 달리 입증되지 않는 한 Ligero/Brakedown이 앞으로 나아갈 길이라는 것입니다.

결론적으로 오늘날까지 해시 기반 커밋 체계가 일반적으로 곡선 기반 체계보다 빠른 것으로 간주되는 주된 이유는 Plonk와 같은 인기 있는 SNARK에서는 증명자가 작은 도메인 요소가 아닌 임의의 도메인 요소에 커밋해야 한다는 것입니다. 이 경우 곡선 기반 약속 솔루션은 매우 느립니다. Lasso와 Jolt는 증명자가 임의의 도메인 요소를 커밋할 필요가 없음을 보여주었습니다. 이 경우 비교는 최소한 더 미묘합니다. 오늘날까지 곡선 기반 솔루션은 실제로 더 빨랐지만 DP의 개선으로 상황이 반전되었습니다(대규모 도메인에서 로컬로 정의된 경우 제외).

Q5: 해시 기반 커밋 방식이 덜 안전하다고 말하지 않았나요?

A：FRI 또는 ​​Ligero/Brakedown과 같은 해시 기반 약정 체계에는 본질적으로 안전하지 않은 것이 없습니다. 그러나 프로젝트는 일반적으로 알려진 공격이 가능한 구성에 FRI를 배포하고 FRI에 대한 이러한 알려진 공격이 최적이라고 가정하여 보안보다 성능을 우선시합니다.

Ligero/Brakedown 약속 계획의 한 가지 이점은 FRI에 대한 주요 추측, 즉 Johnson 경계 외부의 인접 매개변수에 대한 추측의 보안이 관련이 없으므로 SNARK 설계자가 보안을 기반으로 한 추측에 이를 사용할 동기가 없다는 것입니다. .

마찬가지로, 저는 오랫동안 SNARK 배포에서 표면적으로 SNARK 친화적인 해시 함수(예: Poseidon)를 사용하는 것에 대해 우려해 왔습니다. 이러한 해시 함수의 보안(가장 오랫동안 사용된 함수라도)은 Keccak과 같은 표준 해시 함수보다 훨씬 덜 정밀한 조사를 받았습니다.

두 경우 모두, 나는 프로젝트가 오늘날의 SNARK 성능 단점을 은폐함으로써 보안을 손상시키고 있다고 생각합니다. 이러한 관행을 제거하는 가장 쉬운 방법은 더 나은 성능의 SNARK를 개발하는 것입니다.

이와 관련하여 SNARK 친화적인 가상 머신(VM)과 이러한 VM을 구현하는 제약 시스템을 수동으로 설계하는 현재 관행은 제약 시스템을 설계하고 시작하기 때문에 심각한 보안 문제(및 개발자 리소스의 막대한 소모)라고 생각합니다. 고급 언어 개발 새 컴파일러에서 사용자 정의 VM으로 어셈블리 코드는 오류가 발생하기 쉬운 특성을 가지고 있습니다. 나는 Jolt가 표준 명령어 세트가 실제로 SNARK와 동일하게 친화적임을 보여줌으로써 이러한 관행을 쓸모없게 만들고 이러한 명령어 세트를 구현하는 수작업 제약 시스템에 대한 필요성이나 인센티브를 제거하기를 바랍니다.

보안에 부정적인 영향을 미치는 관행을 제거하는 방법은 해당 관행을 관련성 없게 만드는 더 높은 성능의 SNARK를 마련하는 것입니다.

Q6: DP는 다항식 확약 체계 구현에 Reed-Solomon 코드를 사용했지만, Brakedown은 모든 코드를 사용할 수 있습니다. 가능한 성능 이점을 위해 다른 코드를 탐색할 가치가 있습니까?

A：예.

Q 7: Ligero/Brakedown은 FRI보다 증명자에게 어떤 면에서 더 유리합니까?

A：매우 작은 값을 커밋할 때 DP의 입증 시간이 크게 향상된 것은 적어도 현재로서는 Ligero/Brakedown의 고유한 기능입니다. 추가로: DP는 작은 값을 커밋할 때 증명 시간을 향상시킬 뿐만 아니라 증명 공간도 향상시킵니다. 이는 특히 해시 기반 SNARK의 경우 주요 병목 현상입니다. 예를 들어, 현재 Polygon의 zkEVM 증명자는 약 1천만 개 가스의 트랜잭션 배치를 처리하는 회로를 증명하기 위해 250GB 이상이 필요합니다.

Ligero/Brakedown은 오류 수정 코드 사용에 있어 더 큰 유연성을 제공합니다. 실제로 작은 값을 약속하는 DP의 많은 개선 사항은 Ligero/Brakedown 내부의 연결 코드를 사용하여 간단히 얻을 수 있습니다.

Reed-Solomon 코드를 사용할 때 Ligero/Brakedown 증명자는 하나의 큰 FFT 대신 여러 개의 작은 FFT를 수행합니다. 이는 FFT 실행 시간을 두 배로 절약하고 병렬화에 더 적합합니다.

기술적인 수준에서 FRI는 FFT와 IFFT를 모두 수행해야 합니다(기술적으로 이는 FRI가 실제로 여러 지점에서 커밋된 다항식을 평가해야 하기 때문입니다). Ligero/Brakedown의 입증자는 IFFT를 건너뛸 수 있습니다(기술적 수준에서 IFFT를 건너뛰는 것은 Ligero/Brakedown의 오류 수정 코드 선택에 대한 뛰어난 유연성에서 비롯됩니다). Reed-Solomon 인플레이션 팩터 2(증명자 시간을 최적화하는 인플레이션 팩터)를 사용하면 증명자 시간을 33% 더 절약할 수 있습니다.

Ligero/Brakedown의 평가 증명에서는 증명자가 추가 Merkle 해싱을 수행할 것을 요구하지 않습니다. 그러나 FRI는 대부분의 FRI 호출이 많은 커밋된 다항식에 대한 증명 평가 비용을 상각하기는 하지만 FRI를 요구합니다.

Q8: DP가 커밋된 GF[2] 요소가 커밋된 GF[2^4] 요소보다 저렴한 커밋된 GF[2^2] 요소보다 저렴하도록 보장하는 방법을 간략하게 설명할 수 있습니까?

A：증명자가 DP의 커밋 체계를 사용하여 여러 값을 커밋하는 데 걸리는 시간은 대략 값을 지정하는 데 필요한 총 비트 수에만 의존합니다. 여기서 b 비트는 0과 2b 사이의 값을 지정하는 데 사용됩니다. DP SNARK의 추가 증명 비용은 해당 비트를 인코딩하는 데 사용되는 필드 요소의 수에 따라 증가합니다(자세한 내용은 아래 #9 참조). DP가 이를 달성하는 방법은 다음과 같습니다.

브레이크다운의 다항식 커밋 방식은 필수 오류 수정 코드를 사용하여 커밋할 값의 하위 벡터를 인코딩합니다. 커밋할 값 묶음이 GF[2]에 있지만 인코딩 자체가 더 큰 도메인 GF[2^16]에서 작동하기를 원한다고 가정합니다. 우리가 이것을 원하는 데에는 기술적인 이유가 많이 있습니다. 실제로 최대 216 길이의 벡터에 일부 인코딩을 적용하려면 필요합니다.

이를 달성하기 위해 모든 GF[ 2 ] 값을 크기 16의 청크로 나누고 16개의 GF[ 2 ] 값의 각 청크를 단일 GF[ 2 ]로 패킹하는 코드 연결을 간단히 사용할 수 있습니다. ^ 16 ] 필드 요소입니다. 이렇게 하면 커밋할 필드 요소 수가 16배로 줄어듭니다. 그런 다음 GF[2^16] 필드에서 작동하는 모든 오류 정정 코드를 적용할 수 있습니다. 이를 외부 코드라고 합니다. 결과 코드워드의 각 기호는 16개의 GF[2] 요소로 언팩될 수 있으며 결과는 GF[2]에 정의된 내부 코드를 사용하여 인코딩됩니다.

효과적으로 연결 방법은 커밋 벡터의 길이(필드 요소 수로 측정)를 16배로 줄이지만 증명자가 패킹 및 언패킹 작업을 수행하고 내부 코드를 적용해야 합니다.

연결된 코드를 사용하여 브레이크다운을 적용하는 이 간단한 접근 방식은 DP 작업의 많은 이점을 실현했습니다. 그러나 DP는 다른 접근 방식을 취하여 더 빠른 증명을 제공합니다(약간의 더 큰 증명 비용으로). 예를 들어, DP의 실용적인 접근 방식은 외부 코드워드의 압축되지 않은 각 기호에 내부 코드를 적용하는 비용을 방지합니다.

Q 9: DP의 커밋 방식을 사용하면 {0, 1}의 값을 커밋하는 것이 매우 저렴하므로, 증명자가 계산에 나타나는 모든 값의 비트별 분해만 커밋하도록 하면 어떨까요? 즉, 부울 회로를 사용하여 전체 계산을 구현하고 SNARK가 회로의 각 입력 비트와 게이트에 완전한 필드 요소를 할당하도록 하는 것은 어떨까요?

A：Keccak에 대한 SNARK에서 DP는 { 0, 1 }의 값에만 증명자 커밋을 수행하지만 이는 일반적인 경우에 반드시 좋은 생각은 아닙니다.

실제로 DP의 커밋 시간은 해당 값이 얼마나 많은 필드 요소에 분산되어 있는지에 관계없이 모든 커밋된 값의 비트 복잡성의 합에 거의 비례합니다. 따라서 1비트 값만 커밋하는 것이 합리적입니다. Keccak의 SNARK 아이디어에서).

그러나 이것이 모든 비용이 투입된 현장 요소의 수와 무관하다는 것을 의미하지는 않습니다. 특히, 공약 체계의 평가 증명 크기는 공약 필드 요소 수(의 제곱근)에 비례합니다.

커밋된 필드 요소 수에 비례하는 또 다른 비용은 DP의 SNARK에 있는 합계 검사 프로토콜의 일부 응용 프로그램에서 합산해야 하는 용어 수입니다. 대략적으로 말하면, x배의 필드 요소를 커밋한다는 것은 합산 검사를 통해 x배의 용어를 합산해야 함을 증명한다는 의미입니다. 이 오버헤드를 완화하는 데 사용할 수 있는 몇 가지 최적화가 있지만 완화가 완벽하지는 않습니다. 즉, 값을 단일 x 비트 필드 요소로 압축한 후 커밋하는 것과 비교하여 x 1비트 값에 대해서도 합계 검사가 여전히 느린 것으로 입증될 것입니다.

DP는 커밋된 후 많은 1비트 값을 단일 필드 요소로 압축하는 합계 검사 기반 프로토콜을 제공함으로써 많은 1비트 값을 커밋하는 후자의 비용을 완화합니다. 이를 통해 많은 커밋된 값에 대해 너무 많은 합계 확인 증명 시간을 지불하는 비용을 기술적으로 피할 수 있으면서도 여전히 이점을 누릴 수 있습니다(특히 비트 분해 커밋이 합계 확인으로 입증된 경우 비트 AND와 같은 특정 작업 수행). 입증된 경우 추가 약정 비용이 발생하지 않습니다.)

Q1 0: 두 가지 특성을 지닌 분야를 활용한 DP의 구체적인 장점은 무엇입니까?

A：많은 것들이 있는데, 여기에 몇 가지 예가 있습니다.

DP는 타워 현장 건설을 광범위하게 활용했습니다. 특성 2가 있는 필드의 맥락에서 이는 GF[2]의 2차 확장으로 GF[22]를 구성한 다음 GF[4]의 2차 확장으로 GF[24]를 구성하고 GF[28]를 구성하는 것을 의미합니다. GF[ 24 ]의 2차 확장 등. 특히 두 가지 특성을 지닌 분야에서는 매우 효율적인 타워 건설이 존재하는 것으로 알려져 있다.

합계 검사 프로토콜은 다변량 다항식 g에 대해 ∑x∈ 0, 1 ^ng(x)를 계산합니다. 부울 하이퍼큐브 {0, 1 }n(및 해당 하위 큐브)의 크기는 2의 거듭제곱이므로 하위 필드가 하위 큐브와 잘 정렬됩니다. DP는 이를 활용하여 많은 작은 필드 요소를 더 큰 확장 필드의 단일 요소로 쉽게 패키징할 수 있도록 합니다.

DP는 현재 Ligero/Brakedown 다항식 확약 체계에서 Reed-Solomon 코딩을 사용합니다. 효율적인 리드-솔로몬 코딩을 위해서는 가산형 FFT가 필요합니다. 이는 2가지 특성을 갖는 분야에서는 매우 효율적이지만 다른 분야에서는 그다지 좋지 않습니다. 그러나 다른 인코딩을 사용하면 FFT의 필요성을 완전히 피할 수 있습니다.

특성 2를 갖는 필드는 실제 하드웨어에서 잘 처리됩니다. 실제 컴퓨터는 2의 거듭제곱 크기의 데이터 유형을 기반으로 합니다. 패딩 없이 레지스터, 캐시 라인 등에 가장 큰 정보를 완벽하게 넣을 수 있습니다. Intel은 GF에서 특히 빠른 산술 연산을 수행하기 위해 칩 기본 명령어(Galois Field New Instructions[GFNI])도 내장했습니다. 타워 구성을 사용할 때 k > 8인 경우에도 매우 빠른 GF[2k] 산술을 구현하는 데 사용할 수 있습니다.

Q1 1: SNARK 증명을 자신과 재귀적으로 결합하는 DP의 약속 체계를 사용하면 SNARK 증명의 제약이 덜해질 수 있습니까?

A：예, Ligero/Brakedown 약정을 사용하는 SNARK의 재귀 임계값은 상대적으로 높습니다. 재귀 임계값은 검증자에게 Brakedown/Ligero 기반 SNARK를 재귀적으로 적용하여 더 짧은 증명을 생성할 수 없도록 하는 증명의 크기를 나타냅니다. 재귀 임계값은 몇 MB 정도일 것으로 예상됩니다.

더 작은 증거를 얻고 싶다면 SNARK를 다른 더 작은 증거와 결합하면 얻을 수 있다고 생각합니다. 자세한 내용은 Q1 2를 참조하십시오. 이 가정이 틀린 것으로 밝혀지면 Binius의 실패가 아니라 오늘날 인기 있는 SNARK의 확장성에 대한 비난으로 보아야 합니다. 몇 MB의 데이터가 합리적인 시간 내에 해시되었음을 증명할 수 없다면 어떻게 확장 가능하다고 말할 수 있습니까?

어쨌든, 증명 크기를 줄이는 것 외에도 빠른 재귀 구성을 위한 다른 중요한 이유가 있습니다. 가장 중요한 것은 증명 공간 요구 사항을 제어하는 ​​핵심 도구라는 것입니다. (비재귀적) SNARK는 증명을 위해 많은 공간을 차지하므로 사람들은 큰 계산을 작은 덩어리로 나누고, 각 덩어리를 별도로 증명하고, 재귀 증명을 사용하여 덩어리를 함께 연결합니다. 표준 해시 함수(예: Keccak)에 대한 DP의 빠른 SNARK를 사용하면 증명 크기가 다소 크더라도 이러한 재귀 증명을 신속하게 완료할 수 있습니다.

Q1 2: 체인에 증명을 게시하기 전에 검증자의 비용을 줄이기 위해 DP의 약속 체계를 타원 곡선 기반 SNARK(예: Plonk 또는 Groth 16)와 결합한다고 가정해 보겠습니다. 비로컬 필드 산술이 관련되어 있다는 증거가 필요하지 않습니까? DP의 검증자는 GF[2^128]에서 작동하는 반면 곡선 기반 SNARK는 대규모 소수 필드를 사용하기 때문입니다.

A：예, 이는 잠재적인 문제이지만 해결책을 찾을 수 있다고 믿습니다.

한 가지 가능성은 먼저 더 짧은 증명이 포함된 해시 기반 다항식 확약 체계(아마도 FRI, 다중 선형 다항식 확약 체계 또는 BaseFold로 변환됨)를 사용하여 SNARK와 결합한 다음 곡선 기반 SNARK와 결합하는 것입니다. FRI는 기능 2의 필드에서 기본적으로 실행될 수 있으며 실제로 이 사례는 원래 FRI 논문에서 고려되었습니다. 이러한 필드 사용에 대한 현재 대중적인 SNARK 제한은 FRI 자체와 달리 합계 검사를 기반으로 하지 않는 다항식 IOP의 사용에서 비롯됩니다.

이는 비로컬 필드 산술 문제를 제거하지는 않지만 충분히 큰 다항식의 경우 FRI 유효성 검사기가 더 적은 총 작업을 수행하고 특히 Ligero/Brakedown 유효성 검사기가 수행하는 것보다 적은 필드 작업을 수행하기 때문에 크게 완화될 수 있습니다. .

Q1 3: DP의 커밋 방식을 사용하는 SNARK를 Nova와 같은 폴딩 방식과 함께 사용할 수 있나요?

A：이는 Q1 2와 동일한 문제를 겪게 됩니다. 즉, 폴딩 방식은 일반적으로 큰 소수차 필드에서 정의되는 타원 곡선을 사용하는 반면 DP의 커밋션 방식은 2의 거듭제곱 크기의 필드를 사용합니다.

나는 접는 방식에 상당한 진전이 있을 것으로 기대하며, 이는 향후 SNARK 디자인에서 중요한 역할을 할 것입니다. 그러나 매우 작은 기능이 있는 필드에서는 해시 기반 SNARK와 잘 결합되지 않는 경우가 있을 수 있습니다.

현재로서는 큰 필드에 대한 로컬 정의와 관련된 명령문이 포함되거나 증명 공간이 중요한 경우(Nova와 같은 폴딩 계획이 다른 SNARK보다 증명자 공간에서 훨씬 우수함) 타원 곡선 기반 약속 및 접기 방식을 사용해야 합니다. 큰 계산을 다른 SNARK보다 훨씬 작은 부분으로 나눌 수 있습니다. 다른 경우에는 특히 작은 기능 필드의 경우 해시 기반 체계를 사용해야 합니다.

마찬가지로, 향후 폴딩 방식이 추가로 개발되면 해시 기반 방식을 넘어설 수도 있습니다. 실제로 Nova는 이미 일부 벤치마크에서 현재 세대의 해시 기반 SNARK보다 빠릅니다(현재 해시 기반 SNARK가 곡선 기반 SNARK보다 빠르다는 주장이 많이 있지만).

원본 링크