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의 큰 장점이다.

댓글 없음:

댓글 쓰기