Bitcoin: A Peer-to-Peer Electronic Cash System 정리

다음은 Satoshi Nakamoto (satoshin@gmx.com)에 의한 비트코인 논문을 정리한 내용이다. 개인적으로 중요하다고 생각하는 부분만 정리했기 때문에 전체 내용을 파악하고 싶다면 다른 자료를 검색하기 바란다.

전자화폐는 이중지불을 막기 위해 제3자인 금융기관 없이 온라인 결제가 가능하다.
이중 지불을 막기 위해 거래를 해싱해 타임스탬프를 찍어서 해시기반 증명작업(proof-of-work)을 연결한 사슬로 생성한다. 만들어진 사슬로 인해 전체 작업증명을 재수행하지 않고는 기록을 변경할 수 없다.
가장 긴 사슬이 올바른 사슬로 증명되며 CPU 파워 과반에 의한 통제로 이를 넘어가지 않은한 가장 긴사슬을 만들어냄으로써 공격자로부터 보호한다.

작성자: ospace114@empal.com, http://ospace.tistory.com/

서론

인터넷 전자 상거래는 금융기관이 제 3자 역할을 하고 있다. 이는 신뢰기반 모델의 태생적인 약점을 극복하고 있지 못하다.
분쟁으로 인해 완전 철회 불가능한 거래는 있을 수 없고, 이런 중재로 이해 제 3자에 의한 거래 비용을 높이며 최소 거래 규모를 제한하게 되면서 일상적인 거래 가능성을 제한하고 있다.(역주: 아마도 기본적인 거래 수수료가 발생하기에 동전으로 거래는 대부분은 현금으로 하지 온라인으로 지불하지 않는 것을 말하는 것 같다.) 기존에는 제 3자 없이 온라인으로 결제 수행할 수 있는 방법이 없다.
제 3자에 의한 신뢰대신 암호학적 증명을 기반으로한 당사자간 거래하는 전자화폐 시스템이다.
시스템을 공격하려는 노드보다 더 많은 CPU 파워를 가지고 있는한 보안상 안전하다.

거래

디지털 서명의 사슬로 전자 화폐를 정의한다. 각 소유자는 송금할 때에 이전 거래 내역 및 자신의 공개키 해시값에 전자 서명을 하고 이를 화폐 끝에 첨부한다. 수금자를 소유권을 검증하기 위해 해당 서명을 검증한다. 이 과정에서 수금자가 소유자 가운데 이중지불하지 않았는지 검증하기 어렵다.
기존에는 제 3자에 의해 모든 이중 지불 거래를 점검하고 거래가 발생하게 된다. 제 3자를 거친 거래만이 이중지불되지 않는다고 보장한다. 그렇기 때문에 통화체계는 모든 거래가 제 3자를 거쳐가기 때문에 제 3자에 의해서 좌지우지된다.
이전 소유자가 거래에 서명하지 않았음을 수금자에게 알릴 수단이 필요하다. 가장 앞선 거래를 인정되면 이후 이중 지불은 신경쓰지 않아도 된다. 이중 지물 거래가 없음을 확인하는 방법은 모든 거래를 확인해야 한다. 제 3자 없이 이를 실현하려면 거래하는 모든 노드들이 순서로된 단일 거래 이력에 대해 합의가 필요하다.
수금자는 매 거래시 첫 수금이라는 것에 노드 다수(과반)가 동의했음을 증명한다.

타임스탬프 서버

타임스탬프 서버는 타임스탬프가 찍한 블럭 해시를 가져가 온라인으로 배포하는 형태로 동작한다. 데이터가 해시 과정으로 들어가면 해당 시각부터 존재함을 증명한다. 각 타임스탬프가 해시 안에 이전 타임스탬프를 포함하고 있다면 앞선 것을 하나씩 연장하는 형태로 타임스탬프가 찍힌 사슬을 생성하게 된다.

작업 증명

개인 대 개인 기반의 분산 타임스탬프 서버를 구현하기 위해 애덤 백의 해시캐시(Adam Back's Hashcash)와 유사한 시스템을 사용했다.
타임스탬프 네트워크 용으로 블록 해시에 필요한 0비트로 주는 값을 발견할 때까지 nonce을 증분하는 방법으로 작업증명을 구현했다. 작업증명에 CPU가 사용되며 변경하기 위해서는 그 작업을 재수행해야한다. 나중에 블럭이 연결되는 만큼 블록 변경을 위한 재수행 작업은 이후 블럭를 모두 포함해서 수행해야한다.

작업 증명은 다수결(majority decision making)의 대표성도 IP주소당 1표 조건은 CPU당 1표에 의한 다수결로 최다작업 증명 사슬이 대표가 된다. 즉, 다수 CPU에 의해 노드가 통제되며 정직한 사슬이 늘어날수록 다른 공격자 사슬을 앞도하며 공격자는 그 블럭과 뒤의 모든 블럭에 대해 작업증명을 재수행하여 정직한 노트를 따라잡아야 한다.

작업증명 난이도는 시간당 평균 블럭 수에 따라 평균 목표치를 조정해서 결정하며 블럭이 너무 빠르게 생성되면 난이도를 높인다.

네트워크

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

1. 새로운 거래가 모든 노드에 브로드캐스팅
2. 각 노드가 새로운 거래를 블록에 수집
3. 각 노드가 블록에 맞는 난이도의 작업증명을 찾음
4. 노드가 작업증명 찾는 시점에 모든 노드에 그 블록을 브로드캐스팅
5. 노드는 모든 거래가 유효하며 아직 지불되지 않는다는 조건에 맞을 경우만 블럭을 승인
6. 노드는 블록 승인을 표현하기 위해 이전 해시로 승인된 블록의 해시를 사용해 사슬안에 다음 블록을 생성

노드는 항상 가장 긴 사실을 정확힌 것으로 간주하고 그 사슬을 이어가는 작업을 지속한다. 두 노드가 상이한 버전을 브로드캐스트하면 다른 노드는 먼저 수신되는 노드로 작업한다. 다른 사슬도 저장해서 그게 더 길어질 경우에 대비한다. 이는 같은 길이인 경우도 다음 작업증명이 발견으로 길이가 길어지는 경우에 대비해 저장한다. 다른 사슬을 작업하는 노드는 그 뒤에 더 긴 사슬로 전환한다.

새로운 거래에 대한 브로드캐스트는 반드시 모든 노드에 도달할 필요는 없고 많은 노트에 도달하면 된다. 만일 노드가 블록을 받지못하면 다음에 블록을 받을 때에 누락된 것을 알게되면 받지 못한 블럭을 요청한다.

인센티브

거래에서 첫번째로 블럭을 만든 자에게 주는 특별한 거래이다. 네트워크를 지원할 인센티브를 더해 초기 발행한 화폐를 유통하는 방법을 제공한다. 새 화폐를 일정량을 추가하는 것은 금 채굴자가 금을 유통하기 자원을 소비하는 것과 유사하다. 여기서는 CPU시간과 전기이다.
인센티브를 거래 수수료(transaction fees) 재원이 된다. 거래에서 도출된 가치가 투입된 가치보다 작다면 그 차이를 포함하여 인센티브에 추가된다. 인센티브로 인해 노드들이 정직할 수 있게 유지된다. 공격자에 의해 거래를 속이는 것 보다 규칙대로 움직이게 만드는 것이 이득임을 알게된다. 규칙으로 모든 이의 이익과 자신의 이익의 유효성을 해치지 않은게 더 많은 이익을 주게한다.

디스크 공간 회수

최종거래가 충분히 누적되면 이전 거래를 디스크 공간 절약을 위해 폐기될 수 있다. 머클트리(merkie tree)로 해시되고 루트만 블록 해시 안에 포함된다. 오래된 트리 분기를 폐기하고 내부 해시는 저장할 필요 없이 크기를 줄일 수 있다. 거래 없는 블록해더는 약 80 bytes가되고 블럭이 10분마다 만들어진다고 가정하면 80 byte * 6 * 24 * 243 = 4.2MB / 년 이된다. 연간 1.2GB 성장을 예측하는 무어 법칙으로 보면 저장 공간에 문제가 되지 않는다.

간소화한 결제 검증

결제 검증은 전체 네트워크 노드를 구동하지 않아도 된다. 얻을 수 있는 가장 긴 사슬 헤더 사본을 유지하고 해당 거래를 타임스탬프가 찍힌 블록에 연결한 머클 분기를 얻기만 하면 된다.
자신의 거래를 검사할 수 없지만 그것을 사슬에 연결함으로써 네트워크 노드가 받아들인 것과 이후 받아들여졌는지 확인한 뒤 추가된 블럭을 확인할 수 있다.

네트워크 제어하는 노드의 검증을 신뢰할 수 있지만 공격자의 과점으로 더 취약할 수 있다. 거래 자체를 검색할 수 있지만 공격자가 네트워크를 과점할 수 있기 때문에 거래 조작을 방어하기 위해 유효하지 않은 블록 탐지시 경고를 보내고 다시 온전한 블럭을 내려받게하여 거래 불일치를 확인할 수 있다. 거래가 빈번한 비니지스인 경우는 독립적인 보안과 빠른 검증을 위해 자체 노드로 동작하기를 원할 수 있다.

가지 합치기와 나누기

일반적인 화폐를 독립적으로 사용할 수 있어도 푼돈(every cent)을 별도 거래로 만드는 것은 쉽지 않다. 이런 거래를 나누거나 합칠 수 있도록 복수의 입출금을 가질 수 있다.
보통의 이전 거래로부터 단수 입금이거나 소량이 합쳐진 복수 입금이 있을 수 있다. 출금은 지불용 출금과 송금인에게 돌려줄 거스름돈 출금으로 많아야 출금은 두개이다.

여러 거래에 의존되고 이런 거래는 많은 거래들에 의존하는데는 문제가 없다. 완전하고 독립적인 거래내역 사본을 추출할 필요가 없다.

프라이버시

전통적인 은행은 당사자들과 신뢰할 수 있는 제 3자에게만 정보 접근을 허용함으로써 개인 정보 보호을 제공한다. 이는 모든 거래에 대해 공개 필요는 없지만 다른 곳으로 보내는 정보 흐름을 분리함으로서 개인정보 보호가 가능하다.
여기서는 누구나 다른이 보내는 금액을 볼 수 있지만 누구와 거래하는지는 알 수 없다. 이는 증권거래소에서 발표되는 매매정보와 비슷하다. 개인 거래의 규모(거래 기록, tape)는 공개되지만 당사자 정보를 알 수 없다.

방화벽으로 새로운 키쌍(key pair)는 각 거래마다 공통된 소유자에게 연결되는 것을 방지하는데 사용된다. 다중 입력 거래에 대한 연결은 피할 수 없는데 이럴 경우 그런 입력들은 동일한 소유자로 들어나게 된다. 만일 키 소유자가 공개되면, 연결은 다른 거래도 동일한 수유자에게 속하는 거래가 노출될 위험이 있다.

계산

공격자에게 사슬을 대체된다고 해보자. 이런 공격이 새로운 거래를 만들어 소유하지 않은 돈을 획득하는 변경은 허용되지 않는다. 노드는 유효하지 않은 거래가 포함된 사슬을 받아들이지 않는다. 공격자는 오로지 자신이 소유한 거래만 변경할 수 있고, 최근에 지불한 돈을 돌려받을 수 있을 뿐이다.

정직한 사슬과 공격자 사슬은 이항 랜덤 보행(binomial random walk)로 묘사될 수 있다. 성공 이벤트는 정직한 사설에 우위(+1)을 +1을 추가하거나 실패 이벤트는 공격자 사슬과 격차를 -1로 좁힌다.

공격자에 의해 따라잡을 가능성은 도박꾼 파산(Gambler's Ruin)문제에 비유될 수 있다. 도박꾼은 적자로 게임을 시작해서 무한번의 시도로 이익을 얻을 려고 한다. 그가 손익분기에 도달할 확률 또는 공격자가 정직한 사슬을 다라 잡을 확률을 계산할 수 있다.

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

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

p > q라면 공격자가 따라잡아야할 확률은 블록 수가 커지면 지수적으로 감소한다. 초기에 운이 좋아서 앞서나가지 못하면 뒤로갈 수록 공격이 성공할 가능성은 거의 없어진다.

송금인이 수취인에게 지불했다고 믿게한 후에 지불금을 회수하려는 공격자가 있다고 하자. 그런일이 발생하면 수취인이 경고를 받게되지만 늦게 확인하기를 바란다.
수취자는 새로운 키쌍을 생성하고 서명 직전에 송금인에게 공개키를 전달한다. 이는 송금인이 먼저 앞서서 작업을 수행하지 못하도록 방지하기 위한 것으로 그 시점에 거래를 실행하게 된다. 거래가 생성되면 공격자는 거래를 대신할 버전 사슬을 병행작업 진행한다.
수취자는 해당 거래가 블럭에 추가되고 z개 블록이 연결될때까지 기다린다. 정직한 블록으로 예상되는 블록당 평균 기대 시간이 소요된다고 하면 공격자의 잠재적 진척도는 포아송 분포를 따를 것이다.

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

공격자가 따라잡을 수 있는 확률을 계산하기 위해 그 시점에 따라잡을 수 있는 확율에 따라 만들어진 각 규모별 포아송 밀도 함수를 곱한다.

$$ \sum_{k=0}^\infin { \lambda^k e^{-\lambda} \over k!} \begin{cases} (q/p)^{(z-k)} &\text{if }k<=z\\1&\text{if }k>z\end{cases} $$

분포의 꼬리 부분의 무한대를 더하는 것을 피하기 위해서 식을 정리해보자.
먼저 k의 범위를 z이하와 초과로 분리해서 더할 수 있다.

$$ \sum_{k=0}^z { \lambda^k e^{-\lambda} \over k!} (q/p)^{(z-k)} + \sum_{k=z+1}^\infin { \lambda^k e^{-\lambda} \over k!}$$

뒤에 식을 정리하기 위해서

$$ \sum_{k=0}^z { \lambda^k e^{-\lambda} \over k!} (q/p)^{(z-k)} + \sum_{k=z+1}^\infin { \lambda^k e^{-\lambda} \over k!} + \sum_{k=0}^z { \lambda^k e^{-\lambda} \over k!} - \sum_{k=0}^z { \lambda^k e^{-\lambda} \over k!}$$

뒤의 식을 합하면

$$ \sum_{k=0}^z { \lambda^k e^{-\lambda} \over k!} (q/p)^{(z-k)} + \sum_{k=0}^\infin { \lambda^k e^{-\lambda} \over k!} - \sum_{k=0}^z { \lambda^k e^{-\lambda} \over k!}$$

\( \sum_{k=0}^\infin { \lambda^k e^{-\lambda} \over k!} \)은 누적 분포 함수로 k가 무한이기 때문에 1이 된다.

$$ \sum_{k=0}^z { \lambda^k e^{-\lambda} \over k!} (q/p)^{(z-k)} + 1 - \sum_{k=0}^z { \lambda^k e^{-\lambda} \over k!}$$

이를 정리하면

$$ 1 - \sum_{k=0}^z { \lambda^k e^{-\lambda} \over k!} (1 - (q/p)^{(z-k)}) $$

이를 C코드 변경하면

#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 * (l - pow(q / p, z - k));
    }

    return sum;
}

결론

제 3자에 의존하지 않고, 강력한 소유권 통제로 만든 전자화폐이지만 이중 지불을 방지하기 위해 CPU 사용하여 작업증명을 사용해 거래 이력 관리를 제안했다. CPU 자원으로 투표하고 유효한 블럭을 연장을 통해 유효하지 않은 블록을 거부한다. 합의 작용(consensus mechanism)을 통해 유지된다.

참고

[1] https://bitcoin.org/bitcoin.pdf