이 기사의 출처는 다음과 같습니다. a 16 z, 원작자: Justin Thaler, Odaily 번역가 Jessica가 편집함.

8월 10일, 16 z 암호화폐는 널리 배포된 도구 체인의 성능을 10배 이상 향상시킬 수 있는 SNARK 디자인에 대한 새로운 접근 방식을 함께 나타내는 새로운 SNARK 기반 도구 Lasso 및 Jolt를 출시했습니다. 개발자 경험을 제공하고 감사를 더 쉽게 만듭니다.

SNARK(Succinct Non-Interactive Argument of Knowledge)는 누구나 신뢰할 수 없는 검증자에게 특정 속성을 충족하는 증인을 알고 있음을 증명할 수 있는 암호화 프로토콜입니다.

• Web 3의 두드러진 사용 사례는 L2가 일련의 거래를 승인하는 디지털 서명을 알고 있음을 L1에 증명함으로써 L1 네트워크에서 서명 자체를 저장하고 확인할 필요가 없으므로 확장성을 향상시키는 것입니다.

• 블록체인 외부 애플리케이션에는 신뢰할 수 없는 하드웨어 장치에서 생성된 모든 출력의 유효성을 신속하게 입증하여 사용자가 신뢰할 수 있도록 보장하는 것이 포함됩니다. 개인은 신뢰할 수 있는 기관이 생년월일을 공개하지 않고도 연령 제한 콘텐츠에 액세스할 수 있을 만큼 나이가 있음을 증명하는 자격 증명을 발급했음을 영지식 방식으로 증명할 수 있습니다. 네트워크를 통해 암호화된 데이터를 보내는 사람은 누구나 추가 세부 정보를 공개하지 않고도 해당 데이터가 네트워크 정책을 준수한다는 사실을 관리자에게 증명할 수 있습니다.

많은 SNARK가 검증자에게 여전히 매력적인 비용으로 남아 있지만, SNARK는 일반적으로 검증자 계산에서 약 6배 정도의 오버헤드를 발생시킵니다. 증명자가 부담하는 추가 작업은 고도로 병렬화되지만 수백만 번의 오버헤드로 인해 SNARK의 적용 범위가 심각하게 제한됩니다.

더 많은 성능 이점을 갖춘 SNARK는 L 2 속도를 높이고 개발자가 아직 구상하지 않은 애플리케이션을 잠금 해제할 수 있게 해줍니다.이것이 바로 우리가 두 가지 새로운 관련 기술을 도입하는 이유입니다: 증명 비용을 크게 증가시킬 수 있는 새로운 조회 매개변수인 Lasso, 소위 zkVM 및 보다 광범위한 프런트엔드 디자인을 위한 새로운 프레임워크를 제공하기 위해 Lasso를 사용하는 Jolt. 디자인 SNARK . 함께 SNARK 디자인의 성능, 개발자 경험 및 감사 가능성을 향상시켜 결과적으로 웹 3의 빌드를 향상시킵니다.

보조 제목

매개변수 찾기, Lasso 및 Jolt

SNARK 프런트 엔드는 컴퓨터 프로그램을 SNARK 백엔드가 수집할 수 있는 회로로 변환하는 컴파일러입니다.(참고: 회로는 사용 가능한 유일한 원시 연산이 덧셈과 곱셈뿐인 극도로 제한된 계산 모델입니다.)

최신 SNARK 디자인의 핵심 도구는 조회 매개변수라는 프로토콜입니다. 이를 통해 신뢰할 수 없는 증명자가 큰 벡터를 암호화 방식으로 제출한 다음 해당 벡터의 각 항목이 미리 결정된 테이블 중간에 포함되어 있음을 증명할 수 있습니다. 조회 매개변수는 작은 덧셈과 곱셈으로 자연스럽게 계산되지 않는 연산을 효율적으로 처리하여 회로를 작게 유지하는 데 도움이 될 수 있습니다.

그러나 작년에 이더리움 재단의 Barry Whitehat이 말했듯이 조회 매개변수만 사용하여 회로를 효율적으로 정의할 수 있다면 도구와 회로가 더 간단해질 것입니다. 우리가 설계한 회로는 조회만 수행합니다. 시간이 지남에 따라 조회 매개변수는 거의 모든 것에 대해 다항식 제약 조건보다 더 효율적이 될 것입니다.

이 비전은 개발자가 프로그램을 다항식 제약 조건으로 컴파일하는 특수 도메인별 언어를 사용하여 프로그램을 작성하거나 제약 조건을 직접 직접 코딩하여 SNARK를 배포하는 오늘날의 작동 방식과 극명한 대조를 이룹니다. 이 툴체인은 작업량이 많고 안전에 중요한 버그가 침투할 수 있는 많은 표면적을 제공합니다. 복잡한 도구와 회로를 사용하더라도 SNARK의 성능은 여전히 ​​느리므로 적용 가능성이 제한됩니다.

Lasso와 Jolt는 성능, 개발자 경험, 감사 가능성이라는 세 가지 주요 문제를 모두 해결합니다.특이점을 찾는 비전이 함께 실현됩니다. Lasso와 Jolt는 또한 SNARK 디자인에서 인정된 많은 지혜를 재고하도록 강요합니다.

보조 제목

SNARK 디자인 배경: 왜 그렇게 느린가요?

대부분의 SNARK 백엔드는 증명자가 다항식 커밋 방식을 사용하여 회로의 각 게이트 값을 암호화 방식으로 커밋하도록 합니다. 그런 다음 증명자는 제출된 값이 실제로 증인 확인 프로그램의 올바른 실행과 일치함을 증명합니다.

나는 할 것이다다항식 확약 방식의 증명 작업을 확약 비용이라고 합니다.SNARK는 다항식 약속 체계로 인해 추가 증명 비용이 발생합니다. 하지만약정 비용으로 인해 병목 현상이 발생하는 경우가 많습니다.Lasso와 Jolt도 마찬가지입니다. 약정 비용이 주요 증명 비용이 아닌 곳에서 SNARK를 설계한다고 해서 다항식 약정 방식이 저렴하다는 의미는 아닙니다. 오히려 이는 다른 비용이 예상보다 높다는 것을 의미합니다.

직관적으로 약속의 목적은 증명 시스템의 단순성을 암호학적으로 안전하게 높이는 것입니다. 증명자가 값의 큰 벡터를 제출하는 것은 일반적인 증명 시스템이 전체 증인을 검증자에게 보내는 것과 마찬가지로 대략 증명자가 전체 벡터를 검증자에게 보내는 것과 같습니다. 확약 체계는 검증인이 실제로 전체 증인을 받도록 강요하지 않고도 이를 달성할 수 있습니다. 즉, SNARK 설계에서 확약 체계의 목적은 검증인 비용을 제어하는 ​​것입니다.

그러나 이러한 암호화 방법은 증명자에게 매우 비용이 많이 들며, 특히 SNARK가 다항식 약속 체계 외부에서 사용하는 정보 이론적 방법과 비교할 때 더욱 그렇습니다. 정보이론적 방법은 유한장 연산에만 의존합니다. 그리고 현장 작업은 임의의 필드 요소를 제출하는 데 필요한 시간보다 훨씬 빠릅니다.

보조 제목

Lasso와 Jolt가 중요한 이유

Lasso는 증명자가 이전 작업보다 점점 더 작은 값을 약속하는 새로운 조회 매개변수입니다.속도가 20배 이상 향상될 수 있습니다., 2배에서 4배의 속도 향상은 더 적은 수의 제출된 값에서 비롯되고 또 다른 10배의 속도 향상은 Lasso에 제출된 모든 값이 작기 때문에 발생합니다. 이전의 많은 조회 매개변수와 달리 Lasso(및 Jolt)는 공간 집약적이고 대규모 인스턴스의 병목 현상이 될 수 있는 FFT도 방지합니다.

게다가 Lasso는 테이블이 구조화되어 있는 한(정확한 기술적 의미에서) 거대한 테이블에서도 작동합니다. 이러한 테이블은 명시적으로 구현하기에는 너무 크지만 Lasso는 실제로 액세스하는 테이블 요소에 대해서만 비용을 지불합니다. 특히 이전 조회 매개변수와 비교하여 테이블이 구조화되어 있으면 어느 쪽도 테이블의 모든 값을 암호화된 형식으로 커밋할 필요가 없습니다.

Lasso는 분해성과 LDE 구조라는 두 가지 구조적 개념을 활용합니다.(LDE는 Low Degree Extended Polynomial이라는 기술 개념의 약어입니다.)보조 제목

Jolt

Jolt(Just One Lookup Table)는 Lasso의 거대한 조회 테이블 사용 능력으로 인해 잠금 해제된 새로운 프런트엔드입니다.Jolt는 ISA(명령어 세트 아키텍처)라고도 알려진 가상 머신/CPU 추상화를 대상으로 합니다.。이 추상화를 지원하는 SNARK를 zkVM이라고 합니다.. 예를 들어 RISC-Zero 프로젝트도 대상으로 하는 RISC-V 명령어 세트(곱셈 확장 포함)를 생각해 보세요. 이는 SNARK를 염두에 두지 않고 컴퓨터 아키텍처 커뮤니티에서 개발한 인기 있는 오픈 소스 ISA입니다.

보조 제목

SNARK 디자인에서 인정된 지혜 재검토

Lasso와 Jolt는 또한 SNARK 디자인에서 인정된 지혜 중 일부를 전복시킵니다.

#1. 대형 SNARK는 낭비입니다. 일반적으로 대규모에 적용할 수 있는 타원 곡선 기술을 피하므로 모든 사람은 FRI, Ligero, Brakedown 또는 변형을 사용해야 합니다.

여기서 필드 크기는 SNARK 증명에 나타나는 숫자의 크기와 대략적으로 일치합니다. 매우 큰 수의 덧셈과 곱셈은 비용이 많이 들기 때문에 큰 필드의 SNARK가 낭비라는 생각은 결코 큰 수를 갖지 않는 프로토콜을 설계하기 위해 노력해야 한다는 것을 의미합니다. MSM 기반 약속은 일반적으로 대규모 필드(~2,256 크기)에 대해 정의되는 타원 곡선을 사용하므로 이러한 약속은 성능이 좋지 않다는 평판을 얻습니다.

작은 필드를 사용하는 것이 적합한지 여부(옵션이더라도)는 주로 애플리케이션에 따라 다릅니다. Lasso와 Jolt는 더욱 발전합니다. 그들은 MSM 기반 확약 체계를 사용하더라도 증명자의 작업이 필드 크기와 거의 독립적일 수 있음을 보여줍니다. 이는 MSM 기반 커밋의 경우 커밋된 값의 크기가 해당 값이 있는 필드의 크기보다 더 중요하기 때문입니다.

기존 SNARK는 증명자가 많은 임의 필드 요소를 커밋하도록 만듭니다. 예를 들어 Plonk라는 인기 있는 SNARK 백엔드의 증명자는 회로 게이트당 약 7개의 무작위 필드 요소(및 기타 비 무작위 필드 요소)를 커밋합니다. 이러한 랜덤 필드 요소는 입증된 계산에 나타나는 모든 값이 작더라도 클 수 있습니다.

반면 Lasso와 Jolt는 증명자가 작은 값만 제출하도록 요구합니다(Lasso의 증명자는 이전 조회 매개변수보다 적은 값도 제출함). 이는 MSM 기반 구성표의 성능을 크게 향상시킵니다. 최소한 Lasso와 Jolt는 증명자 성능이 중요한 경우 커뮤니티가 MSM 기반 약속을 포기해야 한다는 개념을 해체해야 합니다.

#2 명령어 세트가 단순할수록 zkVM이 더 빨라집니다.

Jolt의 (명령어별) 복잡성은 각 명령어에 대한 평가 테이블이 분해 가능한 한 명령어의 입력 크기에만 의존합니다. Jolt는 놀랍도록 복잡한 명령어, 특히 모든 RISC-V를 분해할 수 있음을 보여주었습니다.

이는 단순한 가상 머신(zkVM)이 필연적으로 더 작은 회로와 더 빠른 증명자(VM의 모든 단계)로 이어진다는 일반적인 믿음과 반대됩니다. 이는 SNARK 친화적으로 특별히 설계된 Cairo VM과 같은 특히 단순한 zkVM 뒤에 있는 지침 동기입니다.

실제로 더 간단한 가상 머신의 경우 Jolt는 이전 SNARK보다 증명자에 대한 약정 비용을 더 낮춥니다. 예를 들어 Cairo VM 실행의 경우 SNARK 증명자는 VM의 각 단계에서 51개의 필드 요소를 제출합니다. Cairo가 배포한 SNARK는 현재 251비트 필드에서 작동합니다(63비트는 SNARK가 사용할 수 있는 필드 크기의 엄격한 하한임). Jolt의 증명자는 RISC-V CPU에 대해 단계당 최대 60개의 필드 요소(64비트 이상의 데이터 유형 정의)에서 작동합니다. 제출된 필드 요소가 작다는 사실을 고려하면 Jolt 증명자 비용은 6개의 무작위 256비트 필드 요소를 제출하는 비용과 대략 동일합니다.

#3 대규모 계산을 작은 덩어리로 나누어도 성능 저하가 없습니다.

이러한 관점을 바탕으로 오늘날의 프로젝트는 대형 회로를 작은 블록으로 분해하고, 각 블록을 개별적으로 증명하고, SNARK를 통해 결과를 재귀적으로 집계합니다. 이러한 배포에서는 이 접근 방식을 사용하여 널리 사용되는 SNARK의 성능 병목 현상을 완화합니다. 예를 들어, FRI 기반 SNARK는 작은 회로의 경우에도 100GB에 가까운 증명 공간이 필요합니다. 또한 SNARK가 대형 회로에 동시에 적용될 경우 병목 현상이 발생할 수 있는 초선형 작업인 FFT가 필요합니다.

현실은 일부 SNARK(예: Lasso 및 Jolt)가 규모의 경제를 나타냅니다(현재 배포된 SNARK에서 발견되는 규모의 불경제가 아님). 이는 증명되는 진술이 클수록 직접 증인 확인(즉, 정확성을 보장하지 않고 증인 회로를 평가하는 데 필요한 작업)에 비해 증명자 오버헤드가 작아진다는 것을 의미합니다. 기술적인 측면에서 규모의 경제는 두 가지 측면에서 발생합니다.

n 크기의 MSM에 대한 Pippenger 속도 향상: 순진한 알고리즘에 비해 log(n ) 요소 개선. n이 클수록 개선 효과가 커집니다.

Lasso와 같은 조회 매개변수에서 증명자는 조회 테이블의 크기에 따라 달라지지만 조회된 값의 개수와는 아무런 관련이 없는 일회성 비용을 지불합니다. 일회성 증명 비용은 테이블에 대한 모든 조회에 대해 분할 상환됩니다. 블록이 클수록 더 많은 조회가 이루어지며, 이는 더 나은 상환액을 의미합니다.

오늘날 대규모 회로를 처리하는 데 널리 사용되는 방법은 사물을 가능한 가장 작은 조각으로 분해하는 것입니다. 각 부분의 크기에 대한 주요 제약은 재귀 집계 증명이 증명자에게 병목 현상이 될 정도로 너무 작을 수 없다는 것입니다.

Lasso와 Jolt는 본질적으로 반대되는 접근 방식을 제안합니다. 사람들은 규모의 경제가 있는 SNARK를 사용해야 합니다. 그런 다음 대규모 계산을 가능한 한 큰 조각으로 나누고 결과를 재귀적으로 분석합니다. 각 조각의 크기에 대한 주요 제한은 조각이 커질수록 커지는 증명 공간입니다.

#4 효율적인 SNARK를 위해서는 높이 제약이 필요합니다.

Jolt는 R 1 CS를 중간 표현으로 사용합니다. Jolt에서 높이 또는 사용자 정의 제약 조건을 사용해도 이점이 없습니다. Jolt에서 증명자 비용의 대부분은 조회를 당연한 것으로 간주하는 결과 제약 시스템의 만족성을 증명하는 대신 Lasso 매개변수를 찾는 데 있습니다.

Jolt는 보편적이므로 다재다능함을 잃지 않습니다. 따라서 이는 오늘날 인기 있는 SNARK에서 향상된 성능을 끌어내기 위한 노력의 일환으로 개발자가 설계 높이 제약(종종 수동으로 지정)에 집중하는 것에 대응합니다.

물론 일부 컨텍스트에서는 여전히 높이나 사용자 지정 제약 조건의 이점을 누릴 수 있습니다. 중요한 예는 5도 제약으로 약정 비용을 약 3배로 줄일 수 있는 Minroot VDF입니다.

#5 희소 다항식 커밋 방식은 비용이 많이 들기 때문에 가능하면 피해야 합니다.

이는 최근 도입된 CCS라는 구속 시스템과 이를 지원하는 SNARK(Spartan 및 Marlin)에 대한 주요 비판입니다. CCS는 오늘날 실제로 널리 퍼져 있는 모든 구속 시스템을 명확하게 일반화한 것입니다.

이러한 비판은 근거가 없습니다. 실제로 Lasso와 Jolt의 기술 핵심은 Spartan - Spark의 희소 다항식 커밋 방식입니다. Spark 자체는 모든 (비희소) 다항식 커밋 방식을 희소 다항식을 지원하는 방식으로 변환하는 일반적인 변환입니다.

Lasso는 증명자가 작은 값에만 커밋하도록 보장하기 위해 Spark를 최적화하고 확장하지만 이러한 최적화가 없더라도 비판은 정당화되지 않습니다. 실제로 Spartan의 증명자는 SNARK(예: 희소 다항식 약속을 피하는 Plonk)보다 적은 수의 (임의) 필드 요소를 약속합니다.

Spartan의 접근 방식은 특히 반복적인 구조를 가진 회로의 경우 추가적인 성능 이점을 제공합니다. 이러한 회로의 경우 추가 게이트는 스파르탄 증명자의 암호화 작업에 추가되지 않습니다. 이 작업은 제약 조건의 수가 아니라 주어진 제약 시스템의 변수 수에 따라 증가합니다. Plonk와 달리 Spartan 증명자는 동일한 변수에 대해 여러 개의 서로 다른 사본을 제출할 필요가 없습니다.

우리는 Lasso와 Jolt가 SNARK 설계 방식을 극적으로 변화시켜 성능과 감사 가능성을 향상시킬 것이라고 낙관하고 있습니다. 이는 증명자의 약속 비용을 최소화할 수 있는 놀라운 능력을 갖춘 핵심 도구입니다.