기술 요약: 빠르고 결정론적으로 안전한 작업 증명(Proof-of-Work) 합의

문제 정의

허가 없는(Permissionless) 블록체인은 보안 보장과 성능 사이의 근본적인 트레이드오프에 직면해 있습니다. 기존 프로토콜은 일반적으로 두 가지 범주로 나뉘며, 둘 다 특정 취약점을 가지고 있습니다:

• PoS 취약점: PoS 프로토콜은 **롱 레인지 공격(long-range attacks)**에 취약합니다. 공격자는 과거의 키를 구매하여 저렴한 비용으로 대안적인 실행 이력을 조작할 수 있습니다. 이를 방어하기 위해서는 일반적으로 외부 메커니즘(예: 사회적 합의 또는 보안 체크포인트)이 필요한데, 이는 시스템의 자기 완결적(self-contained) 특성을 저해합니다.
• PoW 취약점: 전통적인 PoW 프로토콜(예: 비트코인)은 롱 레인지 공격은 피하지만 확률적 안전성 보장에 의존합니다. 이는 공격자가 성공적으로 대안적인 이력을 생성할 가능성을 열어둡니다. 또한, PoW에서 결정론적 안전성을 달하는 것은 역사적으로 매우 느린 프로토콜(예: 지수적 지연 시간)을 초래하거나 제한적인 모델을 요구해 왔습니다.

이 논문이 다루는 핵심 과제는 **"타임 트래블 공격(time-travel attack)"**입니다. 완전히 허가 없는 환경에서, 동적 가용성(dynamically available)을 지원하는 프로토콜은 쿼럼 교차(quorum intersection) 논리에 의존합니다. 그러나 허가 없는 환경에서는 비잔틴 노드들이 먼 과거의 메시지를 생성하여 저장한 뒤, 나중에 이를 방출함으로써 현재 시점의 정당한 노드들의 쿼럼을 왜곡할 수 있습니다. 이러한 "타임 트래블"은 표준적인 쿼럼 교차 논리를 무효화하며, 외부 신뢰 가설 없이는 동적 가용 프로토콜을 불안전하게 만듭니다.

방법론: Sieve-MMR

저자들은 Sieve-MMR을 제안합니다. 이는 외부 메커니즘에 의존하지 않고 결정론적 안전성과 **상수 기대 지연 시간(constant expected latency)**을 달성하는 최초의 완전한 허가 없는 작업 증명 기반 총 순서 브로드캐스트(Total-Order Broadcast, TOB) 프로토콜입니다. 이 시스템은 두 개의 뚜렷한 계층으로 구성됩니다:

1. 하위 계층: Sieve 및 TTRB

주요 기술적 기여는 새로운 브로드캐스트 프리미티브인 **시간 여행 탄력적 브로드캐스트(Time-Travel-Resilient Broadcast, TTRB)**를 구현하는 새로운 알고리즘인 Sieve입니다.

• 목표: TTRB는 전달된 메시지가 바로 이전 라운드에서 생성되었음을 보장하여, "고물(antique)" 메시지(시간 여행하는 메시지)를 걸러냅니다.
• 메커니즘: Sieve는 결정론적 작업 증명(DPoW) 프리미티브를 활용합니다. 메시지를 정점으로 하고, 메시지들이 이전 라운드의 메시지 집합인 "코퍼(coffers)"에 포함되는 것을 엣지로 하는 DPoW 평가의 유향 비순환 그래프(DAG)를 구축합니다.
• 필터링 정책: Sieve는 DAG를 프루닝(pruning)하고 유효한 메시지를 식별하기 위해 두 가지 필터링 전략을 사용합니다:
  • Online-Sieve: 이전 단계에서 활성화되었던 노드들이 사용합니다. 이는 메시지의 코퍼와 두 단계 전의 유효 메시지 집합 사이의 교집합이 가중 임계값($1-\rho$)을 초과하는지 확인함으로써 효율적으로 메시지를 필터링합니다.
  • Bootstrap-Sieve: 시스템에 새로 참여하거나 비활성 상태에서 복구하는 노드들이 사용합니다. 이 방식은 전체 DAG 이력을 분석하는 더 고도의 계산 집약적인 작업을 수행하여, 노드가 자신의 쿼럼 뷰를 혼란스럽게 할 수 있는 고물 메시지를 수락하지 않도록 이전 단계의 유효 메시지 집합을 재구성합니다.
• 가정: Sieve는 동기식 네트워크를 가정하며, 공격자가 충분히 긴 구간 동안 전체 DPoW 계산 능력의 절반 미만($\rho \le 1/2$)을 통제한다고 가정합니다.

2. 상위 계층: MMR

합의 로직은 "동적 가용성" 모델을 위해 설계된 빠르고 결정론적으로 안전한 PoS 프로토콜인 MMR 프로토콜(Malkhi 등)에서 파생되었습니다.

• 통합: Sieve 위에 MMR을 계층화함으로써, 저자들은 합의 로직을 허가 없는 참여 로직으로부터 분리합니다. Sieve는 MMR이 쿼럼 교차를 유지하기 위해 필요로 하는 메시지 전달 보장(TTRB)을 제공합니다.
• 리더 선출: Sieve-MMR은 DPoW 랜덤 오라클을 기반으로 한 확률적 리더 선출 구성 요소를 사용하여 각 단계에서 어떤 체인에 투표하거나 커밋할지를 결정합니다.

주요 기여

1. 시간 여행 탄력적 브로드캐스트 (TTRB): 메시지가 현재 라운드와 인과적으로 일치하도록 보장하여 타임 트래블 공격에 면역력을 가진 새로운 브로드캐스트 추상화를 제공합니다.
2. Sieve 알고리즘: 블랙박스 DPoW 프리미티브를 사용하여 TTRB를 구현하는 새로운 프로토콜입니다. 이는 "코퍼(coffers)"라는 개념과 DAG 기반 프루닝을 도입하여 현재 메시지와 고물 메시지를 구별합니다.
3. Sieve-MMR 프로토콜: 다음을 달성하는 최초의 완전한 허가 없는 TOB 프로토콜입니다:
   • 결정론적 안전성: (Dolev-Yao 모델 내에서) 안전성에 대한 확률적 실패 모드가 없습니다.
   • 상수 기대 지연 시간: 트랜잭션은 상수 횟수의 단계(기대값 7단계, 최선 3단계) 내에 커밋됩니다.
   • 외부 신뢰 불필요: 롱 레인지 공격을 방지하기 위해 사회적 합의나 외부 체크포인트에 의존하지 않습니다.

결과 및 보장

• 안전성: Sieve-MMR은 일관성(모든 정당한 노드가 호환 가능한 체인을 커밋함)과 진행(체인이 결국 성장함)을 보장합니다. Sieve-MMR은 합의 계층에서 $1/3$ 제한 공격자를 견디는 MMR의 능력을 상속받는 한편, Sieve 자체는 메시징 계층에서 $1/2$ 제한 공격자를 견딜 수 있습니다.
• 지연 시간: 프로토콜은 상수 기대 지연 시간을 달성하며, 이는 참여자 수에 따라 지수적 지연 시간을 겪었던 이전의 결정론적 PoW 프로토콜들에 비해 상당한 개선입니다.
• 보안 모델: 보안 주장은 공격자가 암호화 프리미티브를 깨거나 메시지를 예측할 수 없다는 Dolev-Yao 스타일의 모델 내에서 유효합니다. 프로토콜은 동기식 네트워크를 가정하며, 참여 노드 수에 대해 이차(quadratic)적인 대역폭 비용을 발생시키는 전방향(all-to-all) 브로드캐스트를 사용합니다.

의의 및 한계

이 논문은 Sieve-MMR을 실질적이고 빠르며 안전한 PoW 합의를 향한 중요한 이론적 진전으로 자리매김합니다. 이는 이전에 허가 없는 설정으로 저지연 합의를 이식하는 데 있어 근본적인 장벽으로 여겨졌던 "타임 트래블" 취약점이 Sieve 메커니즘을 통해 완화될 수 있음을 입증합니다.

그러나 저자들은 즉각적인 실무 배포와 관련하여 몇 가지 장애물을 언급하며 신중한 태도를 보였습니다:

• 계산 복잡도: Bootstrap-Sieve 단계는 프로토콜의 실행 이력에 대해 지수 시간 문제를 해결해야 합니다. 노드들이 이를 정해진 시간 내에 완료해야 하는 것은 아니지만, 활발한 참여를 하기 전에 반드시 완료해야 하므로 새로운 노드에게는 큰 장벽이 됩니다.
• 네트워크 가정: 프로토콜은 동기식 네트워크와 전방향 통신을 가정하며, 이는 실제 비동기 인터넷 환경에서 효율적으로 확장되지 않을 수 있습니다.
• 검증 오버헤드: 모든 메시지에 대한 DPoW 평가를 검증하는 것은 계산 비용이 많이 들 수 있으나, 저자들은 배치 검증(batch verification) 및 영지식 증명(zero-knowledge proofs)과 같은 암호학적 최적화가 향후 해결책이 될 수 있다고 제안합니다.

결론적으로, Sieve-MMR은 동적 가용 모델과 완전한 허가 없는 모델 사이의 이론적 가교를 제공하며, 계산 및 네트워크 제약 조건이 해결된다면 외부 신뢰 없이도 결정론적 안전성과 상수 지연 시간을 달리는 것이 가능하다는 것을 보여줍니다.