a16z, Lattice Jolt 공개: 증명 속도 3배 향상, 양자 공격에도 견딘다

작성자: a16z crypto

편집: Deep Tide TechFlow

Deep Tide 서문: zkVM은 '증명이 너무 느리고 크기가 너무 크다'는 비판을 받아왔습니다. a16z는 이번에 타원 곡선을 격자 암호로 교체하여 증명 속도를 3배 향상시키고 증명 크기를 100KB 미만으로 줄였습니다. 이는 현재 속도 면에서 기존 타원 곡선 방식을 능가하는 유일한 포스트 양자 솔루션으로, 온체인 검증 비용과 프라이버시 애플리케이션에 직접적인 영향을 미칩니다.

오늘 우리는 오픈소스 zkVM(영지식 가상 머신)의 최신 버전인 Lattice Jolt를 공식 출시합니다. Jolt는 원래 현재 가장 빠르고 간단한 zkVM이며, 그 아키텍처는 변경되지 않았습니다. 그러나 기본 암호화가 타원 곡선에서 격자 암호로 교체되었습니다. 이 한 가지 변경으로 세 가지가 동시에 이루어집니다:

• Jolt가 포스트 양자 안전성을 갖추게 됩니다.
• 증명자(prover)와 검증자(verifier)의 속도가 2~3배 향상됩니다.
• Lattice Jolt는 모든 포스트 양자 zkVM 중 가장 짧은 증명을 제공합니다: 현재 100KB 미만이며, 향후 더 압축할 수 있습니다. 증명은 온체인에 올라가고 네트워크를 통해 전송되어야 하므로, 증명이 작을수록 검증 비용이 낮아집니다.

이러한 특성은 zkVM의 모든 사용 사례를 포괄합니다. 동일한 증명자가 GPU에서 수십억 개의 CPU 사이클을 처리할 수 있고, 휴대폰에서도 수백만 사이클을 증명할 수 있습니다. 두 경우 모두 개발자는 전문 지식이 필요한 회로를 수동으로 작성하지 않고 일반 프로그램을 작성합니다. 이것이 우리가 Jolt를 '만능 SNARK'라고 부르는 이유입니다.

하지만 더 큰 이야기는 Lattice Jolt가 SNARK 설계와 채택에 미치는 의미입니다. 현재 시장에 출시된 거의 모든 포스트 양자 SNARK는 해시 기반입니다. Lattice Jolt는 격자 기반 SNARK가 더 빠르고 더 컴팩트할 수 있음을 증명합니다. 디지털 서명도 동일한 전환을 겪고 있습니다: 해시 방식은 보수적인 선택이지만, 격자 방식이 전 세계적으로 대규모 배포되고 있습니다. 우리는 SNARK도 이 길을 갈 것으로 예상하며, 이 블로그 게시물의 후반부에서 그 이유를 설명할 것입니다.

격자로 타원 곡선 교체

Jolt의 이전 다항식 커밋먼트 방식은 Dory라고 불렸으며, 이는 전체 시스템에서 타원 곡선 암호화에 의존하는 유일한 구성 요소였습니다. Lattice Jolt는 Dory를 Akita로 교체했는데, Akita는 Module-SIS 격자 가정에 기반한 완전히 새로운 다항식 커밋먼트 방식입니다. Lattice Jolt는 이 표준적이고 잘 연구된 가정을 기반으로 하며, 완전한 128비트 보안을 목표로 합니다.

Module-SIS와 그 형제인 Module-LWE는 동일한 가정군에 속하며, 전 세계 디지털 인프라가 이 가정군으로 이동하고 있습니다. 이러한 가정은 디지털 서명 표준 ML-DSA뿐만 아니라 키 설정 표준 ML-KEM을 뒷받침하며, 후자는 이미 전 세계적으로 가장 널리 배포된 포스트 양자 프리미티브입니다.

Akita의 개발 및 구현은 LayerZero의 연구원과 엔지니어가 주도했으며, 카네기 멜런 대학교, 서던캘리포니아 대학교의 연구원들과 a16z crypto의 엔지니어링 및 연구 팀이 참여했습니다.

Lattice Jolt가 더 빠른 이유

Lattice Jolt는 단순히 포스트 양자 안전성을 갖춘 것뿐만 아니라, 교체된 타원 곡선 버전보다 더 빠릅니다.

가속은 주로 간단한 이유에서 비롯됩니다. 타원 곡선은 Jolt가 256비트 필드에서 작동하도록 강제하는 반면, 격자 암호는 128비트 필드에서 동일한 수준의 보안을 달성할 수 있습니다. Jolt 증명자의 주요 작업은 필드 요소 곱셈(본질적으로 매우 큰 숫자의 곱셈)이므로, 숫자 크기가 절반으로 줄면 각 곱셈이 몇 배 더 빨라집니다.

Dory를 사용한 Jolt는 이미 빨랐습니다: 지난 성능 업데이트에서 Jolt가 노트북에서 초당 약 70만 개의 RISC-V(RV64IMAC) 사이클을 증명할 수 있다고 밝혔으며, 이후 최적화를 통해 곡선 버전 Jolt는 초당 100만 사이클을 넘어섰습니다.

Lattice Jolt는 동일한 머신에서 초당 200만 사이클 이상을 증명할 수 있습니다.

지난 6개월 동안 우리는 Akita를 개발하고 Jolt에 통합하는 것뿐만 아니라 Jolt 코드베이스를 처음부터 다시 작성하는 데 많은 시간을 보냈습니다. Jolt는 이전에도 GPU에서 잘 실행되었지만, 이번 재작성을 통해 GPU 구현을 더 쉽게 구축하고 최적화할 수 있게 되었습니다.

첫 번째 성과는 Apple Metal 구현으로, Apple 하드웨어에 큰 가속을 제공합니다. (Metal은 MacBook 및 iPhone과 같은 기기에 내장된 GPU에서 코드를 실행하기 위한 Apple의 프레임워크입니다.)

• GPU 가속 Lattice Jolt는 MacBook에서 초당 1000만 개 이상의 RV64IMAC 사이클을 증명할 수 있습니다.
• 순수 CPU Lattice Jolt는 동일한 머신에서 초당 200만 사이클 이상을 증명할 수 있습니다.
• 곡선 버전 Jolt조차도 Metal이 탑재된 MacBook에서 현재 초당 약 400만 사이클을 달성할 수 있습니다.

즉, 한 번의 출시로 MacBook에서 Jolt가 초당 약 100만 사이클(곡선 버전, 순수 CPU)에서 1000만 사이클 이상(격자 버전, Metal 포함)으로 향상되었습니다.

이 수치를 큰 그림에서 보면: 4년 전 우리가 처음 SNARK 증명자 오버헤드를 작성했을 때, 계산을 증명하는 것이 직접 실행하는 것보다 수백만 배 더 비쌌습니다. Lattice Jolt는 이 오버헤드를 약 1만 배로 줄였습니다. 아직 끝이 아니며, 엔지니어링 및 프로토콜 수준의 최적화 여지가 여전히 존재합니다.

증명 크기는 증명자 속도만큼 중요합니다. 100KB 미만으로, Lattice Jolt의 증명은 다른 포스트 양자 zkVM보다 훨씬 작으며, 다른 방식의 증명은 200KB 이상에서 약 600KB 이상까지 다양합니다.

격자로 전환한 후, Jolt의 이미 우수한 메모리 사용량도 더욱 개선되었습니다: 증명자의 공간 사용량이 사이클당 약 300바이트에서 200바이트로 줄었습니다. 이는 휴대폰에서 수백만 개의 RISC-V 사이클을 증명할 수 있음을 의미합니다.

곧 발표될 동반 논문에서는 Lattice Jolt에 영지식성을 추가할 예정이며, 이는 프라이버시 애플리케이션에 필요한 속성입니다.

해시 대신 격자를 선택한 이유

수년 동안 SNARK 커뮤니티의 관심(그리고 기본적으로 모든 프로덕션 배포)은 포스트 양자 보안으로 가는 경로로서 해시 기반 SNARK에 집중되어 왔습니다.

그러나 LaBRADOR, Greyhound, LatticeFold, SuperNeo, 그리고 Akita의 직접적인 전신인 Hachi를 포함하는 격자 SNARK 및 격자 커밋먼트에 대한 지속적인 연구 라인도 있었습니다. Lattice Jolt는 이러한 연구를 기반으로 하여 격자 커밋먼트 계층을 고성능 zkVM 아키텍처에 도입하면서, 격자 기반 SNARK가 속도와 컴팩트함에서 타의 추종을 불허한다는 것을 증명합니다.

이는 놀라운 일이 아닙니다. 앞서 언급했듯이, 동일한 패턴이 디지털 서명에서 이미 발생했습니다.

암호학자들은 많은 가정을 기반으로 서명을 구성해 왔습니다. 해시 서명은 일반적으로 가장 보수적인 선택으로 간주됩니다: 보안 가정이 단순하고 오래되었기 때문입니다. 그러나 세상은 주로 격자 서명으로 이동하고 있습니다. 더 짧고 빠르기 때문입니다:

• ML-DSA 서명은 약 몇 KB입니다.
• NIST 표준화된 해시 대안인 SLH-DSA는 몇 배 더 큽니다.
• 암호화 및 키 교환의 경우 상황이 더 명확합니다: 해시 방식은 선택할 수 없으며(불가능하다는 증명이 있음), 포스트 양자 배포는 압도적으로 격자 기반입니다. ML-KEM(2024년 NIST가 확정한 주요 키 설정 표준)은 이미 주요 브라우저와 메시징 앱에 기본 배포되어 있으며, 인터넷의 수많은 TLS 연결에서 사용되고 있습니다.

SNARK와 서명 사이의 유사성은 피상적인 것이 아닙니다. 디지털 서명은 본질적으로 권한 있는 메시지에 대한 개인 키 지식의 증명입니다. SNARK는 이 패러다임을 좁은 명제에서 임의의 계산으로 확장합니다. 따라서 SNARK의 장기 암호학적 지형이 서명 및 암호화의 지형과 완전히 다르다면 이상할 것입니다.

여기서 명확히 해야 할 오해가 있습니다: 해시 SNARK는 종종 '해시 함수에만 의존하기 때문에' 보수적인 포스트 양자 선택으로 묘사됩니다. 이는 기본 해시 함수가 비대수적일 때만 성립합니다.

오늘날 대부분의 해시 기반 SNARK 배포는 해시가 올바르게 평가되었음을 저비용으로 증명하기 위해 SNARK 친화적인 대수적 해시 구조(예: Poseidon)에 의존합니다. 이는 재귀(여기서 재귀는 유효한 SNARK 증명을 보유하고 있음을 증명하는 것을 의미)에 특히 중요합니다. 이러한 구조는 표준 해시 함수보다 더 많은 구조를 가지며, 그 암호 분석은 아직 성숙하지 않았습니다.

간단히 말해, 우리는 대수적 해시 함수의 보안에 확신이 없습니다. 그럼에도 불구하고 오늘날 프로덕션급 SNARK 시스템에서 널리 사용되고 있습니다. (하지만 진전의 신호가 있습니다: 이더리움 재단은 최근 이들의 사용을 포기할 것이라고 발표했습니다.)

대수적 해시는 배포된 해시 기반 SNARK의 유일한 숨겨진 가정이 아닙니다: 많은 시스템은 역사적으로 완전히 입증된 경계 대신 추측적인 근접 갭(proximity-gap) 경계를 사용하여 구체적인 보안 수준을 설정해 왔습니다. 가장 강력하다고 여겨졌던 일부 경계는 나중에 잘못된 것으로 판명되었습니다.

위의 추측을 피하는 해시 기반 SNARK조차도 보안 목표가 일반적으로 128비트 미만입니다. 완전한 128비트 보안은 상당한 성능 오버헤드를 초래하기 때문입니다. 왜 그럴까요? 해시 기반 SNARK는 128비트 필드에서 128비트 보안을 달성할 수 없습니다. 그 신뢰성 오류가 n/|F|에 비례하여 확장되기 때문입니다. 여기서 n은 대략 증명되는 명제의 크기이고 |F|는 필드 크기입니다. 따라서 128비트 필드에서 10억 단계의 명제를 증명하면 약 30비트의 보안이 손실되어 100비트 미만이 됩니다. 반면 Lattice Jolt의 신뢰성 오류는 log(n)/|F|에 비례하여 확장되므로, 동일한 필드에서 거의 완전한 128비트 보안을 유지합니다(작은 log(n) 손실은 표준 기술로 복구 가능).

아이러니하게도 '보수적인' 포스트 양자 선택으로 홍보되는 일부 시스템은 실제로 대수적 해시 함수, 추측적인 근접 갭 경계, 그리고 128비트 미만의 목표 보안 수준에 동시에 의존합니다. 따라서 해시 기반 SNARK는 중요한 방향이지만, 많은 사람들이 생각하는 것처럼 자동으로 저위험 옵션이 되는 것은 아닙니다.

하나의 Jolt, 세 가지 기반: 곡선, 격자, 해시

우리는 항상 Jolt가 단일 암호화 기반에 묶여서는 안 된다고 믿어 왔습니다. 곡선, 해시, 격자 기반의 성숙하고 고성능인 SNARK를 보유해야 합니다. 서로 다른 가정과 성능 특성은 서로 다른 시나리오에 적합할 것입니다.

그러나 디지털 서명을 참조한다면, 격자 기반 SNARK가 가장 널리 배포된 포스트 양자 선택이 될 것입니다.

Jolt는 이 전환에서 비범하게 유리한 위치에 있습니다. 원래 Jolt 설계는 희소 벡터에 대한 빠른 커밋먼트를 포함하여 커밋먼트에 특히 유용한 타원 곡선의 특성을 활용했습니다. 격자 커밋먼트도 동일한 특성을 가집니다: 벡터의 대부분 항목이 0이거나 작을 때 벡터에 대한 커밋먼트 비용이 낮으며, Jolt는 거의 이러한 벡터에만 커밋합니다. 이 특성 덕분에 Jolt의 나머지 부분을 변경하지 않고 Dory를 Akita로 교체할 수 있었습니다.

우리는 해시 기반 Jolt 버전을 구축할 것입니다. 그러나 곡선 기반 및 격자 기반 Jolt와 비교할 때 해시 기반 버전은 공간 효율성이 더 나쁘고, 증명이 더 크며, 다양한 복잡한 문제가 있습니다. 가장 유망한 해시 기반 SNARK는 이진 필드에서 작동하기 때문입니다. 이 수 체계는 해시 평가를 증명하는 데 편리하지만 CPU의 산술 방식과 일치하지 않습니다. 이러한 불일치로 인해 일반적인 CPU 곱셈을 증명하는 것이 비용이 많이 듭니다. 그럼에도 불구하고 생태계는 디지털 서명 분야와 마찬가지로 모든 주요 가정군 하에서 zkVM을 보유해야 합니다.

만능 SNARK

Lattice Jolt는 빌더가 zkVM에 요구하는 모든 것을 한 번에 충족합니다: 포스트 양자, 투명성, 빠르고, 컴팩트하며, 공간 효율적입니다. LaBRADOR에서 Hachi에 이르는 격자 SNARK 연구 라인을 프로덕션급 zkVM에 도입하면서, 처음에 Jolt를 빠르게 만든 어떤 이점도 포기하지 않았습니다.

우리의 목표는 성능이 가장 뛰어난 zkVM을 누구나 사용할 수 있도록 오픈소스화하는 것뿐만 아니라, 특정 애플리케이션을 위해 SNARK를 수동으로 튜닝해야 할 필요성을 크게 제거하는 것입니다. 이를 위해 Jolt가 수동으로 튜닝된 증명자만큼 빨라야 하는 것은 아닙니다. 이는 CPU가 모든 작업에서 전용 ASIC과 견줄 것을 요구하는 것과 같은 불가능한 목표입니다. Jolt가 수용 가능한 사용자 경험을 제공할 만큼 충분히 빠르기만 하면 됩니다.

클라이언트 측 증명과 관련된 '작은' 명제(오늘날 수동 최적화 회로가 지배적인 시나리오)의 경우, 핵심 기준은 휴대폰에서 약 1초 이내에 증명을 생성하는 것입니다. Jolt는 이미 이에 근접하고 있으며, 많은 가속 방안이 진행 중입니다.

격자 SNARK의 시대가 도래했습니다.