월드 스테이트와 Merkle Patricia Trie: stateRoot가 모든 것을 약속하는 방식

이더리움 블록 헤더에는 32바이트짜리 필드 stateRoot가 있습니다. 이 필드는 어떤 계정 데이터도 담고 있지 않으면서도, 네트워크 전체 계정의 잔액과 nonce, 컨트랙트 코드와 컨트랙트 스토리지를 한꺼번에 고정할 수 있다고 주장합니다. 이 해시만 맞아떨어지면 그 상태가 어느 버전인지 알 수 있습니다. 이 필드는 Merkle Patricia Trie(MPT, 머클 패트리시아 트라이)의 루트 해시이며, 실행 계층이 월드 스테이트에 대해 내놓는 유일한 약속입니다.

이 약속이 얼마나 무거운지 이해하려면 세 가지를 뜯어봐야 합니다. 트리의 구조, 루트 해시가 왜 전체 상태를 묶어 둘 수 있는지, 그리고 이 트리를 유지하는 데 어떤 비용이 드는지입니다. 세 번째는 뒤에서 상태 샤딩과 상태 트리 세대 교체를 논의할 때 출발점이 됩니다.

블록 헤더 하나에 세 개의 트라이가 들어 있다

이더리움 블록 헤더에는 실행 결과를 설명하는 세 개의 트라이 루트, 즉 stateRoot(월드 스테이트 트라이), transactionsRoot(트랜잭션 트라이), receiptsRoot(영수증 트라이)가 있습니다. 옐로 페이퍼는 이들을 H_r, H_t, H_e로 적습니다. 상하이 업그레이드 이후에는 블록 헤더에 출금 목록을 설명하는 withdrawalsRoot(H_w)가 더해졌는데, 구조는 트랜잭션 트라이와 비슷하지만 출금 하나의 데이터 양이 적고 블록당 개수도 적습니다. 옐로 페이퍼는 "H_r이 블록 안의 모든 트랜잭션을 순서대로 실행하고 모든 출금까지 실행한 뒤 얻는 상태 루트와 같다"는 조건을 블록 헤더의 유효성 조건 가운데 하나로 듭니다. stateRoot가 설명하는 것은 누적된 상태이고, 나머지 루트들은 이 블록만 설명합니다.

트랜잭션 트라이와 영수증 트라이의 리프 수는 이 블록의 트랜잭션 수에 비례합니다. 따라서 어떤 트랜잭션이 블록에 담겼는지 검증하는 비용은 체인 길이와 무관하고 이 블록의 규모에만 달려 있습니다. 월드 스테이트 트라이는 전역에 하나뿐이고, 규모는 네트워크 전체의 계정 수와 스토리지 슬롯 수에 따라 커집니다. 블록 헤더의 logsBloom은 영수증에 담긴 로그 주소와 topic을 모아 만든 것으로, 조회에서 확률적 필터링에 쓰입니다. 이것은 인덱스 가속기이지 약속이 아닙니다.

주소는 해시를 거쳐야 트라이에 들어가고, 계정은 4-튜플이다

월드 스테이트 트라이의 키는 keccak256(계정 주소)이고, 값은 RLP 인코딩된 계정 4-튜플 [nonce, balance, storageRoot, codeHash]입니다. 주소 자체는 트라이에 들어가지 않고, 그 주소의 256비트 해시가 들어갑니다. 32바이트는 64개의 니블(nibble, 반바이트)에 해당하므로, 루트에서 리프까지 최대 64층입니다.

네 필드는 각각 분명한 의미를 지닙니다. nonce는 계정이 보낸 트랜잭션 수이고, 컨트랙트 계정이라면 여기에 그 계정이 생성한 컨트랙트 수까지 포함됩니다. balance는 wei로 표시한 잔액입니다. codeHash는 계정 코드의 keccak256이며, 코드 본문은 이 해시를 키로 상태 데이터베이스에 저장되므로 바이트코드가 같은 컨트랙트는 같은 데이터를 공유합니다. storageRoot는 또 다른 트라이의 루트이고, 그 트리는 이 계정에만 속합니다.

구조는 이렇게 트리 속의 트리로 나타납니다. 월드 스테이트 트라이의 리프 노드 안에는 어떤 계정의 storageRoot가 들어 있고, 이 루트가 그 계정 자신의 스토리지 트라이를 가리킵니다. 스토리지 트라이의 키는 keccak256(32바이트 슬롯 번호)이고, 값은 그 슬롯 내용(256비트)의 RLP 인코딩입니다. 슬롯 값이 0이라는 것은 명세에서 그 슬롯이 존재하지 않는 것과 같으며, 어떤 슬롯을 다시 0으로 쓰는 행위는 상태 계층에서 삭제와 같은 효과를 냅니다.

키를 먼저 해시하기 때문에 트리의 모양은 해시 분포가 결정하고, 공격자는 키를 골라 트리 모양을 만들 수 없습니다. 키로 주소나 슬롯 번호를 그대로 쓴다면, 공격자는 긴 접두사를 공유하는 키 묶음을 골라내어 특정 서브트리를 매우 깊은 사슬로 압축하고 접근과 증명 비용을 키울 수 있습니다. keccak256이 키를 고르게 흩뜨린 뒤에는 이런 구성이 더 이상 통하지 않습니다. EIP-8297 초안도 새 트리 구조를 논증하면서, 해시가 위치를 정해 균형이 유지된다는 점을 설계 근거로 듭니다. 대가는 슬롯 번호가 되돌릴 수 없다는 것입니다. 컨트랙트는 스토리지 트라이에서 자신이 어떤 슬롯에 썼는지 역으로 알아낼 수 없고, 외부에서도 알려진 슬롯 번호로 하나씩 조회할 수밖에 없습니다.

기억해 둘 만한 빈 값 상수가 두 개 있습니다. 뒤에서 증명과 검증에 모두 쓰입니다. 빈 트라이의 루트, 그리고 빈 계정 코드의 해시입니다.

# pip install eth-utils rlp
import rlp
from eth_utils import keccak

# 빈 트라이의 루트: RLP 인코딩한 빈 바이트 문자열에 keccak 적용
print(keccak(rlp.encode(b"")).hex())
# 56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421

# 빈 계정 코드의 해시
print(keccak(b"").hex())
# c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470

세 가지 노드와 2비트 플래그: 64층 경로가 짧아지는 방식

MPT는 이진 트리가 아니라 16진(hexary) 트리입니다. 옐로 페이퍼 부록 D는 세 종류의 노드와 빈 노드 하나를 정의합니다. branch 노드에는 항목이 17개 있고, 앞의 16개는 다음 니블의 16가지 값에 대응하며, 17번째 항목은 키가 여기서 끝나는 경우를 위해 남겨 둡니다. extension 노드는 [encodedPath, key] 두 항목이고, 최소 두 니블 이상의 공통 접두사를 건너뜁니다. leaf 노드는 [encodedPath, value] 두 항목이며, 키의 나머지 부분과 최종 값을 담습니다. 빈 노드는 빈 바이트 문자열로 나타냅니다. 명세에는 놓치기 쉬운 불변식이 하나 더 있습니다. 0이 아닌 항목을 하나만 가진 branch 노드는 존재할 수 없습니다. 그래서 같은 키-값 쌍 집합에는 인코딩 방식이 하나뿐이고, 루트 해시가 하나의 확정된 값을 가집니다.

경로는 바이트가 아니라 니블 단위로 구성되므로, 경로 길이의 홀짝과 노드 타입이라는 두 가지를 첫 니블에 밀어 넣는 컴팩트 인코딩이 필요합니다.

길이가 짝수일 때는 첫 니블 뒤에 0 니블을 하나 더 붙여, 전체 인코딩의 니블 수가 짝수가 되어 바이트 문자열로 떨어지게 합니다. ethereum.org가 제시한 참조 구현은 다음과 같습니다(반환값은 여기서 bytes로 정리했습니다).

def compact_encode(hexarray):
    # 리프 노드의 경로는 16으로 끝나므로, 감지하면 벗겨 내고 leaf 플래그를 세움
    term = 1 if hexarray[-1] == 16 else 0
    if term:
        hexarray = hexarray[:-1]
    oddlen = len(hexarray) % 2
    flags = 2 * term + oddlen                 # 첫 니블이 타입과 홀짝을 함께 인코딩
    if oddlen:
        hexarray = [flags] + hexarray
    else:
        hexarray = [flags] + [0] + hexarray   # 짝수 길이는 0 니블을 하나 채움
    return bytes(16 * hexarray[i] + hexarray[i + 1] for i in range(0, len(hexarray), 2))

경로 압축은 64 니블이라는 이론적 깊이가 실제 메인넷에서 왜 훨씬 덜 쓰이는지 설명해 줍니다. EIP-8297 초안은 동기 부분에서 계정 트라이의 현재 최대 깊이를 약 12층으로 추정합니다. 이는 초안의 자체 추정이며 메인넷 실측 데이터셋이 아닙니다. 층이 얕을수록 증명이 짧아집니다.

노드 사이의 참조 방식은 32바이트 규칙이 결정합니다. 자식 노드를 RLP 인코딩한 결과가 32바이트에 못 미치면 그 내용을 부모 노드에 그대로 인라인하고, 32바이트 이상이면 부모 노드는 keccak(RLP(자식 노드))만 참조로 적습니다. 이 규칙은 일회성으로 발생하는 작은 노드 읽기를 대량으로 줄여 주는 대신, 증명을 검증할 때 실제 인코딩 형태에 맞춰 노드를 재구성해야 하고 각 층이 독립적인 데이터베이스 조회라고 가정할 수 없게 만듭니다.

stateRoot는 전체 상태에 대한 하나의 약속이다

전체 구조를 하나의 해시로 접는 동작은 한 줄이면 됩니다. 루트 노드의 RLP 인코딩에 keccak256을 취하는 것입니다. 옐로 페이퍼가 월드 스테이트를 설명할 때 든 이유는 아주 직접적입니다. 루트 노드는 암호학적으로 내부의 모든 데이터에 의존하므로, 이 해시는 시스템 전체 상태의 안전한 식별자가 될 수 있습니다.

약속의 강도는 참조 방식에서 나옵니다. 부모 노드가 자식 노드를 참조할 때 쓰는 것이 자식 노드의 해시이므로, 어떤 리프의 비트 하나만 바뀌어도 그 리프가 속한 노드가 바뀌고, 이 변화가 층층이 루트까지 올라갑니다. keccak256의 충돌 저항성 위에서, 서로 다른 두 상태가 같은 루트를 내놓는다는 것은 해시 충돌을 찾는 것과 같습니다.

여기서 세 가지 성질이 따라옵니다. 루트 해시는 키-값 집합 하나를 유일하게 결정합니다. 노드가 내용으로 주소를 정하고 구조가 불변이므로 옛 상태를 루트로 되찾을 수 있습니다. 노드가 데이터베이스에 남아 있기만 하면 옛 루트를 아는 것만으로 그때의 상태를 복원할 수 있습니다. 검증자도 경로를 따라 약속을 재구성할 수 있습니다. 경로 위의 형제 해시만 있으면 어떤 리프에서 루트까지 다시 계산할 수 있으며, 옐로 페이퍼 부록 D는 증명의 공간 요구량을 O(log N)으로 적습니다.

블록 헤더의 정의는 시점도 한정합니다. stateRoot는 "블록 안의 모든 트랜잭션과 출금을 실행하고 최종 처리까지 모두 적용한 뒤"의 상태 루트입니다. 그것이 약속하는 것은 이 순간의 키-값 집합이며, 이 상태가 지금의 모습이 된 경로까지 약속하지는 않습니다. 서로 다른 역사가 같은 상태로 수렴할 수 있고, 같은 루트가 연속한 여러 블록에 반복해서 나타날 수도 있습니다. 상태의 가용성도 약속하지 않습니다. 루트 해시 자체에는 어떤 노드 데이터도 들어 있지 않으므로, 특정 계정을 검증하려면 경로 위의 노드를 따로 구해야 합니다.

루트에서 계정 하나까지: 머클 증명은 어떻게 쓰는가

계정 증명은 노드 목록이며, 루트 노드에서 시작해 keccak256(주소)의 니블을 따라 층층이 내려갑니다. 각 층에서는 branch의 해당 항목을 만나거나 extension 또는 leaf의 경로 접두사를 만납니다. 검증자의 동작은 아주 기계적입니다. 첫 노드에 대해 keccak(RLP(노드))를 다시 계산해 알려진 stateRoot와 같은지 확인하고, 디코딩한 뒤 니블에 따라 다음 참조를 찾아 리프에 이를 때까지 반복합니다. 리프 안의 값이 RLP 인코딩된 계정입니다. 존재하지 않는 계정을 증명하는 것도 가능합니다. 핵심은 경로 위에서 마지막으로 일치한 노드를 제시하는 것입니다. 그것이 branch라면 해당 분기가 비어 있고, leaf라면 목표 경로와 어떤 니블에서 갈라집니다. 스토리지 증명은 두 번째 패스로 진행하며, 시작점이 stateRoot에서 계정의 storageRoot로 바뀝니다.

EIP-1186은 이 과정을 eth_getProof로 표준화했습니다. 아래는 요청 예시입니다(주소와 슬롯 번호는 바꿔도 됩니다).

{
  "jsonrpc": "2.0",
  "id": 1,
  "method": "eth_getProof",
  "params": [
    "0x7f0d15c7faae65896648c8273b6d7e43f58fa842",
    ["0x0000000000000000000000000000000000000000000000000000000000000000"],
    "latest"
  ]
}

반환값에서 accountProof는 stateRoot에서 출발하는 노드 배열이고, storageProof의 각 레코드는 그 계정의 storageRoot에서 출발합니다. 둘 다 그저 데이터일 뿐이며, 신뢰할 수 있는지는 검증자가 스스로 다시 계산해 결정합니다.

Helios 같은 라이트 클라이언트가 바로 이 방식으로 동작합니다. 합의 계층 라이트 클라이언트가 먼저 비콘 체인에서 블록 헤더를 검증해 인증된 실행 계층 payload와 stateRoot를 얻고, 다음으로 신뢰하지 않는 아무 RPC에나 eth_getProof를 요청한 뒤, 마지막으로 로컬에서 MPT 검증을 끝냅니다. EIP-1186의 동기 섹션도 이런 증명 덕분에 IoT 기기와 모바일 앱이 신뢰할 수 있는 블록 해시 하나만으로 신뢰할 수 없는 출처의 계정과 스토리지 데이터를 검증할 수 있다고 언급합니다.

약속의 경계: 증명, 옛 루트와 라이트 클라이언트

증명의 능력에는 분명한 상한이 있습니다. 증명은 검증 대상인 그 경로만 덮으며, 상태의 나머지 부분을 끌어낼 수는 없습니다. 증명 크기는 경로 깊이와 분기 너비에 따라 커집니다. EIP-8297 초안은 예시 추정을 통해 이 규모를 설명합니다. 계정 트라이의 최대 깊이를 약 12층으로 계산하면 계정 분기 하나에 12층이 필요하고 층마다 형제 해시 15개가 필요하므로 합계는 15 × 32 × 12 = 5760바이트입니다. 60M Gas를 모두 서로 다른 컨트랙트 코드의 개별 바이트를 건드리는 데 쓰고 코드를 청크로 나누지 않는다면, 초안이 추정한 증명량은 약 1.8 GB입니다. 이는 모두 초안의 자체 추정이며 메인넷 실측으로 재검증되지 않았으므로, 방향성 결론은 받아들일 수 있지만 구체적인 수치를 기준으로 삼는 것은 적절하지 않습니다. 이것이 MPT가 유효성 증명에 불친절하다고 여겨지는 이유입니다. RLP 인코딩, Keccak 해시, 트리 속의 트리 구조, 그리고 코드를 구간별로 증명할 수 없다는 점입니다.

옛 루트에 대한 증명을 영구히 얻을 수 있는 것은 아닙니다. 약속은 블록 헤더에 남아 있지만, 그것을 이행할 수 있는지는 클라이언트가 상태를 어떻게 보관하느냐에 달려 있습니다. Geth는 v1.16부터 경로 기반 아카이브에서 평탄한 상태의 역사적 차분을 저장해 역사 상태를 읽을 수 있지만, v1.16.x에서는 옛 루트에 대한 머클 증명을 생성할 수 없고 v1.17부터 트라이 역사를 명시적으로 보존하는 방식으로 역사 증명을 지원할 수 있습니다. 전통적인 해시 기반 아카이브는 역사 트라이 노드를 보존하므로 임의의 옛 루트에 대해 증명을 내줄 수 있습니다. 디스크 비용은 다음 절에서 다룹니다. 약속의 의미는 합의에 속하고, 약속을 이행하는 방식은 구현 선택에 속합니다.

실행 계층 라이트 클라이언트도 한 차례 축소를 겪었습니다. 메인넷의 LES 프로토콜은 머지 이후 오랫동안 안정적으로 동작하지 못했고, Geth는 2023년 말에 관련 코드를 제거했습니다. 오늘날의 오프체인 검증은 "합의 계층이 루트를 인증하고 실행 계층이 증명을 제공하는" 조합으로 나타나는 경우가 더 많으며, 합의 계층 라이트 클라이언트가 검증하는 것은 비콘 체인 블록 헤더이고 그 자체로 트랜잭션을 다시 실행하지는 않습니다.

상태 팽창: 약속의 청구서는 디스크에 떨어진다

stateRoot의 표현력은 상태 규모와 무관하지만, 그것을 유지하는 비용은 상태 규모에 정비례합니다. 상태를 갱신할 때마다 리프에서 루트까지의 경로 전체를 다시 써야 하므로, 상태가 깊고 넓을수록 트랜잭션 하나에 필요한 읽기와 쓰기가 늘어납니다. 새 노드가 체인을 따라잡으려면 이 상태를 통째로 내려받아야 하는 것도 마찬가지입니다.

이더리움 연구 포럼의 2025년 11월 분석 한 편이 한 묶음의 규모를 제시했습니다. 그 글에 따르면 2025년 5월, 상태만 담당하는 Geth 노드의 비압축 데이터베이스는 약 340 GiB였고, Gas 상한이 30M에서 36M로 인상된 뒤 하루에 새로 추가되는 상태의 중앙값은 약 102 MiB에서 약 205 MiB로 두 배가 되었습니다. bloatnet 프로젝트 페이지는 650 GB를 임계 규모로 표시하며, 이 규모에 가까워지면 상태 접근 시간이 약 40% 늘고 메모리 사용량과 동기화 시간이 뚜렷하게 나빠진다고 말합니다. 이 페이지는 재현 가능한 기준 데이터를 제시하지 않았고, 여기서의 서술은 프로젝트 자체 설명을 옮긴 것이며, 이 페이지가 쓰는 단위는 GiB가 아니라 GB입니다. 그 포럼 분석은 이어서 보수·기준·공격적 세 가지 Gas 상한 경로로 외삽해(2027년 중반 각각 200M, 400M, 700M으로 상승), 2027년 중반의 총 상태 규모가 686 GiB에서 1.08 TiB 사이에 든다고 결론 내립니다. 이것은 시나리오 외삽이지 기정사실이 아닙니다. 값은 클라이언트 구현, 압축과 프루닝 전략, 그리고 Gas 상한의 실제 추이에 따라 달라집니다.

노드 운영으로 내려오면, ethereum.org가 정리한 Geth 풀 노드(snap 동기화)의 디스크 요구량은 500 GB 이상입니다. 아카이브 노드는 Geth 공식 기준으로 경로 기반이 약 2 TB, 역사 트라이 데이터를 보존하는 경우 약 6.5 TB, 해시 기반이 20 TB를 넘으며, ethereum.org가 정리한 클라이언트 간 아카이브 요구량은 3 TB에서 12 TB 이상입니다. 이 수치들은 클라이언트 구현, 압축 방식, 프루닝 전략과 Gas 상한에 의존하므로 구현 간 직접 비교는 의미가 없습니다. 상태 크기가 온체인 역사 크기와 같은 것도 아닙니다. 역사 트랜잭션과 영수증은 별도의 회계입니다.

이더리움 메인넷의 상태는 늘기만 하고 줄지 않습니다. 계정과 스토리지 슬롯은 한 번 기록되면 영구히 공간을 차지하며, 상태 만료나 상태 임대료 같은 메커니즘이 없어 압력이 한 방향으로만 쌓입니다. 완화 방향은 크게 두 갈래입니다. 트리 구조를 바꾸는 것, 예를 들어 오래 논의되어 온 Verkle 트리와 아직 초안 단계인 분할 이진 트리(Partitioned Binary Tree, EIP-8297 초안)입니다. 또는 상태를 쪼개서 개별 노드가 그중 일부만 유지하게 하는 것입니다. 후자는 뒤에 나오는 글의 주제이고, 여기서는 압력의 출처만 짚습니다. 슬롯이 컨트랙트 계층에서 어떻게 배치되는지는 0.19 "Storage Layout"을 참고하십시오.

출처

• Ethereum Yellow Paper(2절의 상태 전이 함수, 4장의 블록 헤더 필드와 전체 유효성(stateRoot의 정의와 검증 조건), 부록 D의 MPT 노드 정의, hex-prefix 인코딩, 32바이트 인라인 규칙, D.1의 O(log N) 증명 공간)
• ethereum.org: Merkle Patricia Trie(노드 타입, 컴팩트 인코딩 참조 구현, 세 트라이의 키-값 정의, 트랜잭션과 영수증의 값 인코딩)
• ethereum.org: Ethereum accounts(storageRoot와 codeHash의 공식 표현)
• EIP-1186: RPC-Method to get Merkle Proofs(eth_getProof의 필드, 존재하지 않는 계정을 증명하는 방식과 사용 사례, 공식 예시의 빈 storageHash(0x56e81f…)와 빈 codeHash(0xc5d246…)도 본문 코드 블록의 두 빈 값 상수를 대조하는 데 사용)
• EIP-8297: Partitioned Binary Tree(Draft, 2026-06-11 생성, 해시 함수 미확정, 계정 트라이 최대 깊이 약 12층, 분기 증명 5760바이트, 최악의 경우 약 1.8 GB의 증명량, MPT가 유효성 증명에 불친절한 이유, 본문에서 이 항목들은 모두 초안의 자체 추정이라고 표시)
• Ethereum Research: State growth scenarios and the impact of repricings(2025-11-19, 340 GiB 상태 규모, 102 MiB에서 205 MiB로의 일일 증가, 세 가지 Gas 상한 경로에 따른 2027년 시나리오 외삽, 이 글은 시나리오 분석이며 기정사실이 아님)
• Bloatnet Initiative(650 GB 임계 규모와 상태 접근 시간 약 40% 증가라는 프로젝트 자체 설명, 페이지에 재현 가능한 기준 데이터 없음)
• go-ethereum: Archive mode(경로 기반 아카이브의 2 TB와 6.5 TB 기준, 해시 기반 아카이브는 20 TB 초과 가능, v1.16.x와 v1.17의 역사 증명 지원 차이)
• ethereum.org: Ethereum archive node와 Spin up your own Ethereum node(클라이언트 간 아카이브 및 풀 노드 디스크 요구 범위, 아카이브 3 TB에서 12 TB 이상, Geth snap 동기화 500 GB 이상)
• go-ethereum PR #28586(LES 및 관련 라이트 클라이언트 코드 제거)
• a16z crypto: Building Helios(합의 계층이 stateRoot를 인증하고 실행 계층이 eth_getProof로 로컬 검증을 하는 라이트 클라이언트 경로)

더 읽기