A Model for Fast Mining Blockchains

기술 요약: 빠른 채굴 블록체인을 위한 모델

문제 제기
본 논문은 블록을 채굴하는 데 소요되는 시간이 네트워크 전체에 블록을 전파하는 데 필요한 지연 시간과 유사한 수준인 "빠른 채굴(fast mining)" 체제에서의 블록체인 채굴 역학을 조사한다. 전통적인 "느린 채굴(slow mining)" 모델에서는 새로운 블록이 네트워크에 완전히 동기화되기 전에 한 브랜치에서 새로운 블록이 채굴될 가능성이 높기 때문에 포크(분기)가 일반적으로 빠르게 해결된다. 그러나 빠른 채굴 시나리오에서는 전파가 진행되는 동안 서로 다른 브랜치에서 여러 블록이 동시에 채굴될 수 있으며, 이로 인해 광부들이 결코 동일한 로컬 블록체인을 보유하지 못할 수도 있는 복잡한 상태가 발생한다. 핵심 질문은 합의가 이루어지는지, 블록체인 높이의 분포가 어떻게 진화하는지, 그리고 광부의 수($N$)가 무한대($\infty$)로 접근할 때 시스템의 점근적 행동은 어떠한가 하는 것이다.

방법론
저자들은 $N$명의 광부로 구성된 네트워크를 위한 연속 시간 마르코프 연쇄(CTMC) 모델을 구축한다.

1. 상태 공간: 상태는 각 광부의 로컬 블록체인 높이 벡터로 정의된다. 전이는 두 가지 메커니즘을 통해 발생한다:
   • 채굴: 광부가 비율 $\lambda$로 새로운 블록을 발견하여 로컬 높이를 증가시킨다.
   • 전파: 광부들이 자신의 로컬 블록체인을 타인에게 전달하는 비율은 $\omega$이다. 수신된 체인이 유효하고 높이가 더 높은 경우, 수신된 광부는 자신의 로컬 체인을 업데이트한다.
2. 유한 $N$ 분석: 저자들은 먼저 임의의 유한한 $N$에 대해 시스템이 양의 재귀적(positive recurrent)임을 증명한다. 즉, 초기 분기 상태와 관계없이 유한한 기대 시간 내에 합의(모든 광부가 동일한 블록체인을 보유함)에 도달한다.
3. 무한 극한 ($N \to \infty$): 거시적 행동을 분석하기 위해, 저자들은 Barbour와 Luczak(2008)의 연구를 바탕으로 기능적 대수의 법칙(FLLN)을 채택한다. 저자들은 높이가 $n$보다 작거나 같은 블록체인을 가진 광부의 비율을 나타내는 경험적 분포 함수 $\phi_n(t)$를 정의한다.
4. 점근적 분석: 정의된 분포는 결정론적 결합 상미분 방정식(ODE) 체계를 만족한다. 저자들은 다음을 사용하여 이 시스템을 분석한다:
   • 이동 좌표계(Comoving Frames): 이동 파형 프로파일을 연구하기 위해, 특정 레벨 셋 $p \in (0,1)$을 고정하고 시간 좌표를 이동시켜 변위 드리프트를 제거한다.
   • 점근적 논증: Brunet과 Derrida(1997) 및 Bramson(1980년대)의 연구에서 영감을 얻어 파동 속도에 대한 보정치를 도출한다.
   • 연속체 근사(Continuum Approximation): 이산 차분 방정식을 드리프트가 있는 편미분 방정식(Fisher-KPP)으로 근사하고, 특정 매개변수 영역에서 명시적인 해석적 해를 찾기 위해 Painlevé 적분성 결과(Ablowitz와 Zeppetella, 1979)를 활용한다.

주요 기여 및 결과

1. 합의 역학:

   • 명제 1: 유한한 수의 광부 $N$에 대해, 합의 상태는 양의 재귀적이다. 높은 전파 지연이 있더라도 시스템은 유한한 기대 시간 내에 합의 상태로 돌아온다.
   • 기능적 대수의 법칙: $N \to \infty$ 극한에서, 확률 과정은 다음과 같은 ODE 시스템(식 3.12)을 만족하는 결정론적 프로파일로 수렴한다:
     $$\dot{\phi}_n(t) = -\lambda(\phi_n - \phi_{n-1}) - \omega\phi_n(1 - \phi_n)$$
     단, 경계 조건은 $\phi_{-1} \equiv 0$이다.

2. 이동 파형(Traveling Wave)으로의 수렴:

   • 정리 12: ODE 시스템의 해들의 수열은 이동 좌표계 내에서 비자명한(non-trivial) 극한 프로파일로 균등하게 수렴한다. 이 프로파일은 경계값 문제에 의해 형태가 정의되는 이동 파형이다.
   • 파동 속도는 선택된 레벨 $p$와 무관한 특정 레벨 셋의 히팅 시간(inter-hitting time) $\tau$에 의해 결정된다.

3. 파동 속도 및 로그 보정:

   • 최소 속도: 이동 파형은 선단(leading edge)에서의 계를 선형화하여 결정된 최소 속도 $v_0$로 전파된다.
   • Bramson 보정: 무한한 광부 극한에서, 전면(front)의 위치 $X_t$는 시간에 따른 주요 로그 보정을 나타낸다:
     $$X_t \sim v_0 t - \frac{3}{2\gamma_0} \log t$$
     여기서 $\gamma_0$는 파동 꼬리의 감쇠율이다.
   • Brunet-Derrida 보정: 유한한 수의 광부 $N$에 대해, 이동 파형 속도 $v_N$은 $N$의 로그의 역제곱에 비례하는 보정항을 가지며 무한 극한 $v_0$로 수렴한다:
     $$v_0 - v_N \sim \frac{C}{(\log N)^2}$$
     이 결과는 절단(cut-off) 수정된 Fisher-KPP 시스템에서 관찰되는 Brunet-Derrida 행동과 일치한다.

4. 프로파일의 해석적 근사:

   • 이산 시스템을 드리프트가 있는 연속 Fisher-KPP 방정식으로 매핑함으로써, 저자들은 특정 매개변수 비율 $\omega/\lambda \approx 0.00781$에서 시스템이 Painlevé 적분 가능한 이동 파형 해를 허용함을 확인한다.
   • 명제 28: Ablowitz와 Zeppetella(1979)에 의해 도출된 특정 해석적 해는 블록체인 모델의 극한 프로파일과 정확히 일치한다. 수치 시뮬레이션은 이 해석적 해와 이산 ODE의 수치해 사이의 강력한 적합성을 확인해 준다.

의의 및 주장
본 논문은 휴리스틱 모델을 넘어 빠른 채굴 블록체인을 이해하기 위한 엄밀한 수학적 프레임워크를 제공한다고 주장한다.

• 빠른 채굴에서도 합의가 즉각적이지는 않지만, 시스템은 안정적이며 유한한 $N$에 대해 유한한 기대 시간 내에 합의 상태로 수렴함을 확립한다.
• 무한 극한에서의 블록체인 헤드의 "모호함(fuzziness)"을 특정 형태와 속도를 가진 이동 파형으로 규명한다.
• 유한한 네트워크에서의 전파 속도가 무한 극한보다 $(\log N)^{-2}$ 인자로 느리다는 것을 보여줌으로써 유한 크기 효과를 정량화한다.
• 본 연구는 이산 확률 과정(블록체인 채굴)을 연속 반응-확산 방정식(Fisher-KPP)과 연결하며, 명시적인 파동 속도 및 프로파일 형태를 도출하기 위해 고급 점근 기술(Bramson, Brunet-Derrida)과 적분계 이론(Painlevé)을 활용한다.

저자들은 수치 시뮬레이션을 통해 시간 및 광부 수에 따른 로그 보정과 Painlevé 기반 해석적 근사의 정확성을 검증함으로써 이러한 이론적 발견을 뒷받침한다.