Bitcoin: A Peer-to-Peer Electronic Cash System

Satoshi Nakamoto

Abstract

peer-to-peer한 전자화폐는 금융 기관을 거치지 않고도 한 개인의 다른 개인에 대한 지불을 가능케할 것이다.
전자서명도 부분적인 솔루션이 될 수 있지만, 이중 지불(double-spending)을 방지하기 위해 제 3자를 필요로한다는 점에서 main benefits(금융 기관을 거칠 필요가 없다는 이점)을 잃게 된다.
우리는 이중 지불에 대한 솔루션으로 peer-to-peer 네트워크를 제안한다.
이 네트워크는 계속해서 이어지는 해쉬 기반의 proof-of-work 체인에 거래를 해싱하여 첨부함으로서 기록한다.
이러한 기록은 proof-of-work를 다시 진행하지 않는 이상 변경될 수 없다.
가장 긴 체인은 일련의 거래들이 감시되었다는 것에 대한 증명인 동시에 이 체인이 엄청나게 거대한 CPU들의 연산 능력의 집합체라는 것에 대한 증명이다.
대다수의 CPU의 연산이 네트워크를 공격하고자 협력하는 것이 아닌 노드들에 의해 통제되고 있는 한, 그것들은 가장 긴 체인을 공격자의 속도보다 빠르게 생성할 것이다.
네트워크 자체는 최소한의 구조만을 요구한다.
메세지(거래를 했음을 의미하는)는 최선을 다해 broadcast(노드에게 소식을 전달)되며 노드들은 네트워크를 자유자재로 떠나거나 재참여할 수 있다.
그리고 proof-of-work 체인을 자신이 네트워크를 떠난 사이 벌어진 일에 대한 증명으로 여긴다.

1. Intorduction

인터넷에서의 상업 행위는 전자거래를 관장하는 신뢰받는 제 3자인 금융기관에 절대적으로 의지해왔다.
이러한 시스템은 대부분의 거래에서 제대로 작동하지만, 아직도 신뢰 기반 모델의 내제된 약점은 해결되지 않았다.
금융기관은 분쟁을 중재해야하기에 완전히 비가역적인 거래라는 것은 현실적으로 힘들다.(환불 같은 것을 책임지기에)
중재에 대한 비용은 거래 비용을 증가시키고, 실용적인 최소한의 거래 사이즈를 제한하며 작은 일상적인 거래를 하기 어렵게 한다.
또한 비가역적인 서비스에 대해서 비가역적인 지불을 불가하게 한다는 넓은 의미에 비용 손실도 존재한다.
반대 방향으로의 거래(환불)에 대한 가능성이 존재하기에 기관의 신뢰성 확보도 필요하다.
상인들은 소비자를 신경쓰고 소비자가 필요로 할, 그 이상의 정보를 번거롭게 준비하게 된다.
사기의 가능성도 배제할 수 없다.
이러한 비용과 지불의 불특정성은 지폐와 같은 현물 화폐를 이용한 거래에서는 일어나지 않는다.
하지만 아직까지 신뢰 기관 없는 메커니즘은 존재하지 않는다.

신뢰가 아닌 암호학적 증명을 기반으로 한 전자 지불 시스템이 필요로 하는 것은 거래하고자 하는 두 객체가 신뢰받는 제 3자를 통해서가 아니라 직접적으로 거래를 하게 하는 것이다.
역연산을 진행하는 것이 계산적으로 실용적이지 않은 거래는 판매자를 사기로부터 보호하고, 구매자를 보호하기 위한 일상적인 escrow 메커니즘을 쉽게 시행할 수 있다.

escrow mechanism : 제3자가 거래 당사자들을 대신해 자금을 보관하고 조건이 충족되면 지급하는 시스템

이 논문에서, 우리는 이중지불 문제애 대한 솔루션으로 분산화된 peer-to-peer 타임스탬프 서버를 이용하여 거래들을 시간 순서에 대해 계산적 증명을 생성하는 것을 제안하다.
이 시스템은 공격자 노드의 그룹보다 정직한 노드들의 CPU의 연산량이 클 수록 안전하다.

2. Transactions

우리는 전자 코인을 전자서명의 체인으로 정의한다. 각각의 소유자는 코인을 다음 소유자에게 전달할 때, 이전의 거래에 대한 다음 소유자의 공개키를 해시한 후 전자서명하여 코인의 마지막에 덧붙인다.

Alice가 Bob에게 코인을 이전 할 때 :
Bob의 public key와 이전 거래를 한꺼번에 합쳐서 해시로 만든다.  
이에 대해서 Alice의 private key로 서명을 하여 체인에 이어 붙인다.

Bob은 Alice의 public key를 이용해서 Alice의 전자서명을 해제한 값이, 
Bob의 public key와 이전 거래에 대한 해시값이 맞는지 검증한다. 

코인을 전달받은 사람(payee, 수취인)은 서명을 검증하여 소유권에 대한 체인을 검증할 수 있다.
일반적인 솔루션은 신뢰하는 중앙 권한(mint, 조폐국 같은)을 들여와서 모든 거래를 감시하는 것이다.
각각의 거래 후, 코인은 반드시 mint로 반환되고 재발행된다.
그리고 mint에서 직접 발행한 코인만이 double-spent 되지 않았다고 믿을 수 있다.
이러한 시스템은 은행처럼 모든 거래가 mint를 거쳐야 하기에 mint을 운영하는 회사에 시스템의 운명을 지탱시킨다는 문제가 있다.

우리는 수취인이 이전의 소유자가 자신과의 거래보다 전에 다른 거래에 서명하지 않았다는 것을 알 수 있게 해야한다.
그러한 목적을 위해서 가장 이른 거래 하나만에 주목하고 그 이외에 것은 배제한다.
이번 거래가 가장 이른 거래인지, 이전에 거래가 없었는지 판단하기 위한 유일한 방법은 모든 거래를 모니터링 하는 것이다.
mint-based 모델에서, mint는 모든 거래를 인지하고 있고 어떤 거래가 선행된 거래인지 판단한다.
이를 신뢰 기관 없이 성취하기 위해서, 거래는 공식적으로 선언되어야 하고, 모든 참가자가 단 하나의 거래 연대기의 순서에 동의할 수 있는 시스템이 필요하다.
수취인은 각 거래마다 대다수의 노드들이 그 거래가 이중 거래가 아님을 인정하는 증명을 필요로 한다.

3. Timestamp Server

우리가 제안하는 시스템은 타임스탬프 서버와 시작한다.
타임스탬프 서버는 타임스탬프를 찍어야 할 항목들의 블록에 대한 해시를 생성하고, 이 해시를 신문이나 유즈넷 게시물과 같은 곳에 널리 공개함으로써 작동한다.
데이터가 그 시기에 존재했어야만 해시에 포함될 수 있으므로 타임스탬프는 데이터가 그 시간에 존재했음을 증명한다.
각각의 타임스탬프는 이전의 타임스탬프를 해시에 포함하고 체인을 형성하여 점점 타임스탬프를 강화한다.

각 항목들을 포함한 블럭과 이전의 해시를 포함한 해시를 형성

4. Proof-of Work

분산화된 타임스탬프 서버를 peer-to-peer 기반으로 시행하기 위해서, Adam Back's Hashcash와 유사한 proof-of-work 시스템을 사용할 필요가 있다.
proof-of-work는 SHA-256과 같은 알고리즘으로 해시되었을 때 특정한 수의 0비트로 시작하는 값을 찾는 과정을 포함한다.
이 작업은 몇개의 0비트를 찾는지에 따라 지수적으로 시간이 증가하지만 검증은 단일 해시로 마칠 수 있다.

타임스탬프 네트워크에서는, 블록의 해시가 요구되는 수의 선행 0비트를 가질 때까지 블록 내의 nonce 값을 증가시키는 방식으로 proof-of-work를 시행한다.
일단 CPU 작업을 통해 proof-of-work를 만족시키면, 블록은 해당 작업을 다시 수행하기 전까지 변경되지 않는다.
블록이 시간 순으로 이어붙기 때문에, 블럭을 바꾸는 것은 이 뒤에 이어붙은 블록에 대한 연산까지 다시 수행하는 것을 포함한다.

블록은 이전 거래의 해시값, 여러 거래에 대한 정보와 nonce를 포함한다. 

proof-of-work는 다수결 의사결정 상황에서 대표성 문제도 해결한다.
만약 다수결이 '한 IP당 한 표' 원칙을 따른다면 이는 여러 IP를 할당할 수 있는 사람에게 전복될 수 있다.
다수결의 결과인 대표는 proof-of-work에 가장 기여를 많이 한 가장 긴 체인이다.
만약 정직한 노드에 의해서 다수의 CPU 능력이 제어되고 있다면 정직한 체인은 갖아 빠르게 성장하여 다른 경쟁 체인을 무시할 수 있다.
과거의 블록을 수정하기 위해서, 공격자는 proof-of-work를 그 블록 이후의 모든 블록에 대해서 다시 시행하고 정직한 노드의 속도를 능가해야 한다.
우리는 느린 공격자가 정직한 노드의 속도를 따라잡을 확률이 블록이 추가되면서 지수적으로 감소하는 것을 보일 것이다.

증가하는 하드웨어 속도와 노드 운영에 대한 관심의 변화에 적응하도록 proof-of-work의 난이도는 평균적인 시간 당 블록의 개수에 맞추어(개수를 유지할 수 있도록) 결정된다.
만약 블록이 너무 빨리 생성되면, 난이도가 상승한다.

5. Network

네트워크는 다음과 같은 단계를 따라 동작한다.

1) 새로운 거래는 모든 노드에 공표(broadcast)된다.
2) 각 노드는 새로운 거래를 블록에 모은다.
3) 각 노드는 블록에 대한 어려운 proof-of-work를 찾는 작업을 한다.
4) 노드가 proof-of-work를 찾으면, 모든 노드에 블록을 공표한다.
5) 노드들은 블록 안의 모든 거래가 유효하고 이전에 이미 사용된 기록이 없을 때 수용한다.
6) 노드들은 다음 블록 생성 작업을 진행할 때, 방금 만들어진 블록의 해시값을 계산에 사용하면서 방금 블록을 인정했음을 표시한다.

노드들은 항상 가장 긴 체인이 옳은 것이라고 여기고 이를 확장하는 작업을 진행한다.
만약 두 노드가 서로 다른 버전의 블록을 동시에 공표한다면, 각기 다른 블록을 먼저 전달받는 경우가 생긴다.
이러한 경우, 각 노드들은 자신이 먼저 받은 블록에 대한 작업을 진행하지만, 다른 블록에 의한 체인(branch)가 더 길어질 경우를 대비해 다른 블록도 저장해둔다.
이러한 접전은 그 다음 proof-of-work에 의해 한 쪽 체인이 더 길어지는 순간 끝난다. (동시에 생성된 두 블록 중 하나로 굳어진다.)
그리고 두개를 저장하고 있던 노드들은 길어진 체인만을 선택한다.

새로운 거래에 대한 공표는 모든 노드에 도달할 필요는 없다.
거래가 최대한 많은 노드에 도달하면 머지않아 블록에 들어가게 된다.
블록의 공표는 메세지 손실에 대해서 내성이 있다.
노드가 블록을 받지 못한다면, 그 다음 블록을 받았을 때 놓친 것을 알고 이를 요청한다.

6. Incentive

일반적으로, 블록의 첫 거래는 블록의 생성자가 소유하게 될 새로운 코인에 대한 특별한 거래이다.
이것은 네트워크를 지원하는 노드에 대한 인센티브이고, 코인에 대한 중앙 발행자가 없는 상황에서 시스템에서 순환할 초기 코인을 생성하고 나누어주는 방법이다.
일정한 양의 코인이 꾸준히 추가되는 것은 금 광부들이 자원을 소비하여 금을 채굴하여 금의 순환량이 많아지는 것과 비슷하다.
우리의 경우, CPU 시간, 전기를 소비한다.

인센티브로는 거래 수수료도 있을 수 있다.
거래의 output 값이 input 값보다 작다면 , 그 차이가 거래 수수료가 되어 거래를 담고 있는 블록의 인센티브에 더해진다.
일단 미리 정해진 코인이 순환에 풀리면, 인센티브는 온전히 거래 수수료 뿐이고, 인플레이션이 일어날 요소가 차단된다.

인센티브는 노드들이 정직함을 유지하도록 돕는다.
만약 욕심쟁이 공격자가 정직한 노드보다 많은 CPU 연산 능력을 모을 수 있다면, 그 연산 능력으로 사람들의 거래에서 사기를 칠지, 그저 새로운 코인을 인센티브로 받을지 골라야 한다.
공격자는 시스템과 자신의 재산의 유효성을 약화시키는 것보다, 규칙을 따라서 새로운 코인을 얻는 것이 이득이 된다고 생각해야 한다.

7. Reclaiming Disk Space

일단 코인의 최근 거래가 많은 블록에 의해 묻히면, 그 거래보다 이전에 사용된 거래는 삭제되고 저장 공간을 절약할 수 있다.
블록들의 해시를 해치지 않으면서 이를 활성화하기 위해, 거래들은 Merkle Tree의 루트만 블록의 해시에 포함시키고, 거래 자체는 Merkle Tree 안에 해시된다.
오래된 블록들은 트리의 가지치기를 통해 간소화될 수 있다.
내부의 해시는 저장될 필요가 없다.

블록이 완전히 채굴된 후, Merkle Tree는 가지치기를 할 수 있다.
오른쪽과 같이 트리를 간소화 한 상태에서도 Tx3을 검증할 수 있다. 

블록의 헤더는 거래가 없을 때, 80bytes이다.
블록이 매 10분마다 생성된다고 할 때, 연간 4.2MB가 생성된다.
2008년에 컴퓨터 시스템은 일반적으로 2GB의 RAM을 사용하며, 무어의 법칙에 따라 1.2GB씩 증가할 것이라고 예상되기에 저장 블록 헤더가 메모리에 보관되어야 한다고 해도 저장 공간은 문제가 되지 않는다.

8. Simplified Payment Verification

풀 네트워크 노드를 거치지 않고 지불을 검증할 수 있다.
사용자는 가장 긴 proof-of-work 체인의 블록 헤더의 사본만 지니고 있으면 된다.
이는 자신이 가장 긴 체인을 가지고 있다고 확신할 때까지 네트워크 노드들에게 질의하여 얻을 수 있으며, 해당 거래를 타임스탬프가 찍힌 블록과 연결하는 Merkle Tree 가지를 얻으면 된다.
사용자는 스스로 거래를 검증할 수 없지만, 체인으 한 부분과 연결함으로서 네트워크 노드가 승인했다는 것을 알 수 있고, 이후에 추가되는 블록은 네트워크가 이를 승인했다는 것을 확실히 해준다.

Tx3이라는 거래에 대한와 블록을 연결해주는 Merkle Branch이다.

이와 같이, 검증은 네트워크에 정직한 노드가 많을수록 신뢰할 수 있다.
하지만 네트워크에 공격자의 비율이 커질수록 취약하다.
네트워크 노드들은 거래를 스스로 검증할 수 있는 반면, 간소화된 방법은 공격자가 네트워크를 압도했을 때 조작된 거래로 속일 수 있다.
이를 방어하는 한 가지 전략은 네트워크 노드가 유효하지 않은 블록을 발견했을 때 경고를 받는 것이다.
이 경고를 받으면 소프트웨어는 모든 블록과 이상한 거래들을 다운받아 불일치를 확인한다.
거래가 빈번한 비즈니스의 경우 스스로의 노드를 운영하여 독립적인 보안과 빠른 인증을 원할 것이다.

9. Combining and Splitting Value

코인을 하나씩 다루는 것도 가능할 수 있지만, 이것은 너무나 사소한 거래까지 만들 것이다.
값들이 나뉘거나 합쳐지는 것을 가능하게 하여, 거래가 여러개의 input과 ouput을 포함할 수 있게 한다.
일반적으로, 이전의 큰 거래로 인한 단일 input이나, 적은 액수를 합친 여러개의 input이 존재할 수 있다.
output은 최대 2개가 될 수 있는데, 하나는 지불을 위한 것이며, 나머지 하나는 스스로에게의 거스름돈이다.

현재의 거래는 이전의 여러 거래에 의존하고, 이런 거래들은 미래의 거래에 영향을 미친다.
거래의 독립적인 사본을 출력할 일은 없다.

10. Privacy

전통적인 은행 모델은 참여자와 신뢰하는 제 3자의 정보에 접근을 제한하여 개인정보 보호 수준에 도달한다.
모든 거래를 공표하기에 이런 방법은 배제된다.
하지만 공개 키의 익명성으로 정보가 다른 곳으로 새는 것을 방지해 개인 정보를 유지한다.
모든 사용자는 누군가가 어느 양의 거래를 진행한다는 것은 보지만 거래를 사람과 매칭시킬 수 있는 정보가 없다.
이는 주식 거래소에서 공개하는 정보와 비슷한 수준이다.
주식 거래소에서는 개별 거래의 시간, 규모를 '테이프'를 통해 공개하지만 거래 당사자가 누구인지는 공개하지 않는다.

비트코인은 신원을 거래와 매치시킬 수 없게하여 개인정보를 지킨다. 

추가적인 방화벽으로, 매 거래마다 새로운 키 쌍이 사용되어 소유자를 매치시키는 것을 막는다.
input이 여러개인 상황에서는 그 input이 모두 한명에 의해 소유되었다는 사실이 드러나는 것은 불가피하다.
키의 소유자가 드러났을 때, 매칭은 다른 거래도 같은 사용자로부터 비롯된다는 것을 드러낸다는 위험이 있다.

11. Calculations

공격자가 정직한 체인보다 빠르게 다른 체인을 생성하는 시나리오를 고려해보자.
이것이 성공한다고 해도, 이는 없는 돈을 만들거나 공격자가 지닌적 없는 돈을 가지게 하는 등 시스템을 임의로 바꿀 수 있는 것은 아니다.
노드들은 유효하지 않는 거래를 지불로 승인하지 않을 것이며, 정직한 노드들은 그것을 포함한 블록을 승인하지 않을 것이다.
공격자는 오직 자신이 최근에 사용한 지불을 되돌리는 것만 시도할 수 있다.

정직한 체인과 공격자의 체인의 경주는 Binomial Random Walk와 비슷한 속성을 지닌다.
정직한 체인이 한 블록 연장되는 것은 성공한 이벤트로 격차를 1 벌리고, 실패한 이벤트는 공격자의 블록이 하나 연장되는 것으로 격자를 1 줄인다.

공격자가 열세에서 정직한 체인을 따라잡을 확률은 Gambler's Ruin Problem과 비슷하다.
도박꾼이 무제한의 신용으로 확률이 낮은 상황에서 손익분기점을 도달하기 위해 무한히 많은 시행을 거친다고 가정하자.
우리는 도박꾼이 손익분기점에 도달하는 확률이나 공격자가 정직한 체인을 따라잡는 확률을 다음과 같이 계산할 수 있다.

$p=$ 정직한 노드가 다음 블록을 찾을 확률
$q=$ 공격자가 다음 블록을 찾을 확률
$q_z=$ 공격자가 z개의 블록을 모두 따라잡는 확률

$q_z = \begin{cases} 1& \text{if } p \leq q\\ (q/p)^z & \text{if } p > q \end{cases}$

$p$가 $q$보다 크다는 가정이 주어졌을 때, 따라잡아야 할 블록이 많을수록 확률은 지수적으로 감소한다.
공격자에게 불리한 상황에서, 공격자는 초반에 행운 질주를 하지 않으면 공격자의 기회는 이내 사라진다.

이제 새로운 거래의 수신자가 송신자가 거래를 변경할 수 없다고 충분히 확신하기 위해 얼마나 오래 기다려야 하느지 고려해보자.
우리는 송신자가 공격자이고, 수신자에게 잠시동안 지불했다고 믿게 하 다음, 시간이 지난 후에 자신에게 다시 지불하도록 변경하려고 한다고 가정한다.
수신자는 이런 일이 발생했을 때, 알림을 받지만 송신자는 알림이 소용 없기를 바란다.

수신자는 새로운 키 쌍을 생성하고, 송신자가 서명하기 직전에 public key를 전달한다.
이것은 송신자가 미리 나중에 일어날 블록을 준비하다가 운좋게 이를 찾아서 거래 시에 실행하도록 하는 것을 방지한다.
일단 거래가 전송되면, 비정직한 송신자는 비밀리에 자신의 거래에 대한 다른 버젼을 평행 채널에서 작업하기 시작한다.

수신자는 거래가 블록에 추가되기를 기다리고, z개의 블록이 이를 뒤따른다.
수신자는 공격자가 얼마만큼의 과정을 거쳤는지 모르지만, 정직한 블록이 각 블록마다 일정한 시간이 걸렸음을 생각하면, 공격자의 과정은 설정한 변수에 대해 푸아송 분포를 따를 것이다.

Poisson distribution : 
확률론에서 단위 시간 안에 어떤 사건이 몇 번 발생할 것인지를 표현하는 이산확률분포

$\lambda = z\frac{q}{p}$

공격자가 따라잡을 확률을 게산하기 위해서, 공격자가 이미 도달한 과정에 대한 푸아송 분포와 여기서 최종저으로 따라잡기위해서 거쳐야 하는 과정에 대한 확률을 곱한다.

$\displaystyle\sum_{k=0}^{\infty}\frac{\lambda^ke^{-\lambda}}{k!}\cdot\begin{cases} (q/p)^{(z-k)}& \text{if } k \leq z\\ 1 & \text{if } k > z \end{cases}$

재배열하면

$1 - \displaystyle\sum_{k=0}^{z}\frac{\lambda^ke^{-k}}{k!}(1-(q/p)^{(z-k)})$

12. Conclusion

우리는 신뢰에 의지하지 않는 전자 거래를 시스템을 제안했다.
우리는 이는 소유권에 대한 강한 역할을 할 수 있지만 이중 지출을 방지하는데에는 불완전한 전자서명을 기반으로 한 코인의 전형적인 프레임워크에서 시작했다.
이 문제를 해결하기 위해서, proof-of-work를 이용한 peer-to-peer 네트워크를 제안하였다.
이는 과거의 거래 기록들을 모두 저장하고, 정직한 노드가 주류를 이루고 있을 때, 공격자의 연산이 신속하게 비효율적으로 변하게 한다.
네트워크는 구조가 틀이 잡혀 있지 않은 심플함 속에서 건장하다.
노드들은 적은 조정으로 동시에 동작한다.
메세지가 특정 장소에 라우트 되지 않고, 전달만 되면 되므로 각 노드들은 식별화될 필요가 없다.
노드들은 네트워크에 원할 때 참가할 수 있고, 이때 proof-of-work 체인을 네트워크에서 자리를 비운 시간 동안 일어난 작업에 대한 증명으로 여긴다.
CPU 연산 능력은 다수결의 표가 되고, 유효한 블록을 계속 확장하고 그렇지 않은 블록은 거절하면서 하나의 체인을 인정함을 표한다.
이 합의 메커니즘을 통해 필요한 규칙이나 인센티브를 시행할 수 있다.