비트코인 최초의 논문; 사토시 나카모토의 P2P 전자화폐 시스템; Bitcoin: A P2P Electronic Cash System - 2부

phuzion7 (62)in #coinkorea • 6 years ago (edited)

@heroldius' Mondrian.jpeg
@sndbox 님의 Bitcoin Logo Art Challenge 우승작 작가: @heroldius

안녕하세요^^ 퓨전7입니다 오늘은 사토시 나카모토의 비트코인 논문 - 2부입니다 이 짧은 논문을 번역하면서 암호화폐를 좋아하지만 이론적인 부분은 역시 진입장벽이 높다는 것을 느꼈습니다 특히 공격자가 정직한 노드들을 따라잡을 확률을 계산하는 수학적인 부분은 간신히 결과가 그렇구나.. 정도만 이해가 가능했습니다 좀 더 좋은 번역을 위해서 이론에 관한 많은 글들을 보아야 했습니다 그러나 원문의 느낌을 그대로 살리기 위해서 용어 설명이나 해설을 추가하지 않았습니다 이론적인 부분은 앞으로 ฿코인 스토리 콘텐츠에서 다룰 수 있습니다 그럼 2부를 시작합니다 감사합니다~ 1부는 여기로

2부
7. 디스크 공간 개선
8. 간소화된 결제 확인
9. 가치 분할과 병합
10. 프라이버시
11. 계산
12. 결론

Bitcoin: A Peer-to-Peer Electronic Cash System

Satoshi Nakamoto
번역: @phuzion7
www.bitcoin.org
2008.10.31

7. 디스크 공간 개선^{Reclaiming Disk Space}

일단 하나의 코인에서 마지막 트랜잭션이 충분히 채워진 블록들 아래에 기록되면, 그 이전의 사용된 거래들은 디스크 공간 절약을 위해서 폐기될 수 있다 이것을 블록 해시를 깨지 않고 손쉽게 하기 위해서, 트랜잭션들은 블록 해시에 포함될 유일한 루트(Root Hash)인, 하나의 머클 트리(Merkle Tree)[7][2][5]로 해시된다 그럼 오래된 블록들은 트리의 분지를 뽑음으로써(stubbing off branches) 압축할 수 있다 내부의 해시들은 저장될 필요가 없어진다

Screen Shot 2018-06-14 at 7.14.42 PM .png

트랜잭션들을 포함하지 않는 하나의 블록 헤더(block header)는 약 80 바이트(byte)이다 만약 우리가 블록들이 10분마다 생성된다고 가정하면, 80 바이트 * 6 * 24 * 365 = 4.2MB(연간)이다 컴퓨터 시스템이 일반적으로 2008년 현재 2GB 램(RAM)으로 판매되는 것을 감안하고, 무어의 법칙(Moore’s Law)이 현재 성장률을 연간 1.2GB로 예측하면, 저장용량(storage)은 만일 블록 헤더가 반드시 메모리(memory)에 유지되야 한다고 하더라도 문제가 안될 것이다

8. 간소화된 결제 확인^{Simplified Payment Verification}

전체 네트워크 노드를 실행하지 않고서도 결제를 확인하는 것이 가능하다 사용자는 오직 가장 긴 작업 증명 체인의 블록 헤더 복사본(copy) 만 가지고 있으면 된다 이것은 그(사용자)가 가장 긴 체인이라고 확신이 들 때까지 네트워크 노드를 요청함으로써 가질 수 있다, 그러면 그 거래가 타임스탬프(timestamped) 된 블록과 연계(linking) 되는 머클 분지(Merkle branch)를 얻을 수 있다 그는 트랜잭션을 스스로 점검할 수는 없지만, 그것을 체인 안의 공간에 연계함으로써, 하나의 네트워크 노드가 그것을 수락하고, 그 뒤로 더 블록들이 추가되면서 네트워크가 그것을 수락했음을 확인할 수 있다

Screen Shot 2018-06-14 at 7.15.32 PM .png

따라서, 그 확인(verification)은 정직한 노드들이 네트워크를 제어하는 한 신뢰받지만, 공격자(attacker)가 네트워크를 장악한다면 손상되기 더 쉬워진다 네트워크 노드들은 스스로 트랜잭션을 확인할 수 있지만, 공격자가 계속해서 네트워크를 장악하는 동안은 공격자의 위조된 트랜잭션으로 이 간편한 수단은 조작될 수 있다 이것을 방지하기 위한 하나의 전략은 승인되지 않은 블록이 발견되면 네트워크 노드들로부터 경보(alerts)를 받는 것이다 사용자의 소프트웨어가 그 블록 전체와 경고를 받은 거래를 다운로드해서 불일치를 확인한다 빈번한 결제를 해야 하는 사업자들은 좀 더 독립적인 보안과 빠른 확인을 위해서 아마도 스스로의 노드를 운영할 필요가 있다

9. 가치 나누기와 합치기^{Combining and Splitting Value}

비록 코인들을 하나하나 처리하는 것은 가능할지라도, 전송할 때 전부 푼돈으로(for every cent) 트랜잭션을 분리하는 것은 어려울 것이다 가치를 나누고 합치기 위해서는, 트랜잭션은 다중 입력(inputs)과 출력(outputs)을 포함하게 된다 일반적으로 이전의 더 큰 트랜잭션으로부터 단일 입력 또는 더 작은 양을 결합한 복수의 입력이 있을 것이다, 그리고 최대 두 개의 출력에는: 결제를 위한 것 하나, 그리고 변경 사항(the change)을 돌려주기 위한 것 하나이다 어떤 경우든 보낸 사람에게 돌려보낸다

Screen Shot 2018-06-14 at 7.17.03 PM .png

팬-아웃(fan-out), 하나의 트랜잭션이 여러 개의 트랜잭션을 포함하고 그 트랜잭션들이 더 많은 것들로 나눠지는 것으로, 이는 여기서는 문제가 안된다는 것을 주목해야 한다 하나의 트랜잭션 역사에 대한 완전하게 독립적인 복사본을 추출할 필요가 전혀 없기 때문이다

10. Privacy

전통적인 은행업(banking) 모델은 관련된 당사자들과 신뢰받는 제3자의 정보에 접근하는 것을 제한함으로써 프라이버시의 수준을 달성했다 (비트코인의) 모든 거래를 공개적으로 발표해야 하는 필연성은 이 방법을 어렵게 하지만, 프라이버시는 다른 곳에서 정보의 흐름을 차단함으로써 여전히 유지할 수 있다: 공개키(public keys)를 익명으로 유지하는 것이다 사람들은 누군가 다른 사람에게 일정 량을 보내고 있는 것을 볼 수 있지만, 트랜잭션은 누구와도 연동된 정보가 없다 이것은 증권 거래소에서 발표하는 정보의 수준과 비슷한 것으로, 개별 거래들의 시간과 크기,“tape”, 가 공표되지만, 당사자들이 누군지는 언급하지 않는다

Screen Shot 2018-06-14 at 7.17.42 PM .png

추가적인 방화벽으로서, 트랜잭션이 일반 소유자와 연동되어 있지 않게 하기 위해서 각각의 트랜잭션에 새로운 키 쌍(new key pair)을 사용해야만 한다 일부 연동(linking)은 다중 입력(multi-input) 트랜잭션으로 여전히 피할 수 없으며, 필연적으로 그 입력(inputs)들이 같은 소유자의 것임이 드러난다 위험 요소는 만일 키의 소유자가 드러나면, 연동으로 같은 소유자에 속한 다른 트랜잭션들이 드러날 수 있다

11. Calculations

우리는 정직한 체인보다 더 빠른 대체 체인을 만들려고 시도하는 공격자의 시나리오를 고려한다 이것이 달성되더라도, 난데없이 가치를 창조하거나 원래 공격자의 것이 아닌 돈을 버는 것 같은 임의의 변경 사항들에 시스템을 열어두지는 않는다 노드들(nodes)은 유효하지 않은 트랜잭션을 결제로 인정하지 않을 것이며, 정직한 노드들은 이를 포함하는 블록을 수락하지 않을 것이다 공격자는 오직 그가 최근에 보낸 돈을 되돌리기 위해 자신의 트랜잭션 중에 하나를 변경하려고 시도할 수 있을 뿐이다

정직한 체인과 공격자 체인 사이의 레이스는 이항식 랜덤 워크(Binomial Random Walk)로 특징지을 수 있다 성공 사건(success event)은 정직한 체인이 블록 하나를 추가하는 것으로, 선두를 +1 증가시킨다, 그리고 실패 사건(failure event)은 공격자의 체인이 블록 하나를 추가한 것으로, 차이를 -1 감소시킨다

적자(deficit, 불리함)가 주어진 상황에서 공격자가 따라잡을 확률은 도박꾼의 파산(Gambler’s Ruin) 문제와 유사하다 무제한 신용(예금)을 가진 한 갬블러가 적자로 시작해서 손익 평형(breakeven)에 도달하기 위해서 무한 실행을 수행한다고 가정하자 우리는 그가 손익 평형에 도달할 가능성, 또는 공격자가 정직한 체인을 따라잡을 확률을 계산할 수 있다, [8]과 같다:

P = 정직한 노드가 다음 블록을 찾을 확률
q = 공격자가 다음 블록을 찾을 확률
qz = 공격자가 z 블록 뒤에서 따라잡을 확률

Screen Shot 2018-06-13 at 10.53.02 PM .png

p > q라는 우리의 가정을 감안할 때, 공격자가 따라잡아야 할 블록의 수가 증가함으로 확률은 기하급수적으로 낮아진다 이런 불리한 상황에서, 만약 그가 초반에 행운의 앞지름을 만들지 못한다면, 점점 뒤로 밀리면서 그의 승산은 거의 사라지게 될 것이다

이제 우리는 발송인이 그 트랜잭션을 변경하지 않았다는 것을 충분히 확인할 때까지 새로운 트랜잭션의 수취인이 얼마나 오래 기다려야 할 필요가 있는지 알아본다 발송인은 공격자(attacker)로서 수취인이 잠시 동안 그가 지불했다고 믿도록 만들고, 얼마의 시간이 지난 후에 이를 전환해서 자신에게 되돌려 받기를 원한다고 가정해보자 수취인은 이런 일이 발생하면 경보 메시지를 받겠지만, 발송인은 그것이 아주 늦기를 원할 것이다

수취인은 새로운 키 쌍(new key pair)을 생성하고 공개키(public key)를 서명하기 직전에 발송인에게 보낸다 이것은 그(공격자)가 운 좋게 충분히 앞지를 때까지 작업을 계속하고, 그때 트랜잭션을 실행함으로써 미리 일련의 블록체인을 준비하는 것을 예방한다 일단 트랜잭션이 전송되면, 부정직한 발송인은 그의 트랜잭션의 대체 버전을 포함하는 평행 체인(parallel chain)에 대한 작업을 몰래 시작한다

수신자는 트랜잭션이 블록에 추가되고 z 블록이 그 뒤에 연결될 때까지 기다린다 그는 공격자가 수행한 정확한 진행의 정도를 알지 못한다 그러나 정직한 블록에 블록당 평균 예상 시간이 걸린다고 가정하면, 공격자의 잠재적인 진행 상태는 예상 값을 가진 푸아송 분포(Poisson distribution)가 될 것이다:

Screen Shot 2018-06-14 at 3.26.48 PM .png

공격자가 따라잡을 수 있는 가능성을 얻기 위해서, 우리는 그가 따라잡을 수 있었던 확률의 그 시점으로부터 그가 수행했던 진행 양에 대해 푸아송 밀도(Poisson density)를 곱한다:

Screen Shot 2018-06-14 at 3.44.30 PM .png

분포상의 무한 소수를 계산하지 않기 위해 정리하면...

Screen Shot 2018-06-14 at 3.56.48 PM .png

C code로 변환하면...

#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

12. 결론

우리는 신뢰 기관에 의지하지 않는 전자 거래 시스템(system for electronic transactions)을 제안했다 우리는 디지털 서명으로 만들어진 코인의 일반적인 프레임워크(framework)로 시작했으며, 이것은 소유권에 대한 강력한 통제를 제공하지만, 이중 지불을 방지하는 방법 없이는 불완전하다 이것을 해결하기 위해, 우리는 트랜잭션의 공적 역사를 기록하기 위해 작업 증명(proof-of-work)을 사용하는 peer-to-peer(P2P) 네트워크를 제안했다 만약 정직한 노드들이 대다수 CPU 파워를 제어한다면 공격자의 변경 시도는 컴퓨터적으로 빠르게 비현실적이 된다 네트워크의 견고함은 정형화되지 않은 단순함에 있다 노드들은 아무 조정 없이도 한 번에 모두 수행한다 그들은 확인을 할 필요가 없다, 메시지들은 특정한 목적지로 라우팅(routed) 되지 않으며 단지 최선을 다해서 전달될 필요가 있을 뿐이기 때문이다 노드는 의지에 따라 네트워크를 떠나고 재접속 할 수 있으며, 그들이 자리를 비울 동안 일어난 일에 대한 증명으로서 가장 긴 작업 증명 (proof-of-work) 체인을 수락하면 된다 그들은 체인을 연장하는 작업으로 유효한 블록의 수락을 표현하며 유효하지 않은 블록에 대한 작업을 거부하면서 그들의 CPU 파워로 투표한다 이러한 합의(consensus) 메커니즘으로 어떤 요구되는 규칙이나 인센티브도 수행할 수 있다

References

_{[1] W. Dai, “b-money,” http://www.weidai.com/bmoney.txt, 1998.

[2] H. Massias, X.S. Avila, and J.-J. Quisquater, “Design of a secure timestamping service with minimal trust requirements,” In 20th Symposium on Information Theory in the Benelux, May 1999.

[3] S. Haber, W.S. Stornetta, “How to time-stamp a digital document,” In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.

[4] D. Bayer, S. Haber, W.S. Stornetta, “Improving the efficiency and reliability of digital time-stamping,” In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.

[5] S. Haber, W.S. Stornetta, “Secure names for bit-strings,” In Proceedings of the 4th ACM Conference on Computer and Communications Security, pages 28-35, April 1997.

[6] A. Back, “Hashcash - a denial of service counter-measure,” http://www.hashcash.org/papers/hashcash.pdf, 2002}