기술 요약: 병렬성의 위험: 실행 불확실성 하에서의 트랜잭션 수수료 메커니즘

1. 문제 정의

현대 블록체인들은 실행(execution)이 아닌 합의(consensus)로 인한 처리량 병목 현상을 극복하기 위해 직렬 실행에서 병렬 실행으로 전환하고 있습니다. 병렬 실행(Sui, Solana, Monad, Ethereum 등에서 사용 중이거나 계획 중)은 용량을 증가시키지만, 실행 불확실성(우발성, contingency)과 자원 경합(resource contention)이 포함된 트랜잭션에 대해 두 가지 결정적인 경제적 과제를 도입합니다.

1. 실행 우발성 및 리스크 할당: 표현력이 풍부한 스마트 컨트랙트 언어(튜링 완전)에서, 트랜잭션의 자원 사용량(접근하는 객체)은 실행 전에는 알 수 없는 블록체인의 런타임 상태에 따라 달라질 수 있습니다. 이는 사용자 리스크(사용자가 사용되지 않는 선언된 객체에 대해 과다 지불하는 것)와 스케줄러 리스크(예약된 용량이 미실행으로 인해 미지급되어 스케줄러가 수익을 잃는 것) 사이의 긴장을 유발합니다.
2. 가스 계산에 대한 쉴 공격(Shill Attacks): 병렬 환경을 위해 설계된 기존 가스 계산 메커니즘(GCM)(예: 샤플리 값(Shapley value) 또는 시간 비례 메이크스팬(Time-Proportional Makespan))은 합리적인 조작에 취약합니다. 사용자나 스케줄러 모두 계산된 가스나 수수료를 전략적으로 변경하기 위해 "쉴"(가짜) 트랜잭션을 주입할 수 있습니다. 사용자는 무의미한 병렬 트랜잭션을 추가하여 수수료를 낮출 수 있고, 스케줄러는 가짜 경합을 추가하여 수수료를 부풀릴 수 있습니다.

본 논문은 현재의 설계들이 병렬성, 실행 불확실성, 그리고 경제적 견고성을 동시에 고려하지 못하며, 이로 인해 비효율성과 악용 가능한 취약점이 발생한다고 주장합니다.

2. 방법론 및 모델

저자들은 실행 불확실성을 동반한 병렬 실행 환경에서의 트랜잭션 수수료 메커니즘(TFM)을 분석하기 위한 프레임워크를 정형화합니다.

• 트랜잭션 모델: 트랜잭션 $tx$는 연산 단위$t$, 우선순위 수수료$g$, 그리고 선언된 읽기/쓰기 집합$(R, W)$로 정의됩니다. 결정적으로, *실제 접근하는 객체*($X_R, X_W$)는 실행 경로(우발성)에 따라 선언된 집합의 부분 집합일 수 있습니다.
• 수수료 정의: 논문은 다음을 구분합니다:
  • 도달 가능 수수료 ($f_{att}$): 모든 선언된 객체가 사용될 경우의 수수료.
  • 기초 수수료 ($f_{base}$): 결정적 객체들에 대해서만 부과되는 수수료.
  • 사용자 이상적 수수료 ($f_{ui}$): 실제로 사용된 객체들에 대한 정확한 수수료.
  • 실제 지불 수수료 ($f_{act}$): 실제로 부과되는 수수료.
• 리스크 지표:
  • **사용자 리스크 ($UR$):**$f_{act} - f_{ui}$ (과다 지불).
  • **스케줄러 리스크 ($SR$):**$f_{att} - f_{act}$ (실현되지 않은 수익).
• 적대적 모델: 사용자와 스케줄러는 비용을 최소화하거나 수익을 최대화하기 위해 쉴 트랜잭션을 삽격할 수 있는 합리적이고 경제적 동기를 가진 에이전트로 모델링됩니다.
• 복잡도 분석: 저자들은 실행 전 객체 사용량을 예측하는 것의 난이도를 분석하기 위해 복잡도 이론(특히 P-완비성)을 활용합니다.

3. 주요 기여 및 결과

A. 리스크 동시 제거의 불가능성

논문은 근본적인 불가능성 결과를 증명합니다: 어떠한 메커니즘도 트랜잭션을 사전 실행하거나 상수 수수료로 수렴시키지 않고서는 사용자 리스크와 스케줄러 리스크를 동시에 제거할 수 없습니다.

• 정리 1: 스케줄러가 컴퓨트 제한 $G$(블록이 허용하는 것보다 더 많은 작업을 수행할 수 없음)의 제약을 받는다면, 충돌하는 우발적 트랜액션이 포함된 모든 입력에 대해 $UR=0$과$SR=0$을 만족하도록 결제를 설정하는 것은 불가능합니다.
• 정리 2 (P-완비성): 특정 객체가 우발적 트랜잭션에 의해 사용되는지 여부를 결정하는 것(객체 사용 결정 문제)은 P-완비(P-complete)입니다. 이는 객체 사용을 검증하는 것이 실행 시간에 비례하는 순차적 작업을 요구함을 의미하며, 따라서 스케줄러가 실행 전에 "저렴하게" 사용량을 예측하는 것은 계산적으로 불가능함을 시사합니다.
• 트레이드오프: 내재적인 선형적 트레이드오프가 존재합니다. 사용자 리스크를 줄이면(사용된 객체에 대해서만 청구), 스케줄러 리스크(수익 손실)가 증가하며, 그 반대도 마찬가지입니다.

B. 리스크 분할 메커니즘의 특성 규명

불가능성을 고려하여, 저자들은 $\alpha \in [0,1]$로 매개변수화된 세 가지 정형적인 리스크 분할 메커니즘을 통해 설계 공간을 규명합니다:

1. 사용자 친화적 ($\alpha=0$): 사용자는 실제 실행된 것에 대해서만 지불합니다 ($f_{act} = f_{ui}$). 스케줄러가 모든 리스크를 부담합니다.
2. 스케줄러 친화적 ($\alpha=1$): 사용자는 모든 선언된 객체에 대해 지불합니다 ($f_{act} = f_{att}$). 사용자가 모든 리스크를 부담합니다.
3. 이븐 스티븐 (Even-Steven, $\alpha=0.5$): 리스크가 균등하게 분할됩니다.
   논문은 다양한 스케줄러 효용 모델(낙관적, 비관적, 중앙값) 하에서 이를 분석하여 수익에 미치는 영향을 매핑합니다.

C. 쉴 공격 및 수수료 기반 쉴 방어성

저자들은 표준 GCM 속성(예: 집합 포함 관계)이 우발성이 존재하는 상황에서 쉴 공격을 방지하기에 불충분함을 밝힙니다.

• 사용자 쉴 공격: 사용자가 자신의 실제 트랜잭션의 유효 가스/수수료를 낮추기 위해 가짜 트랜잭션을 주입합니다.
• 스케줄러 쉴 공격: 스케줄러가 정직한 사용자에게 부과되는 가스/수수료를 높이기 위해 가짜 트랜잭션을 주입합니다.
• 수수료 기반 쉴 방어성: 저자들은 우선순위 수수료와 실행 우발성을 고려하여, 가스뿐만 아니라 수수료를 기준으로 하는 새로운 쉴 방어성 정의를 제안합니다. 그들은 사용자 친화적 메커니즘의 경우, 수수료가 스케줄과 독립적일 때만 쉴 방어성이 달성 가능하다는 것을 증명합니다(정리 3).

D. 객체 가중치 TFM (OW-TFM)

이러한 문제들을 해결하기 위해, 저자들은 **객체 가중치 트랜잭션 수수료 메커니즘 (OW-TFM)**을 제안합니다.

• 메커니즘: 수수료는 트랜잭션에 의해 선언된 객체의 가격을 기준으로 계산되며, 객체 가격은 과거 활용도에 따라 업데이트됩니다(EIP-1559와 유사).
• 리스크 매개변수화: 이 메커니즘은 사용자가 선언되었으나 사용되지 않은 객체에 대해 얼마나 지불할지($\alpha \cdot \text{price}$)를 결정하기 위해 파라미터 $\alpha$를 사용합니다.
• 쉴 저항성: OW-TFM은 특정 조건 하에서 쉴 방어성을 갖는 것으로 나타났습니다. 가격이 과거 블록의 활용도에서 파생되기 때문에, 현재 블록에서의 쉴 트랜잭션은 현재 블록의 객체 가격을 낮출 수 없습니다(미래의 가격만 높일 수 있습니다).
• 조건: 보조정리 4는 우선순위 대비 기초 수수료 비율($\pi_o$), 가격 반응성($\eta$), 유지 비율($\gamma$)에 의존하여 스케줄러 쉴 공격을 방지하기 위해 필요한 $\alpha$의 임계값을 설정합니다.

4. 의의 및 주장

본 논문은 병렬 블록체인을 위한 수수료 메커니즘을 평가하고 설계하기 위한 엄밀한 기초를 제공한다고 주장합니다. 그 의의는 다음과 같습니다:

1. 근본적 한계 식별: 병렬 실행에서 사용자 공정성과 스케줄러 수익 사이의 긴장이 설계 결함이 아니라, 실행 불확실성과 계산 복잡도의 결과로 발생하는 근본적인 결과임을 입증했습니다.
2. 취약점 노출: 기존의 병렬 가스 계산 제안들(예: 샤플리 기반 접근법)이 합리적인 쉴 공격에 취약함을 드러냈으며, 이는 기존 문헌에서 다뤄지지 않았던 위협입니다.
3. 설계 프레임워크 제공: 리스크 할당 전략을 명시적으로 선택하면서도 조작에 대한 저항성을 유지할 수 있도록 하는 원칙적인 설계 공간($\alpha$ 스펙트럼)과 구체적인 메커니즘(OW-TFM)을 제공합니다.
4. 산업적 관련성: 본 연구의 결과는 유명한 병렬 체인(Sui, Monad, Solana)의 설계와 액세스 리스트(access lists)를 통한 이더리움의 병렬 실행 로드맵에 직접적으로 적용 및 비판적 검토가 가능합니다.

저자들은 자신의 연구가 단 하나의 "완벽한" 해결책을 제시하기보다는 근본적인 한계와 트레이드오프를 식별하는 데 중점을 두었음을 밝히며, 실질적인 배포를 위해서는 확률적 실행 모델 및 구체적인 구현 세부 사항에 대한 추가 고려가 필요함을 인정하며 겸허한 태도를 유지합니다.