Consensus in Distributed Systems 박진형, 박찬현, 이동식, 이부형, 전창석, 홍종화이더리움연구회 4 기기술리서치분과 1
2
목차 1. 개요... 4 1.1. 블록체인의등장... 4 1.2. 분산시스템 (Distributed System)... 6 2. FLP Impossibility... 9 3. Byzantine Fault Tolerance (BFT)... 12 3.1. Two Generals Problem... 12 3.2. Byzantine Generals Problem (BGP)... 14 3.3. Solution 1: Oral Message (OM)... 17 3.4. Solution 2: Signed Message (SM)... 20 3.5. Generalized BFT... 24 3.6. 블록체인에서의 BFT 해결... 28 4. Practical Byzantine Fault Tolerance (PBFT)... 30 4.1. Introduction & Proof... 30 4.2. Algorithm Properties... 32 4.3. Normal Case Operation... 35 4.4. Checkpoint... 40 4.5. View Change... 42 5. Use Case: Tendermint... 45 5.1. Consensus Process... 47 5.2. Use Case: Tendermint test with 4 nodes... 56 6. Conclusion... 67... Appendix... 68 1. Introduction... 68 2. CAP 이론소개... 69 3. CAP 이론의한계... 74 4. PACELC Theorem... 76 3
1. 개요 기술의발달은너무나빨라서사람들이채적응하기도전에또다른신기술들의영향을받는다. 특히, 4 차산업혁명이라는거대한물결속에기술의진보는우리사회에더큰영향을끼치고있다. 인공지능, 데이터마이닝, 클라우드컴퓨팅등 4 차산업을대표하는미래유망신사업분야에높은관심이쏠리는이유다. 최근에는암호화폐의기반기술인블록체인이기존의금융서비스판도를바꿀것이라는기대감속에새롭게조명을받고있다. 불과몇년전까지만해도블록체인은 뜬구름잡는이야기 였지만지금은수많은사람들이연구하고다양한사업을창출하는핵심기반이되고있다. 1.1 블록체인의등장 블록체인은사토시나카모토 (Satoshi Nakamoto) 라는익명의인물이비트코인 : P2P 전자화폐시스템 (Bitcoin: Peer-To-Peer Electronic Cash System) [1] 이라는 9 쪽짜리논문을공개하면서세상에본격적으로등장했다. ( 엄밀히따지면사토시논문에는블록체인이라는단어는나오지않는다 ) 2008 년 10 월에공개된이논문은현재의중앙화금융시스템에대한도전장이자, 개인간온라인직접거래 (P2P) 의가능성을보여준획기적인사례였다. 그이유는분산컴퓨팅분야에서오래전부터풀지못했던비잔티움장군문제 (Byzantine Generals problem) 에대한실용적인해결책을제시했기때문이다. 간단히설명하자면, 사토시는악의적인노드가존재할수있는네트워크상에서도합의를이끌어낼수있음을작업증명방식 (Proof of Work) 을통해제시했다. 이해법은분산컴퓨팅과학에서획기적인발자취를남기고, 신뢰할수있는디지털화폐시대의초석을마련한것으로평가된다. 그러나, 사실탈중앙화를이루고자하는블록체인세상은하루아침에탄생한것은아니다. 블록체인의시작은사이퍼펑크 (Cyber Punk) 운동 [2] 이벌어진 1980 년대로거슬러올라간다. 사이퍼펑크운동은정부가개인의사생활정보에접근하지못하도록암호 (cypher) 체계를개발하고사용해야한다고주장한다. 사이퍼펑크운동은데이비드차움 (David Chaum) 의이캐시 (Ecash), 아담백 (Adam Back) 의해시캐시 (HashCash), 웨이다이 (Wei Dai) 의비머니 (B-money), 그리고닉재보 (Nick 4
Szabo) 의비트골드 (Bit Gold) 등중요한암호및거래기술을만드는초석이되었다. 즉, 블록체인은사이퍼펑크 (Cyber Punk) 들의지속적인노력과분산시스템에대한수많은연구의집약체라고볼수있다. 비트코인이세상에나오기까지의과정은아빈나라야나 (Arvind Narayana) 과제레미클락 (Jeremy Clark) 의글 Bitcoin s Academic Pedigree [3] 을통해서도자세히알수있다. ( 해당리서치는지난 3 기발표회 [4] 에서도확인할수있다. ) < 그림 1.1. 비트코인이나오기까지의아이디어연대표 > 5
< 그림 1.1> 을보면알수있듯이다양한이론들이접목되어발전한형태가현재의블록체인기술이다. 암호학과디지털재화, 합의과정, 타임스탬프, 증명방식등다양한분야의기술들이블록체인기술에영감을주면서발전하고있다. 특히, 분산시스템하에서블록체인기술이가지는의의는아주큼으로, 분산시스템과 IT 인프라아키텍처를소개하고자한다. 1.2 분산시스템 (Distributed System) 분산시스템 (Distributed System) [5,6] 이란기존의중앙집중처리를하던시스템에서탈피하여, 통신네트워크를통해서로약결합된 (Loosely Coupled) 처리기들의집합을의미한다. 즉, 사용자는하나의단일시스템으로보지만뒤에서는여러다양한컴퓨터들로구성되어있다. 분산시스템의장점은개별컴퓨터의안정성이낮아도무관하므로저렴한비용의장비로도구축할수있다. 또한, 더많은컴퓨터를이용해서시스템전체의성능을향상할수있어확장성이좋다는특징을가지고있다. 그러나분산시스템은서버의수가증가하면이를운영하기위한구조가점점더복잡해진다. 더불어서버가고장이나더라도이로인한영향을최소화하기위해서는서버의역할을세세하게검토해야한다. 서버를운영하는방법은여러가지형태로존재하며크게집약형과분할형으로구분된다. 몇가지대표적인예시를알아보자. 집약형아키텍처집약형아키텍처는흔히옛날영화에나오는방하나에기계와거대한장치들이있는장면을떠올리면된다. 집약형은대형컴퓨터를이용해모든업무를처리하는형태이다. 하나의컴퓨터로모든처리를하므로집약형이라고부른다. 그러나한대의컴퓨터로모든처리를감당해야하므로대부분은컴퓨터를구성하는주요부품들이모두다중화되어있다. 6
클라이언트-서버형클라이언트-서버형은수직분할형의하나로업무애플리케이션, 미들웨어, 데이터베이스등의소프트웨어를물리서버상에서운영하고, 이들의소프트웨어를클라이언트혹은단말이라고불리는소형컴퓨터가접속해이용하는형태이다. 클라이언트-서버는클라이언트 (client) 가전용소프트웨어를설치해야하며, 업무애플리케이션이갱신이될때마다클라이언트소프트웨어가업데이트되야한다. 또한, 서버의처리가집중되면확장성의한계가발생할수있다. 이를발전시킨것이 3 계층형아키텍처이다. 3 계층형아키텍처 3 계층형은클라이언트-서버형을발전시킨형태로위에서프리젠테이션계층, 애플리케이션계층, 데이터계층의 3 층구조로분할되어있다. 이는서버부하의집중을개선한것으로클라이언트는정기적인업데이트를하지않아도된다는장점이있다. 그러나클라이언트-서버보다복잡하다는단점이존재한다. 이외에도수평분할형아키텍처나지리분할형아키텍처등다양한아키텍처가존재한다. 2000 년대부터는웹이발전함에따라경량웹 (Thin Client) 처리방식이제공되기시작했다. 이는 HTML 을렌더링한결과만을제공하기때문에가볍다는장점이있다. 이후경량웹방식은단일웹페이지애플리케이션 (SPA, Single Page Application) 으로발전하였다. Ajax(Asynchronous Javascript + XML) 등을이용한다양한웹서비스가증가하다보니비동기식처리가많아지게되었다. 동기 (Synchrony) 는누군가에게일을부탁하고그일이끝나기까지기다리는것이고, 비동기 (Asynchrony) 는 끝나면말해 라고하고다른일을하는것을의미한다. 비동기의경우다른작업을하면서호출을한처리가되었는지계속해서체크를한다. 이후가상화기술의발전으로스토리지부터, 서버컴퓨팅, 네트워크, 운영체제에이르기까지모든자원을추상화할수있게되었다. 이렇게발전하게된클라우드컴퓨팅으로인해더인프라를직접구축하지않아도적은비용으로서비스를개발할수있는환경이조성되었다. 7
< 그림 1.2. 컴퓨터의발전 > 블록체인 P2P 컴퓨팅 P2P 컴퓨팅이란네트워크에참여한모든컴퓨터가동일한역할과기능을수행하는방식을의미한다. 이는클라이언트가서버의역할을동시에수행한다는의미이다. P2P 네트워크는중앙집중형, 링형, 계층형, 완전분산형등다양한방법으로연결이될수있다. 이더리움 (Ethereum) 플랫폼 [7] 의경우, P2P 기반에서완전분산형방식으로컴퓨팅프로세스, 파일, 메시지공유기능을활용하여다양한응용서비스를지원하고자한다. 이처럼다양한아키텍쳐가상황에맞게발전하며, 오늘날다양한블록체인시스템발전의촉매제역할을하고있다. 8
2. FLP Impossibility 분산시스템이론중빼놓을수없는이론은바로 FLP Impossibility 이다. FLP Impossibility 는 1985 년피셔 (Fischer), 린치 (Lynch), 패터슨 (Paterson) 이공동으로저술한 Impossibility of Distributed Consensus with One Faulty Process [8] 논문에서나온이론이다. 이는비동기식네트워크환경에서실패할가능성이있는노드가단하나라도있을경우 Safety 와 Liveness 이두가지속성을모두만족하는합의알고리즘은존재할수없음을증명하였다. 비동기네트워크 (asynchronous network) 특성상통신지연시간을예측할수없어특정문제로인해노드가작동에실패한것인지아니면단순히네트워크지연으로인해응답시간이오래걸린것인지알수없다. FLP Impossibility 를이야기하기이전에 FLP 이론에등장하는단어에대한정의를하고자한다. 동기성 (Synchronous) 동기성이란시스템에콜 ( 요청 ) 을하였을때콜이끝날때까지노드가대기하고완료가되면결과값을반환 (return) 하는네트워크를의미한다. 소프트웨어의관점에서는하나의과정 (routine) 이완벽하게끝나야반환을하는형태를의미한다. 비동기성 (Asynchronous) 비동기성이란하나의콜을하고, 완료의유무와상관없이응답 (respond) 를하는것을의미한다. 콜이후에노드는다른작업을병행할수있으며, 콜이완벽하게반환이되면결과물을다시가져오는형태이다. 다음정의를한특징을바탕으로분산네트워크에서는네트워크간의통신을동기성과비동기성으로구분한다. 동기성네트워크 (Synchronous Network) 의경우메시지를전송하고, 이를전파하는과정 (Message Propagation) 에서네트워크의정보전파시간을완전히조절할수있는것을의미한다. 또한, 모든노드는자신이보낸메시지에도달하는시간을조절혹은예측을 9
할수있다. 이때, 정확하게도달시간을예상할수있어야하므로이를방해하는어떤경우의지연 (Delay) 도일어날수없다. 이와달리비동기성네트워크 (Asynchronous Network) 의경우메시지를전송하고, 이를전파하는과정에서네트워크의정보전파시간을예측할수없는경우를의미한다. 네트워크상에존재하는수많은방해노드 (Botnet) 과 DDoS 공격등으로인해노드간의메시지가완전하게유실되거나사라지는가능성이있음을전제로한다. 다음의동기성과비동기성을중첩한경우는부분동기성네트워크 (Partial Synchronous) 라고하며, 네트워크통신상태를사용자가어느정도조절할수있는경우를의미한다. 네트워크상에서의방해가있더라도일정시간하 (Upper Bound) 에는반드시메시지를응답받을수있다. 이는 Chapter 4 의 PBFT 에서더알아보자. FLP 이론은앞서언급한바와같이비동기성네트워크 ( 부분동기성네트워크도포함 ) 환경에서실패가능성이단하나라도있을경우 Safety 와 Liveness 모두를만족하기힘들다는이론이다. 여기서는다루지않지만, Paxos 와같이궁극적으로최종합의가되는경우 (Eventual Liveness) 는가능하지만, 시간의범위 (Time Bounded) 가정해진경우는불가능하다. FLP Impossibility 에따르면, 분산네트워크는다음조건들을만족한다고가정하였다. 1) Termination: 모든동작하는노드들은언젠가는어떤값을결정한다. 2) Agreement: 노드들은모두동일한값을결정한다. 3) Validity: 결정된값은어떤과정을통해결정되어야한다. 가령, 노드가어떤메시지를받던항상 0 의값을출력하는알고리즘을가지고있다면이를만족시키지못한다. FLP Impossibility 는다음의가정을바탕으로크게두가지로정리하여증명 [9] 한다. 1) 비동기성네트워크에서노드의합의는결정성 (Deterministic) 을가지지않고, 노드의실패여부등으로인해비결정성 (Non-deterministic) 을가지게된다. 10
2) 1) 의정리를바탕으로아직합의가이루어지지않은상황은무한히합의가 이루어지지않는상황으로이어지는것이가능하다. 이는합의가발생하지않을수있다는의미이며, 비동기성네트워크에서는합의가 보장되는합의알고리즘은불가능하다는것이다. 다음의증명정리를바탕으로 FLP 이론을 3 가지의경우로간단하게정리할수있다. 1) 증명에서가정되는합의는결정성 (Deterministic) 을가진다. 2) 노드가실패할수있는환경은결정성 (Deterministic) 을가지지않는환경이다. 3) 결정성 (Deterministic) 을가지지않는환경에서는어떠한경우에도결정성을가질수없다. FLP Impossibility 에서는다음과같은증명을통해비동기식네트워크에서는 Safety 와 Liveness 를모두만족하며합의하는것은불가능하다고이야기한다. 블록체인에서는이 FLP Impossibility 를우회하기위해다음과같은방법을이용한다. 1) 합의를재정의한다. (Liveness over Safety) 2) 비동기성을포기한다. (Safety over Liveness) 블록체인에서이두가지방법으로 FLP Impossibility 를우회하는방법을차례대로 알아보자. 11
3. Byzantine Fault Tolerance (BFT) 현재분산네트워크시스템에서는 BFT 기반의합의알고리즘이많이사용되고있다. BFT (Byzantine Fault Tolerance) 는분산네트워크안에서악의의노드 (Byzantine) 가네트워크에존재하는경우에도선의의노드들이안전하게네트워크를사용할수있는합의방법은무엇인지연구하는분야이다. 현재 BFT 가어떻게블록체인기술에서활용되고있는지알아보기이전에, 1982 년레슬리램포트 (Leslie Lamport) [10] 외 2 명이발간한논문을중심으로 BGP (Byzantine Generals' Problem) 를살펴보면서초기의분산네트워크합의알고리즘연구방향과그내용을살펴본다. 3.1 Two Generals' Problem 두장군문제는신뢰할수없는네트워크에서의노드간메시지가올바르게전송되기위한조건을논의하면서처음나온개념이다. 1957 년에출판된논문 " SOME CONSTRAINTS AND TRADEOFFS IN THE DESIGN OF NETWORK COMMUNICATIONS" [11] 에서처음논의를시작했고, 두장군문제라는용어는 1978 년에만들어졌다. 이는네트워크를구성하는노드를장군으로가정하고, 두장군이공동의적을공격하는시나리오이다. 두장군은적진을사이에두고공격시각을합의해야하는상황이다. 다음은합의를위해두장군이고려해야하는사항들이다. 1) 반드시두장군이동시에공격해야만이길수있다. 2) 공격시각을합의하기위해각자의메신저를보낸다. 3) 메신저는메시지전달을위해반드시적진을통과해야한다. 이때장군들은공격시간을결정하기위해다음과같은생각을할수있다. 12
1) 장군 A 가메신저를통해장군 B 에게공격시간을전달 2) 장군 B 가장군 A 의메시지를확인후회신 3) 장군 A 가장군 B 의회신메시지를확인 4) 결정된공격시각에일제히공격! < 그림 3.1. 공격시각결정방법 [12]> 다음과같은공격시간이추가되었을때장군들은고민에빠지게된다. 가령장군 A 가 "11 월 1 일오전 8 시에공격 " 이라는메시지를작성해서장군 B 에게보낸다. 장군 B 가장군 A 의메시지를받고 " 공격확인 " 이라는응답메시지를장군 A 에게보낸다. 장군 A 가메시지를받으면합의는성공적으로이루어진다. 그러나, 장군 A 가보낸메시지를가지고떠난메신저가도중에적군에게잡힐수도있다. 장군 A 의메신저가적군의경계를무사히뚫고장군 B 에게메시지를전달했다고해도장군 B 의메신저가적군에게잡힐수도있다. 이경우메시지가잘전달될확률이항상 100 보다낮기때문에장군들은합의에도달할수없다. 이는누구도메시지가잘도착했는지알수있는방법이없다는것을의미한다. 13
< 그림 3.2. 두장군문제 > 3.2 Byzantine Generals Problem (BGP) BGP (Byzantine Generals' Problem) 는앞서설명한두장군문제를일반화한주제로셋이상이네트워크에참여할때서로합의를도출하기위한방법을논의한다. 두장군문제와같이공동의적을상대로승리하고싶은장군들을예시로제시하고더불어메시지위조가가능하며담합도할수있는배신자를등장시킨다. 여기서의논의주제는배신자가존재할경우에도합의에성공하려면배신자를포함하여몇명의장군이있어야할지를정하는것이다. BGP 에서기본적으로제시하는가정은다음과같다. 1) 적은어느정도의병력이모여서한번에공격을해야이길수있는상대이다. 이를 위해여러부대가적진을둘러싸고있으며각장군들은합의를통해공격을해야할지 말아야할지를결정해야하는상황이다. 14
2) 각부대는하나의장군이이끌고있으며메신저가전달하는메시지를통해서만서로소통이가능하다. 3) 메신저는반드시적진을통과해야지만다른부대로갈수있다. 4) 장군들중한명의사령관이 " 공격 " 혹은 " 후퇴 " 를결정하여메시지를모든장군에게전달한다. 5) 메시지를받은장군들은나머지장군들에게사령관으로부터받은메시지를전달한다. ( 장군들은서로연결되어있다.) 6) 일정시간이후각장군들은자신이받은메시지를종합하여 " 공격 " 혹은 " 후퇴 " 를결정하여명령을이행한다. ( 동기화 ) 메신저 (Messenger) 가메시지를전달하는도중에실패할확률이있다. 적군에게 포획당하거나살해당하는등실패를할수있다. 혹은장군들중에비잔틴즉, 악의적인 배신자가섞여있을수있다. 배신자는두가지경우로생각할수있다. 1. 배신자는메시지내용을위조할수있다. 2. 사령관도배신자가될수있다. 만약사령관이 " 공격 " 명령을하달했을때메시지를받은장군들이모두 " 공격 " 을이행해야전쟁에서승리할수있다. 그렇기때문에배신자의방해가있더라도모두같은결정을할수있어야한다. 이에램포트 (Lamport) 는추가적으로아래의두가지조건을제시한다. (IC, Interactive Consistency) IC1: 배신자가아닌모든장군들은같은명령을이행한다. IC2: 만약사령관이배신자가아니라면, 배신자를제외한모든장군들은 사령관의명령을이행한다. BGP 가생길수있는최소조건은아래와같이합의대상이 3 명일때이다. 15
V(i) 가 i 번째장군이받은메시지의집합이라고할때, 일정시간이후배신자가아닌 장군들은자신이받은메시지내용으로 " 공격 " 과 " 후퇴 " 중하나를선택하여이행한다. ( 과반수우선선택기준 ) 1) 사령관이배신자일경우 V(1) = {" 공격 ", " 공격 "} -> 장군 1 은 " 공격 " 으로판단 V(2) = {" 후퇴 ", " 공격 "} -> 장군 2 는 " 후퇴 " 로판단 2) 장군 2 가배신자일경우 V(1) = {" 공격 ", " 후퇴 "} -> 장군 1 은 " 공격 " 으로판단 < 그림 3.3. 사령관이배신자일경우 ( 왼쪽 ), 장군 2 가배신자일경우 ( 오른쪽 ) m 의수를늘려서 (m = 2, 3,... ) 장군의수가총 3m 일때를생각해보면배신자집단에 사령관이포함될경우정직한장군들이잘못된결정을하도록조작할수있음을알수있다. 16
안정적인합의를위해서는장군들은모두같은알고리즘을통해메시지를전달하고, 전달받은메시지에서 " 공격 " 이나 " 후퇴 " 중하나의의미를도출할수있어야한다. 이를위해램포트 (Lamport) 는두가지알고리즘을제시한다. 첫번째는구두메시지 (Oral Message, OM) 이고두번째는서명된메시지 (Signed Message, SM) 이다. 3.3 Solution 1: Oral Message (OM) 알고리즘 OM 에서의기본가정은아래와같다. 1) 장군들이보낸모든메시지는올바르게전달된다. 2) 메시지를받은장군들은누가보낸메시지인지알수있다. 3) 더이상메시지가도착하지않음을인지할수있다. Algorithm OM(m) BGP 를해결하기위해램포트가제안하는 OM 알고리즘은아래와같다. OM(0) 1) 사령관은모든장군들에게메시지 (" 공격 " 과 " 후퇴 " 중하나 ) 를보낸다. 2) 모든장군들은사령관이보낸메시지를수신하여 " 공격 " 과 " 후퇴 " 중하나를결정한다. OM(m), m은배신자의수 1) 사령관은모든장군들에게메시지 (" 공격 " or " 후퇴 " 중하나 ) 를보낸다. 2) 각 i에대해사령관에게장군 i가받은메시지를 v(i) 라고한다. 만약장군 i 가아무런메시지를받지못했다면그장군은 " 후퇴 " 로결정한다. 장군 i는 OM(m 1) 의사령관역할로 v(i) 를다른 (n-2) 명의장군들에게보낸다. 3) 장군들은메시지를받고 majority(v(1), v(2),..., v((n 1))) 을통해 " 공격 " 과 " 후퇴 " 중하나를결정한다. 4) majority(v(1), v(2),..., v((n 1))) 을통해 " 공격 " 과 " 후퇴 " 중하나를결정한다. 17
majority() 가값을결정하는기준은다음과같다. A. 장군이받은메시지에서 " 공격 " 과 " 후퇴 " 중많은쪽을택한다. 만약아무런메시지를받지못했다면 " 후퇴 " 한다. B. 만약 1 번에과반수를선택할수없는경우, 중앙값을선택한다. ( 메시지가순서집합의형태일때 ) 앞에서장군의수가 3m 이하일경우에는 BGP 를해결할수없음을얘기했기때문에, 여기서는 3m + 1 일경우를가정하여알고리즘 OM 을설명한다. 배신자가 1 명일경우 합의에참여하는장군의수는사령관포함총 4 명이다. 1) 사령관이배신자일경우 V(1) = {" 공격 ", " 후퇴 ", " 공격 "}-> 장군 1 은 " 공격 " 으로결정 V(2) = {" 후퇴 ", " 공격 ", " 공격 "}-> 장군 2 는 " 공격 " 으로결정 V(3) = {" 공격 ", " 후퇴 ", " 공격 "}-> 장군 3 은 " 공격 " 으로결정 2) 장군 2 가배신자일경우 V(1) = {" 공격 ", " 공격 ", " 후퇴 "}-> 장군 1 은 " 공격 " 으로결정 V(3) = {" 공격 ", " 공격 ", " 후퇴 "}-> 장군 3 은 " 공격 " 으로결정 두가지경우모두배신자가아닌장군들이모두 " 공격 " 으로결정하였음으로합의에 성공하여전쟁에승리할것이라예상할수있다. 18
< 그림 3.4. OM(1), 사령관이배신자일경우 > ` < 그림 3.5. OM(1), 장군 2 가배신자일경우 > 19
알고리즘 OM 은 n 3m + 1일때안전하게사용할수있지만, 재귀적으로동작하기때문에배신자의수가늘어날수록메시지의전달과정이지수적으로 ( 기하급수적으로 ) 늘어난다. 예를들어, 배신자가 3 명이라면 OM(3) < OM(2) < OM(1) < OM(0) 과정을거친다. 즉, OM 알고리즘을 (m + 1) 번거쳐야합의에도달할수있다는의미이다. 이에따른복잡도는아래표와같이나타낼수있다. 배신자의수 (m) 복잡도 (n 은장군의수 ) 0 O(n) 1 O(n^2) 2 O(n^3) 3 O(n^4)...... < 표 3.1. 메시지교환횟수에따른 OM 의복잡도 > 3.4 Solution 2: Signed Message (SM) 램포트 (Lamport) 의두번째해결방안은메시지에서명을붙임으로써누가보낸 메시지인지인지할수있도록하는방법이다. 기존 OM 의가정에다음의가정이추가된다. 1) 배신자가아닌장군의서명은위조될수없으며, 메시지를수신한장군은서명된 메시지의내용이변경되었을경우인지할수있다. 2) 작성된서명은누구나검증할수있다. 서명한메시지는다음과같이정의한다. 사령관을포함한장군들은각자의식별자 (ID) 를가진다. - v: 0 -> 사령관이서명한메시지 v v (value: " 공격 " or " 후퇴 " 둘중하나의값을가짐 ): 메시지내용 0: 사령관의 ID 20
- v: i: j -> 장군 i 와장군 j 의서명이담긴메시지 v j: 메시지 v 에서명한장군 j i: 메시지 v: j 에서명한장군 i SM 알고리즘의동작과정은아래와같다. - 사령관은모든장군들에게서명하고 v: 0을보낸다. - 각 i에대해, a. 장군 i 가처음사령관의메시지 v: 0를받았다면, - V(i) = {v - v: 0에자신의서명을붙여서 v: 0: i를다른장군들에게전달한다. b. 장군 i가메시지 v: 0: j 1 : j 2 :... j k 를받았는데, V(i) 에 v가없다면 (i.e., 계속 공격 을받았는데, 방금온메시지는 퇴각 이라면 ) - V(i) 에 v를추가한다. - j(1)~j(k) 를제외한다른장군들에게메시지 v: 0: j 1 : j 2 :... j k : i를전달한다. 더이상메시지가오지않을때, choice(v(i)) 의값을실행하여공격할지퇴각할지 결정한다. < 그림 3.6. 선택을위해사용하는함수 choice> 21
앞에서배신자가 1 명일때장군이 4 명이상이라면합의가가능함을보였으니 (n 3m + 1) 3 명의장군이합의하는경우를생각해보자. 사령관이합의를방해하기위해한명에게는 " 공격 " 이라고전달하고, 다른한명에게는 " 퇴각 " 이라고지시한다. 장군들은아직까지사령관이배신자인지모르기때문에다른장군에게받은메시지를그대로전달한다. 배신자가아닌장군 1 과 2 가받은메시지는아래와같다. V(1) = {" 공격 ": 0, " 후퇴 ": 0: 2} -> 장군 1 은 " 후퇴 " 로결정 V(2) = {" 후퇴 ": 0, " 공격 ": 0: 1} -> 장군 2 는 " 후퇴 " 로결정 장군 1 과 2 는두번째로받은메시지를통해사령관이배신자임을알고 " 공격 " 명령을수행하지않을것이다. 배신자가아닌두장군이 " 후퇴 " 라는합의를얻었기때문에 IC1 을만족했다고할수있다. (choice(v(1)) = choice(v(2))), IC2 는사령관이배신자가아닌경우에만고려 ) 또한, 알고리즘 SM 에서의첫번째가정에의해배신자가아닌장군의서명은위조할수없기때문에장군 1, 2 중하나가배신자라면두번째메시지에사령관의서명이없었을것이다. < 그림 3.7. SM(1), 사령관이배신자일경우 > 22
만약앞의케이스에배신자장군 3 을추가해도 SM(m) 으로합의에성공할수있을지알아본다. 메시지교환과정은 SM(1) 과거의비슷하나, 장군 1 은장군 2 에게메시지 {" 후퇴 " 0: 2} 를받고장군 3 에게메시지 {" 후퇴 " 0: 2: 1} 을보내는과정과장군 2 가장군 1 에게메시지 {" 공격 ": 0: 1} 을받고장군 3 에게메시지 {" 공격 ": 0: 1: 2} 를보내는두과정이추가된다. < 그림 3.8. SM(2), 사령관과장군 3 이배신자일경우 > 장군 1, 2 가받은메시지와최종결정은아래와같다. V(1) = {" 공격 ": 0, " 후퇴 ": 0: 2} -> 장군 1 은 " 후퇴 " 로결정 V(2) = {" 후퇴 ": 0, " 공격 ": 0: 1} -> 장군 2 는 " 후퇴 " 로결정 생각할수있는최소경우인장군의수 n 이 m + 2 일때합의가가능함을보였으므로, n m + 2 일때알고리즘 SM 을이용하면일치된합의를통해전쟁을승리로이끌수있다. 이상으로 Byzantine Generals Problem 에대해알아보았다. 다음의논문을통해 3m 일 23
경우합의가불가능함을알수있었다. 또한, 램포트의솔루션을통해다음과같은경우 합의가가능함을알수있게되었다. 1. 알고리즘 OM 을사용하면 n 3m + 1 일때합의가능 2. 알고리즘 SM 을사용하면 n m + 2 일때합의가능 그러나램포트의논문에따르면많은제약조건을가지게되고실제사용하는네트워크 안에서노드간합의를하는과정은이보다어렵다는것을예상할수있다. 3.5 Generalized BFT 지금까지 BGP 를통해 3m + 1 이상의노드가존재할때 m 명의악의적인노드가있더라도합의가될수있음을알아보았다. 그러나논문의증명을통해알수있듯이램포트는 3m + 1보다작은노드의상황에서합의 (Consensus) 가되지않는다는방식으로증명을하였다. 본단락에서는이를일반화한증명을통해왜전체 3m+1 의노드 (m 명의악의적인노드 ) 가필요한지알아보고자한다. 여기전체 N 개의노드로구성이된네트워크가있다고가정한다. 이중악의적인비잔틴노드가 b 개, 정직한노드가 h 개있다. 이노드들은전체 N 개의노드들중 t 개이상이동의한다음상태 (state) 가있으면해당상태로이동한다. 이네트워크안에서는투표가비동기적 (asynchronous) 으로일어난다. 여기서일어나는합의가 Safety 와 Liveness 모두를만족할때까지가능한 t 의범위를계산해본다. N = h + b 여기새로운상태 A 와 B 가제안되었다. 이때각각의상태에대한투표가진행된다. 정직한노드들은각각절반씩상태 A 와 B 를지지를하게된다.( 상태 A 와 B 이렇게두가지선택이있기때문에확률적으로 1/2 이다 ). 이렇게투표를한정직한노드들은자신의상태에대한투표를다른노드들에게전달한다. 24
< 그림 3.9. 정직한노드들의투표와전파 > 정직한노드들이상태에투표를전파하였다. 남은노드들은비잔틴, 즉악의적인노드들이다. 비잔틴한노드들은네트워크를원할하지못하게하는것이목적이기때문에정직한노드들의전파를모두받고선택을하게된다. 이때비잔틴한노드들은거짓된투표정보를전파한다. 상태 A 에는 B 가맞다는투표를, 상태 B 에는 A 가맞다는정보를동시에보낸다. 이럴경우각상태 A 와 B 는투표를다음과같이얻게된다. 상태 (State) 들이득표한투표수 상태 A 상태 B 상태 A 로의투표수 상태 B 로의투표수 h 2 < 표 3.2. 상태 (State) 가득표한투표수 > h 2 + b h 2 + b h 2 25
다음표를보면알수있듯이만약 t < h/2 + b 일경우노드가다음상태로진행되기 위한최저투표수이상의표를받은상태가존재하게된다. 따라서네트워크의일부는 A, 나머지는 B 로진행되어분할이된다. 이는블록체인네트워크에서자주듣게되는 네트워크포크 (Fork) 상태가된다. 이를방지하기위해서는 t > h + b가되야한다. 2 < 그림 3.10. 비잔틴노드의투표와최종상태투표수 > 방금비잔틴노드들의악의적인투표를막기위해서는 t > h + b 가되야한다고 2 이야기했다. 이는네트워크특성중 Safety 를만족하기위함이다. 그렇다면비잔틴한 노드들은 Liveness 의방해를아예합의에참여안함으로방해할수있다. 이경우는다음 그림을통해알아보자. 26
< 그림 3.11. 새로운상태 C 에대한투표 > 새로운상태인 C 가제안이되었다고가정한다. 여기에정직한노드들은 h 개만큼의지지투표를상태 C 에게보낼것이다. 비잔틴한노드들은네트워크의 Liveness 를방해하기위해투표를하지않았다. 이경우합의의대상인 C 에문제가없다면다음상태인 C 로네트워크는진행이되어야한다. 만약 t>h 인경우, 최종투표수가합의를위한최소표의수보다크기때문에네트워크가상태 C 로진행되지못한다. 따라서 Liveness 가보장이되기위해서는 t <= h 여야만보장이될수있다. 지금까지이야기한것을정리하면다음과같다. N = h + b t > h 2 + b t <= h 이를정리하면다음과같은결론이도출된다. h > h 2 + b, h = N b N b > 2b N > 3b b < 1 3 N 27
따라서 b<1/3n 일때 Safety 와 Liveness 모두를만족시킬수있다는결론이나오게된다. 이는 BFT 에서이야기하는 3m+1 의노드가있을때 m 개의악의적인노드가있더라도합의가가능하다는결론과동일하다. 지금까지일반화증명을통해 BFT 를해결법을알아보았다. 다음에서는블록체인에서어떤방식으로 BFT 문제를해결했는지알아본다. 3.6 블록체인에서의 BFT 해결 [13,14, 23] 블록체인중가장처음제시된비트코인의합의알고리즘중작업증명방식 (Proof of Work, POW) 는타임스탬프 (Timestamp) 와서명 (Sign, 블록체인에서는 Key) 을통해이문제를해결한다. 1) 장군은메시지를보내기위해 10 분의시간을가진다. (nonce 를찾기위한컴퓨팅작업 ) 2) 메시지는모든장군 ( 이전포함 ) 의메시지와메시지를보내기위해 10 분을들였다는증거를포함한다. 다음의규칙이추가됨에따라중간의비잔틴장군이존재하더라도다른장군들은이장군이거짓임을밝혀낼수있다. 혹은초기에메시지를받은장군이존재하더라도앞선시나리오처럼정직한장군들이성을함락할수있게된다. 지금까지비트코인의합의알고리즘 (Proof-of-Work) 을통해 BFT 의해결과정또한알아보았다. 비트코인의합의알고리즘은사토시나카모토의이름을딴나카모토컨센서스 (Nakamoto Consensus) 로도불리며, 작업증명방식에따라언제나어려운문제에대한답 (Nonce) 을마이너 (Miner) 가찾으면블록이생성되어체인을이어나가게된다. 이렇게만들어진가장긴체인은유효 (valid) 한체인이며, 정격체인 (canonical chain) 이라부른다. 이방식은 FLP Impossibility 를우회하는방법중 Liveness over Safety 의방법을택한것이며, 비트코인의경우 Liveness 를먼저확보하고 6 컨펌 ( 약 60 분 ) 을통해완결성 (Finality) 을가져 Safety 를보완한다. 28
FLP Impossibility 를우회하는두번째방법인 Safety over Liveness 의방식으로는 BFT 계열의합의알고리즘이있다. 부분동기성네트워크모델인 PBFT 와이를응용하는 블록체인을통해어떻게문제를해결하는지알아보자. 29
4. Practical Byzantine Fault Tolerance (PBFT) 4.1. Introduction PBFT 합의알고리즘은비잔틴노드가존재할수있는비동기분산시스템상황에서도참여한노드가성공적으로합의를달성할수있도록고안된방안이다. 미구엘카스트로 (Miguel Castro) 와바바라리스코프 (Barbara Liskov) [15] 가 1999 년에제안한이 BFT 계열합의알고리즘은일정수준의배신자노드가존재하더라도비동기네트워크에서합의에도달함을보여준다. 현재 PBFT 모델은다양한비허가형 (permissioned) 및허가형 (permissionless) 블록체인시스템에서적용되고있으며, 특히분산환경에서의노드간의결함감내를보장하기위해사용된다. 4.1.1. Service Properties PBFT 알고리즘은분산시스템에서다른노드들간의복제 (Replicate) 가가능한상태머신 (state machine) 을모델로하며, 각노드는서비스상태 (service state) 1 를유지하면서서비스운영 (service operation) 2 을실행한다. 기존의상태머신복제 (state machine replication) 시스템과마찬가지로, 노드 (replica) 는두가지요구사항을따른다. 1. 노드는결정론적 (deterministic) 이다. 결정론적시스템에서는특정입력값이들어오면항상똑같은과정을거쳐동일한결과를만들어낸다. 2. 노드는동일한상태 (state) 에서시작한다. 따라서, 해당조건에서는모든정직한노드는요청실행순서를합의하기때문에특정 실패가발생해도 safety 를보장한다. 1 Service state: 하나의서비스가작업을수행하기위해읽고쓰는데이터를나타낸다. 2 Service operation: 하나의서비스가어떻게잘운영할지정리하는서비스운영단계이다. 30
4.1.2. System Model Assumption 네트워크에노드가연결되어있는비동기성 (asynchronous) 분산시스템을 가정하기때문에메시지전달이실패, 지연, 중복, 또는무작위순서가될수있다. 비잔틴노드가임의적으로행동할수있는 Byzantine failure 모델을가정한다. 또한, 독립적인노드의실패가능성을열어두어, 특정노드의실패가개별노드의직접적인영향을주지않도록한다. 즉, 한노드가악의적인공격으로입은피해가다른노드의영향을주어서는안되기때문에서로다른서비스코드 (service code) 와운영시스템 (operating system) 을실행시켜야하며, 루트패스워드 (root password) 와관리자계정또한모두서로달라야한다. Replicated service 에심각한장애를일으키기위해아주강력한비잔틴공격자의상황을가정하여정직한노드의시스템을지연시킨다. 단, 정직한노드를무기한지연시키는것은불가능하며정직한노드의유효한서명을위조할수는없다. 4.1.3 Cryptography 암호기법을통해서 spoofing 및 replay 공격을방지하고악의적인메시지를구별한다. 메시지에는퍼블릭키서명 (Public-key signatures), 메시지인증코드 (MAC), 충돌회피해시함수 (CRHF) 에서나온메시지다이제스트 (message digest) 3 를포함한다. 전체노드는퍼블릭키서명을통해해당메시지를인증한다. 노드 i가서명한메시지 m은 < m > σi 으로, 메시지다이제스트는 D(m) 으로표기한다. 3 메시지다이제스트 (Message Digest) 메시지다이제스트는고정된크기의메시지로, 해쉬함수를이용해서생성된다. 해쉬함수가안전성이보장된다는가정하에서, 메시지다이제스트서명은메시지자체에서명을하는것과동일한보안서비스를제공한다. (http://ko.security.wikidok.net/wp-d/575aa262d16e73173de7a3ed/view) 31
4.2 Algorithm Properties Safety: 모든정직한노드는실패가발생하더라도메시지요청실행순서를합의한다. Liveness: 리더 primary 노드의문제가생기더라도시스템은멈추지않는다. PBFT 메시지합의과정은크게 Pre-Prepare, Prepare, Commit [17] 순으로이어진다. 클라이언트의요청이성공적으로실행이되면답변 (reply) 을받게된다. PBFT 알고리즘의 대략적인진행방향은다음과같다. 1) 클라이언트가서비스운영 (service operation) 을호출하기위해 primary 노드에게요청을전송한다. 2) Primary 노드는해당클라이언트의메시지요청을수집하고정렬하여나머지노드 (backups) 에게전송한다. 3) 각노드는해당요청사항을실행하여검증절차를거친다. 모든검증작업이끝나면해당메시지에대한답변을클라이언트에게전송한다 4) 클라이언트는 f+1 개이상의동일한결과를서로다른노드로부터전달받으면해당요청사항이문제없이처리된것을확인한다. < 그림 4.1. PBFT Consensus Algorithm [16]> 32
본격적으로합의알고리즘의진행방향을알아보기전에몇가지개념을다시한번 정의하고자한다. v n σ m p 뷰번호 (view number) 순서번호 (sequence number) 서명 (signature) 요청메시지 (requested message) Primary 리더노드 (primary replica) < m > σ i 노드 i 가서명한메시지 D(m) 메시지다이제스트 m < 표 4.1. PBFT 용어설명 > 4.2.1. Request 클라이언트는 < REQUEST, o, t, c > σ c 형태로 primary p 에게메시지를전송한다. Primary 가클라이언트요청 m을수신하면, 이를정렬하여나머지백업노드들에게전송한다. 그러나프로토콜에서처리되는메시지의수가기준치를초과하면 primary 노드는프로토콜을즉각적으로실행하지못한다. 따라서, 이경우에는, 메시지요청을버퍼 (buffer) 시켜서뒤이어서전송한다. 이를통해메시지트래픽및 CPU 오버헤드를줄일수있다. 4.2.2. The Client 메시지요청이시작되는클라이언트 (client) 의관점에서일련의합의과정을알아보자. 먼저, 클라이언트 c 는 < REQUEST, o, t, c > σ c 메시지를 primary 에게전송하여 state machine operation 의실행을요청한다. 요청을받은 primary 는이를정리해서노드 (backup) 에게전송한다. 각노드는전달받은요청 (request) 에대한답변을 33
클라이언트에게직접전달한다. 답변의형태는 < REPLY, v, t, c, i, r > σ i 이며, 의미는다음과같다. v는현재뷰번호 (view number) 이다. 클라이언트는뷰 (view) 를확인하여현재 primary 가누구인지확인한다. 뷰 (view) 는쉽게말해, 리더노드인 primary 와나머지 backup 노드가한번활동하는기간이다. 뷰번호 (View number) 를확인하여클라이언트는현재 primary 에게요청 (request) 메시지를보내게되는데, 이때전송방식은점대점 (point-to-point) 4 을사용한다. t 는요청에대한타임스탬프, i 는노드의숫자를나타내며, r 은요청한 operation 에대한실행결과이다. < 그림 4.2. Client Request & Reply [16]> 클라이언트는유효한서명및동일한 t 와 r 이담긴메시지답변을각각의노드에게서 f+1 개일때까지기다린다. 그전까지는결과값 r 을수락해서는안된다. 만약클라이언트가답변을제때받지못했다면, 이번엔해당요청을모든노드에게전송한다. 요청은이미처리가된상황이고단순히네트워크문제로메시지전달이지연된 4 Point to point: 한명의송신자가한명의수신자에게메시지를보내는방식으로계속해서대화를나누며빠른응답을필요로 하는경우에주로사용된다. 34
경우라면노드는해당요청에대한답변을재전송해야한다. 따라서, 모든노드는각각의클라이언트에게보낸마지막답변메시지 (reply message) 를항상기억해야한다. 반대로, primary 가요청 (request) 을백업노드에게전송하지않아서, 메시지가처리되지않았을수있다. 이때, 다수의노드들은현재 primary 가악의적인노드라판단하고 view change 를발생시킨다. View change 는리더인 primary 를교체하는작업으로 <4.5. view change> 에서더자세히알아본다. 4.3.Normal Case Operation Pre-prepare 및 prepare 는요청순서를제안한 primary 가악의적인노드일지라도동일한뷰 (view) 에서보내진요청을정렬화시키기위한단계이다. Prepare 및 commit 은커밋된요청을뷰 (view) 전반에걸쳐서순서를정돈하는단계이다. 4.3.1. Pre-prepare 단계 클라이언트로부터요청이도착하면가장먼저 primary 는유효한요청에 sequence number n 을부여하는데, 이는요청순서를의미한다. Primary 는 pre-prepare 메시지를나머지노드에게전송하고자신의 log 에해당메시지를저장한다. 이때, 메시지 m은 piggyback 5 ( 같이태워서보냄 ) 형식으로보내게되어데이터전송효율성을높인다. Pre-prepare 메시지는 PRE PREPARE, v, n, d > σ p, m > 형태로전송된다. 해당메시지의의미는다음과같다. v: 메시지가전송되는 view n: 메시지요청순서 (sequence number) 5 Piggyback 이란? 수신자는수신받은데이터에대한확인 (Acknowledgement) 를즉각적으로보내지않고, 우선기다리고있다가전송할데이터가있는경우에함께보낸다. 이렇게하는이유는수식자측에서데이터를잘받았다는확인서 (Ack) 를보낼때일정량의대역폭을사용하게된다. 수신자는송신자에게데이터를전송할때, 나머지데이터도함께태워서보내면이런비효율성을줄일수있다. 35
d: 메시지 m 의다이제스트 (digest) σ p : 메시지의유효성을증명하는 primary 의서명 m: 클라이언트가요청한메시지 < 그림 4.3. Pre-prepare Phase [16]> 이제노드 (backup) 들은 pre-prepare 메시지의진위여부를확인후수락하는작업에 착수한다. 메시지의참인성립조건은다음과같다. v, n, d, σ 모두유효해야한다. 다른다이제스트가포함된 view v와 sequence number n을수신하지않아야한다. Pre-prepare 메시지의 sequence number 는 low water mark h와 high water mark H 사이에존재해야한다. 특히, 마지막 (h<n H) 조건은악의적인 primary 노드가가장큰수를선택함으로써 sequence number 의공간을모두차지하는것을방지한다. (4.4. Checkpoint 부분에서 (h<n H) 조건에대해서더자세히알아본다. 36
4.3.2. Prepare 단계 Backup 노드 i 가 PRE PREPARE, v, n, d > σ p, m > 메시지를수락하면 prepare 단계에진입하게된다. 이제 < PREPARE, v, n, d, i > σ i 메시지를다른모든노드들에게전송하고자신의 log 에저장한다. Primary 를포함한노드들은다음조건을확인하면해당 prepare 메시지를수락하고자신의 log 에저장한다. 메시지의서명이유효하다. 메시지의 view number 와노드의현재 view 가일치하다. Sequence number 는 h 와 H 사이다. Pre-prepare 와 prepare 단계에서는동일한 view 에서보낸메시지순서를정렬한다. 이두단계를통해정직한노드들은동일한 view 내에메시지에대한전체순서를합의하게된다. 노드들은동일한뷰 (view), 순서번호 (sequence number), 다이제스트 (digest) 를가지고있는지확인하면서 prepare 메시지와 pre-prepare 메시지가일치하는지검증한다. 서로다른노드로부터 pre-prepare 메시지와일치하는 prepare 메시지 2f 개를수집하면검증절차가완료되고, 이를 prepared 된상태라부른다. < 그림 4.4. Pre-prepare & Prepare(Prepared)> 37
만약노드 i 입장에서 prepared(m, v, n, i) 메시지가참이라면정직한노드 j 에게는 prepared(m`, v, n, j) 은거짓이며, 따라서 D(m`)!=D(m) 조건은성립된다. 이조건이참인이유는 prepared(m, v, n, i) 와 R=3f+1 을통해최소 f+1 개의정직한노드는 sequence number n 을가진 view v내에메시지 m에해당하는 pre-prepare 또는 prepare 를보냈기때문이다. 4.3.3. Commit Phase 노드 i는 prepared(m, v, n, i) 메시지가참이되면 < COMMIT, v, n, D(m), i > σ i 메시지를노드들에게전송한다. 각노드들은다음조건을확인하면해당 commit 메시지를수락하고자신의 log 에저장한다. 메시지의서명이유효하다. 메시지의 view number 와노드의현재 view 가일치하다. Sequence number 는 h 와 H 사이다. Commit 단계에서는 committed 와 committed-local 이존재한다. committed(m, v, n) : f+1 개의정직한노드가존재하는상황에서 prepared(m, v, n, i) 가참인경우 committed local(m, v, n, i) : prepared(m, v, n, i) 가참이고노드 i 가자신의메시지를포함해서다른노드로부터 pre-prepare m 과일치하는 2f+1 개의 commit 메시지를받은경우 38
< 그림. 4.5. Commit Phase> 바로이부분에서 commit 단계가필요한이유다. 노드 i 는다른노드로부터 preprepare m 과일치하는 2f+1 개의 commit 메시지를받는다고했다. 그렇다면왜 prepare 메시지가아닌 pre-prepare 메시지와대조작업을하는것일까? 아래예를통해확인해보자. 2f+1 개의 prepare 메시지를받지못한 ( 정직한 ) 노드가있다고가정해보자. 네트워크연결이끊어졌거나잠시동안오프라인상태여서메시지를못받았을것이다. 따라서, 이들은당연히 prepared 단계를시작하지못하였다. 그러나약간의시간이지난후, 2f+1 개의노드가 commit 메시지를전파했다는사실을듣는다면, 그때서야 (m, v, n, i) 을커밋해도된다는확신을하게된다. 즉, 정직한노드라면내부적으로커밋한요청메시지의순서번호 (sequence number) 를합의하게된다. 결론적으로, 메시지전달은순서대로진행되지않기때문에노드는요청메시지를뒤죽박죽 (out-of-control) 으로커밋 (commit) 할수있다. 그럼에도메시지처리문제가발생하지않는이유는해당요청메시지가실행되기전까지, 각노드는 pre-prepare, prepare 그리고 commit 단계마다메시지를자신의 log 에저장해두기때문이다. 39
4.4 Checkpoint (Garbage Collection) PBFT 알고리즘은 safety 를보장하기위해노드가메시지를자신의 log 에저장하도록한다. 최소 f+1 개의정직한노드가요청을실행했다는사실을알기전까지는메시지를보관해야한다. 하지만, 지속적으로쌓여가는메시지를적절히관리하지않으면노드의 log 는비대해지고결국비율효적인상태가된다. 이런문제를해결하기위해서일정기간을두고안정된체크포인트 (stable checkpoint) 를만들어낸다. 체크포인트 (Checkpoint) 란노드의 log 에저장해두었던메시지를정리하여폐기하는단계로써, 검증이안정적으로완료되면 stable checkpoint 가만들어진다. 그럼이제구체적으로체크포인트가어떻게진행되는지알아보자. 먼저, 노드 i는체크포인트를만들고 < CHECKPOINT, n, d, i > σ i 메시지를나머지노드에게전송한다. 해당메시지의의미는다음과같다. n 은상태 (state) 에서실행된마지막메시지의순서번호 (sequence number) 이며 d 는상태 (state) 의다이제스트이다. 다른노드가서명한동일한다이제스트 d 를가진 sequence number n에해당하는 2f+1 개의체크포인트메시지를모으기전까지는자신의 log 에해당메시지를모아둔다. 유효한체크포인트메시지 2f+1 개가모이면, 이체크포인트는안전하다고증명 (proof) 된다. 안전성이증명된체크포인트 (stable checkpoint) 에서는노드는자신의 log 의 sequence number 보다작거나같은 pre-prepare, prepare, commit 메시지를모두버린다. 또한, 체크포인트에는메시지를얼마나받아들이고제한할지를결정하는 low water mark h 와 high water mark H 가존재한다. 매번 operation 을실행한후메시지처리과정을진행하는것은비용적으로비효율적이다. 따라서, 체크포인트 (state snapshot 상태 ) 는일정주기를두고생성된다. Low water mark 는마지막 stable checkpoint 의 sequence number 에해당하여, 메시지의 sequence number 가 H 에도달하게되면, 40
체크포인트작업을시작한다. High-water mark 와 low-water mark 의직관적인이해를 돕기위해데이터처리가어떻게이루어지는지알아본다. < 데이터전송에서 High-water mark 와 Low-water mark 에대한이해 >[18] High-water mark 와 low-water mark 는데이터처리를원활하게하기위한장치이다. Buffer 는일부의데이터를잠깐저장하는제한된공간이다. 아래의그림에서 media server 는 buffer 의 water-mark 를통해얼마만큼의데이터를전송할지결정한다. Buffer 가 low-water mark 보다데이터를덜갖고있으면, media player 는더많은데이터를전송해달라는신호를보내고, 반대로데이터가 high-water mark 를넘으면, media player 는데이터를그만보내라는신호를보내게된다. < 그림. 4.6. Low-water mark & High-water mark> 41
4.5. View Change 리더노드가요청메시지를멀티캐스트하지않고일정시간이지나게되면리더변경절차인 view change 가발생한다. View change 는 liveness 를확보하는단계로써, primary 노드가비잔틴일경우에도시스템이계속해서작동하도록하는단계이다. 즉, primary 의메시지를기다리는 backup 노드들은무기한기다리지않으며, 타임아웃되면리더를변경하는 <VIEW-CHANGE> 를발생시킨다. Backup 노드의타이머조건은다음과같다. 타이머 (Timer) 가시작되는조건 -이미다른타이머가작동하지않고메시지요청을수신했을때 타이머 (Timer) 를정지하는조건 - 메시지요청실행을더이상기다리지않을때 타이머 (Timer) 를재시작하는조건 - 특정시점을기다리면서다른요청을실행할때 특정 view 내의 backup 노드 i의타이머가만료되면, view v+1 로이동하기위한 view change 가시작된다. View change 가시작되면, 노드는 checkpoint, view-change, new-view message 를제외한다른메시지를일절받지않으며, < VIEW CHANGE, v + 1, n, C, P, i > σ i 메시지를모든노드에게전송한다. 해당메시지의의미는다음과같다. v + 1: 새로운 view 번호 n: 노드 i가알고있는가장최신의 stable checkpoint s의순서번호 (sequence number) C: s가올바른 checkpoint 인지증명하는 2f+1 개의유효한체크포인트메시지 P: 노드 i의 prepared 메시지중에서 n 보다큰 sequence number 를가진요청메시지집합 42
< 그림 4.7. View Change & New-View> v+1 에서 primary p 가다른노드로부터 2f 개의유효한 view-change 메시지를 전달받으면, < NEW VIEW, v + 1, V, O > σ P 메시지를다른모든노드에게전송한다. 해당메시지의의미는다음과같다. v + 1: 새로운 view 번호 V : primary 가받은유효한 view-change 메시지 + primary 가보낸 viewchange 메시지 (v+1) O: pre-prepare 메시지집합 ( 피기백 (piggyback) 요청은제외 ) 앞서서보았듯이, 2f+1 개이상의노드가메시지를검증하면나머지노드를기다리지않기때문에일부노드는요청메시지 m 또는 stable checkpoint 가다른노드와정확히일치하지않을수있다. 따라서, view-change 가일어나서새롭게교체된 primary 가유효한작업을시행하려면 backup 노드들과메시지반영상태를 sync 할필요가있다. 이때필요한작업이유효한집합 O 의계산이다. Pre-prepare 메시지집합인 O 가만들어지는과정은다음과같다. 먼저, V 의메시지들중가장최근의 stable checkpoint 의순서번호 (sequence number) 를 min-s 라하고, V의 prepare 메시지들중가장높은순서번호 (sequence 43
number) 를 max-s 라한다. 모든 sequence number n 이 min-s< n < max-s 에대해, primary 는새로운 pre-prepare 메시지를만든다. 이경우두가지의경우를생각해볼 수있다. Case 1: V내의 P가 sequence number n 인메시지집합이적어도하나인경우, < PRE PREPARE, v + 1, n, d > σ p 메시지를생성한다. Case 2: 메시지집합이하나도없는경우, < PRE PREPARE, v + 1, n, d null > σ p 메시지를생성한다. 이제 Primary 는 O 의 pre-prepare 메시지를자신의 log 에붙이게되면, v+1 로진입하게 되어메시지를다시수신받게된다. Backup 노드들이 v+1 의 NEW-VIEW 메시지를 받아들이는조건은다음과같다. 서명이유효하다. 포함되어있는 view-change 메시지가유효하다. 집합 O 의계산이유효하다. 검증을완료한노드들은 NEW-VIEW 를받아들이고 normal-case operation 대로다시 진행하게된다. 44
5. Use Case: Tendermint PBFT 가어떤방식으로합의에도달하는지증명을통해알아보았다. 블록체인에서는 PBFT 를어떻게응용하여사용하는지대표적인코스모스 (Cosmos) 프로젝트의 텐더민트 (Tendermint) [19,20] 를통해알아보자. 텐더민트는코스모스네트워크 (Cosmos Network) 에서사용하는합의엔진으로써, 전통적인 PBFT 합의프로세스를블록체인에맞게적용한대표적인사례이다. PBFT 와 Tendermint 모두최대 1/3 개의비잔틴노드가존재하는상황에서도성공적으로합의에도달한다. 텐더민트의전체합의프로세스는 PBFT 와유사하지만약간의용어차이가존재함으로 알아보자. PBFT Primary Replica Pre-prepare phase Prepare phase Commit phase View change Tendermint Proposer Validator Propose step Prevote step Precommit step Round change < 표 5.1. Terminology of PBFT & Tendermint> 45
텐더민트투표프로세스 (Voting Process) 는 < 그림 5.1> 과같은방식으로이루어진다. < 그림 5.1.Tendermint voting process> 텐더민트는비잔틴결함을감내하기위해 3f+1 규칙에따라최소 4 명의검증인이필요하다. 각검증인은퍼블릭키를통해신원을확인하며, 모든제안과투표는각검증인의프라이빗키를통해서명이이루어지는데, 이때디지털서명은비대칭암호키쌍 (asymmetric cryptographic key-pair) 을사용한다. 이를통해서, 제안과투표의유효성을검증할수있다. 합의 (consensus) 는라운드 0 에서시작하며검증인리스트 L에서의첫검증인이첫번째블록제안자가된다. 라운드별결과는항상 commit 을하거나다음라운드로이동하는결정 (decision) 두경우로나뉜다. 여러번의라운드를통해네트워크가비동기이거나검증인에게문제가생기는경우에도합의에도달할수있는기회가제공한다. 여러번의라운드가발생할수있는상황은다음과같다. 네트워크가지연될때 지정된블록제안자가온라인상태가아닐때 46
지정된블록제안자가생성한블록이유효하지않을때 지정된블록제안자가생성한블록을제때전송하지않을때 제안된블록은유효하나검증인들이 pre-commit 단계에진입할때 2/3 이상의 prevote 를제때수신하지못할때 제안된블록도유효하고충분한숫자의검증인이 2/3 이상의 prevote 하였지만 2/3 이상의 pre-commit 을수신하지못했을때 이런문제를극복하기위해텐더민트는매라운드마다새로운블록제안자가선택된다. 블록제안자선정방식은 <5.1.4 Leader Selection Procedure> 에서좀더자세히 알아본다 5.1. Consensus 1. 제안 (Proposals): 각라운드마다정직한제안자는새블록을생성한다. 제안이제때도착하지못하면, 해당제안자의순번은건너띈다. 2. 투표 (Votes): 최적의비잔틴결함내성을보장하기위해투표는 pre-vote 와 precommit 두단계를거친다. 동일한라운드 (round) 에서 2/3 이상의지분을가진검증인 (validator) 이 pre-commit 하면블록은커밋 (commit) 된다. 3. 잠금 (Locks): 텐더민트는두명의검증인이동일한높이에서서로다른블록을커밋하지못하도록잠금매커니즘 (Locking mechanism) 을활용한다. 잠금매커니즘은동일한높이에서이전 pre-votes 와 pre-commits 에따라서, 다음라운드에서검증인이 pre-vote 또는 pre-commit 할지결정하는방식이다. 5.1.1 Proposal 한라운드는 Propose>Prevote>Precommit> 순서로진행되며, 동일한높이의블록제안 (proposal) 이매라운드의시작이다. 라운드별제안자는 Mempool( 블록이포함되기전의트랜잭션저장소 ) 에서최근수신된트랜잭션을가져와서, 블록을생성하고, 서명된 47
제안자메시지 (ProposalMsg) 를전송한다. ( 만약블록제안자가비잔틴이라면, 다른검증인에게다른제안을전송하게된다.) 결정론적인라운드로빈 (round robin) 방식을통해블록제안자순서가정해지기때문에각라운드별단한명의검증인만이유효하다. 만약제안이낮은숫자의라운드에서수신되거나비잔틴제안자에서온다면, 해당제안은거부된다. 텐더민트는투표와잠금매커니즘을통해 safety 를확보하며, 제안자순환을통해 liveness 를유지한다. 따라서, 한명의제안자가트랜잭션을제때처리하지않으면다른검증인이뒤이어서처리한다. 5.1.2 Votes 투표는두단계 (Pre-vote, Pre-commit) 를거쳐서진행되며, 성공적으로 2/3 이상의검증인 (stake, 지분 ) 이동일라운드의같은높이의블록을 pre-commit 하면해당블록은성공적으로 commit 된다. 비잔틴검증인이존재할수있는비동기환경에서는단일투표단계는 safety 를충분히보장하지못한다. 단일투표단계에서는검증인들은제안이무엇인지서로알수있다. 그러나비잔틴결함을극복하기위해서는, 검증인은다른검증인들이해당제안에대해알고있는사실들을서로에게알려줘야한다. 쉽게말해서, 두번째투표단계를통해서검증인들은첫번째투표결과를충분히알수있어악의적인검증인의행동을알아차릴수있다. Pre-vote 에서의블록투표는블록을커밋하기위한준비단계이다. Pre-vote 에서 nil 에투표는다음라운드의이동을의미한다. 즉, 2/3 이상의검증인이제안을 prevote 하게되면올바른방향으로진행됨을알수있다. 한라운드에서하나의블록이 2/3 이상의 pre-vote 가이루어졌으면이를 polka 라부르며, 반대로 nil 에투표가진행되었다면 nil-polka 라한다. ( 현재는자주언급되는개념은아니지만해당글에서는 polka 의미를사용한다.) 만약검증인이 ProposalTimeout내에유효한제안을수신받지못하면, pre-vote 에는 nil을선택하게된다. 성공적으로검증인이 polka 를받으면, 해당블록의 pre-commit 투표를서명하고전파하는단계에돌입한다. 그러나종종네트워크비동기성때문에, 특정검증인은 polka 를받지못하는상황이있을수있다. 이경우검증인은해당블록을 pre- 48
commit 으로서명할수없기에 pre-commit 투표는 nil 에서명한다. 바꿔말하면, polka 를받지못한검증인이 pre-commit 을서명하면, 이는비잔틴행위이다. 이제검증인이한개블록의 2/3 이상의 pre-commit 을받으면, 해당블록은커밋 (commit) 되고, 다음높이에서새로운라운드 0 이시작된다. 마찬가지로, 검증인이 2/3 이상의 pre-commit nil 을수신하면다시블록을만들기위해다음라운드로이동한다. 5.1.3. Locks 동일한블록높이에서에서서로다른두개의라운드및블록이만들어지는상황을피하기위해텐더민트는잠금매커니즘 (Locking mechanism) 을활용한다. 2/3 이상의 prevote 를의미하는 polka 를통해 pre-commit 이정당화된다. 잠금규칙에는 Prevotethe-Lock 과 Unlock-on-Polka 총 2 가지가있다. Prevote-the-Lock : 특정블록에잠긴검증인들은반드시 pre-vote 해야하며, 제안자인경우블록을반드시제안해야한다. 이를통해검증인들이첫라운드에서동일한높이에서한개의블록에대해 pre-commit 하고다음라운드에서다른블록의 polka 를외치는것을막기위함이다. (Safety 와연관된사항 ) Unlock-on-Polka: 검증인들은자신들이잠금된라운드보다높은라운드에서 polka 가이루어졌다면, 잠금을해제하고 (unlock) 새로운블록에서 precommit 을한다. 이를통해검증인들이어디한곳에갇혀합의에도달하지못하는상황을막는다. 쉽게말해, 시스템이멈추지않고계속동작하도록한다. (Liveness 와연관된사항 ) 49
검증인이매블록높이에서 round-1 에 nil 을투표해서잠금됬을경우, 새로운블록높이에서 polka 를보기전까지 pre-commit 할수없음을 Unlock-on-Polka 를통해알수있다. 잠금매커니즘의직관적인이해를돕기위해검증인예시를통해알아보자. A, B, C, D 총 4 명의검증인이있으며특정라운드 R 에서블록 X 에대한제안을가정한다. 블록 X 의 polka 가이루어졌지만 A 는확인하지못해 pre-commit nil 을한다. ( 물론나머지 B,C,D 검증인은 pre-commit 한상태 ) 이제비동기네트워크로단지지연이발생한상황에서모든검증인의 pre-commit 을확인한사람은 D 이며, B 와 C 는 D 의 pre-commit 을보지못했다고가정해보자. (B 와 C 는서로 pre-commit 한사실과 A 의 pre-commit nil 을확인한상태 ) D 는 2/3 가블록을 pre-commit 한사실을확인했음으로블록을커밋 (commit) 하지만나머지 B 와 C 는합의에필요한정족수를채우지못했음으로 R+1 로이동한다. 검증인 D 는이미블록 X 에커밋을했기때문에 R+1 라운드에는새로운제안자가블록 Y 를제안하고투표가진행될경우, safety 가훼손된다. ( 누구도비잔틴이아닌상황 ) 검증인 D 의경우나머지검증인 B 와 C 의 pre-commit 을보고블록 X 를커밋했기때문에, 잠금매커니즘을통해이미 pre-commit 한검증인 D 는블록 X 를유지한다. 특정라운드에 2/3 이상의 pre-commit 된블록이있을경우, 해당블록은잠금된다는사실을잊지말자. 즉, 더높은라운드에서새로운블록에유효한 polka 를만들어낼수없다. 이를 Prevote-the-Lock 이라한다. 그러나 liveness 를희생하지않기위해서는잠금을해제하는과정이필요하다. 특정라운드에검증인 A 와 B 가블록 X 에 pre-commit 했고검증인 C 와 D 가 pre-commit nil 을해서투표가양분된상황이라고가정해보자. 이경우모든검증인이다음라운드로이동하고 C 와 D 가 pre-vote 하기위한블록 Y 가제안된다. (A 와 B 는이미블록 X 에 pre-commit 했음으로잠금된상태 ) 이제검증인 A 가비잔틴노드여서, 블록 Y (block X 에잠금되었지만 ) 에또 pre-vote 를해서 polka 가만들어졌다고가정해보자. 이제, 검증인 B 는 polka 를보지못한상태여서 pre-commit nil 을한상황이지만검증인 C 와 D 는블록 Y 에 pre-commit 한상황이다. ( 악의적인검증인 A 는 off-line 으로전환한상태 ) 비잔틴합의에도달하지못하였음으로다음라운드로이동한다. 검증인 B 는여전히 50
블록 X 에잠금되어있고, 검증인 C 와 D 는블록 Y 에잠금되어있다. 비잔틴검증인인 A 는 offline 상태이기때문에절대합의 (polka) 에도달하지못한다. 이런딜레마를해결하기위해검증인 B( 블록 X 에잠금된상태 ) 가블록 Y 의 polka 를확인했다면, 잠금을해제하고블록 Y 에 pre-commit 할수있다. 이것이 Unlock-on-Polka가필요한이유다. 5.1.4 Leader Selection Procedure <21> 앞서서소개한블록제안자선택절차에대해서알아본다. 텐더민트에서는각제안자는 결정론적 6 으로선택이이루어지며선택의횟수는아톰의총본딩물량 ( 자가 물량 + 위임자로부터받은물량 ) 에좌우된다. 예를들어, 모든검증인의아톰본딩총합이 100 아톰이라고가정해보자. 이때 A 라는검증인의총본딩물량이 10 아톰이라면 10% 확률로다음블록제안자가된다. 텐더민트검증인은라운드로빈방식으로블록제안자로선택된다. 라운드로빈방식이란리스트의최상위순번에서최하위순번으로차례대로순번이돌아간다는뜻이다. 마지막순번이끝나면다시제일위상위순번에게순서가돌아간다. 텐더민트제안자선택에서이순번을정하는핵심요소가바로투표력 (Voting power) 이다. 첫블록라운드가시작되면검증인의총투표력 ( 자가물량 + 위임자로부터스테이킹받은물량 ) 과아쿰 (Accum) 이 0 인상태서시작된다. 제안자선택에서는투표력을 Accum 으로표시하여이해를돕고있다. 각라운드가진행될때마다 IncrementAccum 기능을통해검증인의 Accum 이자신의투표력만큼상승한다. 이때, 각라운드별투표력이가장큰검증인이제안자로선택된다. 6 결정론적알고리즘 (deterministic algorithm) 은예측한그대로동작하는알고리즘이다. 어떤특정한입력이들어오면언제나 똑같은과정을거쳐서언제나똑같은결과를내놓는다. 51
검증인제안자선택방식은다음검증인 A,B,C,D 예시를통해좀더자세히 확인해보자. 먼저, < 표 5.2> 처럼, 검증인 A,B,C,D 의투표력이각각 10,20,30,40 으로총 투표력이 100 이라고가정해보자. < 표 5.2. Tendermint Proposer Selection Procedure> 첫라운드가시작되고각검증인의 Accum 은자신의투표력에비례하여 < 표 5.3> 과같이 상승하였다. < 표 5.3. Tendermint Proposer Selection Procedure> D 의 Accum 이가장높기때문에첫라운드는블록제안자는 D 가된다. 첫라운드 제안자가된 D 의 Accum 은총투표력 (100) 만큼떨어져서 < 표 5.4> 과같은수치가된다. 52
< 표 5.4. Tendermint Proposer Selection Procedure> 두번째라운드가시작되고각검증인의 Accum 은자신의투표력만큼상승한다. < 표 5.5. Tendermint Proposer Selection Procedure> 두번째라운드제안자는 Accum 이가장높은 C(60) 가된다. 제안자가된 C 의 Accum 은 총투표력 (100) 만큼떨어져서 < 표 5.6> 과같은수치가된다. < 표 5.6. Tendermint Proposer Selection Procedure> 53
세번째라운드가시작되고각검증인의 Accum 은자신의투표력만큼다시상승한다. < 표 5.7. Tendermint Proposer Selection Procedure> 세번째라운드의 B 가가장큰 60 Accum 을가지게되어블록제안자가된다. 제안자가 된 B 의 Accum 은총투표력 (100) 만큼떨어져서 < 표 5.8> 과같은수치가된다. < 표 5.8. Tendermint Proposer Selection Procedure> 네번째라운드가시작되고각검증인의 Accum 은자신의투표력만큼상승한다. < 표 5.9. Tendermint Proposer Selection Procedure> 54
네번째라운드의 D 가가장큰 Accum 을가지게되어블록제안자가된다. 제안자가된 D 의 Accum 은총투표력 (100) 만큼떨어져서 < 표 5.10.> 과같은수치가된다. < 표 5.10. Tendermint Proposer Selection Procedure> 지금까지텐더민트의 BFT+BPOS 컨센서스알고리즘을알아보았다. Internet of Blockchains 으로디자인된퍼블릭블록체인코스모스네트워크는이개선된합의알고리즘으로점점더구체화되고있으며, 다년간의개발의결실이얼마남지않은코스모스메인넷으로꽃피우게될것이다. 55
5.2. Use Case: Tendermint test with 4 nodes [22] 텐더민트의합의프로세스에이어이번에는실제로텐더민트가어떻게작동하는지 도커 (Docker) 를통해멀티노드를구성하여 PBFT 합의의작동테스트를진행해보았다. 테스트순서 docker-compose 를이용하여 4 개 node 의 tendermint core 를구동 각 tendermint core 에구동될 ABCI 서비스구동 (key & value 저장 ) 테스트 transaction 을발생및 Consensus (BPOS+PBFT) 의 +2/3 합의과정을확인 docker-compose 는개별 docker container 들을하나의네트워크로묶어주고구동, 정지및상태모니터링등을관리해주는도구이다. 테스트노드구성도 < 그림 5.2. docker-compose 4-nodes 구성 > 56
텐더민트검증자 (Validator) 는라운드로빈 (Round Robin) 방식으로블록제안자 (Proposer) 를선택하며이때, Voting Power 를기준으로순서가정해진다는사실을 앞서서확인하였다. ( 여기에서는각노드의 voting power 를동일하게 10 으로지정하였다 ) 구동및확인 1. docker-compose 로노드구동하기 < 그림 5.3. Docker-Compose 로노드구성 > 2. docker-compose node 인스턴스확인 57
< 그림 5.4. Docker-compose 로노드인스턴스확인 > 텐더민트의 Voting Process 확인 58
< 그림 5.5. 텐더민트의 Voting Process > 트랜잭션발생및블록생성확인순서 1. 트랜잭션발생 2. New Round 의 Proposer 선택 3. Proposer 의 Validation 과정 4. 생성된블록확인 1. 트랜잭션발생 key:value 값을블록에저장하는 kvstore abci 서비스로트랜잭션을발생시킨다. $ curl -s 'localhost:46657/broadcast_tx_commit?tx="abcd"' 2.New Round 의 Proposer 선택 텐더민트노드에서 validation 을위한 Proposer 선택은 Validation Power 를 기반으로하는 Round-Robin 방식으로선택된다. 59
< 그림 5.6. New Round 에서 Proposer 선택 > 각 node 의로그를확인해보면 node3 이현재발생한트랜잭션을처리하기위한블록 Proposer 로선택되었다는사실을 < 그림 5.6> 을통해확인할수있다. enterpropose: Our turn to propose 메시지확인 3.Proposer 의 Validation 과정다음으로, node3 의 Voting 과정을로그를통해서확인해보자. 다음은 99 Height 의새로운블록이생성되고 Voting validation 이완료되어새로운블록이생성되는과정의로그이다. 60
< 그림 5.7. Proposer 의 Validation 과정 > < 그림 5.7> 의로그를 Voting 순서에맞도록나누어서 < 텐더민트 Voting Process > 7 가지의과정으로확인해보자. < 그림 5.8. Consensus Process> 99 번으로 NewRound 가시작된다. 61
확인해보면다음과같이확인이된다. node3 이 Proposer 로선택되었다. 이때, Proposer node 의 ID 를 NODE1 : 7DF7317A9FB25305540BDE9B8B10BA62134782EB NODE2 : 35D784137255623F499AE56C9530374BD00C6107 NODE3 : 645AB334CEE4FA0B1CAA45363D8A3E6F349D010E <-현재블록의 Validator> NODE4 : 500FB1138FC7FC1CC241ED6815C6EF923E825767 < 그림 5.8. 현재블록의 Validator> < 그림 5.9. Added to Prevote> Added to prevote 로전체 4 개 Validator 중순차적으로 node3, node1, node2 가 검증자 (Validator) 로서 Prevote 를했음을알수있다. 62
전체노드의 +2/3 이 prevote 되길기다리다가, +2/3 를충족하는 순간 prevoted proposal 이 block 이 locking 된다. locking 이후에들어온 prevote 도들어오지만이미 +2/3 은충족된다. < 그림 5.10. Locking 이후 prevote 충족 > 다음단계로 Added to precommit 메시지가 조건을충족하게된다. 순차적으로들어와서 +2/3 precommit 의 < 그림 5.11. precommit 충족 > 63
+2/3 precommit 의조건이완료되면, 최종으로해당블록은 commit 된다. < 그림 5.12.> 의로그를통해최종생성된블록정보를확인할수있다. < 그림 5.12. 로그최종생성된블록정보 > 64
생성된블록과트랜잭션정보를확인해보면 < 그림 5.13.> 과같이체크해볼수있다. < 그림 5.13. 생성된블록과트랜잭션정보확인 > 텐더민트를실제로도커를이용해 4 개의노드로구성하여테스트를진행하였다. 이를통해실제로텐더민트가어떻게합의과정을이루는지알수있었다. 텐더민트의경우 2/3+1 개의합의가각스텝에서모여야하며어떤경우에도서로다른두블록이동시에생성되지않는다. 그러나이러한전송메시지는시간안에도달하는것을보장못하는비동기네트워크에서는사용되기어려울수있다. 앞서서언급하였듯이, 비동기시스템모델의경우메시지가전송되는것을보장하는상한시간이없기때문에메시지가전달실패또는거의무한히지연될수있다. 반대로시간안에메시지를보장하는동기성시스템모델을분산시스템에서사용하는것도무리가있다. 따라서텐더민트에서는동기성시스템과비동기시스템의특성을번갈아가면서 65
사용하는데, 이를부분동기성 (Partial Synchrony) 이라한다. 부분동기성시스템에서는정해진시간 (fixed time) 안에메시지가도착하는것은보장하지만얼마나걸리는지에대한시간 (unknown amount of time) 은알수없다. 다시말해, 네트워크안에서정해놓은시간안에는도착하지만그정해진시간을노드들은파악하지못함을이야기한다. 이처럼분산시스템혹은블록체인과같은 P2P 컴퓨팅방식을합의하는과정에서어려움을많이겪는다. 66
6. Conclusion 본리서치를통해분산시스템에서의합의과정은매우제한된조건에서만족함을알수있었다. 이는블록체인에서도완벽하게해결을하지못한다. 그러나최초에나온비트코인의작업증명방식은 FLP Impossibility 를우회적으로해결하기위해 Liveness over Safety 를선택하며, BFT 기반의텐더민트는 Safety over Liveness 를선택한다. 이더리움 (Ethereum) 의경우현재작업증명방식 (Proof-of Work) 을통해 Liveness 를지분증명방식 (Proof of Stake) 의형태인 Beacon chain 을통해 Safety 까지보장하려는 Casper the Friendly Finality Gadget (Casper FFG) 을목표로개발을하고있다. (Casper FFG 는토큰이코노미분과자료를통해경제학적인모델설계까지고려하고있음을확인할수있다.) 현재블록체인에서는수많은합의알고리즘방식이등장하고있다. 그러나흔히들혼동되는것은합의를하는과정과합의를가지는주체의차이이다. 가령 BFT 계열의합의알고리즘은이더리움, EOS, 텐더민트등이있다. 이들이합의하는과정을 BFT 계열로한다면이를실제로처리하는이들은우리가알고있는 PoS, DPoS, BPoS 등이다. 합의과정과주체를혼동하지않도록주의가필요하다. 앞선몇가지의논문을가지고분석을진행하였지만, 본리서치만으로합의하는과정을모두정리했다고볼수없다. 추후리서치를통해 Paxos 혹은하이퍼랫져 (Hyperledger) 등에서사용하는 Raft 등에대한리서치를통해분산시스템에서의합의과정을더욱심도있게연구할계획이다. 67
APPENDIX CAP and PACELC: The Classifying Criterion for Distributed Computer System 1. Introduction of CAP theorem 기술리서치분과는분산시스템내에서합의알고리즘에대한리서치를수행하였다. 이과정에서 CAP Theorem 을이용한 Private Blockchain 의합의알고리즘을분류하려는시도가있음을발견하였다. 해당문서는 Proof-of-Authority(PoA) 와 PBFT 를 CAP Theorem 을기준으로유형화하는논문 (PBFT vs proof-of-authority: applying the CAP theorem to permissioned blockchain: University of Southampton) [24] 이다. PBFT 리서치의일환으로해당논문에대한리서치를진행하던중, 많은이들이 CAP 과 FLP 의개념에대한혼동이있음을발견할수있었다. 해당이론은블록체인의근간이되는분산컴퓨팅의기초에직결되는아이디어이므로본분과에서는깊은관심을가지고리서치를진행하였다. 그러나, 이러한논문은거시적합의알고리즘자체에집중하고있는본연구보고서에적합하지않다고보았다. 미시적통신이론인 CAP 과 PACELC 을자세히설명하는것은본연구보고서의전반적인흐름과다르다고판단하였다. 그러나 CAP 과 PACELC [28] 이론은블록체인의근간이되는분산컴퓨팅분야에서비중있게다루어진다는점, 비중있게다루어지는이론임에도불구하고학계에서 CAP 이론에대한해석의여지가모두다르다는점, 국내에 PACELC 이론이자세히소개된적이없다는점을고려하여 Appendix( 부록 ) 에별도로서술하기로결정하였다. Appendix 에서는미시적통신의가부여부를판단하는 CAP 이론에대해알아보고자한다. 이후, CAP 의한계점을지적한뒤이를보완하는새로운개념인 PACELC 를설명하고자한다. PACELC 에기초해현존하는합의알고리즘을분류할것이다. 이를통하여다양한합의알고리즘이어떠한부분을강조하고포기하는지에대하여알아보고 FLP 와분명히다른것임을알아본다.. 68
2. CAP 이론소개 [26,27,28, 33, 35] 분산컴퓨팅시스템에서네트워크의원활한운영을촉진하기란어려운법이다. 컴퓨터과학자인에릭브루어 (Eric Brewer) 는 [25,26] 2000 년 7 월 19 일 PODC (Symposium on Principles of Distributed Computing) 에서 CAP 이론을발표하였다. CAP 이론은분산데이터베이스시스템을바탕으로, 네트워크분할허용 (Network Partition) 이이루어지는경우에일관성 (Consistency), 가용성 (Availability) 을동시에만족하는것은불가능하며이들사이에양자택일해야한다는이론이다. CAP 이론에따르면모든분산네트워크는일관성을지키는상황 (Consistency- Partition Tolerance: CP) 과가용성을지키는상황 (Availability-Partition Tolerance: AP) 으로나눌수있다고보았다. 모든노드는데이터를업데이트하는과정에서다른작업이불가능하다. 따라서업데이트가진행되는시간에는일시적으로데이터베이스에접속할수없게되어서비스가중지된다. 모든노드에정보를업데이트하여일관성 (Consistency) 을지키되가용성 (Availability) 을포기할것인가? 혹은일부노드에만정보를업데이트하여가용성 (Availability) 을지키되일관성 (Consistency) 를포기할것인가? 에대한문제이다. 각용어에대한의미에대해자세하게파악해보자. 2.1 네트워크분할허용 (Network Partition) - 노드간의통신이실질적으로어려운상태에도달하여네트워크가사실상 분할 (Partition) 되었을때도네트워크가정상적으로작동할수있는경우를의미한다. 네트워크분할허용을전제하는네트워크는노드간의통신이완전히불가능하거나비동기성네트워크 (asynchronous network) 에서메시지가유실될수있고, 현실성이떨어지는시간에메시지가전달될수있다. 이러한상황에서도최종사용자 (End- User) 입장에서는문제없이네트워크를이용할수있어야한다. 다시말해, 최종사용자가 69
하나의분산네트워크가여러가지의노드로나뉘었다는사실을인지하지못하도록하여야 한다. 분산네트워크가단일네트워크처럼보여야유의미하다고말할수있다. 모든분산네트워크는네트워크분할허용성 (Network Partition, P) 을보유할수밖에없다. 현실적으로노드간의네트워크통신은다양한환경적조건에따라서불안정해질수있기때문이다. 또한, 모든분산네트워크는비동기성네트워크 (asynchronous network) 상황에처해질가능성이존재한다. 분산네트워크는노드간의통신이불안정하더라도네트워크가정상적으로동작할수있도록한다는것에의의가있다. 따라서분산형네트워크에서분할허용성을가정하지않는다면사실상의미가없어지게된다. 즉, CAP 이론에서는네트워크분할허용 (P) 을기본으로전제한다. 2.2 일관성 (Consistency) - 모든요청은최신데이터또는에러를응답받는다. 일관성 (Consistency, C) 은최신데이터의전파속도및업데이트노드양에따라서그 강도가다르게분류된다. 그러나 CAP 이론이초창기에소개될때어느강도의일관성을 70
의미하는지에대해서실질적으로명시된바가없었다. 애시당초 CAP 이론은 Brewer 가 제시한가설에불과하였으므로구체적인근거를제시하지않았다. CAP 이론을추후에 Lynch 가증명할때 Linearizability(Atomic/Strong Consistency) 를일관성의기준으로설정하였다. 이외에도증명을위하여읽기와쓰기권한만을싱글스레드로순차적으로처리하는 Simple Service 를가정하였다. Linearizability 는 Operation A 가성공적으로종료된이후에 Operation B 가시작될때, Operation B 는 Operation A 의최종결과치를모든시스템에서하나의동일한상태 (the same state) 로같은논리적시간 (logical time) 에업데이트되어관찰할수있어야한다는기준이다. 즉, 한노드에서특정데이터의처리가완료되었을때다른노드가동시다발적으로업데이트된정보에접근할수있어야한다는것이다. 따라서 Lineraizability 는매우강력한형태의일관성을요구한다. 쉬운이해를담보하기위하여 Not Linearizable 한시스템을시나리오로 이야기해보자. 철수는근처펍에가서 2018 월드컵조별리그, 한국대독일의경기를보고있다. 영희는한국이이기지못할것으로생각하고, 학교에서시험공부를하고있던찰나여서경기를보지못하고있다. 경기가끝나고한국이 2:0 으로이겼다. 철수는감격한나머지포털사이트에접속해서경기결과를재확인했다. 철수는영희에게카카오톡으로메시지를보내경기결과를알려주었다. 한국이무려 2:0 으로승리했다는사실을듣고영희는포털사이트에접속했다. 그러나영희가접속한포털사이트에는여전히게임이진행되고있다라는표시가뜬다. 철수는최신업데이트가된정보를받을수있었다. 하지만영희는받지못했다. 철수와연결된서버노드는월드컵경기가끝나고결과를확인했다. 그러나영희와연결된서버노드는새로운결과를받지못했다. 즉, 가용성을우선시하고 Linearizable 한일관성을포기한것이다. 2.3 가용성 (Availability) - 정상적으로이루어진모든요청은정상적으로작동하고있는모든노드로부터응답을받을 수있다. 71
일반적으로우리가높은가용성 (High Availability) 라고일컫는경우는다음과같다. 우선높은가용성은시스템자체가모든요청에대한정상적인응답을할수있다는것을전제한다. 따라서모든요청은정상적으로작동하고있는노드중일부만응답을받을수있어도충분하다. 하나의정상노드만응답해도시스템은가용이가능하다고 (Available) 말할수있기때문이다. 또한높은가용성을가정하는데이터베이스는현실적인응답시간 (realistic response time) 을고려한다. 그러나 CAP 이론에서의미하는가용성은높은가용성보다훨씬높은난이도를요구한다. 높은가용성을보장하는서버는일반적으로 CAP 이론이주장하는가용성에해당하지않는다. CAP 이론에서주장하는가용성은다음과같다. 우선오류가없는노드가발송한메시지는오류가없는모든노드로부터응답을받을수있어야한다. 데이터저장소에대한모든동작이오류가없는모든노드로부터성공적으로리턴을받아야한다. 또한가지주목해야할점은 CAP 이론의가용성은응답시간에대한제한을걸어두지않는다 (unbounded response time) 는사실이다. 다시말하면응답시간 (Latency) 에대한고려가부재하다는것이다. 분산형네트워크는기본적으로응답시간이실사용에있어서중요한고려요소 (consideration) 이될수밖에없다. 기본적으로분산형네트워크는단일네트워크보다속도가느리다. 그이유는모든또는일부데이터를복제하여저장하고자하기때문에정보의전파과정에서일정한시간이필수적으로요구되기때문이다. 하나의데이터를복제하여저장해야하는노드의수가많아질수록속도가느려진다. 그렇다고해서속도가치명적으로느린네트워크는실제사용하기에큰장애가있을것이다. 가용성은응답시간과깊은관련이있음에도 CAP 이론에서는이를고려하지않는다는단점이있다. CAP 이론의가용성에따르면아무리늦게보내도받기만하면충분하다. 특정데이터를 20 시간뒤에받는다면 CAP 의가용성에는부합할지모르나실제사용시에는부적합하다고보아야한다. CAP 이론이이야기하는네트워크분할용이성 (Network Partition) 에따르면노드간의통신이완전히불가능한경우도상정한다. 이러한경우, 완전한 CP (Consistency- 72
Partition Tolerance) 시스템은존재할수없다. 노드간의통신이끊어진상황에서데이터를업데이트하는것이불가능하기때문이다. 분산네트워크의기본적인특징을설명하는 ACID 이론에따르면, 모든네트워크는고립성 (Isolated) 이존재한다. 트랜잭션이실행이되는중에생성하는연산의중간결과는다른트랜잭션이접근할수없다는것이다. 다시말하면, 트랜잭션을처리할때다른트랜잭션이연산작업중간에끼어들지못하는것이다. 트랜잭션실행내역이연속적이어야하기때문이다. 노드간의네트워크가물리적으로는끊어지지않았으나원활한통신을보장할수없는 경우에는다음과같은선택지가나타날수있다. Choosing Availability over Consistency (AP 시스템 ) AP 시스템은가용성을우선시하므로모든 request 에응답하게될것이다. 또한 stale reads 를허용하게될가능성이높고서로충돌되는데이터가쓰여질가능성이높다. 완벽한가용성을지니는시스템은정상적인모든노드가어떤상황에서라도응답할수있어야한다. 하나의노드가네트워크파티션으로고립되었을때고립된노드의데이터는일관성이깨지므로쓸모가없어진다. 그러나정상적으로응답을하면완벽한가용성을 73
지닌다. 이러한사실을모르는사용자는문제를인지하지못하고요청을계속해서보낼 것이다. Choosing Consistency over Availability (CP 시스템 ) CP 시스템은완벽한일관성을갖는분산시스템으로하나의트랜잭션이다른모든노드에완전히복제된후에야그다음작업으로넘어갈수있다. 네트워크가완전히분리되어노드간의통신이불가능한경우가용성을잃게된다. 노드간의통신이가능한현실적인경우에는성능의희생을필요로한다. 하나의노드라도문제가생기면트랜잭션은실패한다. 노드가늘어날수록지연시간은길어질수밖에없다. 일부 request 는경우에따라정상적인모든노드가 refuse 할수있다. 시스템전체를일시적으로정지시킬수도있고 (single-node data store clients) 또는아예쓰기를거부할수도있고 (Two-Phase Commit) 또는마스터노드만파티션부분 (partition component) 에쓰기를할수도있다. 예시로는 Membase 가있다. 3. CAP 이론의한계 [27,30,31, 33] CAP 이론은분산네트워크시스템에서새로운아이디어를제시했다는점에서의미가있으나엄밀하지못한이론이라는점에서실제분석에적용하기에는두가지의문제점이존재한다. 3.1 편협한정의로인한상대적인관점의부족 CAP 이론의가장큰문제점은일관성과가용성이배타적이라고전제한다는것이다. 일관성과가용성은상호배치되는속성인것은사실이다. 그러나일관성과가용성이무조건양자택일의관계라고주장하기에는어폐가있는것이사실이다. 완벽한 CP 시스템과 AP 시스템은존재하지않고필요하지도않다. 모든데이터베이스는상대적인관점을바탕으로설계된다. 가용성을중시하면서일관성을일부포기하거나, 일관성을중시하면서가용성을일부포기하는것이다. 그러나 CAP 이론은일관성과가용성중하나만을선택하라고강요한다. 74
이러한양자택일의속성은 CAP 이론이증명과정에서채택하는일관성과가용성의정의가편협하다는것에비롯된다. 한쪽이업데이트되면다른쪽도동시다발적으로업데이트되어야하며, 정상적인모든노드가모든요청을 100% 응답할수있어야한다는가정은실제세계에서이루어질수없는수준의가정이다. 실제설계에서채택되는상대적인관점을고려할수없다는것이 CAP 이론의가장큰문제점이다. 3.2 Network 에대한적용범위협소 CAP 이론에따르면네트워크분할용인성은노드간의통신이완전히불가능한경우를위주로고려한다. 다시말해서, 물리적인이유로인하여노드간의통신이불가능하여상호간의업데이트가전혀일어날수없는경우를위주로설명한다. 물론굳이물리적인이유가아니더라도소프트웨어적인문제로인하여유의미한시간에노드간데이터가정상적으로 ( 실질적으로 ) 통신될수없는경우까지포괄한다. 실제로작동하는데이터베이스에서완전히또는실질적으로통신이불가능한경우를찾기는쉽지않다. 모든데이터베이스는일반적으로노드끼리서로유의미한시간에데이터를주고받을수있는환경에있다. 이러한경우에는각노드간의정보업데이트가원활하게이루어질수있다. 이를부분동기성네트워크 (Partial Synchronous Network) 라고지칭하겠다. CAP 이론은부분동기성네트워크의경우를고려하지않는다. 네트워크분할용이성이포괄하는범위가지나치게협소하여노드간의통신이정상적으로이루어지는부분동기성네트워크의경우를무시하였기때문이다. 해당내용은가용성 (Availability) 부분에서이미자세하게소개하였다. 따라서실질적으로 CAP 이론을적용할수있는네트워크또는데이터베이스는많지않다. Single-reader replication 의사례를보면다음과같다. 이는하나의 single leader 를 replicated database 에쓰기작업을할수있는일반적인경우이다. 이러한설정에서 client 가 leader 로부터 partition 되는경우에해당데이터베이스는전혀사용가지가없게된다. 따라서엄밀한의미에서 CAP-available 하지않다는문제점이있다. 75
예를들어서, 새로운 data 가나왔는데제대로된응답을해주지못하기때문이다. 따라서 CA 시스템이아니다. 그렇다면이경우가 CP 시스템이라고할수있을까? 그렇지않다. client 가읽기작업을한다는것은일반적으로비동기성 (asynchronous) 을전제한다. 따라서클라이언트가읽기작업을하는순간에쓰기작업을수행하는리더보다뒤쳐질가능성이있다. 그러므로완전한 Lineraizability 를충족하는일관성이있다고보기어렵다. 편협한정의로인하여일관성과가용성이대치되지않는것이다. 4. PACELC Theorem [28, 29,30,34] [ 사진출처 : http://eincs.com/2013/07/misleading-and-truth-of-cap-theorem/] CAP 이론은분산시스템의특징을명료하게드러내준다. 고민할만한지점을던져준것은유의미한일이다. 그러나실제적용하기에는편협한정의로인하여여러이유로무리가있는것이사실이다. 일관성과가용성은상충관계에있지만절대적인것은아니다라는것이다. 다소약한가용성을지니지만상대적으로강한일관성을지닐수있고, 다소약한일관성을지니지만상대적으로강한가용성을지닐수있다. 가용성과일관성은서로대치되지만궁극적으로일치되는것을목표로하기때문에상대적이라는것을알수있다. 다른한가지는네트워크노드간의연결이원활한경우이다. 노드간의통신이원활한경우에는 CAP 이론이정의하는네트워크분할용이성 (Network Partition) 의정의에해당하지않는다. 결론적으로이러한경우는해석하지못한다. 분산네트워크에서는특정 76
노드가추후오류가나서임의의데이터에접근하지못하는경우를배제하기위하여다른노드에도데이터를복사하여저장한다. 이러한경우에도분산네트워크가지니는대칭적특성이드러난다. 이는앞서설명한것으로, 속도 (latency) 와일관성 (consistency) 간의문제이다. 최대한많은노드에데이터를하나하나전파할수록일관성은높아지지만속도는떨어지게된다. 네트워크에전파되는데이터의가용성역시 ACID 이론이설명하는고립성 (Isolated) 특징에따라낮아진다. 이러한 CAP 이론의한계를극복하기위하여나온것이바로 PACELC 이론이다. PACELC ( 파셀크라고읽는다 ) 는 CAP 의한계점을보완하기위하여등장한분류방법이다. PACELC 이론은네트워크노드간의통신이불가능한상황과가능한상황을나누어서판단할수있도록한다. 만일불가능한상황에는 CAP 이론의축을따른다. 노드통신이가능한경우에는속도와일관성을배치되는축으로놓는다. 또한, Latency 와 Availability (Partition 이없을경우 ) 및 Consistency 와 Availability (Partition 이있을경우 ) 에대해서양자택일을강요하기보다는하나의스펙트럼으로바라볼수있도록하는관점을제공한다. PACELC 에따라네트워크의유형을구분하려면선제적으로노드간의정상적통신이가능한상태인지를확인해야한다. 분산시스템에서노드끼리정보를교환할때타임아웃 (time-out) 이발생하는모든경우를통신의실패라고분류한다. 분산시스템에서정상적인통신이원천적으로불가능한경우를가정하는것을 Partition 되어있다고표현한다. 만약정상적인통신이가능하다는전제가있다면네트워크에 Partition 이일어나지않았다고표현할수있다. 77
PACELC 이론은기존의 CAP 이론이주창하는축에파란색축을하나더두었다. 이는지연시간과일관성을배치되는축으로두는형태이다. 아래쪽에위치할수록지연시간이짧아지며, 위쪽에위치할수록지연시간은길어지고일관성은높아진다. 네트워크노드간의통신이원활한상황에서일관성에치우칠수록더많은데이터를복제하여전파해야하기때문에지연시간이그만큼길어질수밖에없다. PACELC 이론은네트워크장애상황과원활상황에서시스템이어떻게작동하는지에따라시스템을 PC/EC, PC/EL, PA/EC, PA/EL 로나눈다. Siddhartra Reddy 에의하면, MySQL 은마스터-슬레이브로구성된경우 PA/EL 가기본적이고경우에따라 PA/EC 로분류될수있다. 기본값은마스터 (master) 가트랜잭션을발생시키면슬레이브 (slave) 에비동기적으로데이터를복제한다 (asynchronous replication). ( 기존네트워크를자세하게분류해놓은자료는 Siddhartra Reddy 의발표자료를참조 ) 78
PACELC 이론에따른분류는다음과같다. PC/EC: choosing consistency all the time (regardless of network partitions) PC/EL: choosing consistency when partition, and choosing latency otherwise PA/EL: sacrificing consistency all the time (regardless of network partitions) PA/EC: choosing consistency when no partition, and choosing latency otherwise 맺는말 기술리서치분과에서는 Proof-of-Authority(PoA) 와 PBFT 를 CAP Theorem 을기준으로유형화하는논문 (PBFT vs proof-of-authority: applying the CAP theorem to permissioned blockchain: University of Southampton) 을리서치하였다. 리서치를통해해당논문이 CAP 이론을기반으로 PoA 와 PBFT 를유형화한것이실제와맞지않다는판단을하였다. 예를들어논문에서는 PBFT 를 CP (Consistency-Partition Tolerance) 시스템으로분류하였다. 그러나 PBFT 는전체노드가동의하지않아도네트워크의 safety 를위해서투표과정을거친다. ⅔ 이상의노드가동의하면자동적으로블록이확정된다. 따라서 PACELC 이론을바탕으로다시분류하고자하였으나, 리서치주제결이맞지않다고판단하여이를시도하지않았다. 추후연구를통해각종합의알고리즘을 PACELC 이론에바탕하여분류하는시도를해보고자한다. 해당문서는비영리목적으로누구나공정이용및공유하실수있으나이용시반드시출처를 표기해주시기바랍니다. 해당문서를비영리목적이아닌영리목적으로무분별하게이용할 경우저작권법제 37 조에의거하여법적인제재를받을수있습니다. 79
Acknowledgments 홍종화 ( 분과장 ) hjh93411@gmail.com 분산시스템에서의합의과저을리서치하면서블록체인에서합의알고리즘이라고명시하는 PoS, DPoS 와 BFT, PBFT 의명확한구분을할수있었고, 문서로정리하면서국내에부족하고분산되어있는자료들을한글화하여정리할수있어서의미깊은시간이었다. 전창석 jcs191072@gmail.com 마지막으로소회를밝히는시점이다가오니끝난다는안도감과아쉬움이동시에밀려온다. 약한달여동안수십개의블로그글과논문들을읽고정리하면서많은것을배울수있는시간이었지만, 더만족스러운결과물을만들수있지않았을까라는아쉬움도남는다. 혼자였다면절대이긴여정을끝내지못했을것이다. 진형, 찬현, 부영, 종화, 동식님의헌신적인노력과블록체인에대한열정에감사와찬사를아낌없이보내고싶다. 이부형 na4980@gmail.com 4 기기술리서치분과에서는 BFT Consensus 를주제로초기기술제안과발전과정에대한연구를진행했습니다. 바쁜일과중에도늦게까지기술토론과리뷰에힘써주신분과원들에게감사의인사를드립니다. 분과활동기간동안많이배울수있는시간이었습니다. 또한성공적인 Devstamp 행사운영과함께이더리움연구회가앞으로더번창하길바랍니다. 감사합니다. 이동식 dongsik.lee@gmail.com 이번기회에 BFT Consensus 에대한명확한이해를할수있는문서를만들고자하는리서치분과의목표로시작한이번과제는종화, 부형, 진형, 찬현, 창석님들의부단한노력과리서치의결과물입니다. 아마도새로블록체인에입문하시는분이나, 그동안어렴풋이알고있지만명확하게이해하지못했던 BGP, BFT 에대한제대로된이해를할수있는좋은기회가될것입니다. 수많은논문들을일일이리뷰하고토론하고정리해주신종화, 부형, 진형, 찬현, 창석님께감사드립니다. 80
박찬현 ryanpark045@gmail.com 블록체인기술의가장근본인비잔틴장애허용의기초들을리서치하고이해할수있는시간이되어서의미있었던것같습니다. 특히많은부분들에서거의당연시될정도로여겼던여러상수들과알고리즘들의분석과증명을정리할수있었기에추후연구자들에게도움이될수있는자료가될것같습니다. 이번 4 기기술리서치분과에서정리한자료를통해미래블록체인기술의발전과응용에도움이되기를기원하며 박진형 hophfg@yahoo.co.kr 이더리움연구회 4 기에서블록체인을진지하게연구하려는사람들과함께할수있어서매우기뻤습니다. 암호화폐시장은하락장이고블록체인산업은침체기에있지만, 이기술이지니는잠재력은무궁무진하다고믿습니다. 따라서블록체인의본질을지속적으로연구하는것이필요할것이라고봅니다. 4 기에서는블록체인의본질이라고할수있는분산네트워킹시스템에대해서진지하게연구하는시간을가졌습니다. BFT Consensus 에대한전반적인이해와 CAP PACLEC 이론까지밑바닥을리서치할수있었습니다. 이번분과에서하지못한연구주제는다음분과에계속하여연구함으로써블록체인에대한열정을이어나가고자합니다. 81
Reference [1] Bitcoin: Peer-To-Peer Electronic Cash System, Satoshi Nakamoto, (2008) https://bitcoin.org/bitcoin.pdf [2] Cypherpunk, Wikipedia https://en.wikipedia.org/wiki/cypherpunk [3] Bitcoin s Academic Pedigree, Arvind Narayanan and Jeremy Clark, (2017) https://queue.acm.org/detail.cfm?id=3136559 [4] 거인의어깨위에서미래를보다. < 비트코인에영향을준기술들과블록체인의현재와미래 >, 박재현, 블로그 http://wisefree.tistory.com/504 [5] 그림으로보는 IT 인프라구조, 김완섭, 책, JPub, (2015) [6] 코어이더리움 (Core Ethereum), 박재현, 박혜영, 오재훈, 책, JPub, (2018) [7] Ethereum White Paper, Github https://github.com/ethereum/wiki/wiki/white-paper [8] Impossibility of Distributed Consensus with One Faulty Process, Ficher, Lynch, Paterson, (1985) https://groups.csail.mit.edu/tds/papers/lynch/jacm85.pdf [9] A Brief Tour of FLP Impossibility, The Paper Trail, Henry Robinson,(2008) https://www.the-paper-trail.org/post/2008-08-13-a-brief-tour-of-flpimpossibility/ [10] Byzantine Generals Problem, Lamport, Shostak, Pease, (1982) https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf [11] Akkoyunlu, Eralp A., Kattamuri Ekanadham, and Richard V. Huber. "Some constraints and tradeoffs in the design of network communications." ACM SIGOPS Operating Systems Review. Vol. 9. No. 5. ACM, 1975. [12] Two Generals Problem Explained, Finematics, video (2018) https://www.youtube.com/watch?v=s8wbt0b8bwy 82
[13] POW 를통한비잔틴오류허용 ( 비잔틴장군문제 ) 해결과정, 블로그 http://goodjoon.tistory.com/256 [14] 슭의개발블로그 : Safety & Liveness - FLP Impossibility 으로보는블록체인, 블로그 https://blog.seulgi.kim/2018/05/safety-liveness-in-blockchain.html [15] Practical Byzantine Fault Tolerance, Castro, Liskov, 1999 http://pmg.csail.mit.edu/papers/osdi99.pdf [16] Practical Byzantine Fault Tolerance by Miguel Castro and Barbara Lisko, Matthhias Eberli, Anna Yudina https://www.slideshare.net/annayudi/pbft-7987140 [17] Practical Byzantine Fault Tolerance, Standford edu http://www.scs.stanford.edu/14au-cs244b/notes/pbft.txt [18] What are high and low water marks in bit streaming, Stackoverflow https://stackoverflow.com/questions/45489405/what-are-high-and-lowwater-marks-in-bit-streaming [19] Tendermint github, https://github.com/tendermint/tendermint [20] Tendermint: Byzantine Fault Tolerance in the Age of Blockchains, Ethan Buchman, (2016) https://atrium.lib.uoguelph.ca/xmlui/bitstream/handle/10214/9769/buchma n_ethan_201606_masc.pdf?sequence=7&isallowed=y [21] 코스모스사용자커뮤니티, 웹사이트, 전창석, 이기호 www.cosmostalk.io [22] Tendermint-starterkit, Github https://github.com/blockchainvn/tendermint-starterkit [23] L6: Byzantine Fault Tolerance, Distributed Systems Course https://www.youtube.com/watch?v=_e4wnotv3gw 83