파이프라인형 BFT 합의에서 발생하는 꼬리 포크(tail-forking) 문제를 설명하고, 이를 방지하기 위한 MonadBFT의 재제안(reproposal) 메커니즘을 소개한다.
현대의 지분증명(Proof-of-Stake) 블록체인은 일부 검증인(validator)이 악의적일 수 있는 상황(이를 _비잔틴_이라고 부르기도 한다)에서도 트랜잭션 블록을 순서대로 정렬하고 최종 확정하기 위해 비잔틴 장애 허용 (BFT, Byzantine Fault-Tolerant) 합의 프로토콜을 사용한다.
높은 트랜잭션 처리량을 달성하기 위해 일부 BFT 프로토콜은 파이프라이닝(pipelining) 기법을 사용한다. 이는 하나의 블록을 순차적으로 하나씩만 최종 확정하는 대신, 여러 블록을 동시에 진행(“비행 중(in flight)”)하도록 하는 방식이다.
그러나 파이프라이닝은 미묘한 공정성 문제를 야기한다. 구체적으로, 꼬리 포크(tail-forking) 라고 알려진 현상의 문을 연다. 대략적으로 말하면, 꼬리 포크에서는 어떤 블록의 리더가, 가장 최근에 제안된 블록이 다른 검증인들로부터 충분한 투표를 받았음에도 불구하고 그 블록 위에 블록을 구축하지 않는다. 대신, 시점 이슈나 악의적 행동 때문에 그 블록을 버리고 더 오래된 블록 위에 새로운 블록을 쌓는다. 꼬리 포크는 특정 블록의 잠재적 보상과 그 블록이 갖는 최대 추출 가능 가치(MEV, Maximal Extractable Value) 기회를 탈취하는 데 악용될 수 있다.
이 짧고 개념적인 글에서는, 전통적 BFT 합의 프로토콜과 파이프라인형 BFT 합의 프로토콜 사이의 주요 차이를 간단히 설명하고, 꼬리 포크 문제를 더 자세히 다룬다. 마지막으로, 파이프라이닝의 성능 이점을 유지하면서도 꼬리 포크에 강한 새로운 파이프라인형 BFT 프로토콜인 MonadBFT에서 꼬리 포크를 방지하는 메커니즘을 설명한다.
블록체인은 블록들의 순서 있는 시퀀스로 볼 수 있으며, 여기서 블록의 높이(height) 는 그 시퀀스에서 블록의 위치를 의미한다. 블록체인이 동작하면서, 검증인들은 특정 높이에 어떤 블록을 추가할지에 대해 합의함으로써 이 블록 시퀀스를 확장해 나간다.
앞서 언급했듯, 지분증명 블록체인은 블록에 합의하기 위해 BFT 프로토콜을 사용한다. 여기서는 전통적 BFT 프로토콜과 파이프라인형 BFT 프로토콜, 두 가지 유형을 간단히 살펴본다.
전통적 BFT 합의 프로토콜에서는 높이 i 의 블록에 대한 합의가 완료된 후에야 비로소 높이 i+1 의 블록에 대한 합의가 시작된다. 프로토콜은 명확히 구분되는 인스턴스(instance) 로 동작하는데, 각 인스턴스는 해당 높이에 대한 합의를 이룰 때까지의 합의 프로토콜 실행을 의미하며, 블록당 하나씩 존재한다.
여기서 Basic HotStuff는 이러한 방식으로 동작하는 전통적 프로토콜의 예시이다. 이 프로토콜은 prepare, pre-commit, commit 의 세 가지 투표 단계를 따른다. 각 단계에서 리더가 제안을 하고 나머지 검증인들이 투표를 하는 식이다. 아래 그림에서 볼 수 있듯, 다음 높이/블록으로 넘어가기 전에 단일 블록에 대한 결정을 내리기 위해 세 단계가 필요하다. 개념적으로 이런 프로토콜에서는 어느 시점에나 활성화된 높이가 하나뿐이며, 높이 간에 합의 인스턴스의 파이프라이닝은 없다.
또한, 위 그림에서 볼 수 있듯이 Basic HotStuff 및 그 변형들에서는 시간이 1, 2, 3, ... 과 같이 계속 증가하는 뷰(view) 로 나뉘며, 각 뷰마다 지정된 리더 역할을 하는 검증인이 존재한다. Basic HotStuff 에서는 각 뷰가 3개의 투표 단계로 구성된다. 프로토콜이 실행됨에 따라 검증인들은 하나의 블록체인만을 확장하면서 뷰를 따라 전진해 나간다. 블록체인 자체는 높이(각 높이당 한 블록) 단위로 진행되지만, 예를 들어 어떤 뷰의 리더가 다운되어 있는 경우처럼, 블록을 최종 확정하는 데 여러 뷰가 걸릴 수 있다.
또 다른 전통적 프로토콜의 예시로 널리 사용되는 Tendermint가 있다. Tendermint 역시 한 번에 하나의 높이만 순차적으로 처리하며, 높이 i 의 블록이 커밋된 이후에야 높이 i+1 블록에 대한 합의를 시작한다.
파이프라인형 BFT 프로토콜에서는 연속된 블록들에 대한 합의가 시간상 겹쳐서 진행될 수 있다. 높이 i 의 블록이 아직 최종 확정되지 않았더라도, 프로토콜은 이미 그 후속 높이들의 블록들을 처리하고 있을 수 있다.
여기서는 파이프라이닝을 활용하는 최적화된 HotStuff 변형인 Chained HotStuff 를 예시로 든다. Basic HotStuff 와 마찬가지로 Chained HotStuff 에도 뷰가 있으며, 각 뷰마다 지정된 검증인이 리더 역할을 한다. 각 뷰에서 리더는 블록을 제안하고, 그 안에 투표 증명서(vote certificate) 를 포함한다. 투표 증명서는 이전 블록에 대한 투표 모음(일반적으로 f 를 최대 악의적 검증인 수라고 할 때, 2f+1 개의 검증인으로 구성된 초과 과반(supermajority) 의 투표)을 의미한다.
Chained HotStuff 는 Basic HotStuff 의 각 단계에서 지정된 리더가 어떤 것을 제안하고 검증인들이 이에 투표한다는 점에 주목하여 이를 확장한 것으로 볼 수 있다. Basic HotStuff 의 세 단계는 서로 유사하므로, Chained HotStuff 는 Basic HotStuff 를 개선하여, 이러한 제안-투표 단계 하나를 파이프라인 방식으로 사용한다. 이때 각 단계는 가장 최신 블록에 대해서는 prepare 로, 그 부모 블록에 대해서는 pre-commit 으로, 그 조부모 블록에 대해서는 commit 으로 동작한다. 어떤 블록이 최종 확정되려면 그 위에 3개의 연속된 블록이 쌓여야 한다. 여기서 연속된다는 의미는, 각 블록이 바로 이전 블록을 검증하는 투표 증명서를 포함해야 한다는 것이다. 직관적으로, 블록을 최종 확정하기 전에 세 개의 연속된 블록을 요구하는 것은, 안전성을 보장하기 위해 여러 번의 투표 단계를 필요로 하는 Basic HotStuff 의 세 단계와 유사한 역할을 수행한다.
파이프라이닝의 핵심 아이디어는, 아래 다이어그램에서 볼 수 있듯이, 여러 개의 인접한 블록들이 한 번에 “비행 중” 상태가 될 수 있다는 것이다(그림 하단에서 보듯, 사실상 각 뷰마다 서로 다른 블록들에 대한 다른 단계가 동시에 진행될 수 있다). 이는 Basic HotStuff 와 같은 전통적 접근과는 다르다. Basic 과 비교하면, Chained HotStuff 는 각 뷰에 투표 단계가 한 번뿐이라는 점도 주목할 만하다.
따라서 파이프라이닝은, 네트워크가 한 블록이 완전히 최종 확정될 때까지 기다린 다음에야 다음 블록 작업을 시작하는 것이 아니라, 그사이에 다가오는 블록들에 대한 작업을 미리 시작할 수 있게 해 주기 때문에 처리량을 개선하는 매력적인 방법이다. 하지만 이는 동시에 항상 여러 개의 미확정 블록들(예: 위 그림의 b' 와 b'' 블록들)이 한꺼번에 쌓이는 “꼬리(tail)”가 존재한다는 뜻이기도 하다. 다음에서는, 이 미확정 블록들의 꼬리가 어떻게 꼬리 포크라는 공정성 문제를 일으키는지 살펴본다.
파이프라인형 BFT 합의 프로토콜은 꼬리 포크(tail-forking)로 알려진 공정성 문제에 취약하다. 이 문제는 파이프라인형 BFT 합의에서 여러 블록에 대한 합의가 동시에 진행되고, 이전 블록이 최종 확정되기 전에 각 새 블록이 체인을 확장하는 사실에서 비롯된다. 앞 절에서 설명했듯, 이는 여러 개의 미확정 블록이 동시에 “비행 중” 상태에 있을 수 있음을 의미하며, 그 결과 체인의 꼬리 부분이 취약해진다. 이는, 앞선 블록이 최종 확정된 이후에야 그 다음 블록에 대한 합의를 시작하는 전통적 접근과 대조된다.
파이프라인형 BFT 합의에서 각 뷰의 리더는 두 가지 책임을 가진다. 새로운 블록을 제안하는 것과, 이전 제안에 대한 투표를 모아 투표 증명서를 만드는 것이다. 블록을 최종 확정하려면 여러 뷰가 필요하므로, 만약 어떤 뷰의 리더가 이전 뷰에 대한 투표를 모으는 데 실패한다면, 충분한 검증인들이 해당 블록에 투표했음에도 불구하고, 이후 뷰의 리더가 그 블록을 버려 버릴 수 있다. 이는 리더가 일정 시간 동안 오프라인 상태인 경우 발생할 수 있으며, 더 나쁘게는, 리더가 고의적으로 이전 뷰의 투표를 무시하여 보상을 탈취하거나 MEV 기회를 악용하고자 할 때도 발생할 수 있다.
두 명의 사용자 Alice와 Bob이 연속된 두 뷰에서 각각 리더를 맡는 예시를 생각해 보자. Alice가 블록 b 를 확장하는 블록 b’ 를 제안했고, 초과 과반(supermajority)의 검증인들이 이에 투표했다고 가정하자. Bob은 이 모든 투표를 관찰하지만, 이를 모아 투표 증명서를 만들고 Alice의 블록을 확장하는 블록을 제안하는 대신, Alice가 제안했던 블록 b’ 를 새로운 제안으로 재제안하기로 결정한다. 즉, Alice의 부모 블록인 b 를 확장하면서 b’ 와 동일한 트랜잭션 집합을 포함하는 새로운 블록 b’’ 를 만든다. 이런 식으로 Bob은 투표 증명서를 숨김으로써 Alice의 보상을 훔칠 수 있다. 제안자는 일반적으로 자신의 블록이 실제로 최종 체인에 포함될 때 보상을 받기 때문이다. 그 전에는 보상이 주어지지 않는다.
MonadBFT 는 꼬리 포크에 강한 파이프라인형 BFT 합의 프로토콜이다. 이 프로토콜은 정직한 검증인이 어떤 제안을 했고, 충분한 수의 검증인이 이를 지지(투표 증명서를 형성할 만큼)했다면, 해당 제안은 버려질 수 없음을 보장한다. 즉, 이후 뷰에서 나오는 모든 제안은 반드시 그 제안을 확장해야 한다. MonadBFT 는 이를 새로운 재제안(reproposal) 메커니즘을 통해 달성한다. 이 메커니즘이 어떻게 작동하는지 설명하기 전에, MonadBFT 의 몇 가지 세부 내용을 먼저 설명한다.
다른 BFT 합의 프로토콜과 마찬가지로, MonadBFT 에서도 검증인은 미리 정해진 시간 안에 다음 뷰로 진행하지 못하면 타임아웃(timeout) 메시지를 발행한다. 다른 프로토콜과 다른 점은, 검증인이 타임아웃 메시지에 자신이 가장 최근에 투표한 제안(이를 로컬 팁(local tip) 이라고 부른다)을 반드시 포함해야 한다는 것이다. 이는 다음에서 보게 되듯 꼬리 포크 방지에 핵심적인 역할을 한다. 타임아웃 증명서(timeout certificate)는 초과 과반의 검증인들로부터 수집된 타임아웃 메시지들로 생성된다.
이제 MonadBFT 의 재제안 메커니즘을 설명할 준비가 되었다. 이 메커니즘은 특정 뷰의 리더가 자신의 제안이 다른 검증인에게 수용되기 위해 반드시 따라야 하는 일련의 규칙을 강제한다. MonadBFT 에서 어떤 뷰에 대한 제안은, 이전 뷰에서 제안된 블록에 대한 투표 증명서 또는 이전 뷰가 실패했음을 증명하는 타임아웃 증명서 가운데 하나를 반드시 포함해야 한다.
제안이 투표 증명서를 포함한다면, 이는 이전 뷰가 성공했다는, 즉 해당 제안이 충분한 지지를 모았다는 뜻이다. 이 경우 리더는 반드시 이전 뷰에서 제안된 블록을 확장해야 한다. 반면, 제안이 타임아웃 증명서를 포함한다면, 이는 이전 뷰가 실패했다는 뜻이다. 이런 경우 리더는 타임아웃 증명서에 포함된 검증인들의 로컬 팁 가운데, 가장 높은 뷰 번호를 가진 로컬 팁을 최고 팁(highest tip) 이라고 부르고, 리더는 이 최고 팁이 가리키는 제안을 재제안해야 한다. 타임아웃 증명서가 제안에 포함되어 있으므로, 검증인들은 리더가 실제로 최고 팁에 해당하는 블록을 재제안하고 있는지 검증할 수 있으며, 그렇지 않을 경우 해당 제안을 거부할 수 있다.
이것이 바로 MonadBFT 를 꼬리 포크 공격으로부터 보호하는 핵심 메커니즘이다. 어떤 제안이 실패한 뷰에서 충분한 지지를 모았으면, 해당 뷰에 대한 모든 타임아웃 증명서에는 반드시 그 제안을 가리키는 팁을 포함한 최소 하나의 타임아웃 메시지가 들어가게 된다.
다만 예외가 있다. 효율성을 위해, 타임아웃 메시지에 포함되는 로컬 팁은 블록 전체가 아니라 블록의 해시만을 포함한다. 따라서 몇몇 극단적인 경우에는, 최고 팁이 가리키는 블록을 복구할 수 없을 수도 있다. 예를 들어, 타임아웃 메시지에 그 팁을 포함시킨 검증인이 메시지를 보낸 직후 크래시해 버리는 경우 등이 있다. 이럴 때 리더는 재제안 메커니즘을 건너뛰고 자유롭게 새로운 블록을 제안할 수 있다.
그러나 그 경우에도, 리더는 해당 블록을 복구할 수 없었다는 사실을 증명하기 위해 자신의 제안에 비인준 증명서(no-endorsement certificate) 를 포함해야 한다. 이 증명서는 리더가 블록을 가져오는 데 실패했으며, 그 제안은 절대 투표 증명서를 얻을 수 없었음을 증명한다. 이를 통해 꼬리 포크 방지 성질은 계속 보장된다.
위에서 설명한 재제안 메커니즘은 비공식적이며 엄밀함을 의도한 것은 아니다. 재제안 메커니즘에 대한 상세하고 형식적인 설명은 MonadBFT 논문 을 참고하길 바란다.
