텐더민트의 View-change 방법을 알아보자

텐더민트의 합의는 PBFT와 Polka(Proof of lock change)에 의해서 이루어집니다. 텐더민트 합의는 (프로포즈->프리보트->프리커밋)+->커밋의 순서로 이루어지게 됩니다. 하지만 선택된 프로포져가 오프라인이 되고 바뀌지 않는다면 합의가 멈추게될 것인데요. PBFT는 Liveness를 유지하기 위해서 비잔틴 노드가 프로포져가 되었을 때 프로포져를 바꿔줘야 합니다. 이 글에서 텐더민트가 어떻게 프로포져를 선택하고 어떤 이슈가 있었는지에 대해서 살펴보겠습니다.

텐더민트는 View-change를 위해서 WRR(weighted round robin) 방식을 사용합니다. 텐더민트는 일반적인 PBFT와는 다르게 모든 노드가 동일한 투표권을 가지는 것이 아니라 각 노드가 서로 다른 보팅파워를 가질 수 있습니다. 코스모스 허브의 경우 각 노드의 보팅파워는 스테이킹 받은 양만큼이 됩니다. 텐더민트는 프로포져를 선택할 때도 보팅파워를 감안해서 보팅파워에 비례한 확률만큼 프로포져가 될 수 있습니다. 텐더민트는 View-change를 위해서 추가적인 네트워킹을 요구하지 않습니다. 텐더민트에서 View-change의 순서는 결정론적으로 정해져있고 정해진 시간안에 적절한 블록이 프로포즈 되지 못하거나 커밋되지 못하면 각 노드가 모두 동일하게 정해진 순서에 따라서 프로포져를 바꾸게 됩니다. 이 방식은 추가적인 네트워크 트래픽이 필요없지만 대신 공격자가 다음 프로포져로 누가 선택될 지 미리 다 알고 있다는 단점이 있습니다. 공격자가 다음에 선택될 프로포져의 순서대로 DDOS 공격을 가하는 등의 공격이 가능할 확률이 약간이나마 있습니다. 이 문제를 개선하기 위해서 센트리 노드라는 개념이 있는데 이는 나중에 기회가 되면 다루겠습니다.

텐더민트의 View-change 알고리즘에 대해서 알아보겠습니다. 텐더민트의 WRR 알고리즘의 기본적인 원리는 꽤 심플합니다. 텐더민트에서는 프로포져 선택을 위해 각 노드마다 proposer priority(이하 pp)라는 값을 가지고 있습니다. 매 라운드마다 각 노드들의 pp를 보팅파워만큼 증가시키고 가장 높은 pp를 가진 노드가 그 라운드의 프로프져가 됩니다. 블록을 프로포즈하고 나서는 그 노드의 pp를 노드들의 전체 보팅파워만큼 빼게 됩니다.

예를들어,
A, B, C, D 검증인이 각각 10, 20, 30, 40만큼의 보팅파워를 가지고 있다고 가정합시다.
첫 라운드에서
A -> 10
B -> 20
C -> 30
D -> 40 -> -60 (40–100=-60)
의 pp를 가지게 됩니다. 이 경우 D의 pp가 가장 컸으므로 D는 프로포져로 선택되고 전체 보팅파워인 100 만큼의 pp를 빼게 됩니다. 그러므로 D의 pp는-60이 됩니다.
A -> 20(10+10)
B -> 40(20+20)
C -> 60(30+30) -> -40 (60–100)
D -> -20 (-60+40=-20)
두번째 라운드에서 각 노드의 pp는 각 노드의 보팅파워만큼 증가합니다. C의 pp가 가장 컸으므로 C가 프로포져가 되고 pp가 100만큼 하락해서 -40이 됩니다.
새롭게 추가되는 프로포져는 0의 pp를 가진채로 시작하게 됩니다.

이런 방식으로 최종적으로 자신이 가진 보팅파워에 비례한 만큼 프로포져로 선택될 기회를 얻게됩니다. 하지만 이 방식에서 문제가 있었는데 음수의 pp를 가진 프로포져가 언본딩 했다가 다시 본딩하게 된다면 pp가 0으로 시작하게 됩니다. 이런 방식으로 자신의 보팅파워보다 더 많이 블록을 프로포즈할 기회를 가질 수 있게 됩니다. 그래서 이 방식은 최신 버전에서 개선되었습니다.

우선 새롭게 추가되는 검증인은 pp가 -(전체 보팅파워 * 1.125)로 시작하게 됩니다. 1.125를 곱하는 것은 이렇게 해도 위의 공격이 간혹 유효한 경우가 있기 때문에 이를 완화하기 위해서 1.125라는 매직넘버를 곱해주는 것입니다. 하지만 이렇게 했을때 또 문제가 발생하는 것이 새롭게 추가되는 노드는 음수의 pp만을 가지기 때문에 노드들의 평균적인 pp가 0이 되는 것이 아니라 점점 낮아지게 됩니다. 그래서 이 문제를 완화하기 위해서 열번째 라운드마다 각 노드의 pp를 전체 노드의 평균 pp만큼 빼주게 됩니다. (참조)

하지만 여기서 끝이 아니라 더 심오한 내용이 있습니다. PBFT는 라운드 간의 Safety를 보장하지 않지만 텐더민트는 PBFT에 Polka라는 독자적인 기법을 더해서 라운드 간의 Safety를 보장하도록 개선하였습니다. 텐더민트에서 모든 높이에서 블록의 Safety는 보장되지만 그 블록이 정확히 어느 라운드에서 커밋되는지는 보장하지 않습니다. 그래서 각 노드는 다른 라운드에 블록을 커밋할 수도 있습니다. 그렇기 때문에 노드는 라운드가 아닌 높이에 따른 Canonical한 기준이 필요하게 됩니다. 그래서 위의 표와같이 프로포져는 (H,R) == (H+1,R-1)가 되도록 만들어져 있습니다.

하지만 여기서도 이슈가 있는데 저런 경우 자신 앞의 프로포져가 연속적으로 비잔틴일 경우 그 다음의 노드가 연속적으로 블록을 프로포즈하게 됩니다. 이 문제는 현재 논의 중인데 커밋된 블록에 Lock된 라운드의 정보도 포함하게 만들어서 이 문제를 해결하자는 제안이 있습니다. (참조)

감사합니다.