Fluid limit of a distributed ledger model with random delay

이 논문은 배치 도착과 무작위 지연을 고려한 분산 원장 (DAG) 모델의 점근적 거동을 분석하여, 도착률이 무한대로 갈 때 잎 노드 수 및 기타 확률 변수가 지연 편미분 방정식으로 표현된 유체 극한으로 근사됨을 증명하고 안정 상태를 규명하며 시뮬레이션을 통해 검증했습니다.

핵심

🏛️ 1. 배경: 거대한 도서관과 미해결 과제

이 논문에서 다루는 시스템 (예: IOTA 같은 기술) 은 거대한 디지털 도서관과 같습니다.

• 책 (블록/거래): 도서관에 쌓이는 정보들입니다.
• 서가 (DAG): 책이 쌓이는 방향성 있는 구조입니다.
• 작업 증명 (POW): 책을 서가에 꽂기 전에, 도서관 사서가 **"이 책이 진짜인지 확인하는 복잡한 퍼즐"**을 풀어야 하는 규칙입니다.

문제 상황:
새로운 책 (거래) 이 도착하면, 사서 (사용자) 는 퍼즐을 풀어야만 책을 서가에 꽂을 수 있습니다. 퍼즐을 풀고 있는 동안, 그 책은 **'미해결 상태 (Pending)'**로 남아 있습니다. 퍼즐이 풀리면 비로소 **'완료된 상태 (Tip)'**가 되어 다른 책들이 그 위에 쌓일 수 있게 됩니다.

🌊 2. 연구의 핵심: "물 (Fluid)"로 예측하기

저자들은 이 시스템이 너무 복잡하고 무작위적이라서 하나하나 세는 것이 불가능하다고 생각했습니다. 그래서 **"유체 역학 (Fluid Limit)"**이라는 개념을 도입했습니다.

• 비유: 도서관에 책이 10 권 들어오면 하나하나 셀 수 있지만, 매초마다 수백만 권의 책이 쏟아져 들어오는 상황을 상상해 보세요.
  • 이때는 "책 1 권, 2 권"을 세는 대신, **"책이 흐르는 물의 양"**으로 생각하면 훨씬 쉽게 예측할 수 있습니다.
  • 마치 강물이 흐르는 속도와 양을 예측할 때, 물 분자 하나하나를 추적하지 않고 **물의 흐름 (유체)**을 보듯이요.

이 논문은 **"작업 증명 (POW) 을 푸는 시간이 사람마다 다르고 (랜덤), 여러 사람이 동시에 책을 가져오는 상황"**에서도 이 '물의 흐름'을 수학적으로 정확히 예측할 수 있는 공식을 찾아냈습니다.

🎲 3. 주요 발견: "기다리는 책"과 "안전한 책"

연구자들은 이 '물 흐름' 공식을 통해 두 가지 중요한 사실을 알아냈습니다.

① '미해결 책'의 수를 예측할 수 있다

• 상황: 퍼즐을 풀고 있는 책들이 너무 많으면, 새로운 책들이 그 위에 쌓일 수 없어 시스템이 느려집니다.
• 발견: 작업 증명에 걸리는 시간이 얼마나 오래 걸리는지 (평균 시간) 만 알면, **"언제쯤 도서관이 혼잡해지고, 언제쯤 여유로워질지"**를 정확히 계산할 수 있습니다.
• 비유: "오늘 점심시간에 식당에 손님이 얼마나 몰릴지, 요리사가 음식을 만드는 속도에 따라 예측할 수 있다"는 것과 같습니다.

② '위험도'를 분석할 수 있다

• 상황: 어떤 책은 퍼즐을 풀고 있는 지 1 분밖에 안 지났고, 어떤 책은 10 분이나 걸렸습니다.
• 발견: 시스템은 단순히 책의 수만 세는 게 아니라, **"어떤 책이 얼마나 오래 기다리고 있는지"**까지 세분화해서 분석했습니다.
• 의미: 이는 보안과 직결됩니다. "어떤 책이 아직 퍼즐을 풀지 않아서 해커가 조작하기 쉬운 상태인지"를 수치로 파악할 수 있게 된 것입니다.

📊 4. 결론: 시뮬레이션 없이도 미래를 본다

이 논문이 제안한 수학적 모델 (유체 한계) 은 다음과 같은 장점이 있습니다.

1. 컴퓨터 시뮬레이션 불필요: 실제로 수백만 번의 퍼즐을 풀고 결과를 보는 대신, 이 공식을 사용하면 순간적으로 시스템의 미래 상태를 예측할 수 있습니다.
2. 설계 최적화: "작업 증명 시간을 이렇게 줄이면 시스템이 얼마나 빨라질까?", "사용자가 동시에 얼마나 몰려도 버틸 수 있을까?"를 미리 계산하여 시스템을 더 안전하고 빠르게 설계할 수 있습니다.

💡 한 줄 요약

"수백만 개의 거래가 동시에 쏟아지는 복잡한 디지털 도서관에서, '퍼즐을 푸는 시간'이 들쑥날쑥해도 시스템이 얼마나 붐빌지, 그리고 얼마나 안전한지 '물의 흐름'처럼 정확히 예측하는 수학적 지도를 그렸다."

이 연구는 블록체인이나 분산 원장 기술을 더 안정적이고 효율적으로 만들기 위한 이론적인 나침반 역할을 합니다.

기술 요약

1. 연구 배경 및 문제 정의 (Problem)

• 배경: 블록체인 및 IOTA 와 같은 분산 원장 기술 (DLT) 은 신뢰할 수 있는 네트워크 구성원들이 투명하게 데이터를 업데이트할 수 있도록 설계된 탈중앙화 데이터베이스입니다. 이러한 시스템의 동역학은 방향성 비순환 그래프 (DAG) 로 수학적으로 모델링됩니다.
• 핵심 문제:
  • 기존 연구들 (예: [14]) 은 작업 증명 (Proof-of-Work, POW) 의 지속 시간이 **고정된 값 (deterministic)**이라고 가정하고 DAG 의 팁 (tip, 아직 다른 블록에 의해 첨부되지 않은 유효한 블록) 수의 유체 한계 (fluid limit) 를 분석했습니다.
  • 그러나 실제 시스템 (특히 IOTA) 에서 POW 수행 시간은 네트워크 부하, 하드웨어 성능 등에 따라 **무작위 (random)**하게 분포합니다.
  • POW 지속 시간이 무작위일 경우, 팁이 언제 '첨부 (attachment)'되어 더 이상 팁이 아닌 상태가 될지 예측하기 어렵고, 이는 시스템의 안정성과 보안 (거래 확인 속도) 에 직접적인 영향을 미칩니다.
• 목표: POW 지속 시간이 무작위 (다항 분포) 이고, 여러 블록이 동시에 도착하는 상황을 고려한 DAG 모델의 점근적 거동을 분석하고, 이를 **지연 편미분 방정식 (Delayed Partial Differential Equations, PDEs)**으로 표현된 유체 한계로 근사화하는 것을 목표로 합니다.

2. 방법론 (Methodology)

• 모델 설정:
  • 도착 과정: 시간 간격 $\epsilon$마다 $N$개의 정점이 동시에 도착합니다. 도착률 $\lambda = N/\epsilon$를 무한대로 보내고 $\epsilon \to 0$으로 두어 연속 시간 한계를 취합니다.
  • POW 지속 시간: 각 도착 정점은 $\{h_1, h_2, ..., h_M\}$ 중 하나의 POW 지속 시간을 확률 $p_i$로 가집니다 (다항 분포).
  • 부모 선택 (Parent Selection): IOTA 의 규칙에 따라 각 정점은 현재 존재하는 팁 (tips) 집합에서 무작위로 2 개의 부모를 선택합니다.
  • 상태 변수:
    • $L(t)$: 전체 팁 수
    • $F(t)$: 자유 팁 (Free tips, 아직 선택되지 않은 팁) 수
    • $W(t, u)$: 잔여 수명 (Residual Lifetime, RLT) 이 $u$인 대기 팁 (Pending tips) 수. 팁은 부모로 선택되면 대기 팁이 되며, 해당 POW 가 완료될 때까지 팁 상태를 유지합니다.
• 유체 한계 유도 (Fluid Limit Derivation):
  • 확률 변수들의 기대값을 계산하여 주된 항 (leading order term) 만 추출합니다.
  • 이산적인 업데이트 규칙 (Equations 2.7 - 2.11) 을 기반으로 기대값을 취하고 $\epsilon \to 0$ 극한을 적용하여 지연 편미분 방정식 (Delayed PDEs) 시스템을 유도합니다.
  • 유도된 PDE 시스템은 $f(t)$ (자유 팁 밀도), $l(t)$ (팁 밀도), $w_i(t, u)$ (유형 $i$ 대기 팁 밀도) 의 시간에 따른 변화를 설명합니다.
• 수렴성 증명:
  • 분리 기법 (Separation Technique): 확률 과정과 유체 한계 사이의 차이를 '변동 (fluctuation)'과 '기대값과 유체 한계의 차이'로 분리합니다.
  • Azuma-Hoeffding 부등식: 마팅게일 (martingale) 성질을 이용하여 변동 항의 확률적 상한을 구합니다.
  • 그론월 부등식 (Gronwall's Lemma): 오차 항을 누적하여 전체 시간 구간 $[0, T]$에서 유체 한계가 확률 과정에 수렴함을 증명합니다.

3. 주요 기여 (Key Contributions)

1. 무작위 POW 지속 시간을 고려한 새로운 DAG 모델: 기존 고정 시간 가정을 넘어, POW 시간이 다항 분포를 따르는 더 현실적인 모델을 제시했습니다.
2. 지연 편미분 방정식 (Delayed PDEs) 기반 유체 한계 도출: 무작위 지연과 동시 도착을 고려할 때, 시스템의 거동을 설명하는 새로운 형태의 PDE 시스템을 확립했습니다. 이는 기존 연구보다 더 정교한 분석을 가능하게 합니다.
3. 팁의 유형별 세분화 분석: 단순히 팁의 총수뿐만 아니라, 팁이 대기 상태 (pending) 가 될 때까지 예상되는 잔여 수명과 POW 유형에 따라 팁을 세분화하여 분석했습니다. 이는 보안 관점에서 다양한 리스크 수준에 있는 팁의 비율을 이해하는 데 기여합니다.
4. 강한 수렴성 증명: 유한 시간 구간 $[0, T]$에서 스케일링된 확률 과정이 유체 한계로 확률적으로 수렴함을 엄밀하게 증명했습니다 (Theorem 3.1).
5. 정상 상태 (Stable State) 분석: 유도된 PDE 를 통해 시스템의 균형점 (equilibrium point) 을 분석하고, POW 지속 시간 분포가 팁 수와 검증 속도에 미치는 영향을 정량화했습니다.

4. 주요 결과 (Results)

• 수렴성 (Theorem 3.1): 도착률 $\lambda$, 배치 크기 $N$, 시간 간격 역수 $\epsilon^{-1}$이 무한대로 갈 때, 확률 과정과 유체 한계 사이의 최대 오차 $g(T)$가 0 으로 수렴할 확률이 1 에 가까워짐을 보였습니다.
  • 수렴 조건: $N$이 $\epsilon^{-3}$보다 빠르게 증가해야 함.
• 정상 상태 분석 (Proposition 3.2):
  • 시스템이 안정 상태에 도달하면 팁 수 $l$, 자유 팁 수 $f$, 대기 팁 수 $w$는 $f = w = l/2$ 관계를 만족합니다.
  • POW 기대 지속 시간 ($\sum p_i h_i$) 이 짧을수록 팁이 더 빠르게 첨부되어 대기 팁 수가 줄어들고, 전체 팁 수 $l$도 감소함을 보였습니다.
  • 이는 팁이 더 빠르게 검증됨을 의미하며, 시스템의 처리량과 보안성 향상에 기여합니다.
• 시뮬레이션 검증: 수치 시뮬레이션을 통해 유체 한계 모델이 실제 무작위 과정의 동역학을 매우 정확하게 예측함을 확인했습니다 (Figure 4).

5. 의의 및 결론 (Significance)

• 이론적 기여: 분산 원장 시스템, 특히 DAG 기반 프로토콜 (IOTA 등) 의 동역학을 수학적으로 엄밀하게 분석하는 데 중요한 이정표를 세웠습니다. 무작위 지연을 포함한 복잡한 시스템의 거동을 PDE 로 설명할 수 있음을 보였습니다.
• 실용적 함의:
  • 보안 및 검증 속도: 팁 수와 대기 팁의 분포를 예측함으로써, 거래가 얼마나 빨리 검증되는지 (confirmation time) 를 예측할 수 있습니다. 팁 수가 많을수록 검증이 느려지므로, 시스템 설계 시 POW 난이도나 네트워크 대역폭을 조절하여 팁 수를 최적화하는 데 활용 가능합니다.
  • 시스템 설계: 무작위 지연 하에서도 시스템이 안정적으로 작동할 수 있는 조건을 제시하여, 실제 배포 시 발생할 수 있는 병목 현상이나 보안 취약점을 사전에 파악하는 데 도움을 줍니다.
• 향후 연구 방향: 본 연구는 무작위 지연을 고려한 기초 모델을 제시했으며, 향후 악의적 공격자 (adversarial nodes) 가 개입하는 상황이나 통신 지연을 함께 고려한 보안 분석으로 확장될 수 있음을 제안합니다.

요약하자면, 이 논문은 무작위 작업 증명 (POW) 지연을 고려한 분산 원장 모델의 동역학을 유체 한계 (Fluid Limit) 이론을 통해 수학적으로 규명하고, 이를 통해 시스템의 안정성과 검증 속도를 예측할 수 있는 강력한 도구를 제공했습니다.