기술 요약: BigDipper

문제 정의

리더 기반 비잔틴 장애 허용(BFT) 프로토콜은 낮은 지연 시간과 단순한 통신 구조 덕분에 프로덕션 블록체인 시스템에서 지배적으로 사용됩니다. 그러나 이들은 리더에게 트랜잭션 포함에 대한 단기적인 제어권을 부여합니다. 악의적인 리더는 프로토콜을 활성 상태로 유지(liveness 보장)하면서도, 경매 입찰, 오라클 업데이트, 청산, 브릿지 메시지와 같이 시간에 민감한 트랜잭션을 선택적으로 지연시키거나 제외할 수 있습니다. 이러한 현상은 **단기 검열(short-term censorship)**이라 불리며, 표준 BFT의 활성 보장(liveness guarantees)으로는 포착되지 않습니다.

기존 솔루션들은 강력한 안티-검열, 은닉 또는 순서 지정 메커니즘을 합의 경로에 하드코딩합니다. 이러한 접근 방식은 특정 사용 사례에는 효과적이지만, 특정 트랜잭션이 그러한 견고성을 필요로 하는지 여부와 관계없이 모든 트랜잭션에 동일하게 높은 비용을 지불하게 만듭니다. 본 논문은 **종단 간 원칙(end-to-end principle)**을 준수하는 더 모듈화된 설계를 제안합니다. 즉, 합의 계층은 안전한 순서 지정 및 데이터 가용성을 위한 최소한의 프리미티브(primitives)만을 노출하고, 검열 저항 전략과 그에 따른 비용의 선택은 상위 계층 애플리케이션에 맡겨야 한다는 것입니다.

방법론

BigDipper는 트랜잭션 제출과 리더 기반 BFT 합의 사이에 위치하는 검열 저항적 데이터 가용성(DA-CR) 계층을 도입합니다. 이 시스템은 세 가지 핵심 구성 요소를 중심으로 설계되었습니다:

1. DA-CR 추상화: 레플리카(replica)들이 미니 블록을 기여하는 계층이며, 어떤 데이터가 가용하며 리더가 반드시 캡처해야 하는지를 인증하는 메커니즘입니다. 이 계층은 파라미터 $(t, \eta)$로 특징지어지는데, 여기서 $t$는 정직한 미니 블록의 보장된 포함을 나타내고, $\eta$는 리더의 잔여 공간 캡처 능력(데이터 제외 능력)을 나타냅니다.
2. 샤딩된 합의 크리티컬 패스(Sharded Consensus Critical Path): 검증자들이 전체 블록 페이로드를 다운로드하고 실행해야 하는 전통적인 설계와 달리, BigDipper는 크리티컬 패스 상에서 데이터를 샤딩된 상태로 유지합니다. 검증자들은 전체 페이로드를 재구성하는 대신, 컴팩트한 커밋먼트(commitment), 가용성 증거, 그리고 DA-CR 포함 규칙을 바탕으로 투표합니다.
3. 클라이언트 튜너블 제출(Navigator): 클라이언트가 $x$개의 서로 다른 레플리카로 트랜잭션을 보내는 팬아웃(fanout) 파라미터 $x$를 선택하는 트랜잭션 전파 프로토콜입니다. 이를 통해 클라이언트는 통신 비용과 신속한 포함 확률 사이의 절충안을 선택할 수 있습니다.

핵심 구성 요소

본 논문은 리드-솔로몬(Reed-Solomon, RS) 에러 코딩과 **선형 다항식 커밋먼트(KZG)**를 기반으로 한 구체적인 DA-CR 구성을 제시합니다:

• Card-7: 리더가 포함된 미니 블록에 대한 증명(attestation)을 제공해야 하는 책임 있는(accountable) 프로토콜입니다. 이는 $t = n - 2f$개의 정직한 미니 블록이 포함됨을 보장하며, $\eta = 0$(공간 캡처 불가)을 보장합니다. 이를 위해 $n \ge 3f + 1$이 필요합니다.
• Card-1/4: 오버헤드가 낮은 비책임(non-accountable) 변형입니다. 리더가 어떤 레플리카가 포함되었는지 숨길 수 있도록 공개 증명 요구 사항을 제거합니다. 이는 $t = n - 3f$ 및 $\eta = n - f - 1$을 달성하며, $n \ge 4f + 1$이라는 더 강한 가정을 필요로 합니다.
• Card-Lite: 이중 동형 커밋먼트 스킴(doubly homomorphic commitment scheme)을 사용하여 Card-7을 최적화한 버전입니다. 전체 리스트를 전송하는 대신 커밋먼트를 샘플링함으로써 레플리카당 오버헤드를 $O(\log n)$으로 줄이면서도 $t \approx n - 2f$를 유지합니다.

HotStuff-2와의 통합

BigDipper는 HotStuff-2 내에 구현됩니다. 이 통합은 Scooping rule을 유효성 판별식(validity predicate)으로 도입하는 정교한 방식으로 이루어집니다. 리더의 제안은 완료된 DA-CR 출력(데이터 가용성 및 필수 미니 블록 포함을 증명하는 인증서)을 포함해야만 유효합니다. 이는 HotStuff-2의 안전성 핵심을 변경하지 않으면서, 리더가 요구되는 레플리카 기여 데이터를 캡처하지 않고는 진행할 수 없도록 방지합니다.

주요 기여

1. 단기 검열 저항을 위한 모듈형 추상화: 데이터 가용성을 특정 검열 정책으로부터 분리하는 DA-CR을 도입했습니다. 이는 데이터 가용성 메커니즘을 데이터 포함 보장($t$)과 리더의 영향력($\eta$) 사이의 트레이드오프를 공식화합니다.
2. 샤딩된 확장 가능한 데이터 경로: 일반 검증자들이 투표를 위해 전체 블록 페이로드를 다운로드할 필요가 없는 설계입니다. 검증자들은 커밋먼트와 메타데이터를 검증하며, 이를 통해 총 제안 대역폭이 단일 리더의 입력 대역폭에 제한되지 않고 레플리카 측의 데이터 기여량에 따라 확장될 수 있게 합니다.
3. 클라이언트 튜너블 검열 저항성: Navigator 프로토콜은 클라이언트가 팬아웃을 늘림으로써 포함 확률을 증폭할 수 있게 합니다. 본 논문은 유니언 바운드(union-bound) 논증을 통해, 제출된 트랜잭션 수와 레플리카 수가 증가함에 따라 광범위한 검열이 기하급수적으로 어려워짐을 증명하며 비용/보안 트레이드오프를 분석합니다.
4. 구체적인 통합 및 분석: HotStuff-2 내부에 BigDipper를 완전히 구현하여, DA-CR이 안전성과 활성을 해치지 않으면서 기존 리더 기반 BFT 프로토콜에 정밀하게 연결될 수 있음을 입증했습니다.

결과 및 분석

• 검열 저항성: 분석 결과, 악의적인 리더가 소수의 레플리카로 전송된 트랜잭션은 검열할 수 있지만, 대규모의 트랜잭션을 검열하는 것은 시스템 규모가 커짐에 따라 기하급수적으로 어려워짐을 보여줍니다. 구체적으로, $T$명의 클라이언트가 각각 $x$개의 복사본을 보낼 경우, 적대자가 $\alpha$ 비율의 트랜잭션을 검열할 확률은 $T$가 증가함에 따라 지수적으로 감소합니다.
• 확장성: 합의와 전체 데이터 실행을 분리함으로써, BigDipper는 합의 계층이 레플리카의 총 대역폭에 따라 선형적으로 확장될 수 있도록 합니다. 시스템 용량은 모든 검증자가 전체 페이로드를 처리해야 하는 병목 현상에 의해 제한되지 않습니다.
• 성능: Card-7 프로토콜은 새로운 단계를 추가하지 않고 기존 HotStuff-2의 메시지 스케줄(Propose, Vote, Prepare, Vote2) 내에 부합하며, DA-CR 메시지(Collection, Dispersal, Approval, Agreement)를 표준 BFT 메시지에 실어 보냄(piggybacking)으로써 동작합니다.

의의

본 논문은 BigDipper가 기존 프로토콜의 "일률적인(one-size-fits-all)" 비용을 피하면서 단기 검열 저항성을 위한 모듈형 프레임워크를 제공한다고 주장합니다. 종단 간 원칙을 따름으로써, 애플리케이션이 레이턴시 및 포함 보장에 대한 경제적 요구에 따라 자신만의 제출 전략(예: 접촉할 레플리카 수, 에러 코딩 사용 여부)을 선택할 수 있게 합니다.

이 논문의 의의는 검열 저항의 부담을 고정된 프로토콜 비용에서 튜닝 가능한 클라이언트 측 파라미터로 전환하는 데 있으며, 동시에 합의 계층이 효율적이고 샤딩된 상태를 유지하도록 보장하는 데 있습니다. 이는 리더 기반 BFT가 전체 복제가 아닌 샤딩된 커밋먼트 기반 메커니즘을 통해 데이터 가용성을 인증받는다면, 리더 기반 모델의 저지연 이점을 희생하지 않고도 검열 저항성을 갖출 수 있음을 보여줍니다.