비트코인: 개인 간 전자 화폐 시스템

Abstract

순수한 peer-to-peer 방식의 전자 화폐는 금융 기관을 거치지 않고 한쪽에서 다른 쪽으로 직접 온라인 지불을 가능하게 할 것이다. 전자 서명이 해결책의 일부를 제공하지만, 이중 지불을 방지하기 위해 여전히 신뢰할 수 있는 제3자가 필요하다면 주요 이점은 사라진다. 우리는 peer-to-peer 네트워크를 이용한 이중 지불 문제의 해결책을 제안한다. 이 네트워크는 거래를 hash 기반의 proof-of-work 체인에 hash하여 타임스탬프를 부여하며, proof-of-work를 다시 수행하지 않고는 변경할 수 없는 기록을 형성한다. 가장 긴 체인은 목격된 사건의 순서에 대한 증거일 뿐만 아니라, 그것이 가장 큰 CPU 연산 능력의 풀에서 나왔다는 증거이기도 하다. CPU 연산 능력의 과반수가 네트워크를 공격하려고 협력하지 않는 노드들에 의해 통제되는 한, 그들은 가장 긴 체인을 생성하여 공격자를 앞지를 것이다. 네트워크 자체는 최소한의 구조만을 필요로 한다. 메시지는 최선 노력(best effort) 기반으로 브로드캐스트되며, 노드들은 자유롭게 네트워크를 떠났다가 다시 참여할 수 있고, 부재 중에 일어난 일의 증거로서 가장 긴 proof-of-work 체인을 수용한다.

Introduction

인터넷 상의 상거래는 전자 지불을 처리하는 신뢰할 수 있는 제3자 역할을 하는 금융 기관에 거의 전적으로 의존하게 되었다. 이 시스템은 대부분의 거래에서 충분히 잘 작동하지만, 신뢰 기반 모델의 본질적인 약점으로부터 여전히 벗어나지 못한다. 금융 기관이 분쟁 중재를 피할 수 없기 때문에, 완전히 비가역적인 거래는 사실상 불가능하다. 중재 비용은 거래 비용을 증가시키며, 최소 실용적 거래 규모를 제한하고, 소규모 일상 거래의 가능성을 차단한다. 또한 비가역적 서비스에 대해 비가역적 지불을 할 수 없게 됨으로써 더 광범위한 비용이 발생한다. 취소 가능성이 존재하면 신뢰의 필요성이 확산된다. 상인은 고객을 경계해야 하며, 본래 필요하지 않을 정보까지 요구하게 된다. 일정 비율의 사기는 불가피한 것으로 받아들여진다. 이러한 비용과 지불 불확실성은 물리적 화폐를 사용하여 대면 거래에서는 피할 수 있지만, 신뢰할 수 있는 당사자 없이 통신 채널을 통해 지불하는 메커니즘은 존재하지 않는다.

필요한 것은 신뢰 대신 암호학적 증명에 기반한 전자 지불 시스템으로, 신뢰할 수 있는 제3자 없이도 두 당사자가 직접 거래할 수 있게 하는 것이다. 계산적으로 되돌리기가 실질적으로 불가능한 거래는 판매자를 사기로부터 보호하고, 일상적인 에스크로 메커니즘을 쉽게 구현하여 구매자를 보호할 수 있다. 이 논문에서 우리는 거래의 시간 순서에 대한 계산적 증명을 생성하기 위해 peer-to-peer 분산 타임스탬프 서버를 사용하는 이중 지불 문제의 해결책을 제안한다. 이 시스템은 정직한 노드들이 공격자 노드들의 어떤 협력 그룹보다 더 많은 CPU 연산 능력을 집합적으로 통제하는 한 안전하다.

Transactions

우리는 전자 화폐를 전자 서명의 체인으로 정의한다. 각 소유자는 이전 거래의 hash와 다음 소유자의 공개 키를 전자 서명하고 이를 화폐의 끝에 추가함으로써 화폐를 다음 소유자에게 전달한다. 수취인은 서명을 검증하여 소유권의 체인을 확인할 수 있다.

물론 문제는 수취인이 소유자 중 한 명이 화폐를 이중 지불하지 않았는지 검증할 수 없다는 것이다. 일반적인 해결책은 모든 거래의 이중 지불 여부를 확인하는 신뢰할 수 있는 중앙 기관, 즉 조폐국을 도입하는 것이다. 각 거래 후, 화폐는 새로운 화폐를 발행하기 위해 조폐국으로 반환되어야 하며, 조폐국에서 직접 발행된 화폐만이 이중 지불되지 않았다고 신뢰된다. 이 해결책의 문제는 전체 화폐 시스템의 운명이 조폐국을 운영하는 회사에 달려 있으며, 은행처럼 모든 거래가 그들을 거쳐야 한다는 것이다.

우리는 수취인이 이전 소유자들이 어떤 더 이른 거래에도 서명하지 않았음을 알 수 있는 방법이 필요하다. 우리의 목적상, 가장 이른 거래가 유효한 것이므로 이후의 이중 지불 시도는 신경 쓰지 않는다. 거래의 부재를 확인하는 유일한 방법은 모든 거래를 인지하는 것이다. 조폐국 기반 모델에서, 조폐국은 모든 거래를 인지하고 어떤 것이 먼저 도착했는지 결정했다. 신뢰할 수 있는 당사자 없이 이를 달성하려면, 거래는 공개적으로 발표되어야 하며[^1], 참여자들이 거래가 수신된 순서에 대한 단일한 이력에 동의하는 시스템이 필요하다. 수취인은 각 거래 시점에 노드의 과반수가 그것이 최초로 수신되었다는 데 동의했다는 증거가 필요하다.

Timestamp Server

우리가 제안하는 해결책은 타임스탬프 서버에서 시작한다. 타임스탬프 서버는 타임스탬프를 부여할 항목 블록의 hash를 취하고, 그 hash를 신문이나 유즈넷 게시물[^2] [^3] [^4] [^5]과 같이 널리 공개하는 방식으로 작동한다. 타임스탬프는 hash에 포함되기 위해서는 당연히 그 시점에 데이터가 존재했어야 함을 증명한다. 각 타임스탬프는 자신의 hash에 이전 타임스탬프를 포함하여 체인을 형성하며, 추가되는 각 타임스탬프는 그 이전의 타임스탬프들을 강화한다.

Proof-of-Work

peer-to-peer 기반으로 분산 타임스탬프 서버를 구현하려면, 신문이나 유즈넷 게시물 대신 Adam Back의 Hashcash[^6]와 유사한 proof-of-work 시스템을 사용해야 한다. proof-of-work는 SHA-256과 같은 방식으로 hash했을 때, hash가 일정 수의 0 비트로 시작하는 값을 찾는 것을 포함한다. 필요한 평균 작업량은 요구되는 0 비트 수에 대해 지수적이며, 단일 hash 실행으로 검증할 수 있다.

우리의 타임스탬프 네트워크에서, 블록의 hash가 요구되는 0 비트를 갖는 값이 발견될 때까지 블록 내의 nonce를 증가시키는 방식으로 proof-of-work를 구현한다. CPU 노력이 proof-of-work를 충족하도록 투입되면, 그 작업을 다시 수행하지 않고는 블록을 변경할 수 없다. 이후 블록들이 그 뒤에 체인으로 연결되므로, 해당 블록을 변경하려면 그 이후의 모든 블록을 다시 수행하는 작업이 포함된다.

proof-of-work는 다수결 의사 결정에서 대표성을 결정하는 문제도 해결한다. 만약 다수결이 1-IP-주소-1-투표에 기반한다면, 다수의 IP를 할당할 수 있는 누구라도 이를 전복할 수 있다. proof-of-work는 본질적으로 1-CPU-1-투표이다. 다수결 결정은 가장 큰 proof-of-work 노력이 투입된 가장 긴 체인으로 대표된다. CPU 연산 능력의 과반수가 정직한 노드에 의해 통제되면, 정직한 체인이 가장 빠르게 성장하여 경쟁하는 어떤 체인도 앞지를 것이다. 과거 블록을 수정하려면, 공격자는 해당 블록과 그 이후 모든 블록의 proof-of-work를 다시 수행한 후 정직한 노드들의 작업을 따라잡고 능가해야 한다. 뒤처진 공격자가 따라잡을 확률이 후속 블록이 추가됨에 따라 지수적으로 감소함을 나중에 보일 것이다.

증가하는 하드웨어 속도와 시간에 따라 변동하는 노드 운영에 대한 관심을 보상하기 위해, proof-of-work 난이도는 시간당 평균 블록 수를 목표로 하는 이동 평균에 의해 결정된다. 블록이 너무 빨리 생성되면 난이도가 증가한다.

Network

네트워크를 운영하는 단계는 다음과 같다:

1. 새로운 거래가 모든 노드에 브로드캐스트된다.
2. 각 노드는 새로운 거래를 블록에 수집한다.
3. 각 노드는 자신의 블록에 대한 어려운 proof-of-work를 찾기 위해 작업한다.
4. 노드가 proof-of-work를 찾으면, 해당 블록을 모든 노드에 브로드캐스트한다.
5. 노드들은 블록 내의 모든 거래가 유효하고 아직 지출되지 않은 경우에만 블록을 수락한다.
6. 노드들은 수락된 블록의 hash를 이전 hash로 사용하여 체인의 다음 블록을 생성하는 작업을 함으로써 블록 수락을 표현한다.

노드들은 항상 가장 긴 체인을 올바른 것으로 간주하고 이를 연장하는 작업을 계속한다. 만약 두 노드가 다음 블록의 서로 다른 버전을 동시에 브로드캐스트하면, 일부 노드는 한쪽을, 다른 노드는 다른 쪽을 먼저 수신할 수 있다. 이 경우, 먼저 수신한 것에 대해 작업하되, 더 길어질 경우를 대비하여 다른 분기를 저장한다. 다음 proof-of-work가 발견되어 한 분기가 더 길어지면 동률은 깨지며, 다른 분기에서 작업하던 노드들은 더 긴 분기로 전환한다.

새로운 거래 브로드캐스트가 반드시 모든 노드에 도달할 필요는 없다. 많은 노드에 도달하는 한, 머지않아 블록에 포함될 것이다. 블록 브로드캐스트 역시 누락된 메시지에 대해 관대하다. 만약 노드가 블록을 수신하지 못하면, 다음 블록을 수신할 때 하나를 놓쳤음을 인지하고 해당 블록을 요청할 것이다.

Incentive

관례적으로, 블록의 첫 번째 거래는 블록 생성자가 소유하는 새로운 화폐를 시작하는 특별한 거래이다. 이는 노드들이 네트워크를 지원할 인센티브를 추가하며, 화폐를 발행할 중앙 기관이 없으므로 화폐를 유통에 최초로 배분하는 방법을 제공한다. 일정량의 새로운 화폐가 꾸준히 추가되는 것은 금 채굴자들이 자원을 투입하여 금을 유통에 추가하는 것과 유사하다. 우리의 경우, 투입되는 것은 CPU 시간과 전기이다.

인센티브는 거래 수수료로도 충당될 수 있다. 거래의 출력 값이 입력 값보다 작으면, 그 차이는 해당 거래를 포함하는 블록의 인센티브 값에 추가되는 거래 수수료이다. 사전에 정해진 수의 화폐가 유통에 들어가면, 인센티브는 완전히 거래 수수료로 전환될 수 있으며, 완전히 인플레이션이 없게 된다.

인센티브는 노드들이 정직하게 유지되도록 장려하는 데 도움이 될 수 있다. 탐욕스러운 공격자가 모든 정직한 노드보다 더 많은 CPU 연산 능력을 모을 수 있다면, 자신의 지불을 되돌려 훔치는 사기에 사용하거나, 새로운 화폐를 생성하는 데 사용하는 것 중에서 선택해야 한다. 그는 다른 모든 사람을 합친 것보다 더 많은 새로운 화폐를 자신에게 유리하게 하는 규칙대로 행동하는 것이, 시스템과 자신의 부의 유효성을 훼손하는 것보다 더 수익성이 높다고 판단해야 할 것이다.

Reclaiming Disk Space

화폐의 최신 거래가 충분한 블록 아래에 묻히면, 그 이전의 지출된 거래들은 디스크 공간을 절약하기 위해 폐기할 수 있다. 블록의 hash를 깨뜨리지 않으면서 이를 용이하게 하기 위해, 거래들은 Merkle Tree[^7] [^2] [^5]로 hash되며, 루트만 블록의 hash에 포함된다. 오래된 블록은 트리의 가지를 잘라내어 압축할 수 있다. 내부 hash는 저장할 필요가 없다.

거래가 없는 블록 헤더는 약 80바이트이다. 블록이 10분마다 생성된다고 가정하면, 80바이트 * 6 * 24 * 365 = 연간 4.2MB이다. 2008년 기준으로 컴퓨터 시스템이 일반적으로 2GB RAM과 함께 판매되고, 무어의 법칙이 연간 1.2GB의 현재 성장률을 예측하고 있으므로, 블록 헤더가 메모리에 유지되어야 하더라도 저장 공간은 문제가 되지 않을 것이다.

Simplified Payment Verification

전체 네트워크 노드를 운영하지 않고도 지불을 검증하는 것이 가능하다. 사용자는 가장 긴 proof-of-work 체인의 블록 헤더 사본만 유지하면 되며, 이는 가장 긴 체인을 확보했다고 확신할 때까지 네트워크 노드에 질의하여 얻을 수 있고, 거래를 타임스탬프된 블록에 연결하는 Merkle 분기를 확보하면 된다. 거래를 직접 확인할 수는 없지만, 체인의 한 위치에 연결함으로써 네트워크 노드가 이를 수락했음을 알 수 있고, 그 이후에 추가된 블록들은 네트워크가 이를 수락했음을 추가로 확인해 준다.

이와 같이, 정직한 노드들이 네트워크를 통제하는 한 검증은 신뢰할 수 있지만, 네트워크가 공격자에 의해 압도되면 더 취약해진다. 네트워크 노드가 거래를 스스로 검증할 수 있는 반면, 간소화된 방법은 공격자가 네트워크를 계속 압도할 수 있는 한 공격자의 조작된 거래에 속을 수 있다. 이에 대한 한 가지 보호 전략은 네트워크 노드가 유효하지 않은 블록을 감지했을 때 경고를 수락하여, 사용자의 소프트웨어가 전체 블록과 경고된 거래를 다운로드하여 불일치를 확인하도록 하는 것이다. 빈번한 지불을 수신하는 사업체는 보다 독립적인 보안과 빠른 검증을 위해 자체 노드를 운영하기를 원할 것이다.

Combining and Splitting Value

화폐를 개별적으로 다루는 것이 가능하겠지만, 이체에서 매 센트마다 별도의 거래를 만드는 것은 다루기 어려울 것이다. 가치의 분할과 결합을 허용하기 위해, 거래는 다수의 입력과 출력을 포함한다. 일반적으로 더 큰 이전 거래로부터의 단일 입력 또는 더 작은 금액을 결합하는 다수의 입력이 있으며, 최대 두 개의 출력이 있다: 하나는 지불을 위한 것이고, 하나는 잔돈이 있는 경우 발신자에게 돌려주는 것이다.

하나의 거래가 여러 거래에 의존하고, 그 거래들이 다시 더 많은 거래에 의존하는 팬아웃(fan-out)은 여기서 문제가 되지 않음에 유의해야 한다. 거래 이력의 완전한 독립 사본을 추출할 필요는 결코 없다.

Privacy

전통적인 은행 모델은 관련 당사자와 신뢰할 수 있는 제3자에게만 정보 접근을 제한함으로써 일정 수준의 개인정보 보호를 달성한다. 모든 거래를 공개적으로 발표해야 하는 필요성은 이 방법을 배제하지만, 정보의 흐름을 다른 곳에서 끊음으로써 개인정보 보호는 여전히 유지될 수 있다: 공개 키를 익명으로 유지하는 것이다. 대중은 누군가가 다른 누군가에게 금액을 보내고 있음을 볼 수 있지만, 거래를 누구에게도 연결하는 정보가 없다. 이는 증권 거래소가 공개하는 정보 수준과 유사하며, 개별 거래의 시간과 규모, 즉 "시세 테이프"는 공개되지만 당사자가 누구인지는 알리지 않는다.

추가적인 방화벽으로, 각 거래마다 새로운 키 쌍을 사용하여 공통 소유자에게 연결되는 것을 방지해야 한다. 다중 입력 거래에서는 일부 연결이 여전히 불가피한데, 이는 그 입력들이 동일한 소유자의 것이었음을 필연적으로 드러내기 때문이다. 위험은 키의 소유자가 밝혀지면 연결을 통해 동일한 소유자에게 속한 다른 거래들이 드러날 수 있다는 것이다.

Calculations

우리는 공격자가 정직한 체인보다 더 빠르게 대안 체인을 생성하려고 시도하는 시나리오를 고려한다. 이것이 달성되더라도, 무에서 가치를 만들거나 공격자에게 속하지 않은 돈을 빼앗는 것과 같은 임의적인 변경에 시스템을 개방하지는 않는다. 노드들은 유효하지 않은 거래를 지불로 수락하지 않을 것이며, 정직한 노드들은 그러한 거래를 포함하는 블록을 절대 수락하지 않을 것이다. 공격자는 오직 자신의 거래 중 하나를 변경하여 최근에 지출한 돈을 되돌리려고 시도할 수 있을 뿐이다.

정직한 체인과 공격자 체인 간의 경쟁은 이항 랜덤 워크(Binomial Random Walk)로 특성화할 수 있다. 성공 사건은 정직한 체인이 한 블록 연장되어 리드를 +1만큼 증가시키는 것이고, 실패 사건은 공격자의 체인이 한 블록 연장되어 격차를 -1만큼 줄이는 것이다.

주어진 격차에서 공격자가 따라잡을 확률은 도박사의 파산 문제(Gambler's Ruin problem)에 비유된다. 무한한 신용을 가진 도박사가 적자에서 시작하여 손익분기점에 도달하기 위해 잠재적으로 무한한 횟수의 시도를 한다고 가정하자. 그가 손익분기점에 도달하는 확률, 또는 공격자가 정직한 체인을 따라잡는 확률은 다음과 같이 계산할 수 있다[^8]:

p = probability an honest node finds the next block
q = probability the attacker finds the next block
q = probability the attacker will ever catch up from z blocks behind
``````

\[
qz =
\begin{cases}
1 & \text{if } p \leq q \\
\left(\frac{q}{p}\right) z & \text{if } p > q
\end{cases}
\]

p  q라는 가정하에, 공격자가 따라잡아야 하는 블록 수가 증가함에 따라 확률은 지수적으로 감소한다. 불리한 상황에서, 초반에 운 좋게 앞서 나가지 못하면, 뒤처질수록 그의 가능성은 극히 작아진다.

이제 새로운 거래의 수신자가 발신자가 거래를 변경할 수 없다고 충분히 확신하기 전에 얼마나 기다려야 하는지 고려한다. 발신자는 수신자에게 자신이 지불했다고 한동안 믿게 만든 후, 일정 시간이 지난 후 자신에게 되돌려 지불하도록 전환하려는 공격자라고 가정한다. 그런 일이 발생하면 수신자에게 경고가 가지만, 발신자는 그때쯤이면 너무 늦기를 바란다.

수신자는 새로운 키 쌍을 생성하고 서명 직전에 발신자에게 공개 키를 제공한다. 이는 발신자가 충분히 앞서 나갈 만큼 운이 좋을 때까지 블록 체인을 미리 연속적으로 작업하여 준비한 후 그 시점에 거래를 실행하는 것을 방지한다. 거래가 전송되면, 부정직한 발신자는 자신의 거래의 대안 버전을 포함하는 병렬 체인을 비밀리에 작업하기 시작한다.

수신자는 거래가 블록에 추가되고 z개의 블록이 그 뒤에 연결될 때까지 기다린다. 공격자가 이룬 정확한 진행 정도를 알 수 없지만, 정직한 블록이 블록당 평균 예상 시간이 걸렸다고 가정하면, 공격자의 잠재적 진행은 기대값이 다음과 같은 포아송 분포가 될 것이다:

\[
\lambda = z\frac{q}{p}
\]

공격자가 지금이라도 따라잡을 수 있는 확률을 구하기 위해, 그가 이룰 수 있었던 각 진행 정도에 대한 포아송 밀도에 그 지점에서 따라잡을 수 있는 확률을 곱한다:

\[
\sum_{k=0}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \cdot \left\{
\begin{array}{cl}
\left(\frac{q}{p}\right)^{(z-k)} & \text{if } k \leq z \\
1 & \text{if } k > z
\end{array}
\right.
\]

분포의 무한 꼬리를 합산하는 것을 피하기 위해 재배열하면...

\[
1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left(1-\left(\frac{q}{p}\right)^{(z-k)}\right)
\]

C 코드로 변환하면...

```c
#include math.h

double AttackerSuccessProbability(double q, int z)
{
    double p = 1.0 - q;
    double lambda = z * (q / p);
    double sum = 1.0;
    int i, k;
    for (k = 0; k = z; k++)
    {
        double poisson = exp(-lambda);
        for (i = 1; i = k; i++)
            poisson *= lambda / i;
        sum -= poisson * (1 - pow(q / p, z - k));
    }
    return sum;
}

몇 가지 결과를 실행하면, z에 따라 확률이 지수적으로 감소하는 것을 볼 수 있다.

q=0.1
z=0 P=1.0000000
z=1 P=0.2045873
z=2 P=0.0509779
z=3 P=0.0131722
z=4 P=0.0034552
z=5 P=0.0009137
z=6 P=0.0002428
z=7 P=0.0000647
z=8 P=0.0000173
z=9 P=0.0000046
z=10 P=0.0000012

q=0.3
z=0 P=1.0000000
z=5 P=0.1773523
z=10 P=0.0416605
z=15 P=0.0101008
z=20 P=0.0024804
z=25 P=0.0006132
z=30 P=0.0001522
z=35 P=0.0000379
z=40 P=0.0000095
z=45 P=0.0000024
z=50 P=0.0000006

P가 0.1% 미만인 경우를 풀면...

P  0.001
q=0.10 z=5
q=0.15 z=8
q=0.20 z=11
q=0.25 z=15
q=0.30 z=24
q=0.35 z=41
q=0.40 z=89
q=0.45 z=340

Conclusion

우리는 신뢰에 의존하지 않는 전자 거래 시스템을 제안했다. 전자 서명으로 만들어진 화폐의 일반적인 프레임워크에서 출발했는데, 이는 소유권의 강력한 통제를 제공하지만 이중 지불을 방지할 방법 없이는 불완전하다. 이를 해결하기 위해, 거래의 공개 이력을 기록하는 proof-of-work를 사용하는 peer-to-peer 네트워크를 제안했으며, 정직한 노드가 CPU 연산 능력의 과반수를 통제하는 한 공격자가 변경하는 것이 계산적으로 빠르게 실질적으로 불가능해진다. 네트워크는 비구조적 단순성에서 강건하다. 노드들은 거의 조율 없이 모두 동시에 작업한다. 메시지가 특정 장소로 라우팅되지 않고 최선 노력(best effort) 기반으로만 전달되면 되므로, 노드를 식별할 필요가 없다. 노드들은 자유롭게 네트워크를 떠났다가 다시 참여할 수 있으며, 부재 중에 일어난 일의 증거로서 proof-of-work 체인을 수용한다. 그들은 CPU 연산 능력으로 투표하며, 유효한 블록을 연장하는 작업을 통해 수락을 표현하고, 유효하지 않은 블록에 대한 작업을 거부함으로써 이를 거부한다. 필요한 규칙과 인센티브는 이 합의 메커니즘으로 시행될 수 있다.

References