Introducton to Error-Correcton Codes Proof-of-Work 박상준, 김형성, 1 이흥노 {sjpark1, hyoungsung, heungno}@gst.ac.kr 광주과학기술원 1. Introducton 2008 년신원미상의사토시나카토모는백서 [1] 를통해탈중앙화된 즉신뢰받는기관이없는 화폐시스템을소개하고, Peer-to-Peer (P2P) 네트워 크를통해구현하였다. 이것이최초의암호화폐인 비트코인이고, P2P 네트워크에서의이중지불을막 기위해블록체인을사용하였다. 블록체인이란블록들이하나의체인으로써연결된것을뜻한다. 각블록들은거래내역 ( 데이터 ) 을담고있고, P2P에존재하는불특정다수노드들에의해검증받는다. 검증하는노드들을채굴자라일컫고, 이검증과정을작업증명이라한다. 작업증명의목적은다수의채굴자들이하나의블록을채굴 즉검증 하기위해많은노력을했다는것을입증하기위함이다. 비트코인의경우, SHA256 (Secure Hash Algorthm) 함수의특정해쉬값을산출하게하는 nonce를찾음으로써작업증명이완료된다. SHA256의출력값을통해역으로입력값을알아내는것이불가능하므로, 채굴자들은무차별적으로 nonce들을대입해야한다. SHA256의출력값인해쉬값은블록간의연결을위해사용된다. 이전블록의해쉬값을현재블록내역에포함시킴으로써인접한블록들을연결시킨다. 이와같이연결하여채굴된블록들의위 변조를어렵게만들고, 이를통해이중지불을막는다. 초창기비트코인의작업증명은 CPU를통해서이뤄졌다. 이시기는사토시가백서에서언급한것처럼, 어느누구나 CPU만있다면공정한채굴경쟁이가능하였다. 비트코인이세상에알려지고, 채굴이윤이발생함에따라채굴경쟁이시작되었고, 2010년, 2013년각각 GPU와 ASIC (Applcaton- Specfc Integrated Crcut) 채굴장비들이등장하였 1 교신저자 다. ASIC 채굴의성능은 CPU/GPU 보다월등하였기때문에, 채굴난이도의급격한상승을야기하였다. 결국 CPU/GPU 채굴자들은더이상이윤창출이불가능해졌고, 오늘날의비트코인채굴은 ASIC 을통해이뤄진다. ASIC 채굴로전환됨에따라일반사람들혹은자본이적은사람들은채굴에서배제되고, 막대한자본력을가지고있는소수의집단들이채굴을독점하였다. 이집단들이전세계의채굴능력을많이점유하면 ( 극단적인예로써, 51% 이상 ), 이중지불등을수행하여악의적인용도로블록들을채굴하고, 채굴된블록들을위 변조할가능성이존재하게되는것이다. ASIC 채굴을억제하기위한새로운작업증명들 [3][4] 이제안됐지만, 결국 ASIC 채굴장비들이등장하였다. 오류-정정부호 [6] 는무선통신에서발생하는오류를정정하기위해사용된다. 대표적인부호들중하나로 LDPC [5] 부호가있다. 문헌에따르면, LDPC 디코더의 ASIC 구현은구조적 / 비용적문제로인하여, 구현의유연성이떨어진다 [7]. LDPC 디코더와해쉬함수를결합한오류-정정부호기반의작업증명 [2] (ECCPoW, Error-Correcton Codes Proof-of-Work) 을제안하였다. 본특집호의목표는 ECCPoW의동작과정과 ASIC 채굴장비의등장을어떻게억제하는지설명하는것이다. 본특집호는다음과같이구성되었다. 2장에서는 ASIC 장비등장을억제하기위한작업증명들을소개하고, 이들의한계점을보여준다. LDPC 부호및디코더에관한문헌결과를보고한다. 3장에서는 ECCPoW의동작과정과 ASIC 채굴장비등장억제의요인을설명한다. 4장에서는확률적분석을통해 ECCPoW의작업증명완료가쉽지않다는것을보여준다. 5장에서본특집호의결론을제시한다. 2. Background 본섹션에서는 ASIC 채굴장비등장을억제하기위한작업증명들 (Ethash와 X11) 과한계점들을소개한다. LDPC 부호및디코더소개와, ASIC 디코더에대한문헌들을제공한다. 이문헌들을제공하는이유는 ECCPoW의 ASIC 채굴장비억제기능이 LDPC 디코더에서기인하기때문이다. 2.1. Ethash [3] and X11 [4]
이더리움의작업증명인 Ethash [3] 는비선형그래 프 (DAG, Drected Acyclc Graph) 를이용하여 ASIC 채굴장비등장을억제하였다. 이 DAG 는 30,000 블록단위로무작위로생산되는데이터들의집합 으로써, 2019 년 5 월기준, DAG 의크기는약 3 기가 바이트이다. 표 1은 Ethash의동작과정을보여준다. Nonce와 BH ( 블록헤더 ) 를활용하여해쉬값을생산하고, 이값은 mx0에저장한다. 이과정이 Step 2이다. Step 4에서는 DAG로부터데이터 (data1) 를읽어온다. 읽어올데이터위치는 mx0에의해결정된다 Step 5에서는 data1과 mx0를 mxng 함수에넣고얻은결과를 mx0에저장한다. Step 4부터 5까지총 63번반복수행하고, 최종적으로얻은 mx0를사용해작업증명완료유무를판단한다. 63번의반복수행에서의 mxng 함수는 ASIC을통해처리가능하다. 데이터읽기연산은 ASIC와무관하다. 더욱이, 어떤데이터를읽어오는지미리알수없고, DAG의크기가너무크기때문에캐쉬를이용해빠르게읽는것또한불가능하다. 따라서, 데이터읽기와 mxng 함수실행사이에서병목현상이발생한다. 이병목으로인해, ASIC 채굴장비를사용할필요가없던것이었다. 하지만병목이해결되면, ASIC 채굴장비를활용해좀더빠른채굴이가능해진다. 문헌조사에따르면, 2018년 7 월비트메인은 ASIC 장비를공포하였다. 대쉬의작업증명인 X11 [4] 은다수의해쉬함수들을사용하여 ASIC 채굴장비등장을억제하였다. 이 X11은다음함수들이순차적으로사용한다 : Blake, Bmw, Groestl, Jh, Keccak, Sken, Luffa, Cubehash, Shavte, Smd and Echo 표 2는 X11의동작과정을보여준다. Nonce와 BH 를이용하여 Blake의해쉬값을얻는다. 얻어진값을 Bmw의입력값으로사용한다. 이과정을반복하여최종적으로 Echo의해쉬값을얻고, 이해쉬값을통해작업증명완료유무를판단한다. X11에서사용되는해쉬함수들의순서는고정이다. 따라서 ASIC 채굴장비를개발하려면, 함수들을구현하고, 연결하면된다. 2014년과 2016년사이에는하드웨어생산비용문제로, ASIC 채굴장비개발이억제되었다. 하지만, 공정기술발달로저비용생산이가능해짐에따라, ASIC 채굴장비 표 1. Ethash 의사결정코드 Inputs: BH, L and DAG Step 1: for nonce = 0, 1, 2, 2 32 1 Step 2: mx0 = ( SHA3( nonce, BH) ) Step 3: for = 1, 2,, 63 data1 = Fetch DAG,mx0 Step 4: ( ) Step 5: mx0 = Mxng ( mx0,data1) Step 6: end Step 7: If mx0 begns wth L zero bts, then break. Step 8: end BH는블록헤더, L은주어진난이도. 해당의사결정, 코드는본연구팀의논문인 [2] 로부터인용. 표 2. X11 의사결정코드 Inputs: BH and L Step 1: for nonce = 0, 1, 2, 2 32 1 Step 2: e = Blake( nonce, BH) Step 3: e= Bmw ( e ). Step 12: e= Echo( e ) Step 13: If e begns wth L zero bts, then break. Step 14: end BH는블록헤더, L은주어진난이도. 해당의사결정, 코드는본연구팀의논문인 [2] 로부터인용. 가 2016 년부터판매되고있다. X11을확장하여 X13, X14, X15 그리고 X17 작업증명들이제안되었다. 이름에서알수있듯이, 별도의함수들을추가적으로사용하여 ASIC 채굴장비등장을억제하는것이다. 2019년, X17을제외한작업증명들의 ASIC 채굴장비가판매되고있다. 2.2. LDPC 부호와디코더 대표적인오류정정부호중하나인 LDPC [5] 부호는대부분의원소값이 1인패리티체크행렬 H 0,1 m n (PCM, party check matrx) 를이용해정 { } 의된다. 구체적으로, PCM이주어졌을때, 다음조건을만족시키는 벡터들 { } 1 { c Hc 0 c { } } : = = 0,1 n 1 c 0,1 n 의집합이 LDPC 부호이다. PCM을이용해 LDPC 부호를이분그래프로표현할수있다. 이그래프는, 변수 (varable) 및체크 (check) 노드들과이들을연결하는선으로구성된다. 변수 / 체크노드들은 PCM의열 / 행에각각대
응한다. PCM 의 (, j) 번째원소값이 1 이면 번째변 수노드와 j 번째체크노드가연결된것을뜻한다. LDPC 부호의성능 얼마나많은오류들을고치는지 은 PCM의최소해밍거리 d (mnmum hammng dstance) 에의해결정된다. 이값은 PCM 을통해생성할수있는 0 벡터를제외한모든부호들중에가장적은해밍값이다 : d = mn u u u 0, 여기서 k = n m, c 는 번째부호, 부호의개수는총 2 k, 그리고벡터 x 의해밍값은다음과같다 : x : x에포함된 1의개수. h = PCM의최소해밍거리 d가주어지면, LDPC 부호를활용해정정할수있는 bts 오류들의숫자는다음과같이결정된다 : ( d ) h t = 1 2 (1) 여기서 x 는 x의정수를표시한다. 위의결과의유도과정은 [6] 에있다. LDPC 부호가무선채널을통해전송되면, 채널에존재하는잡음으로인하여오류가발생한다. 잡음에의해왜곡된부호 y는다음과같이표현할수있다 : 여기서 e { } y = c+ e 0,1 n 는잡음에의한오류벡터이고그 리고 c는전송된부호이다. LDPC 디코더의목적은오류를정정하여, 원부호 c를찾는것이다. 이디코더는일반적으로메시지전달 (message passng) [6] 알고리즘을사용한다. 이알고리즘은변수 / 체크노드들이서로메시지를반복적으로주고받으며원부호를찾기위해노력한다. 일반적으로, 알고리즘들을빠른속도및저전력으로실행시키기위해, ASIC 장치를사용한다. 따라서, LDPC 디코더또한 ASIC을사용해구현된다. ASIC-LDPC 디코더에서는변수및체크노드들이 PCM에따라물리적으로연결된다. 따라서, 부호의길이의변화에따라노드들을늘리거나혹은 PCM 변화에따라유동적으로노드들의연결을재설정 하는것이쉽지가않기때문에, 다수의 PCM들을지원하는 ASIC-LDPC 디코더구현은어렵다. 최신리뷰논문 [7] 에따르면, 추가적인하드웨어장치들을이용하면다수의 PCM들을지원하는 ASIC-LDPC 디코더를구현할수있다고보고하였다. 하지만, 그로인해디코더면적혹은생산비용이증가되는문제가발생한다고보고했고, 그사례로써 [8] 에서구현된 ASIC-LDPC 디코더를소개했다. 이디코더는약 100 개의 PCM들을지원하지만, 추가적인장치들이디코더면적의약 75% 를점유하는문제를가지고있다. 더많은 PCM들을지원하려면더많은장치들이사용되고, 그로인해 ASIC-LDPC 구현이매우비효율적이다. 마지막으로, [7] 에는 ASIC-LDPC 디코더의구현사례들이표로제시되어있다. 이표에서부호의길이가가장긴경우는 n = 64,800로써, 해당디코더는 [9] 에구현되어있다. 3. 오류-정정부호기반의작업증명본섹션에서 ECCPoW 동작과정을간단히소개하고, ASIC 채굴장비등장의억제요인을설명한다. ECCPoW에관한자세한설명및이론적분석결과들은 [2] 에있다. 원활한설명을위해용어들을다음과같이축약한다. 현재블록헤더와이전블록헤더를각각 CBH (current block header) 와 PBH (prevous block header) 로사용한다. 먼저, ECCPoW에포함된 LDPC 디코더와그입력값을다음과같이각각정의한다. 정의 1. 크기가 m n인 PCM H와길이가 n인해쉬벡터 r이주어졌다가정한다. LDPC 디코더는 H와 r을취득하고, 메시지전달알고리즘을사용해길이가 n인벡터 ĉ 을산출한다 : n { rh} c ˆ { } 1 :, 0,1. (2) MP 정의 2. 길이가 n인해쉬벡터 r은다음과같이정의된다 : [ n] s1 1: f n 256 r : = s1 sl sl+ 1[ 1: j] f n > 256 여기서 l = n 256, j = n 256 l, (3)
1 ( ) { } 256 s : = SHA256 nonce,cbh 0,1 (4) 그리고, u = 2, 3,..., l + 1 에대해 = u 1 ( ) { } 256 s : SHA256 s 0,1. (5) 하나의블록을채굴하기위한작업증명에서는, CBH 와 PCM 은모두상수로써취급된다. Nonce 가 변경되면, 정의 2 에나온것처럼해쉬벡터가재 생성되고, 그로인해디코더의출력값이변경된다. Nonce 와디코더의입력값인해쉬벡터의관계는 SHA256 함수들에결정된다. 따라서 nonce 만보고 디코더의출력값이무엇인지미리예측하는것은 불가능하다. 특정조건을만족하는디코더의출력 값을찾으려면무수히많은 nonce 들을대입해야 한다. 결론적으로 ECCPoW 의작업증명은디코더의 출력값 ĉ 이다음조건 Hcˆ = 0 (6) 을만족하게하는 nonce 를찾으면완료된다. ECCPoW 가어떻게동작하는지살펴보았다. 이제 LDPC 디코더의입력값으로써활용되는 PCM 에 대해논의한다. 블록들을채굴할때, 하나의 PCM 사용을가정한다. 섹션 2 에서이야기한것처럼, 이가정에서는 ASIC-LDPC 디코더구현에아무런 문제가없다. 하지만, 이가정하에서는, ECCPoW 를 위한 ASIC 채굴장비가등장할수있다. 이제, 매블록채굴할때마다무작위로생성된 PCM 사용을가정한다. 섹션 2에서언급한것처럼, 다수의 PCM을위한 ASIC-LDPC 디코더구현에는추가적인하드웨어장치들이필요하다. 더욱이, 각 PCM들이무작위로생성된다. 따라서어떤형태로생성될지예측할수가없다. 매블록마다변하는 PCM을사용하면, 결국 ASIC-LDPC 디코더구현을억제할수있다. 이것이 ECCPoW에서 ASIC 채굴장비등장을억제하는이유이다. 이제부호의길이에대해논의를해보자. 부호의길이인 n인경우, ASIC-LDPC 구현을위해필요한 computng fabrc의총량은 n의제곱에비례한다. 가령 n을 2배키우면, 필요한총량은 4배이다. 또한, n은가변적으로변하는값이다. 무수히많은 PCM을지원하는 ASIC-LDPC 구현에성공하더라도, n을크게키움으로써구현된 ASIC-LDPC 디코더의사용을막을수있다. 어떻게하면매블록마다무작위로변하는 PCM을생성할수있을까? 우리의해답은 PBH의해쉬값과 Gallager의 PCM 생성방법 [5] 을동시에이용하는것이다. 이방법은사용하면, 임의의 seed 값이주어졌을때, PCM을결정적으로생성할수있다. 즉, 여러사람들이동일한 seed 값을가지고있으면, 동일한 PCM을생성할수있는것이다. 그리고, PBH의해쉬값은매블록마다바뀌고, 이미채굴된블록이므로, 알려진값이다. 따라서, 이값을 seed로활용함으로써, 매블록마다무작위로 PCM을생성할수있다. [2] 에우리의 PCM 생성방법의의사결정코드및좀더자세한설명들을기록하였다. 4. 해쉬사이클분석 이섹션에서는 ECCPoW 작업증명을푸는것이쉽지않다는것을보인다. 이를다음아래에해쉬사이클을정의한다. 정의 3. 하나의 nonce을이용하여, LDPC 디코더의출력값을산출하고, 이값을이용해작업증명의완료유무를검증하는것까지포함한과정을해쉬사이클로정의한다. 이제작업증명을완료하기위해서총몇번의해쉬사이클이필요한지고려한다. 이섹션의분석결과들은 [2] 에서일부발췌된것이다. 용이한분석을위하여다음 2가지를가정한다. 첫번째로, 디코더는이상적 (optmal) 이다. 즉, 섹션 2에서나온것처럼 t개이하의오류가발생시항상정정가능한것을가정한다. 두번째로, 해쉬벡터와 nonce는서로 1:1 관계로가정한다. 즉, 다른 nonce들은각각다른해쉬벡터를생성한다. 이제 번째부호가주어졌을때, 해당부호와의해밍거리가 t보다작은벡터들의집합을 ( c, t) : = { r: r c t} (7) h 로정의한다. 이집합의크기는다음과같다 n n n n 1 2 t l t ( c, t) = 1+ + + + = l = 0 k 여기서 = 1, 2,..., 2.
첫번째가정으로인하여, 해쉬벡터가 ( c, t) 의원소라면, 출력값이항상 번째부호이다. 즉, MP r ( c, t) { rh} :, c. 따라서, 번째부호를산출할확률은다음과같다 n { cˆ = c } = ( c t) Pr 2, n t n = 2 l = 0 l d 1 n n 2 = 2 l = 0 l 여기서마지막등호는 (1) 에서기인한다. 디코더의 출력값이임의의부호일확률은다음과같다 : { Hcˆ 0 } p : = Pr = k 2 = 1 m { ˆ } = Pr c= c (8) d 1 k n n 2 = 2. l = 0 l LDCP 디코더가부호를출력할확률이 p 이므로, 이것의역수는부호를출력하기위해필요한평균 해쉬사이클이다. 따라서, p 를알면어느정도해쉬 사이클이필요한지계산가능하다. P 를계산하려면, d 를알아야한다. 임의의주어진 PCM 의 d 를찾는 것은어렵다. 우리는편의를위해 d 를 n 의 10% 로 가정한다. 첫번째로, n = 64, m = 32라하자. 이경우 p는약 2 10-10 이다. 이작업증명을완료하기위해필요한해쉬사이클은 p의역수인 4 10 9 이다. 두번째로, n과 m을각각 128과 64로하면, p는 5 10-20 이다. 따라서, 2 10 19 해쉬사이클이필요하다. 이것들은작업증명완료를위해많은해쉬사이클이필요한것을보여준다. 마지막으로, LDPC 디코더의총연산량은 Iter O ( n log n) 여기서 n은부호의길이이고, Iter은메시지전달알고리즘의반복횟수이다. 각 nonce마다디코더를실행하므로, 평균적으로작업증명을완료하기위해사용되는연산량은다음과같다 : 1 ( log ) Iter O n n p 이것을 ECCPoW 의채굴난이도로여길수있다. 4. 결론 본특집호에서는블록체인커뮤니티에서많이주목받고있는 ASIC 채굴장비등장으로인한중앙화문제를고찰하였다. 이문제를해결하기위해제안된오류-정정부호기반의작업증명 [2] (ECCPoW, Error-Correcton Codes Proof-of-Work) 를소개하였다. 이방법의핵심은기존 SHA256함수와 LDPC 디코더를연결한것이다. SHA256의출력값이디코더의입력값이되고, 이디코더의출력값을이용해작업증명의완료유무를판단하였다. ASIC 채굴장비등장의억제는 LDPC 디코더의사용에서기인한다. 매블록마다새로운패리티체크행렬을무작위로생성함으로써, ASIC-LDPC 디코더의구현을현실적으로매우어렵게만든다. 그로인해디코더의실행을 CPU/GPU에의해서만처리되도록설계한것이다. Acknowledgement 이논문은 2019 년도광주과학기술원의재원으로 GRI(GIST 연구원 ) 사업의지원을받아수행된연구임. 이논문은 2019 년도광주과학기술원의재원으로 과학기술응용연구단의실용화연구개발사업 의지원을받아수행된연구임. 참고문헌 [1] S. Nakamoto, Btcon: A Peer-to-Peer Electronc Cash System. [Onlne]. Avalable: https://btcon. org/btcon.pdf. [2] Sangjun Park, Haeung Cho and Heung-No Lee, Tme-varant proof-of-work usng errorcorrecton codes, n preparaton. [3] V. Butern. Dagger: A memory-hard to compute, memory-easy to verfy scrypt alternatve. Tech Report, hashcash.org webste, 2013. [4] E. Duffeld and D. Daz, Dash: A paymentsfocused cryptocurrency, [Onlne]. Avalable: https: //gthub.com/dashpay/dash/wk/whtepaper [5] R. G. Gallager, Low Densty Party Check Codes, Monograph, M.I.T. Press, 1963 [6] W. E. Ryan and S. Ln, Channel Codes Classcal and modern, Cambrdge [7] S. Shao, P. Hales, T-Y. Wang, J-Y. Wu, R. G. Maunder, B. M Al-Hashm and L. Hanzo, Sur-
vey of Turbo, LDPC and Polar Decoder ASIC Implementaton, IEEE Communcatons Surveys & Tutorals 2019 [8] Y. L. Ueng, B. J. Yang, C. J. Yang, H. C. Lee, and J. D. Yang, An Effcent Mult-Standard LDPC Decoder Desgn Usng Hardware-Frendly Shuffled Decodng, IEEE Trans. Crcuts Syst. I, vol. 60, no. 3, pp. 743 756, March 2013. [9] T. Brack, M. Alles, T. Lehngk-Emden et al., Low complexty LDPC code decoders for next generaton standards, n Proceedngs of the Desgn, Automaton and Test n Europe Conference and Exhbton (DATE 07), pp. 331 336, Aprl 2007 Bography 박상준 2005 년 3 월 ~ 2009 년 2 월충남대학교, 컴퓨터과학사졸업 2018 년 5 월 ~ 2019 년 2 월광주과학기술원블록체인경제센터연구원 2009 년 ~ 현재광주과학기술원전기전자컴퓨터공학석 / 박통합과정 < 관심분야 > 정보이론, 신호처리, 블록체인, 수치최적화이론, 압축센싱 이흥노 1993 년 Unversty of Calforna 전기공학과졸업 1994 년 Unversty of Calforna 전기공학과석사 1999 년 Unversty of Calforna 전기공학과박사 1999 년 ~ 2002 년 HRL Laboratores Research Staff Member, 2002 년 ~ 2008 년 Unversty of Pttsburgh Assstant Professor 2009 년 ~ 현재광주과학기술원전기전자컴퓨터공학부교수 < 관심분야 > 정보이론, 신호처리, 통신 / 네트워크, 압축센싱, 블록체인경제, 센서지능화 김형성 2013 년 3 월 ~ 2019 년 2 월전남대학교, 전자컴퓨터공학부학사졸업 2019 년 3 월 ~ 현재광주과학기술원전기전자컴퓨터공학석사과정 < 관심분야 > 블록체인