Barnabé , Luca , Dankrad , Francesco 에게 여러 가지 아이디어를 제공해 주셔서 진심으로 감사드립니다. 특히 Luca는 중요한 논문을 소개해 주었고, Dankrad는 HoneyBadger 사용을 도와주었습니다.
I. 본 프로젝트의 배경 및 "리더리스"에 대한 논의
A. 리더 주도형 합의 프로토콜과 리더 없는 합의 프로토콜
B. "리더십 부재" 상황에서 고려해야 할 사항
II. 연구 결과 — 주요 성과
A. 이정표 I
B. 알고리즘적 공통점
1. 예시 (1): t < n/3, O(n²) 메시지, O(1) 예상 시간 복잡도를 갖는 서명 없는 비동기 이진 비잔틴 합의
2. 예시 (2): BFT의 꿀오소리
B. 리더 없는 합의 프로토콜의 원칙/구성 요소
1. 안정적인 방송
2. 비잔틴 이원 협정
3. 동점자 발생 시 공통 동전 사용
4. " 미니 블록" 또는 미니 트랜잭션 세트의 "강제적" 포함(다수/만장일치 제안)
D. 속성 분석
E. 두 번째 주요 단계 — 구현 및 실제 고려 사항
III. 다음 단계는 무엇인가요?
A. 이더리움 개발 동기
IV. 문학
I. 본 프로젝트의 배경 및 "리더리스"에 대한 논의
제가 처음 탈중앙화 네트워크 합의 프로토콜의 기본 원리를 탐구하는 여정, 혹은 재발견을 시작했을 때, 두 가지 동기가 있었습니다. 첫 번째는 블록체인 아키텍처와 설계를 어떻게 접근하는 것이 가장 좋을지에 대한 순수한 질문에서 비롯되었습니다. 예를 들어, 어떻게 하면 시스템을 더욱 민주적이고 많은 사람들이 접근할 수 있도록 만들면서 하드웨어 요구 사양은 최소화할 수 있을까 하는 질문이었습니다. 이는 많은 사람들이 블록체인 업계에 뛰어들게 된 근본적인 이념적 이유를 대변하는 사고방식이었습니다. 블록체인이 개방성, 투명성, 그리고 개인정보 보호를 동시에 실현하며 기술 산업에 혁명을 일으킬 것이라는 확고한 믿음이 항상 존재해 왔습니다. 블록체인 자체가 이러한 가치들을 융합하여 새로운 기술 패러다임을 형성하고, 그 발전을 통해 이러한 가치들을 더욱 발전시켜 나갈 것이라는 믿음이었습니다. 두 번째 동기는 리더 주도 합의 프로토콜이 업계 표준이 된 것이 단순히 네트워크 효과 때문인지, 아니면 리더 없는 합의 메커니즘이 성능 면에서 경쟁력이 없기 때문인지에 대한 순수한 호기심에서 비롯되었습니다.
이러한 개인적인 관심사 외에도, 2024년에는 블록체인 연구자들 사이에서 리더리스 알고리즘에 대한 공개적인 관심도 높아졌습니다. 패러다임(Paradigm)은 리더리스 경매 제안을 발표했고, 아이겐레이어(Eigenlayer)의 스리람(Sreeram)은 빅디퍼(BigDipper)를 위해 일종의 다중 제안자 체계를 다룬 논문을 공동 집필했으며, 전 SMG 멤버였던 맥스 레스닉(Max Resnick)은 이더리움을 위한 잠재적인 멀티체인(일종의 다중 제안자) 아키텍처인 BRAID를 구상했습니다.
지금은 리더가 없는 합의 프로토콜에 대한 연구가 그 어느 때보다 중요합니다. 하지만 이러한 과제에 대한 해결책을 논의하기 전에, "진정한 리더 없는 합의 프로토콜"이란 무엇을 의미하는지 명확히 해봅시다.
A. 리더 주도형 합의 프로토콜과 리더 없는 합의 프로토콜
리더 주도형 합의 프로토콜과 리더리스형 합의 프로토콜은 동일한 스펙트럼의 양극단에 존재하지만, 리더 주도형을 정의하는 것이 리더리스형을 정의하는 것보다 훨씬 간단합니다. 리더 주도형 알고리즘은 중앙 조직자가 프로토콜 진행을 주도하는 프로토콜을 의미하며, 예를 들어 통신 라운드를 조정하거나 각 라운드의 의사 결정자 역할을 합니다. 대부분의 고전적인 리더 주도형 합의 프로토콜에서 리더는 일반적으로 다른 프로세스로부터 메시지를 수집하거나 전체 프로토콜에 대한 제안을 하는, 지정, 선출 또는 기타 방식으로 미리 선택된 단일 프로세스(예: 노드 참여자, 복제본)를 의미합니다(일반적으로 한 라운드 동안만 리더 역할을 하며, 이후에도 다시 리더가 될 수 있습니다).
리더 주도 BFT는 다음과 같은 두 가지 방식으로 효율적입니다. (1) 리더는 최악의 시나리오(모두 대 모두) 대신 프로토콜 메시지를 수집하는 중앙 집중식 조정자 역할을 합니다(모두 대 일). 따라서 통신 복잡성이 크게 줄어듭니다. (2) 유효한 제안을 하는 단일 프로세스는 여러 프로세스가 많은 제안을 제공하는 것보다 더 효율적입니다. 이는 프로세스가 서로 다른 제안을 통신하고 "최상의" 제안을 선택하고 합의하는 방법을 찾아야 하는 라운드를 제거하기 때문입니다.
리더 주도형 프로토콜의 가장 큰 취약점은 리더가 네트워크에 공개적으로 알려져 있기 때문에 뇌물 수수 및 표적 DDoS 공격에 취약하다는 점입니다. 리더리스 알고리즘은 (1) 비동기적으로 작동하도록 설계되었기 때문에 (2) 응답하지 않는 참여자를 허용할 수 있으므로 전체 네트워크에 영향을 미칠 수 있는 단일 프로세스에 덜 취약하고 노출되지 않기 때문에 리더 주도형 알고리즘보다 더 견고합니다. 그러나 비동기 리더리스 프로토콜은 프로토콜에 수백 개의 프로세스가 참여하게 되면 지연 시간과 처리량 문제가 발생합니다.
리더리스 프로토콜을 정의하거나 설명하는 것은 개념적으로 모호하기 때문에 더 어렵습니다. 어떤 면에서는 리더리스 프로토콜이 무엇인지보다 무엇이 아닌지에 더 가깝습니다. 어떤 이들은 리더리스 프로토콜을 특정 프로세스를 중단하더라도 전체 프로토콜의 진행에 지장을 주지 않는 프로토콜로 정의합니다. 좀 더 유연한 방식으로 리더리스 프로토콜을 생각할 수도 있는데, 각 라운드가 특정 프로세스에 의해 지배되지 않는다는 것입니다. 이러한 특징이 강할수록 리더리스에 가깝다고 볼 수 있습니다. 또한, 합의 도출 과정이 협력적일수록 리더리스에 가깝다고 볼 수도 있습니다. 다음은 리더리스 합의 프로토콜의 세 가지 예시와 각각의 예시가 리더리스 스펙트럼에서 어느 위치에 있는지(가장 덜 리더리스한 것부터 가장 "리더리스한" 것까지)를 보여줍니다.
민주적 BFT(DBFT): DBFT는 모든 프로세스가 "약한" 조정자의 도움을 받아 이진 제안을 만들고 받을 수 있도록 합니다. 아이러니하게도 이는 이 세 가지 예시 중 가장 민주적이지 않은 방식입니다 .
Mir: 여러 명의 리더가 (충돌 없이) 동시에 제안을 하는 다중 제안자 프로토콜. 이는 중간 방식입니다 .
HoneyBadger BFT: 프로세스는 지속적으로 트랜잭션을 수신하고 각 에포크 내에서 최종 블록 제안에 포함될 트랜잭션 집합의 하위 집합을 제공합니다. 최종 제안이 유효하려면 모든 트랜잭션 집합이 포함되어야 합니다. 이는 고도로 협력적인 합의 블록 구축 방식이며, 세 가지 방식 중 리더리스 스펙트럼에서 순수한 "민주주의"에 가장 가깝습니다 .
여기서 잠시 멈춰서 협력적 블록 생성 방식이 과연 "가장 민주적인 방식"인지 생각해 볼 필요가 있습니다. 블록체인 맥락에서 민주적이란 무엇을 의미하는지 생각해 보면, 참여자 대부분이 제안 선택에 있어 최소한 동등한 발언권을 갖는 것을 의미할 수 있습니다. 이는 제안 제출 및 검토뿐 아니라 최종적으로 블록에 추가될 제안 선택에도 적용될 수 있습니다. 리더 주도형 설계에서는 의사 난수 리더 선정, 합의 참여자 투표 위임, 가중 투표(예: 경제적 지분이 높을수록 블록 제안자가 되어 다음 블록을 결정할 확률이 높아짐)와 같은 메커니즘을 통해 이를 구현할 수 있습니다. 이와 대조적으로 리더리스 합의 프로토콜은 본질적으로 "모두를 위한 민주주의"와 같은 원칙에 부합하며, 모든 개별 프로세스 간에 최대한 동등한 발언권을 확보하는 동시에 통신 복잡성 및 지연 시간과 같은 성능 지표에 대한 타협을 최소화하는 것을 목표로 합니다.
덧붙여 말하자면, 비트코인이 사용하는 나카모토 합의 프로토콜이 리더리스 프로토콜인지에 대한 질문이 꽤 자주 제기됩니다. 결론부터 말씀드리자면, 제 생각에는 그렇지 않습니다. 철학적으로 이 질문은 크게 두 가지 관점에서 볼 수 있습니다. (1) 나카모토 합의는 리더리스 프로토콜과 유사한 속성을 일부 공유하지만, 그 결과는 리더리스 프로토콜과 같지 않습니다. 다시 말해, 우리가 "기회 기반 민주주의"라고 부를 수 있는 것을 달성하는데, 여기서 기회 기반 민주주의란 모든 프로세스가 블록을 "획득"하고 발언권을 가질 수 있는 동등한 기회를 갖는 것을 의미합니다(하드웨어 요구 사항의 지속적인 증가 비용은 무시함). 하지만 다음 사항을 고려하는 것이 중요합니다. (2) 각 라운드에는 단 하나의 "승자"만 존재하며, 이 승자가 전체 거래 블록을 "결정"합니다. 본질적으로 각 프로세스는 발언권을 가질 기회가 있지만, 최종적으로는 단 하나 의 프로세스만이 발언권을 갖습니다. 게다가, 현실적으로 현재 단계에서 채굴 장비 요구 조건 및 투자 비용을 고려할 때, 참여자들이 채굴 풀을 통해 참여하더라도, 대부분의 사람들과 신규 참여자들을 배제하는 가격 때문에 프로토콜이 더 이상 진정한 민주적이라고 보기는 어렵습니다. 여기서 주목할 점은 현재 이더리움이 개인 투자자나 경제적 지분이 낮은 스테이커를 우선시하는 문제에 대한 윤리적 논쟁에 휩싸여 있다는 것입니다. 이는 민주주의와 효율성 및 "진보"라는 원칙 사이의 갈등으로 이어집니다. 그러나 이 논쟁은 본 보고서의 범위를 벗어납니다.
이제 우리는 합의 프로토콜의 두 가지 범주, 즉 리더리스 방식과 리더 주도 방식을 또 다른 근본적인 질문 아래 비교합니다. 리더리스 프로토콜의 효율성에는, 특히 리더 주도 방식과 비교했을 때, 본질적인 한계가 존재하는가? 리더리스 BFT 합의 알고리즘이 이론적으로 더 바람직하다고 하더라도, 구현 가능성 또는 이론적 측면에서 리더 주도 방식보다 최소한 동등하거나 더 효율적인 방식으로 설계될 수 있는가?
역사적으로 볼 때, 이러한 연구 분야는 제대로 탐구되지 않았습니다. 리더 주도 합의 프로토콜이 인기를 얻게 된 주된 이유는 설계가 쉽고 현재 운영 중인 거의 모든 블록체인 프로토콜에서 잘 작동하기 때문입니다. 이러한 현재의 패러다임에서 사용자와 프로토콜 설계자는 나카모토 합의에서 경험하는 것과 같은 민주주의에 자연스럽게 매몰되어 왔습니다. 즉, 모든 참여자가 블록 생성에 참여하는 진정으로 민주적이고 협력적인 블록 생성 과정보다는 리더가 되는 민주적 과정에 노력을 집중하게 되는 것입니다.
B. "리더십 부재"에 대한 고려 사항
그렇다면 왜 지금 우리 업계가 합의 프로토콜, 특히 리더리스 합의 프로토콜(또는 최소한 리더 주도형 프로토콜에서 벗어나는 것) 방향으로 재고하는 것이 중요할까요? 진정한 리더리스 합의 프로토콜은 블록체인이 항상 지향해 온 이상적인 윤리적 가치를 증진시킬 뿐만 아니라, 이더리움과 같은 프로토콜에 혁신적인 변화를 가져올 수 있기 때문입니다. 특히, 리더리스 합의 계층은 L1 계층이 겪고 있는 기존의 문제점들을 완화하거나 완전히 해결하여(일부 문제점을 무의미하게 만들거나 아예 문제가 되지 않도록 만들 수 있음) 균형을 재조정할 수 있습니다. 이더리움의 맥락에서 리더리스 합의 계층은 타이밍 게임과 같은 문제를 최소화하고, 제안자와 블록 생성자의 분리 문제를 없애 "제안자 독점"을 종식시키는 등 여러 가지 바람직하고 유익한 기회를 제공합니다. 또한, 리더리스 합의 프로토콜은 포괄적이고 협력적인 블록 생성 방식과 그 특성상 기본적으로 검열 및 MEV(Mean Execution Expansion)에 대한 저항력을 제공합니다.
이 논의를 마무리하면서, 이념적 주장과 효율성 주장 사이 어딘가에 존재하는 합의에 대한 더 폭넓고 심층적인 고찰을 제시하고자 합니다. 블록체인 은 합의를 기반으로 하기 때문에, 이념적 측면과 효율성 측면 모두에서 합의가 업계에 매우 중요하다는 점을 분명히 인식해야 합니다. 합의가 블록체인의 "진실"과 정당성 또는 표준적인 블록체인을 결정한다면, 이러한 결정이 가능한 한 정직하고 정확하게, 그리고 커뮤니티 전체의 이익을 위해 이루어지도록 해야 합니다. 따라서 합의 결정 과정은 공정하고 형평성 있게, 그리고 선의에 기반하여 이루어져야 합니다. 이 보고서의 목적은 철학적 사고 과정에 깊이 들어가 블록체인의 거버넌스 방식을 정당화하려는 것이 아니라, 합의 프로그래밍에 대한 대안적인 접근 방식이 존재할 수 있으며, 리더 없는 합의 알고리즘이 최선의 선택일 수 있다는 점을 제시하고자 합니다.
이처럼 리더리스 합의 프로토콜을 탐구하고 수용하는 것이 왜 중요한지 간략하게 살펴본 후, 기존 연구 및 관련 원칙에서 주목할 만한 몇 가지 결과를 검토해 보겠습니다. 이러한 결과는 리더리스 합의 프로토콜이 충분한 성능을 발휘할 수 있는지 여부를 판단하는 데 필요한 기초를 제공하고, 이더리움과 호환되는 설계를 구상하는 데 도움을 줄 것입니다.
III. 연구 결과 — 주요 성과
A. 1단계: 관련 BFT 문헌(비동기 BFT 문헌 포함)을 완벽하게 검토합니다. 리더리스 프로토콜과 연관되어 유용할 수 있는 흥미로운 컴퓨팅 개념을 검토합니다.
이 섹션에서는 마일스톤 I을 다룹니다. 이 심층 분석을 위해 합의 프로토콜 관련 논문 40편 이상을 검토했습니다( 가장 관련성이 높은 논문 목록은 보고서 말미의 부록을 참조하십시오) . 리더 없는 합의 알고리즘 논문들은 이론적 사고가 어떻게 서로 영향을 주고받으며 발전해 왔는지 파악하기 위해 시간 순서대로 읽었습니다. 실제로, 특히 활용된 구체적인 구성 요소 측면에서 알고리즘들 간의 사고 과정의 주제적 중복과 명백한 유사점을 발견했습니다.
B. 알고리즘적 공통점
유망한 리더리스 합의 알고리즘들은 명확한 공통점을 가지고 있으며, 리더리스 합의 연구 초기 단계에 속합니다. 실제로, 2015년 논문 "t < n/3, O(n²) 메시지, O(1) 예상 시간을 갖는 서명 없는 비동기 이진 비잔틴 합의"에서 사용된 구성 요소들은 이후 대부분의 리더 합의 연구에서 기초적인 구성 요소로 활용되었습니다. 이러한 구성 요소들을 분석하기 위해, 그 활용 사례를 보여주는 두 가지 중요한 리더리스 프로토콜의 구조를 쉬운 말로 설명하겠습니다.
1. 예시 (1): t < n/3, O(n²) 메시지, O(1) 예상 시간 복잡도를 갖는 서명 없는 비동기 이진 비잔틴 합의
이 합의 프로토콜은 이진 비잔틴 합의(Binary Byzantine Agreement) 방식을 사용합니다. 각 프로세스는 이진 값(0 또는 1)을 제안합니다. 분산 알고리즘은 다음과 같은 단일 이진 값에 대해 합의에 도달합니다.
1. 모든 정직한 과정은 동일한 값을 출력합니다.
2. 합의된 가치는 적어도 하나의 공정한 절차를 통해 제시되었습니다.
이 프로토콜은 "이진 비잔틴 합의(Binary Byzantine Agreement)" 프로토콜을 다음과 같이 구성합니다. 각 프로세스는 먼저 로컬에서 제안된 값으로 추정치를 설정합니다. 그런 다음 알고리즘은 단일 값이 도출될 때까지 DSBV(아래 설명 참조)의 인스턴스를 반복적으로 실행하며, 프로세스가 미결정 값이나 기본값을 만나면 로컬 추정치를 공통 코인에서 추출한 임의 값으로 대체합니다.
이를 달성하기 위해 본 논문에서는 점진적으로 더 강력해지는 분산 알고리즘 세트를 구축합니다.
이진 값(BV) 브로드캐스트: 모든 프로세스는 자신이 제안하는 값을 브로드캐스트합니다.
어떤 프로세스가 다른 프로세스로부터 특정 메시지를 최소 t+1개 이상 수신하면, 해당 메시지를 모든 프로세스에 브로드캐스트합니다.
어떤 프로세스가 다른 프로세스로부터 특정 메시지를 최소 2t+1개 이상 수신하면, 해당 메시지의 값을 출력에 추가합니다.
직관적으로, 비잔틴 암호화만 허용하는 메시지는 2t+1(정직한 프로세스 수가 악의적인 프로세스 수보다 많음을 보장하는 데 필요한 최소 프로세스 비율)에 의해 수신된 메시지만 BV에서 출력되므로 필터링됩니다.
하지만 이 알고리즘은 두 가지 값을 모두 출력할 수 있고 종료 지점이 없기 때문에 아직 합의 알고리즘이라고 할 수는 없습니다.
동기화/강력한 이진 값(SBV) 브로드캐스트: 이 알고리즘은 출력을 제공 하고 종료함으로써 이진 값(BV)을 확장합니다. 그러나 단일 값 또는 두 값의 집합을 동시에 출력할 수 있으므로 완전한 이진 합의를 제공하기에는 충분히 강력하지 않습니다. 단, 종료 시 단일 값을 출력하는 모든 프로세스는 동일한 값을 출력해야 합니다. 구현에서는 BV 브로드캐스트를 두 번 연속으로 호출합니다.
이중 동기화 이진 값(DSBV) 브로드캐스트: 이는 SBV의 개선된 버전입니다. 프로세스가 두 값을 모두 출력할 경우, 해당 값은 기본값으로 대체됩니다. 하지만 프로세스는 여전히 두 값(이 경우 하나의 이진 값과 기본값)을 출력할 수 있으며, 두 이진 값을 동시에 출력하는 경우는 없습니다. DSBV는 SBV를 두 번 연속으로 호출하여 구현됩니다.
특정 프로세스들이 결정을 내릴 수 없는 경우, 약한 공통 코인을 뽑을 수 있습니다. 공통 코인은 모든 참여자가 관찰할 수 있지만 적대자는 예측할 수 없는 무작위 오라클입니다(즉, 적어도 하나의 정직한 프로세스가 요청하기 전까지는 공통 코인 값을 알 수 없어야 합니다). 대부분의 논문에서는 Rabin의 "Randomized Byzantine Generals"를 공통 코인 프레임워크로 참조합니다.
2. 예시 (2): BFT의 꿀오소리
HoneyBadger는 CKPS01 멀티캐스트를 사용하는데, 이는 ACS(후술)를 신뢰할 수 있는 브로드캐스트(Reliable Broadcast)와 비동기 이진 비잔틴 합의(Asynchronous Binary Byzantine Agreement, ABA)로 축소한 것입니다. HoneyBadger는 CKPS01에 도입된 비동기 공통 부분집합(ACS) 프리미티브를 통해 프로세스가 블록에 포함할 트랜잭션을 제안할 수 있으므로 리더가 없는 트랜잭션 처리 시스템(즉, 블록체인)을 구축할 수 있다는 점에 주목했습니다. 그러나 CKPS01의 구현은 비효율적이었고, HoneyBadger는 신뢰할 수 있는 브로드캐스트와 비동기 이진 비잔틴 합의(ABA)를 결합하여 보다 효율적인 ACS 시스템을 구현했습니다.
각 프로세스는 ACS(Atomic Broadcast System)의 원자적 브로드캐스트를 사용하여 자신의 큐에서 B/N(네트워크 전체 프로세스 수 중 B개)개의 트랜잭션을 제안합니다. 프로세스는 각 큐의 첫 번째 B개(FIFO)에서 무작위로 선택된 트랜잭션을 제안합니다. 직관적으로, 이는 대부분 서로 다른 트랜잭션의 포함을 촉진합니다. 이러한 트랜잭션 부분 집합은 암호화되며 ACS가 완료된 후에만 복호화됩니다. 직관적으로, ACS가 완료된 후에만 복호화하고 지정된 임계값 암호화 방식(TPKE)을 사용함으로써, 공격자가 제안 내용을 알아내기 전에 트랜잭션 집합을 결정할 수 있습니다. 즉, 적어도 하나의 정직한 프로세스가 복호화 정보를 공개하기 전에 트랜잭션 집합을 결정할 수 있습니다.
N개의 프로세스는 최종 집합에 포함되는 것으로 확인된 제안된 값의 벡터에 동의하기 위해 이진 비잔틴 합의를 사용합니다. 직관적으로 프로세스는 브로드캐스트가 서로 다른 순서로 완료되는 것을 관찰할 수 있으므로 최종 벡터에 적어도 Nf개의 양수(1) 비트가 포함될 것이 확실해질 때까지 음수(즉, 0)를 제안하지 않습니다.
C. 리더 없는 합의 프로토콜의 원칙/구성 요소
1. 안정적인 방송
신뢰성 있는 브로드캐스트(Reliable Broadcast) 개념은 가브리엘 브라차(Gabriel Bracha)와 샘 투에그(Sam Toueg)가 "비동기 합의 및 브로드캐스트 프로토콜(Asynchronous Consensus and Broadcast Protocols)"에서 처음 제시한 것으로 알려져 있습니다. 신뢰성 있는 브로드캐스트는 최소한 아래의 유효성, 합의성, 그리고 완전성이라는 필수 조건을 충족해야 합니다.
유효성: 올바른 프로세스가 집합 v를 출력하면 |v| >= Nf이고 v에는 최소 N — 2f개의 올바른 프로세스의 입력이 포함됩니다.
합의: 만약 올바른 프로세스가 v를 출력한다면, 모든 프로세스는 v를 출력한다.
전체성: 만약 Nf개의 올바른 프로세스가 입력을 받는다면, 모든 올바른 프로세스는 출력을 생성합니다.
2. 이진 비잔틴 협정*
*이진 비잔틴 합의는 다중 값을 수용하도록 수정할 수 있습니다.
이 알고리즘은 비잔틴식 또는 악의적인 방식으로 프로세스가 실패할 수 있는 시스템 내에서 합의를 도출할 수 있어야 합니다(예: 비잔틴 행위자에 의한 실패). 이를 성공적으로 해결하기 위해서는 다음 조건을 충족해야 합니다.
타당성: 결정된 값은 올바른 프로세스를 통해 제시되었습니다 (결함 있는 프로세스에 의해서만 제시된 값은 결정될 수 없습니다).
합의: 두 가지 올바른 과정이 서로 다른 값을 결정하지 않는다.
결정: 각 올바른 절차가 결정합니다.
이와 관련하여, 리더리스 합의 프로토콜에서 때때로 사용되는 유사한 기본 요소로는 비동기 검증 가능 정보 분산(AVID-FP)이 있습니다. 이 개념은 크리스티안 카친과 스테파노 테사로가 2004년에 발표한 논문 "비동기 검증 가능 정보 분산(Asynchronous Verifiable Information Dispersal)"에 제시되어 있습니다. 이 방식은 신뢰할 수 있는 브로드캐스트 프로토콜과 소거 코딩을 결합하여 비잔틴 공격에 최적으로 저항하는 비동기 환경에서 정보 분산 네트워크의 검증 가능성을 확보합니다.
3. 동점자 발생 시 공통 동전 사용
합의에 도달할 수 없는 모호한 프로토콜 결과가 발생하는 경우, 무작위성을 도입하는 오라클이 사용됩니다. 일반적인 코인은 약한 코인과 강한 코인으로 나뉘며, 주요 절차의 마지막 단계에서 모호성이나 교착 상태를 해결하는 역할을 합니다.
4. " 미니 블록" 또는 미니 트랜잭션 세트의 "강제적" 포함(다수/만장일치 제안)
HoneyBadger, BigDipper, Mir와 같은 일부 리더리스 합의 프로토콜은 모든 리더(모든 프로세스 또는 특정 프로세스 하위 집합)가 라운드 트랜잭션 세트의 일부 이상을 제안해야 한다는 프로토콜 요구 사항을 포함함으로써 효과적인 리더리스 합의를 구현합니다. 이러한 트랜잭션은 최종 블록 제안에 반드시 포함되어야 합니다.
D. 속성 분석
다음은 리더리스 합의 프로토콜 설계에서 자주 볼 수 있는 일반적인 속성/가정입니다.
최적의 복원력: f개의 비잔틴 프로세스 또는 결함 있는 프로세스를 허용하려면 n >= 3f+1이 필요합니다.
전체 간 의사소통의 복잡성.
비동기 또는 최종 동기(즉, 부분적으로 동기) 네트워크 환경에서 작동합니다.
결정론적이라는 점에 주목할 필요가 있습니다. 결정론적 비동기 합의 프로토콜은 비잔틴 오류가 단 하나라도 발생하면 허용할 수 없습니다. 비결정론적 환경에서는 프로토콜이 N/3개 이상의 부정직한 프로세스를 허용할 수 없습니다.
서명이 필요 없는 합의 알고리즘: 많은 리더 없는 합의 알고리즘은 서명이 필요 없는데, 이는 모든 프로세스 간에 직접적인 지점 간 통신 채널이 존재하기 때문입니다. 프로세스 간 통신에서 프로세스들이 안전하게 합의에 도달하려면 일정 수준의 프라이버시가 보장되어야 합니다(비잔틴 구조에서).
임계값 암호화: 합의가 이루어지기 전에 비잔틴 행위자(예: 거래 순서를 바꾸거나 검열하려는 자)로부터 제안 내용이 비공개로 유지되도록 보장하는 데 도움이 됩니다.
이 시점에서 탐구해 볼 중요하고 흥미로운 질문은 이러한 속성들 중 어느 것이 리더리스 합의 프로토콜의 필연적인 속성인지 여부입니다. 답은 이러한 속성들 중 어느 것도 절대적인 규칙이 아니며 논리적으로 반드시 따라야 하는 것도 아니라는 것입니다. 즉, 이론적으로 불가능하다는 이유로 리더리스 합의 프로토콜이 이러한 속성 중 어느 하나라도 충족하지 않으면 존재할 수 없다는 것은 아닙니다. 이러한 자유를 바탕으로, 우리는 이더리움과 호환되는 리더리스 합의 프로토콜 설계에 있어 이러한 제약 없이 나아갈 수 있습니다.
E. 두 번째 주요 단계 — 구현 및 실제 고려 사항
다음 두 가지 질문에 답하십시오. (1) 리더가 없는 BFT 프로토콜은 이론적으로 리더가 있는 프로토콜보다 항상 성능이 떨어집니까(효율성과 실용성)? (2) 그렇다면 얼마나 떨어집니까(이를 정량화할 수 있습니까?).
본 프로젝트에서는 연구 대상 알고리즘을 직접 실행하지는 않았지만, 논문 저자들이 수행한 실험에서 관찰된 성능 지표를 검토했습니다. 이러한 지표는 벤치마크라는 맥락에서 고려할 때만 의미를 가지며, 본 프로젝트에서는 이더리움 L1의 현재 상태를 벤치마크로 삼는 것이 타당합니다. 그러나 이더리움의 합의 알고리즘과 전반적인 설계는 매우 복잡하고 세부적인 요소가 많아 허니배저와 같은 단순화되고 추상적인 프로토콜과 직접 비교하기는 어렵습니다.
현재로서는 이러한 다른 프로토콜들은 이더리움에서 사용 가능한 상태가 아니므로, 지금으로서는 이더리움용 리더리스 합의 프로토콜 설계의 실효성을 측정하려면 성능과 실용성에 영향을 미칠 수 있는 관련 저수준 세부 사항을 갖춘 성숙한 프로토콜이 필요하다는 결론을 내릴 수 있습니다.
이 논문들은 일반적으로 우수한 성능을 보이는 리더리스 합의 프로토콜 설계가 가능하다는 개념 증명을 제공하며, 이는 앞으로 나아갈 강력한 동기를 부여합니다. 특히 HoneyBadger의 사례는 매우 흥미로운데, 이 프로토콜은 지리적으로 분산된(5개 대륙) WAN 환경에서 104개의 프로세스를 사용하여 초당 1,500건의 확정 트랜잭션 처리량을 달성하는 실험을 수행했습니다.
IV. 다음 단계는 무엇인가요?
그렇다면 이러한 연구 결과는 리더리스 프로토콜이 훌륭하다는 것을 의미하는 걸까요? 우리는 리더리스 프로토콜을 더 많이 도입해야 할까요? 성능이 더 뛰어난 걸까요? 이더리움과 호환되는 리더리스 합의 프로토콜을 성공적으로 설계할 수 있을까요? 리더리스 프로토콜이 이더리움이 현재 겪고 있는 고질적인 문제들을 실제로 해결하거나 완화할 수 있을까요?
이러한 질문에 답하기 위해, 리더리스 합의 프로토콜이 해결할 수 있는 잠재적인 문제점들을 간략하게 살펴보겠습니다. 문제점들은 다음과 같습니다.
A. 이더리움 개발 동기
타이밍 게임
블록 생성자는 각 슬롯 내에서 가능한 한 늦게 블록 제안을 제출하도록 유도됩니다. 마감일에 가까울수록 블록 보상이 높아지기 때문입니다. 이러한 현상의 이유는 이전 가격 변동(즉, 마지막 블록) 이후 시간이 길어질수록 가격 변동, 즉 자산 가격 차익거래(거래) 기회가 발생할 확률이 높아지기 때문입니다.
검열 저항
블록 생성자가 블록 제안에서 특정 거래를 누락하지 못하도록 방지합니다. 약한 설정은 자신의 블록에서 특정 거래를 제외하는 것을 방지하고, 강한 설정은 다른 블록 생성자가 특정 거래를 블록에 포함하지 못하도록 방지합니다.
메브
MEV(최대 추출 가능 가치)는 블록체인 활동에서 "추출"하거나 얻을 수 있는 수익을 의미하며, 이는 블록체인의 고유한 엔지니어링 설계/아키텍처 덕분에 가능한 것입니다. MEV는 특히 블록 보상, 수수료 및 팁을 초과하는 수익을 가리킵니다. MEV는 근본적으로 두 가지 주요 원칙에 기반하여 이더리움에서 실현 가능합니다. (1) 공개 멤풀과 블록 생성의 선형적 특성 덕분에 확정된 블록의 예상 결과 또는 효과를 상당한 수준의 신뢰도로 예측할 수 있습니다. (2) 따라서 합리적인 MEV 추구자는 차익 거래 기회를 포착하기 위해 하나의 블록 내에서 또는 블록 간, 혹은 여러 체인에 걸쳐 특정 거래의 순서나 포함/제외를 조작할 수 있습니다. 여기서 차익 거래는 정보/시장/가격 비대칭성을 이용하여 수익을 창출할 수 있는 상황을 의미하는 넓은 의미로 사용됩니다.
제안자-시공자 분리
MEV-Boost와 같이 중앙 집중화된 서비스로 변모하여 이더리움(및 사용자)의 신뢰와 의존을 요구하는 프로토콜 외부 서비스에 대한 의존도를 줄이기 위해 제안자와 구축자의 역할을 분리하려는 움직임이 있었습니다. 구축자가 항상 제안자와 일치하는 것은 아니지만, 이 두 역할의 분리가 의무화된 것은 아닙니다.
제안자 독점
이 보고서의 서두에서 논의된 바와 같이, 일부에서는 각 슬롯마다 한 명의 주요 블록 제안자가 있는 것이 본질적으로나 실제적으로 그다지 민주적이지 않다고 생각하고 믿습니다.
리더리스 합의 프로토콜에서는 위에서 언급한 문제들의 영향을 완화하기 위해 몇 가지 도구와 메커니즘을 통합할 수 있습니다. 예를 들어, "제안자 독점" 문제는 리더리스 합의 프로토콜에서는 당연히 발생하지 않습니다. 합의 및 실행 역할이 블록 생성 활동에 통합되어 제안자-블록 생성자 분리가 필요 없어집니다. 이는 현재 이더리움의 프로토콜 외 서비스 문제에 대한 근본적인 해결책이라기보다는 임시방편에 가까운 조치입니다. 검열 저항, MEV(Method Execution Value), 타이밍 게임과 같은 더 어려운 내재적 문제들은 실행 실패 및 경제적 인센티브를 고려하면서 협력적인 블록 생성을 통해 트랜잭션 무작위화를 강제하는 설계를 통해 완화될 수 있습니다.
이더리움을 중심으로 한 리더리스 합의 프로토콜 도입의 이점 외에도, 표준적인 리더리스 합의 프로토콜의 속성들은 이더리움의 현재 개발 단계와 자연스럽게 부합합니다. 예를 들어, 미니 블록 강제 포함 개념은 이더리움이 제안한 포함 목록과 일맥상통하는데, 이는 특정 트랜잭션의 강제 포함을 통해 검열 저항성을 검증하는 과정에서 의도치 않게 발생하는 부작용을 방지하는 역할을 합니다.
이 특정 순수 연구 프로젝트의 최종 목표는 이더리움 코어에서 작동할 수 있는 리더리스 프로토콜의 비교적 완성도 높은 골격을 만드는 것입니다. 마일스톤 III 및 IV와 관련하여, 첫 두 마일스톤을 완료한 후 리더리스 BFT 프로토콜이 높은 수준의 안정성과 성능을 모두 갖출 수 있는 충분한 잠재력을 가지고 있음을 확인했습니다.
IV. 문학
Borran, F. (2009). 리더가 필요 없는 비잔틴 합의 알고리즘.
램포트, L. (2011). 지도자 없는 비잔틴 팍소스.
Mostéfaoui, A., Moumen, H., & Raynal, M. (2015). t < n/3, O(n²) 메시지, O(1) 예상 시간을 갖는 서명 없는 비동기 이진 비잔틴 합의.
Miller, A., Xia, Y., Croman, K., Shi, E., & Song, D. (2016). BFT 프로토콜의 꿀오소리.
Duan, S., Reiter, MK, & Zhang, H. (2018). BEAT: 비동기 BFT를 실용화하다.
Crain, T., Gramoli, V., Larrea, M., & Raynal, M. (2018). DBFT: 효율적인 리더리스 비잔틴 합의 및 SMR.
Gągol, A., et al. (2019). Aleph: 비동기 네트워크에서 효율적인 원자적 브로드캐스트.
“팀 로켓.” (2020). Avalanche: 불안정성을 통한 확장 가능하고 확률적인 리더리스 BFT 합의.
Antoniadis, P., et al. (2021/2022). 리더 없는 합의.
Stathakopoulou, C., et al. (2021). Mir-BFT: 분산 네트워크를 위한 고처리량 강건 BFT.
Spiegelman, A., et al. (2022). Bullshark: DAG BFT 프로토콜을 실용화했습니다.
Flamini, A., et al. (2022). Cob: 임의의 값 집합을 위한 리더 없는 비잔틴 합의.
Danezis, G. 등. (2022). Narwhal 및 Tusk: DAG 기반 멤풀 및 효율적인 BFT 합의.
Müller, S., et al. (2022). Tangle 2.0: DAG 기반 확률적 합의 프로토콜.
Xue, J., et al. (2023). BigDipper: 미니 블록 집계를 통한 확장 가능한 비잔틴 장애 허용.
Niu, J., et al. (2023). EBFT: 무작위 제안을 사용한 효율적인 비잔틴 내결함성.
Morais, R., et al. (2023). Nero: DAG 시스템을 위한 결정적 리더 없는 BFT.
Gelashvili, R., et al. (2024). Jolteon 및 Ditto: 비동기 폴백을 사용하는 네트워크 적응형 효율적인 합의.
Castro, M., & Liskov, B. (1999). 실용적인 비잔틴 오류 허용성.
램포트, L. (2006). 패스트팩소스.
Moraru, I., Andersen, DG, & Kaminsky, M. (2013). EPaxos: 평등주의적 합의.
Zhang, I., et al. (2015). 일관성 없는 복제를 사용하여 일관성 있는 트랜잭션 구축.
Buchman, E., Kwon, J., & Milosevic, Z. (2018). BFT 합의에 대한 최신 소문.
Bonniot, L., et al. (2019). PnyxDB: 최종 일관성을 갖춘 비잔틴 내결함성 데이터베이스.
Guo, S., et al. (2020). Dumbo: 더 빠른 비동기 BFT 프로토콜.
Qin, T. (2020). 리더 없는 비잔틴 장애 허용.
Niu, J., et al. (2020). 리더 없는 비잔틴 내결함성 합의.
Tollman, S., et al. (2021). EPaxos 재검토.
Du, H., et al. (2021). 프라이빗 체인에서 밀리초 단위 합의를 위한 리더 확인 복제.
Wang, X., et al. (2022). 노드 평판 기반의 계층적 비잔틴 내결함성 프로토콜.
Lu, H., et al. (2023). Aurora: 고처리량 리더리스 컨센서스.
Lu, H., et al. (2023). Arena: 다중 리더 동기식 비잔틴 장애 허용.
Dwork, C., Lynch, N., & Stockmeyer, L. (1988). 부분적 동기화가 존재하는 경우의 합의.
Abraham, I., et al. (2018). 최적의 복원력과 효율성을 갖춘 검증된 비동기 비잔틴 합의.
Kleppmann, M. (2020). 비잔틴 최종 일관성과 P2P 데이터베이스의 한계.
Wang, G. (2021). SoK: 블록체인 시대의 BFT 합의 이해.
Stathakopoulou, C., et al. (2022). 상태 머신 복제 확장성을 간소화합니다.
Zhang, Q., et al. (2023). 비잔틴 제국에서의 합의 도달: BFT 알고리즘에 대한 종합적인 검토.
