비트코인 : 개인 - 대 - 개인간전자화폐시스템 Satoshi Nakamoto satoshin@gmx.com www.bitcoin.org 초록. 순수하게개인대개인간의전자화폐버전은금융기관을거치지않고한쪽에서 다른쪽으로직접전달되는온라인결제 (payments) 를가능케한다. 전자서명은부분적 인솔루션을제공하지만, 만일이중지불 (double-spending) 을막기위해여전히신뢰받 는제 3 자를필요로한다면그주된이점을잃게된다. 우리는개인대개인네트워크를 사용해이중지불문제를해결하는솔루션을제안한다. 이네트워크는거래를해싱해타 임스탬프를찍어서해시기반작업증명 (proof-of-work) 을연결한사슬로만들고, 작업증 명을재수행하지않고서는변경할수없는기록을생성한다. 가장긴사슬은목격된사 건의순서를증명할뿐아니라, 그것이가장광대한 CPU 파워풀에서비롯했음을증명하 기도한다. CPU 파워과반을통제하는노드가네트워크를공격하기위해협력하지않는 한, 이들은가장긴사슬을만들어내며공격자를압도한다. 이네트워크스스로는최소 한의구조만을요구한다. 메시지는최선의노력을다해퍼져나가고, 노드는의사에따라 네트워크를떠나거나최장의작업증명사슬을그들이없는사이에벌어진일의증거로 채택해재합류할수있다. 임민철번역 ver.0.8 imc@live.co.kr encodent.com 1. 서론 인터넷기반상거래는전자결제를처리할신뢰받는제 3 자역할을거의전적으로금융기관에의존해왔다. 이시스템은대다수거래에충분히잘동작하지만, 여전히신뢰기반모델의태생적약점을극복하지못한다. 금융기관은분쟁중재를피할수없기에, 완전한철회불가거래는실제로가능하지않다. 중재비용은거래비용을높이고, 실거래최소규모를제한하며소소한일상적거래가능성을가로막고, 철회불가서비스를위한철회불가결제능력의상실에서더큰비용이발생한다. 철회가능성을위해신뢰확산이요구된다. 상거래자 (Merchants) 는필요수준보다더많은정보를위해그들을괴롭히는고객을경계해야한다. 사기의일정비율은불가피한것으로간주된다. 이런비용과결제불확실성은직접물리적통화 (currency) 를사용시회피될수있지만, 신뢰 ( 받는제 3) 자없이통신채널로결제를수행할방법은존재하지않는다. 필요한것은신뢰대신암호학적증명 (cryptographic proof) 에기반해, 거래의사가있는두당사자가신뢰받는제 3 자를필요로하지않고서로직접거래하게해주는전자화폐시스템이다. 전산적으로철회가불가능한거래는사기로부터판매자를보호하고, 통상적인제 3 자예치 (escrow) 방법은구매자를보호하기위해쉽게구현될수있다. 이논문에서, 우리는시간순으로거래의전산적증거를생성하는개인대개인간분산타임스탬프서버를사용한이중지불문제의솔루션을제안한다. 이시스템은정직한노드가공격을하려고협력하는노드그룹보다총체적으로더많은 CPU 파워를통제하는한보안상안전하다. 1
2. 거래 우리는디지털서명의사슬로써전자적화폐 (electronic coin) 을정의했다. 각소유자는화폐를송금할때먼젓번거래내역및다음소유자공개키의해시값에전자적으로서명을하고이정보를이화폐의끝에첨가한다. 수금자 (payee) 는소유권 (ownership) 의사슬을검증하기위해해당서명을검증할수있다. Transaction Owner 1's Public Key Transaction Owner 2's Public Key Transaction Owner 3's Public Key Verify Verify Owner 0's Signature Owner 1's Signature Owner 2's Signature Sign Sign Owner 1's Private Key Owner 2's Private Key Owner 3's Private Key 이과정상문제는수금자가소유자가운데누군가가화폐를이중지불하지않았는지검증할수없다는점이다. 통상적인솔루션은신뢰받는중앙통제기관 (trusted central authority) 이나조폐국 (mint) 을두고모든거래에서이중지불여부를점검하는것이다. 거래를마칠때마다이화폐는조폐국으로회수돼새로운화폐로발행돼야하고, 조폐국에서직접발행된화폐만이이중지불되지않았다고신뢰받는다. 이솔루션의문제는전체통화체계 (the entire money system) 의운명이은행처럼모든거래가거쳐가야하는조폐국운영회사에달려있다는점이다. 우리에게는먼젓번소유자가이전에어떤거래에도서명하지않았음을수금자에게알릴수단이필요하다. 이런목적에서우리는가장앞선거래하나를인정하고, 이후이중지불시도에는신경쓰지않는다. 그런 ( 이중지불된 ) 거래가없음을확인할유일한방법은모든거래를인식하고있는것뿐이다. 조폐국기반모델에서, 조폐국은모든거래를인식했고최초로받은거래를 ( 승인대상으로 ) 결정했다. 신뢰받는 ( 제 3) 자없이이방식을실현하려면, 거래는공개적으로알려져야하고 [1], 노드들이거래를받는순서의단일이력에합의하는시스템이필요하다. 수금자는매거래시그게첫수금이라는것에노드다수가동의했음을증명해야한다. 3. 타임스탬프서버 우리가제안하는솔루션은타임스탬프서버로시작한다. 타임스탬프서버는타임스탬프가찍힌항목블록의해시를가져가그해시를신문이나유즈넷게시물 [2-5] 처럼널리배포하는식으로작동한다. 이타임스탬프는그데이터가, 명백히, 해시 ( 과정 ) 에들어가기위해해당시각부터존재했음을증명한다. 각타임스탬프는그해시안에먼젓번타임스탬프를포함하고, 그에앞선것들을하나씩연장하는 (reinforcing the ones) 타임스탬프가찍힌사슬을생성한다. Item Item... Item Item... 2
4. 작업증명 개인대개인기반으로분산타임스탬프서버를구현하기위해우리는신문이나유즈넷게시물대신애덤백의해시캐시 (Adam Back's cash) 와유사한작업증명시스템 [6] 을사용할필요가있다. 작업증명은 0 비트 (zero bits) 여러개로시작하는, SHA-256 같은해시된값스캐닝을수반한다. 이에필요한평균작업은요구되는 0 비트수에따라지수적이며단일해시를실행함으로써확인될수있다. 타임스탬프네트워크용으로, 우리는블록의해시에필요한 0 비트를주는값이발견될때까지블록안에임시값을증분 (incrementing a nonce) 하는것으로작업증명을구현했다. 작업증명을만족하는데한번 CPU 동작 (CPU effort) 이쓰였으면, 그블록은그작업을재수행하지않고는변경될수없다. 거기에나중블록이연결되는만큼, 블록을변경하기위한재수행작업은그뒤모든블록까지포함한다. Tx Tx... Tx Tx... 작업증명은다수결 (majority decision making) 의대표성문제도해결한다. IP 주소당 1 표에기반한다수조건이라면누구든지많은 IP 를할당할수있는이에의해장악될 (subverted) 수있다. 작업증명은기본적으로 CPU 당 1 표다. 다수의사는최다작업증명동작이투입된가장긴사슬로대표된다. 만일다수 CPU 파워가정직한노드에의해통제된다면, 가장정직한사슬이가장빠르게늘어나다른경쟁사슬을압도 (outpace) 할것이다. 과거블록을변경하려면공격자는그블록과그뒤를잇는모든블록의작업증명을재수행해야하고그러면서가장정직한노드들의작업을따라잡아앞질러야한다. 뒤에서우리는이어지는블록이추가될수록더느린공격자가따라잡을확률이지수적으로감소함을보이겠다. 시간이지날수록노드를구동하는하드웨어의속도증가와변화하는관여도 (interest) 를보상하기위해, 작업증명난도 (difficulty) 는시간당평균블록수에따른평균목표치를조정해결정된다. 그것들 ( 블록 ) 이너무빨리생성되면난도가증가한다. 5. 네트워크 네트워크를실행하는단계는다음과같다 : 1) 새로운거래가모든노드에브로드캐스트된다. 2) 각노드가새로운거래를블록에수집한다. 3) 각노드가그블록에맞는난도의작업증명찾기에나선다. 4) 노드가작업증명을찾은시점에, 그는모든노드에게그블록을브로드캐스트한다. 5) 노드는모든거래가유효하며아직지불되지않았다는조건에맞을경우에만그블록을승인한다. 6) 노드는블록승인을표현하기위해먼젓번해시로승인된블록의해시를사용해사슬안에다음 블록을생성한다 노드는항상가장긴사슬을정확한것으로간주하고그걸잇는작업을지속한다. 만일두노드가동시에다음블록의상이한버전을브로드캐스트하면, 어떤노드는그중하나또는다른것을먼저받을수있다. 이경우그들이먼저받은것을작업하지만, 다른 branch 도저장해그게더길어질경우에대비한다. 이동점 (tie) 은다음작업증명이발견되면서깨지고한 branch 가더길어지며 ; 다른 branch 를작업하던노드는그뒤 ( 작업대상을 ) 더긴것으로전환한다. 3
새로운거래브로드캐스트가반드시모든노드에게도달할필요는없다. 브로드캐스트는많은노드에도달하는만큼곧한블록안에들어간다. 블록브로드캐스트는또한누락된메시지에내성을갖는다. 만일노드가블록을받지못하면그는다음블록을받을때누락된것을알아차리고그걸요청한다. 6. 인센티브 관례상블록안의첫거래는블록을만든이의몫이될새화폐로시작하는특별한거래다. 이는화폐를발행하는중앙기관없이, 노드가네트워크를지원할인센티브를더해주며초기에발행한화폐를유통할방법을제공한다. 새화폐일정량을꾸준히추가하는것은금채굴자가유통하는금을추가하기위해자원을소비하는것과유사하다. 우리의경우소비되는것은 CPU 시간과전기다. 이인센티브는또거래수수료 (transaction fees) 재원이될수있다. 만일거래에서도출된가치가투입된가치보다작다면, 그차이가거래를포함한블록의인센티브가치에더해질거래수수료다. 한번선결된화폐수가유통되면, 이인센티브는모두거래수수료로전환돼인플레이션에서완전히자유로워질수있다. 이인센티브노드들이계속정직하길유도하는데도움을줄수있다. 만일탐욕스러운공격자가모든정직한노드보다더많은 CPU 파워를모을수있다면, 그는그걸자신의결제를도로훔쳐사람들을속이는데쓰는것, 또는새로운화폐를만들어내는데쓰는것사이에서선택해야한다. 그는규칙대로움직이는게더이득임을알게돼있는데, 규칙은그에게다른모두의몫을합친것보다, 시스템과그가보유한부의유효성을해치는것보다더많은새화폐를베푼다. 7. 디스크공간회수 화폐안의최종거래가충분한블록에묻히면, 그전에지불된거래는디스크공간을절약하기위해폐기될수있다. 블록의해시를깨지않고이걸촉진하기위해, 거래는그블록의해시안에포함된 root 만으로, 머클트리 (Merkle Tree)[7][2][5] 로해시된다. 그러면오래된블록은트리의가지 branches 를걷어냄으로써작아질수있다. 내부해시는저장될필요가없다. Header ( ) Header ( ) Root Root 01 23 01 23 0 1 2 3 2 3 Tx0 Tx1 Tx2 Tx3 Tx3 Transactions ed in a Merkle Tree After Pruning Tx0-2 from the 거래가없는블록헤더는약 80 바이트가된다. 블록이 10 분마다만들어진다고가정하면, 80 바이트 * 6 * 24 * 365 = 연간 4.2MB 다. 2008 년부터통상적으로판매되는 RAM 2GB 짜리컴퓨터시스템, 그리고현재연간 1.2GB 씩성장을예측하는무어의법칙으로보면, 만일블록헤더가메모리에보존돼야한다더라도저장공간은문제가되지않는다. 4
8. 간소화한결제검증 결제검증은전체네트워크노드를구동하지않고도가능하다. 사용자는그가가장긴사슬을가졌다고확신할때까지네트워크노드를조회하게해주면서, 해당거래를타임스탬프가찍힌블록으로연결한머클 branch 를얻게해줄, 가장긴작업증명사슬의블록헤더사본을갖고있기만하면된다. 그는자신의거래를검사할수는없지만그걸사슬안의장소로연결함으로써, 네트워크노드가그걸받아들인것과, 이후그게받아들여졌음을확인한뒤추가된블록을볼수있다. Longest Proof-of-Work Chain Header Header Header Merkle Root Merkle Root Merkle Root 01 23 Merkle Branch for Tx3 2 3 Tx3 이처럼, 네트워크를제어하는노드가정직한한검증은믿을만하지만, 만일네트워크가공격자에의해과점된다면더취약해진다. 네트워크노드가거래를자체검증할수있긴하지만, 간소화한방법은공격자가네트워크를계속과점할수있는한그가조작한거래에의해기만당할수있다. 이를방어하기위한한가지전략은네트워크노드가유효하지않은블록을탐지시그로부터경고를받아, 사용자의소프트웨어가그온전한블록을내려받게하고경고된거래에그불일치 (inconsistency) 를확인하도록하는것이다. 수금이빈번한비즈니스는아마도여전히더독립적인보안과더빠른검증을위해그들의자체노드를구동하길원할것이다. 9. 가치합치기와나누기 화폐를독립적으로다루는것은가능하더라도, 송금에모든푼돈 (every cent) 을별도거래로만드는건무리한일이다. 가치를나누고합칠수있도록, 거래는다중입출력을포함한다. 일반적으로입력은더큰먼젓번거래의단일입력또는더작은양을결합한다중입력이며, 출력은지불용출력하나와만일있다면송금자 (sender) 에게돌려줄거스름돈출력하나, 이렇게많아야둘이다. Transaction In In Out...... 펼친부채꼴 (fan-out) 처럼, 거래가여러거래에의존하고그여러거래가더많은거래에의존하는것은문제가되지않는다는것에주목해야한다. 완전독립된 (standalone) 거래내역사본을추출해야할필요는전혀없다. 5
10. 프라이버시 전통적인은행모델은참여당사자 (the parties involved) 와신뢰받는제 3 자에게정보접근을제한함으로써일정수준프라이버시를달성한다. 이방법은모든거래를공개할필요성에따라배제되지만, 공개키익명성을보존해다른장소에서정보의흐름을끊는걸로여전히프라이버시가보장될수있다. 대중은누군가가다른누군가에게보내는금액을볼수있지만, 그거래에연결된누군가에대한정보는볼수없다. 이는증권거래소에서공개되는정보수준과비슷하게, 개별거래시각과규모를나타내는 " 테이프 (tape)" 는공개되지만, 그당사자가누구인지알지는못하는것이다. Traditional Privacy Model Identities Transactions Trusted Third Party Counterparty Public New Privacy Model Identities Transactions Public 추가방화벽으로, 새로운키쌍이각거래마다공통된소유자와연결을유지하도록사용돼야한다. 어떤연결은다중입력거래시여전히불가피하게그입력이동일소유자의것임을필연적으로드러낸다. 만일키소유자가공개되면, 연결은다른거래도동일소유자에게속하는것임을노출할위험이있다. 11. 계산 정직한사슬보다더빨리대체사슬을만들어내려는공격자의시나리오를고려해보자. 만일이런시도가성공한다하더라도, 그게아무것도없는곳에서가치를만들어내거나공격자가소유한적도없는돈을얻게만드는식으로이시스템을무단변경되도록허용하진않는다. 노드는유효하지않은거래를결제로받아들이지않으며, 정직한노드는그걸포함하는블록을절대받아들이지않는다. 공격자는오로지자신의거래에서그가최근지출한돈을거둬들이는것하나만을바꿀수있다. 정직한사슬과공격자사슬간의경주는이항임의보행 (Binomial Random Walk) 으로특징지을수있다. 성공이벤트는정직한사슬이그우위 (lead) 를 +1 만큼늘리는블록하나를연장한것이고, 실패이벤트는공격자사슬이그격차를 -1 만큼좁히는블록하나를연장한것이다. 공격자가주어진열세를따라잡을확률은도박꾼의파산 (Gambler's Ruin) 문제와유사하다. 도박꾼이무제한의신용을갖고열세로시작하고손익분기 (breakeven) 에도달하려는시도를잠재적으로무한한횟수에걸쳐시행한다고가정해보자. 우리는그가점차손익분기에도달할확률, 다시말해공격자가정직한사슬을따라잡을확률을다음과같이계산할수있다 [8]: p = 정직한노드가다음블록을발견할확률 q = 공격자가다음블록을발견할확률 q z = 공격자가 z 블록뒤에서부터따라잡을확률 q z ={ 1 if p q q/ p z if p q} 6
p > q 라가정하면, 공격자가따라잡아야하는블록수가늘어날수록그럴수있는확률은지수적으로감소한다. 그에게주어진조건상, 만일그가초기에운좋게앞으로치고나가지못한다면, 그의기회는그가뒤쳐질수록보이지않을만큼작아진다. 이제발신자 (sender) 가새로운거래를변경할수없다고충분히확신하기전까지수신자 (recipient) 가얼마나오래기다려야할지고려해보자. 발신자가자신이지불했음을수신자로하여금한동안믿게한다음, 시간이좀지나서지불금을회수하도록만들려는공격자라고가정한다. 해당수신자 (receiver) 는그런일이생길때경고를받겠지만, 발신자는그게늦기를바란다. 수신자는새로운키쌍을생성하고서명직전에발신자에게공개키를준다. 이는발신자가운좋게충분히앞설때까지계속그작업을수행함으로써미리블록의사슬을준비하지못하게방지하고, 그시점에거래를실행한다. 거래가한번발신되면, 이부정직한 (dishonest) 발신자는몰래그의거래를대신할버전으로사슬작업을병행하기시작한다. 수신자는해당거래가블록에추가되고그뒤에 z 블록이연결될때까지기다린다. 그는공격자가진척시킨규모를알지못하지만, 정직한블록이예상되는블록당시간평균치를따른다고가정하면, 공격자의잠재적진척도는기대값을갖는푸아송분포 (Poisson distribution) 가될것이다 : =z q p 현재공격자가여전히따라잡을수있는확률을얻기위해, 그가해당시점부터따라잡을수있는확률로만들어낼각진척규모별푸아송밀도를곱한다 : k e k=0 k! { q/ p z k if k z 1 if k z} 분포의무한꼬리합산을피하도록정리하고 z 1 k=0 k e 1 q/ p z k 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 * (1 - pow(q / p, z - k)); } return sum; } 7
결과를실행하면, 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 0.1% 미만의 P 를풀면 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. 결론 우리는신뢰에의존하지않는전자거래용시스템을제안했다. 강력한소유권통제를제공하는디지털서명으로만든화폐 (coins made from digital signatures) 의유력한프레임워크로시작했지만, 이는이중지불방지수단없이는불완전하다. 이를해결하기위해, 우리는정직한노드가 CPU 파워대부분을제어한다면공격자가전산적으로변경하기가금세비현실적이되는작업증명을사용해공개된거래이력을기록하는개인대개인네트워크를제안했다. 이네트워크의견고함은그정형화하지않은단순성 (unstructured simplicity) 에있다. 노드는거의조정 (coordination) 없이한번에모두동작한다. 이들은메시지가경로를지정받아어떤특정위치로가는게아니라단지최선의노력을다해전달되면그만이기때문에식별될필요가없다. 노드는의지에따라, 네트워크를떠났다가그가없는동안벌어진일의증거로작업증명사슬을받아들여재합류할수있다. 이들은 CPU 파워를사용한투표로, 유효한블록을연장하는작업을통해그걸승인했음을나타내고유효하지않은블록에대한작업을거부함으로써그걸기각한다. 어떤필요규칙과유인이든이합의작용 (consensus mechanism) 을통해집행될수있다. 8
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, "cash - a denial of service counter-measure," http://www.hashcash.org/papers/hashcash.pdf, 2002. [7] R.C. Merkle, "Protocols for public key cryptosystems," In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980. [8] W. Feller, "An introduction to probability theory and its applications," 1957. 9