[블록체인] Bitcoin 백서 정리 #2 - 메커니즘

https://godd.tistory.com/92

[블록체인] Bitcoin 백서 정리 #1 - 도입부

지난 포스팅에는 비트코인에 대한 간략한 소개와 나오게 된 배경에 대한 서론쪽을 정리해보았다.

이어서 비트코인을 사용하기 위한 메커니즘들에 대해서 정리해본다.

 

Transaction

We define an electronic coin as a chain of digital signatures. Each owner transfers the coin to the next by digitally signing a hash of the previous transaction and the public key of the next owner and adding these to the end of the coin. A payee can verify the signatures to verify the chain of ownership

전자 화폐를 전자서명의 체인으로 정의한다. 각 Owner는 이전 Transaction와 다음 Owner의 Public Key에 대한 Hash에 전자서명을 한 것을 추가하여 코인을 전달한다. 수취인은 소유권의 체인을 검증하기 위해서는 전자서명을 검증할 수 있다. 

 

수취인의 Public Key와 이전 거래의 Hash를 하고 그 값에 발행인의 Private Key로 서명함으로써 체인을 형성한 것을 전자화폐로 정의한다. 즉, 전자상의 거래를 정의하기 위해 필요한 요소는 수취인 정보, 이전 거래 정보, 여기에 발행인의 전자서명으로 이뤄지는 것이다. 여기서 사용되는 공개 키 방식은 타원곡선암호 알고리즘 쓰는데 여기 길이 제한이 있어서 Hash 값으로 사용한다.

The problem of course is the payee can't verify that one of the owners did not double-spend the coin. A common solution is to introduce a trusted central authority, or mint, that checks every transaction for double spending. After each transaction, the coin must be returned to the mint to issue a new coin, and only coins issued directly from the mint are trusted not to be double-spent. The problem with this solution is that the fate of the entire money system depends on the company running the mint, with every transaction having to go through them, just like a bank. 

이렇게 정의한 전자 화폐의 문제점은 소유자들중 한명이 이중 지불을 했는지 검증할 수 없는 것이다. 이중 지불을 안했다는 신뢰성이 있어야 하는데 보통은 신뢰 기관인 조폐국 (mint) 이 모든 거래들을 체크하도록 하는 방식을 도입한다. 거래가 완료된 코인은 회수 되었다가 직접 새로 코인을 발행함으로써 이중 지불이 되지 않은 코인임을 신뢰할 수 있다. 하지만 은행처럼 전체 통화 시스템의 운명이 결국 조폐국을 운영하는 회사에 의존적이라는 것이다. 

 

결국, 이중 지불을 검증하기 위한 기존의 전자 화폐 시스템의 큰 문제는 제 3자에 의해 운명이 결정된다는 것이다.

 

We need a way for the payee to know that the previous owners did not sign any earlier transactions. For our purposes, the earliest transaction is the one that counts, so we don't care about later attempts to double-spend. The only way to confirm the absence of a transaction is to be aware of all transactions. In the mint based model, the mint was aware of all transactions and decided which arrived first.

수취인은 이전 소유자들이 이전 거래에서 서명하지 않았다는 걸 알 수 있는 방법이 필요하다. 여기서는 가장 최초의 거래만이 중요하며, 나중에 이중 지불을 하려는 시도들은 신경쓰지 않는다는 것이다. 거래의 부재를 확인하기 위한 유일한 방법은 모든 거래들을 확인하는 방법이다. 조폐국 기반의 모델에서는 모든 거래들을 확인하여 먼저 도착한 거래인지 결정한다. 

 

To accomplish this without a trusted party, transactions must be publicly announced [1], and we need a system for participants to agree on a single history of the order in which they were received. The payee needs proof that at the time of each transaction, the majority of nodes agreed it was the first received.

제 3자 없이 이중 지불을 확인하려면, 거래들은 공개적으로 알려져야 하며 참가자들이 거래 순서의 단일 기록을 동의할 수 있는 시스템이 필요하다. 수취인은 각각 그 시간의 거래들에 대해 대다수의 노드들이 첫번째 지불이라는 것을 동의하는 증명이 필요하다. 

 

데이터의 무결성, 신뢰성을 입증하기 위해서는 두가지 방법이 있다.

 1. 중앙에서 데이터를 접근 못하게 관리하여 신뢰성을 유지하는 방법

 2. 전체 공개해서 누구나 볼 수 있게 하여 신뢰성을 유지하는 방법

 

이 논문에선 2번의 방법을 택하며 결국 P2P 기반으로 모든 거래들을 참여자들에게 공개적으로 알림으로써 이중 지불에 대한 신뢰성을 해결할 수 있다. B-money라는 Wei Dai 가 만든 초기 암호화폐로부터 인용 됐으며 이 Wei Dai 가 사토시 나가모토 라고 추측하기도 한다.

 

하지만, P2P 기반은 거래가 다른 노드로 Broadcast 되고 동기화 시간 등으로 인해 어떤 거래가 먼저 일어났는지 판단하기 힘들다. 그 시간에 대한 증명을 위해 Timestamp Server가 필요하며 대신 이 때 퍼지는 거래 기록의 순서들이 단일 기록이라는 걸 보장하기 위해 합의 알고리즘이 필요한데 그것이 작업 증명이고 과반수 이상의 노드가 합의하는 Longest Chain만이 단일 기록이라고 볼 수 있다.

 

 

Timestamp Server

The solution we propose begins with a timestamp server. A timestamp server works by taking a hash of a block of items to be timestamped and widely publishing the hash, such as in a newspaper or Usenet post [2-5].

위 문제의 솔루션은 Timestamp Server로 시작한다. Timestamp Server는 Timestamp 할 거래들의 블록에 대한 해시를 계산하여 신문이나 Usenet처럼 공표하는 방식이다. 

 

 

The timestamp proves that the data must have existed at the time, obviously, in order to get into the hash. Each timestamp includes the previous timestamp in its hash, forming a chain, with each additional timestamp reinforcing the ones before it.

Timestamp는 해시로 계산되기 위해 명백하게 그 시점에 데이터가 존재했음을 증명한다. 각 Timestamp는 이전 Timestamp를 포함한 해시들의 체인들을 형성하여 증명을 강화시킬 수 있다.

 

이중 지불을 막기 위해서는 최초의 거래만 받아들이며 이 거래가 이중 지불이 아님을 증명해야 한다. 따라서, 시간순으로 모든 거래를 확인해야 하는데 이를 위해서 P2P 방식으로 Timestamp를 찍어 거래에 대한 순서를 공표 한다는 것이다. 그림은 이전 Hash와 현재 Block에 대한 Timestamp를 기록하여 이를 다시 Chain 형태로 위조를 할 수 없도록 강화한다는 내용이다.

만약 Timestamp나 Block의 Item을 조작하게 되면 Hash 값이 바뀔 것이고 다시 이 Hash를 바꾸려면 Chain의 모든 값들을 바꿔줘야 하므로 사실상의 조작이 불가능하다.

 

Proof-Of-Work

To implement a distributed timestamp server on a peer-to-peer basis, we will need to use a proofof-work system similar to Adam Back's Hashcash [6], rather than newspaper or Usenet posts. The proof-of-work involves scanning for a value that when hashed, such as with SHA-256, the hash begins with a number of zero bits. The average work required is exponential in the number of zero bits required and can be verified by executing a single hash.

P2P 기반의 분산 Timestamp Server를 구현하기 위해선 Adam Back의 Hashcash와 비슷한 PoW 시스템을 사용할 필요가 있다. PoW는 SHA-256 같은 방식으로 해시할 때 제로 비트로 시작되는 해시 값을 찾는 작업을 포함한다. 평균적인 작업은 제로 비트의 개수에 따라 지수적으로 증가하지만 한번의 수행으로 검증이 가능하다.

 

SHA-256 기준으로 256비트의 값이 나오고 16진수로 표현되면 64 Byte로 표시할 수 있다.

dongha는 해시로 "8209EDB0971093DCD5ED976E4B300CFC12E0F5947C34D31B767366CBC79C271D"인데, 제로 비트 해시 값이란 "0000C9BE8DB6E29D340963A0F301E633BE089CF932C2E43936F65B39BA2EAA2C" 과 같이 해시 앞의 값이 제로로 시작되는 값을 말한다. 

 

제로 개수에 따라 난이도가 어려워지는데 그 이유는 아래와 같다.

"0XXX..." -> 맨 앞은 0, 63개는 아무거나 : 전체 (64^16)개 중 (63^16)개 허용

"00XX..." -> 맨 앞의 2개는 0, 62개는 아무거나 : 전체 (64^16)개 중 (62^16) 개 허용

"000X..." -> 맨 앞의 3개는 0, 61개는 아무거나 : 전체 (64^16)개 중 (61^16) 개 허용

...

따라서 지수적으로 증가한다는 뜻은 앞의 제로 개수에 따라서 해시 값을 찾을 수 있는 확률 범위가 적어지므로 찾는데 시간이 더 많이 걸릴것이란 뜻이다.

For our timestamp network, we implement the proof-of-work by incrementing a nonce in the block until a value is found that gives the block's hash the required zero bits. Once the CPU effort has been expended to make it satisfy the proof-of-work, the block cannot be changed without redoing the work. As later blocks are chained after it, the work to change the block would include redoing all the blocks after it.

우리의 Timestamp 네트워크를 위해 우리는 필요한 제로 비트를 포함한 Block의 해시 값을 찾을 때 까지 Block의 nonce를 증가시킴으로써 PoW 를 구현한다. 일단 CPU 연산으로 PoW를 만족시켰다면, Block은 이 작업을 다시 하지 않고는 변경할 수 없다. 그 이후 Block들이 체인으로 연결되기 때문에, 그 Block의 작업 변경은 그 후의 모든 Block들을 다시 해야 할 것이다.

 

위 그림에서 빨간 표시 된 부분은 Block을 생성할 때 고정 값인 거래 (Tx) 들과 이전 Block의 해시 값이다. 거래들과 이전 해시를 포함하여 해시를 만들면, 항상 같은 값이 나올텐데 여기에 Nonce 값을 증가시켜가면서 제로로 시작하는 해시 값을 찾는 과정인 것이다. 이 과정을 작업증명 (PoW) 라고 하고 이 해시값을 가장 먼저 찾아낸 노드만이 Block을 생성하게 된 것이다.

 

The proof-of-work also solves the problem of determining representation in majority decision making. If the majority were based on one-IP-address-one-vote, it could be subverted by anyone able to allocate many IPs. Proof-of-work is essentially one-CPU-one-vote. The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it.

작업 증명은 다수결 의사결정에 있어서 투표자 선정 문제도 해결해 준다. 과반수가 한 IP당 한표 방식으로 결정된다면 많은 IP를 할당받는 것이 가능한 사람에게 공격받을 수 있다. 작업증명은 한 CPU당 한 표 방식이다. 다수결의 결정은 가장 긴 체인으로 나타내지며 작업 증명을 위한 가장 많은 노력이 들어간 체인이다.

 

If a majority of CPU power is controlled by honest nodes, the honest chain will grow the fastest and outpace any competing chains. To modify a past block, an attacker would have to redo the proof-of-work of the block and all blocks after it and then catch up with and surpass the work of the honest nodes. We will show later that the probability of a slower attacker catching up diminishes exponentially as subsequent blocks are added.

만약 과반수의 컴퓨팅 파워가 정직한 노드들로 통제된다면, 정직한 체인이 가장 빠르게 길어져 다른 경쟁 체인들을 앞서게 될 것이다. 지난 Block을 수정하기 위해 Attacker들은 Block의 작업 증명을 다시 해야 할 것이고 또 정직한 노드들의 작업을 추월하고 따라잡아야 한다. 우리는 더 느린 Attacker들이 따라잡을 확률은 Block이 추가됨에 따라 지수적으로 감소함을 보여줄 것이다.

 

작업 증명은 결국 CPU를 많이 돌리는 노력이 들어가야 하고 이런 정직한 노드들로만 통제될 경우 Block을 수정하려고 해도 가장 긴 체인이 될 확률은 사실상 낮다는 뜻이다. 저자는 과반수 이상을 통제하는 Attacker가 될 경우도 결국 Block을 수정하기 보다는 Incentive를 얻기 위해 노력하는게 경제적으로 이득이라고 말한다.

 

To compensate for increasing hardware speed and varying interest in running nodes over time, the proof-of-work difficulty is determined by a moving average targeting an average number of blocks per hour. If they're generated too fast, the difficulty increases.

시간이 흘러 하드웨어의 속도 증가나 노드 운영에 대한 관심의 변화를 보정하기 위해서 작업 증명의 난이도는 정해진 시간 당 평균 Block 수를 목표로 하는 이동 평균 (moving average) 에 의해 결정 될 것이다. 너무 빨리 생성된다면 난이도는 증가하게 된다.

 

현재 비트코인에서는 평균 10분에 하나씩 Block이 생성된다고 알려져 있는데, 예를 들면 작업 난이도나 채굴 속도에 따라 5분만에 목표 해시 값을 찾았을 경우 난이도를 높여서 더 오랜 시간에 걸쳐 작업 증명을 할 수 있도록 조정한다는 뜻이다. 

 

작업 증명은 결국 해시 값을 구하는 과정인데 신규 Block을 기존의 체인에 추가하는 작업을 완료했음을 증명하고 싶은 것으로 불특정 노드들의 작업을 믿지 못하기 때문에 시스템 규칙에 따라 작업을 한 내용을 통해 생성 된 Block만을 체인에 추가하겠다는 의미로 보인다. 

또한, 아무나 Block 을 마구 생성해서 Longest Chain을 만드는 것을 막는 용도로도 사용된다.

Network

The steps to run the network are as follows:
1) New transactions are broadcast to all nodes.
2) Each node collects new transactions into a block.
3) Each node works on finding a difficult proof-of-work for its block.
4) When a node finds a proof-of-work, it broadcasts the block to all nodes.
5) Nodes accept the block only if all transactions in it are valid and not already spent.
6) Nodes express their acceptance of the block by working on creating the next block in the chain, using the hash of the accepted block as the previous hash.

네트워크를 실행하는 단계들은 다음과 같다.

 1) 새로운 거래들이 모든 노드들로 Broadcast 된다.

 2) 각 노드는 새로운 거래들을 Block으로 수집한다.

 3) 각 노드는 그 Block에 대한 어려운 PoW를 수행한다.

 4) 한 노드가 PoW를 찾아낼 때, 모든 노드들로 Block을 Broadcast 한다.

 5) 노드들은 모든 거래들이 유효하고 소비되지 않았다면 그 Block을 승인한다.

 6) 노드들은 이전 해시에 해당 Block을 Chain으로 만듦으로써 Block의 승인을 표현한다. 

 

6번 단계는 위 Timestamp Server의 해시 Chain을 뜻하며 사실상의 조작을 불가능하게 해준다. 하지만, 여기서의 문제는 P2P이므로 Block의 도착이 노드마다 다를 수 있어 PoW를 찾아낸 Block Chain이 여러개가 발생할 수 있다는 점이다.

 

아래 그림으로 어떤 경우인지 확인해보자.

 

P2P 환경이므로 노드들은 연결된 노드들에만 Broadcast를 할 것이고 순서를 보자.

1. 2번 노드에서 PoW를 찾아 Timestamp를 찍어 Block을 생성한다.

2. Block을 Broadcast. 여기서는 연결된 3번 노드에 Block을 알리고 1번 노드로 Block을 보내줄 것임을 기대한다.

3. 3번 노드에 새로운 Block이 오기 전 99번 노드에서는 다른 시간대의 PoW를 찾아 Block을 생성한다.

4. 생성된 Block을 Broadcast. 여기서는 연결된 1번 노드에 알리고 연결된 다른 노드로 보내줄 것임을 기대한다.

5. 그 사이 3번 노드에 Block이 도착하고 Chain을 함으로써 승인한다.

6. 그 후 3번 노드에서 Block을 1번 노드로 알리기 전 1번 노드는 다른 버전의 Block을 받아 Chain을 형성한다.

 

이렇게 될 경우 여러 Branch의 Chain이 발생할 수 있어 단일 기록으로 알 수가 없는 것이다.

 

Nodes always consider the longest chain to be the correct one and will keep working on extending it. If two nodes broadcast different versions of the next block simultaneously, some nodes may receive one or the other first. In that case, they work on the first one they received, but save the other branch in case it becomes longer. The tie will be broken when the next proofof-work is found and one branch becomes longer; the nodes that were working on the other branch will then switch to the longer one.

노드들은 항상 가장 긴 체인을 올바른것으로 간주하고 그 체인을 확장하도록 유지할 것이다. 만약 두 노드가 다른 버전의 다음 Block을 동시에 Broadcast 했다면 어떤 노드들은 서로 다른 블록을 먼저 받게 될 지도 모른다. 이 상황에선, 노드들은 그들이 첫번째로 받은 한 Block만 작업하지만 다른 Branch도 더 길어질 경우를 대비해 저장한다. Chain 길이의 Tie는 다음 PoW 발견 때 깨질 것이다. 그리고 한 Branch가 더 길어질 것이다. 다른 Branch 에서 작업하던 노드들은 더 긴 Branch로 전환 할 것이다.

 

Chain이 여러개 발생하더라도 결국 가장 긴 체인만을 유지하여 단일 기록으로 유지할 것이므로 여러 Branch에 대한 문제점은 해결될 수 있다는 것이다.

 

New transaction broadcasts do not necessarily need to reach all nodes. As long as they reach many nodes, they will get into a block before long. Block broadcasts are also tolerant of dropped messages. If a node does not receive a block, it will request it when it receives the next block and realizes it missed one.

새로운 거래는 모든 노드들에게 도달할 필요가 없다. 많은 노드들에게 도착하기만 한다면 그 노드들은 머지 않아 Block을 받아들일 것이다. 노드에서 Block을 받지 못했다 해도 다음 Block을 받았을 때 유실한 Block을 발견해서 바로 다시 요청하게 될 것이다. 

 

 

다음 포스팅에서는 그 외 P2P 암호화폐를 지속적으로 유통시키기 위한 기타 정책 및 방법에 대해서 알아보겠다.

 

Reference

https://www.bitcoin.com/get-started/bitcoin-white-paper-beginner-guide/

https://en.wikipedia.org/wiki/Hashcash

http://wiki.hash.kr/index.php/%EB%B9%84%EB%A8%B8%EB%8B%88