블록 업데이트 다이제스트: 전역 상태 트리가 없는 멤버십 증명

저자: Cody Littley, Alejandro Ranchal-Pedrosa( @alranpe ), Omar Garcia — 세이(Sei) Labs

요약: BUD는 전체 상태 크기가 아닌 블록별 쓰기 거래량 에 따라 확장되는 멤버십 증명 방식이며, 핵심 경로에 전역 상태 트라이가 필요하지 않습니다.

동기 부여

멤버십 증명( eth_getProof 에서 제공하는 상태 증명이라고도 함)은 오프체인 관찰자가 제3자를 신뢰하지 않고도 온체인 값을 암호학적으로 검증할 수 있도록 합니다. 표준 접근 방식은 전체 상태에 대해 머클 트라이를 구축하여 루트 해시 에 대한 서명과 머클 경로를 통해 모든 키의 포함 또는 제외를 증명합니다.

이 접근 방식의 비용은 전체 상태 크기에 비례하여 증가합니다. 모든 블록 수백만 개의 계정과 저장 슬롯에 걸쳐 있는 리프 노드를 가진 트리를 업데이트해야 합니다. 처리량이 높은 EVM급 체인의 경우, 이러한 오버헤드는 순수 연산량과 데이터베이스 레이아웃 측면에서 모두 심각한 병목 현상을 초래합니다. 이더리움 L1조차도 전역 상태 트라이를 유지 관리하는 데 상당한 복잡성과 I/O 비용을 수반합니다.

본 논문에서는 블록 업데이트 다이제스트(BUD)를 제안합니다. BUD는 상태 확정 비용을 전체 상태 크기와 분리하고, 대신 블록별 업데이트 거래량 에 따라 확장하는 증분 인증 데이터 구조입니다. BUD는 SuperBUD 라고 부르는 계층적 다이제스트 레이어와 온디맨드 터치 트랜잭션을 결합하여 지연 시간, 증명 크기 및 비용 요구 사항의 전체 범위를 포괄합니다.

이진 상태 트리와 버클 트리의 차이점

이더리움 L1 로드맵은 장기적인 상태 커밋먼트 메커니즘으로 바이너리 상태 트리(이더리움 개선 제안(EIP)-7864)에 집중하고 있으며, 상태 증명의 O(1 ) SNARK 검증 을 향한 경로를 제시합니다. 합의에 중요한 경로에서 전역적으로 인증된 데이터 구조를 유지하는 데 전념하는 체인의 경우, 이러한 제안은 현재의 MPT보다 확실히 개선된 것입니다. BUD는 완전히 다른 질문을 다루며, 경쟁 관계가 아니라 상호 보완적입니다.

BUD는 다른 아키텍처적 질문을 다룹니다. 즉, 인증된 데이터 구조가 합의에 중요한 경로에 존재해야 하는가 하는 것입니다.

구현 효율(MPT, 바이너리, Verkle 등)에 관계없이 전역 상태 트리는 모든 검증자가 블록 실행 중에 트라이 형태의 데이터 구조를 유지하고 업데이트해야 합니다. 트라이는 데이터베이스 레이아웃을 제약하고, 모든 쓰기 작업에서 트리 깊이에 비례하는 I/O 증폭을 유발하며, 실행 처리량과 상태 커밋 비용을 얽히게 합니다. 완벽한 바이너리 트라이조차도 O(log n) O ( log n )의 시간 복잡도를 가지게 됩니다. n ) 경로는 O(w ⋅ log n) O ( w ⋅ log) 를 부과합니다. n ) w w 상태 쓰기에 대한 블록 당 해시 계산 횟수이며, 데이터베이스는 중간 노드를 트라이 친화적인 레이아웃으로 저장해야 합니다.

BUD(Buy Outcomes Design)는 고처리량 실행 환경에서 트라이(Trie)는 검증자의 핵심 경로에 적용하기에 부적절한 추상화 구조라고 주장합니다. 대신, 검증자는 블록별로 경량의 다이제스트(쓰기 세트에만 비례하는 비용, 전체 상태 크기에 의존하지 않음)를 생성하고, 완전한 증명 인프라는 아카이브 노드에 위임합니다. 상태 자체는 트라이 형태의 I/O 제약 없이, 순수 실행 속도에 최적화된 평면 키-값 저장소 구조로 저장될 수 있습니다.

이는 임시방편이 아니라 아키텍처적인 선택입니다. BUD를 채택하는 체인점은 "더 나은 트라이로 마이그레이션하기를 기다리는" 것이 아니라, 핵심 경로에서 전역 트라이를 아예 유지하지 않기로 선택한 것입니다.

SNARK 검증 논증은 대칭적이라는 점에 유의해야 합니다. BUD 머클 증명 역시 SNARK로 검증할 수 있으며, BUD 트리가 더 작기 때문에(전체 상태가 아닌 블록 기록 집합에 비례함) 회로가 더 간단합니다. 크로스체인 브리지와 라이트 클라이언트를 위한 SNARK 검증 상태 증명이 최종 목표라면 두 접근 방식 모두 목표 달성에 도움이 됩니다. 문제는 순전히 블록 생성 과정에서 검증자에게 부과되는 비용에 관한 것입니다.

핵심 아이디어

버즈

BUD는 단일 블록 (또는 더 일반적으로 k 개의 블록으로 이루어진 연속된 윈도우)에 의해 생성된 변경 사항을 기반으로 구축된 작은 머클 트리입니다. 각 리프는 다음을 기록합니다.

1. 열쇠,
2. 그것의 새로운 가치,
3. 현재 블록 번호, 그리고
4. 키가 마지막으로 수정된 이전 블록 번호입니다.

필드(4)는 중요한 추가 사항입니다. 이는 BUD 시퀀스를 통해 키별 수정 체인을 연결하여 동일한 키에 대한 두 개의 인접한 BUD 항목이 그 사이에 아무것도 변경되지 않았음을 증명할 수 있도록 합니다. 이를 지원하기 위해 키 값 저장소의 각 항목에는 마지막 수정의 블록 높이를 기록하는 8바이트의 메타데이터가 추가로 포함됩니다(직렬화 버전 필드에 대한 1바이트 추가).

그림 1: BUD 머클 트리의 구조. 각 리프는 (키, 새 값, 현재 블록 번호, 수정된 이전 블록 번호)를 기록합니다. BUD 해시 쿼럼이 (n+f)/2 예치(stake) 보다 큰 검증자에 의해 서명됩니다.

BUD 트리 다이어그램 1600×815 127KB

검증자는 일반적인 방식으로 BUD 해시에 서명하고 서명을 집계합니다(쿼럼은 > (n+f)/2 > ( n + f ) / 2 예치(stake), 여기서 최대 f 는 공격자입니다). 그런 다음 BUD는 장기 저장 및 증명 제공을 위해 아카이브 노드로 스트리밍됩니다.

트리는 블록 에서 수정된 키에 대해서만 구축되므로, 구축 비용은 전체 상태 크기가 아니라 블록의 쓰기 집합에 비례합니다. 10,000개의 키를 수정하는 블록 전체 상태에 1억 개의 항목이 있더라도 10,000개의 리프 노드로 구성된 트리를 구축합니다.

슈퍼버즈

단일 BUD는 키가 수정된 블록 에서의 값을 증명하지만, d d 블록 전에 마지막으로 기록된 키의 현재 값을 조회하는 라이트 클라이언트는 제외된 BUD를 찾기 위해 d d개의 BUD를 확인해야 합니다. SuperBUD는 이러한 선형 스캔을 로그 스캔으로 압축합니다.

레벨 \ell ℓ SuperBUD는 e^\ell e ℓ 블록(설정 가능한 기본 e e 에 대해, 구체적인 인스턴스로 e = 2 e = 2를 사용)에 걸쳐 있으며, e^\ell e ℓ 의 배수인 블록 높이에서 생성됩니다. 내부적으로 SuperBUD는 해당 범위 내에서 접촉된 각 키를 해당 키가 수정된 가장 최근 블록 번호에 매핑하는 Merkle 트라이입니다. 같은 레벨에 있는 두 개의 인접한 SuperBUD는 키 집합의 합집합을 취하고, 두 SuperBUD 모두에 나타나는 키에 대해서는 더 최근 블록 번호만 유지함으로써 다음 레벨의 단일 SuperBUD로 병합될 수 있습니다. 이 병합은 정렬된 두 트라이에 대한 단일 O(n) O ( n ) 조정 순회입니다.

주어진 키에 대한 SuperBUD 증명은 (a) 해당 키가 수정된 스팬 내 최상위 블록 보여주거나, (b) 해당 키가 스팬 내에서 전혀 수정되지 않았음을 보여줍니다. 식별된 블록 에서의 BUD 증명과 결합하면 완전한 멤버십 증명이 됩니다.

그림 2: 기본 e=2 e = 2 인 블록 B0–B11에 대한 SuperBUD 계층 구조. 레벨 1 SuperBUD는 2개의 블록에 걸쳐 있고, 레벨 2는 4개의 블록에 걸쳐 있으며, 레벨 3은 8개의 블록에 걸쳐 있습니다. 같은 레벨에 있는 인접한 SuperBUD는 단일 O(n) O ( n ) 순회를 통해 다음 레벨로 병합됩니다.

SuperBUD 계층 구조 타임라인 1380×340 28.2KB

지연 시간 및 증명 크기. 마지막 수정이 d d 블록 전에 발생했다면 클라이언트는 레벨 \lceil \log_e d \rceil ⌈ log e 의 SuperBUD가 필요합니다. d ⌉ . 최악의 경우, 클라이언트는 e^{\lceil \log_e d \rceil} e ⌈ log e 까지 기다립니다. d ⌉ 블록은 해당 레벨에서 다음으로 정렬된 창이 닫힐 때까지 대기합니다. 따라서 대기 시간은 최악의 경우 지연 시간에 비례하여 선형적으로 증가하지만, 이러한 계층 구조의 장점은 증명의 간결성 입니다. 즉, 블록별 배제 증명의 선형적인 연결 대신 로그 함수적인 다이제스트 조회 횟수와 상수 개수의 머클 경로만 필요합니다.

터치 트랜잭션

SuperBUD는 온체인 비용 없이 증명 간결성을 위해 지연 시간을 감수하는 반면, 터치 트랜잭션은 그 반대의 장단점을 제공합니다. 즉, 소액의 온체인 수수료를 지불하면 키가 얼마나 오래되었는지에 관계없이 현재 블록 에서 즉시 BUD 증명을 얻을 수 있습니다.

터치 트랜잭션은 키 값을 수정하지 않고, "최종 수정일" 메타데이터만 업데이트하고 현재 블록의 BUD(Built Update Data)에 항목을 생성합니다. 이는 유닉스 셸의 touch 명령어와 유사합니다. 즉, 콘텐츠를 변경하지 않고 타임스탬프를 갱신하는 것입니다. 터치 트랜잭션은 블록체인의 기존 리소스 사용량 측정 방식(상태 접근 및 메타데이터 쓰기 단위당)에 따라 요금이 부과되므로, 기존 수수료 체계에서 고려된 것 외에 새로운 DoS 공격 표면을 생성하지 않습니다.

SuperBUD와 터치 트랜잭션은 함께 지연 시간/비용 설계의 전체 영역을 아우릅니다. 비용에 민감한 사용자는 SuperBUD를 기다리고, 지연 시간에 민감한 사용자는 터치를 이용합니다.

증명 전략

BUD와 SuperBUD는 각각 다른 장단점을 가진 여러 가지 검증 전략으로 구성됩니다.

단일 BUD 증명. 조회된 블록 높이가 수정(또는 터치)과 일치하는 경우, 하나의 BUD 증명으로 충분합니다. 매우 간결하지만 수정 지점에서만 사용할 수 있습니다.

이중 BUD 증명. 동일한 키에 대해 두 번 연속으로 BUD 증명을 수행하고, 두 번째 증명의 "이전 블록 수정" 필드가 첫 번째 증명을 가리키도록 하면, 그 사이의 모든 블록 에서의 값이 동일함을 증명할 수 있습니다. 키별 수정 체인은 중간 변경 사항이 누락되지 않았음을 보장합니다.

BUD + SuperBUD. 마지막 수정 시점의 BUD 증명과 해당 수정 시점 및 대상 블록 모두 포함하는 범위의 SuperBUD를 결합한 방식입니다. SuperBUD는 해당 범위 내에 이후의 수정 사항이 없음을 증명합니다. 소형이고 저렴하지만, 최근 수정된 항목의 경우 지연 시간이 적당하고 오래된 항목의 경우 지연 시간이 더 깁니다.

그림 3: BUD + SuperBUD 전략. 블록 B2에서의 BUD 증명과 A~C에 걸친 SuperBUD를 결합하면 터치 트랜잭션 없이 SuperBUD의 상한선까지 모든 블록 에서 키 K의 값을 증명할 수 있습니다.

BUD + SuperBUD 전략 다이어그램 1441×940 64.8KB

BUD와 여러 개의 SuperBUD를 함께 사용하는 방식입니다. 터치 트랜잭션 없이 지연 시간을 줄이려면, 인접한 여러 SuperBUD를 연결하여 간격을 메울 수 있습니다. 이 방식은 압축률이 낮아지지만(증명 크기가 오래될수록 증가함), 온체인 비용을 절감할 수 있습니다.

최초 수정 증명. BUD 항목의 "이전 블록 수정됨" 값이 -1 − 1 인 경우, 해당 키가 그 블록 이전에는 존재하지 않았음을 증명합니다(설정 가능한 증명 마감 시간 기준). 배제 증명 및 최근에 생성된 키에 유용합니다.

디자인 선택 및 유연성

이 구조물은 의도적으로 모듈식으로 설계되었습니다. 유연성의 주요 축은 다음과 같습니다.

BUD의 세분성. 기본값으로 1:1 비율( 블록 당 BUD 1개)을 제시하지만, 이전 윈도우 기간 동안 k 개의 블록마다 BUD를 생성할 수도 있습니다. 이는 증명 정확도가 약간 떨어지는 대신 서명 오버헤드를 분산시킵니다.

SuperBUD의 기본 구조와 일정. 계층 구조의 기본 e 는 분기 계수를 제어합니다. e = 2 일 때, 레벨 간격은 두 배로 늘어나고(2, 4, 8, 16, …), 최대 병합 깊이 L 은 최대 증명 기간을 결정합니다. 즉, 시스템은 최근 e^L e L 블록 내의 모든 블록 에 대한 증명을 지원합니다. e 값 이 클수록 레벨 수는 줄어들지만 최악의 경우 대기 시간은 늘어납니다. 체인의 완결성 주기가 특정 경계를 더 자연스럽게 만드는 경우, 생산 일정( e^\ell e ℓ 의 배수에 맞춰 정렬됨)을 조정하거나 분산시킬 수 있습니다.

최대 증명 기간 및 툼스톤. 키를 삭제해도 수정 체인이 파괴되어서는 안 됩니다. 항목을 삭제하는 대신, 상태는 툼스톤(nil 값, "마지막 수정" 메타데이터 유지)을 기록합니다. 구성 가능한 최대 증명 기간(예: 블록의 일 또는 월)은 툼스톤이 유지되는 기간을 제한합니다. 툼스톤이 설정된 기간보다 오래되면 가비지 컬렉션됩니다. 설정된 기간 이전에 생성된 증명은 무기한으로 유효하고 검증 가능합니다. 만료되는 것은 매우 오래된 블록에 대한 새로운 증명을 생성하는 기능입니다.

배제 증명. SuperBUD만으로는 키의 기존 상태에 대해 아무것도 주장하지 않기 때문에 배제를 증명할 수 없습니다. 완전한 배제 증명을 위해서는 BUD 항목(존재하지 않는 키에 대한 터치 트랜잭션을 통해 생성될 수 있으며, 이 과정에서 툼스톤이 생성됨)이 필요합니다. 이는 의도적인 설계상의 절충입니다. 존재하지도 않고 툼스톤도 없는 키의 부재를 증명하는 예외적인 경우는 매우 드물기 때문에 터치 트랜잭션을 요구하는 것이 허용 가능합니다.

전역 상태 트리와의 비교

핵심적인 장단점은 다음과 같습니다. 전역 트라이는 실행과 트라이 유지 관리가 얽혀 있다는 단점이 있지만, 모든 키에 대해 최근 블록 에서 즉각적인 증명을 제공합니다. BUD는 수정 시점(또는 touch를 통한 요청 시)에서만 즉각적인 증명을 제공하지만, 실행 계층을 트라이 구조의 제약에서 해방시킵니다.

목표 및 다음 단계

BUD는 합의에 중요한 경로에서 전역 상태 트리를 유지하는 것에 대한 영구적인 아키텍처 대안입니다. BUD는 더 나은 트라이를 채택할 때까지 기다리는 체인을 위한 과도기적 메커니즘도 아니고, 기존 트라이 위에 추가되는 보완재도 아닙니다. 오히려 BUD는 검증자의 중요 경로에서 전역 인증 데이터 구조를 전혀 유지하지 않고, 제약 없는 실행 처리량을 얻는 대가로 증명 인프라를 아카이브 노드에 위임하기로 선택한 체인을 위해 설계되었습니다.

주요 대상은 상태 트라이 유지 관리가 실행 병목 현상이 되었거나 될 가능성이 있는 고처리량 EVM 유사 L1 및 롤업 서버입니다. 이더리움 L1 서버의 경우 바이너리 트리 마이그레이션(이더리움 개선 제안(EIP)-7864)이 이미 진행 중이므로 BUD는 적합한 솔루션이 아닙니다. 하지만 상태 커밋 전략을 처음부터 설계하거나 상태 증가에 따라 전략을 재고하는 블록체인의 경우, BUD는 근본적으로 다른 확장 경로를 제공합니다.

저희는 건설 계획을 공식화하기 위해 정보 제공 목적의 이더리움 개선 제안(EIP)( 엔지니어링 개선 계획)를 준비 중입니다. 설계, 매개변수 선택 및 잠재적 도입 경로에 대한 논의를 환영합니다.

전체 RFC는 검토 가능하며, 이더리움 개선 제안(EIP) 초안이 게시되면 링크(Chainlink) 를 제공할 예정입니다.

미해결 질문

다음 주제에 대한 토론을 환영합니다.

1. 매개변수 선택: 실제 고처리량 체인에 적합한 기본 e 값과 최대 증명 연령 은 무엇일까요? e=2가 올바른 기본값 일까요 , 아니면 더 큰 분기 계수가 일반적인 키 생성 연령 분포에 더 적합할까요?
2. 배제 증명 예외 사례: 터치 트랜잭션에서 존재하지 않는 키를 증명해야 하는 요구 사항은 의도적인 절충안입니다. 이것이 실제로 허용 가능한 것일까요, 아니면 다른 해결책이 필요할까요?
3. 아카이브 노드 인센티브: BUD는 증명 제공 기능을 전적으로 아카이브 노드에 위임합니다. 어떤 인센티브 구조가 아카이브 노드가 장기간에 걸쳐 가용성과 신뢰성을 유지하도록 보장할까요?
4. 도입 경로: 이미 글로벌 상태 트라이를 운영하고 있는 블록체인의 경우, BUD로의 전환에 있어 가장 혼란이 적은 경로는 무엇일까요?