비트코인에서 UTXO set을 초기 동기화하기 위한 정렬된 머클트리(sorted merkle tree)
/* 이 글은 제가 2017년 7월 경에 작성했던 것이라서, 일부 내용은 이 날짜를 기준으로 작성되었다 */
Abstract. 비트코인은 다른 노드들을 믿지 못하는 비신뢰 특성 때문에, 새로 블록생성에 참여하는 새 노드는 초기 블록체인 동기화(Initial Blockchain Download, IBD)를 통해 전체 블록체인을 전송받고 이를 검증해야 한다. 하지만, 이 방법은 전체 블록체인 데이터를 다운받아야 하기 때문에 여러 가지 문제를 발생시킨다. 이 논문은 이를 해결하기 위한 방법 중에 새 노드가 전체 블록체인 대신에, 거래의 전체 상태인 UTXO set를 다운로드받는 UTXO 확정(UTXO commitments) 방법을 살펴본다. 하지만 이 방법은 현재 여러 문제로 적용되지 못하고 있다. 이를 해결하기 위해, 우리는 기존 트리를 이용하는 새로운 정렬된 머클트리(sorted merkle tree)를 제안한다. 이것은 UTXO set을 머클트리로 만들 때 기존의 머클트리에 비해 노드의 개수를 약 1/2로 줄일 수 있다.
1. 서론
비트코인(Bitcoin)과 같은 블록체인 기술은 신뢰하는 중앙기관이 없이 분산된 다수의 노드들이 피어-투-피어(peer-to-peer, p2p) 네트워크를 구성하여 데이터베이스(DB)인 블록체인을 관리하는 DB 기술이다.[1] 또한 이것은 각 노드들이 동일한 블록체인을 보관하도록 복제하는 복제 시스템(replication system)이다. P2P 네트워크를 구성하는 노드들은 작업증명(proof-of-work, PoW) 또는 지분증명(proof-of-stake, PoS) 합의 알고리즘을 통해서 어느 노드가 새로운 블록을 생성할지를 결정한다. 즉, 비트코인 네트워크에는 합의 알고리즘을 통해 노드들이 하나의 주체인(main chain)을 유지하여 이중지출 방지한다. 따라서 합의 알고리즘이 이중지출(doubling spending)을 막는 핵심적인 역할을 하고, 블록체인 자체는 추가 전용 데이터베이스(append-only database)에 불과하다.
블록체인은 추가 전용 DB이기 때문에, 그 크기가 선형적으로 계속 늘어날 수밖에 없다. 예로, 2017년 5월 20일(이하, ‘현재’라고 칭함)에 비트코인의 블록체인 사이즈는 116 GiB이었고, 최근 1년 동안 블록체인 사이즈는 47 GiB가 증가했다. 현재 비트코인 코어(bitcoin core)에서 블록 사이즈는 1 MiB로 고정되어 있고,[2] 평균적으로 10분에 한 번씩 블록을 생성하므로 1년 동안 추가될 수 있는 블록 사이즈는 1 MiB * 6 * 24 * 365 , 즉52.56 GiB이다. 현재 비트코인 네트워크의 예상 최대 거래 처리량은 초당 7거래로 알려져 있지만[3], 현재 평균적으로 약 3~4 거래를 처리하고 있다. 이에 반해서 비자카드에서 거래의 평균 초당 처리량은 약 2,000 거래이며, 최대(peak) 처리량은 초당 약 56,000 거래로 알려졌다.[3] 따라서 비트코인의 현재 거래 처리량은 매우 작다. 이 때문에, 만일 비트코인의 초당 거래 처리량이 크게 증가한다면, 블록체인의 사이즈 문제는 더욱 심각해질 것이다. 또한 블록체인은 추가 전용 DB이기 때문에 그 크기가 너무 빠르게 증가하는 피할 수 없는 문제를 가진다.
2. 비트코인에서 거래 및 거래의 전체 상태
비트코인에서 거래(transaction)는 하나 이상의 입력과 출력(one or more of inputs and outputs)으로 구성된다. 비트코인에서 거래의 출력(outputs)은 단 한 번만 입력(input)에서 소비될 수 있기 때문에, 소비되지 않은 거래 출력(unspent transaction outputs, UTXOs)과 이미 소비된 거래 출력(spent transaction outputs, STXOs)으로 구분된다. 구체적으로, 입력은 소유자가 소비할 수 있는 UTXO와 디지털 서명과 공개키로 구성되고, 출력은 새로운 UTXO를 생성하기 위한 지갑주소와 이체할 코인 개수로 이루어진다. 따라서 거래가 유효하려면, 입력에 STXO가 아닌 UTXO만 사용하여 소비해야 한다.[4] 결국 비트코인에서 거래는 UTXO를 소비하여 STXO로 만들고 새로운 UTXO를 생성하는 과정이다.[4] 비트코인 지갑은 일반적으로 거래의 입력과 출력을 디지털 서명하여 네트워크에 전파한다. 즉 비트코인은 소유권의 증거로 디지털 서명을 제공하는 서명 기반의 소유권 이전 시스템이다.
그림 1은 비트코인의 주요 DB인 맴풀(mempool), 블록체인 그리고 UTXO set을 보여준다. 여기서, 맴풀은 블록에 기록되기를 기다리는 미승인 거래(unconfirmed Tx)를 저장하는 DB이고, 이 때문에 특정 거래가 블록에 기록이 되면 이 거래는 맴풀에서 삭제된다. UTXO set는 미래에 사용할 수 있는 출력인 모든 UTXO를 모아놓은 DB이고, 이 때문에 새 블록이 전파될 때마다 이것의 내용이 바뀐다. 구체적으로, 새 블록이 전파될 때마다 이 블록에 포함된 거래에 의해서 STXO, 즉 소비한 UTXO를 UTXO set에서 제거하고, 새로 발생한 UTXO를 이것에 추가하여 내용을 업데이트한다. 따라서 UTXO set은 전체 계정 상태와 같이 거래의 전체 상태를 관리한다. 여기서 중요한 것은 “공개 블록체인(public blockchain)의 비신뢰 특성 때문에, 분산된 노드들이 블록체인을 통해서 모든 거래를 독립적으로 검증하여 거래의 전체 상태인 UTXO set를 완성하는 것이다.”는 것이다. 따라서 비트코인은 노드 관점에서 블록체인을 복제하여 이를 동기화하고, 이를 통해서 모든 거래를 독립적으로 검증하여 전체 상태인 UTXO 세트를 완성하는 것이다. 이는 비트코인의 비신뢰(trustless) 특성 때문이다. 결국 비트코인의 모든 상태는 UTXO set와 맴풀이 가지고 있다. 이때 UTXO 세트는 전체 상태인 모든 UTXO를 관리하고, 맴풀은 블록체인에 기록되기를 기다리는 모든 미승인 거래(unconfirmed Tx)를 관리한다.
비트코인은 분산된 비신뢰 합의 알고리즘(distributed trustless consensus algorithm)이기 때문에 노드는 다른 노드들을 믿을 수 없다.[5] 이 때문에 노드 자신이 전체 블록체인을 독립적으로 검증해야 한다. 이것은 블록이 디지털 서명이 포함된 거래와 다른 블록과 체인으로 연결되어 있기 때문에 가능한 것이다. 이 때문에, 새 노드가 비트코인 네트워크에 처음 접속하면, 그는 전체 블록체인을 반드시 다운로드 받으며, 이를 초기 블록체인 동기화(Initial Block Download, IBD)라고 부른다[6]. 즉 IBD는 새 노드가 비신뢰 네트워크에서 독립성을 유지하기 위해 블록체인 전체를 다운받아 모든 거래를 검증하고, 이를 통해서 올바른 UTXO 세트를 독립적으로 완성하기 위한 목적으로 사용한다. 참고로, 비트코인 코어(bitcoin core) 0.10.0은 노드가 144개의 블록, 즉 약 24시간 이상 동안 네트워크에 접속하지 못하면, IBD를 다시 시작하여 블록체인을 동기화시킨다[6].
3. 최근의 블록체인만 포함한 부분 삭제 노드(pruned node)
부분 삭제 노드(pruned node)는 전체 블록체인을 저장하지 않는 노드를 말한다.[7] 구체적으로 말하면, 새 노드가 전체 블록체인을 다운받고 이를 검증한 후, UTXO set을 완성한다. 그 후 이 노드는 특정 개수의 최근 블록체인만을 가지고 있고, 그전의 블록체인을 삭제한 부분 삭제 노드(pruned node)가 될 수 있다[7]. 이 노드는 전체 블록체인을 검증하여 거래의 상태인 UTXO set를 완성했기 때문에, 전체 블록체인 대신에 최신의 일부 블록체인만을 저장하고 있어도 올바로 동작한다. 따라서 만일 자신의 노드만 생각한다면, 노드가 일단 UTXO set을 완성한 후에 전체 블록체인을 가지고 있을 필요는 없다. 이 노드는 단지 블록체인에 포크가 발생하였을 경우를 대비하여 최근의 몇 개 블록만 저장해도 된다.[8]. 노드들이 전체 블록체인을 가지고 있는 목적은 새 노드들이 블록생산(채굴)에 참여할 수 있도록 이들에게 전체 블록체인을 제공하는 위한 것이다[9].
그림 2(a)는 전체 블록체인을 가지고 있는 기존 블록체인(conventional blockchain)을 보여준다. 여기서 h와 t는 블록체인의 헤더부(header part)와 거래부(transaction part)를 각각 나타내고, 아래 첨자는 블록의 생성순서를 나타낸다. 기존 블록체인은 그림 2(a)과 같이 최초 블록(genesis block)부터 최근 블록까지 전체 블록체인을 포함한다. 그림에서 화살표는 이전 블록의 블록해시를 현재 블록에 포함시켜서 체인으로 연결시킨 것을 나타낸다. 만일 새 노드가 비트코인 네트워크에 참여한다면, 이 노드는 이 그림 2(a)과 같이 전체 블록체인을 다운로드받기 위해 IBD를 진행해야 한다. 그리고 그림 2(b)는 특정 개수의 최근 블록체인을 저장한 부분 삭제 블록체인(pruned blockchain)을 보여준다. 부분 삭제 노드는 그림 2(b)와 같이 특정 개수의 최신 블록만을 가지고 있다.[7] 그림 2(b)의 경우, 이 노드는 m번째 블록부터 최신 블록인 n번째 블록을 포함하고, n — m은 일정한 상수이다. 노드는 전체 블록체인을 저장하여 검증하고 UTXO set을 완성한 후, 부분 삭제 노드가 될 수 있다. 하지만 이 경우, 이 노드는 새 노드가 네트워크에 참여하도록 전체 블록체인을 제공할 수는 없다.
4. 초기 UTXO 다운로드(Initial UTXO Download) 방법
비트코인에서 거래의 전체 상태인 UTXO set은 채굴의 편의를 위해서 메모리에 저장된다. 전체 UTXO set의 크기는 2017년 5월 20일 현재 약 1.9 GiB이었고, 당시 블록체인 크기의 약 1.6%에 불과할 정도로 작다.[10] 블록체인이 거래에 대한 추가전용 DB이기 때문에, 이 비율은 앞으로 점점 작아질 것이다. 이런 이유 때문에, 새 노드가 비트코인 네트워크에 처음 접속하여 IBD를 통해 전체 블록체인을 전송받는 것보다 전체 UTXO set을 전송받는 것이 더 좋은 방법이다. 즉, 만일 새 노드가 초기 동기화 동안 올바른 전체 UTXO set를 이웃 노드로부터 다운받을 수 있다면, 전체 블록체인을 다운받지 않아도 된다. 하지만, 공개 블록체인(public blockchain)에서 노드들은 서로를 믿지 못하는 비신뢰 특성 때문에, 새 노드가 이웃 노드들로부터 UTXO 세트를 직접 다운받는 것은 안전하지 않다. 왜냐하면, 새 노드가 다운로드 받은 UTXO set이 올바른 것인지를 판단할 수 없기 때문이다.
이를 해결하기 위해서, UTXO 확정 (UTXO commitments) 방법이 이미 제안되었고, 이를 경량 지갑(light wallet)에 적용하려는 여러 가지 제안들이 있었다.[11–13] 이것은 전체 UTXO set를 머클트리(merkle tree)로 구성하고, 이것의 루트 해시를 블록에 기록하는 방법이다. 그리고 새 노드는 전체 UTXO set을 전송받고 이를 머클트리로 구성하여 이것의 루트 해시를 구하고 블록에 기록된 루트해시를 비교하여 안전성을 검증한다. 즉 UTXO 확정은 p2p 네트워크에서 다른 노드로부터 전파 받은 UTXO set이 올바른지를 확인하는 데 사용할 수 있다. 이것을 초기 UTXO 동기화(initial UTXO download, IUD)라 부르자. IUD의 장점은 다음과 같다. 1) IUD는 기존의 IBD를 통해 전체 블록체인을 다운받는 방법보다 전송받는 데이터가 매우 작다. 이 때문에 새 노드가 매우 빨리 초기 동기화를 시킬 수 있다. 2) 기존의 IBD는 서명의 검증에 많은 CPU 자원이 필요하다. 하지만, IUD는 모든 블록을 검증하는 대신에, 전체 UTXO set을 검증하기 때문에 검증을 위한 계산량 및 시간을 크게 줄일 수 있다.
그렇지만 IUD는 노드의 독립성을 일부 포기한 것으로 보일 수 있다. 왜냐하면 기존의 IBD는 비신뢰 특성 때문에 새 노드가 전체 블록체인을 전송받아 이것에 포함된 모든 거래를 독립적으로 검증하기 때문이다. 하지만 비트코인에서 IUD가 안전한 이유는 공격자가 최근의 블록체인을 새로 만들 때 상당한 비용이 들기 때문이다. 즉, 새 노드가 IUD를 통해 UTXO set를 전송받은 후, 그가 몇 개의 최신 블록을 연속으로 검증하면 안전한 UTXO 세트를 전송받았는지 쉽게 검증할 수 있다. 그리고 비트코인 지갑은 거래가 포함된 블록 이후 6개의 새 블록이 생성되면 이체가 가능하다. 이와 유사하게, 예로 들면, 새 노드는 IUD 동안 먼저 최신 블록과 UTXO set을 전송받고 이를 검증한 후, 연속으로 5개의 새로운 블록을 전파 받아서 이 UTXO set를 계속 검증한다. 이 과정을 모두 통과할 경우 새 노드는 이 UTXO set을 사용할 수 있다.
블록에 UTXO set의 루트 해시를 기록하는 방법은 아래와 같을 수 있다. 예를 들면, 노드들은 기존 방법대로 난이도 조건을 만족하는 블록해시를 먼저 찾은 후에, UTXO set의 머클트리를 구성하여 그것의 루트 해시를 계산한다. 그리고 기존 블록과 동일하게 블록을 만들고, 추가로 머클트리의 루트 해시를 블록에 기록한다. 또한 이 루트 해시와 블록해시로 새로운 해시를 만들어 이를 블록에 추가할 수 있다.
5. 기존 트리의 정렬을 이용한 정렬된 머클트리(sorted merkle tree)
그림 3(a)에 보인 기존 머클트리를 먼저 살펴보자. 이 그림의 기존 머클트리는 이진트리(binary tree)이고, 데이터인 UTXO가 모두 말단 노드(leaf nodes)에 위치한다. 그리고 이것의 내부노드(interior nodes)는 두 자식 노드를 연결하여 계산한 해시로 구성하고 루트 해시와 연결된다.[14] 그림 3에서 u와 h는 각각 UTXO와 해시(hash)를 나타내고, 아래첨자는 이들의 이름을 가리킨다. 내부노드의 해시를 구하는 예를 들면, 2번 노드의 해시는 h2 = hf(h4 || h5)로 계산한다. 이때, hf는 해시함수이고, ||는 연결(concatenation) 연산자이다. 따라서 기존 머클트리에서 루트 노드의 루트 해시(h1)는 단말노드에 위치한 데이터인 모든 UTXO에 의존하게 된다. 이 때문에, 만일 데이터가 하나라도 바뀌면, 해당 노드로부터 루트 노드로 이어지는 노드들의 해시가 바뀌고 결국 루트 해시(h1)가 바뀐다.
2017년 5월 20일 현재 UTXO set의 크기는 약 1.9 GiB이고, 이것은 약 5천4백만 개의 UTXO를 포함한다.[15] 이것은 앞으로 더 증가할 수밖에 없다. 그리고 전체 UTXO set를 머클트리로 구성하고 이것의 루트 해시를 구하는 것은 많은 해시 계산이 필요하다. 하지만 비트코인에서 새 블록이 생성될 때마다, UTXO set에 새로 생성된 UTXO를 삽입하고 소비한 UTXO를 삭제한다. 새 블록마다, UTXO set의 머클트리를 업데이트하고 내부노드의 해시를 다시 계산하는 것은 너무 많은 해시 계산이 발생하는 등의 문제가 있었다. 이런 이유로 아직까지 비트코인에 IUD를 적용하지 못하고 있다[13]. 더불어 기존 머클트리는 모든 데이터, 즉 전체 UTXO가 단말 노드에 위치하기 때문에, UTXO가 정렬되어 있지 않는다. 이 때문에, 기존 머클트리는 특정 데이터의 비존재 증명에 이용할 수 없었다.[16]
이를 해결하기 위해, 우리는 기존 이진트리를 이용한 정렬된 머클트리(sorted merkle tree)를 제안한다. 그림 1(b)는 우리가 제안한 새로운 머클트리를 보여준다. 이 머클트리는 기존의 이진트리를 이용하여 데이터인 UTXO를 모든 노드에 정렬시키고, 그 후에 내부노드의 해시를 계산한다. 이 때문에, 우리가 제안한 머클트리는 AVL 트리 또는 레드-블랙 트리(red-black tree) 등과 같은 시간 복잡도가 O(log n)인 균형 이진트리(balanced binary tree) 등을 사용할 수 있다. 구체적으로, 우리가 제안한 머클트리는 새 블록이 생성될 때마다 먼저 기존 UTXO의 이진트리에 사용된 UTXO 및 새로 생성된 UTXO를 삭제 및 삽입하고, 그 후에 해당하는 노드의 해시를 부가적으로 계산한다. 구체적으로, 그림 3(b)에서 말단노드의 해시는 h2와 h3이고, 이들은 hself = hf(uleft || uright || uself)로 구한다. 예를 들면, 2번 노드의 해시(h2)는 u4, u5와 u2를 연결하여 구한다. 그리고 만일 자식 노드에 해시가 존재할 경우, 이 노드의 해시는 자식노드의 해시와 자신의 UTXO를 연결하여 구한다. 예를 들면, 루트 해시(h1)는 h2, h3와 u1을 연결하여 구한다. 이 머클트리의 장점은 다음과 같다. 첫 번째, 이것은 내부노드에 데이터를 저장하고 있기 때문에 기존 머클트리에 비해서 이진트리의 노드 개수를 약 1/2로 줄인다. 이 때문에 기존 머클트리에 비해 해시의 개수가 약 절반으로 줄어든다. 즉 데이터의 업데이트 시에 해시 계산의 개수가 줄어든다. 두 번째, 제안한 머클트리는 기존 이진트리로 데이터인 UTXO를 먼저 정렬하고, 이 때문에 이것은 특정 UTXO의 존재 여부를 쉽게 증명할 수 있다. 따라서 경량 지갑에서 특정 거래의 존재 여부에 대한 검증이 가능하다. 우리의 머클트리에서 데이터의 비존재 증명은 비존재하는 데이터의 양 옆에 있는 데이터가 바로 이웃하고 있는지를 증명하면 가능하다. [16] 참고로, 경량지갑에서 거래의 존재 증명은 아래와 같이 확인할 수 있다. 예를 들면, 그림 3(b)의 제안한 머클트리에서 u2의 검증은 u4, u5, u2, h3가 필요하다. 이에 비해 그림 3(a)의 기존 머클트리에서 u2의 검증은 u1, u2, h5, h3가 필요하다.
더불어, 기존 머클트리는 각 데이터, 즉 UTXO를 검증할 때, 단 하나의 이웃 데이터를 포함한다. 하지만 우리가 제안한 머클트리는 내부 노드에 데이터를 포함하기 때문에 각 데이터를 검증할 때, 기존 머클트리에 비해서 더 많은 데이터를 포함해야 한다. 하지만, 비트코인은 공개 블록체인이므로, 특정 거래의 검증 과정에서 특정 utxo를 노출하는 것은 전혀 문제가 되지 않는다.
그리고 이더리움은 UTXO 대신에 계정(accounts)을 가지고 있고, 머클 페트리샤 트리(merkle patricia tree)에 저장한다.[17] 비슷하게 코스모스 코인도 계정을 가지고 있고, 이를 머클 IAVL+ 트리(merkle IAVL+ tree)에 저장된다.[18] 하지만, 이들도 모두 단말노드에 계정 데이터를 저장한다. 따라서 이더리움과 같이 계정의 전체 상태를 가진 암호화폐에도 우리가 제안한 정렬된 머클트리 구조를 적용할 수 있다.
6. 결론
본 논문은 비트코인에서 초기 동기화 시에 UTXO 확정(commitments)을 이용하기 위해, 머클트리의 노드의 개수를 약 1/2로 줄인 정렬된 머클트리(sorted merkle tree)를 제안한다. 이 머클트리를 사용하면, 매 블록마다 삭제 및 추가되는 UTXO에 때문에 발생하는 머클트리에서 변화된 전체 해시 계산 개수를 줄일 수 있다. 이 때문에 전체 블록체인을 다운받는 초기 블록 다운로드(IBD) 대신에, UTXO set을 다운로드받는 초기 UTXO 다운로드(IUD)를 사용할 수 있을 것으로 추측한다. 결론적으로 우리는 IUD를 사용할 수 있도록, 머클트리에서 노드의 개수를 기존 머클트리에 비해서 약 1/2로 줄인 새로운 머클트리 구조를 제안한다.
References
[1] Satoshi Nakamoto, “Bitcoin: A Peer-to-Peer Electronic Cash System.” https://bitcoin.org/bitcoin.pdf (2009)
[2] No Auther, “Bitcoin Core.” https://en.wikipedia.org/wiki/Bitcoin_Core (accessed 3 April 2018)
[3] No Auther, “Scalability.” Bitcoin Wikipedia https://en.bitcoin.it/wiki/Scalability (accessed 3 April 2018)
[4] No Auther, “Block Chain Overview.” https://bitcoin.org/en/developer-guide#block-chain-overview
[5] Aleksandr Bulkin, “Explaining blockchain — how proof of work enables trustless consensus.” https://keepingstock.net/explaining-blockchain-how-proof-of-work-enables-trustless-consensus-2abed27f0845
[6] No Auther, “Initial Block Download.” https://bitcoin.org/en/developer-guide#initial-block-download
[7] No Auther, “Block file pruning.” https://github.com/bitcoin/bitcoin/blob/v0.11.0/doc/release-notes.md#block-file-pruning
[8] No Auther, ”Chain Reorganization.” https://en.bitcoin.it/wiki/Chain_Reorganization
[9] No Auther, “Full Node.” https://bitcoin.org/en/developer-guide#full-node
[10] No Auther. “Unspent transaction output set.” Statoshi.info http://statoshi.info/dashboard/db/unspent-transaction-output-set (accessed 5 April 2017)
[11] Andrew Miller. “Storing UTXOs in a Balanced Merkle Tree.” Bitcointalk https://bitcointalk.org/index.php?topic=101734.0
[12] No Auther. “Pettycoin Revisted Part I: Utxo Commitments.” http://rustyrussell.github.io/pettycoin/2014/11/29/Pettycoin-Revisted-Part-I:-UTXO-Commitments.html
[13] Peter Todd. “Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments.” https://petertodd.org/2016/delayed-txo-commitments
[14] No Auther. “Merkle tree.” https://en.wikipedia.org/wiki/Merkle_tree
[15] No Auther. “Number of Unspent Transaction Outputs.” https://blockchain.info/charts/utxo-count?timespan=all
[16] No Auther. “sorted-merkle-tree-issue693.” https://gist.github.com/chris-belcher/eb9abe417d74a7b5f20aabe6bff10de0
[17] Gavin Wood. “Ethereum: A secure decentralized generalized transaction ledger” No Publisher (2014) http://gavwood.com/paper.pdf
[18] Jae Kwon and Ethan Buchman. “Cosmos whitepaper.” Cosmos https://cosmos.network/whitepaper (accessed 3 April 2018)