EIP-7916 SSZ 프로그레시브 리스트 (SSZ ProgressiveList)

콜 결정 없음 · 확장성·데이터 · 원문 상태 Review · 2025-03-24 작성

용량 상한 없이 실제 원소 수만큼 자라는 새 SSZ 타입 ProgressiveList[type]와 ProgressiveBitlist를 추가합니다. 짧은 리스트의 해시 계산을 줄이고 리스트가 길어져도 각 원소의 증명 위치가 변하지 않게 합니다.

왜 필요한가

지금 SSZ의 리스트 타입 List[type, N]은 최대 용량 N을 미리 정해야 합니다. 그런데 실제 데이터는 대개 상한보다 훨씬 짧아서 비어 있는 자리를 0으로 채운 뒤 그 부분까지 해시를 계산하는 낭비가 생깁니다. 트랜잭션 목록처럼 리스트 안에 리스트가 겹겹이 들어가면 낭비는 더 커집니다. 또 MAX_BYTES_PER_TRANSACTION 같은 N 값은 미래 설계 여지를 내다보고 임의로 크게 잡은 숫자라 근거가 약합니다. 포크에서 N을 바꾸면 트리 안에서 각 원소가 차지하는 위치(gindex, 제너럴라이즈드 인덱스)가 달라져 그 위치로 증명을 검증하던 외부 검증 코드가 깨집니다. 이 EIP는 용량 상한 개념을 버리고 실제 원소 수에 맞춰 점진적으로 자라는 머클 트리 모양을 도입해 이 세 가지 문제를 함께 해결하려 합니다.

무엇이 바뀌나

지금

EIP-7916 이후

누구에게 영향이 있나

심층 설명

merkleize_progressive 헬퍼 함수

SSZ 머클화 명세에 merkleize_progressive(chunks, num_leaves=1)를 추가합니다. 정의는 재귀적입니다. len(chunks) == 0이면 루트는 영값 Bytes32()입니다. 그렇지 않으면 루트를 hash(a, b)로 계산하는데, a는 앞쪽 최대 num_leaves개 청크를 merkleize(chunks[:num_leaves], num_leaves)로 이진 트리 머클화한 값이고 b는 그 뒤 청크들을 merkleize_progressive(chunks[num_leaves:], num_leaves * 4)로 재귀 머클화한 값입니다. 결과는 잎 수가 1, 4, 16, 64개로 4배씩 커지는 이진 서브트리들이 0으로 끝나는 사슬을 이루는 모양입니다. 가장 깊은 서브트리만 0 청크로 패딩하며 이 패딩은 메모리 효율을 위해 가상으로 처리합니다.

깊이별 용량

깊이 1에서 청크 1개(32바이트), 깊이 2에서 누적 5개(160바이트), 깊이 3에서 21개(672바이트)로 늘어나고 깊이 15에서는 누적 357'913'941개 청크, 11'453'246'112바이트에 이릅니다. 각 단계에서 추가되는 서브트리 잎 수가 4배씩 커지므로 깊이는 리스트 크기에 대해 로그 수준으로만 늘어납니다. 트리 모양이 길이와 무관하게 고정되어 있어 특정 청크 인덱스는 리스트가 자라도 항상 같은 gindex에 머뭅니다.

새 타입 정의와 직렬화

두 복합 타입을 새로 정의합니다. ProgressiveList[type]은 상한 없는 가변 길이 동종 컬렉션이고(예: ProgressiveList[uint64]), ProgressiveBitlist는 상한 없는 boolean 컬렉션입니다. 둘 다 variable-size로 분류되고 기본값은 빈 리스트 []입니다. 편의를 위해 ProgressiveByteList를 ProgressiveList[byte]의 별칭으로 둡니다. 직렬화, 역직렬화, JSON 매핑은 각각 기존 List[type, N], Bitlist[N]과 동일해서 구현을 그대로 재사용할 수 있습니다. 기존 타입과 충돌 없이 공존합니다.

머클화 규칙

머클화 정의를 세 경우로 확장합니다. 기본 객체의 프로그레시브 리스트는 mix_in_length(merkleize_progressive(pack(value)), len(value)), 프로그레시브 비트리스트는 mix_in_length(merkleize_progressive(pack_bits(value)), len(value)), 복합 객체의 프로그레시브 리스트는 각 원소의 hash_tree_root를 모아 mix_in_length(merkleize_progressive([hash_tree_root(element) for element in value]), len(value))로 계산합니다. 기존 List와 마찬가지로 길이를 루트에 섞는 구조는 유지하고 안쪽 머클화 함수만 progressive 방식으로 바뀝니다.

왜 이 설계인가

재귀 구조는 작은 리스트가 더 적은 해시를 쓰게 하고(3개짜리 리스트는 1024개 용량의 List보다 낭비가 적습니다), 서브트리 크기가 고정이라 gindex가 안정적이며 상한 없이 커질 수 있습니다. 대안인 동적 깊이 머클화는 길이를 먼저 조회한 뒤 gindex를 다시 조회하는 2단계 질의가 필요해 지연과 리오그 위험을 키우고 증명을 복잡하게 만들어 배제했습니다. 초기 잎 수 1과 배율 4는 매개변수로 노출하지 않고 고정했는데, 단순함을 지키고 도입 장벽을 낮추기 위한 선택이며 필요하면 이후 EIP에서 매개변수화할 수 있다고 밝힙니다.

보안 고려 사항

타입 자체에 상한이 없어도 무한히 커질 수 있는 것은 아닙니다. 다른 복합 타입 안에 들어가면 가변 길이 오프셋의 uint32 한계로 사실상 약 4GB 상한이 생기고 실제로는 10MB libp2p 메시지 같은 현실적 한도가 먼저 적용됩니다. 구현은 맥락에 맞는 크기 제한을 강제해야 합니다(SHOULD). 또 큰 인덱스의 원소일수록 재귀를 따라 내려가야 해서 증명 크기가 커질 수 있지만 배율 4 덕분에 리스트 크기에 대해 로그 수준에 그칩니다.

현재 상태

이 EIP는 Review 상태입니다. 명세가 아직 확정되지 않아 세부 내용이 바뀔 수 있습니다. 테스트는 ethereum/remerkleable의 test_impl.py, test_typing.py에 정적 테스트가 있고 ethereum/consensus-specs 릴리스의 tests/general/phase0/ssz_generic에 랜덤 테스트가 있습니다. 참조 구현도 ethereum/remerkleable에 있습니다. 특정 포크에 포함하기로 한 콜 결정은 제공된 기록에 없습니다.

EIP 원문 · ← EIPs