확률적 지분증명

확률적위임지분증명(Stochastic dPoS)이란 합의에 참여할 커미티를 랜덤하게 선출하되 코인 보유량 등에 비례하여 선출될 확률이 높아지는 합의 알고리즘이다. 이것은 알고랜드의 무허가형 순수지분증명방식과 유사한 알고리즘으로서 '실사용 암호화폐'를 목표로 하고 있는 로커스체인이 채택한 방식으로 알려져 있다. 합의에 참여할 수 있는 노드를 미리 정하는 이오스의 위임지분증명과 달리 로커스체인의 확률적위임지분증명은 코인 보유량, 최근 투표 참여 횟수, 네트워크 참여도 등에 따라 매 라운드마다 새로운 커미티를 랜덤하게 선출하기 때문에 로커스체인은 이것을 통해 높은 수준의 탈중앙화를 이룰 수 있다고 주장한다. 합의에 참여할 노드(프로포저, 밸리데이터)를 특정하거나 미리 예측할 수 없으므로 악의적 공격에 의한 조작이 어려워져 합의결과의 공정성과 네트워크의 안정성(security)이 확보되는 장점이 있다.

개요

로커스체인은 다이내믹 샤딩을 적용하여 네트워크를 샤드 단위로 쪼개고 각 샤드에서 독립적으로 BFT합의를 수행한다. 이때 합의에 참여할 커미티를 선출하는 알고리즘으로 채택한 방식이 확률적위임지분증명이다. 각 샤드에서 라운드 합의를 위해 투표인단에 포함되는 노드를 랜덤으로 선출할 때, 지분량(stake)이 높은 노드는 선출될 확률이 높아진다.

활용

확률적위임지분증명의 구체적인 활용은 로커스체인이 홈페이지에 공개한 자료에 다음과 같이 기술되어 있다.

지분량 계산

로커스체인은 코인 보유량 뿐만이 아니라 최근 투표 참여 횟수, 네트워크 참여도(온라인 시간) 등에 기반해 지분량을 측정한다. 지분량이 높은 노드가 시스템 유지에 높은 기여를 하는 구조인데 로커스체인의 어카운트는 자기 지분량을 다른 어카운트에 위탁(delegate)할 수 있다. 이를 통해, 네트워크에 항상 접속하지 않는 어카운트도 자신의 지분량을 유효하게 활용할 수 있다. 노드의 지분량은 해당 노드의 대표 어카운트가 가진 자기 지분량과 다른 어카운트로부터 위탁받은 지분량의 합계가 된다.

선출 방식

합의에 참여하는 노드는 두 그룹으로 나뉜다. 첫 번째 그룹은 라운드에 발생한 트랜잭션을 검증하는 역할을 하는 노드그룹인 "제안인단 노드 커미티(프로포저)"이다. 두번째 그룹은 제안인단 노드가 제출한 복수의 트랜잭션 상태를 검증하여 합의 투표를 실시하는 "투표인단 노드 커미티(밸리데이터)"이다. 두 커미티 모두 각 라운드마다 새로 선출된다. 커미티의 선출에는 공개된 과거의 원장 상태와 노드의 공개된 정보로부터 값을 도출하는, 결과가 재현 가능한 슈도-랜덤 함수를 사용한다. 예를 들어 VRF함수(Verifiable Random Function)등이 사용 가능하다. 새 라운드가 시작한 직후, 각 노드는 자기 자신의 정보를 사용하여 랜덤 함수를 계산, 자기 자신이 커미티에 선출되었는지를 확인한다. 선출된 노드는 자기 자신이 어떤 커미티에 선출되었는지를, 계산된 랜덤값과 함께 브로드캐스트한다. 다른 노드는 선출된 노드의 정보를 수신하여 랜덤값을 로컬에서 계산 및 검증, 집계하여 해당 라운드의 커미티를 파악한다. 각 라운드 및 샤드마다 선출하고자 하는 목표 커미티 노드수가 존재하지만, 실제 선출은 각 노드의 독립된 랜덤 계산으로 실시되기 때문에 실제로 선출되는 숫자는 매번 달라진다. 실제 선출된 노드의 숫자를 집계에 의해 알 수 있고, 또한 높은 확률로 오차범위 내에서 충분한 수의 노드가 선출되게 된다. 선출된 커미티 노드가 실제 합의에 참여하여 검증이 성립되면, 활동 내용에 따라 인센티브를 지급받는다.

투표 방식

• 상태 제안 단계: 라운드가 종료되고 일정 시간이 지난 후 제안인단 노드 커미티에 선출된 모든 노드는 라운드 내에 발생한 정보를 집계하여 라운드 상태 해쉬를 계산한다. 라운드 상태 해쉬는 수신된 트랜잭션을 머클-패트리시아 트라이(MPT / Merkle-Patricia Trie)상에 배치함으로써 계산된다. MPT는 radix trie의 일종으로, 데이터의 추가 순서와 관계 없이 항상 같은 트리가 구성되며, 포함되는 모든 트리 노드가 대표되는 해쉬값을 갖는다는 성질이 있다. 제안 노드는 계산된 라운드 상태값(MPT의 루트 해쉬값)과 포함되는 트랜잭션 수를 사용하여 라운드 제안 패킷을 구성, 서명하여 브로드캐스트한다.

• 상태 선택 투표 단계: 라운드 상태 제안 단계가 수행되면 샤드 내에는 라운드 상태 제안 커미티 만큼의 상태 제안 패킷이 발생한다. 라운드 상태 투표는 이 제안 상태 중 하나를 선택하여 고르는 단계이다. 투표 노드가 제안을 선택하면, 선택된 제안을 사용하여 선택 투표 패킷을 구성, 서명하여 브로드캐스트한다.

• 상태 확정 투표 단계: 투표인단 커미티는 각 투표 노드가 발행한 투표 패킷을 수신하여, 각 제안에 대한 투표수를 집계한다. 만약 어떤 한 상태 해쉬값이 투표 노드의 2/3+1이상의 투표수를 모은 경우, 그 상태 해쉬값은 해당 라운드의 최종 상태로서 확정되었다 볼 수 있다. 각 커미티 노드는 투표 패킷을 수신하여, 한 상태 해쉬값이 전체 투표노드 2/3+1이상의 투표수를 수신한 순간 해당 제안을 확정으로 판단, 이에 대해 다시 서명을 실시하여 확정 투표 패킷을 구성, 공유한다. 이 확정된 투표 정보에는 참여한 여러 투표 노드의 서명이 슈노르(Schnorr) 서명 등의 방법으로 복수 부여되게 된다. 샤드 내의 모든 노드는 충분한 숫자의 커미티 노드가 서명한 확정된 투표 정보를 수신하면, 해당 제안이 확정된것으로 보고 합의를 완결짓는다.

참고자료

• <로커스체인 합의알고리즘의 기본 아이디어>, 《Locus Insight》, 2019-02-01
• <각 트랜잭션의 정당성과 로커스체인 합의알고리즘의 관계>, 《Locus Insight》, 2019-03-02

같이 보기

• 로커스체인
• 알고랜드
• 위임지분증명