레이블이 merkle patricia trie인 게시물을 표시합니다. 모든 게시물 표시
레이블이 merkle patricia trie인 게시물을 표시합니다. 모든 게시물 표시

2018-05-12

Secure Tree - state trie의 키가 256 bit인 이유

지난번 글에서 설명했듯이 ethereum의 상태는 modified Merkle Patricia Trie(a.k.a. MPT)에 저장된다. Ethererum에서 값은 nonce, balance 등 account의 상태고, 그 키는 account의 주소다. 이 Account의 주소는 160bit이기 때문에, MPT의 root에서부터 40 nibble의 경로를 타고 가면 account의 상태가 나와야 한다. 하지만 실제로 ethereum의 상태가 저장된 MPT에서 account의 주소를 키로 가지는 노드를 찾으면, leaf node가 아닌 branch nodeextension ndoe가 나온다.

이는 ethereum이 account를 MPT에 집어넣을 때, account의 주소를 바로 키로 사용하는 것이 아니라, 주소의 keccak-256 hash를 키로 사용하기 때문이다. 즉, 40 nibble의 account 주소를 따라가는 것이 아니라, 64 nibble의 hash를 따라가야 원하는 account를 찾을 수 있다. 이렇게 account의 주소를 바로 경로로 사용하는 것이 아니라, 주소의 hash를 경로로 사용하는 것을 ethereum은 secure tree라고 부른다.

Secure tree에 대해 자세히 설명하기 전에 ethereum이 사용하는 MPT에 대해서 더 알아야할 것이 있다. Ethereum에 있는 MPT는 state trie만이 아니다. Ethereum은 총 네 종류의 MPT가 있다.

첫 번째는 state trie다. 여기에는 ethereum의 account 정보가 저장된다. 여기서 account 정보는 account의 nonce, balance, storage root의 hash, code의 hash다. 만약 계정이 smart contract라면 storage root에는 smart contract의 state를 가지는 MPT의 root가 저장되고, code에는 evm bytecode의 hash 값이 저장된다.

두 번째는 storage trie다. etheruem의 smart contract는 내부 상태를 가진다. 따라서 smart contract인 account는 자신의 상태를 간직하는 storage trie를 하나씩 만들어서 가지고 있다.

나머지 두 개는 transactions trie와 receipts trie다. 이들은 각각 블록이 가지고 있는 트랜잭션들과 각 트랜잭션을 실행한 실행 결과를 배열로 했을 때, 배열의 인덱스를 키로 하는 MPT다. Transactions trie와 receipts trie는 merkle proof를 위해 사용된다.

이 네 개의 MPT 중에서 state trie와 storage trie만 secure tree를 사용하고, transactions trie와 receipts trie에는 secure tree를 사용하지 않는다. 즉, state trie와 storage trie는 keccak-256 hash 값인 256 bit 값을 키로 사용하고, transactions trie와 receipts trie의 키는 임의의 길이의 값이다.

Ethereum이 secure tree를 사용하는 이유는 DoS 공격을 막기 위해서다. State trie와 storage trie는 파일에 저장된다. 즉, 이 두 trie에 새 노드가 추가되거나, 수정하거나, 노드를 읽는 것은 disk IO가 있어야 하고, 가능하면 leaf node에 도착할 때까지 최대한 적은 노드를 지나서 가는 것이 좋다. MPT는 이를 위해서 중복되는 1-child branch nodeextension node로 압축할 수 있도록 했다.

하지만 자식이 하나인 branch nodeextension node로 압축된다. 따라서 공격자가 악의적으로 2개의 자식이 생기는 branch node를 만들 수 있다면, 적은 비용으로 공격할 수 있다. 그래서 secure tree는 keccak-256 hash 값을 키로 사용하여 공격자가 자신이 원하는 위치에 노드를 생성할 수 없도록 하였다.

Transactions trie와 receipts trie는 secure tree를 사용하지 않는 이유는 키를 hash 하는 것으로 보호할 수 있는 것이 없다. Transactions trie와 receipts trie에서 키는 트랜잭션과 receipt의 index기 때문에 공격자가 원하는 키를 삽입하는 것이 불가능하기 때문이다.

또한, Secure tree는 키가 256 bit로 고정된다는 장점도 있다. 덕분에 트리의 깊이가 64 이하라는 것이 보장되기 때문에 state trie나 storage trie의 임의의 값을 변경하는데 드는 최대 비용을 계산할 수 있다. 특히 state trie나 storage trie는 트랜잭션에 의해서 읽히거나 수정되는데, 이때 읽히거나 수정되는 값이 어떤 노드에 있는지 상관없이 같은 일을 하는 트랜잭션은 같은 비용을 낸다. 그렇기 때문에 최대 비용이 보장되는 것은 secure tree의 큰 장점이다.

2018-05-06

Modified Merkle Patricia Trie - ethereum이 상태를 저장하는 방법

Ethereum에서 네트워크 부분을 빼고 보면, Ethereum은 하나의 state machine이고, transaction은 ethereum의 state를 변경시키는 것이다. 이 state는 key-value pair로 표현된다. Key-value pair를 저장하는 방법은 여러 가지 있지만, ethereum에서는 state를 저장하기 위해 Modified Merkle Patricia Trie(a.k.a. MPT)라는 특수화된 방법을 사용하도록 스펙에서 정의하고 있다.

MPT는 기본적으로 Patricia trie와 Merkle tree를 합친 것이다. 여기에 추가로 ethereum의 특성에 맞게 몇 가지 최적화를 했다. 따라서 MPT를 쉽게 이해하기 위해서는 Patricia trie와 Merkle tree를 아는 것이 좋다.

Patricia Trie

Patricia trie는 Prefix tree, radix tree, trie 등 다양한 이름으로 불리는 자료구조다. Trie는 path에 key를 집어넣어 공통된 prefix를 가지는 노드들은 같은 path를 가진다. 공통된 prefix를 찾는데 가장 빠르고, 적은 메모리로 구현할 수 있으며, 구현도 간단하다. 그래서 router 등 낮은 사양의 기계에 들어가는 routing table의 구현체로 많이 사용된다.

https://commons.wikimedia.org/wiki/File:Trie_example.svg

Merkle Tree

Merkle tree는 hash들의 tree다. Leaf 노드에는 데이터를 보관한다. Leaf의 부모는 leaf의 hash를 가지고, 그 부모는 자식들의 hash의 합을 다시 hash 한 값을 가진다. Merkle tree는 leaf 노드를 제외한 노드들은 전부 hash를 가지고 있기 때문에 hash tree라고도 불린다.

https://commons.wikimedia.org/wiki/File:Hash_Tree.svg

Merkle tree를 사용하면 서로 다른 두 노드가 같은 데이터를 가졌는지 효율적으로 비교할 수 있다. 예를 들어 위와 같은 L1, L2, L3, L4가 있을 때, 같은 Top Hash를 가졌는지만 비교하면 된다. 만약 Top Hash가 다르고, 어떤 데이터가 다른지 알고 싶으면 Hash0Hash1을 비교하고, 둘 중 다른 브랜치의 hash를 비교해나가면 어떤 데이터가 다른지 알 수 있다.

Merkle Patricia Trie

MPT는 Merkle tree처럼 각 노드가 hash를 가진다. 노드의 hash는 노드 내용의 sha3 hash로 결정된다. 이 hash는 노드를 지칭하는 key로도 사용된다. go-ethereumleveldb를, parityrocksdb라는 key-value storage에 state를 저장한다. 이때 스토리지에 저장되는 key와 value는 ethereum state의 key-value가 아니다. 스토리지에 저장되는 value는 MPT 노드의 내용이고, key는 이 노드의 hash다.

대신 ethereum state의 key는 MPT에서 path로 사용된다. MPT에서 key가 같은지 비교하는 단위는 nibble이기 때문에 하나의 노드에서 최대 16개의 branch를 가질 수 있다. 거기에 노드도 값을 가지기 때문에, 16개의 브랜치와 값을 합쳐 17개의 아이템을 가진 배열이 branch node가 된다.

아래로 자식이 없는 노드는 leaf node라고 불린다. Leaf node는 자신의 path와 value 두 개의 아이템으로 이루어진 배열이다. 예를 들어 "0xBEA"라는 키에 1000이 들어있고, "0xBEE"라는 키에 2000이 들어있는 경우를 생각해보자. 그렇다면 "0xBE"를 path로 가지는 branch node가 있고, 그 아래 "0xA"와 "0xE"를 path로 가지는 두 leaf node가 붙는다.

MPT에는 앞서 설명한 branch nodeleaf node 외에 extension node가 있다. Extension nodebranch node의 최적화다. Ethereum의 state에서는 하나의 branch node가 하나의 자식만 가지는 경우가 많다. 그래서 MPT는 하나의 자식만 가지는 branch node를 경로와 자식의 hash를 가지는 extension node로 압축한다.

여기서 문제가 하나 생긴다. Leaf nodeextension node는 둘 다 2개의 아이템을 가진 배열이다. 따라서 이 두 개의 node를 구분할 방법이 필요하다. MPT는 이를 위해서 경로에 prefix를 붙인다. 만약 노드가 leaf node고 경로가 짝수개의 nibble로 구성돼 있으면 0x20을 붙이고, 홀수개의 nibble로 구성돼 있으면 0x3을 붙인다. 반대로 extension node의 경우 짝수개의 nibble로 구성돼 있으면 0x00을, 홀수개의 nibble로 구성돼 있으면 0x1을 prefix로 붙인다. 홀수개의 nibble로 구성된 경로에는 한 개의 nibble을 prefix로 붙이고, 짝수개의 nibble로 구성된 경로에는 두 개의 nibble을 prefix로 붙이기 때문에 경로는 항상 byte로 표현 된다.