한빛출판네트워크

인터넷에서의 상거래는 거의 전적으로 전자 결제를 처리해주는, 신뢰할 만 한 제3자 역할을 하는 금융 기관에 의존해왔습니다. 이러한 시스템은 대부분의 거래에서 잘 작동하지만, 여전히 신뢰 기반 모델이 지닌 약점에 시달리고 있습니다. 완전히 비가역적인 거래는 금융 기관들의 분쟁 조정을 피할 수 없기 때문에 사실상 불가능합니다.

중재 비용은 거래 비용을 증가시키고 실거래의 최소 규모를 제한하며 일상적인 소액 거래의 가능성을 차단합니다. 또한 비가역 서비스를 위한 비가역 결제를 생성하는 능력을 잃어버려 더 큰 비용이 발생합니다. 그리고 가역성 때문에 신뢰를 요구하는 일이 널리 퍼지게 됩니다.

가맹점은 고객에게 주의를 기울여야 하고, 그렇게 하지 않았으면 필요 없었을 정보를 더 많이 요구해 고객을 괴롭힙니다. 그리고 일정 비율의 사기는 피할 수 없는 것으로 받아들입니다. 이러한 비용과 지불의 불확실성은 물리적인 통화를 직접 사용하면 피할 수 있으나, 신뢰 당사자가 없는 통신 채널 상에서 결제를 수행하는 메커니즘은 존재하지 않습니다.

필요한 것은 신뢰 대신 암호학적 증명에 기반하여 거래 의사가 있는 두 당사자가 신뢰하는 제3자를 필요로 하지 않으면서 서로 직접 거래할 수 있게 해주는 전자 결제 시스템입니다. 계산상 되돌리는 것이 불가능한 거래는 사기로부터 판매자를 보호하고, 일상적인 에스크로 메커니즘을 쉽게 구현할 수 있게 하여 구매자를 보호합니다. 이 논문에서는 P2P 분산 타임스탬프 서버를 이용하여 거래의 시간 순서에 대한 연산 증거를 생성하는, 이중지불 문제에 대한 해법을 제시합니다. 정직한 노드들이 모여 공격자 노드의 협력 그룹보다 더 많은 CPU 파워를 통제하는 한 시스템은 안전합니다.

거래

우리는 전자코인을 디지털 서명의 체인으로 정의합니다. 각 소유자는 이전 거래의 해시 및 다음 소유자의 공개키에 디지털 서명을 하고 코인 끝에 추가함으로써 코인을 다음 사람에게 송금합니다. 수취인은 서명을 검증하여 소유권의 체인을 검증할 수 있습니다.

이 과정에는 수취인이 소유자 중 누군가가 코인을 이중지불하지 않았다는 것을 검증할 수 없는 문제가 있습니다. 일반적인 해법은 신뢰하는 중앙 기구나 조폐국 등을 두고 모든 거래에 대해 이중지불을 검사하게 하는 것입니다. 매 거래 후 코인은 새 코인을 발행할 조폐국으로 반환되어야 하고, 조폐국으로부터 직접 발행된 코인만이 이중지불되지 않은 것으로 신뢰받을 수 있습니다. 이 해법의 문제는 전체 화폐 시스템의 운명이 은행과 마찬가지로 모든 거래가 거쳐가야 하는, 조폐국을 운영하는 회사의 손에 달려 있다는 점입니다.

우리는 수취인에게 이전 소유자가 그 전의 어떤 거래에도 서명하지 않았다는 것을 알릴 방법이 필요합니다. 우리의 목적상 중요한 것은 가장 앞선 거래이므로, 이후의 이중지불 시도에 대해서는 신경 쓰지 않습니다. 거래 하나가 없다는 것을 확인하는 유일한 방법은 모든 거래를 확인하는 것입니다. 조폐국 기반 모델에서 조폐국은 모든 거래를 알고 있으며 어느 것이 먼저 도착했는지 결정합니다. 이 방식을 신뢰하는 당사자 없이 실현하려면 거래가 공개적으로 알려져야 하고, 참가자가 거래를 수신한 순서의 단일 이력에 합의하는 시스템이 필요합니다. 수취인에게는 각 거래 시점에 그 거래가 먼저 도착했다는 데 노드의 과반수가 합의했다는 증거가 필요합니다.

타임스탬프 서버

우리가 제안하는 해법은 타임스탬프 서버에서 시작됩니다. 타임스탬프 서버는 타임스탬프를 찍을 항목의 블록 해시를 가져와, 그 해시를 신문이나 유즈넷 게시물 같은 곳에 널리 배포하는 방식으로도 동작합니다. 타임스탬프는 해당 데이터가 해시에 포함되려면 해당 시점에 분명히 존재했어야 함을 입증합니다. 각 타임스탬프는 그 해시 내에 이전 타임스탬프를 포함하고 있으며, 각각 추가되는 타임스탬프는 그 이전에 있던 것들을 강화하면서 체인 형태를 이룹니다.

작업증명

P2P 기반으로 분산형 타임스탬프 서버를 구현하려면 신문이나 유즈넷 게시물이 아니라 애덤 백Adam Back의 해시캐시Hashcash와 유사한 작업증명 시스템을 사용할 필요가 있습니다. 작업증명은 SHA256 같은 것으로 해시를 계산했을 때 그 해시가 여러 개의 비트로 시작되는 특정 값을, 탐색하는 작업이 포함됩니다. 요구되는 평균 작업량은 필요한 0비트의 개수에 따라 지수적으로 증가하며 한 번의 해시 연산 실행으로 검증 가능합니다.

타임스탬프 네트워크의 경우, 블록의 해시에 필요한 수의 0비트를 주는 값이 발견될 때까지 블록 내의 논스nonce를 증가시키는 방식으로 작업증명을 구현합니다. 일단 CPU의 노력이 작업 증명을 만족시키는 수준에 도달하면 블록은 그 작업을 재수행하지 않고는 변경될 수 없습니다. 이후의 블록들이 그 뒤에 연달아 이어지므로 블록을 변경하는 작업은 그 뒤의 모든 블록들을 재작업하는 것까지 포함합니다.

작업증명은 다수결에서 대의를 결정하는 문제도 해결합니다. 과반수가 IP 주소당 한 표에 기반한다면, 많은 IP를 할당할 수 있는 누군가에 의해 전복될 수 있습니다. 작업증명은 기본적으로 CPU당 한 표입니다. 과반의 결정 사항은 가장 많은 작업증명 노력이 투입된 가장 긴 체인으로 대표됩니다. 만약 CPU 파워의 과반수를 정직한 노드들이 통제한다면, 정직한 체인은 가장 빨리 자라나 다른 경쟁 체인들을 압도할 것입니다. 과거의 블록을 변경하려면 공격자는 해당 블록과 그 뒤에 이어지는 모든 블록들의 작업증명을 재수행한 후 정직한 노드들의 작업을 따라잡고 앞질러야 합니다. 더 느린 공격자가 따라잡을 확률은 후속 블록들이 추가됨에 따라 지수적으로 감소한다는 것을 뒤에서 살펴보겠습니다.

시간이 지날수록 하드웨어 속도가 증가하고 동작 노드의 이익이 변화하는 것을 보상하기 위해, 작업증명 난이도는 시간당 평균 블록 수를 대상으로 이동 평균에 의해 결정됩니다. 블록이 너무 빨리 생성되면 난이도가 증가합니다.

네트워크

네트워크의 구동 단계는 다음과 같습니다.

1) 새로운 거래가 모든 노드에 전파됩니다.
2) 각 노드는 블록에 새로운 거래들을 수집합니다.
3) 각 노드는 자신의 블록에 해당하는 어려운 작업증명을 발견하기 위해 작업을 수행합니다.
4) 한 노드가 작업증명을 발견하면 해당 노드는 그 블록을 모든 노드에 전파합니다.
5) 노드들은 블록 안의 모든 트랜잭션이 유효하고 이미 지불된 것이 아닐 경우에만 그 블록을 승인합니다.
6) 노드들은 승인된 블록의 해시를 이전 해시로 사용하여 체인 내 다음 블록을 생성하는 작업을 함으로써 해당 블록을 승인했음을 표현합니다.

노드들은 항상 가장 긴 체인을 올바른 것으로 간주하고 그 체인을 확장하는 작업을 계속해나갑니다. 만일 두 노드가 동시에 다음 블록의 서로 다른 버전을 전파하면, 일부 노드는 어느 한쪽을 먼저 받게 될 수 있습니다. 그 경우 노드들은 자신이 받은 첫 번째 블록으로 작업하지만 다른 쪽 가지도 그 쪽이 더 길어질 경우를 대비하여 저장해둡니다. 무승부 상태는 다음 작업증명이 발견되어 한 가지가 더 길어지면 깨지는데, 다른 쪽 가지에서 작업하던 노드들은 더 긴 가지로 옮겨옵니다.

새로운 거래의 전파가 반드시 모든 노드에 도달할 필요는 없습니다. 그 트랜잭션이 많은 노드에 도달하면 머지않아 하나의 블록에 포함될 것입니다. 블록 전파는 메시지가 누락되는 경우도 허용합니다. 노드가 블록을 받지 못하면 다음 블록을 받을 때 그 블록이 누락된 것을 알게 되고 누락된 블록을 요청할 것입니다.

인센티브

관례상 블록의 첫 거래는 블록 생성자가 소유한 신규 코인으로 시작되는 특별한 거래입니다. 이것은 네트워크를 지원하는 노드를 위해 인센티브를 추가하며, 화폐를 발행하는 중앙 기관이 없기 때문에 초기에 코인 유통 방법을 제공합니다. 일정량의 새 코인을 꾸준히 추가하는 것은 금 채굴자들이 유통할 금을 추가하기 위해 자원을 소비하는 것과 유사합니다. 우리의 경우, 소비되는 것은 CPU 전력과 시간입니다.

인센티브는 거래 수수료로도 자금을 조달할 수 있습니다. 거래의 출력값이 입력값보다 작을 경우, 그 차이는 해당 거래를 포함한 블록의 인센티브에 추가되는 거래 수수료입니다. 미리 결정된 수만큼의 코인이 일단 유통되면, 인센티브는 거래 수수료로 모두 전환되어 인플레이션으로부터 완전히 자유로워질 수 있습니다.

인센티브는 노드가 정직한 상태를 유지하도록 독려할 수 있습니다. 만약 탐욕스러운 공격자가 다른 모든 정직한 노드보다 더 많은 CPU 파워를 모을 수 있다면, 공격자는 그 파워를 자신의 지불을 도로 훔쳐 사람들을 속이는 데 사용하거나, 새 코인을 만드는 데 사용하는 것 중 하나를 선택해야 할 것입니다. 공격자는 규칙대로 행동하는 것이 더 이익이라는 것을 알 수밖에 없는데, 규칙은 공격자가 시스템과 자신이 보유한 부의 유효성을 해치는 대신 모두의 지분을 합한 것보다 더 많은 코인을 베풀어줍니다.

디스크 공간 회수

코인의 가장 최근 거래가 충분한 수의 블록 아래에 묻히면, 그 이전에 소비된 거래는 디스크 공간 절약을 위해 폐기할 수 있습니다. 블록의 해시를 손상시키지 않으면서 이를 쉽게 진행하기 위해 거래들은 머클트리Merkle Tree 내에 해시되고, 트리의 루트만 블록의 해시에 포함됩니다. 그러면 오래된 블록들은 트리의 가지를 쳐냄으로써 크기를 줄일 수 있습니다. 그리고 트리 내부의 해시들은 저장될 필요가 없습니다.

거래가 없는 블록의 헤더는 대략 80바이트 정도입니다. 블록이 10분마다 생성된다고 가정하면, 80바이트×6×24×365=연간 4.2MB입니다. 2008년 현재 보통 2GB 램이 탑재되어 팔리는 컴퓨터 시스템과 연간 1.2GB가 성장할 것으로 예상되는 무어의 법칙을 고려하면, 블록 헤더를 메모리에 저장해야 하는 경우라도 저장 공간은 문제되지 않습니다.

단순 지불 검증

결제를 검증하는 것은 전체 네트워크 노드를 구동하지 않고도 가능합니다. 사용자는 가장 긴 작업증명 체인의 블록 헤더 사본만 갖고 있으면 되는데, 자신이 가장 긴 체인을 갖고 있다는 확신이 들 때까지 네트워크를 조회해서 특정 거래와 그 거래의 타임스탬프가 들어 있는 블록을 연결해주는 머클 가지를 가져와 얻을 수 있습니다. 사용자는 거래를 스스로 검사할 수 없지만 해당 거래를 체인 내 특정 위치에 연결함으로써 한 네트워크 노드가 그것을 승인했다는 것과, 그 뒤에 추가되는 블록들이 네트워크에서 그 거래를 승인했다는 것을 추가로 확인시켜줌을 알 수 있습니다.

이와 같이 검증은 정직한 노드들이 네트워크를 제어하는 한 신뢰할 수 있지만 네트워크가 공격자에 의해 압도당하면 더 취약해집니다. 네트워크 노드가 결제를 스스로 검증할 수 있는 반면, 단순화 방법에서는 공격자가 네트워크를 계속 압도하는 한 공격자가 조작한 결제에 속을 수 있습니다. 이러한 상황에 대처하기 위한 한 가지 전략은, 유효하지 않은 블록을 탐지한 네트워크 노드들로부터 경고를 받아들여 사용자의 소프트웨어가 전체 블록을 다운로드하고 경고를 받은 트랜잭션의 불일치를 확인하게 하는 것입니다. 결제가 빈번하게 이뤄지는 사업에서는 아마도 더 독립적인 보안과 빠른 검증을 위해 자체적으로 노드를 실행하고 싶을 것입니다.

가치 합치기와 나누기

코인을 독립적으로 다룰 수는 있겠지만, 송금 시 모든 소액별로 별도의 거래를 생성하는 것은 어려울 것입니다. 이에 트랜잭션에는 가치를 나누고 합칠 수 있도록 복수의 입력값과 출력값이 포함됩니다. 보통은 더 큰 이전 거래에서 나온 단일 입력이나 더 적은 금액을 합한 복수 개의 입력값, 그리고 많아야 두 개의 출력값(결제용으로 하나, 송금인에게 돌려줄 잔돈이 있을 경우 잔돈용으로 하나)이 있을 것입니다.

하나의 거래가 여러 거래에 의존하고, 그 거래들은 더 많은 거래에 의존하는 식으로 전개되는 과정은 여기서 문제로 다루지 않는다는 점에 유의해야 합니다. 거래 이력이 완전히 분리된 사본을 추출해낼 필요는 없습니다.

개인정보보호

전통적인 은행 모델은 관계 당사자들과 신뢰받는 제3자에게 정보 접근을 제한시킴으로써 어느 정도의 개인정보보호를 달성합니다. 모든 트랜잭션은 공개되어야 하므로 이런 방법은 사용할 수 없지만, 공개키를 익명으로 유지하면 다른 곳으로 정보가 흘러가는 것이 차단되므로 개인정보를 보호할 수 있습니다. 대중은 누군가가 다른 누군가에게 얼마의 금액을 전달하는지 볼 수 있지만 그 트랜잭션이 누구에게 연결되는지는 알 수 없습니다. 이것은 주식 거래소의 정보 공개 수준과 유사한데, 개인적 트랜잭션이 일어난 시간과 액수를 나타내는 ‘테이프’는 공개되지만, 트랜잭션을 만든 당사자가 누구였는지 알려주는 정보는 없는 것과 마찬가지입니다.

추가적 안전조치로, 각 트랜잭션들이 공통의 소유자에게 연결되는 것을 막으려면 새로운 키 쌍을 사용해야 합니다. 입력값들을 동일인이 소유하고 있다는 점이 드러날 수밖에 없는 복수 입력값 거래에서는 어느 정도 연결이 일어나는 것을 피할 수 없습니다. 키의 소유자가 밝혀질 경우 연결 정보가 같은 소유자에게 속한 다른 거래를 노출시킬 수 있다는 것은 위험 요인입니다.

연산

정직한 체인보다 더 빠르게 대체 체인을 만들어내려는 공격자의 시나리오를 고려해봅시다. 공격이 발생하더라도 없던 가치를 만들어낸다거나 공격자가 자신이 소유한 적 없는 돈을 갖게 되는, 즉 시스템이 임의의 변경에 개방되는 일은 발생하지 않습니다. 노드들은 유효하지 않은 거래를 결제로 승인하지 않을 것이고, 정직한 노드들은 그런 거래를 담고 있는 블록을 절대 승인하지 않을 것입니다. 공격자는 이미 지불한 돈을 환불받기 위해 자신의 거래들 중 하나를 변경하는 시도만 할 수 있습니다.

정직한 체인과 공격자 체인 사이의 경쟁은 이항 랜덤 워크Binomial Random Walk^*로 특징 지을 수 있습니다. 성공 이벤트는 정직한 체인을 한 블록 늘려서 선두를 +1만큼 증가시키고, 실패 이벤트는 공격자의 체인을 한 블록 늘려서 차이를 –1만큼 줄입니다.

공격자가 주어진 열세를 만회할 확률은 노름꾼의 파산Gambler’s Ruin 문제와 유사합니다. 무한한 자금을 가진 도박꾼이 적자 상태에서 시작하여 손익분기점에 도달하기 위해 무한 번 시도한다고 가정해봅시다. 도박꾼이 손익분기점에 도달하거나 공격자가 정직한 체인을 따라잡을 확률은 다음과 같이 계산할 수 있습니다.

● p = 정직한 노드가 다음 블록을 발견할 확률
● q = 공격자가 다음 블록을 발견할 확률
● qz = 공격자가 뒤처진 z 블록만큼 따라잡을 확률

p > q라고 가정하면 공격자가 따라잡아야 하는 블록 수가 늘어날수록 따라잡을 확률은 지수적으로 감소합니다. 초기에 크게 앞서나가지 않는다면, 그가 가진 확률로는 점점 더 뒤처질수록 기회가 보이지 않을 만큼 작아지게 이제 발신자가 거래를 변경할 수 없다는 확신을 충분히 가질 때까지 새 거래의 수취인이 얼마나 오래 기다려야 할지 알아봅시다. 발신자는 공격자이며 수취인이 공격자에게 지불받았다고 한동안 믿게 만든 후 얼마간의 시간이 지나면 자신에게 그 돈이 환불되도록 전환하고 싶어 한다고 가정하겠습니다. 수신자는 그런 일이 발생하면 경보를 받겠지만, 발신자는 경보가 늦게 일어나기를 바랍니다.

수신자는 새로운 키쌍을 생성하고 서명 직전에 발신자에게 공개키를 전달합니다. 이것은 발신자가 운 좋게 충분히 멀리 앞서 나갈 때까지 작업을 계속 진행하여 블록의 체인을 미리 준비해놓고 그 시점에 거래를 실행하지 못하도록 합니다. 일단 거래가 전송되면 정직하지 않은 발신자는 몰래 그의 거래를 대체하는 버전을 포함한 병렬 체인상의 작업을 진행하기 시작합니다.

수취인은 해당 거래가 블록에 추가되고 그 뒤로 z개의 블록이 추가될 때까지 기다립니다. 수취인은 공격자가 진행한 작업 분량이 정확히 얼마나 되는지 모르지만, 정직한 블록들이 블록당 평균 예상 시간만큼 걸린다고 가정하면 공격자의 잠재적 작업 분량은 다음의 기대값을 갖는 푸아송 분포Poisson distribution를 이룰 것입니다.

이제 공격자가 따라잡을 수 있는 확률을 구하기 위해, 공격자가 해당 지점에서 따라잡을 수 있는 확률로 계산되는 각 작업량에 푸아송 밀도를 곱합니다.

분포에서 무한대 길이의 꼬리 부분을 합산하는 것을 피하기 위해 수식을 정리하면 다음과 같습니다.

C 코드로 변환하면 다음과 같이 됩니다.

												#include 												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.1z=0 P=1.0000000z=1 P=0.2045873z=2 P=0.0509779z=3 P=0.0131722z=4 P=0.0034552z=5 P=0.0009137z=6 P=0.0002428z=7 P=0.0000647z=8 P=0.0000173z=9 P=0.0000046z=10 P=0.0000012q=0.3z=0 P=1.0000000z=5 P=0.1773523z=10 P=0.0416605z=15 P=0.0101008z=20 P=0.0024804z=25 P=0.0006132z=30 P=0.0001522z=35 P=0.0000379z=40 P=0.0000095z=45 P=0.0000024z=50 P=0.0000006

P가 0.1보다 작아질 때를 계산해 보면 다음과 같습니다.

P < 0.001q=0.10 z=5q=0.15 z=8q=0.20 z=11q=0.25 z=15q=0.30 z=24q=0.35 z=41q=0.40 z=89q=0.45 z=340

결론

우리는 신뢰에 의존하지 않는 전자 거래 시스템을 제안했습니다. 이 시스템은 디지털 서명을 사용하여 소유권을 강력하게 통제하는 코인이라는 평범한 생각에서 출발했으나, 이중지불을 방지하는 방법이 없으면 온전한 시스템이 될 수 없습니다. 우리는 이중지불 문제를 해결하기 위해 트랜잭션 이력을 공개적으로 기록하는 작업증명 기반의 P2P 네트워크를 제안했고, 네트워크는 정직한 노드들이 절반 이상의 CPU 연산능력을 장악할 경우 공격자가 기록 변경을 일으키려는 시도를 빠른 시간 내에 계산적으로 불가능하게 만듭니다. 네트워크는 그 구조화되지 않은 단순성으로 인해 견고하게 유지됩니다. 노드들은 거의 조정할 필요 없이 모두 동시에 동작합니다. 노드들은 서로를 식별할 필요가 없는데, 발신 메시지가 특별히 지정된 경로를 거쳐 가는 방식이 아니라 받는 메시지를 열심히 주변에 전송하기만 하면 되기 때문입니다. 노드는 자유롭게 네트워크를 떠나고 재합류할 수 있으며, 자신이 떠나 있는 동안 발생한 일에 대한 증거로 작업증명 체인을 채택합니다. 노드는 자신의 CPU 연산능력을 이용하여 투표를 진행하는 데 노드가 블록을 늘리는 작업을 한다는 것은 유효한 블록으로 받아들인다는 의사를 나타내는 것이고, 블록을 늘리는 작업을 거부한다는 것은 유효하지 않은 블록을 거절한다는 의사를 나타내는 것입니다. 필요한 규칙과 보상 체계는 이러한 합의 메커니즘을 통해 강제로 유지될 수 있습니다.