기술 요약: BFT 합의용 거리 보존 다이제스트

1. 문제 제기

HotStuff, PBFT, Ethereum 2.0 을 포함한 비잔틴 장애 허용 (BFT) 합의 프로토콜은 검증자 상태를 비교하기 위해 충돌 저항성 해시 (예: SHA-256) 에 의존합니다. 위조 방지에 효과적이지만, 이 접근법은 '거리' 정보를 파괴합니다. 두 검증자가 20 개 거래 중 19 개에 동의하더라도, 그들의 해시는 완전히 무관하며 거래를 공유하지 않는 검증자와 구별할 수 없습니다. 이 한계는 BFT 문헌에 세 가지 구조적 제약을 부과합니다:

1. 강제적 상태 동기화: 해시는 부분적 합의를 측정할 수 없으므로, 검증자는 투표 전에 상태를 완전히 동기화해야 합니다.
2. 측정 불가능한 합의 품질: 프로토콜은 모든 투표 라운드가 완료될 때까지 만장일치 합의를 감지할 수 없으므로, 이상적인 조건에서도 고정된 다중 라운드 지연을 강요합니다.
3. 대규모 계층적 위원회: 트리 구조 합의에서 안전성을 보장하기 위해, 리프 그룹은 독립적으로 $2N/3$ 비잔틴 허용 임계값을 충족할 만큼 충분히 커야 합니다 (예: 이더리움의 128 명 검증자). 이는 트리 깊이와 확장성을 제한합니다.

2. 방법론: 거리 보존 다이제스트

본 논문은 상태 비교를 위해 충돌 저항성 해시를 대체하는 거리 보존 다이제스트 (Distance-Preserving Digests) 라는 원시적 요소를 도입합니다. 구성 과정은 다음과 같습니다:

• 벡터화: 각 거래는 SHA-512 로 해시됩니다. 64 바이트 출력은 8 개 세그먼트로 분할됩니다.
• 좌표 매핑: 각 세그먼트는 부호 없는 정수로 간주되어 10,000 으로 나눈 나머지 (mod 10,000) 를 취한 후 10,000 으로 나누어 $[0, 1)$ 범위의 좌표를 생성합니다.
• 가환 합산: 검증자의 거래 집합 $T$에 대한 다이제스트는 8 차원 공간에서의 벡터 합 $D(T) = \sum_{tx \in T} v(tx)$ 입니다.

이 원시적 요소는 해시가 lacking 하는 세 가지 속성을 갖습니다:

1. 비례 거리: 두 다이제스트 간의 유클리드 거리는 서로 다른 거래 수에 비례합니다.
2. 정확한 요약: 다이제스트 그룹의 가중 평균은 그룹의 집계 상태를 정확히 나타내므로, 정보 손실 없이 검증자 그룹을 단일 압축 값 (76 바이트) 으로 요약할 수 있습니다.
3. 집합 차이 식별: 다이제스트가 다를 때, 불린 필터 차이를 통해 집계기가 검증자의 뷰에서 누락된 정확한 거래를 식별할 수 있어, 전체 상태 교환 없이 표적 동기화가 가능합니다.

3. 주요 기여 및 응용

본 논문은 Proxima라는 새로운 프로토콜 내에서 이 원시적 요소의 세 가지 주요 응용을 입증합니다:

A. 2 단계 BFT 프로토콜 (Proxima)

Proxima 는 두 단계로 운영됩니다:

• 1 단계 (거리 필터링): 검증자가 다이제스트와 불린 필터를 집계기에 전송합니다. 집계기는 거리 임계값 내에서 검증자를 클러스터링합니다. 클러스터 분산이 거의 0 에 가까울 경우 (높은 합의 표시), 프로토콜은 단일 라운드 최종성 증명서를 발행합니다 (빠른 경로). 그렇지 않으면 불린 차이를 통해 누락된 거래를 푸시합니다.
• 2 단계 (약속): 클러스터 구성원은 BLS 서명을 사용하여 블록 해시에 서명합니다. 집계기는 집계된 서명을 생성합니다.
• 결과: 합의 여부와 관계없이 3 라운드가 필요한 HotStuff 와 달리, Proxima 는 검증자들이 합의할 때 단일 라운드 최종성을 달성합니다.

B. 소규모 그룹을 활용한 트리 구조 합의

거리 필터링은 그룹 수준의 BFT 를 요구하지 않고 개인 수준에서 작동하므로, Proxima 는 소규모 그룹 (예: 10 명 검증자) 을 통한 계층적 합의를 가능하게 합니다.

• 메커니즘: 리프 리더는 기준에서 멀리 떨어진 비잔틴 검증자를 필터링하고 정직한 검증자의 가중 평균을 보고합니다.
• 결과: 이는 안전성을 보장하기 위한 대규모 위원회 (128 명 검증자) 의 필요성을 제거하여 더 깊은 트리 (2~3 단계 대비 5 단계) 를 허용하고 메시지 복잡성을 줄입니다.

C. 크로스-샤드 일관성 검증

다이제스트는 샤드 간 일정한 비용의 검증을 가능하게 합니다.

• 메커니즘: 인접한 샤드들은 중첩 영역 거래의 다이제스트를 교환합니다. 거리가 0 이면 상태가 일치합니다. 0 이 아니면 불린 차이가 특정 분기 거래를 식별하여 해결합니다.
• 결과: 이는 2 단계 커밋 (2PC) 또는 영수증 체인의 거래별 조정을 대체하여, 95% 전파율에서 2PC 대비 크로스-샤드 오버헤드를 99% 줄입니다.

4. 결과 및 평가

본 논문은 $N=100,000$ 검증자와 30% 비잔틴 장애를 시뮬레이션하여 Proxima 를 HotStuff, PBFT, 이더리움의 위원회 구조와 비교 평가합니다.

• 메시지 복잡성: Proxima Tree 는 HotStuff 보다 2.2 배 적은 메시지를 사용합니다. 이는 병렬화의 영향을 받지 않는 구조적 속성으로, 2 단계 실행, 비잔틴 노드의 사전 필터링, 그리고 압축 요약을 통한 트리 라우팅에서 비롯됩니다.
• 지연 시간:
  • 싱글 코어: Proxima 는 HotStuff 의 약 18 초 대비 약 0.9 초 (902 ms) 에 단일 코어 최종성을 달성합니다. 트리 구조는 BLS 집계를 분산시켜 임계 경로 처리를 낮게 유지합니다 (9.9 ms).
  • 멀티 코어: 멀티 코어 BLS 집계가 격차를 좁히지만 (HotStuff 는 약 940 ms 로 감소, Proxima Flat 은 약 220 ms), 리프 노드가 매우 적은 서명을 처리하므로 트리 구조는 임계 경로 BLS 시간에서 여전히 우위를 점합니다.
• 크로스-샤드 오버헤드: 95% 전파율에서 다이제스트 기반 검증은 2PC 보다 99% 적은 메시지, 영수증 기반 접근법 (NEAR Nightshade) 보다 95% 적은 메시지를 사용합니다.
• 안전성: 안전성은 1 단계 클러스터링과 무관하게 입증됩니다. $N/3$ 미만의 비잔틴 검증자는 충돌하는 최종화를 일으킬 수 없습니다. 1 단계는 정직한 검증자를 제외할 수 있을지라도 (활성화 위험), 이는 Hoeffding 부등식에 의해 무시할 수 있는 수준으로 제한됩니다 (실용적 $N$에서 $<10^{-9}$).

5. 중요성 및 주장

본 논문은 거리 보존 다이제스트가 BFT 에서 충돌 저항성 해시가 부과한 세 가지 근본적 제약을 제거한다고 주장합니다. 합의 품질의 측정을 가능하게 함으로써, 이 원시적 요소는 다음을 가능하게 합니다:

1. 낙관적 빠른 경로: 프로토콜은 합의가 높을 때 한 라운드에서 최종성을 달성할 수 있습니다.
2. 확장 가능한 계층 구조: 안전성이 그룹별 투표가 아닌 거리 필터링을 통해 유지되므로, 합의 트리는 소규모 그룹 (크기 10) 과 깊은 구조를 활용할 수 있습니다.
3. 효율적인 샤딩: 크로스-샤드 일관성은 샤드 쌍당 일정한 비용으로 검증될 수 있으며, 총 거래량이 아닌 실제 분기에 따라 확장됩니다.

저자들은 이 원시적 요소가 데이터 구조에서 지역 민감성 해싱 (LSH) 의 알려진 응용이지만, 비잔틴 합의에 적용된 것은 novelty 라고 강조합니다. 시스템의 안전성은 표준 암호학적 가정 (BLS 서명 및 SHA-512) 에 의존하며, 거리 필터는 안전 메커니즘이 아닌 활성화 및 최적화 메커니즘으로 작용합니다. 본 논문은 이 접근법이 해시를 통해 상태를 비교하는 모든 BFT 프로토콜에 일반적인 개선을 제공한다고 결론지었습니다.