Strategies for quantum-enabled Bitcoin miners

기술 요약: 양자 지원 비트코인 채굴자를 위한 전략

문제 정의
비트코인 네트워크의 보안은 51% 공격(연합체가 네트워크 연산력의 과반을 통제하여 이중 지불을 하거나 거래를 되돌리는 행위)을 실행하는 비용이 매우 높다는 가정에 의존합니다. 기존 연구들은 그로버 알고리즘(Grover's algorithm)이 작업 증명(PoW) 문제를 해결하는 데 있어 이차적 가속(quadratic speedup)을 제공함으로써 이러한 공격 비용을 낮출 수 있다고 이론적으로 제시해 왔으나, 이러한 연구들은 대개 좁은 적대적 모델에 국한되었습니다. 구체적으로, 이전 모델들은 양자 채굴자가 단 한 번의 양자 측정만을 수행하거나, 새로운 블록이 브로드캐스트되면 탐색을 중단하는 "평화로운(peaceful)" 전략을 사용하는 것으로 제한했습니다. 본 논문은 두 명의 비협력적이고 공격적인 양자 채굴자가 존재하는 더 현실적인 적대적 모델 내에서 51% 공격 임계값에 미치는 영향을 연구함으로써 이 간극을 메웁니다. 핵심 문제는 여러 번의 양자 측정을 수행할 수 있고 Sattath의 공격적 양자 채굴 전략(AQMS)을 활용할 수 있는 두 경쟁 채굴자 사이의 최적 양자 채굴 전략을 결정하고, 그 결과 발생하는 네트워크 정체율($p_{stale}$) 및 유효 51% 공격 임계값에 미치는 영향을 정량화하는 것입니다.

방법론
저자들은 클래식한 비트코인 네트워크 내에서 두 양자 채굴자 Alice와 Bob 사이의 경쟁을 모델링하기 위해 대칭적 2인 양자 경주(S2QR) 게임 이론 프레임워크를 확장합니다.

1. 모델 확장:

   • 다중 측정: 단일 측정을 가정하는 이전 모델과 달리, 이 모델은 채굴자가 연속된 블록 사이에 $c$번의 양자 측정을 수행할 수 있도록 허용합니다.
   • 공격적 전략: 이 모델은 채굴자가 새로운 블록의 브로드캐스트를 받는 즉시 탐색을 중단하고 즉시 측정하는 Sattath의 AQMS를 포함합니다. 이는 계산 노력을 버리지 않는 방식입니다. 이 전략은 측정 시간과 블록 발견 사이의 상관관계를 증가시켜 잠재적으로 정체율을 높일 수 있습니다.
   • 자원 제약: 채굴자는 $c$번의 측정에 분배된 누적 그로버 반복 횟수(Grover iteration) 예산 $\kappa$ 하에 작동합니다. 전략 공간은 성공 확률을 극대화하기 위해 이러한 반복 횟수를 할당하는 것을 포함합니다.

2. 게임 이론적 정식화:

   • 경쟁은 Alice와 Bob이 순수 전략(각 $c$번의 측정에 대한 그로버 반복 횟수의 벡터)을 선택하는 전략 게임으로 모델링됩니다.
   • 보상 행렬: 저자들은 양측 플레이어를 위한 보상 행렬($A$와 $B$)의 폐쇄형 식을 도출합니다. 이 행렬들은 다음을 고려합니다:
     • 그로버 반복 횟수에 기반한 유한 예산 양자 탐색(FQS) 알고리즘의 성공 확률.
     • 다중 측정에 따른 보상의 가산적 구조.
     • AQMS에 의해 도입된 항들로, 이는 상대방이 이미 솔루션을 찾았을 때(또는 측정이 동시에 발생할 때) 보상을 수정합니다.
   • 평형 계산: 최적 전략은 내쉬 평형(Nash equilibria)으로 식별됩니다. 전략 공간의 조합론적 폭발(c가 증가함에 따라 증가) 때문에, 저자들은 순수 전략 공간을 샘플링하는 휴리스틱을 사용하고 Lemke-Howson 알고리즘을 사용하여 정확한 내쉬 평형을 계산합니다.

3. 시뮬레이션:

   • 보안 영향을 평가하기 위해, 저자들은 계산된 내쉬 평형을 사용하여 몬테카를로 시뮬레이션(1,000,000일)을 수행합니다.
   • 시뮬레이션은 가장 긴 체인 외부에 있는 블록의 비율인 정체율($p_{stale}$)을 추적합니다.
   • 연구는 $p_{stale}$이 임계값인 $1/3$을 초과하여 유효 51% 공격 임계값을 40% 또는 그 이하로 낮추는지 여부를 평가합니다.
   • 시뮬레이션은 세 가지 네트워크 난이도 체제에 대해 수행됩니다: 저난이도($D \le 2^{32}$), 고난이도($D > 2^{32}$, 현재 및 예상되는 난이도 반영), 그리고 이상적 체제(양자 오라클이 전체 블록 헤더를 인코딩하는 경우).

주요 기여

• 새로운 전략 포함: 본 논문은 "공격적 양자 채굴 전략(AQMS)"을 게임 이론적 프레임워크에 도입하여, 다중 양자 측정과 함께 그 영향을 분석합니다.
• 일반화된 보상 행렬: 저자들은 $c$번의 양자 측정에 대한 보상 행렬의 수학적 구조를 도출하여, 다중 시도의 누적 특성과 AQMS에 의해 유도된 특정 타이밍 상관관계를 처리하도록 S2QR 모델을 확장했습니다.
• 최적 전략 계산: 연구는 다양한 난이도 체제에 대해 $c \in \{1, 2, 3, 4\}$에 대한 최적 양자 채굴 전략(내쉬 평형)을 계산하여, 채굴자들이 어떻게 그로버 반복 예산을 할당해야 하는지 밝혀냅s.
• 보안 정량화: 본 논문은 단순한 이론적 가능성을 넘어 시뮬레이션된 결과를 통해 최적 전략 하에서의 51% 공격 임계값에 대한 정량적 평가를 제공합니다.

결과

• 최적 전략:
  • 고난이도 체제 (현재 및 예상): 두 채굴자 모두에게 최적의 전략은 모든 자원을 마지막 측정에 할당하는 것입니다. 기대 보상은 매우 낮으며($\approx 8.9 \times 10^{-5}$), 채굴자들은 통계적으로 클래식 채굴자와 구별되지 않습니다.
  • 저난이도 및 이상적 체제: 채굴자들은 여러 측정에 걸쳐 자원을 분배합니다. $c=2$인 경우, 성공 확률과 시간적 이점 사이의 균형을 맞추기 위해 자원을 나눕니다. $c \ge 3$인 경우, 채굴자들은 종종 다른 시도의 이차적 성공 확률을 극대화하기 위해 일부 측정에 자원을 집중하거나 일부 시도에서 반복 횟수를 0으로 설정합니다.
• 정체율 및 51% 공격 임계값:
  • 고난이도: 정체율에 미치는 영향은 미미합니다. $p_{stale}$의 95백분위수와 99백분위수는 사실상 0입니다. $p_{stale}$이 $1/3$ 임계값을 초과할 확률은 0입니다. 네트워크는 예상대로 일일 144개의 블록을 생성하며, 양자 채굴자의 존재는 감지 불가능합니다.
  • 저난이도/이상적: 이 체제들은 상당한 $p_{stale}$ 증가를 보이며, 일부 시뮬레이션된 날들은 $1/3$ 벤치마크에 근접합니다. 그러나 $p_{stale} > 1/3$일 실질적인 확률은 매우 작습니다 ($10^{-6}$ ~ $10^{-8}$).
  • 탐지: 저난이도 및 이상적 체제에서는 비정상적인 포크율로 인해 양자 채굴자의 존재가 통계적으로 확실히 감지됩니다 ($P_{det} = 1$). 반면 고난이도 체제에서는 탐지가 거의 불가능합니다.

의의 및 주장
본 논문은 비트코인 네트워크를 향해 서로 경주하는 두 명의 비협력적 양자 채굴자가 제기하는 위협은 가까운 미래에 무시할 만한 수준이라고 결론짓습니다.

• 보안 유지: 가장 공격적인 가정(다중 측정, AQMS 및 최적 플레이) 하에서도, 결과적인 정체율은 51% 공격을 가능하게 하는 임계값을 지속적으로 초과하지 않습니다. 비트코인 네트워크는 이 특정 적대적 모델에 대해 여전히 안전합니다.
• 현실성: 저자들은 $p_{stale}$이 크게 증가하는 체제(저난이도 및 이상적)가 실제로는 발생하기 어렵다는 점을 강조합니다. 저난이도 체제는 비트코인 탄생 이래 보지 못한 네트워크 난이도를 요구하며, 이상적 체제는 전체 640비트 블록 헤더를 인코딩할 수 있는 양자 오라클을 필요로 하는데 이는 현재 기술적으로 불가능합니다.
• 탐지: 정체율이 증가하는 시나리오에서는 네트워크가 양자 채굴자를 즉시 통계적으로 감지할 수 있어 잠재적인 대응책을 마련할 수 있습니다.
• 제한적 범위: 저자들은 본 모델이 상태 준비(state preparation) 및 오라클 구축과 관련된 오버헤드를 무시한 채로 채굴자에게 "최선의 시나리오"를 나타낸다고 언급합니다. 따라서 실제 정체율에 미치는 영향은 예측된 것보다 훨씬 낮을 가능성이 큽니다. 이 연구는 더 많은 수의 채굴자나 협력 전략을 연구하기 위한 기초를 마련하지만, 두 명의 채굴자에 대해서는 51% 공격 임계값이 견고함을 확언합니다.