Game-Theoretic Analysis of Transaction Selection in DAG-Based Distributed Ledgers

기술 요약: DAG 기반 분산 원장의 트랜잭션 선택에 대한 게임 이론적 분석

문제 제기
DAG 기반 분산 원장 기술 (DLT) 에서는 처리량을 향상시키기 위해 여러 검증자가 동시에 블록을 제안합니다. 그러나 이러한 병렬성은 트랜잭션 충돌이라는 과제를 야기하는데, 이는 여러 검증자가 동일한 트랜잭션을 선택하여 중복 포함이 시스템 유틸리티를 증가시키지 못함으로써 비효율성을 초래합니다. 기존 시스템들은 종종 균일 선택이나 비례 선택과 같은 단순한 휴리스틱에 의존하여 트랜잭션을 선택하지만, 이러한 전략들이 특정 수수료 할당 메커니즘 하에서 내시 균형 (NE) 을 구성하는지 엄밀하게 분석하지는 않았습니다. 또한, 탈중앙화된 비협력적 환경에서 수수료 분배 모델과 검증자 인센티브 간의 상호작용은 충분히 연구되지 않았습니다. 본 논문은 두 가지 서로 다른 수수료 할당 메커니즘 하에서 트랜잭션 선택 전략에 대한 대칭적 혼합 내시 균형을 유도하고, 이를 단순한 벤치마크와 비교하여 성능을 평가함으로써 이러한 격차를 해소합니다.

방법론
저자들은 트랜잭션 선택 과정을 $N$명의 검증자와 다양한 수수료를 가진 $m$개의 트랜잭션으로 구성된 유한 풀을 포함하는 단일 샷 게임 (단기적 모델) 으로 모델링합니다. 각 검증자는 블록에 포함할 $b$개의 트랜잭션 부분집합을 선택합니다. 본 연구는 두 가지 수수료 할당 메커니즘에 초점을 맞춥니다:

1. 무작위 수수료 할당 (RFA): 여러 검증자가 동일한 트랜잭션을 포함할 경우, 수수료가 정확히 한 검증자에게 무작위로 할당됩니다. 이 메커니즘은 총 순서가 있는 작업 증명 (PoW) 시스템 (예: GHOSTDAG) 에서 일반적입니다.
2. 협력적 수수료 분배 (CFS): 적어도 한 명의 검증자가 트랜잭션을 포함할 경우, 수수료가 모든 $N$명의 검증자에게 균등하게 분배됩니다. 이 메커니즘은 비잔틴 장애 허용 (BFT) 과 유사한 프로토콜에서 더 일반적입니다.

저자들은 게임 이론적 프레임워크를 활용하여 대칭적 내시 균형을 유도합니다. 먼저 기대 보상 지분을 나타내는 엄격하게 감소하는 함수 $f(p)$를 사용하여 내시 균형을 특징짓는 일반 이론적 결과 (정리 IV.1) 를 확립합니다. RFA 의 경우 $f(p)$를 직접 역산하는 것이 계산적으로 매우 복잡하다는 점을 인식하여, 카루쉬 - 쿤 - 터커 (KKT) 조건을 활용한 효율적인 최적화 기반 접근법을 제안합니다. 이를 통해 균형 유도 문제를 투영된 경사 하강법으로 해결 가능한 오목 최적화 문제로 변환합니다.

유도된 균형의 성능은 두 가지 단순한 벤치마크에 대해 수치적으로 평가됩니다:

• 무작위 트랜잭션 선택 (RTS): 균일 선택.
• 비례 트랜잭션 선택 (PTS): 트랜잭션 수수료에 비례한 선택 확률.

평가 지표로는 유효 트랜잭션 처리량(포함된 고유 트랜잭션의 기대 수) 과 유효 수수료 처리량(수집된 총 기대 보상) 이 포함됩니다. 시뮬레이션은 왜곡된 수수료 구조를 모델링하기 위해 지프 (Zipf) 유사 수수료 분포를 사용합니다.

주요 기여

1. 대칭적 내시 균형 유도: 본 논문은 단일 샷 트랜잭션 선택 게임에서 RFA 및 CFS 모델에 대한 대칭적 혼합 내시 균형을 최초로 명시적으로 유도합니다.
2. 효율적인 계산 방법: 저자들은 KKT 조건을 활용한 오목 최적화 프레임워크를 도입하여 이러한 균형을 효율적으로 계산하는 방법을 제시하며, 특히 RFA 모델에서 직접 역산 방법의 계산적 비실용성을 극복합니다.
3. 비교 성능 분석: 수치 시뮬레이션을 통해 협력적 수수료 분배 (CFS) 메커니즘의 내시 균형이 무작위 수수료 할당 (RFA) 의 내시 균형보다 일관되게 더 높은 수수료 처리량과 보상을 달성함을 보여줍니다. 특히 왜곡된 수수료 분포 하에서 그 차이가 두드러집니다.
4. 단순 전략 벤치마킹: 분석 결과, CFS-NE 는 수수료 수익 측면에서 최적이지만, 비례 트랜잭션 선택 (PTS) 휴리스틱은 종종 보상 측면에서 RFA-NE 보다 우수한 성능을 발휘하는 것으로 나타났습니다. CFS 가 불가능한 시나리오 (예: 허가 없는 PoW 시스템) 에서는 PTS 가 복잡한 균형 계산을 요구하지 않으면서 RFA 균형의 성능에 근접할 수 있는 강력한 대안으로 작용합니다.

결과
다양한 매개변수 (트랜잭션 수, 최대 수수료, 수수료 왜곡도) 하의 수치 평가는 다음과 같은 통찰을 제공합니다:

• 수수료 처리량: CFS 균형은 모든 테스트된 시나리오에서 일관되게 수수료 처리량을 최대화합니다. PTS 전략 또한 잘 수행되어 RFA 균형을 크게 능가합니다. 반면, RFA 균형은 종종 균일 전략 (RTS) 보다도 낮은 수수료 처리량을 보입니다.
• 트랜잭션 처리량: 수수료 극대화와 트랜잭션 다양성 사이에는 트레이드오프가 존재합니다. 균일 전략 (RTS) 은 균등한 확률 분포를 통해 충돌을 최소화함으로써 가장 높은 유효 트랜잭션 처리량을 달성합니다. 그러나 이는 낮은 수수료 처리량이라는 대가를 치릅니다. CFS 균형은 수수료를 최대화하지만, 검증자들이 고수수료 트랜잭션에 집중하여 해당 항목에 대한 충돌률이 높아지기 때문에 가장 낮은 유효 트랜잭션 처리량을 초래합니다.
• 왜곡도의 영향: 수수료 분포가 더 왜곡될수록 (더 높은 지프 매개변수) 성능 격차는 커집니다. CFS 와 PTS 는 우수한 수수료 처리량을 유지하는 반면, RFA 는 어려움을 겪으며 다양한 수수료 구조를 처리하는 데 비효율적임을 보여줍니다.

의의 및 주장
본 논문은 DAG 기반 DLT 의 트랜잭션 선택 및 인센티브 메커니즘 설계에 대한 실행 가능한 통찰을 제공한다고 주장합니다. 내시 균형을 특징짓는 것을 통해 저자들은 균일 선택과 같은 직관적 전략이 항상 최적은 아니며, 수수료 할당 메커니즘의 선택이 검증자의 행동과 시스템 성능을 근본적으로 변화시킨다는 것을 보여줍니다.

구체적으로, 본 연구는 다음과 같은 점을 시사합니다:

• 수익을 위한 CFS 의 우위: 주요 목표가 수수료 수익 극대화라면, 이에 상응하는 균형 전략을 가진 CFS 가 가장 효과적인 메커니즘입니다.
• RFA 의 본질적 비효율성: 작업 증명 (PoW) 시스템에서 일반적인 RFA 메커니즘은 비례 선택과 같은 단순한 휴리스틱보다 열등한 균형을 초래하여, 이러한 설계에서 개인적 인센티브와 집단적 후생 간의 불일치를 나타냅니다.
• 실용적 휴리스틱: 허가 없는 환경에서 검증자 집합을 알 수 없는 경우와 같이 CFS 가 불가능한 프로토콜의 경우, 비례 선택은 복잡한 균형 계산 없이 RFA 균형의 성능을 근사하는 가치 있는 휴리스틱을 제공합니다.

저자들은 연구 범위를 단조로운 모델, 정적 수수료, 동질적 지연 시간을 가진 단일 샷 모델로 제한한다는 점을 겸손하게 인정합니다. 동적 수수료와 이질적인 네트워크 조건을 가진 다중 라운드 순차 게임으로 이 분석을 확장하는 것이 실제 적용을 위해 필수적인 단계라고 지적합니다. 본 논문은 새로운 프로토콜 구현을 제안하는 것이 아니라, 기존 및 미래의 인센티브 구조를 평가하기 위한 이론적 및 수치적 기반을 제공합니다.