Bitcoin: A Peer-to-Peer Electronic Cash System

0. Terminology

Node: 네트워크에 참여한 모든 사람들 (Light Node, Full Node, 채굴 Node, ...) 

I. Electronic Coin과 Transactions의 정의

Bitcoin에서는 Electronic Coin을 Chain of Digital Signatures로 정의한다.
Coin을 소유한 Owner는 이전 Transaction과 Next Owner의 Public Key를 Hash하여 Coin을 전달한다.

Fig . Electronic Coin의 Transfer 과정

Fig . Node와 Transaction의 관계

이러한 방법의 문제점으로는 Payee(받는 사람)이 Owner가 Double-spend하였는지를 확인(verify)할 수가 없다.
Payee가 이전 Owner들이 이전 Transactions들에 대해서 sign하지 않았음을 확인하기 위한 방법이 필요하다.
해결방안으로는 trusted central authority(mint)를 도입하여 매 transaction마다 확인하는 것인데, central-dependent하다.

따라서, Transactions는 Public하게 공개되어 있어야 하고, System에 참가하는 사람들이 Single History Order에 대해 동의하는 System이 필요하다. Payee는 각 Transaction에 대한 Proof가 필요하고, 이는 Majority of Nodes가 해당 transaction이 처음으로 도착했음에 동의해야 한다.

II. Timestamp Server의 구현

II-1. Timestamp Server: in Newspaper or Usenet Post

Timestamp Server는 아이템들을 모아놓은 Block들의 Hash를 따서 해당 Hash를 Widely하게 Publish한다.
이러한 Timestamp는 해당 시간에 해당 Data가 존재했음을 증명한다. 각 Hash는 이전 Timestamp를 Hash에 포함하여, Chain을 이룬다.

Fig . Hash Chain of Timestamp Server

II-2. Timestamp Server: in P2P Network w/ Proof-of-Work (PoW)

앞에서 소개한 Timestamp Server를 P2P Network에 있어 구현하고 싶었고, Bitcoin 저널에서는 PoW System을 도입했다.
Adam Back's Hashcash에서 유래된 Proof-of-Work (PoW) 시스템은 SHA-256과 같이 Hash될 때 Value를 확인한다.
Hash는 000....0으로 시작하며, 해당 작업을 완료하기 위한 'Work'의 양이 0의 #에 exponential하게 비례한다.

Fig . PoW Timestamp Network: Nonce

PoW Timestamp Network에서 우리는 각 Block에 Nonce(암호화 일시값)이 포함된다. 이는 Hash값이 원하는 0의 #에 따른 exponential한 확률에 통과하여 원하는 Hash Value 값을 가질 때 까지 계속해서 Nonce를 추출한다. 이후, CPU 연산이 원하는 시간만큼 이루어져서 PoW가 만족되면, 해당 Block은 해당 Work를 Redo하지 않는 한 수정할 수 없다. 시간이 지날수록, 다음 Block이 Chain되어 연결되기 때문에, 해당 Block을 수정하기 위해서는 그 다음 Block들에 대해서도 Redo가 이루어져야 한다.

Fig . PoW Timestamp Network: Majority Decision

Hash 함수는 일방향성(얻어낸 Hash값으로 원래 데이터를 보장할 수 없는 성질)과 임의성(Hash값과 원래 값의 연관성 추론이 불가능해야 하는 성질)이 모두 만족해야 한다.

PoW는 one-CPU-one-vote로 이루어지며, majority decision은 longest chain에 의해 표현된다. (PoW Effort가 가장 많이 투자된 Chain일 것이다!) 만약 많은 양의 CPU Power가 Honest(신뢰 가능한) Node에 의해 조절된다면, Honest(신뢰가능한, 올바른) Chain이 다른 경쟁 Chain에 비해 가장 빠르게 성장할 것이다. 만약 과거 Block을 공격자가 수정하려 한다면, 뒤의 Block에 대한 Work까지 진행해야 따라잡을 수 있는데, 이러할 확률은 현저히 떨어진다...!(수학적인 증명은 논문의 Calculations 참고)

PoW Difficulty의 결정은 평균 Block # / hour가 최대한 상수가 되게끔 Moving Average에 따라 유동적으로 결정된다. Block이 많이 생성되면 PoW 난이도는 올라갈 것이고, 적게 생성된다면 반대로 PoW 난이도는 내려갈 것이다.

III. Network

Blockchain의 Network는 다음과 같이 작동한다.

(1) 새로운 Transaction이 모든 Node에 Broadcast된다.
(2) 각 Node는 도착하는 모든 Transaction을 Block에 수집한다.
(3) 각 Node는 해당 Block에 대해 PoW를 찾기 위해 CPU Effort를 투자한다.

Fig . Network Flow of Blockchain

(4) PoW가 갖춰지면, 해당 Block을 다른 Node에 Broadcast한다.
(5) 각 Node들은 Broadcast된 여러 Block들에 대해서 Transactions이 Valid한지, 이미 지불되지 않았는지를 확인한다.
(6) 각 Node들은 다음 Block을 생성할 때에 해당 Block의 Hash값을 사용하는 것으로 Acceptance를 표현한다.

앞에서도 서술하였지만, Node는 가장 Longest Chain을 옳다고 여기며, 해당 Chain을 연장한다. 만약 2개 이상의 Node가 다른 버전의 Next Block을 Broadcast해온다면, 연결된 P2P Network 상에서 어떤 Node는 특정 Block을, 어떤 Node에서는 다른 Block을 먼저 받을 수 있다. 이럴 때에는, 먼저 도착한 Block에 대해서 Work하되, 다른 Block이 도착한다면 이를 다른 Branch에 저장한다(길어질 수도 있기 때문에). 이는 다음 PoW가 발견되어 어느 한 Branch가 다른 Branch들에 비해 길어짐과 동시에 tie가 깨지게 되며, Main Chain이 된다.

새로운 Transaction이 모든 Node에 꼭 도달할 필요는 없다. 또한, Block Broadcast 또한 drop-tolerant하다. Block을 받지 못했다면, Next block을 받을 때 Drop되었음을 알아차려 request할 수 있다.

IV. Incentive: First Transaction & Transaction Fees

(1) 관례적으로 Block의 첫 Transaction은 Block의 Creator가 소유한 새로운 Coin을 시작하는 Special한 Transaction이다. 이는 Network를 support하기 위한 것으로 해당 Node를 위한 Incentive를 쥐어주는 Transaction이다. (채굴)
이때, 인플레이션을 방지하기 위해 시간이 감에 따라 축소되도록 설계함.
(2) Transaction Fees(거래 수수료)는 Transaction Total Input Value > Total Output Value일 때 그 Difference이다. 이는 Block의 Incentive에 포함되어 계산된다.

이러한 Incentive는 Node로 하여금 Honest하게 행동하도록 유도한다. 만약 공격자가 Node의 다른 User보다 강력한 CPU power를 사용할 수 있게 된다면, 공격자는 자기 payments를 강탈해 돌려받거나, 새로운 coin을 발행하여 사람들을 속일 수 있을 것이다. 이러한 인센티브는 위의 두 행동 대신 룰을 따라 거래할 때 더 profitable하게끔 한다. 다시 말해, 다른 사람이 결합된 coin을 다루는 것보다 새로운 coin을 마구 찍어내는 것이 많은 $으로 직결되게끔 한다.

V. Merkle Tree: Reclaiming Disk Space

Coin의 가장 최근 Transaction이 수많은 Block 속에 묻혔다면, 이미 소비된 일부 transaction을 폐기할 수 있다. 그러나, block의 hash를 망가뜨리지 않게 하기 위해, Merkle Tree라는 구조를 도입한다. 새로운 Block의 Hash에 2개의 Transaction Node가 가리키는 Root가 포함되어 있고, 오래된 blocks에서는 Branch를 잘라내어 전체 Tree를 간소화할 수 있다. 

Fig . Merkle Tree

이러한 Longest Chain에서 우리는 Transaction 각각에 대해서 직접 Check는 불가능하지만, Chain 안의 Place에 Link함으로써 Network Node가 이 Transaction을 받아들였으며, 뒤이어 추가도니 Block 또한 Network가 해당 Transaction을 받아들였음을 증명하는(Payment Verification) 격이 된다.

Fig . Simplified Payment Verification

그러나, 만약 Attacker가 Network에 대해 overpower를 지속하여 위조된 transaction을 악용하게 된다면 어떠할까? 이는 Invalid한 Block을 탐지하여 경고를 주어 전체 Block과 경고된 Transaction을 다운로드하는 것을 중단하고 inconsistency를 확인하는 방법을 통해 해결할 수 있다.

VI. Combining & Splitting Value

Value의 Split과 Combination의 원활함을 위해, Transaction은 Multiple Input과 Output을 가진다.

Fig . Transaction (Multiple I/O)

VII. Privacy

매 Transaction마다 새로운 Key Pair들이 사용되어야 한다. 그러나, Multi-I/O Transaction에서 몇 개의 Input이 Same Owner에 의해 Owned되었음을 밝혀야 할 수도 있기에, 일부 Linking은 피할 수 없다. 만약 Key의 Owner가 공개된다면, 다른 Transaction들 또한 그 Owner의 소유임이 드러나게 된다.