양자 후 서명 집계: 폴딩 접근법

저자: Thomas Coratger , Srinath Setty

서론: 양자 후 서명 전환

이더리움과 같은 지분증명(Proof-of-Stake) 시스템에서 디지털 서명은 네트워크를 보호하는 수십만 명의 검증인에 대한 책임을 보장합니다. 엄청난 양의 검증 작업은 확장성 측면에서 큰 과제를 안겨줍니다. 바로 이렇게 많은 서명을 어떻게 효율적으로 검증할 것인가 하는 문제입니다. 이 문제를 해결하기 위해 이더리움의 합의 계층은 BLS 서명 체계를 채택했으며, 이는 네트워크 확장성을 확보하는 데 매우 중요한 역할을 했습니다.

BLS의 장점은 암호화 쌍( e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T e : G 1 × G 2 → G T )을 사용하여 매우 효율적인 서명 집계를 가능하게 하는 고유한 대수적 구조에 있습니다. 쌍 맵의 쌍선형성은 놀라운 특성을 제공하는데, 이는 전체 n 개의 서명 집합의 유효성을 단 하나의 방정식으로 확인할 수 있다는 것입니다.

이더리움의 실제 구현에서, 집계 서명은 위원회에서 어떤 검증자들이 참여했는지 를 식별하는 비트 필드(aggregation_bits ) 와 함께 제공됩니다. 검증자는 이 비트 필드를 사용하여 최종 암호화 검사를 실행하기 전에 집계 공개 키 (∑pk_i ) 를 계산 합니다 . 최종 검사는 상수 시간(두 번의 페어링)이 걸리지만, 전체 검증 비용에는 이 집계 공개 키를 구성하는 선형 시간 단계가 포함됩니다.

이 모델은 확장성에 필수적이며 Eth2 책 에 자세히 설명되어 있지만, BLS의 보안은 양자 컴퓨터에 취약한 문제에 기반하고 있습니다. 해시 기반 XMSS 와 같은 양자 컴퓨팅 이후의 대안으로의 전환은 확장성 문제를 다시 제기합니다. XMSS는 BLS의 대수적 속성을 결여하고 있으며, 서명 크기가 더 크고 검증에 많은 계산 비용이 소요되어 블록당 수천 개의 서명을 개별적으로 검증하는 것이 불가능합니다.

이 솔루션은 간결한 지식 논증(SNARK)을 사용하여 전체 서명 집합에 대한 단일하고 간결한 증명을 생성하는 새로운 형태의 서명 집계 방식입니다. (간단히 설명하기 위해 종종 상수 크기라고 하지만, 최신 해시 기반 SNARK의 증명은 기술적으로는 문장 크기에 대해 다항 로그적입니다.) 검증자는 P2P 네트워크에 분산되어 있으므로 단일 노드가 모든 서명을 수집하는 것은 현실적으로 불가능합니다. 따라서 집계 또한 분산 방식으로 이루어져야 하며, 서로 다른 노드가 중복되는 서명 하위 집합을 집계해야 합니다. 이러한 "증명의 증명" 요구 사항은 자연스럽게 재귀적 아키텍처로 이어집니다. 이 글에서는 이러한 재귀를 구현하는 두 가지 주요 패러다임을 비교합니다.

1. 재귀적 SNARK 검증: 다른 SNARK 회로 내에서 완전한 SNARK 증명을 검증합니다.
2. 특수화된 재귀적 기본 요소: 폴딩 기법을 활용하여 증명의 기본 수학적 명제를 직접 결합함으로써 전체 검증 단계를 생략합니다.

우리는 이더리움의 양자 보안 서명 집계 방향을 제시하기 위해 각 접근 방식의 메커니즘, 성능 및 장단점을 분석합니다.

집계 프레임워크

수십만 명의 참여자로 확장될 수 있는 검증자 집합의 증명을 처리하기 위해, 양자 후 검증 집계 시스템은 다계층 병렬 처리 방식으로 설계되어야 합니다. BLS 서명의 단순 합산과는 달리, SNARK 기반 증명 집계에는 구조화된 재귀적 접근 방식이 필요합니다. 이 과정은 집계 노드로 구성된 P2P 네트워크를 통해 진행되며, 최종적으로 온체인 검증을 위한 간결한 단일 증명을 생성합니다.

BLS 집계의 실제 적용: 현황

양자 컴퓨팅 이후 접근 방식을 자세히 설명하기 전에, 이더리움 합의 계층에서 BLS 서명을 사용하여 집계가 현재 어떻게 구현되는지 이해하는 것이 유용합니다. 핵심 메커니즘은 책임성을 보장하기 위해 참여를 추적하는 데 기반을 두고 있으며, 이는 보상과 벌칙을 정확하게 적용하는 데 필수적입니다.

검증자들은 각 슬롯별로 위원회로 구성됩니다. 위원회 소속 검증자가 증명을 생성하면 서명된 객체에는 `aggregation_bits` 라는 필드가 포함됩니다. 이 필드는 비트 목록이며, 각 위치는 해당 위원회 내에서 검증자의 인덱스에 해당합니다. 증명을 생성하는 검증자는 자신의 비트를 1로 설정합니다.

나중에, 동일한 체인 관점을 증명하는 여러 검증자의 증명을 통합할 수 있습니다. 이는 `aggregation_bits` 에 비트 단위 OR 연산을 수행하고 개별 BLS 서명을 타원 곡선 점 덧셈 방식으로 합산하여 이루어집니다. 결과적으로, 결합된 비트 필드와 하나의 통합 서명을 포함하는 단일 `Attestation` 증명 객체가 생성됩니다. 이를 검증하기 위해 노드는 최종 `aggregation_bits` 에서 비트가 1로 설정된 검증자들의 공개 키만 합산하여 통합 공개 키를 재구성합니다. 이 시스템을 통해 단 한 번의 효율적인 페어링 검사로 수백 개의 서명을 검증할 수 있으며, 누가 참여했는지에 대한 기록을 정확하게 보존할 수 있다는 점이 중요합니다.

양자역학 이후 시스템에서 비트필드를 이용한 참여 추적

양자역학 이후 프레임워크는 정확한 참여 추적에 대한 이러한 중요한 요구 사항을 계승합니다. 익명 서명 집합의 유효성을 단순히 증명하는 것만으로는 합의 프로토콜에 충분하지 않습니다. 따라서 시스템은 모든 서명자를 식별하기 위해 비트필드를 계속 사용합니다.

이더리움의 무허가형 모델에서 검증자 집합은 동적입니다. 이를 관리하기 위해 비콘 상태는 특정 시점에 활성화된 모든 검증자에 대한 표준적이고 순서가 정해진 레지스트리를 유지합니다. 검증자의 인덱스는 특정 상태에서 이 글로벌 레지스트리 내에서의 고유한 위치를 나타냅니다. 검증자가 참여하거나 탈퇴함에 따라 레지스트리는 변화하지만, 인덱스는 모든 합의 작업에 대해 안정적이고 명확한 참조를 제공합니다. 이를 통해 동적인 환경에서도 참여 현황을 정확하게 추적할 수 있습니다.

그림 1에서 보는 바와 같이, 각 양자 후 서명은 서명자의 전역 인덱스를 1로 표시하는 비트 필드와 연결됩니다. 증명이 집계될 때, 해당 비트 필드들은 비트 단위 OR 연산을 사용하여 결합됩니다. 이렇게 생성된 집계 비트 필드는 SNARK의 공개 입력값이 되어, 최종 증명이 "이 특정 비트 필드로 표시된 검증자들이 모두 유효한 서명을 제공했다"는 주장을 정확하게 입증하도록 합니다.

그림 1 292×224 7.72KB

고수준 설계: 집계(Aggregate) 및 병합(Merge )

이 시스템은 재귀적 구조의 기반이 되는 두 가지 핵심 암호화 연산을 토대로 구축되었습니다. 이러한 연산을 통해 작업 부하를 분산시킨 후 점진적으로 결합할 수 있습니다.

• 집계 (Aggregate) : 이는 초기 단계이며 재귀적이지 않습니다. 집계 노드는 검증자 하위 집합으로부터 원시 XMSS 서명 배치를 수집합니다. 각 서명을 개별적으로 검증한 후, 전체 서명의 유효성을 증명하는 초기 SNARK 증명을 생성합니다. 이러한 서명을 검증하고 올바른 비트필드를 구성하기 위해 각 집계 작업 노드는 전역 검증자 레지스트리에 접근할 수 있어야 합니다. 각 검증자의 인덱스를 해당 공개 키에 매핑하는 이 레지스트리는 필수적인 공개 입력 역할을 합니다. 이 작업은 검증 비용이 많이 드는 대규모 서명 집합을 단일의 간결한 증명 객체로 변환합니다.

• 병합 (Merge) : 이는 재귀적인 단계입니다. 집계 노드는 각각 서로 다른 서명 집합의 유효성을 증명하는 두 개의 기존 증명을 입력받아 결합합니다. 출력은 두 입력 증명의 모든 서명을 검증한 것과 동일한 암호학적 보장을 제공하는 새로운 단일 증명입니다. 이 연산은 확장성의 핵심이며, 증명을 효율적으로 결합할 수 있도록 합니다.

암호화 과정을 명확하게 설명하기 위해 그림 2와 같이 집계를 논리적 재귀 트리로 모델링합니다. 이 트리 구조 는 증명 시스템의 기본 구성 요소인 두 가지 핵심 암호화 단계, 즉 집계 (Aggregate) 와 병합(Merge)을 명확하게 분석할 수 있게 해주기 때문에 유용한 추상화입니다.

실제로 이 논리 모델은 동적인 P2P(피어 투 피어) 네트워크에서 구현됩니다. 높은 대역폭 요구 사항을 관리하기 위해 검증자 집합은 여러 서브넷으로 분할됩니다. 프로세스는 이러한 서브넷 내에서 병렬로 시작되며, 여기서 집계(Aggregate) 연산 을 사용하여 로컬 서명 집합으로부터 초기 증명이 생성됩니다. 그림 2에서 볼 수 있듯이 각 Agg 연산은 전역 상태(검증자 레지스트리)에 의존합니다. 이는 집계자가 이 전역 레지스트리에 쿼리를 보내 자신이 검증하는 서명을 가진 검증자에 해당하는 공개 키를 얻고 생성된 증명에 대한 집계 비트필드를 올바르게 업데이트해야 함을 의미합니다. 이러한 초기 증명은 네트워크 전체로 전파됩니다. 집계 노드는 증명을 수신하면 병합(Merge) 연산을 수행하여 점진적으로 더 큰 검증 자 집합을 증명하기 위해 증명을 결합합니다. 이러한 분산 병합은 전체 참여 검증자 집합의 증명을 나타내는 단일 최종 증명이 생성될 때까지 계속됩니다.

그림 2 815×499 32.4 KB

이 설계의 중요한 결과는 최종 증명만 블록체인에 제출된다는 점입니다. 크기가 고정된 이 단일 객체는 온체인에서 수천 개의 개별 서명을 처리해야 하는 필요성을 대체합니다. 선택된 암호화 패러다임은 집계 (Aggregate) 및 병합(Merge) 연산 을 모두 효율적으로 지원해야 합니다. 다음으로 살펴볼 근본적인 아키텍처 차이점은 바로 이 두 연산의 구현 방식 에 있습니다.

경로 A: 무차별 대입 SNARK 재귀 호출

재귀를 구현하는 가장 직접적인 아키텍처 패러다임은 완전한 SNARK 검증기를 다른 SNARK 회로 내부에 배치하는 것입니다. 이 모델에서 병합(Merge) 연산 은 다른 SNARK의 검증을 증명하는 SNARK입니다. 이러한 "증명을 검증하는 증명" 방식은 계산 집약적이기는 하지만 재귀를 구현하는 간단한 방법입니다.

핵심 메커니즘: 증명을 검증하는 증명

병합(Merge) 연산 의 기본 목표는 두 개의 입력 증명, 즉 증명 A 와 증명 B 를 받아 이들의 유효성을 입증하는 새로운 출력 증명, 즉 출력 증명 을 생성하는 것입니다. 병합 SNARK에서 증명되는 관계는 다음 과 같이 형식적으로 표현할 수 있습니다.

여기서 V 는 SNARK 시스템의 검증 알고리즘을 나타냅니다. \text{proof}_{\text{out}}을 생성 하기 위해, \texttt{Merge} 병합 단계의 증명 자는 새로운 증명의 산술 회로 내에서 두 입력 증명 모두에 대해 검증 알고리즘 V 의 전체 논리를 실행해야 합니다. 이는 해시 계산, 다항식 커밋먼트 검사, 필드 연산을 포함하여 검증자의 모든 암호화 단계를 산술화하는 것을 의미합니다. 최신 해시 기반 증명 시스템은 검증자가 비용이 많이 드는 페어링 연산을 필요로 하지 않기 때문에 이러한 작업에 적합합니다.

zkVM 추상화의 역할

이 접근 방식의 주요 과제는 검증기 회로의 엄청난 복잡성입니다. 최신 SNARK 시스템의 검증기는 정교한 암호화 연산 시퀀스를 포함하며, 이는 방대하고 매우 복잡한 제약 조건 시스템으로 이어집니다. 이러한 회로를 수작업으로 구축, 검토 및 유지 관리하는 것은 현실적으로 불가능하며 오류 발생 가능성이 매우 높습니다.

이러한 상황에서 제로 지식 가상 머신(zkVM)이 실질적으로 필수적입니다. zkVM은 이러한 복잡성을 관리하는 추상화 계층 역할을 하여 개발자가 저수준 회로 제약 조건 대신 익숙한 프로그래밍 모델을 사용하여 작업할 수 있도록 합니다. 작동 방식은 다음과 같습니다.

1. 고수준 논리: 개발자는 회로를 설계하는 대신 간단한 고수준 명령어 세트 아키텍처(ISA)를 사용하여 검증기의 논리를 구현하는 프로그램을 작성합니다. 이 프로그램은 집계(Aggregate) 단계 와 병합(Merge) 단계 모두에 대한 논리를 통합 된 방식으로 표현할 수 있습니다.

2. 암호화 사전 컴파일: zkVM은 비용이 많이 드는 암호화 기본 연산을 위한 고도로 최적화된 사전 컴파일된 회로를 갖추고 있습니다. POSEIDON 해시 순열 과 같은 연산은 상위 수준 프로그램 내에서 단일의 효율적인 명령어로 호출될 수 있습니다.

3. 컴파일 및 실행 추적: 컴파일러는 고수준 프로그램을 zkVM의 바이트코드로 변환합니다. 이 프로그램이 실행되면 zkVM의 검증 도구는 명령어 인출부터 메모리 접근까지 VM의 모든 상태 변화를 기록하는 완전한 실행 추적을 생성합니다. 이 전체 추적은 자동으로 최종 대규모 제약 조건 시스템으로 변환되어 SNARK에 의해 검증됩니다.

zkVM 내부 의 AggregateMerge 프로그램

zkVM 모델을 사용하면 집계 (Aggregate) 및 병합(Merge) 연산 을 단일 통합 프로그램 내에서 구현할 수 있습니다. 이러한 프로그램의 간소화된 버전인 집계 병합( AggregateMerge ) 은 공개 입력으로 모든 검증자 공개 키 목록과 이 단계에서 검증 대상이 되는 검증자를 나타내는 비트필드를 받습니다. 비공개 입력으로는 원시 XMSS 서명과 기존 SNARK 증명이 혼합되어 제공됩니다.

그렇다면 프로그램의 논리는 다음과 같을 것입니다:

1. 입력 증명을 재귀적으로 검증합니다. 제공된 각 내부 증명에 대해 SNARK 검증 함수(zkVM의 명령어와 사전 컴파일을 사용하여 구현됨)를 호출합니다.
2. 원본 서명을 직접 검증합니다. 제공된 각 원본 서명에 대해 XMSS 서명 검증 알고리즘을 실행합니다.
3. 비트필드 일관성 검사: 내부 증명의 비트필드와 원시 서명의 인덱스가 올바르게 결합되어 더 큰 새 출력 비트필드를 형성하는지 확인합니다.

zkVM 증명기는 이 \texttt{AggregateMerge} AggregateMerge 프로그램의 전체 실행에 대한 단일 SNARK 증명을 생성합니다.

성능 프로필 및 병목 현상

zkVM 기반 접근 방식의 주요 단점은 증명자가 부담하는 상당한 계산 오버헤드입니다. 증명자는 애플리케이션 로직(서명 및 증명 검증)을 증명하는 것뿐만 아니라 가상 머신 실행 자체의 정확성도 증명해야 합니다. 이러한 VM 오버헤드는 명령어 인출 및 디코딩부터 레지스터 업데이트, 메모리 접근, 점프와 같은 제어 흐름 로직에 이르기까지 CPU의 모든 내부 단계를 산술 연산하는 것을 포함합니다.

이러한 추가적인 작업 부하로 인해 각 병합(Merge) 단계 는 계산 집약적이 되며, 이는 곧 지연 시간 증가로 이어져 시간 제약이 있는 P2P 집계 네트워크에서 병목 현상을 일으킬 수 있습니다. 이는 검증 회로가 컴파일 시점에 미리 정해진 단일 프로그램에 특화되어 범용 CPU 아키텍처와 그에 따른 오버헤드가 필요 없는 "고정 프로그램" 재귀 방식과 대조적입니다.

하지만 해시 기반 SNARK의 성능 환경은 빠르게 진화하고 있다는 점에 유의해야 합니다. 기본 증명 시스템의 순수 성능이 충분히 높다면 "충분히 좋은" 원칙이 적용될 수 있습니다. 최근 증명 기술의 발전으로 매우 높은 처리량을 달성하고 있습니다. 이러한 추세가 지속된다면 zkVM의 지속적인 오버헤드는 개발자 경험과 유연성 측면에서 얻을 수 있는 이점과 맞바꿀 수 있는 절충안이 될 수 있으며, 시간 제약이 있는 애플리케이션에서도 실행 가능한 옵션이 될 수 있습니다. 높은 증명 비용에도 불구하고, 최신 해시 기반 SNARK는 매우 간결한 증명을 생성할 수 있어 온체인 크기 목표를 달성할 수 있습니다.

경로 B: 특수화된 재귀적 기본 요소

무차별 대입 재귀 방식의 대안으로, 이 작업을 위해 특별히 설계된 암호화 기본 요소인 폴딩 및 누적 방식을 활용할 수 있습니다. 이 방식은 회로 내에서 완전한 SNARK를 검증하는 대신, 증명의 기본 수학적 명제에 직접 접근합니다. 이를 통해 여러 계산 무결성 주장을 단일하고 동등한 주장으로 결합하는 매우 효율적인 암호화 지름길을 제공하여, 각 재귀 단계에서 증명자의 작업량을 크게 줄입니다.

인스턴스-위트니스 프레임워크

이 접근 방식의 핵심은 특정 NP 관계 R 에 대한 계산 명제를 나타내는 인스턴스-증인 쌍 ( x , w ) 의 개념입니다. 인스턴스 x 는 명제의 공개 데이터를 포함하고, 증인 w 는 명제를 만족시키는 비밀 데이터를 포함합니다. 이 통일된 구조는 집계 (Aggregate) 및 병합(Merge) 연산 모두에 사용됩니다.

• 집계 단계 : 이 연산은 첫 번째 인스턴스-증인 쌍을 생성합니다. 관계 R 은 XMSS 서명 검증 알고리즘입니다. 인스턴스 x는 공개 데이터 (메시지, 비트 필드 및 관련 공개 키)로 구성되고, 증인 w 는 비밀 데이터(원시 XMSS 서명)로 구성됩니다. 출력은 폴드 또는 누적 준비가 된 초기 인스턴스-증인 쌍입니다.
• 병합 단계 : 이 연산은 두 개의 인스턴스-증인 쌍, (x_1, w_1) ( x₁ , w₁ ) 과 ( x_2, w_2) ( x₂ , w₂ ) 를 입력 받아 경량 프로토콜을 사용하여 동일한 관계 R에 대한 단일 폴딩 쌍, (x_{\text{folded}}, w_{\text{folded}}) ( x₁folded , w₁folded ) 를 계산 합니다. 이 과정은 회로 내에서 전체 SNARK 검증기 를 실행하는 것보다 계산 비용이 훨씬 저렴합니다. 또한, 폴딩 증명기는 동일한 관계에 대한 SNARK 증명기보다 계산 비용이 저렴합니다.

이제 우리는 이러한 패러다임을 구현하는 두 가지 양자역학적 메커니즘을 살펴보겠습니다.

격자 기반 접기

폴딩 스키마는 두 개의 관계 인스턴스를 결합하여 동일한 관계의 새로운 인스턴스를 하나 생성하는 프로토콜입니다. 양자 컴퓨팅 이후의 폴딩 스키마의 대표적인 예로는 Neo가 있으며, 이는 양자 컴퓨팅 이후의 격자 가정을 기반으로 합니다.

격자 기반 암호화에서 핵심적인 과제는 증인의 노름(norm)을 관리하는 것입니다. 선형 조합과 같은 암호화 연산을 수행하면 이 노름이 증가합니다. 노름이 너무 커지면 커밋먼트 체계의 보안이 무너질 수 있습니다. 네오는 이러한 노름 증가를 신중하게 관리하는 3단계 주기로 설계되었습니다.

본 사용 사례에서, 집계( Aggregate ) 단계는 XMSS 검증 회로를 나타내는 Matrix CCS(MCS)라는 관계에 대한 초기 인스턴스-증거 쌍을 생성합니다. 그런 다음 병합 (Merge) 작업은 이 새로운 MCS 인스턴스와 실행 중인 누적기(더 간단한 평가 관계인 ME의 인스턴스)를 가져와 Neo의 사이클을 실행합니다(그림 3은 이 워크플로를 보여줍니다).

그림 3 824×450 65.3KB

해시 기반 분할 누적

재귀를 위한 또 다른 기본 요소는 분할 누적 방식입니다. 이 방식은 여러 관계에 대한 주장들의 유효성을 증명하는 누적기를 지속적으로 유지합니다. 분할 누적 방식과 폴딩 방식은 동시에 도입되었습니다. 두 방식 사이에는 몇 가지 구체적인 차이점이 있지만, 본 설명에서는 중요하지 않습니다. 병합(Merge) 연산 은 이 누적기에 새로운 주장을 추가하는 것입니다. 양자 컴퓨팅 이후 분할 누적 방식의 대표적인 예로는 WARP가 있습니다. WARP는 양자 컴퓨팅 이후 해시 함수를 기반으로 하며, 증명자의 성능을 극대화하도록 특별히 설계되었습니다.

분할 적립 방식

분할 누적 방식의 핵심 아이디어는 누적기를 두 부분으로 나누는 것입니다. 하나는 작고 공개된 인스턴스 부분이고, 다른 하나는 크고 비공개된 증거 부분입니다. 각 재귀 단계에서 증명자( P_{ACC} P A C C )는 이전 누적기와 새로운 주장을 입력받아 업데이트된 누적기를 생성하고, 이 전환에 대한 간단한 증명을 생성합니다.

핵심은 검증자( V_{ACC} V A C C )가 이 전환 증명을 확인하기 위해 기존 및 새로운 누적기의 공개 인스턴스 부분만 필요로 한다는 점입니다. 검증자는 대규모 증거 부분을 보거나 처리하지 않으므로 재귀적 검증 단계가 매우 가볍습니다. 전체 증거는 프로세스의 맨 마지막 단계에서 최종 증명자("결정자")가 온체인 SNARK를 생성할 때만 필요합니다.

회로에서 다항식까지: PESAT

WARP 프레임워크에서 누적되는 클레임은 다항식 만족 가능성(PESAT) 인스턴스로 표현됩니다. WARP는 계산을 게이트 회로로 표현하는 대신, 주어진 인스턴스와 증거에 대해 모두 0으로 평가되어야 하는 다항식 방정식 집합으로 표현합니다. 이는 R1CS 및 CCS와 같은 일반적인 제약 조건 시스템을 포괄할 수 있는 매우 범용적인 프레임워크입니다. 본 사용 사례에서 XMSS 서명 검증 알고리즘과 비트필드 로직은 PESAT 인스턴스로 컴파일됩니다.

선형 시간 증명기

WARP의 가장 큰 장점은 선형 시간 증명기입니다. 필드 연산과 해시 계산으로 측정되는 증명기의 실행 시간은 계산 규모에 비례하여 선형적으로 증가합니다. 이는 증명기 효율성 측면에서 획기적인 발전이며, 다른 시스템에서 발견되는 두 가지 주요 오버헤드 원인을 제거합니다.

• 초선형 비용( O(N \log N) O ( N log ) 그룹 기반 암호화의 N ) 은 대규모 다중 스칼라 곱셈이 지배적입니다.
• 범용 zkVM은 애플리케이션 로직 외에도 자체 CPU 아키텍처의 실행을 입증해야 하므로 상당한 고정 오버헤드를 발생시킵니다.

서명 집계와 같은 대규모의 반복적인 작업의 경우, 선형 시간 증명기는 성능을 크게 향상시켜 재귀 엔진에 매우 매력적인 옵션이 됩니다.

최종화: 온체인 SNARK 생성

재귀적인 병합(Merge) 프로세스 는 폴딩(folding) 또는 누적(accumulation) 방식을 통해 최종 인스턴스-증인 쌍을 생성합니다. 이 쌍은 계산적으로 유효하며, 집계된 서명 전체를 정확하게 나타내지만, 전통적인 의미에서 간결하지는 않습니다. 증인 구성 요소는 여전히 존재하며 최종 증명자가 필요로 하기 때문에 객체의 크기가 너무 커서 온체인에서 직접 검증하기 어렵습니다.

결과적으로 최종 집계 노드는 추가 단계를 수행해야 합니다. 즉, 최종 접힌 쌍에 대한 표준 비재귀 SNARK를 생성해야 합니다. 이로 인해 두 개의 서로 다른 암호화 엔진을 사용하는 하이브리드 아키텍처가 만들어집니다.

1. 재귀 엔진: 증명 효율성을 위해 선택된 폴딩 또는 누적 방식입니다. 주요 목적은 각 재귀 단계에서 낮은 계산 비용으로 여러 문장을 하나로 결합하는 것입니다.
2. 간결성 엔진: 온체인 사용을 위해 간결하고 효율적으로 검증 가능한 증명을 생성하는 데 사용되는 최종 비재귀 SNARK입니다.

최종화 파이프라인은 다음과 같습니다.

1. 최종적으로 접힌 사건-증인 쌍은 입증되어야 할 진술로 취급됩니다.
2. (Super)Spartan 과 같은 다항식 대화형 오라클 증명(PIOP)을 적용하여 접힌 증거에 대한 지식 증명 작업을 다선형 다항식 평가 주장 집합으로 축소합니다.
3. BaseFold 또는 WHIR 과 같은 양자역학 기반 다항식 커밋먼트 스키마(PCS)를 사용하여 평가를 증명합니다.

이 하이브리드 아키텍처는 효율적인 재귀 기능과 최종 결과의 간결성이라는 두 가지 기능을 분리합니다. 각 접근 방식의 장점을 활용하여 확장 가능하고 온체인 증명을 간결하게 생성하는 시스템을 구축합니다.

공학적 과제: 증인 관리

이 경로에서 중요한 엔지니어링 과제는 P2P 네트워크를 통한 증명 데이터 관리입니다. 모든 병합(Merge) 단계 의 증명자는 결합되는 두 증명의 증명 데이터에 접근해야 합니다. 단순한 구현 방식으로는 이러한 대용량 증명 데이터를 전송해야 하므로 상당한 대역폭 병목 현상이 발생할 수 있습니다.

이 문제는 증인 청킹 기법을 사용하여 프로토콜 수준에서 해결할 수 있습니다. 이 접근 방식은 증인 처리 방식을 변경하여 대역폭 요구 사항을 완화합니다.

1. 청크 분할 커밋: 대규모 증거는 단일 객체로 취급되지 않고 여러 개의 더 작고 일정한 크기의 벡터로 분할됩니다. 그런 다음 증명자는 이러한 각 청크에 대해 개별적으로 커밋합니다.

2. 청크 폴딩: 두 개의 증명을 폴딩하면 결과적으로 생성되는 폴딩된 증명은 단 하나의 작은 벡터가 됩니다. 따라서 재귀 단계 간에 전달해야 하는 암호화 상태는 크기가 일정하고 간결하게 유지되어 데이터의 누적 증가를 방지합니다.

3. 효율적인 검증: 이 방법은 재귀적 검증기가 처리해야 하는 커밋먼트 수를 증가시키지만, Neo와 같은 체계는 이를 효율적으로 처리하도록 설계되었습니다. 증인 청크에 대한 커밋먼트는 검증기 회로에 상당한 복잡성이나 비용을 추가하지 않고도 통합될 수 있습니다.

이 설계는 문제를 암호화 제한에서 P2P 데이터 가용성 문제로 재구성합니다. 즉 , 집계 노드가 병합 작업 을 수행하기 위해 네트워크에서 필요한 증거 청크를 찾아 가져올 수 있도록 보장하는 것입니다.

절충점: 격자 기반 vs. 해시 기반 기본 요소

Neo와 같은 격자 기반 폴딩 방식과 WARP와 같은 해시 기반 누적 방식 중 하나를 선택하는 것은 주로 보안 가정과 성능 및 구현 복잡성 사이의 아키텍처적 절충을 수반합니다.

• 보안 가정: 이것이 해시 기반 방식의 가장 큰 장점입니다. 이러한 방식의 보안은 일반적으로 랜덤 오라클로 모델링되는 암호화 해시 함수의 속성에만 의존합니다. 이는 폴딩/스플릿 누적과 같은 최소한의 가정이지만 널리 신뢰받고 있습니다. 반면, 격자 기반 방식은 모듈-SIS(Module Short Integer Solution) 문제와 같은 구조화된 가정에 의존합니다. 양자 컴퓨팅 이후의 난해함으로 강력하게 여겨지지만, 특정 격자 매개변수화의 실제 보안은 활발히 연구되고 발전하는 분야입니다. 하이브리드 공격 에 대한 실질적인 개선과 같은 암호 분석의 지속적인 발전은 구체적인 보안 수준에 대한 이해를 더욱 정교하게 만들고, 단순한 해시 기반 방식에는 없는 장기적인 위험 요소를 도입합니다.

• 재귀 오버헤드: 이는 격자 기반 방식의 핵심 장점입니다. 해시 기반 시스템의 재귀적 '병합' 단계에서는 다음 증명 과정에서 머클 경로의 열림 여부를 검증해야 합니다. 반면 격자 기반 방식에서는 폴딩 연산이 보다 대수적이며, 전체 암호화 객체를 검증하지 않고 수학적 명제를 직접 결합합니다. 따라서 재귀 검증 회로가 훨씬 간단해지며, 결과적으로 계산 오버헤드를 크게 줄일 수 있습니다.

• 특수 기능: Neo와 같은 격자 기반 구조는 고유한 성능 이점을 제공할 수 있습니다. 예를 들어, Neo는 "비트당 지불" 방식의 커밋 비용을 도입하여, 증인(witness)에 대한 커밋 비용이 해당 값의 비트 폭에 비례하도록 합니다. 이는 많은 증인 값이 작은 실제 연산에 매우 유리하며, 모든 데이터를 머클 해싱을 위한 전체 크기 필드 요소로 처리하는 해시 기반 시스템에서는 일반적으로 찾아볼 수 없는 특징입니다.

건축적 절충에 대한 비교 분석

무차별 대입 재귀 방식과 특수화된 기본 요소 방식 중 어느 것을 선택할지는 시스템 설계에서 뚜렷한 장단점을 수반합니다. 두 접근 방식은 주로 복잡성을 암호화 증명 인프라에 배치하는지 아니면 P2P 프로토콜 계층에 배치하는지에 따라 차이가 나며, 결과적으로 성능과 개발 추상화 사이의 균형에도 차이가 발생합니다. 다음 표는 이 두 가지 아키텍처 방식의 주요 차이점을 요약합니다.

표 1: 재귀적 집계 아키텍처 비교

결론

이더리움 합의 계층의 양자 보안 서명 체계로의 전환에는 재귀적 집계 아키텍처가 필수적입니다. 이러한 아키텍처를 선택하는 것은 간단한 결정이 아닙니다. zkVM과 폴딩 방식은 각각 고유한 강점과 엔지니어링 과제를 가지고 있습니다.

무차별 대입 방식의 SNARK 재귀 호출을 특징으로 하는 경로 A는 zkVM을 사용하여 암호화 복잡성을 추상화함으로써 이를 관리합니다. 이 접근 방식은 애플리케이션 로직 개발을 단순화하지만, 증명자가 VM의 실행 추적을 증명해야 하므로 재귀 단계에서 상당한 계산 오버헤드가 발생하며 이는 불가피합니다.

경로 B는 폴딩 및 누적 방식과 같은 특수한 기본 요소를 사용하며, 재귀에 더욱 효율적인 암호화 엔진을 활용하여 고성능을 발휘하도록 설계되었습니다. 이러한 설계는 복잡성을 암호화 코어에서 P2P 프로토콜 계층으로 옮겨놓으며, 따라서 프로토콜 계층은 증거 데이터 가용성과 같은 문제들을 해결해야 합니다.

궁극적으로 이더리움의 최적 경로는 아직 확정되지 않았으며, 활발한 연구가 진행 중인 분야입니다. 최적의 경로는 zkVM과 폴딩 기술의 지속적인 발전, P2P 네트워크 역학에 대한 추가 분석, 합의 계층의 정확한 성능 및 보안 요구 사항, 그리고 범용성과 특수성 중 어느 것이 장기적인 가치를 지니는지에 대한 전략적 선택에 달려 있습니다. zkVM 기반 솔루션은 특정 작업에서는 성능이 다소 떨어질 수 있지만, 프로토콜의 향후 다른 요구 사항도 충족할 수 있는 유연한 인프라를 제공하는 반면, 특수화된 폴딩 방식은 고도로 최적화되었지만 활용 범위가 제한적일 수 있습니다. 이 글은 이러한 근본적인 장단점을 명확히 하고, 현재 진행 중인 논쟁에 대한 체계적인 틀을 제공하는 것을 목표로 했습니다.