기술 요약: 블록체인 내 적대적 조달

문제 정의

본 논문은 수행과 검증 작업 간의 계산적 비대칭성 (예: 영지식 증명 또는 SNARK) 을 활용하는 새로운 설계의 맥락에서, 블록체인 프로토콜 내 **적대적 조달 (adversarial procurement)**의 과제를 다룹니다. 이러한 시스템에서 프로토콜은 블록의 유효성 증명 생성과 같은 고비용 계산 작업을 $n$명의 익명이며 신뢰할 수 없는 증명자 (prover) 집단에 아웃소싱해야 합니다.

핵심 문제는 다음과 같은 메커니즘을 설계하는 것입니다:

1. 적어도 한 명의 증명자가 작업을 수행하도록 유인하여 (생존성 (liveness) 보장).
2. 최대 $n-h$명의 증명자가 적대적 (비잔틴) 이며 생존성 결함 (증명 미전달) 을 유발하거나 과지불을 초래하기 위해 프로토콜에서 이탈할 수 있는 최악의 시나리오에서 경제적 손실을 최소화하고.
3. 증명자에게는 평판이 없으며 미래 행위에 대한 신뢰할 수 있는 약속을 할 수 없으므로 신뢰 없이 작동하도록 합니다.

저자들은 이를 메커니즘 설계 문제로 모델링하여, 프로토콜 설계자가 적대자가 증명자의 부분 집합을 통제하고 프로토콜의 손실을 극대화하도록 행동한다고 가정할 때, 지불금의 합과 증명이 전달되지 않을 경우 발생하는 벌금 $C$의 합을 최소화하려 한다고 봅니다.

방법론

저자들은 문제를 게임 이론적 프레임워크를 사용하여 공식화했습니다:

• 설정: $n$명의 증명자가 있으며, 이 중 $h$명은 정직합니다. 증명 생성 비용은 1 로 정규화됩니다. 증명이 생성되지 않으면 프로토콜은 생존성 벌금 $C$를 부담합니다.
• 적대자 모델: 적대자는 최대 $a = n-h$명의 증명자를 타락시킬 수 있습니다. 적대자는 메커니즘을 관찰하고 최악의 행동을 선택합니다 (벌금 $C$를 유발하기 위해 증명 전달을 거부하거나, 지불금을 조작하기 위해 증명을 전달하는 것).
• 목표: 메커니즘이 인센티브 호환적 (정직한 증명자가 프로토콜을 따름으로써 효용을 극대화) 이라는 제약 하에, 최악의 적대적 전략 하의 기대 총비용 (지불금 + 벌금) 으로 정의된 최악의 손실 $\ell(p, s)$를 최소화합니다.

문제를 다루기 쉽게 만들기 위해 저자들은 다음과 같은 작업을 수행했습니다:

1. 각 증명자가 증명을 전달할 확률인 전략 벡터 $s$를 매개변수로 하는 최적 프로토콜 손실에 대한 하한 함수 $g(s)$를 유도합니다. 이 하한은 "약화된" 적대자가 완전히 정직하게 행동하거나 완전히 전달을 거부하는 두 가지 극단적 전략 중 하나를 선택한다고 가정합니다.
2. 이 하한의 최소화자를 분석하여, 이를 지정된 균일 위원회 균형 (Designated Uniform Committee Equilibria)(한 명의 결정론적 리더 + 무작위화 위원회) 또는 대칭 위원회 균형 (Symmetric Committee Equilibria)(지정된 리더 없이 무작위화 위원회) 으로 특징짓습니다.
3. 구현 가능성을 조사합니다: 이러한 균형을 유도하면서 하한 비용을 달성할 수 있는 지불 규칙이 존재하는지 확인합니다.
4. **음수 지불 (슬래싱/스테이킹)**을 포함하도록 분석을 확장합니다. 여기서 증명자는 프로토콜이 공격을 감지하면 몰수될 수 있는 담보를 게시합니다.

주요 기여 및 결과

1. 최적 균형의 특징화

본 논문은 하한 $g(s)$의 최소화자가 오직 두 가지 유형으로만 존재함을 증명합니다:

• 지정 균형 (Designated Equilibria): 한 명의 증명자가 확률 1 로 증명을 전달하도록 지정되며, 크기 $k$의 위원회가 확률 $s \in (0, 1)$로 증명을 전달합니다.
• 대칭 균형 (Symmetric Equilibria): 크기 $k$의 위원회가 확률 $s$로 증명을 전달하며, 단일 증명자는 지정되지 않습니다.

2. 근사 보장

• 가법적 1-근사: 저자들은 어떤 지불 규칙과 균형에 대해서도, 최적 손실보다 최대 1 단위 (단일 증명 비용) 만 높은 지정 균형이 존재함을 증명합니다 (정리 3.1).
• 구현 가능성: 모든 지정 균형은 간단한 지불 규칙으로 구현 가능합니다 (보조정리 3.4). 반면, 대칭 균형은 특정 조건 (예: $C$가 $n$과 $h$에 비해 충분히 큰 경우) 에서만 구현 가능하며, 종종 복잡하거나 실현 가능한 음수 지불을 요구합니다.

3. 점근적 확장

• 로그 확장: 최적 지정 균형의 최악 손실은 $O(\frac{\log C}{\tau})$로 확장됩니다. 여기서 $\tau = h/n$은 정직한 증명자의 비율입니다. 이는 고정된 비율의 적대자가 있더라도 프로토콜 비용이 생존성 벌금의 심각도에 따라 로그적으로만 증가함을 나타냅니다.
• 스테이킹의 영향: 총 담보 $B$를 도입하면 확장이 크게 개선됩니다. $B$가 $C$에 비례하면 손실은 $O(1/\tau)$로 확장되어 $C$에 대해 사실상 상수가 됩니다.

4. 전환 역학

본 논문은 $C$(벌금 크기) 와 $\tau$(정직 비율) 의 함수로서 지정 최적성과 대칭 최적성 간의 전환을 분석합니다.

• $C$가 작거나 $\tau$가 높은 경우, 지정 메커니즘이 최적입니다.
• $C$가 매우 큰 경우, 하한 분석에서 대칭 메커니즘이 최적이 됩니다.
• 그러나 구현 가능성 제약으로 인해, 대칭 하한이 더 낮은 영역에서도 지정 메커니즘이 종종 실용적인 선택으로 남습니다. 이는 대칭 해법이 실현 불가능하거나 구현이 복잡한 음수 지불을 요구할 수 있기 때문입니다.

중요성 및 실용적 권장사항

본 논문은 이론적 결과가 zk-EVM(영지식 이더리움 가상 머신) 및 기타 검증 가능한 아웃소싱 시장을 위한 블록체인 프로토콜 설계자에게 실행 가능한 지침을 제공한다고 주장합니다.

• 권장사항: 저자들은 최적 지정 균일 위원회 균형을 채택할 것을 강력히 권장합니다. 이 설계는 증명을 결정론적으로 생성하는 단일 "리더"(또는 주요 작업자) 를 지정하고, 계산된 확률 $s$로 증명을 생성하는 "백업" 위원회를 지원합니다.
• 근거:
  1. 간단함: 지불 규칙은 직관적이며 기존 합의 메커니즘 (예: 인증 위원회를 갖춘 리더 기반 합의) 과 유사합니다.
  2. 근접 최적성: 손실은 이론적 최적치에서 증명 비용 1 개 이내이며, 이는 현재 증명 비용 (종종 몇 달러의 일부) 을 고려할 때 무시할 수 있습니다.
  3. 견고성: 이는 최악의 적대적 행동을 효과적으로 처리하며, 벌금 $C$에 따라 로그적으로 확장됩니다.
  4. 실현 가능성: 최적을 위해 복잡하거나 음수 지불 (슬래싱) 이 필요한 대칭 메커니즘과 달리, 지정 메커니즘은 항상 양수 지불로 구현 가능합니다.

본 논문은 대칭 메커니즘이 이론적으로 흥미롭고 특정 점근적 영역에서 최적이지만, 지정 메커니즘이 이론적 최적성, 구현 가능성, 그리고 블록체인 커뮤니티의 친숙함 사이의 가장 좋은 균형을 제공한다고 결론지었습니다. 저자들은 그들의 모델이 검증 가능한 AI 추론 및 TEE 기반 계산을 포함한 생존성 결함과 관련된 모든 무허가 위임 문제에 광범위하게 적용된다고 언급합니다.