a16z, Lattice Jolt 출시: 증명 속도 3배 향상, 양자 공격에도 대응

편집: 선차오 TechFlow

편집자 주: zkVM은 줄곧 "증명이 너무 느리고, 크기가 너무 크다"는 불평을 들어왔는데, a16z가 이번에 타원 곡선을 격자 암호로 교체하여 증명 속도를 3배 높이고 증명 크기를 100KB 이하로 압축했다. 이는 현재 속도 면에서 전통적인 타원 곡선 방식을 능가하는 유일한 양자 내성 방식이며, 온체인 검증 비용과 프라이버시 애플리케이션에 직접적인 영향을 미친다.

오늘 우리는 Lattice Jolt를 공식 발표한다. 이는 우리가 오픈소스로 공개한 zkVM(영지식 가상 머신)의 최신 버전이다. Jolt는 원래부터 현재 가장 빠르고 가장 단순한 zkVM이었으며, 그 아키텍처는 변하지 않았다. 하지만 기반 암호학이 교체되었다: 타원 곡선에서 격자 암호로. 이 하나의 변경이 동시에 세 가지를 가져온다:

Jolt가 양자 내성(포스트퀀텀)을 갖춘다.
증명자와 검증자의 속도가 2-3배 향상된다.
Lattice Jolt는 모든 포스트퀀텀 zkVM 중에서 증명 크기가 가장 작다: 현재 100 KB 미만이며, 이후에도 계속 압축할 수 있다. 증명을 온체인에 올리고 네트워크를 넘어 전송해야 한다면, 증명이 작을수록 검증 비용이 낮아진다.

이러한 특성들은 zkVM의 모든 사용 사례를 아우른다. 동일한 증명자가 GPU에서는 수십억 개의 CPU 사이클을 처리하고, 휴대폰에서도 수백만 개의 사이클을 증명할 수 있다. 두 경우 모두 개발자는 일반 프로그램을 작성하면 되며, 전문 지식이 있어야만 해결할 수 있는 회로를 직접 작성할 필요가 없다. 이것이 우리가 Jolt를 "만능 SNARK"라고 부르는 이유다.

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

타원 곡선을 격자로 교체하기

Jolt의 이전 다항식 약속 방식은 Dory라고 불렸으며, 이는 전체 시스템에서 유일하게 타원 곡선 암호학에 의존하는 구성 요소였다. Lattice Jolt는 Dory를 Akita로 교체했는데, Akita는 모듈-SIS 격자 가정에 기반한 완전히 새로운 다항식 약속 방식이다. Lattice Jolt는 이 표준적인, 충분히 연구된 가정에 기반하며, 완전한 128비트 보안을 목표로 한다.

Module-SIS와 그 형제인 모듈-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 구현으로, 애플 하드웨어에 막대한 가속을 가져왔다. (Metal은 애플의 프레임워크로, MacBook과 iPhone 등 기기에 내장된 GPU에서 코드를 실행하는 데 사용된다.)

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만 배로 낮추었다. 이것이 끝이 아니며, 엔지니어링과 프로토콜 차원의 최적화 여지가 여전히 남아 있다.

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

격자로 교체한 후, Jolt의 원래도 뛰어났던 메모리 사용량은 더욱 개선되었다: 증명자의 공간 사용이 사이클당 약 300바이트에서 200바이트로 줄었다. 이는 휴대폰에서 수백만 개의 RISC-V 사이클을 증명할 수 있다는 뜻이다.

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

왜 해시가 아니라 격자인가

수년 동안 SNARK 커뮤니티의 관심(그리고 사실상 모든 생산 배포)은 해시 기반 SNARK에 집중되어 있었으며, 이를 포스트퀀텀 안전으로 가는 경로로 여겼다.

하지만 격자 SNARK와 격자 커밋먼트에 대한 지속적인 연구 흐름도 있어 왔으며, LaBRADOR, Greyhound, LatticeFold, SuperNeo, 그리고 Akita의 직접적인 전신인 Hachi를 포함한다. Lattice Jolt는 이러한 연구 위에 세워져, 격자 커밋먼트 계층을 고성능 zkVM 아키텍처에 도입하는 동시에 격자 기반 SNARK가 속도와 컴팩트함에서 비할 데 없음을 증명한다.

이는 놀라운 일이 아니다. 앞서 언급했듯이, 같은 패턴이 디지털 서명에서 이미 한 번 일어났다.

암호학자들은 많은 가정에 기반해 서명을 구성해 왔다. 해시 서명은 일반적으로 가장 보수적인 선택으로 여겨진다: 그들의 보안 가정은 단순하고 오래되었다. 하지만 세계는 주로 격자 서명으로 이동하고 있는데, 그것이 더 짧고 더 빠르기 때문이다:

ML-DSA 서명은 약 몇 KB이다.
NIST가 표준화한 해시 대안 SLH-DSA는 몇 배 더 크다.
암호화와 키 교환의 경우 상황은 더 명확하다: 해시 방식은 아예 선택지가 없다(불가능하다는 증명이 있다). 포스트퀀텀 배포는 압도적으로 격자 기반이다. ML-KEM(NIST가 2024년에 확정한 주요 키 설정 표준)은 이미 주요 브라우저와 통신 앱에 기본 배포되어 있으며, 네트워크상의 수많은 TLS 연결에서 사용된다.

SNARK와 서명 사이의 유추는 표면적인 것이 아니다. 디지털 서명은 본질적으로 권한이 부여된 메시지에 대한 개인 키 지식 증명이다. SNARK는 이 패러다임을 좁은 진술에서 임의의 계산으로 확장한다. 따라서 SNARK의 장기적인 암호학적 지형이 서명과 암호화의 지형과 완전히 다르다면, 그게 오히려 이상할 것이다.

여기서 정리할 만한 오해도 하나 있다: 해시 SNARK는 종종 "해시 함수에만 의존하기" 때문에 보수적인 포스트퀀텀 선택이라고 말해진다. 이는 기반 해시 함수가 비대수적일 때만 성립한다.

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

간단히 말해, 우리는 대수적 해시 함수의 안전성에 확신이 없다. 그럼에도 불구하고 그것들은 오늘날 생산급 SNARK 시스템에서 널리 사용되고 있다. (다만 진전의 신호가 하나 나타났다: 이더리움 재단이 최근 그것들의 사용을 포기하겠다고 발표했다.)

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

위에서 추측한 해시 기반 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는 거의 그러한 벡터에만 커밋합니다. 이 특성 덕분에 우리는 Dory를 Akita로 교체하면서 Jolt의 나머지 부분을 그대로 유지할 수 있습니다.

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

만능 SNARK

Lattice Jolt는 구축자가 zkVM에 필요로 하는 모든 것을 한 번에 충족합니다: 포스트퀀텀, 투명, 빠름, 간결하며 공간 효율적입니다. 이는 LaBRADOR에서 Hachi로 이어지는 격자 SNARK 연구 노선을 생산급 zkVM으로 가져오면서도, 처음에 Jolt를 빠르게 만든 어떤 장점도 포기하지 않습니다.

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

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

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