[논문리뷰] Bitcoin: A Peer-to-Peer Electronic Cash System

29 Jul 2020 . category: Journal . Comments
#bitcoin #blockchain #cyptocurrency

Author

Satoshi Nakamoto (Unknown)

in www.bitcoin.org

Original Link: Where did I find
Archived Link: Download in Google Drive

필자리뷰

거대한 역사가 시작한 위대한 논문이다. 이 9쪽밖에 안되는 논문이 2020년 기준 약 3.57조 원 규모의 시장(3 billion dollars)을 만들었다고 할 수 있다. 2009년과 비교해서 많은 발전이 있어왔고 많은 변형과 아종(Alt-coins)들이 생겼다. Bitcoin에 담겨있는 핵심 기술이 아니라 사토시 나카모토가 어떤 연유에서 이런 생각과 아이디어를 할 수 있었는지, 그런 발상. 비전을 본 논문에서 찾는 것이 큰 의미가 있을 것이라 생각한다.

Introduction

현행의 전자 결제 시스템은 신뢰 기반 모델에 기초¹해있으므로 근본적으로 취약점이 존재한다. 또한, 완전 Non-reversible transaction²이 불가능하다. Reversal이 가능하게 하기 위해서 신뢰할만한 Spreads가 필요하다.

필요한 것은 신뢰대신에 암호학적 증명을 기반으로한 전자 화폐이다. 그러니깐 제 3자의 개입(은행이나 어떤 공식기관) 없이 송신자 / 수신자가 직접 거래할 수 있는 그런 것이다. 결제시스템이 계산적으로 Non-Reversible 하면, 판매자로 하여금 사기(안 보냈는데 보냈다고 하는)를 방지할 수 있고 구매자를 보호하기 위한 에스크로 서비스(전자 결제)를 구현하는데 필요한 Routine을 쉽게할 것이다.

본 논문은 이중 지불 문제(Double Spending Problem)³를 Peer-to-Peer 분산 타임스탬프 서버가 Transaction의 시간적 순서를 이용한 계산적 증명을 이용해서 해결하는 방법을 제시하는 것에 목적이 있다. 본 시스템은 신뢰할만한 Node의 CPU 파워가 Attacker node의 CPU 파워보다 더 클 때는 안전하다.

Transaction

Electronic coin이란 디지털 서명의 Chain이다. 각각의 코인 소유자는 코인의 마지막에 이전 Transaction에 대한 디지털 서명과 Public key를 적어서(추가해서) 다음 소유자에게 넘긴다. 수령인은 서명을 Ownership의 Chain에 의해 검증할 수 있다. (8장에서 재설명)

이 과정의 문제점은 수령인이 코인 소유자 중의 한명이 이중 지불³을 했는지 안했는지에 대한 검증을 할 수 없다는 것이다. 일반적인 해결책으로 매 Transaction을 조폐국과 같은 Mint(중앙시스템)에서 해결해주는 것이 있는데 이것은 일반적인 은행이랑 다를게 없다. 그리고 이 방식은 전적으로 어떤 Mint 회사에 종속되어 있는 것이므로 화폐 시스템 자체에 대한 신뢰성 문제가 존재한다. (예를 들어서, 어떤 회사가 잘 하고 있다가 악의적인 마음을 품거나 그렇다면?)

그러므로 수령자가 이 돈이 이전에는 한번도 결제되지 않았다(이중결제되지 않았다.)는 것을 알아차릴 수 있는 방법이 필요하다. 그 방법으로, 시간적으로 먼저 결제된 것만 count하고, 그 뒤에 결제된 것은 신경쓰지 않기로 하였다. Mint(중앙시스템) 기반 시스템에서, 중앙시스템은 모든 거래를 알고 어떤 요청이 먼저인지를 알고있다. 이 방법을 수행하기 위해서, 거래자체가 public하게 공개되어야하며, 하나의 History에 어떤 요청을 받았는지를 기록하기로 모든 참여자가 동의해야한다. 그리고 수령자가 매 Transaction 마다 대다수의 Nodes가 처음 이 요청을 받았음에 동의해야 한다. 그러므로, 신뢰할만한 node의 CPU 파워가 Attacker Node의 CPU파워보다 커야한다.

Timestamp Server

위에서 제안한 방법은 Timestamp server를 만드는 것에서 시작한다. Timestamp Server는 타임스탬프가 찍힌 아이템들의 블록들의 해시들을 받고, Newspaper나 Usenet Post 같은 곳에 공개함으로써 작동한다. Timestamp가 해시에 들어가기 위해서 명백히 그 시간대에 존재한다는 사실을 증명한다. 각각의 Timestamp는 해시에 있는 이전 Timestamp를 포함하며, 체인을 이룸으로써 이전의 Timestamp가 반드시 존재해야함을 강제한다. 이전 Timestamp을 기입하고 지금 Timestamp를 기록해서 동일 History(Database)를 쓰겠다는 의미.

Proof of Work

Peer-to-Peer 기반의 분산 Timestamp server를 구현하기 위해서, Proof-of-Work 시스템을 사용할 것이다. (Newspaper나 Usenet Post에 공지하는 것이 아니라.) Proof-of-Work 는 SHA-256 같은 해시알고리즘을 사용한 결과가 0비트 여러개로 시작하는 특정 값을 찾는 작업을 포함한다. 뭔 소리지? 보통 요구되는 작업은 0비트의 개수에 따라 지수적으로 달라지며, 해시연산을 한번만 하면 verify 할 수 있다.

Timestamp Network 에서 블록의 해시에 필요한 0비트를 주는 값이 발견될 때까지 블록 안에 Nonce를 증분하는 것으로 Proof-of-Work를 구현하였다. 위 사진 처럼, CPU가 한번 Proof-of-Work를 충족하는데 사용됐다면, 이 작업들을 다시 하지 않는 이상 변경될 수 없다. 예를 들어서, 100번째 블록을 변경하고 싶다면 1~99번 블록을 모두 다시 연산해야할 것이다.

Proof-of-Work는 다수결의 대표를 결정하는 문제를 해결할 수도 있다. 만약에 하나의 IP당 하나의 투표를 할 수 있다면, IP를 많이 할당받은 사람이 전체를 장악할 것이다. 그래서 Proof-of-Work는 필수적으로 CPU 당 1 투표가 되어야한다. Majority Decision은 가장 긴 체인으로 표현된다. 왜냐하면, 가장 긴 체인이 가장 Proof-of-Work에 기여를 많이 했을 것이기 때문이다. 만약, 다수의 CPU 파워가 가장 정직한 노드들에 의해 통제된다면, 가장 정직한 체인은 가장 빠르게 성장할 것이고 이는 다른 체인들을 압도할 것이다. 지난 블록을 수정하려면, 공격자는 현재와 그 이전의 모든 블록들에 대해서 Proof-of-Work 작업을 다시 해야하고 심지어 그 속도를 능가하여 가장 정직한 노드보다 빨라야할 것이다.

하드웨어 속도와 변화하는 Interest에 보상하기 위해서 Proof-of-Work 난이도는 시간당 평균 블록 수의 평균 목표치를 향해서 조정될 것이다. 너무 빠르게 만들어지면 난이도가 올라갈 것이다.

Network

1. 새로운 Transaction 들은 모든 노드들에 Broadcast 되어야한다.
2. 각각의 노드들은 새로운 Transaction들을 블록에 담아야한다.
3. 각각의 노드들은 그 블록의 작업 난이도를 찾는 작업을 해야한다.
4. 만약, 어떤 노드가 Proof-of-Work를 찾았다면, 모든 노드들에게 이 사실을 알려야한다.
5. 오직, 블록에 있는 모든 Transaction 들이 유효하고, 아직 지불(Spent)되지 않았다면 노드들은 블록을 받아들여야한다.
6. 노드들은 이전 블록으로서 체인에 Accept 된 블록의 해시값을 사용하여 다음 블록을 만드는 것으로서 블록을 받아들였음을 표현해야한다.

노드들은 항상 제일 긴 체인을 고려하고 그것을 더 늘리려고 노력해야한다. 만약에 두 노드가 서로 다른 버전의 다음 블록을 동시에 만들어 발표했다면, 몇몇 노드들은 하나를 먼저 수신할 것이다. 이 경우에는 먼저 받은 것에 작업하고, 다른 가지가 더 길어질 것을 생각해서 저장해놓는다. 분명히 다음 Proof-of-Work에서 어느 한 가지가 더 길어질 것이고, 작업 중인 Branch는 더 긴것으로 바뀔 것이다.

새로운 Transaction Broadcast 들은 모든 노드에 닿을 필요는 없다. 많은 노드에 도달할 수록, 길어지기전에 하나의 블록에 도달한다. 블록을 못 받을 경우, 다음 블록을 받을 때 하나가 빠졌다는 것 알아차리고 다시 요청할 것이기 때문에 메시지 누락에 대한 내성을 갖는다.

Incentive

관례상, 블록의 첫번째 거래는 블록을 만든 사람이 소유한 새로운 코인의 시작을 의미하는 특별한 거래이다. 이것은 네트워크를 지원하는 노드들에 대한 인센티브를 더해주며, 처음으로 발행된 코인이 순환하는 길을 제공한다. 새 코인들을 꾸준히 추가하는 것은 금을 채굴하는 사람이 더 많을 금을 채굴하기 위해서 자원을 추가하는 것과 유사하다. 우리 경우에서는 CPU 파워랑 전기이다.

인센티브는 거래 수수료로 지불될 수 있다. 만약 거래의 출력값이 입력값보다 적다면, 그 차이는 거래를 포함하는 블록 가치에 더해질 수수료이다. 일단 미리 정해진 숫자의 코인이 유통되기 시작하면, 인센티브는 전적으로 수수료로 바뀌고 인플레이션에 대해서 자유로워진다.

그리고 인센티브는 노드들이 정직하게 행동하도록 장려한다. 만약에 탐욕스러운 공격자가 모든 정직한 노드들보다 CPU 파워가 더 높을 수 있다고 치면, 결제를 훔쳐서 사람들을 속이는데 사용하거나 새로운 코인을 발행하는데 사용하는 2가지 선택지가 주어진다. 그는 룰에 따르는게 더 이익이라고 생각할 것이다. 왜냐하면, 규칙은 시스템이나 자신의 부를 해치는 것보다 더 많은 새로운 화폐를 줄 것이기 때문이다. 어감이 이상하긴 한데, 암튼 시스템을 해치는 것보다 코인 많이 채굴하는게 더 이득이라는 뜻이다. 항상 이익을 따라가는 해커만 있는 것이 아니다. 재미로(?) 파괴하는 미친놈들도 많은데, 이 경우에 대해서는 어떻게 방어할 수 있을지 잘 모르겠다. 애초에 그럴 가능성이 없기 때문에 의미 없는 질문인걸까?

Reclaming Disk Space

일단 최근 거래가 충분한 블록들에 의해 묻혀졌다면, 사용된 거래는 Disk space를 구하기 위해서 삭제될 수 있다. 블록의 해시값을 해치지 않으면서 이 요구사항을 해결하기 위해서, 거래들은 Merkle Tree로 (루트 블록만 해시값에 포함되는) 해시될 것이다. 오래된 블록은 트리 구조의 Branch 들을 조금씩 뜯어냄으로써 압축될 수 있다. 내부 해시값들은 저장될 필요가 없다.

계산해보면 매 10분마다 블록이 생긴된다고 치고 계산해보면 1년에 4.2MB 정도씩 증가할 것이기 때문에 무어의 법칙상 문제될 것이 없을 것이라고 사토시는 판단했다.

Simplified Payment Verification

지불을 모든 네트워크 노드들을 돌리지 않고 검증하는 것은 가능하다. 유저는 가장 긴 Proof-of-Work 체인의 블록 헤더 사본을 가지고만 있으면 된다. (요청하면 많은 노드들에서 금방 준다.) 스스로 거래 자체를 검증할 순 없지만, 체인안의 특정 부분에 링크하고 Network 노드들이 승인했으면 다음 블록을 추가할 것이기 때문에 이걸로 검증가능하다. (네트워크에 물어본다는 의미같다.)

검증과정 자체는 정직한 노드들이 네트워크를 지배하고 있을 때 믿을 수 있다. 만약, 공격자가 네트워크에서 힘이 더 세다면 검증과정 자체는 더욱 취약점이다. 네트워크 노드가 자체 검증을 할 수 있지만, 간소화된 검증법은 공격자가 네트워크 점령을 할 수 있는 한 (CPU 파워가 세면) 속을 수 있다. 이걸 막을 수 있는 하나의 전략은 네트워크 노드들이 유효하지 않은 블록을 알아차리고 보낸 경고알림을 받아들이고 유저에게 모든 블록을 다운 받게 한 뒤에 불일치한 거래에 대해서 재확인을 알리는 것이다. (요약: 뭔가 잘못됐다고 생각되면 유저한테 알리고 재확인을 받자.)

Combining and Splitting Value

코인을 하나하나 다룰 수 있을지라도 모든 푼돈마다 분리된 Transaction을 만드는건 별로다. (Unwieldy, 통제하기 어렵다)

사진처럼 하나의 거래에 여러 입출금을 묶어놓으면 된다. 출금은 지불용 출금 하나와 송신자에게 보낼 거스름돈 출금 하나해서 많아도 2개면 된다.

Privacy

전통적인 은행 모델은 구성원과 신뢰할만한 제 3자들의 정보 접근을 일정 제한함으로써 일정 수준의 Privacy를 얻을 수 있다. 대중들은 누군가가 다른 사람에게 얼마를 보내는 것을 알 수 있지만, 거래랑 관련된 사람이 누구인지는 모를 수 있다. 이거는 주식거래소에서 시간이랑 수량을 알려주는 “Tape”를 알려주는 거랑 비슷한 수준(누가 샀는지는 모르듯이)의 정보 공개이다.

부가적인 방법으로 거래마다 새로운 키 쌍이 사용되어야 각 Transaction이 공통의 소유자에게 연결되지 않도록 할 수 있다. 몇몇의 연결은 여러 입력 Transaction으로 피할 수 있지만, 같은 소유자에게 나왔다는 사실을 드러내야한다. 만약 키의 소유자가 드러나면, 그 소유자의 다른 Transaction 도 드러날 위험이 있다.

Calculations

공격자가 정직한 체인보다 더 빨리 다른 체인을 만드는 시나리오를 고려해보자. 설령 이게 성공한다고 할지라도, 이상한데서 가치를 만들거나, 공격자가 소유한 적이 없는 돈을 갖게하는 것 같은 시스템 제멋대로의 변경은 없을 것이다. 노드들은 지불이라고 유효하지 않은 거래를 승인하지 않을 것이고 정직한 노드들은 그것이 포함된 블록은 받지 않을 것이다. 공격자는 그저 최근 거래에서 자기가 사용한 돈만 돌려받는 정도만 할 수 있을 것이다.

정직한 노드와 공격자의 체인의 대결은 Binomial Random Walk 로 특징지어질 수 있다. 성공한 이벤트는 정직한 체인이 한 블록을 늘리고 lead(선두, 우세)를 1 올리는 것이다. 실패한 이벤트는 공격자의 체인이 한 블록 늘어나고 gap을 -1 좁히는 것이다.

공격자가 주어진 결손(Deficit)을 따라잡을 확률은 Gambler Ruin Problem 과 유사하다. 도박꾼이 무제한 카드로 본전에 도달하기 위해서 무한한 횟수의 시도를 한다고 쳐보자. 우리는 그가 본전에 도달할 확률, 정직한 체인을 따라잡을 확률을 계산할 수 있다.

\(p =\) 정직한 노드가 다음 블록을 찾을 확률

\(q =\) 공격자가 다음 블록을 찾을 확률

\(q_z =\) 공격자가 Z 블록 뒤에서부터 따라잡을 확률

\(q_z = \begin{Bmatrix}1 & if \quad p \leq q \\ (q/p)^z & if \quad p>q\end{Bmatrix}\)

\(p > q\)라고 해보자. 공격자가 따라잡아야하는 블록 수가 많을 수록 확률은 기하급수적으로 감소한다. 확률상 초반에 엄청 운이 좋지 않았다면, 가능성은 거의 없어질 정도로 사라질 것이다.

새로운 거래의 수취인이 확실히 발신자가 거래를 바꿀 수 없는게 확실해질 때까지 얼마나 기다려야하는지 생각해보자. 발신자가 공격자라고 가정하자. 현재 공격자는 수취인이 공격자가 돈을 지불했다고 잠시동안 믿고싶도록 하고 싶다고 하자. 잠시가 지나면 다시 돈을 돌려받을 것이다. 받는 사람은 이 일이 일어남과 동시에 경고를 받겠지만 보낸 사람은 이 사실이 늦길 바라고 있다.

받는 사람은 새로운 키쌍을 만들고 서명 직전에 발신자에게 공개키를 줄 것이다. 이것은 발신자가 운좋게 충분히 앞설 때까지 계속 작업을 수행함으로써 미리 블록들의 체인을 준비하지 못하게 한다. 거래가 한번 보내지면, 정직하지 않은 발신자는 몰래 거래를 대체할 다른 버전의 평행한 체인을 만들기 시작할 것이다.

수취인은 블록에 거래가 추가되고 \(z\) 블록이 연결될 때까지 기다린다. 그는 공격자가 얼마나 진척이 있었는지는 모른다. 정직한 블록이 블록당 평균 예상 시간을 따른다고 가정하면, 공격자의 잠재적 진척도는 기대값을 갖는 푸아송(Poisson) 분포가 될 것이다.

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

현재 공격자가 따라잡을 수 있는 확률을 계산하기 위해서 해당 시점부터 따라잡을 수 있는 확률로 만들어낼 각 진척 규모별 푸아송 밀도를 곱한다.

\[ \sum_{k=0}^{\infty} \frac{\lambda^k e^{-k}}{1} \cdot \begin{Bmatrix}(q/p)^{(z-k)} & if \quad k \leq z \\ 1 & if \quad k>z\end{Bmatrix} \]

분포의 무한 꼬리 합(the infinite tail of the distribution)을 피하기 위해 정렬하면,

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

그리고 C언어로 계산하여 기하급수적으로 감소함을 밝혔다. (생략)

Conclusion

본고에서 신뢰에 기반을 두지 않은 전자 거래 시스템을 제안하였다. 우리는 디지털 서명으로 만들어진 코인들의 일반적인 프레임워크에서 시작했는데, 소유권에 대한 강한 제어를 제공한다. 그러나 이중 지불 문제를 예방하지 않는다면 불완전한 기술이다. 그래서 본고에서 Proof-of-Work라는 공개된 히스토리(장부)에 기록하는 방식의 Peer-to-Peer 네트워크를 제안하였다. 이것은 만약에 정직한 노드들이 CPU 자원의 대부분을 가지고 있다면 공격자는 계산적으로 공격이 불가능하다. 네트워크의 견고함은 통일성이 없는 단순함에서 비롯된다. 노드들은 거의 Coordination 없이 한번에 작동된다. 노드들은 식별될 필요가 없다. 왜냐하면 어느 특정 장소로 메시지를 전달하는 것이 아니라 그냥 최선만 다하면 되기 때문이다. 노드들은 자유의지를 가지고 네트워크를 떠나거나 재가입이 가능하고 그냥 없었던 동안 Proof-of-Work 체인이 어떻게 흘러갔는지 받아들이기만 하면 된다. 그들은 CPU 파워로 투표하고, 체인을 확장시키거나 무효한 블록들을 거절함으로써 그들의 (블록에 대한) 승낙여부를 표현할 수 있다. 어떤 필요한 규칙이나 인센티브들은 이 합의 메커니즘에 의해 강화될 수 있다.

---

---