a16z crypto에서 새로 출시한 두 가지 SNARK 도구에 대한 자세한 설명

원문 제목：Approaching the 'lookup singularity': Introducing Lasso and Jolt
편집: 취원, ChainCatcher

SNARK는 신뢰할 수 없는 검증자에게 특정 속성을 충족하는 "증거"(witness)를 알고 있음을 증명할 수 있게 해주는 암호 프로토콜입니다. SNARK의 Web3에서의 두드러진 응용은 L2 롤업이 L1 블록체인에 그들이 일련의 거래를 승인하는 디지털 서명을 알고 있음을 증명하는 것입니다. 이렇게 하면 서명 자체가 L1에 저장되고 검증될 필요가 없어져 확장성이 향상됩니다.

SNARK의 블록체인 외부 응용에는 속도가 빠르지만 신뢰할 수 없는 하드웨어 장치가 생성한 모든 출력의 유효성을 증명하여 사용자가 이를 신뢰할 수 있도록 보장하는 것이 포함됩니다. 개인은 제로 지식 방식으로 신뢰 기관이 그들에게 발급한 증명서를 증명할 수 있습니다. 예를 들어, 그들의 생년월일을 공개하지 않고도 연령 제한 콘텐츠에 접근할 수 있을 만큼 나이가 충분하다는 것을 증명할 수 있습니다. 네트워크를 통해 암호화된 데이터를 전송하는 누구나 관리자에게 해당 데이터가 네트워크 정책에 부합함을 증명할 수 있으며, 추가 세부 정보를 공개할 필요가 없습니다.

많은 SNARK가 증명자(prover)에게 비용이 낮지만, SNARK는 일반적으로 검증 계산에서 약 여섯 배의 오버헤드를 발생시킵니다. 검증자가 감당해야 하는 추가 작업은 높은 수준의 병렬화가 가능하지만, 백만 배의 계수 오버헤드는 SNARK의 응용을 심각하게 제한합니다.

더 강력한 SNARK는 L2의 속도를 높일 수 있으며, 구축자가 아직 구현되지 않은 응용을 잠금 해제할 수 있게 합니다. 따라서 우리는 두 가지 관련 기술을 출시했습니다: Lasso는 증명자 비용을 크게 줄일 수 있는 새로운 조회 매개변수이며; Jolt는 Lasso 기술을 사용하여 zkVM 및 기타 프론트엔드 설계를 위한 SNARK 설계의 새로운 프레임워크를 제공합니다. 이들은 함께 SNARK 설계의 성능, 개발자 경험 및 감사 가능성을 향상시켜 web3의 구축을 촉진합니다.

인기 있는 SNARK 도구 체인 halo2의 조회 매개변수와 비교할 때, Lasso의 초기 구현은 속도가 10배 이상 향상된 것으로 입증되었습니다. 우리는 Lasso 코드베이스가 완전히 최적화되면 속도가 약 40배 향상될 것으로 예상합니다. Jolt는 Lasso 기반의 더 많은 혁신을 포함하고 있으며, 우리는 그것이 기존 zkVM과 유사하거나 더 높은 속도를 달성할 수 있기를 바랍니다.

조회 매개변수, Lasso 및 Jolt

SNARK 프론트엔드(SNARK frontend)는 컴퓨터 프로그램을 회로로 변환하고 SNARK 백엔드에서 수용하는 컴파일러입니다. 회로는 원시 연산이 단순히 덧셈과 곱셈인 극히 제한된 계산 모델입니다.

현대 SNARK 설계의 핵심 도구 중 하나는 조회 매개변수(lookup argument)로, 이는 신뢰할 수 없는 증명자가 암호화된 방식으로 대규모 벡터를 제출한 다음 해당 벡터의 각 항목이 특정 미리 정해진 테이블에 포함되어 있음을 증명할 수 있게 해주는 프로토콜입니다. 조회 매개변수는 적은 수의 덧셈과 곱셈으로 자연스럽게 계산할 수 없는 연산을 효과적으로 처리할 수 있어 회로가 소형 규모를 유지하는 데 기여합니다.

이더리움 재단의 Barry는 "조회 매개변수만으로 효율적으로 회로를 정의할 수 있다면 더 간소화된 도구와 회로를 가져올 수 있다"는 아이디어를 제안했습니다. 즉, "조회 특이점"을 실현할 수 있으며, 이 경우 우리는 "조회만 수행하는 회로를 설계할 수 있다"는 것입니다. 이 방식은 거의 모든 면에서 다항식 제약보다 우수합니다.

이 비전은 오늘날의 작업 방식과 뚜렷한 대조를 이룹니다. 오늘날의 작업 방식에서 개발자는 SNARK를 배포하기 위해 특수 목적의 도메인 특정 언어(프로그램을 다항식 제약으로 컴파일하는)로 프로그램을 작성하거나 직접 수동으로 제약을 코딩합니다. 이러한 도구 체인은 많은 인력과 자원을 소모하여 보안에 중요한 취약점이 발생할 확률이 높습니다. 복잡한 도구와 회로를 사용하더라도 SNARK는 여전히 느리며, 이는 그 응용을 제한합니다.

Lasso와 Jolt는 성능, 개발자 경험 및 감사 가능성이라는 세 가지 주요 문제를 모두 해결했습니다. 나는 이들이 함께 조회 특이점의 비전을 실현할 것이라고 믿습니다. Lasso와 Jolt는 또한 SNARK 설계의 많은 공진리 문제에 대해 다시 생각하게 합니다. 필요한 배경 지식을 소개한 후, 이 글에서는 SNARK 성능에 대한 몇 가지 일반적인 관점을 재검토하고 Lasso와 Jolt와 같은 혁신 기술에 따라 이러한 관점을 어떻게 업데이트할 수 있는지 설명할 것입니다.

SNARK 설계 배경: 왜 이렇게 느린가?

대부분의 SNARK 백엔드는 검증자가 회로의 각 게이트 값에 대해 암호화된 약속을 하도록 하며, 이 방법을 다항식 약속 방식이라고 합니다. 그런 다음 증명자는 약속된 값이 증거 검증 프로그램의 올바른 실행을 충족함을 증명합니다.

나는 다항식 약속 방식에서 오는 증명자의 작업을 약속 비용(commitment cost)이라고 부릅니다. SNARK에는 다항식 약속 방식 외부에서 발생하는 추가 증명자 비용이 있습니다. 그러나 약속 비용은 종종 병목 현상이 됩니다. Lasso와 Jolt의 경우도 마찬가지입니다. SNARK를 설계할 때 약속 비용이 주요 증명자 비용을 구성하지 않는다면, 이는 다항식 약속 방식의 비용이 낮다는 것을 의미하지 않으며, 오히려 다른 비용이 그들이 마땅히 가져야 할 수준보다 높다는 것을 의미합니다.

직관적으로 약속의 목적은 암호화 방법을 통해 증명 시스템의 간결성을 안전하게 증가시키는 것입니다. 증명자가 큰 값 벡터에 대해 약속을 할 때, 이는 증명자가 전체 벡터를 검증자에게 보내는 것과 유사합니다. 미세한 증명 시스템(trivial proof system)이 전체 증거를 검증자에게 보내는 것과 같습니다. 약속 방식은 검증자가 실제로 전체 증거를 수신해야 한다는 강제를 필요로 하지 않으며, 이는 SNARK 설계에서 약속 방식의 목적이 검증자 비용을 제어하는 것임을 의미합니다.

그러나 이러한 암호화 방법은 증명자에게 매우 비쌉니다. 특히 SNARK가 다항식 약속 방식 외부에서 사용하는 정보 이론적 방법과 비교할 때 더욱 그렇습니다. 정보 이론적 방법은 유한체 연산에만 의존합니다. 한 번의 필드 연산 속도는 임의의 필드 요소에 대한 약속을 수행하는 데 필요한 시간보다 몇 배 빠릅니다.

사용되는 다항식 약속 방식에 따라 약속 계산은 다중 거듭제곱(다중 스칼라 곱셈 또는 MSM이라고도 함) 또는 FFT 및 머클 해시를 포함합니다. Lasso와 Jolt는 어떤 다항식 약속 방식도 사용할 수 있지만, MSM 기반 방식(예: IPA/Bulletproofs, KZG/PST, Hyrax, Dory 또는 Zeromorph)을 사용할 때 추가 비용이 발생합니다.

Lasso와 Jolt가 중요한 이유는 무엇인가?

Lasso는 새로운 조회 매개변수 방법으로, 이전 방법에 비해 증명자가 약속하는 값이 더 적고 더 작습니다. 상황에 따라 이는 속도를 20배 이상 향상시킬 수 있으며, 그 중 2배에서 4배는 더 적은 약속 값에서 오고, 나머지 10배는 Lasso에서 모든 약속 값이 작기 때문입니다. 이전의 많은 조회 매개변수와 달리 Lasso(및 Jolt)는 FFT를 피할 수 있으며, FFT는 많은 공간을 필요로 하여 대규모 인스턴스에서 병목 현상을 초래할 수 있습니다.

또한, 테이블이 "구조화"되어 있는 한(정확한 기술적 의미에서), Lasso는 심지어 거대한 테이블(예: 크기가 2^128에 달하는)에도 적용될 수 있습니다. 테이블 크기가 너무 클 경우, 누구도 이를 명확하게 구체화할 수 없지만, Lasso는 실제로 접근하는 테이블 요소에 대해서만 비용을 지불합니다. 주목할 점은, 테이블이 구조화되어 있다면, 어느 쪽도 테이블의 모든 값에 대해 암호화된 약속을 할 필요가 없다는 것입니다.

Lasso는 두 가지 다른 구조 개념을 활용합니다: 분해 가능성과 LDE 구조. 분해 가능성은 대략적으로 매우 작은 규모의 테이블에서 소량의 조회를 통해 테이블에 대한 조회를 완료할 수 있음을 의미합니다. 이는 LDE 구조보다 더 엄격한 요구 사항이지만, Lasso는 분해 가능한 테이블에 적용될 때 매우 효율적입니다.

Jolt

Jolt(Just One Lookup Table "단 하나의 조회 테이블")는 Lasso를 기반으로 거대한 조회 테이블을 사용하는 새로운 프론트엔드입니다. Jolt는 가상 머신/CPU 추상화, 즉 명령어 집합 아키텍처(ISA)를 대상으로 합니다. 이러한 추상화를 지원하는 SNARK는 zkVM이라고 합니다. 예를 들어, RISC-Zero 프로젝트에서 지원하는 RISC-V 명령어 집합(곱셈 확장을 포함한 명령어 집합)이 있습니다. 이는 컴퓨터 아키텍처 커뮤니티에서 개발한 인기 있는 오픈 소스 ISA로, 개발 시 SNARK를 고려하지 않았습니다.

각 RISC-V 명령어 fi에 대해 Jolt의 주요 아이디어는 fi의 전체 평가 테이블을 포함하는 조회 테이블을 생성하는 것입니다. 따라서 fi가 두 개의 32비트 입력을 받는 경우, 해당 테이블은 2^64개의 항목을 가지며, (x,y)'번째 항목은 fi(x,y)가 됩니다. 64비트가 아닌 32비트 데이터 유형의 명령어를 고려할 경우, 각 명령어의 테이블 크기는 2^128이 될 것입니다.

기본적으로 각 RISC-V 명령어의 조회 테이블은 분해 가능하며 Lasso에 적용됩니다. 일부 명령어는 다른 명령어의 짧은 시퀀스를 적용하여 처리됩니다. 예를 들어, 나눗셈 명령어의 처리 방법은 증명자가 몫과 나머지를 제출하고, 한 번의 곱셈과 한 번의 덧셈을 통해 몫과 나머지가 올바르게 제공되었는지 확인하는 것입니다.

T 단계 RISC-V CPU의 회로는 다음과 같이 생성될 수 있습니다. T 단계의 각 단계에 대해 회로는 해당 단계에서 실행할 원래 RISC-V 명령어 fi와 해당 명령어의 입력(x, y)을 결정하는 간단한 논리를 포함합니다. 그런 다음 회로는 한 번의 조회만 수행하여 관련 테이블의 (x,y) 항목을 드러내어 fi를 실행합니다. 더 정확하게 말하면, Jolt는 각 명령어의 테이블이 연결되어 형성된 단일 테이블만 고려하므로 "단 하나의 조회 테이블"이라고 불립니다.

SNARK 설계에서 공진리를 재검토하다

Lasso와 Jolt는 SNARK 설계의 몇 가지 공진리를 전복시켰습니다.

1. SNARK의 과도한 필드(over large field)는 낭비입니다. 모든 사람은 FRI, Ligero, Brakedown 또는 그 변형을 사용해야 하며, 이러한 기술은 타원 곡선 기술을 피할 수 있습니다. 타원 곡선 기술은 일반적으로 더 큰 필드에 적합합니다.

여기서 필드 크기는 대략적으로 SNARK 증명에서 나타나는 숫자의 크기로 이해할 수 있습니다. 큰 수의 덧셈과 곱셈 비용이 크기 때문에, 큰 필드에서의 SNARK는 낭비를 초래하며, 이는 우리가 가능한 한 큰 수가 나타나지 않는 프로토콜을 설계해야 함을 의미합니다. MSM 기반의 약속은 타원 곡선을 사용하며, 타원 곡선은 일반적으로 큰 필드에서 정의됩니다(크기 약 2^256), 따라서 타원 곡선의 성능이 떨어집니다.

나는 이전에 작은 필드를 사용하는 것이 합리적인지 여부는 응용에 크게 의존한다고 논의했습니다. Lasso와 Jolt는 MSM 기반의 약속 방식을 사용하더라도 증명자의 작업이 필드 크기의 영향을 거의 받지 않음을 보여줍니다. 이는 MSM 기반의 약속에서 약속 값의 크기가 이러한 값이 위치한 필드의 크기보다 더 중요하기 때문입니다.

기존의 SNARK는 증명자가 많은 무작위 필드 요소를 제출하도록 합니다. 예를 들어, Plonk라는 증명자는 각 회로 게이트에 대해 약 7개의 무작위 필드 요소(및 추가 비무작위 필드 요소)를 제출합니다. 증명된 계산에서 나타나는 모든 값이 작더라도 이러한 무작위 필드 요소는 여전히 큽니다.

반면에, Lasso와 Jolt는 증명자가 더 작은 수치를 제출하도록 요구합니다 (Lasso의 증명자가 제출하는 수치는 이전의 조회 매개변수보다도 적습니다). 이는 MSM 기반 방식의 성능을 크게 향상시킵니다. 최소한, Lasso와 Jolt는 증명자 성능이 중요한 경우 커뮤니티가 MSM 기반의 약속을 포기해야 한다는 관점을 버려야 합니다.

2. 명령어 집합이 더 간단할수록 zkVM 속도가 더 빨라집니다.

각 명령어의 평가 테이블이 분해 가능하기만 하면, Jolt(각 명령어)의 복잡성은 명령어의 입력 크기에만 의존합니다. Jolt는 거대한 복잡한 명령어들이 모두 분해 가능하다는 것을 증명했습니다. 특히 모든 RISC-V 명령어가 그렇습니다.

이는 더 간단한 가상 머신(zkVM)이 반드시 더 작은 회로와 관련된 더 빠른 증명기(가상 머신의 각 단계)로 이어진다는 일반적인 생각과 반대입니다. 이 관점은 극소형 zkVM(예: Cairo VM)의 설계를 이끌어왔습니다.

사실, 더 간단한 가상 머신에 대해 Jolt는 이전의 SNARK보다 증명자의 약속 비용을 더 낮출 수 있습니다. 예를 들어, Cairo VM에서 실행되는 증명자는 가상 머신의 각 단계에서 51개의 필드 요소를 제출해야 합니다. Cairo VM이 배포한 SNARK는 현재 251비트 필드에서 작동하며(63비트는 SNARK가 사용할 수 있는 필드 크기의 하드 하한입니다), Jolt의 검증자는 RISC-V CPU에서 각 단계마다 약 60개의 필드 요소를 제출합니다(64비트 데이터 유형으로 정의됨). 제출된 필드 요소가 적기 때문에, Jolt 검증자의 비용은 약 6개의 256비트 무작위 필드 요소를 제출하는 비용과 대략 동일합니다.

3. 대규모 계산을 작은 조각으로 분해하는 것은 성능 손실을 초래하지 않습니다.

이러한 관점에 따라, 오늘날의 프로젝트는 대형 회로를 작은 조각으로 분해하고 각 조각을 별도로 증명하며 SNARK 재귀를 통해 결과를 집계합니다. 이러한 배포는 대부분의 SNARK의 성능 병목 현상을 완화하기 위해 이러한 방법을 사용합니다. 예를 들어, FRI 기반의 SNARK는 작은 회로에 대해서도 거의 100GB의 증명기 공간이 필요합니다. 이들은 또한 FFT가 필요하며, 이는 초선형 작업으로, SNARK가 대형 회로에 한 번에 적용될 경우 병목 현상이 될 수 있습니다.

현실은 Lasso와 Jolt와 같은 일부 SNARK가 규모의 경제성을 보여준다는 것입니다(현재 배포된 SNARK는 규모의 경제성을 가지지 않습니다). 이는 증명된 문장이 클수록 증명자의 오버헤드가 증거 검증(witness checking, 즉 올바름을 보장하지 않고 증거 회로를 평가하는 데 필요한 작업)에 비례하여 작아진다는 것을 의미합니다. 기술적으로 규모의 경제는 두 가지 측면에서 발생합니다:

1) 크기가 n인 MSM의 피펜저 가속(Pippenger speedup)은 원래 알고리즘보다 log(n)배 향상됩니다. n이 클수록 향상도 커집니다.

2) Lasso와 같은 조회 매개변수에서는 증명자가 조회 테이블의 크기에 따라 한 번의 비용을 지불해야 하지만, 조회 값의 수와는 무관합니다. 증명자의 한 번의 비용은 테이블에 대한 모든 쿼리에서 분산됩니다. 더 큰 데이터 블록은 더 많은 조회를 의미하며, 이는 더 나은 분산을 의미합니다.

오늘날 대형 회로를 처리하는 주류 방법은 회로를 가능한 한 작은 조각으로 나누는 것입니다. 각 조각의 크기에 대한 주요 제한은 너무 작아서는 안 되며, 그렇지 않으면 재귀 집계 증명이 증명자의 병목 현상이 됩니다.

Lasso와 Jolt는 기본적으로 반대의 접근 방식을 제안합니다. 우리는 규모의 경제성을 가진 SNARK를 사용해야 합니다. 그런 다음 대형 계산을 가능한 한 큰 부분으로 나누고 결과를 재귀적으로 처리합니다. 각 계산 조각의 크기에 대한 주요 제한 요소는 증명자 공간이며, 계산 조각이 커짐에 따라 증명자 공간도 증가합니다.

4. 고차 제약은 효율적인 SNARK의 필요 조건입니다.

Jolt는 R1CS를 중간 표현으로 사용합니다. Jolt에서는 "고차" 또는 "사용자 정의" 제약을 사용하는 것이 아무런 이점이 없습니다. Jolt에서는 증명자의 대부분의 비용이 조회 매개변수 Lasso에 있으며, 제약 시스템의 만족 가능성에 있지 않습니다(이 시스템은 조회 옵션을 당연하게 여깁니다).

Jolt는 범용적이므로 범용성을 잃지 않습니다. 따라서 개발자는 오늘날 인기 있는 SNARK에서 더 높은 성능을 끌어내기 위해 고도로 제약된 설계를 할 때, Jolt는 정반대의 방향으로 나아갑니다.

물론 특정 상황에서는 높은 정도의 사용자 정의 제약이 여전히 도움이 될 수 있습니다. 중요한 예로는 Minroot VDF가 있으며, 이 경우 5단계 제약이 약 3배의 약속 비용을 줄일 수 있습니다.

5. 희소 다항식 약속 방식(Sparse polynomial commitment)은 비용이 많이 들며 가능한 한 피해야 합니다.

진정한 비판은 최근에 출시된 CCS라는 시스템과 이를 지원하는 SNARK: (Super-)Spartan 및 (Super-)Marlin에 대한 것입니다. CCS는 오늘날의 관행에서 인기 있는 모든 제약 시스템에 대한 간결한 요약입니다.

이 비판은 근거가 없습니다. 사실, Lasso와 Jolt의 기술 핵심은 Spartan의 희소 다항식 약속 방식인 Spark입니다. Spark는 본질적으로 모든(비희소) 다항식 약속 방식을 희소 다항식을 지원하는 방식으로 변환합니다.

Lasso는 Spark를 최적화하고 확장하여 증명자가 "작은" 값을 제출하도록 보장하지만, 이러한 최적화가 없더라도 이 비판은 타당하지 않습니다. 사실, Spartan의 증명자는 SNARK(예: Plonk 등)와 비교할 때 약속하는(무작위) 필드 요소가 더 적습니다.

Spartan의 접근 방식은 특히 반복 구조를 가진 회로에 대해 추가적인 성능 이점을 제공합니다. 이러한 회로에 대해 게이트를 추가하는 것은 Spartan 검증자의 암호화 작업량을 증가시키지 않습니다. 이 작업량은 주어진 제약 시스템의 변수 수가 증가함에 따라 증가하지만, 제약 수가 증가함에 따라 증가하지 않습니다. 또한 Plonk와는 달리 Spartan 검증자는 동일한 변수의 여러 다른 "복사본"에 대해 약속할 필요가 없습니다.

결론

우리는 Lasso와 Jolt가 SNARK 설계 방식을 크게 변화시켜 성능과 감사 가능성을 향상시킬 것이라고 믿습니다. 이 시리즈의 후속 기사에서는 Lasso와 Jolt의 작동 원리를 깊이 탐구할 것입니다.