Tenderand: Randomized Leader Election in Tendermint
텐더민트 내의 검증인 집단은 가중 라운드 로빈 방식으로 교차하며 리더, 즉 블록 제안자를 선출한다. 검증인은 위임된 지분에 비례하여 투표권을 수취할 수 있다. 지분이 많을수록 투표에 대한 더 많은 투표권을 가지며, 이는 선출될 가능성의 증가로 이어진다. 리더는 블록을 제안(Propose)한다. 검증인 집단은 그 제안의 타당성 여부를 투표(Prevote)를 통해 검증한다. 전체 검증인 2/3 이상의 동의를 얻었다면 다음 과정으로 넘어가게 된다. 다음 과정은, 제안된 블록에 대해 2/3 이상의 동의가 모인 것을 봤다는 투표(Precommit)를 진행한다. 즉, Precommit은 Prevote에 대한 검증과 투표를 수행하는 과정이다. Prevote의 타당성에 대해 전체 검증인 2/3 이상의 동의를 얻었다면, 그 블록은 확정된다.
이 알고리즘의 간략한 작동 방식은 다음과 같다:
1. 검증인은 위임된 지분에 비례하는 가중치를 가지고 있다.
2. 검증인 집단에서 새로운 리더가 선출된다.
3. Propose: 리더는 다음 블록을 제안한다.
4. Prevote: 제안된 블록을 검증하며 투표한다.
5. Precommit: 전체 검증인의 2/3에 Prevote를 했다면, Prevote에 대해 검증하며 투표한다.
6. 전체 검증인의 2/3에 Precommit을 했다면, 제안된 블록은 확정(Commit)된다.
7. 검증인 집단에서 새로운 리더를 선출한다.
위 프로토콜에서 리더는 결정론적(deterministically)으로 선출된다. 따라서 검증인 집단과 각 검증인의 투표 권한을 알고 있는 네트워크 관찰자라면, 누가 다음 리더로 임명될지 확인할 수 있다. 하지만 다음과 같은 문제가 발생할 수 있다: 가령, 악의적인 공격자가 리더의 순서를 예측한다고 하자. 공격자는 선정될 리더에게 DoS 공격을 할 수 있고, 그다음에 선정될 리더에게도 DoS 공격을 할 수 있다. 최악의 경우, 네트워크 전체가 블록을 생성하지 못하는 상황이 야기될 수도 있다. 이에 텐더민트 커뮤니티에서는 Sentry Node Architecture를 구현함으로써 대처하는 방안이 논의되고 있다. 정상적인 검증인이라면 자신의 IP 주소와 정보를 노출하거나, 다른 검증인과의 연결을 허용하지 않을 것이다. 또한, 실제 위치를 확인하지 못하도록 풀 노드의 proxy 역할을 수행하는 Sentry 노드를 생성함으로써 공격에 대응할 수 있다. 하지만 위 대응은 근본적으로 문제를 해결할 수 없다.
랜덤 함수를 이용하여 공정하게 리더를 선출하는 방식은 어떨까? 특정 블록이 확정되고 난 뒤, 모든 참여자를 대상으로 랜덤하게 리더를 선출한다고 하자. 하지만 공격자 역시 동일한 랜덤 함수를 구성하여, 다음 리더를 예측할 수 있다. 공격할 수 있는 빈도를 줄일 수 있어도, 여전히 공격이 가능하다. 공격자의 행위와 각 참여자의 자격을 올바르게 구분할 수 있는 검증 과정이 필요하다. 리더의 자격을 갖춘 참여자가 있는 상황에서, 어떻게 그 자격을 다른 참여자가 검증할 수 있을까? 또한, 어떻게 모든 참여자가 리더로 선출되는 것을 동등한 확률로 보장할 수 있을까?
Algorand는 위 문제를 ‘Cryptographic Sortition’이라 칭한다. VRF는 참여자의 Secret Key와 Seed 값을 이용하여, Random Hash와 Proof를 출력한다. 이 Proof는 Secret Key로부터 Hash가 생성되었다는 것을 담고 있다. 역으로, 참여자의 Public Key와 Hash 그리고 Proof를 통해, 이 Hash 값의 타당성을 검증할 수 있다. 특정 라운드가 되면, 각 참여자는 VRF를 이용하여 자신의 리더 자격을 계산한다. 그 계산 결과를 다른 참여자에게 공표하고, 그들은 결과를 검증한다. 검증 결과에 의해, 올바른 자격을 갖춘 참여자가 리더로 선출된다. 참여자가 공표 결과를 검증하는 과정이 있어서, VRF를 이용한 리더 선출은 공격자가 다음 리더를 예측하는 행위를 방지할 수 있다.
CodeChain은 텐더민트 합의 알고리즘에 VRF를 이용한 Tenderand: Randomized Leader Election(이하, Tenderand)을 제안한다. 우선, Algorand는 어떠한 알고리즘으로 Cryptographic Sortition를 해결하는지 이해해보자. Algorand는 다음과 같은 알고리즘을 사용한다:
위 알고리즘에서는 리더를 선출하는 과정에서 선출될 참여자의 수를 조절하기 위해 임계값 𝛕가 사용된다. 즉, 𝛕는 몇 명이 선출되기를 기대하는지에 관한 기대값이다. 참여자가 소유하고 있는 지분에 비례하여 선출 확률을 정하기 위해서, Algorand는 매 라운드마다 𝒋 를 사용한다. 위 내용은 추가적인 설명은 지난 포스트 Cryptographic Sortition에서 확인할 수 있다. 단, 참여자가 리더로서 표를 갖게 될 확률은 지분의 비율에 비례한다. 이때, 표를 가질 수 있는 확률변수는 이항분포를 따르게 되는 점을 상기하는 것이 좋다.[1]
스테이킹을 고려하지 않고, 30명의 검증자가 모두 같은 지분을 가지고 있다고 하자. 또한, 텐더민트 합의 알고리즘에서는 단 한 명의 리더가 선출되어야 하므로, 선출 기대값 𝛕를 1이라고 하자. 그렇다면 다음과 같은 확률분포표를 갖는다:
위 확률분포표에서 가장 좋지 않은 상황은 0.362의 확률로 리더가 선출되지 않는 것이다. 따라서 블록을 유효하게 제안할 수 없으며 이 라운드는 합의되지 못하고 종료하게 된다. 이 경우에 대응하기 위해확률변수를 조정할 필요가 있다.
가장 높은 자격을 갖춘 단 한명의 리더를 선출해야하는 상황이지만, 기대값 𝛕를 6으로 설정하여 리더가 존재하지 않는 상황을 피해보자. 따라서, 다음과 같은 확률분포표를 갖는다:
위 확률분포표에 따르면, 리더로 선출되었음을 공표하는 참여자는 대략 6명이 될 것이다. 또한 많은 지분을 가지고 있는 참여자는 여러 차례 선출되었을 가능성도 존재한다. 리더가 존재하지 않는 상황은 확률적으로 줄어들었지만, 리더임을 밝히는 6명의 참여자 중에서 누가 단 한 명의 리더만 남길 여과 과정이 필요하다. 어떻게 단 한 명만 선택할 수 있을까?
Tenderand는 선정된 리더 후보자 중에 단 한 명을 선택하기 위해서 Priority를 도입하였다. Priority는 VRF의 결과인 해시값과 자신이 당선된 횟수 미만의 기수 집합을 해시함으로써 계산할 수 있다. 가령, 참여자가 3번 당선이 되었다면 기수 0과 1, 2를 갖는다. 그렇다면 해당 참여자는 VRF의 해시 결과값과 0과 1, 2를 각각 해시함으로써, 3번의 기회를 사용할 수 있다. 따라서 다른 참여자보다 높은 Priority를 얻을 확률은 자신의 당선 횟수 혹은 지분에 비례하며, 이 역시 확률적으로 보장된다. 이러한 과정을 통해, 단 한 명의 검증된 리더를 선정할 수 있다.
CodeChain은 텐더민트 합의 알고리즘 내의 Valid Block을 판단하는 로직에서 위 검증 과정을 진행할 것을 제안한다:
위 제안은 Valid Block을 검증하는 과정에 Tenderand를 적용하는 것이므로, 텐더민트의 다른 프로세스에 영향을 미치지 않는다. 만약 악의적인 공격자가 Priority를 거짓으로 공표했을 때, VRF에 특성상 검증 과정에서 실패할 것이다. 따라서, 기존에 텐더민트가 가지고 있는 Safety와 Liveness는 큰 영향을 받지 않고 보장될 수 있다.
지난 10월, CodeChain 김선표 엔지니어는 VRF를 이용한 텐더민트에서 Randomized Leader Election 제안에 대한 테크톡을 진행했다. 아래의 영상은 Valid Block을 판단하는 과정에서 어떻게 Tenderand를 적용했는지, 그 과정에서 알고리즘 최적화와 추가적인 검증 과정에 대한 자세한 설명을 포함하고 있다. 또한, 위 제안에 대한 전체적인 과정과 테스트넷 내의 구현 결과는 아래의 CodeChain Research에서 확인할 수 있다. 더 궁금한 점이 있으면, 아래의 영상과 자료에서 확인해보자.
[1] The example of binomial distribution in VRF
