원장

안전한 원장이 있다면 이를 디지털 결제 시스템으로 전환하는 과정은 비교적 간단합니다. 예를 들어, 앨리스가 페이팔을 통해 밥에게 100달러를 송금하면, 페이팔은 앨리스의 계좌에서 100달러를 차감하고 밥의 계좌에 100달러를 입금합니다. 이는 전통적인 은행 시스템에서도 대체로 비슷하게 작동하지만, 은행 간에 공유되는 단일 원장이 없다는 점에서 더 복잡해집니다.

원장의 개념은 비트코인을 이해하기 위한 출발점입니다. 원장은 시스템 내에서 발생하는 모든 거래를 기록하는 장소이며, 시스템 참가자 모두가 이를 열람하고 신뢰할 수 있습니다. 비트코인은 이 결제 기록 시스템을 화폐로 변환했습니다. 은행 시스템에서는 계좌 잔액이 은행에서 요구할 수 있는 현금을 나타내지만, 비트코인에서는 하나의 비트코인 단위가 무엇을 나타내는 것일까요? 지금은 거래되고 있는 것이 본질적으로 가치를 가진다고 가정해 봅시다.

참가자들이 서로를 신뢰하지 않을 수 있는 인터넷과 같은 환경에서 원장을 어떻게 구축할 수 있을까요? 먼저 쉬운 부분부터 시작해 보겠습니다. 데이터 구조의 선택입니다. 몇 가지 바람직한 속성이 있습니다. 원장은 변경 불가능하거나, 더 정확히 말하면 추가만 가능한 형태여야 합니다. 즉, 새로운 거래를 추가할 수는 있지만 기존 거래를 삭제하거나 수정하거나 순서를 바꾸어서는 안 됩니다. 또한, 원장의 상태를 언제든 간결하게 요약할 수 있는 암호학적 다이제스트를 생성할 수 있어야 합니다. 다이제스트는 원장의 전체 내용을 저장하지 않고도, 원장이 조금이라도 조작되었다면 결과적으로 다이제스트가 변하기 때문에 이를 통해 조작 여부를 탐지할 수 있습니다.

이러한 속성들이 필요한 이유는 원장이 단일 기계에 저장되는 일반적인 데이터 구조와 달리, 상호 신뢰하지 않는 참가자 집단에 의해 공동으로 유지되는 글로벌 데이터 구조이기 때문입니다. 이는 또 다른 탈중앙화 원장 접근 방식과 대조를 이룹니다. 그 방식에서는 많은 참가자가 각자 로컬 원장을 유지하며, 원장 간의 충돌을 해결하는 책임은 원장을 조회하는 사용자에게 있습니다.

연결된 타임스탬핑

비트코인의 원장 데이터 구조는 1990년부터 1997년 사이에 스튜어트 하버(Stuart Haber)와 스콧 스토네타(Scott Stornetta)가 작성한 일련의 논문에서 최소한의 수정만 가하여 차용되었습니다(1991년 논문은 데이브 베이어(Dave Bayer)라는 공동 저자가 추가로 참여했습니다). 나카모토는 자신의 비트코인 백서에서 이를 명확히 밝히고 있습니다. 하버와 스토네타의 연구는 문서 타임스탬핑 문제를 다뤘으며, "디지털 공증" 서비스를 구축하는 것을 목표로 했습니다. 이는 특허, 사업 계약, 기타 문서에서 문서가 특정 시점에 생성되었음을 확립하려는 목적을 가졌습니다. 그들의 문서 개념은 매우 일반적이어서 데이터 유형에 관계없이 적용될 수 있었습니다. 그들은 금융 거래를 잠재적인 응용 분야로 언급하기는 했지만, 이는 주된 초점이 아니었습니다.

하버와 스토네타의 제안을 단순화하면, 문서가 지속적으로 생성되고 방송된다고 가정할 수 있습니다. 각 문서의 생성자는 생성 시점을 주장하며 문서, 타임스탬프, 그리고 이전에 방송된 문서를 서명합니다. 이전 문서는 자신의 선행 문서에 서명했기 때문에, 문서들은 시간적으로 뒤로 연결되는 긴 체인을 형성합니다. 외부 사용자는 타임스탬프가 부여된 메시지를 수정할 수 없는데, 이는 생성자가 서명했기 때문입니다. 또한, 생성자는 메시지를 수정하려면 이후의 모든 메시지 체인을 수정해야 합니다. 따라서, 신뢰할 수 있는 소스(예: 다른 사용자 또는 전문 타임스탬핑 서비스)로부터 체인의 한 항목을 제공받는다면, 해당 시점까지의 전체 체인은 고정되어 있으며, 변경 불가능하고 시간적으로 순서가 정해져 있습니다. 또한 시스템이 잘못된 생성 시간을 가진 문서를 거부한다고 가정하면, 문서가 주장하는 시간보다 늦게 생성되지 않았음을 상당히 확신할 수 있습니다. 어쨌든, 비트코인은 하버와 스토네타의 작업에서 데이터 구조만을 차용하며, 이후에 설명되는 작업 증명(proof-of-work) 방식을 추가하여 보안 속성을 새롭게 설계합니다.

후속 논문에서 하버와 스토네타는 이 데이터 구조를 더욱 효과적이고 효율적으로 만드는 다른 아이디어들을 제안했습니다(일부는 첫 번째 논문에서도 암시되었습니다). 첫째, 문서 간의 연결을 서명 대신 해시를 사용해 생성할 수 있습니다. 해시는 계산이 더 간단하고 빠릅니다. 이러한 연결을 "해시 포인터(hash pointer)"라고 부릅니다. 둘째, 문서를 개별적으로 연결하는 대신, 비슷한 시간대에 생성된 여러 문서를 그룹화하여 배치나 블록으로 처리할 수 있습니다. 블록 내 문서는 기본적으로 동일한 타임스탬프를 가집니다. 셋째, 각 블록 내 문서를 선형 체인이 아닌 해시 포인터로 이루어진 이진 트리, 즉 머클 트리(Merkle tree)로 연결할 수 있습니다. 흥미롭게도, 조쉬 베날로(Josh Benaloh)와 마이클 드 마레(Michael de Mare)는 하버와 스토네타의 첫 논문 직후인 1991년에 이 세 가지 아이디어를 독립적으로 제안했습니다.

머클 트리

비트코인은 기본적으로 하버와 스토네타가 1991년과 1997년 논문에서 제안한 데이터 구조를 사용하며, 이는 간략화된 형태로 그림 2에 나타나 있습니다(나카모토는 아마도 베날로와 드 마레의 작업을 인지하지 못했을 가능성이 큽니다). 물론 비트코인에서는 문서 대신 거래가 해당 자리를 대체합니다. 각 블록의 머클 트리에서 리프 노드(잎 노드)는 거래를 나타내며, 각 내부 노드는 본질적으로 두 개의 포인터로 구성됩니다.

이 데이터 구조는 두 가지 중요한 속성을 가지고 있습니다. 첫째, 최신 블록의 해시는 요약(digest) 역할을 합니다. 어느 거래(리프 노드)에라도 변화가 생기면 그 변화는 블록의 루트까지, 그리고 이후 모든 블록의 루트까지 전파되어야 합니다. 따라서 최신 해시 값을 알고 있다면, 신뢰할 수 없는 소스에서 원장을 다운로드하더라도 원장이 변경되지 않았는지 확인할 수 있습니다.

둘째, 이 데이터 구조는 특정 거래가 원장에 포함되어 있음을 효율적으로 증명할 수 있다는 점에서도 중요합니다. 이를 위해 사용자는 해당 거래가 포함된 블록의 소수의 노드만 전송하면 되며(머클 트리의 핵심이 바로 이것입니다), 이후 모든 블록에 대해 소량의 추가 정보를 전송하면 됩니다. 거래의 포함 여부를 효율적으로 증명할 수 있는 능력은 성능과 확장성 면에서 매우 바람직한 속성입니다.

참고로 머클 트리는 비대칭 암호학의 선구자인 랄프 머클(Ralph Merkle)이 1980년 논문에서 제안한 아이디어에서 이름을 따왔습니다. 머클의 의도는 디지털 인증서의 공공 디렉터리에 대한 요약(digest)을 생성하는 것이었습니다. 예를 들어, 웹사이트가 사용자에게 인증서를 제시할 때, 인증서가 글로벌 디렉터리에 포함되어 있음을 증명하는 간단한 증명도 함께 제공할 수 있습니다. 사용자는 디렉터리 내 인증서의 머클 트리 루트 해시만 알고 있다면 이 증명을 효율적으로 검증할 수 있습니다. 이 아이디어는 암호학적으로는 오래된 개념이지만, 그 강력함은 최근에 와서야 널리 인정받고 있습니다. 머클 트리는 최근 구현된 Certificate Transparency 시스템의 핵심입니다. 2015년 논문에서는 머클 트리를 공개 키 디렉터리에 적용하는 CONIKS를 제안했으며, 이는 종단 간 암호화 이메일을 위한 것입니다. 글로벌 상태의 일부를 효율적으로 검증하는 기능은 새로운 암호화폐인 이더리움의 원장이 제공하는 주요 기능 중 하나입니다.

비트코인은 하버와 스토네타의 데이터 구조를 현실 세계에서 가장 잘 알려진 형태로 구현한 사례일 수 있지만, 최초는 아닙니다. 최소 두 개의 회사—1990년대 중반 시작된 Surety와 2007년에 시작된 Guardtime—가 문서 타임스탬핑 서비스를 제공했습니다. 이들 서비스에는 베이어, 하버, 스토네타가 언급한 흥미로운 아이디어가 적용되었는데, 그것은 머클 루트를 주기적으로 신문 광고에 게시하는 방식입니다. Guardtime이 신문에 게시한 머클 루트의 예는 그림 3에 나와 있습니다.

비잔틴 장애 허용

중앙 권한 없이 운영되는 인터넷 화폐는 훨씬 더 엄격한 요구사항을 충족해야 합니다. 분산 원장은 필연적으로 포크(fork)를 가지게 되는데, 이는 일부 노드가 블록 A를 최신 블록으로 간주하는 반면, 다른 노드는 블록 B를 최신 블록으로 간주하는 상황을 뜻합니다. 이는 원장을 방해하려는 공격자가 존재하거나 단순히 네트워크 지연으로 인해 발생할 수 있습니다. 네트워크 지연은 서로의 블록을 인지하지 못한 상태에서 서로 다른 노드가 거의 동시에 블록을 생성하는 결과를 초래합니다. 1998년 마이크 저스트(Mike Just)는 단순한 연결된 타임스탬핑만으로는 이러한 포크 문제를 해결할 수 없음을 보여주었습니다.

이 문제는 고장 허용 분산 컴퓨팅(fault-tolerant distributed computing)이라는 다른 연구 분야에서 다뤄져 왔으며, 이 분야에서는 이를 상태 복제(state replication) 등 다양한 이름으로 부릅니다. 이 문제의 해결책은 특정 노드 집합이 동일한 상태 전이를 동일한 순서로 적용하도록 보장하는 것입니다. 일반적으로 그 순서 자체는 중요하지 않지만, 모든 노드가 일관된 상태를 유지해야 합니다. 디지털 화폐의 경우, 복제될 상태는 계좌 잔액 집합이며, 거래는 상태 전이에 해당합니다.

레슬리 램포트(Leslie Lamport)가 1989년에 제안한 초기 해결책인 Paxos는 통신 채널이 신뢰할 수 없고, 일부 노드가 "현실적인" 결함(예: 영구적으로 오프라인 상태가 되거나, 재부팅 후 오래된 메시지를 보내는 경우)을 보일 수 있는 상황에서 상태 복제를 다룹니다. 이 후속 연구에서는 더욱 악화된 환경과 효율성 간의 트레이드오프를 포함한 다양한 설정을 다루는 풍부한 문헌이 등장했습니다.

이와 관련된 또 다른 연구는 네트워크가 대체로 신뢰할 수 있는 상태(메시지가 제한된 지연 내에 전달됨)를 가정하면서 "결함"의 정의를 프로토콜에서 벗어난 모든 행동을 포함하도록 확장했습니다. 이러한 비잔틴 결함(Byzantine faults)은 자연 발생적인 오류뿐만 아니라 악의적으로 설계된 행동도 포함합니다. 이러한 결함은 램포트, 로버트 쇼스탁(Robert Shostak), 마샬 피스(Marshall Pease)가 1982년에 발표한 논문에서 처음 연구되었습니다. 이후, 1999년 미겔 카스트로(Miguel Castro)와 바바라 리스코브(Barbara Liskov)가 발표한 획기적인 논문은 실용 비잔틴 결함 허용(PBFT, Practical Byzantine Fault Tolerance)을 소개하며, 비잔틴 결함과 신뢰할 수 없는 네트워크를 모두 수용했습니다. Paxos, PBFT 등 주요 프로토콜의 수백 가지 변형 및 최적화를 포함하는 고장 허용 문헌은 방대한 규모입니다.

나카모토는 비트코인 백서에서 이러한 문헌을 인용하거나 그 언어를 사용하지 않았습니다. 그는 자신의 프로토콜을 합의 메커니즘(consensus mechanism)이라고 부르며, 공격 형태뿐만 아니라 네트워크에 참여하거나 떠나는 노드에 대한 결함도 고려했습니다. 이는 연결된 타임스탬핑(및 이후 설명되는 작업 증명)에 대한 명시적 의존성과는 대조적입니다. 비트코인이 비잔틴 장군 문제(Byzantine Generals’ Problem)와의 관계에 대해 메일링 리스트에서 질문받았을 때, 나카모토는 작업 증명 체인이 이 문제를 해결한다고 주장했습니다.

이후 몇 년 동안 다른 학자들은 분산 시스템의 관점에서 나카모토 합의를 연구해 왔습니다. 이는 아직 진행 중인 작업입니다. 일부 연구에서는 비트코인의 속성이 비교적 약하다고 주장하는 반면, 다른 연구에서는 비잔틴 결함 허용(BFT) 관점이 비트코인의 일관성 속성을 충분히 설명하지 못한다고 주장합니다. 또 다른 접근 방식은 잘 연구된 속성의 변형을 정의하고, 비트코인이 이를 충족하는지 증명하는 것입니다. 최근에는 메시지 전달에 대한 현실적인 가정을 기반으로 보다 표준화된 일관성 정의가 크게 정교해졌습니다. 그러나 이러한 모든 연구는 참가자 일부가 "정직한"(즉, 프로토콜을 준수하는) 행동을 한다는 가정을 바탕으로 합니다. 반면, 나카모토는 정직한 행동이 맹목적으로 가정될 필요는 없으며, 이는 인센티브에 의해 유도된다고 제안합니다. 인센티브의 역할을 고려한 나카모토 합의의 더 풍부한 분석은 과거의 고장 허용 시스템 모델에 깔끔하게 들어맞지 않습니다.