근사 합의를 통한 분산 난수 생성: 비동기 비잔틴 장애 허용 프로토콜

1 서론

난수화는 분산 시스템 설계에서 중요한 도구입니다. 시스템 구성원들이 예측 불가능한 난수에 합의할 수 있게 하는 공통 코인 기본 요소는 비잔틴 합의, 분산 키 생성, 리더 선출과 같은 프로토콜에 특히 유용하게 입증되었습니다. 그러나 FLP 불가능성 결과로 인해 결함이 발생할 수 있는 비동기 시스템에서 진정한 무작위 공통 코인 프로토콜을 구현하는 것은 불가능합니다.

본 논문은 완벽한 공통 코인의 두 가지 완화된 형태를 소개합니다: (1) 서로 가까운 난수를 생성하는 근사 공통 코인과 (2) 임의로 작지만 0이 아닌 실패 확률로 공통 난수를 생성하는 몬테카를로 공통 코인입니다. 우리의 프로토콜은 근사 합의 기본 요소 위에 구축되며, 신뢰 기반 설정이나 공개 키 인프라 없이 최대 1/3의 비잔틴 프로세스를 허용합니다.

2 배경 및 관련 연구

3 프로토콜 설계

4 기술적 분석

5 실험 결과

우리는 다양한 프로세스 수(n = 10~100)와 비잔틴 장애율(f < n/3)을 가진 시뮬레이션된 비동기 네트워크에서 우리의 프로토콜을 평가했습니다. 결과는 다음과 같음을 보여줍니다:

• 일반적인 매개변수에 대해 5-10 라운드 내에서 합의로의 기하급수적 수렴
• 이진 비잔틴 합의에 대한 O(n³log n) 통신 복잡도
• 이전 O(n⁴) 솔루션 대비 상당한 개선

다음 의사 코드는 핵심 근사 합의 라운드를 설명합니다:

function ApproximateAgreementRound(value, round):
    broadcast("PROPOSE", value, round)
    received = wait_for_messages(n - f, round)
    valid_values = filter_within_range(received, value - ε, value + ε)
    new_value = median(valid_values)  // 또는 연속 도메인에 대한 평균
    return new_value

6 구현 상세

우리의 구현은 해시 함수와 디지털 서명을 포함한 표준 암호학적 기본 요소를 사용합니다. 핵심 알고리즘 구조:

class MonteCarloCommonCoin:
    def __init__(self, n, f, delta):
        self.n = n  # 전체 프로세스
        self.f = f  # 최대 비잔틴 장애
        self.delta = delta  # 실패 확률
        self.round = 0
        
    def generate_coin(self):
        while True:
            self.round += 1
            estimate = self.approximate_agreement_round()
            if self.consensus_achieved(estimate):
                return self.finalize_output(estimate)
            if self.round > self.required_rounds():
                return self.fallback_output()

7 응용 및 향후 방향

현재 응용 분야:

• O(n³log n) 통신 복잡도를 가진 비잔틴 합의
• 그레이 코드를 사용한 근사 공통 코인을 이용한 교차 무작위 부분집합 문제
• 무허가 블록체인 시스템에서의 리더 선출

향후 연구 방향:

• 양자 내성 암호화를 위한 프로토콜 적응
• 동적 멤버십 설정으로의 확장
• 부분적 동기성을 가진 실제 네트워크 조건에 대한 최적화
• 샤딩된 블록체인 아키텍처와의 통합

8 참고문헌

1. Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM.
2. Rabin, M. O. (1983). Randomized Byzantine generals. Symposium on Foundations of Computer Science.
3. Cachin, C., Kursawe, K., & Shoup, V. (2000). Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography. PODC.
4. Miller, A., Xia, Y., Croman, K., Shi, E., & Song, D. (2016). The honey badger of BFT protocols. CCS.
5. Abraham, I., Malkhi, D., & Spiegelman, A. (2019). Asymptotically optimal validated asynchronous Byzantine agreement. PODC.