블록체인허브 (blockchainhub.kr) - 블록체인 포털

SymSensus에 대하여

심버스 5 293 2018.10.18 16:24


1. 램버트의 비잔틴 장군문제는 참가자의 수가 배반자의 수보다 3배 이상되어야 배반을 극복할 수 있다고 하였다. 이러한 결과가 응용된 것이 BFT 계열이라고 부르는 PAXOS 알고리즘이다. 현재 PoW나 PoS 외 거래속도를 해결했다고 주장하는 대부분의 메인넷 합의과정은 주로 PAXOS 알고리즘의 변형으로 BFT 계열이라 불러야 한다.

a9c1c92f11e1bf8430e267625f7f4dab_1545361575_8031.JPG
Practical Byzantine Fault Tolerance 

2. 그러면 BFT 계열의 합의과정이 기존의 알고리즘을 어떻게 개선할 수 있는가를 살펴보면, 참가자 N개의 노드를 임의의 집단으로 나누는 방법과 동시투표방식을 개선하는 방법으로 구분해볼 수 있다.

3. 사회선택이론은 전략적 투표이론으로도 부르며 게임이론의 한 분야이다. 이 분야의 학자들은 대부분 수학자들이다. 후생경제학(Welfare Economics)에서 가장 유명한 정리가 Arrow 불가능성 정리( Arrow Impossibility Theorem) 이다. 그 내용은 다음과 같다.

<모든 개인의 선호를 만족시키는 하나의 사회후생함수는 존재하지 않는다>

이 불가능성의 정리를 두 명의 수학자 Gibbard와 Satterswaite가 독립적으로 연구하여 사회선택이론에서 가장 유명한 정리로 바꾸어 놓았다. 바로 Gibbard — Satterswaite 정리이며 다음과 같다.

<시민주권사회에서 3개 이상의 투표결과가 있을 때, Voting(투표방식)이 독재적이라면 어느 누구도 투표결과를 조작하여 이득을 얻을 수 없다>

<조작하여 이득을 얻을 수 없다>는 <not manipulable> 또는 <Strategy Proof>라고 표현한다. 투표이론에서 독재적이라는 것은 Veto(거부권)을 의미한다. 이러한 거부권은 Golden share 등에 응용되고 있고 사회선택이론의 중요한 연구분야이기도 하다.

4. Gibbard — Satterswaite 정리의 문제점은 투표결과가 대상의 순서(Ordinality)라서 합의과정에 그대로 적용하기 힘들다는 것이다. 그런데 Hylland라는 노르웨이의 수학자가 이 문제를 확률적 독재자 (Random Dictatorship)라는 방식으로 재해석하였다. 확률적 독재자라는 것은 Veto권을 가진 투표자를 확률적으로 선택하는 것을 말하며 이때 투표결과를 숫자(Cardinality)로 표현할 수 있다는 점이다. Hylland의 정리는 다음과 같다.

<시민주권사회에서 확률적인 독재자(비토권)의 투표방식은 어느 누구도 투표결과를 조작하여 이득을 얻을 수 없다>

5. 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.

 

추천&비추천 정책안내

, ,

신고
  • 카카오톡으로 보내기
  • 페이스북으로 보내기
  • 트위터로 보내기
  • 구글플러스로 보내기
  • 카카오스토리로 보내기
  • 네이버밴드로 보내기
  • 네이버로 보내기
  • 텀블러로 보내기
  • 핀터레스트로 보내기

Comments

[컬럼] ID 체인과 암호화폐 지갑의 미래 28

지갑은 오래 전부터 인류와 함께 해왔다. 주조된 동전을 저장할 때에는 쌈지나 복주머니를 쓰곤 했다. 그러다 플라스틱이 나온 후로는 빨간 돼지저금통이 인기를 끌었고 쉽게 꺼낼 수 없는 최소한의 보안이 돼 있었다. 아마도 그 돼지의 배를 갈라 동전을 곶감 빼듯 꺼내 쓰곤 했던 아련한 기억을 갖고 있을 것이다...
274 | 23 | 2019.05.10

Trusted Identity and Blockchain: Self-Sovereign Identity (Part 2) 4

What was once known to be the haven for geeks, the internet has now become the platform for everyone. With the advent of smartphones, it is safe to assume that we are now...
333 | 6 | 2019.03.28

Trusted Identity and Blockchain: Self-Sovereign Identity (Part 1) 8

Reminiscing the past years of blockchain’s history, we have seen various innovations stem from blockchain technology, trying to address alternatives to centralized contro...
667 | 8 | 2019.03.26

[컬럼] 분산ID와 이용자 자기주권시대 12

블록체인 기술이 세상의 변화를 이끌어 가고 있다. 이런 세상의 변화를 크게 정리하면 다음과 같은 5가지를 꼽을 수 있다.​• 블록체인 기술을 사용한 새로운 자금모집 방식이 조직의 거버넌스와 비즈니스 모델을 변화시킨다.• 블록체인에 쓰이는 신뢰성 있는 데이터를 이용해 P2P 거래가 활성화됨으로써 거래를 지...
1,030 | 13 | 2019.02.27

통인 익스프레스 매거진 'Home&Moving' 8

통인 익스프레스에서 발간하는 '홈앤무빙' 2월호에'블록체인을 통한 스마트 홈케어' 기고문이 실렸습니다. (p90-92)(캡쳐화면은 화질이 선명하지 않네요. 링크 눌러서 편하게 읽어보실 수 있습니다 :)
358 | 10 | 2019.02.11

SymVerse at World Blockchain Summit MARVELS 1

2018. 12.12 서울 신라호텔에서 열린 '월드 블록체인 써밋 마블스'에 심버스 최수혁 박사가 스피커로 참여했습니다. 코리아씨이오서밋이 주최하고 매일경제TV, 한국블록체인산업진흥협회, 한국블록체인 스타트업협회, 국회 4차산업혁명포럼이 공동주관하며 서울시와 TV조선, 오픈블록체인산업협회, 한국블록체인콘...
309 | 3 | 2019.01.18

SymVerse의 새로운 진화 (1) 6

SymVerse는 “공생” 그 자체입니다.블록체인 생태계의 주체는 블록체인을 만드는 낼 수 있는 노드들인 공급자와 블록체인을 사용하여 서비스를 만들어내는 애플리케이션 사업자와 일반지갑 소유자인 소비자입니다.블록체인을 만들어낼 수 있는 공급자들과 이를 사용하는 소비자들은 P2P네트워크를 통하여 서로연결되어...
457 | 7 | 2019.01.08

Economic Foundation of SymVerse Innovations 7

<Old Blockchain Regime>Economic Components of TokenEconomy-소비자(Consumers): Wallet users and dApps Usage fee payment-생산자(Producers): Full nodes using PoS (Future Eth...
329 | 5 | 2018.12.21

[심버스 어드바이저] 경청의 멘토- 대니 휴즈 1

며칠 사이- 경청에 대한 포스팅을 올렸었지요?오늘 아름다운 한 분의 예를 올려봅니다.Danny Hugheshttp://www.dannyhughes.me/여긴 대니 휴즈의 홈페이지네요. 그의 경력을 보면 독특합니다.축구선수였다가 사회사업가가 되었고 책의 저술가가 되었으며..... 청취자! 이건 뭘까요?그는...
650 | 3 | 2018.12.20

[심버스 어드바이저] 등 뒤의 웅혼한 바람- 신근영 회장님 6

마을에는 어르신이 계시듯 블록체인계에도 그런 존재가 필요하다고 봅니다.블록체인 세계는 전반적으로 매우 젊은 세대가 주축이 되어 있죠. 그러기에 젊은 피가 끓고는 있으나 완숙한 경륜은 모자란 경우가 많은 것은 당연한 일인지도 모릅니다.경륜은 바른 사상을 제시하며 사상은 우리 프론티어들에게 방향의 준거를 주...
793 | 5 | 2018.11.19

[심버스 어드바이저] 조너선 하이트(Jonathan Haidt) 6

심버스에는 어드바이저가 계십니다.어드바이저를 잘 살펴보는게 왜 중요할까요?어드바이저의 정신과 사상의 총합, 그 중심점에 그 회사가 있을 것이기 때문이지요.첫번째 소개할 분이 이 분입니다.조너선 하이트(Jonathan Haidt)는 미국의 심리학자며 뉴욕대학교 교수입니다.그의 저서 '바른 마음' 등은 우리...
269 | 4 | 2018.11.14

SymVerse Mechanism Design 10

암호화폐의 디자인과 실행작업은 하나의 생태계를 만들어내는 ‘구조설계(Mechanism Design)’입니다.(Mechanism Design: 게임이론, 응용경제학의 한 분야. 2007년 Hurwicz, Maskin, Myerson이 노벨 경제학상을 수상함. https://en.wikipedia.org/w...
648 | 12 | 2018.10.23

탈중앙화에 대한 정의와 측정방법 11

1. 기존의정의이더리움의 창시자로 널리 알려진 비탈릭 부테린(Vitalik Buterin)이 쓴 <The Meaning of Decentralization > 에서 부테린은 다음과 같이 탈중앙화를 구분하고 있다.- 구조적 탈중앙화- 정치적 탈중앙화- 논리적 탈중앙화이 중 구조적 탈중앙화는 네트...
2,659 | 12 | 2018.10.23

SymVerse White paper 10

심버스 백서는 현재 한글, 영문, 중문, 일문 버전으로 나와있습니다.차후 외국어 버전이 추가되는 대로 업데이트 하겠습니다.감사합니다.
1,287 | 8 | 2018.10.22

'메인넷 톺아보기' 행사 중 SymVerse 8

10월 19일 고려대학교에서 주회한 '메인넷 톺아보기' 행사 중 심버스 발표 부분을 정리했습니다.흔히 속도와 용량을 가장 따지는데 그런 것은 길어야 3년 안에 모두 해결될 문제라고 봅니다.정말로 근본적인 이슈는-아마존과 같은 인터넷 생태계에 대해 블록체인 생태계가 과연 더 나은 대안이 될 수 있는 것일까...
542 | 6 | 2018.10.22

SymSensus에 대하여 5

1. 램버트의 비잔틴 장군문제는 참가자의 수가 배반자의 수보다 3배 이상되어야 배반을 극복할 수 있다고 하였다. 이러한 결과가 응용된 것이 BFT 계열이라고 부르는 PAXOS 알고리즘이다. 현재 PoW나 PoS 외 거래속도를 해결했다고 주장하는 대부분의 메인넷 합의과정은 주로 PAXOS 알고리즘의 변형으...
294 | 7 | 2018.10.18

SymVerse 특징 4

SymVerse는 블록체인을 통하여 더 나은 세상을 구현하기 위해새로운 접근방법과 혁신적인 설계철학을 도입하였습니다.게임이론에 기반한 사회 경제적 융합기존의 블록체인 플랫폼은 블록생산과 거래확정에지분증명이나 작업증명과 같은 방식을 도입하고 있습니다.그러나 이는 취약한 면을 내포하고 있으며 우리는 이 문제...
527 | 7 | 2018.10.18

SymVerse 의미와 비젼 8

심버스의 로고는 한자 마음'心'의 가장 오래된 전서의 형태로,서로 다른 두 개의 블록이 하나로 합쳐지는 상생을 표현합니다.가운데 'S'는 블록체인에 심어진 심버스 혁신(SymVerse Innovation)을 의미합니다.SymVerse는‘함께(together)’를 의미하는 접두어인Sym과‘상호작용(inte...
760 | 8 | 2018.10.18


추천 주간월간전체

최근글

최근댓글