2018-06-15

Skewed Merkle Tree

지난번 글에서 설명했듯이 이더리움Modified Merkle Patricia Trie를 4가지 용도로 사용한다. 이 중 State Trie와 Storage Trie는 변경되는 데이터를 효율적으로 저장하고 검증하기 위해서 사용된다. 하지만 Transaction Trie와 Receipts Trie는 변경되는 데이터가 대상이 아니다. 이 두 trie는 하나의 블록에서 사용된 트랜잭션과 그에 의해 생성된 receipt의 검증을 위해서만 사용되는 휘발성 데이터다.

이더리움이 두 가지 목적을 위해 같은 데이터 구조를 사용하는 이유는 같은 구현을 공유하기 위해서였다. 하지만 목적이 다르기 때문에 Transaction Trie나 Receipts Trie를 생성하는데 최적화된 코드는 State Trie나 Storage Trie를 생성하는데 필요한 코드와 다르다. 실제로 Parity는 각각의 용도로 다른 코드를 사용한다. 그렇다면 Transaction Trie나 Receipts Trie를 위해 애초에 같은 Trie를 사용할 이유가 없지 않았을까?

현재 코드박스에서 개발하고 있는 코드체인의 transactions_root와 invoices_root는 이런 고민이 반영됐다. 그래서 UTXO를 저장하는 Merkle Patricia Trie와는 다른 구현을 사용하기로 결정했다. 그렇다면 transactions_root와 invoices_root에 필요한 특성은 무엇이 있을까?

최소한의 필요조건은 데이터를 검증할 수 있어야 한다는 것이다. 이 검증은 단순히 데이터셋을 검증할 뿐 아니라 데이터의 순서도 일치하는지 확인해야 한다. 여기까지가 이더리움을 비롯한 일반적인 블록체인에서 필요한 특성이다. 코드체인에서는 여기에 몇 가지 요구사항이 더 들어갔다.

우선 구현이 간단해야 한다. 간단해야 한다는 것은 코드가 단순하다는 것뿐 아니라 메모리 사용량이 적고, 실행하는데 시간이 적게 걸려야 한다는 것을 의미한다. 이는 코드체인이 라이트 클라이언트를 고려하고 있기 때문이다.

다음으로 전체 트랜잭션을 검증할 수 있어야 한다는 것이다. 이는 다른 블록체인에 없는 코드체인에만 존재하는 특성이다. 코드체인이 동기화를 맞추는 방법에는 Snapshot Sync가 있다. Snapshot Sync는 이력을 다 받을 필요 없이 신뢰할 수 있는 헤더 하나만 있으면 해당 블록을 받은 것과 같은 상태로 동기화되도록 하는 방법이다. 이를 위해서 하나의 헤더만으로 전체 트랜잭션을 검증할 수 있어야 한다.

마지막으로 incremental 하게 만들 수 있어야 한다. 코드체인의 transactions_root는 전체 트랜잭션 목록을 검증할 수 있어야 하기 때문에 incremental 하게 만들 수 없다면 블록이 쌓여갈수록 검증에 필요한 시간이 길어지게 된다. 이를 방지하기 위해 incremental 하게 만들 수 있어야 한다는 것이 필수적이다.

이런 조건들을 만족시키기 위해서 이더리움이 사용하는 Merkle Patricia Trie는 가장 먼저 배제됐다. 이는 전체 데이터에 대해서 incremental하게 만들 수 있지만 Trie를 구성하는데 드는 오버헤드가 컸다.

그다음으로는 전통적인 Merkle Tree를 고려했다. 하지만 이는 위의 특성 중 오버헤드가 적어야 한다는 것과 incremental 하게 만들 수 있어야 한다는 것을 만족시키지 못했다.

그래서 우리는 왼쪽으로 치우친 Skewed Merkle Tree를 사용하기로 결정했다. Skewed Merkle Tree에서는 전 블록의 root위에 현재 블록의 트랜잭션들을 이용해 새 tree를 만들어 지금까지 실행된 전체 트랜잭션 목록을 담는 해시를 빠르고 가볍게 생성할 수 있다. 즉, 전체 트랜잭션 목록을 incremental 하게 만들 수 있고, 만드는데 드는 시간과 메모리는 트랜잭션 수에 선형적으로만 비례한다. 게다가 우리가 관심있는 것은 검증을 위한 root값 뿐이기 때문에 사용하는 메모리는 트랜잭션 개수와 상관없이 상수배만큼 사용하도록 최적화할 수 있다. 실제로 코드체인에서 사용한 코드는 다음과 같이 간단하다.

물론 Skewed Merkle Tree도 만능은 아니다. Skewed Merkle Tree는 Merkle Tree의 기본적인 기능인 Merkle path를 만드는 데 비효율적이다. 따라서 Merkle path를 만들어야 하는 경우 Skewed Merkle Tree보다 고전적인 balanced Merkle Tree가 더 적절하다. 하지만 코드체인이 transactions_root와 invoices_root를 사용하는 용도를 고려해봤을 때, Merkle-proof path를 사용하지 않는다. 오로지 데이터의 검증을 위해서만 사용하기 때문에 Skewed Merkle Tree가 더 적절하다고 판단했다.

2018-06-03

2018년 22번재 주 - P2P Network

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다.
보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다.

지난주에 이어 이번 주는 P2P를 주제로 발표했다. 이번에도 발표자료를 만들면서 참고한 자료를 공유하도록 하겠다.


Chord: a scalable peer-to-peer lookup protocol for internet applications

Tapestry: A Resilient Global-scale Overlay for Service Deployment

Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems

A Scalable Content-Addressable Network

P2P 네트워크 중에서도 네트워크 토폴로지가 특정한 규칙에 의해서 구성되는 네트워크를 structured 네트워크라고 말한다. Structured network는 unstructured network에 비해 특정 노드에 부하가 걸리거나 의존하는 것을 방지하면서 잘 분산된 네트워크를 구성할 수 있다. 위의 4 논문은 각기 Chord, Tapestry, Pastry, Content Addressable Network(a.k.a. CAN)라는 대표적인 structured 네트워크 오버레이를 제시하는 논문이다.

Kademlia: A Peer-to-Peer Information System Based on the XOR Metric

Kademlia는 위의 네 논문을 개선하는 네트워크 오버레이를 제시한다. BitTorrent, eDonkey, 이더리움 등 많은 P2P 시스템이 kademlia 방식을 이용한다. 실질적으로 P2P 네트워크에서 가장 많이 사용되는 방식이다.
Kademlia의 가장 큰 특징은 xor distance를 사용하는 것이다. Xor distance는 노드 아이디의 공통된 prefix가 길수록 가까운 노드로 판단하는 방식이다. 이 방식은 triangle inequality를 만족하며, 각 노드가 작은 라우팅 테이블만으로 전체 네트워크를 효율적으로 연결할 수 있다.
게다가 거리가 대칭적이기 때문에 TCP로 연결해야 하는 시스템에서도 사용하기 좋다.

Understanding churn in peer-to-peer networks

Churn이라는 것은 새 노드가 네트워크에 참여하거나 네트워크에서 노드가 빠져나가는 변동성을 말한다. 위 논문은 다양한 p2p 네트워크에서 네트워크 상태를 조사해서 각 네트워크가 어떤 churn을 가지는지 분석했다.
사실 churn 자체는 서비스의 종류마다 다 다를 것이다. 이 논문에서 주목할 점은 그 churn을 어떻게 분석했는지 그 방법론에 대한 것이라고 생각한다.

Low-Resource Eclipse Attacks on Ethereum’s Peer-to-Peer Network

이더리움에 가할 수 있는 eclipse attack에 관해 정리한 논문이다. 자세한 내용은 전에 쓴 적이 있으니 참고 바란다.

Eclipse Attacks on Bitcoin’s Peer-to-Peer Network

이 논문은 비트코인에서 할 수 있는 eclipse attack에 관해 정리한 논문이다. 이더리움은 2대의 머신으로 공격할 수 있었던 반면 비트코인에서는 약 400개의 머신이 필요하다. 아직 비트코인에서 이보다 적은 수로 공격할 수 있는 방법은 나오지 않았다.

BLAKE2: simpler, smaller, fast as MD5

Cryptographic hash function 중 하나인 BLAKE2를 소개하는 논문이다. SHA-3 finalist였던 blake의 개선판으로 blake보다 더 적은 메모리로 빠르게 돌아간다.

The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC)

Codechain에서는 MD5SHA-1을 이용하는 일반적인 HMAC 대신에 BLAKE2를 HMAC으로 사용한다. 이와 관련하여 이론적 분석이 있을 것이라고 생각하고 보기 시작했는데, HMAC에 관한 내용은 별로 없고, BLAKE2의 알고리즘과 구현에 관한 내용이 대부분이었다.

O(1) Block Propagation

이건 내가 발표한 내용이 아니라 양준모 님의 발표에 있던 비트코인의 Graphene의 아이디어를 줬던 제안이다. 트랜잭션은 언제나 전파하는 비트코인의 특성상 대부분 트랜잭션이 이미 전파돼있을 거라고 가정하고, IBLT라는 자료구조를 이용해서 없는 트랜잭션을 빠르게 확인할 수 있다는 것이 메인 아이디어다.

Invertible Bloom Lookup Tables

이 논문이 위에서 말한 IBLT를 제시하는 논문이다.