격자 SNARK를 활용한 빠른 포스트 양자 서명 집계

알베르토 센테예스, 꽝 다오, 저스틴 세일러, 마르코스 게오르기아데스, 마이클 주, 앤드루 트레티야코프 (Alberto Centelles, Quang Dao, Justin Thaler, Markos Georghiades, Michael Zhu, Andrew Tretyakov)
2026년 10월 16일

비트코인을 제외한 대부분의 주요 블록체인은 지분증명(PoS) 방식으로 운영되며, 검증인은 각 블록에 서명해 투표한다. 대규모 검증인 집합을 실용적으로 만드는 핵심이 서명 집계다. 이더리움은 BLS 서명을 사용하며, 이 서명의 대수적 구조 덕분에 매 슬롯마다 수만 건의 검증인 서명을 하나의 그룹 원소로 결합할 수 있다. 전체 거래의 약 4분의 3을 검증인 투표가 차지하는 솔라나도 Alpenglow 업그레이드의 일환으로 BLS 집계를 도입하고 있다.

하지만 BLS는 유용한 만큼 양자내성을 갖추지 못했다. 실제로 현재 알려진 양자내성 서명 체계 가운데 이런 방식의 집계를 지원하는 것은 없다. 양자내성 서명은 현재의 타원곡선 서명보다 크기가 10배에서 100배가량 크기 때문에, 집계가 없으면 블록이 비대해진다. 이는 처리량을 제한하고 노드 운영 비용을 높인다. 스테이블코인 송금부터 AI 에이전트의 결제까지 블록체인이 전 세계 결제에서 차지하는 비중이 커지는 상황에서 이는 중요한 문제다.

SNARKs(Succinct Non-interactive Arguments of Knowledge)는 이런 문제를 해결한다. 이 경우 ‘집계 서명’은 배치에 포함된 모든 서명이 유효하다는 점을 입증하는 하나의 간결한 증명이 된다. 현재 주류인 SNARK 기반 접근법은 이더리움 로드맵의 핵심으로, 해시 기반 서명과 해시 기반 SNARK를 결합한다. 하지만 이 방식은 느리다. 해시 기반 서명은 증명 비용이 크기 때문이다. 단일 노트북으로는 슬롯 전체 분량의 서명을 처리할 수 없고, 이 때문에 이더리움 설계는 작업을 여러 프로버로 나눈 뒤 재귀적으로 증명을 병합한다.

이 때문에 이번에 Aerie를 공개한다. Aerie는 반대로 격자 기반 SNARK를 이용해 격자 기반 서명을 집계하는 방식이다. Aerie는 NIST가 표준화 대상으로 선정한 격자 기반 서명 체계인 Falcon을 지원하며, Falcon-512와 Falcon-1024 두 변형을 모두 지원한다.

Aerie 핵심 수치

Aerie는 단일 노트북만으로도 이더리움 한 슬롯 분량에 해당하는 서명을 대략 집계할 수 있을 만큼 빠르다.

- 빠른 증명 생성: GPU 가속 없이 Apple M4 Max 노트북에서 Aerie는 32,768개의 Falcon-512 서명을 0.65초 만에 집계한다. 초당 5만개 이상이다. 비교하면 Lean Consensus 팀의 2026년 계획 목표는 초당 1,000개 서명이다.

- 작은 크기: 서명당 약 42바이트다. Falcon-512 서명보다 약 16배 작고, Falcon-1024 서명보다 약 30배 작다.

- 빠른 검증: 증명 검증에는 단일 코어 기준 54밀리초가 걸린다. 서명을 하나씩 검증하는 것보다 10배 빠르다.

더 단순한 설계 공간

Aerie의 속도는 더 단순한 집계 설계도 가능하게 한다.

이더리움의 현재 계획에서 leanVM의 각 증명은 약 900개의 서명만 다룬다. leanVM은 Lean Ethereum의 일부로 개발 중인 zkVM으로, 해시 기반 서명을 집계하는 데 쓰인다. 따라서 슬롯 전체를 처리하려면 재귀적 병합을 여러 차례 거쳐야 하며, 각 단계는 이전 단계의 증명이 도착해야 시작할 수 있다.

재귀는 리스크도 키운다. 구조가 복잡하고 버그가 발생하기 쉬우며, 각 재귀 단계는 증명을 비상호작용형으로 만드는 데 사용된 바로 그 해시 함수에 대한 명제를 다시 증명한다. 따라서 이렇게 만들어진 증명의 보안성은 랜덤 오라클 모델에서도 확립할 수 없다.

Aerie에서는 슬롯의 서명을 수집한 노드가 중간 증명이나 재귀 없이 곧바로 하나의 증명을 생성한다. 이 접근법은 다음과 같은 장점이 있다.

- 각 슬롯에서 투표를 수집하고 블록을 전파하는 데 더 많은 시간을 남긴다.

- 더 많은 참여자에게 집계 기회를 연다.

- 복구를 단순화한다. 집계자가 실패하더라도 같은 서명을 보유한 어떤 노드든 대체 증명을 만들 수 있다.

Aerie가 빠른 이유

이유는 두 가지이며, 모두 격자에 기반한다.

첫 번째는 Akita다. 이는 LayerZero Labs와 함께 구축한 격자 기반 다항식 커밋먼트 체계다. 여기에 Lattice Jolt로 이어지는 과정에서 개발한 sum-check 기반 증명 기법이 결합된다. 이 기법은 병렬화에 매우 적합하며 GPU와도 잘 맞는다. 따라서 Aerie는 앞으로 더 빨라질 여지가 충분하다.

두 번째 이유는 격자 서명 검증에서 해싱 비중이 상대적으로 작기 때문이다. 해시 기반 서명은 서명 하나를 검증할 때 수백 번의 해시 계산이 필요하다. 이를 집계하려면 그 모든 해시 계산을 증명해야 한다. 해싱은 증명 비용이 크며, 일반적으로 해시를 네이티브로 계산하는 것보다 100배가 넘는 오버헤드를 더한다.

격자 서명은 다른 방식으로 검증된다. 핵심 검사는 대수적이며, 해싱은 작은 역할만 한다. 서명당 수백 번이 아니라 몇 번의 해시 계산만 필요하다.

왜 Falcon 서명인가

Falcon은 해싱 비중이 특히 낮다. 이는 hash-and-sign 방식으로, 해시는 메시지와 솔트만 입력으로 받는다. 따라서 집계에 각 서명의 솔트가 포함되면 검증자는 모든 해시를 직접 계산할 수 있고, 증명은 대수적 검사만 다루면 된다. 이것이 Aerie가 빠른 큰 이유이며, Falcon부터 시작한 이유이기도 하다.

Falcon은 크기도 작다. Falcon-1024는 NIST의 최고 보안 수준을 충족하면서도 서명 크기는 가장 낮은 보안 수준의 ML-DSA 파라미터 세트인 ML-DSA-44의 절반 정도다.

모든 블록체인이 Falcon을 채택해야 한다고 주장하는 것은 아니다. Falcon의 서명 알고리즘은 복잡하며, 부동소수점 연산과 수십 KB의 작업 메모리에 의존해 역사적으로 하드웨어 지갑에 탑재하기 어려웠다. 사이드채널 대응 강화도 여전히 활발히 연구되는 분야다.

다만 이런 단점은 빠르게 해소되고 있다. 최근 연구는 부동소수점 대신 고정소수점 연산으로 Falcon 서명을 구현하는 방법을 제시했고, NIST도 이제 FN-DSA 표준에서 이 방식을 요구할 계획이다. 새로운 구현은 Falcon-512 서명에 필요한 메모리를 약 11kB까지 줄였고, 이는 하드웨어 지갑의 보안 요소에 들어갈 수 있을 정도로 작다. 이 두 가지 이유로 Falcon은 1년 전과 비교해도 훨씬 배포하기 쉬워졌다.

하드웨어 지갑은 상태 비저장 해시 기반 서명에도 과제다. 하드웨어 지갑에 들어갈 만큼 가벼운 SPHINCS- 변형도 Ledger 보안 요소에서 서명하는 데 47초에서 6분 이상이 걸린다.

Falcon의 장단점을 검토한 뒤 이를 선택하는 체인이라면, 솔라나가 검토 중이고 알고랜드가 이미 도입한 것처럼 Aerie는 빠른 집계 경로를 제공한다.

현재는 일부 해싱을 증명해야 하는 확장도 진행 중이다. 해시가 서명 자체에 의존하는 ML-DSA를 지원하는 것, 그리고 SNARK 내부에서 Falcon의 해시를 증명해 집계에서 Falcon의 솔트를 제거하는 것이다. LaBinius 같은 최근 진전은 이처럼 소수의 해시를 효율적으로 증명할 수 있는 경로를 제시한다. 또 격자 서명과 타원곡선 기반 서명을 결합한 하이브리드 서명으로도 Aerie를 확장하고 있다. 이는 중요한 다층 방어 수단이다. 이런 확장이 초당 5만개 서명 수준에 도달하지는 못할 수 있지만, 이더리움이 목표로 제시한 초당 1,000개를 여전히 크게 웃도는 여유가 있을 것으로 본다.

격자의 보안성에 대한 논거

블록체인 설계에서 격자 기반 암호와 해시 기반 암호를 둘러싼 논쟁은 활발하다. AI가 암호해석에 어떤 의미를 가질지에 대한 추측이 이를 더 부각시키고 있다. 격자를 수용해야 하는 전체 논거는 향후 별도 글에서 다룰 예정이다. 요지는 이렇다. 격자든 다른 어떤 암호든 새로운 공격이 발견되지 않을 것이라고 누구도 장담할 수는 없다. 하지만 추정에 기반한 암호해석 리스크는 더 복잡한 시스템에 내재한 명확하고 현재적인 리스크와 함께 저울질해야 한다.

앞서 언급했듯 이더리움이 계획 중인 해시 전용 서명 집계 설계는 SNARK 재귀에 의존한다. 이 접근법에는 조정 오버헤드, 버그 발생 가능성, 그리고 확립되지 않은 보안성이 따른다.

해시 전용 설계는 비표준 구조에도 크게 의존한다. 이더리움이 계획 중인 합의 및 계정 서명은 NIST 표준 밖의 맞춤형 체계이며, 기반 해시도 아직 정해지지 않았다. 이는 개인 사용자를 위한 하드웨어 지갑 지원과 기관이 의존하는 하드웨어 보안 모듈 및 커스터디 시스템의 지원을 제한한다.

해시 기반 암호에만 의존하는 것이 더 안전해 보일 수는 있지만, 이런 설계에서는 오히려 시스템을 더 취약하게 만들 수 있다. 중요한 것은 전체 시스템의 보안성이다. 격자 암호를 전면적으로 수용하는 편이 블록체인을 덜이 아니라 더 안전하고 더 기능적으로 만든다고 본다.

격자의 프라이버시 측면 논거

프라이빗 결제에는 서명과 증명만이 아니라 암호화가 필요하다. 수신자는 자신에게 전송된 노트를 알아야 하고, 뷰잉 키는 읽기 권한을 부여해야 하며, 암호화된 멤풀은 거래가 정렬되기 전까지 이를 숨겨야 한다.

프라이빗 결제는 사이퍼펑크와 금융기관 모두에 중요하며, 이더리움도 이미 이를 계획에 포함하고 있다. 이더리움 재단의 strawmap은 베이스 레이어 장기 로드맵 초안으로, 해시 기반 양자내성 L1과 함께 차폐 전송을 지원하는 프라이빗 L1을 다섯 가지 ‘north stars’ 중 하나로 제시한다. 하지만 이 두 목표는 긴장 관계에 있다. 차폐 전송에는 암호화가 필요하고, 해시만으로는 바로 그 암호화를 제공할 수 없기 때문이다.

이 두 목표는 긴장 관계에 있다. 차폐 전송에는 암호화가 필요하지만, 해시만으로는 바로 그 암호화를 제공할 수 없다.

Russell Impagliazzo와 Steven Rudich의 고전적 결과에 따르면 공개키 암호화는 해시 함수만으로 블랙박스 방식으로 구축할 수 없다. 가장 나은 해시 전용 대안인 Merkle puzzles는 정직한 사용자에게 공격자 대비 이차적 우위만 제공하며, 이보다 나은 것은 불가능하다. 해시를 랜덤 오라클로 모델링할 때 어떤 프로토콜도 더 나은 성능을 낼 수 없다. 해시 전용 설계의 지지자들조차 이를 인정한다.

따라서 프라이빗 이더리움은, 프라이빗 결제를 지원하는 다른 어떤 체인과 마찬가지로, 스택 어딘가에서 구조화된 암호에 의존하게 된다. 그리고 실제로 이는 격자를 뜻한다. 격자 기반 체계인 ML-KEM은 NIST의 대표적인 양자내성 암호화 표준이며, 이미 인터넷 전반에 걸쳐 배포되고 있다.

우회 방법은 없을까. 한 가지 제안된 해법은 암호화된 노트를 오프체인에 두는 것이다. 이렇게 하면 영구적으로 공개되는 암호문 수를 줄일 수 있다. 하지만 이것도 암호화를 피하는 것은 아니다. 노트는 여전히 메시징 앱과 기타 채널을 통해 수신자에게 암호화된 상태로 전달돼야 하며, 이런 채널은 이미 ML-KEM으로 이동하고 있다. 오프체인 전달도 자체적인 상충관계를 안고 있다. 항상 가용해야 하는 채널이 필요하고, 메타데이터를 관찰할 수 있으며, 채널 장애가 발생하면 수신자가 자금을 찾고 사용하지 못할 수 있다.

따라서 프라이버시를 지원하는 양자내성 블록체인에서 서명과 증명에 격자를 쓰지 않는다고 해서 격자 의존성이 사라지는 것은 아니다. 오히려 격자가 제공하는 성능과 단순성을 포기하게 될 뿐이다. 비용은 감수하면서 이점은 얻지 못하는 셈이다. 결국 진짜 질문은 격자에 의존할지 여부가 아니라, 잘못된 안전감 때문에 격자의 이점을 포기할 것인지다.

Aerie 추가 세부사항: 증명 크기와 성능

Aerie의 증명 크기는 약 66KiB다. 32,768개의 Falcon-512 서명을 다루든 16,384개의 Falcon-1024 서명을 다루든 같다. 이는 기존 격자 기반 접근법 가운데 가장 작은 축에 속하는 방식과 비슷한 수준이다. PSE의 벤치마크에 따르면 LaBRADOR 기반 Falcon 집계는 1만개 서명에 대해 약 74KB를 기록했지만, 검증에는 밀리초가 아니라 수초가 걸린다.

Aerie의 검증기는 각 서명의 해시를 직접 계산하기 때문에, 각 서명의 40바이트 솔트도 필요하다. 대규모 배치에서는 솔트가 대부분을 차지한다. 32,768개의 솔트는 약 1.3MB이며, 증명 자체는 66KiB다. 그럼에도 집계 비용은 서명당 약 42바이트에 불과하다. 이는 Falcon-512 서명(666바이트)보다 16배 작고, Falcon-1024 서명(1,280바이트)보다 거의 30배 작다.

일부 배포 환경에서는 솔트 비용을 아예 없앨 수 있다. 알고랜드의 deterministic Falcon은 서명을 결정론적으로 만들어 서명마다 필요한 무작위 솔트를 고정값으로 대체할 수 있게 한다. 이 서명을 집계하면 솔트가 전혀 필요 없고 66KiB 증명만 있으면 된다. 이를 위해서는 Aerie가 솔트와 서명 인코딩을 처리하는 방식을 조금만 바꾸면 된다.

Falcon 자체와 비교해도 Aerie의 프로버 비용은 낮다. 단일 코어에서 증명 생성 시간은 같은 서명들을 표준 Falcon 검증기로 검증하는 시간의 약 8배에 불과하며, 서명 생성 시간의 1.4배 수준이다.

가장 빠른 기존 Falcon 집계 방식인 Orthus와 비교하면, Aerie는 같은 AVX-512 서버의 단일 코어 기준으로 다음과 같다.

- 증명 생성은 1.5배 빠르다.

- 검증은 38배 빠르다.

- 증명 크기는 1.7배 더 작다.

또한 Aerie는 표준 Falcon 검증기가 확인하는 모든 항목을 증명한다. 기존 Falcon 집계 연구는 그렇지 않았다. 각 서명이 정규 인코딩됐는지 확인하는 검사를 생략했기 때문에, 표준 Falcon 검증기가 거부할 서명도 집계에서는 받아들일 수 있었다.

Aerie는 XMSS 서명을 집계하는 leanVM과도 비교했다. XMSS는 이더리움이 합의용으로 사용할 계획인 상태 기반 해시 서명 체계다. 같은 장비에서 Aerie는 초당 집계 가능한 서명 수가 leanVM보다 29배 많았다. 약 50,800개 대 1,770개다.

XMSS 같은 상태 기반 서명은 합의 계층에서는 잘 작동한다. 각 검증인이 슬롯당 최대 한 개의 메시지만 서명하므로 슬롯 번호 자체를 서명 상태로 사용할 수 있기 때문이다. 하지만 실행 계층에서는 큰 리스크를 낳는다. 사용자가 두 기기에서 서명하거나 백업에서 지갑을 복원하면 서명 상태를 재사용할 수 있고, 이 경우 공격자가 해당 키로 서명을 위조할 수 있다. 이 때문에 이더리움은 계정 서명에 상태 비저장 해시 기반 체계를 계획하고 있다. 그리고 상태 비저장 해시 기반 서명은 집계 비용이 더 크다. leanVM의 가장 최근 공개 벤치마크에 따르면 같은 노트북 모델에서 초당 약 820개를 집계하는데, 이는 Aerie보다 약 60배 느리다. 벤치마크된 구성은 각 키를 약 12만7,000개 서명으로 제한하지만, 훨씬 더 많은 서명을 허용하는 구성도 키 생성 비용만 더 들 뿐 집계 속도는 같다.

코드는 a16z/aerie에서 확인할 수 있고, 논문은 여기에서 볼 수 있다.

Aerie는 Alberto Centelles(임페리얼 칼리지 런던), Quang Dao(카네기멜런대), Justin Thaler(a16z crypto), Mohammadtaghi Badakhshan(LayerZero Labs)이 공동으로 진행한 작업이다.