[백서 번역 프로젝트] Part.2 리플 합의 알고리즘 (2) 본문

in #ripple6 years ago (edited)

안녕하세요, 상당히 오랜만에 돌아왔습니다.  

사실 시험이 끝난것은 한 일주일 전인데, 그 외에 여러가지 할 일도 있었고, 이 프로젝트에 대해서도 어떻게 진행을 해야할지 고민을 좀 하다보니 오늘에서야 글을 쓰게 되었습니다.  일단 리플에 대한 것은 이번 글과 다음 글(리플에 대한 논쟁과 견해)로 마무리 지으려고 합니다.  원래는 최소한 한달에 백서 하나씩은 번역을 하려고 했는데, 첫번째 주자로 리플을 선택했고, 그에 대해 너무 자세히 알아보려고 하다보니 벌써 세달이나 지나버렸네요. 

이부분에 대해 지원해주신 @coinkorea 님께는 죄송하게 생각하고, 리플에 대해 글을 마무리 지은 후에는 좀 더 고민하고 제대로 준비해서 더 나은, 양질의 글을 작성할 수 있도록 노력해보겠습니다. 

그럼, 이번 글도 시작하도록 하겠습니다.

1. 서론


여느 암호화폐 프로젝트가 그러하듯, 리플 또한 기존의 중앙집중된 시스템(SWIFT, 스위프트) 를 대체하기 위해 제안되었습니다. 그리고 리플은 여기서 더 나아가 타 분산화된 지불 시스템이 가지고 있는 기술적인 문제에도 집중합니다. 리플 프로토콜에서는 기술적인 문제들을 세가지 카테고리로 분류하였습니다.  

 정확성correctness, 동의agreement, 활용성utility 

정확성은 분산화된 시스템이 올바른 거래와 위조된 거래의 차이를 식별할 수 있어야 한다는 의미입니다.  가장 기본적이고, 중요한 부분입니다. 100$의 잔고에서 120$를 송금하려고 시도하는 것은 정확성을 어기는 행위가 됩니다. 

동의는 하나의 통일된 장부를 갖는 것을 말합니다.  100$의 잔고를 가지고 있다고 할 때, 60$ 의 거래와 70$의 거래는 개별적으로는 문제가 되지 않습니다. 하지만, 두 개의 거래를 동시에 처리하는 것은 문제가 됩니다. 리플에서 트랜잭션은 UNL이라는 노드 집합체'들'에 의해 각각 이루어집니다.   이것이 가능한 것은 모든 장부가 동일하기 때문입니다. 만약 그렇지 않다면, 이중지불 문제가 발생하겠지요. 

활용성은 위의 두 문제들보다는 사소한 문제들을 말합니다. 활용성에 해당하는 문제로는 [시스템 지연 시간] 문제를 들 수 있습니다. 이것은 비트코인에서 가장 문제가 되는 부분이자, 리플 프로토콜의 장점이 되는 부분입니다. 아무리 이중지불을 방지하고, 거래가 올바르다고 해도, 트랜잭션 처리가 너무 오래걸린다면 지불 수단으로서의 가치를 얻을 없을 것입니다. 


2. 정의, 규격화, 그리고 사전 연구


2.1 리플 프로토콜의 요소


뒤에서 설명할 부분들을 이해하기 위해 용어들을 정의하고 넘어가겠습니다.

서버(server) : 서버는 합의 프로세스에 참여하는, 리플 서버 소프트웨어(rippled)를 운영하는 독립체를 말합니다. 앞의 게시글에서도 설명하였지만, 개인 또한 적절한 사양을 갖추면 서버가 될 수 있습니다. 뒤에서 설명할때 's'로 표시합니다. 

장부(ledger)  :  장부는 각 유저의 계좌에 있는 화폐 액수의 기록이고, 네트워크의 “기본적인 신뢰” 를 나타냅니다. 장부는 합의 프로세스를 성공적으로 통과한 트랜잭션과 함께 반복해서 업데이트 됩니다.  특히, 리플의 장부는 비트코인의 것과 완전히 다릅니다. 비트코인의 장부는 트랜잭션이 담기는 블록을 지속적으로 연결하는 방식으로 구성되지만, 리플의 장부는 트랜잭션을 지속적으로 추가하는 방식으로 그 자체가 업데이트 됩니다. 즉, 리플의 장부에는 블록이 없고, 장부 자체가 10초마다 업데이트됩니다.

최종 장부(Last-Closed Ledger) : 마지막으로 닫힌 장부는 합의 프로세스에 의해 비준된 가장 최근의 장부이므로, 네트워크의 현재 상태를 나타냅니다.  참고로 현재 리플의 장부는  [ledger #40140145]  입니다.

열린 장부(Open Ledger) : 사용자들의 트랜잭션은 열린 장부에 올라가고, 합의 프로세스를 거쳐 최종장부에 남거나, 탈락하게 됩니다. 처음 열린 장부는 10초가 지난 후, 닫힌 장부가 됩니다. 

고유 노드 리스트(Unique Node LIst, UNL) : 각 서버,  s는 개별적인 노드 집합을 운영합니다. 서버 s는 이 집합의 결정에 따라 트랜잭션이 옳은지, 그른지를 판단합니다. (그 결정은 합의 프로세스에 의해 판단됩니다.) 이론적으로 각 서버는 그 자체도 UNL이 될 수 있지만, 그렇게 된다면 리플의 구조상 이중 지불 문제가 발생할 우려가 생깁니다. 현재, 고유 노드 리스트를 만드는데 포함할 수 있는 서버는 리플 사에서 제공하는 몇몇개에 불과합니다. 이것이 리플 블록체인이 누구든 노드가 될 수 있는 퍼블릭 블록체인임에도 불구하고 사실상 프라이빗 블록체인이라고 비판받는 이유입니다.

2.2 공식화


리플에서는  네트워크 내에서 정직하게 행동하고 에러가 없는 노드를 무결점(non-faulty) 노드라고 부릅니다. 만약 정직할지라도, 잘못된 데이터나 구현 오류 등의 이유로 에러를 경험했거나, 처음부터 악의를 갖고 있는 노드는 장애노드라고 부릅니다. 리플 프로토콜은 다음 세가지 공리에 따라 합의를 정의합니다.

C1 : 모든 무결점 노드는 각각 한정된 시간 내에 결정한다.

C2: 모든 무결점 노드들은 같은 결과 값에 도달한다. 

C3: 무결점 노드는 0과 1 모두 선택 가능하다. 


2.3 현존하는 합의 알고리즘


이 파트에서는 현존하는 합의 알고리즘을 다룹니다. 하지만, 별로 중요하지 않아 생략했으니, 궁금하신 분들은 백서 원문을 참고해주시면 되겠습니다. 


2.4 합의 목표


이 백서에서의 목표는 리플 프로토콜에 의해 사용되는 합의 알고리즘이 각 장부 종료 시점에서 합의를 이루는 것입니다. 이 합의는 비잔틴 장애에 직면한 상황에서도 알려진 확률로만 이루어져야 합니다. (합의 공식에 따라)

네트워크의 각 노드는 UNL에서 제안된 트랜잭션들에게만 투표하고, 각 노드들은 아마 각기 UNL을 다르게 설정했을 것이기 때문에  우리는 UNL의 일원이 누군지에 상관없이 모든 노드들 사이에서 오직 한가지 합의만이 도출될 수 있다는 것을 보일 것입니다. 그리고 이것은 네트워크 내에서  '포크'를 방지하는 것이라고 할 수 있습니다. 

위의 내용은 합의 백서에 써 있는 내용입니다. (앞서 설명한대로 실제와는 다릅니다.)  참고로 리플에서는 포크가 불가능한데, 리플 합의 알고리즘에 따라 오직 한가지 장부만이 도출될 수 있으므로 포크 - 두가지 장부가 공존하는 것 - 는 불가능하게 됩니다. 

추가로, 리플 프로토콜은 비잔틴 장애를 20%까지 허용할 수 있습니다. 즉, 전체 노드의 20%가 배신하더라도 리플 프로토콜은 정상적으로 돌아갑니다. 


3. 리플 합의 알고리즘


리플 합의 알고리즘은 네트워크의 정확성과 동의를 유지하기 위해 매초마다 모든 노드에 대해 적용됩니다. 한번 합의가 이루어지면, 현재의 장부는 "닫힌" 장부가 되고, 최종 장부로 간주됩니다. 합의 알고리즘이 성공적으로 적용된다면, 네트워크내에서는 어떠한 포크도 일어나지 않고, 네트워크 내의 모든 노드에 의해 유지되는 최종 장부는 동일합니다 .

3.1 정의


리플 합의 알고리즘은 라운드 제로 진행됩니다.

  1. 라운드 시작 전, 각 서버는 아직 장부에 적히지 않은 모든 "유효한 트랜잭션"을 취합니다. (이 "유효한 트랜잭션"은 각 서버의 최종 사용자의 트랜잭션이나 이전 합의 프로세스에서 넘어온 트랜잭션을 말합니다. )
  2. 각 서버는 전체 서버의 후보세트를 통합하고, 모든 트랜잭션에 대해 투표합니다. (비트코인의 경우에는 댠순히 블록이 쌓이는 것으로 위조여부를 판단하는데 비해, 리플은 모든 서버가 직접 위조 여부를 판단합니다. 이 부분은 다음 글에서 구체적으로 다뤄보겠습니다.)
  3. 최소 기준 이상의 찬성 투표를 받은 트랜잭션은 다음 라운드로 옮겨집니다. 옮겨지지 못한 트랜잭션은 버려지거나, 다음 장부 합의 프로세스에 참여될 수 있습니다. 처음에는 절반의 동의가 필요합니다. 
  4. 50% > 60% > 70% > 80% 순으로 진행되어, 마지막 80%의 동의를 얻으면 최종 장부에 오를 수 있습니다.


3.2 정확성


비잔틴 장애의 최대치(20%)를 감안할 때, 정확성을 달성하기 위해서는 80%의 동의가 필요합니다. 간단히 말해, 80%의 동의를 얻은 이상 나머지 20%가 동의를 하든, 악의적으로 동의를 하지 않던 상관 없다는 것입니다. 어차피 필요한건 80% 이기 때문이죠. 

//

여기서 문제는 이 '80%' 가 모두 정직한 노드이냐 하는 것입니다. 리플 프로토콜 백서에서는 이 80%가 모두 정직한 노드라고 가정했지만, 아닐 수도 있습니다. 예를 들어, 위에서 설명한 100$의 잔고의 경우를 보면 두 개중 하나의 트랜잭션은 정당합니다. 정당한 트랜잭션을 A, 이중지불을 위한 악의적인 트랜잭션을 B라고 할 때, 해킹 집단은 A를 찬성합니다. 즉, 해킹 집단은 위에서 설명한 80% 안에 들어갈 수 있다는 것이지요. 

이러한 이유로 리플 프로토콜 합의 알고리즘의 오류에 대해 문제가 제기 되었고, 이를 개선하기 위해 코발트(cobalt) 라는 새로운 알고리즘이 제안되었습니다. (언제 새로운 알고리즘이 도입될지는 정해지지 않았고, 현재 리플 프로토콜은 백서에서 설명된 합의 알고리즘을 사용하고 있습니다.)

//

3.2 의 내용은 정확성을 수식으로서 설명하는 내용입니다만, 이해하기도 쉽지 않고, 이해하더라도 그 내용이 사실이 아니라고 판정되었기 때문에 설명하지 않는것이 낫다고 판단하여 생략합니다. 원본 백서에는 나와있습니다.


3.3 동의


동의 요건을 충족시키기 위해서는 모든 정상 노드가 그들의 UNL에 상관없이 동일한 트랜잭션 집합에 대해 합의를 이룬다는 것을 증명해야 합니다. 

위에서 설명한대로 각 서버는 (이론적으로) 개별적인 UNL을 갖습니다. 따라서 합의 내용이 다를 수 있겠죠. 그렇다 하더라도 최소한의 연결성은 갖고 있어야 장부가 두개가 되는 일이 일어나지 않습니다. 

만약 A서버와 B서버의 교집합이 20% 미만일 경우, 각 서버에서 다른 합의가 가능해집니다. 구체적으로 설명해서, 각 서버는 어떤 트랜잭션에 대해 [찬성] 라는 결정과 [반대] 라는 결정 두가지가 가능합니다. 만약 A 서버의 UNL에서 80%가 찬성을 한다는 것은 나머지 20%는 반대를 말한다는 것과 같습니다.  반대로, B서버의 UNL에서 80%가 반대를 한다는 것은 나머지 20%가 찬성한다는 것과 같죠. 

이 경우, 서버의 교집합이 20%가 되지 않는다면, 각각의 서버에서 다른 결정을 할 수 있게 됩니다.  

 위 이미지에서 선에 의해 연결된 노드(점) 은 UNL을 이루는 하나의 서버를 나타냅니다. 즉, 첫번째(위) 그림에서 이 노드를 비롯한 왼쪽의 모든 노드가 [찬성] 을 외치더라도 오른쪽의 '연결된 노드' 를 제외한 다른 모든 노드가 [반대] 를 외친다면, 80%를 충족하므로 양쪽이 다른 결론을 내게 됩니다. 이는 곧 두 개의 장부가 생길 수 있다는 것을 의미하고, 포크가 가능하다는 것을 말하게 됩니다. 따라서 두 노드의 교집합은 20%를 넘어야 합니다.

한편, 이상적인 합의 알고리즘의 실현 형태에서 각 서버들의 UNL은 거미줄 처럼 엉켜있게 됩니다. (실제로도  서버의 개수는 150개에 달하기 때문에 위의 내용처럼 단순하게 판단할 수는 없습니다.) 따라서 포크는 교집합이 20%를 넘지 않더라도 불가능할 가능성이 큽니다.  

한 가지 흥미로운 점은, '동의(agreement)' 요건을 충족하는데에 교차하는 노드의 본질은 상관이 없다는 것입니다. 위에서 설명한 예를 다시보면, 교차하는 노드가 [찬성] 을 선택하거나 [반대] 를 선택하는지에 상관없이 중요한 것은 교차하는 크기라는 점을 알 수 있습니다. 


3.4 활용성


활용성에서 다루는 문제는 [시간 지연] 입니다. 

3.4.1 수렴

수렴(convergence)은 리플 합의 알고리즘이 장부와 함께 합의에 도달하고, 이 장부가 최종 장부가 되는 시점을 말합니다. 모든 트랜잭션이 위조되지 않았고, 모든 서버가 같은 장부를 도출해낸다면, 이제 남은 것은 그것이 시간내에 이루어지느냐 하는 문제입니다. 

합의가 시간내에 이루어지는 데에 방해요소는 노드 사이의 통신 지연시간입니다. 이것을 제한하기 위해 노드의 응답시간은 모니터링되고, 정해진 기준을 초과하는 노드는 전체 UNL에서 삭제됩니다. 

3.4.2 휴리스틱과 절차

휴리스틱이란 어림짐작을 말합니다. 어떤 상황에 대해 객관적으로 판단하기 보다는 즉흥적으로 판단하는 것이죠. 여기서의 휴리스틱이란 다음을 말합니다.

- (모든 트랜잭션에 대해 "아니오" 라고 투표하는 노드) / (합의 라운드에서 탈락한 트랜잭션을 지속적으로 제안하는 노드) 를 네트워크에서 제거하는 것. 

이러한 행동을 하는 노드는 이리저리 재보지 않아도 악의적이라고 판단할 수 있으므로(어림짐작으로) 네트워크에서 제거하는 것입니다. 

이 같은 휴리스틱 외에 선별된 UNL을 기본 세트로 제공한다던지, 모든 노드가 합의 라운드 시작 전에 의무적으로 2초간 창을 띄워서 후보 트랜잭션 세트를 제안할 수 있도록 한다든지 하는 등의 정해진 절차가 있습니다.


4. 시뮬레이션 코드


네트워크 내 노드의 숫자, 노드 중 악의적인 노드의 숫자 등을 설정해두고 리플 합의 알고리즘을 실현해볼 수 있습니다. 링크 - 시뮬레이터 깃허브


그동안 너무 어렵게 내용을 설명해 왔다는 생각이 들어서 좀 쉽게 풀어보려고 했는데 잘 되었을런지 모르겠네요 ㅎ 다음 글에서는 리플에 대한 논쟁과 그에 대한 제 견해를 소개하고 [리플 합의 알고리즘] 을 마무리하도록 하겠습니다. 

읽어주셔서 감사하고 궁금한 점은 댓글로 남겨주세요!



Sort:  

You got a 7.67% upvote from @upmewhale courtesy of @whitecat97!

Earn 100% earning payout by delegating SP to @upmewhale. Visit http://www.upmewhale.com for details!

Congratulations @whitecat97! You have completed the following achievement on Steemit and have been rewarded with new badge(s) :

Award for the number of upvotes received

Click on the badge to view your Board of Honor.
If you no longer want to receive notifications, reply to this comment with the word STOP

To support your work, I also upvoted your post!

Do not miss the last post from @steemitboard:
SteemitBoard World Cup Contest - The results, the winners and the prizes

Do you like SteemitBoard's project? Then Vote for its witness and get one more award!