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