*오늘은 문과생인 저보다 개발자이며 대표인 최수혁님의 글입니다.
다소 난해해보이시겠지만...(저에게도 무쟈게 어려움ㅠㅠ;) 이런 글을 이해할 수 있는 분도 계실거라 믿고 과감히 올려봅니다. 왜냐하면-
이 부분은 메인넷 설계에 있어서 중요한 부분이기 때문이지요.
- 램버트의 비잔틴 장군문제는 참가자의 수가 배반자의 수보다 3배 이상되어야 배반을 극복할 수 있다고 하였다.
이러한 결과가 응용된 것이 BFT 계열이라고 부르는 PAXOS 알고리즘이다.
현재 PoW나 PoS 외 거래속도를 해결했다고 주장하는 대부분의 메인넷 합의과정은 주로 PAXOS 알고리즘의 변형으로 BFT 계열이라 불러야 한다.
Practical Byzantine Fault Tolerance
그러면 BFT 계열의 합의과정이 기존의 알고리즘을 어떻게 개선할 수 있는가를 살펴보면, 참가자 N개의 노드를 임의의 집단으로 나누는 방법과 동시투표방식을 개선하는 방법으로 구분해볼 수 있다.
사회선택이론은 전략적 투표이론으로도 부르며 게임이론의 한 분야이다. 이 분야의 학자들은 대부분 수학자들이다. 후생경제학(Welfare Economics)에서 가장 유명한 정리가 Arrow 불가능성 정리( Arrow Impossibility Theorem) 이며 그 내용은 다음과 같다.
<모든 개인의 선호를 만족시키는 하나의 사회후생함수는 존재하지 않는다>
이 불가능성의 정리를 두 명의 수학자 Gibbard와 Satterswaite가 독립적으로 연구하여 사회선택이론에서 가장 유명한 정리로 바꾸어 놓았다. 바로 Gibbard — Satterswaite 정리이며 다음과 같다.
<시민주권사회에서 3개 이상의 투표결과가 있을 때, Voting(투표방식)이 독재적이라면 어느 누구도 투표결과를 조작하여 이득을 얻을 수 없다>
<조작하여 이득을 얻을 수 없다>는 (not manipulable)또는 (Strategy Proof)라고 표현한다.
투표이론에서 독재적이라는 것은 Veto(거부권)을 의미한다.
이러한 거부권은 Golden share 등에 응용되고 있고 사회선택이론의 중요한 연구분야이기도 하다.
- Gibbard — Satterswaite 정리의 문제점은 투표결과가 대상의 순서(Ordinality)라서 합의과정에 그대로 적용하기 힘들다는 것이다.
그런데 Hylland라는 노르웨이의 수학자가 이 문제를 확률적 독재자 (Random Dictatorship)라는 방식으로 재해석하였다. 확률적 독재자라는 것은 Veto권을 가진 투표자를 확률적으로 선택하는 것을 말하며 이때 투표결과를 숫자(Cardinality)로 표현할 수 있다는 점이다.
Hylland의 정리는 다음과 같다.
<시민주권사회에서 확률적인 독재자(비토권)의 투표방식은 어느 누구도 투표결과를 조작하여 이득을 얻을 수 없다>
- Hylland의 결과를 BFT에 적용하면 다음과 같은 정리(SymSensus Theorem)를 도출할 수 있다.
<Veto권이 존재하는 BFT 합의과정에서 Primary 노드(확률적 독재자)가 블록을 생성할 때 투표참가자들은 합의과정을 조작하여 이득을 얻을 수 없다>
이 정리를 이용하면 SymVerse 합의알고리즘은 합의과정에 걸리는 시간을 기존의 알고리즘의 50% 이상 줄일 수 있다. 그 방법은 합의 알고리즘에 거부권그룹을 만들어 다음과 같이 투표를 진행하면 된다.
합의과정에 참가하는 집단을 두 개로 분류하고 A집단은 정수[N/3] +1 개의 노드로 구성된다.
A집단은 투표권만 있으며 모두 동일한 투표결과를 보여준다.
나머지 노드들은 B집단으로 부르고 블록을 생성하는 Primary 노드가 될 수 있으며 투표권을 갖게 만든다.
두 집단이 동시에 합의를 시작하면 A집단은 과반수만 넘으면 투표권의 결과가 결정되고, B집단의 절반이 투표를 진행하면 자동적으로 투표결과가 나타나기 때문이다.
기존의 BFT에서 합의정족수가 정수[2N/3] +1 되어야 했지만 B그룹의 정족수가 정수[N/3]이 되면 전체적인 합의가 이루어진다. A그룹은 과반수만 넘으면 전체가 합의하기 때문에 A그룹의 합의 종료시간이 B그룹보다 항상 짧기 때문에 합의는 신속하게 이루어진다.
[참고문헌]
● Lambert, L., “Generalized Consensus and Paxos” Microsoft Research Technical Report MSR-TR-2005–33 , 15 March 2005.
● Lambert, L., “Fast Paxos”, Distributed Computing 19, 2 , October 2006. pp.79–103.
● Lambert, L, Danny Dolev, Marshall Pease, and Robert Shostak “The Byzantine Generals” in Concurrency Control and Reliability in Distributed Systems, Bharat K. Bhargava, editor, Van Nostrand Reinhold (1987) pp. 348–369.
● Moulin, H. The Strategy of Social Choice. Series: Advanced textbooks in economics, 18. North-Holland: Amsterdam, The Netherlands. 1983.
● Peleg, B. Game Theoretic Analysis of Voting in Committees, Cambridge University Press, Cambridge, 1984.
● Hylland, A. “Strategy proofness of voting procedures with lotteries as outcomes and infinite sets of strategies,” mimeo. 1980
● Sen, A. “The Gibbard random dictatorship theorem: a generalization and a new proof,” SERIEs 2, 515–527, 2011.
"도움이 되셨쥬?"
