ISSN 2383-630X(Print) / ISSN 2383-6296(Online) Journal of KIISE, Vol. 45, No. 8, pp. 848-855, 2018. 8 https://doi.org/10.5626/jok.2018.45.8.848 블록체인의이중지불탐지알고리즘 (Algorithm for Detecting Double-Spending in Blockchain) 김민호 김수진 최훈 (Minho Kim) (Sujin Kim) (Hoon Choi) 요약블록체인은전자화폐시스템으로널리사용되고있는비트코인의기반이되는기술이다. 비트코인에서하나의전자화폐로두번이상의거래를하는것을이중지불 (double-spending) 이라고하며불법거래에해당한다. 현재블록체인은블록들이연결된체인에서분기가생기는경우, 더많은블록들이연결된체인을유효한거래로인정하는방식을취하는데, 불법거래를포함한블록들의체인이정상거래블록들의체인보다더길어질수있는가능성이존재하므로체인의길이만으로는불법거래를완벽하게방지할수는없다. 본논문에서는이중지불을탐지하는방법과탐지후다른노드에게알리는방법을제안한다. 비트코인오픈소스를사용하여제안방법을구현하고검증하였다. 키워드 : 블록체인, 이중지불, 비트코인, 트랜잭션, 역추적 Abstract The blockchain is a key technology of the Bitcoin, which is widely used as an electronic cash system. In the Bitcoin, one digital currency is valid for only one transaction. It is called double-spending, a type of illegal transaction, if two or more transactions are made by using the same digital currency. When the blockchain is forked, the blockchain specification assumes that the longer blockchain may be valid, but the blockchain containing double-spending may become longer than the blockchain containing normal transactions, so comparing lengths of the chain cannot completely prevent illegal transactions. In this paper, we propose an algorithm to detect double-spending and a mechanism to notify other nodes after detection. This algorithm is implemented and verified by using the bitcoin core. Keywords: blockchain, double-spending, bitcoin, transaction, backtracking 본연구는충남대학교학술연구비에의해지원되었음 학생회원 : 충남대학교컴퓨터공학과 minho.kim093@gmail.com sujin.kim1414@gmail.com 종신회원 : 충남대학교컴퓨터공학과교수 (Chungnam Nat'l Univ.) hc@cnu.ac.kr (Corresponding author 임 ) 논문접수 :2017년 12월 16일 (Received 16 December 2017) 논문수정 :2018년 5월 15일 (Revised 15 May 2018) 심사완료 :2018년 5월 28일 (Accepted 28 May 2018) CopyrightC2018 한국정보과학회ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지제45권제8호 (2018. 8) 1. 서론블록체인 (Blockchain) 은 2008년개발된비트코인 (Bitcoin) 전자화폐시스템의기반기술이다 [1]. 블록체인은거래내역이포함된블록을 Peer-to-Peer(P2P) 통신방식으로네트워크에전파하여모든노드 (peer) 가같은블록을저장하는방식이다. 따라서각노드는전자화폐를통한거래후잔고와거래의성립여부등을자신이보관하고있는블록들을보고스스로확인할수있다. 블록은거래내역과네트워크시간그리고직전블록의내용으로계산된해시 (hash) 값을저장하기때문에, 서로다른시간에만들어진블록들간에선후관계가형성되어일련의블록체인으로구성된다. 비트코인에서조작을가해하나의전자화폐로두번이상의거래를발생시킬수가있는데, 이것을이중지불 (double-spending) 이라하며불법거래에해당한다. 비트코인시스템이신뢰받기위해서는, 하나의전자화폐로
블록체인의이중지불탐지알고리즘 849 반드시한번의거래만허용함으로써이중지불로인한피해를방지하여야한다. 이중지불이발생하는경우에는정상거래를기록한블록체인과중복된지불을기록한또다른불록체인이공존하게되며, 얼마후길이가더긴블록체인이채택되고짧은것은무시되어폐기된다 [1,2]. 긴체인길이의기준은전자화폐시스템마다다른데, 비트코인의경우에는 6개이다. 즉거래발생후 6개의블록이생성되는약 1시간이지나서야이중지불중하나의거래는채택되고다른거래는기각되는판정이일어난다. 그러나단순히긴블록체인을선택하는경우, 블록체인기술의여러가지보안측면취약성들 [3, 4] 중에서 51% Attack에노출되게된다. 이중지불을포함한체인이길어질수있는확률이존재하기때문에이중지불을완벽하게방지할수는없다. 본논문은블록체인을기반으로하는비트코인시스템에서이중지불이발생할때, 제안하는알고리즘이이를신속히탐지하여다른노드들에게알림으로써사용자또는응용에서이중지불에대한대처를하여피해를줄이는방법에대한것이다. 블록이새로생성되어전파될때실행되어이중지불여부를탐지하는알고리즘과, 문제가되는거래를네트워크의모든노드들에게알릴수있는방법을제안하였으며비트코인오픈소스를사용하여제안방법을구현하고검증하였다. 블록체인에대한이중지불탐지또는방지에관한선행연구들이있으나이논문에서의접근방식과는차이들이있다. [5] 에서는거래를시작하기전에거래가유효할지를제 3의 notary 서비스가먼저확인하는방법을제시하였다. 물론제 3의확인자가개입하여이중지불을방지할수있으나서버방식의 notary 서비스를이용해야한다는점에서블록체인의 P2P 개념에벗어난다. 본연구는제 3자가개입하지않고개개인의노드가이중지불을탐지한다. 이는이미거래가성사되어블록으로만들어진후에실시간탐지하는것으로서, 거래이전에이중지불을검사받는방법과는차이가있다. [6] 에서는여러가지이중지불공격유형들을분류하였는데, 이러한이중지불공격은블록체인네트워크를모니터링하여대응할수있다고하였다. 본연구에서제시하는방법과마찬가지로정상거래가블록으로포함된후에이중지불을탐지할수있다고하였지만, 구체적인모니터링방법을제시하지않았다. [7] 에서는거래가발생하였으나아직블록으로형성되기전시점에이중지불을방지하는방법을다루고있다. 이방법은같은블록에포함될일련의거래내역들을검사해이중지불을찾을수는있으나, 본연구에서제시하 는것처럼일단정상거래가블록으로포함된후조작을가해이중지불이생기는경우또는정상거래와불법거래가서로다른블록에포함되는경우는탐지하지못한다. 논문의구성은다음과같다. 먼저 2장에서블록체인에대해간단히설명한후, 3장에서제안하는이중지불탐지방법을기술한다. 제안방법을검증한프로토타입구현을통한실험및제안방법의시간오버헤드에대해 4장에서다룬후 5장에서결론을맺는다. 2. 블록체인 2.1 트랜잭션트랜잭션은거래내역을의미하며, 임의의노드에서트랜잭션발생시네트워크를통해연결된모든노드들에게전달된다. 각트랜잭션은고유한식별자인 TXID를가진다. 그림 1에서알수있듯이각트랜잭션은이전트랜잭션출력이새트랜잭션입력으로참조되고그트랜잭션의출력으로연결된다. 2.1.1 입력입력은이전트랜잭션의출력에대한참조와서명스크립트 (signature script), 그리고일련번호로구성된다. 트랜잭션은하나이상의입력을가지며, 입력들값의합은출력값합보다같거나커야한다. 2.1.2 출력출력은값 (value) 과공개키스크립트 (pubkey script) 로구성된다. 트랜잭션은하나이상의출력을가지는데, 두개이상의입력이하나의출력에결합될수있다. 트랜잭션의각출력은다음트랜잭션의입력으로한번만참조될수있으며, 한트랜잭션에서전체입력값합은전체출력값합과같다. 그림 1 트랜잭션구조 Fig. 1 Transaction structure
850 정보과학회논문지제 45 권제 8 호 (2018. 8) 2.2 블록거래가발생할때마다블록체인네트워크로브로드캐스트된트랜잭션들은마이너 (miner) 라고불리는노드들이모아서블록으로만든다. 트랜잭션들은블록에포함됨으로써확인 (confirm) 되었다고말한다. 새롭게생성되는블록은이전블록에연결되며참조가능하다. 이러한블록들의연결을블록체인이라한다. 새로운블록을만들려면그블록의해시값을계산해내야한다. 이해시값계산은큰연산작업이필요하다. 예를들어현재비트코인의경우평균 10분의연산시간이필요하다. 어떤트랜잭션을조작하려면조작한트랜잭션이포함된블록이후의모든블록을조작해야한다. 블록의연결개수가많을수록비용이많이들게되어조작하기힘들어진다. 2.3 블록체인분기여러마이너들이블록생성을시도하기때문에거의동시에서로다른블록을만들어낼수있다. 뿐만아니라이중지불공격자에의해고의로조작된블록이만들어질수도있다. 서로상충된블록이수신되면노드들은일단이들을모두이전블록에연결하기때문에그림 2에서와같이 101번블록에서로다른 102번블록이연결된형태인블록체인의분기 (fork, split) 가발생한다. [8] 에서실제비트코인의 180,000번에서 190,000번사이의블록을추출하여실제분기회수를조사하니 100,000개블록에서 1690번의분기 (1.69%) 가발생하였다. 약 60개블록마다평균한번씩분기가발생한셈이므로분기가자주발생하는현상이라고할수있다. 수학적모델에서의산출한결과도 1.78% 로제시되었다. 분기된블록체인들중항상가장긴체인이선택된다. 긴블록체인일수록조작하기힘드니신뢰할수있다는논리에기반한다. 2.4 이중지불이중지불은어떤트랜잭션이발생하고블록에포함됨으로써확인된후에, 공격자가상충된블록을만들어네트워크에전파하고, 빠르게후속블록들을만들어더긴체인을형성시키면된다. 그림 2에서트랜잭션 A C 가공격자에의해조작된트랜잭션이고 A B가정상적인트랜잭션이라고할때, 공격자가 A C 트랜잭션이포함된 102번블록이후의다음블록들을빠르게만 들어내면정상체인보다길어질수있다. 블록체인은항상가장긴체인을선택하기때문에이중지불이포함된블록체인이정상적인체인보다앞서나가긴체인을형성하게되면불법거래가정상으로승인된다. 2.5 이중지불성공가능성 [1] 에서는공격자가정상체인보다더긴체인을형성할수있다고이미예견하였고그에대한성공확률식을도출하였다. 정직한노드가다음블록을만들확률을, 는공격자의노드가다음블록을만들확률, 가 개의다음블록들을빨리만들확률이라고할때, 공격자가정상체인을따라잡을수있는확률은기댓값이 인 Poisson 분포를따르며, 식 (1) 과같다. (1) 표 1 이중지불의성공가능성 Table 1 The probability of successful double-spending 표 1은공격자가더긴체인을형성할수있는가능성에대한식 (1) 에서, 개블록에따라계산한표이다. 결과는조작할블록개수 가커질수록공격자의이중지불성공가능성은지수적으로감소한다. 하지만 가증가할수록성공할확률이높아지고, 50% 일때이중지불성공확률이 100% 로계산된다. 블록을만들려면큰연산작업이필요하기때문에대부분의노드들은서로협력하여블록보상을나눠갖는마이닝풀 (mining pool) 형태를이룬다. 최근상위 3개의주요마이닝풀의연산능력합은 51.9% 이다 [9]. 이는이중지불위협에대해노출되어있는것을보여준다. 또한공격자가더긴체인을형성하기위한가능성을 0으로줄이는것은불가능하다 [4]. 언제나이중지불가능성이존재하기때문에이중지불로인한피해를줄이기위해서는이를신속하게탐지하는방법이필요하다. 3. 이중지불탐지방법 그림 2 블록체인분기 Fig. 2 Blockchain Forking 3.1 트랜잭션역추적트랜잭션은고유한 TXID를가지고있다. 트랜잭션의
블록체인의이중지불탐지알고리즘 851 입력과출력이연결되어있어 TXID를이용하여참조할수있다. 트랜잭션의 TXID를이용하여 IN에서 OUT으로의연결을지속적으로따라갈수있으므로모든트랜잭션은블록들에서찾아낼수있다. 3.2 알고리즘이중지불트랜잭션을블록체인에포함시키는공격이시도될경우, 임의의노드는기존에자신이가지고있던블록체인과공격자에의해만들어진분기된블록체인을가지게된다. 분기가되는시점에서일반적으로어느것이정상인지즉시알수없다. 노드가먼저가진블록체인을 Active라하고, 분기된블록체인을 Forked라고할때, 블록체인에복수개분기가발생할때만이중지불이발생할가능성이있으므로, 분기상태를전제조건으로이중지불여부를검사하는알고리즘을실행한다. 본논문에서제안하는알고리즘의개요는다음과같다. 1. 블록체인의분기여부확인 2. 분기된지점의블록에포함된트랜잭션을 Active 와 Forked로분류 3. 블록안의트랜잭션정보를모두탐색하여이전트랜잭션의 OUT과다음트랜잭션의 IN의 TXID를묶어저장 4. Active 블록내트랜잭션들과 Forked 블록의트랜잭션들을 1:1 비교 5. 두트랜잭션의 OUT TXID가같고 IN TXID가다른경우 ( 이중지불 ) 가찾아질때까지 4, 5 반복 6. 이중지불검출후연결된모든노드들에게경고메시지전달이중지불여부를파악하기위해가장먼저블록체인의분기여부를확인해야한다. 이중지불이발생하려면반드시분기가생기기때문이다. 표 2에서 2번줄은서로상충된블록을검사하기위해분기가발생한높이 (height) 의블록들을가지고온다. 4에서 15번까지줄은 Active 블록과 Forked 블록에포함된트랜잭션들을따로분류한다. 각트랜잭션은이전트랜잭션과연결된구조로되어있으므로각트랜잭션의 IN TXID와해당트랜잭션과연결되어있는이전트랜잭션의 OUT TXID를묶어서하나의자료형으로저장한다. 이때코인베이스 1) 트랜잭션은이전트랜잭션을가지지않기때문에제외시킨다. 17에서 21번까지줄은 Active와 Forked로분류되어있는 TXID(OUT, IN) 를같은 OUT을가지면서다른 IN값을가지는트랜잭션이있는지그림 3과같이 1:1로비교하는완전탐색 (brute-force search) 을수행한다. 1) 블록을생성하면보상으로주어지는첫번째트랜잭션. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 표 2 이중지불탐지알고리즘 Table 2 Double-spending detection algorithm detectdoublespending() { settips <- get all block for (block : settips) { if (block state is active chain) { txs <- get all transaction in block for (tx witout coinbase : txs) activetxinfo <- add txid(tx out, tx in) } else if (block state is forked chain) { txs <- get all transaction in block for (tx witout coinbase : txs) forkedtxinfo <- add txid(tx out, tx in) } } for (activetxid(out, in) : activetxinfo) for (forkedtxid(out, in) : forkedtxinfo) if ( (activetxid.out == forkedtxid.out) && (activetxid.in!= forkedtxid.in) ) return broadcast warning message if double-spending not found, set flag on if next block received and flag on, then execute this algorithm } 그림 3 트랜잭션들의비교 Fig. 3 Comparison of transactions 비교하는두트랜잭션이, 이전트랜잭션의 OUT TXID 가서로같고현재트랜잭션의 IN TXID가서로다를때이중지불에해당한다. 하나의출력이두개의입력으로참조되었으므로하나의전자화폐로 2번이상의거래를수행한것이다. 이경우, 다른노드들에게이중지불발생상황을알리기위해경고메시지를전파한다. 23에서 25번까지줄은분기된높이의블록에서이중지불이탐지되지않을경우, 후속블록에서이중지불이발생할수있기때문에잠재적위험을나타내는 flag를설정하고새블록이들어오면다시검사를한다. 3.3 탐지후경고이중지불이탐지되면이사실을네트워크의모든노드들에게전파한다. 노드들간에통신을하기위해비트코인에서사용하는프로토콜을기준으로경고메시지형식을정의하였다.
852 정보과학회논문지제 45 권제 8 호 (2018. 8) 그림 4 메시지구조 Fig. 4 Message structure 현재비트코인에서노드들의통신에사용하는메시지의프로토콜구조는그림 4와같다. 메시지타입을나타내는 Command Name을 doublespend 로정의한다. Payload에는경고메시지를받은노드가어느위치에서이중지불이일어났는지알수있는최소한의정보를포함한다. Payload에포함되는정보는다음과같다. 1. 이중지불이발생한블록의번호와해시값 2. 이중지불에해당하는트랜잭션의 TXID 경고메시지는이중지불을가장최초로탐지한노드가자신과연결된모든노드들에게전파한다. 경고메시지를받은노드들은메시지의타입을나타내는 Command Name이 doublespend 인것을확인하고, Payload에포함된이중지불에해당하는블록과트랜잭션이어느것인지확인할수있다. 경고메시지를받은노드들은 Payload에포함된정보를가지고, 블록체인응용에서정의한대로대처한다. 4. 구현및분석 4.1 구현환경오픈소스로공개된비트코인코어 [10] 의소스를일부수정하여제안하는알고리즘을구현하고검증하였다. 비트코인에서제공하는테스트네트워크환경중실제로 사용되는비트코인환경과같은 Regtest 네트워크환경을선택하였다. 실험을위해 3대의노드로로컬네트워크를구성한후알고리즘을적용하여패킷분석프로그램 Wireshark 와콘솔을통해출력되는정보를통하여결과를확인하였다. 4.2 이중지불생성비트코인의테스트네트워크 Regtest에서실제로생성된 101개의정상적인블록들을가져와실험에이용하였다. 이중지불을쉽게만들기위해서 101개의블록에서는특별히다른트랜잭션을만들지않고코인베이스트랜잭션만사용하였지만실제로일반적인트랜잭션에서도이중지불을탐지할수있다. 이중지불상황을만들기위해인위적으로이중지불을포함한블록을생성해정상블록체인에분기시켰다. 블록체인을분기시킬때는두개이상의노드에서동시에블록을생성하면된다. 일반적으로하나의노드에서는두개이상의트랜잭션을서로다른블록에포함되도록만들수없다. 따라서두개이상의노드에서실험을진행하였다. 이중지불을만들기위한실험시나리오는다음과같다. 1. 3개의노드 A, B, C를로컬네트워크연결 2. 각각의노드는 Wallet(Bitcoin Address) 을생성 3. A가 101개의블록을생성 (A, B, C는 101개의블록체인을공유 ) 4. 3개노드의네트워크연결을모두끊음 5. A가 B의주소로비트코인을전송하는트랜잭션을만듦 (A는 1번블록의코인베이스트랜잭션을사용 ) 6. A가아닌다른노드 (B 또는 C) 에서 A의 Wallet 을복사하여적용함으로써임시로두개의 A 노드를만든후, A가 C의주소로비트코인을전송하는트랜잭션을만듦 ( 이중지불트랜잭션 ) 7. 두개의 A 노드는각자만든트랜잭션을포함한블록을생성 8. 3개노드의네트워크를모두연결 9. 두개의 A 노드가만든 102번블록을동시에전파 ( 블록체인분기 ) 그림 5 이중지불트랜잭션의연결구조 Fig. 5 Linked structure of transactions in double-spending
블록체인의이중지불탐지알고리즘 853 3번까지의과정은노드가만들어내는블록을네트워크를통해연결된다른노드에게전파하여모든노드가같은블록을공유할수있는일반적인과정이다. 4번과정은연결된노드들의네트워크를끊어블록과트랜잭션이생성되더라도공유되지않도록만든다. 5번과정에서 A 노드는최상위블록체인 (best blockchain) 2) 의높이가 101인상태에서 102번째블록안에포함될 A B의트랜잭션을발생하는데이는그림 5에서와같이 1번블록의코인베이스트랜잭션과연결된다. 비트코인에서는코인베이스트랜잭션을 100개의블록이만들어진후에사용할수있다. 실험을위해서 101개의블록에특별히다른트랜잭션을만들지않았기때문에 101번이전의 100개의블록에는코인베이스트랜잭션만존재한다. 따라서최상위블록체인의높이가 101인상태에서는 100개이전블록인 1번블록의코인베이스트랜잭션만사용할수있다. 6번과정은새로운노드에서 A의 Wallet을적용하기때문에해당노드는 A의정보그대로가지게된다. 하지만 5번과정에서만들어낸트랜잭션은네트워크를통해공유되지않았으므로현재노드에서는이에대한트랜잭션정보를가지고있지않다. 따라서새로운노드에서 A가트랜잭션을발생시키면 102번째블록안에포함될 A C의트랜잭션이그림 5에서와같이 1번블록의코인베이스트랜잭션과연결된다. 7, 8, 9번째과정은 6번까지과정에서 A 노드가만들어낸 A B 트랜잭션과 A C 트랜잭션을포함하는서로다른블록들이, 네트워크에연결되면서 B와 C 노드에게동시에공유되게만드는것이다. 이는서로다른노드에서 A가만들어낸두블록을동시에전파시키므로블록체인이분기되면서 1번블록의코인베이스트랜잭션에서서로다른트랜잭션으로연결되는이중지불을만들어낸다. 4.3 검출결과이중지불탐지알고리즘의실험결과, 콘솔에출력되는블록과트랜잭션들의정보들을파악하여이중지불여부를확인하였다. 또패킷분석프로그램인 Wireshark 를통하여본논문에서정의한경고메시지가전달되는지확인하였다. 4.3.1 블록체인분기그림 6은최상위블록체인의정보이다. 두개의 102번블록을동시에받아들여블록체인의분기가일어났다. 첫번째체인은 Active이며, 두번째체인은 Forked이다. 그림 7은두개의 102번블록의상세한정보이다. 두블록의해시값은 3731-, 1077-로시작하며서로다르다. 2) 재생성하기어려운가장긴블록체인. 그림 6 최상위블록체인정보 Fig. 6 Best blockchain 그림 7 102번째 Active와 Forked 블록정보 Fig. 7 Active and Forked block #102 그러나이전블록의해시값은 4a73-으로서로같다. 이러한블록체인형태는그림 5와같이두개의서로다른 102번블록이 101번블록을이전블록으로가지는것으로블록체인이분기가되었다는것을보여준다. 4.3.2 이중지불확인그림 8에서 TXID가 65d0-인트랜잭션은해시값 3731-인블록에포함되어있다. 또 TXID가 69fc-인트랜잭션은해시값 1077-인블록에포함되어있다. 두트랜잭션은분기된체인의블록에각각포함되어있는형태이다. TXID가 334b-인트랜잭션은 1번블록에포함되어있는것을그림 9에서확인할수있다. 이트랜잭션은 1 번블록이생성될때처음만들어지는코인베이스트랜잭션이다. 그림 8의 TXID 65d0- 트랜잭션과 69fc- 트랜잭션은자신의 IN이참조하는이전트랜잭션의 OUT TXID가서로 334b-로같고이는 1번블록에포함되어있는코인베이스트랜잭션이다. 따라서그림 5에서 A B 트랜잭션과 A C 트랜잭션이이중지불에해당한다. 4.3.3 경고메시지전파이중지불을탐지한노드는경고메시지를자신과연결된노드에게전파한다. 경고메시지는네트워크를통해전파되므로블록체인을기반으로하는응용프로그램 ( 비트코인, 이더리움 [11] 등 ) 마다통신에사용되는프로토콜을이용한다. 그림 10은이중지불을탐지한노드가경고메시지를
854 정보과학회논문지제 45 권제 8 호 (2018. 8) 그림 8 각블록에포함된트랜잭션정보 Fig. 8 Transactions contained in each block 그림 10 경고메시지패킷 Fig. 10 Warning message packet 그림 9 1번째블록정보 Fig. 9 Block #1 전송할때패킷을 Wireshark 에서캡처한것이며, 설계한대로경고메시지안에이중지불이발생한블록과트랜잭션의정보가포함되어있는지확인할수있다. Command name은 doublespend 이고 Payload에는이중지불정보가담겨있다. 첫번째블록의번호는 102이고, 해시값은 3731-이며, 트랜잭션 TXID는 65d0-이다. 두번째블록의번호는역시 102이고, 해시값은 1077-이며, 트랜잭션 TXID는 69d0-로실험에서보인값과일치한다. 4.3.4 탐지시간오버헤드본논문에서제시한탐지알고리즘을실행하는데소요되는시간오버헤드는 이다. 은 Active 체인블록의트랜잭션개수와 Forked 체인의블록내트랜잭션개수중적은수이다. 비트코인의경우블록하나에포함될수있는최대트랜잭션개수는약 2,700개정도이다. 최악의경우 2,700 2,700=7,290,000번트랜잭션비교가필요하다. Intel Core i7 6950X를예로들면실행속도가 3.0 GHz에서 317,900 MIPS이다 [12]. 이는 3억 1,790만인스트럭션을실행하는데 1ms가걸린다는의미이다. 최대 7,290,000번의트랜잭션비교에필요한시간은그리크지않음을예상할수있으나, 실제측정을통해분석해보았다. 그림 11은본논문에서제시한탐지알고리즘실행시간을트랜잭션개수에따라측정한그래프이다. Active 체인과 Forked 체인의블록에포함된트랜잭션의최대개수 2700개를비교한결과 1.034s의시간이걸렸다. 이는비트코인에서블록이만들어지는시간 10 분에서 1/600 정도이다. 본논문에서제시한이중지불탐지알고리즘은블록을새로받았을때분기가발생하면실행된다. 알고리즘의실행시간은이중지불을발견하그림 11 알고리즘실행시간 Fig. 11 Execution time of an algorithm
블록체인의이중지불탐지알고리즘 855 지못하여모든트랜잭션을비교할때최악의경우로가장오랜시간이걸린다. 비트코인에서평균 60개블록 [8], 즉 600분마다분기가발생하므로, 600분에서 1.034s 정도의실행시간은블록체인시스템에영향을줄정도의큰오버헤드는아니라고판단한다. 5. 결론 블록체인을기반으로한전자화폐시스템은분기된체인들중가장긴체인을선택하는방식을취하기때문에낮은확률이지만여전히이중지불이발생하는가능성이존재한다. 본논문에서는블록체인시스템을기반으로하는비트코인의오픈소스를사용하여이중지불이발생하면가능한한일찍탐지하여노드들에게알림으로써이중지불에의한피해를줄이는데방법을기술하였다. 블록이새로수신될때마다실행되는이중지불탐지알고리즘과문제가되는거래를네트워크의모든노드들에게알릴수있는경고하는방법을소개하였다. 모든노드들은경고메시지기능을통하여이중지불의발생여부를알수있지만어떤트랜잭션이부정한거래인지알수는없다. 하지만거래당사자들에게이상황을경고하여응용프로그램이나블록체인운영관리기능차원에서조치하여피해를줄일수있다. 또한본방법으로인해블록을만드는노드는부당한블록으로인해분기된체인에서의불필요한마이닝작업을피할수있다. 일반노드는기존의전자화폐시스템에서거래를한후다음거래를위해기다려야하는시간을줄일수있는장점이있다. References [1] S. Nakamoto, "Bitcoin: A Peer-to-Peer Electronic Cash System," [Online]. Available: https://bitcoin.org/ bitcoin.pdf, 2008. [ 2 ] Bitcoin, "Bitcoin Developer Guide," [Online]. Available: https://bitcoin.org/en/developer-guide (Accessed on Oct. 10, 2017) [3] Bitcoin wiki, "Weaknesses," [Online]. Available: https://en.bitcoin.it/wiki/weaknesses (Accessed on Nov. 30, 2017) [4] M. Resenfeld, "Analysis of hashrate-based doublespending," arxiv preprint arxiv:1402.2009, 2014. [5] Corda, "How does Corda solve the double spending problem?," [Online]. Available: https://discourse.corda. net/t/how-does-corda-solve-the-double-spendingproblem/1137 (Accessed on Nov. 30, 2017) [6] H. Lee, S. Lee, "Bitcoin`s trust structure and double-spending threats," Review of The Korea Institute of Information Security and Cryptology, Vol. 26, No. 2, pp. 25-30, 2016. (in Korean) [7] C. Pérez-Solà, S. Delgado-Segura, G. Navarro- Arribas, J. Herrera-Joancomartí, "Double-spending Prevention for Bitcoin zero-confirmation transactions," IACR Cryptology eprint Archive, 2017. [8] C. Decker, R. Wattenhofer, "Information Propagation in the Bitcoin Network," Proc. of the 2013 IEEE 13th International Conference on Peer-to-Peer Computing (P2P), Sept. 2013. [9] An estimation of hashrate distribution amongst the largest mining pools, [Online]. Available: https:// blockchain.info/pools (Accessed on Dec. 12, 2017) [10] Bitcoin Core, [Online]. Available: https://github.com/ bitcoin/bitcoin (Accessed on Jul. 11, 2017) [11] Ethereum White Paper, "A Next-Generation Smart Contract and Decentralized Application Platform," [Online]. Available: https://github.com/ethereum/wiki /wiki/white-paper (Accessed on Oct. 10, 2017) [12] Intel InGaAs FTW, "Core i7-6950x Extreme Edition Deca Core benchmarks. About 6% IPC gains over Haswell-E," cpubenchmark, passmark, cpuboss, geekbench, cinebench, Oct. 2016. 김민호 2012 년 ~ 현재충남대학교컴퓨터공학과재학 ( 학사 ). 관심분야는분산네트워크, 컴퓨터알고리즘 김수진 2018년충남대학교컴퓨터공학과졸업 ( 학사 ). 관심분야는모바일개발, 네트워크, 가상현실 최훈 1983년서울대학교컴퓨터공학과졸업 ( 학사 ). 1990년 Duke University 전산학과졸업 ( 석사 ). 1993년 Duke University 전산학과졸업 ( 박사 ). 1983년~1996년한국전자통신연구원광대역통신망연구부근무. 1996년~현재충남대학교컴퓨터공학과교수. 2000년미국 NIST(National Institute of Standards and Technologies) 객원연구원. 2012년~2014년충남대학교정보통신원장. 2015년~2017년충남대학교 SW 중심대학사업단장. 관심분야는모바일컴퓨팅 / 분산시스템미들웨어, 운영체제, 컴퓨터통신