기술 요약: 만장일치에 의한 순서 결정 (Ordering by Unanimity)

1. 문제 정의

블록체인 애플리케이션은 올바르게 작동하기 위해 실행 순서에 관한 특정한 선호도를 가질 때가 많습니다. 예를 들어, 자동 마켓 메이커(AMM)는 오라클 가격 업데이트가 스왑보다 앞서 수행되어야 하며, 오더북 거래소는 취소 주문이 시장 주문보다 먼저 실행되어야 하고, 온체인 경매는 입찰이 높은 가격부터 낮은 가격 순으로 처리되어야 합니다. 현재 트랜잭션 순서는 기본 블록체인(예: 블록 생성자 또는 우선순위 수수료를 통해)에 의해 결정되는데, 이는 애플리케이션의 특정 요구사항과 일치하지 않을 수 있습니다.

순서를 강제하기 위한 기존 솔루션들은 종종 결합성(composability)—공유 원장에서 애플리케이션들이 자유롭게 상호작용하는 능력—을 희생합니다. 예를 들어, PropAMMs(오라클 의존형 AMM)는 솔라나의 특정 순서 규칙 덕분에 가능하지만 다른 곳에서는 구현하기 어렵습니다. 하이퍼리퀴드(Hyperliquid)와 같은 거래소는 자신들의 순서 로직을 보호하기 위해 격리된 체인을 구축했습니다. 롤업(rollup) 또한 베이스 레이어로부터 트랜잭션을 격리함으로써만 순서 제어를 달성합니다. 본 논문은 블록체인을 파편화하거나 결합성을 희생하지 않으면서, 애플리케이션에 시퀀싱 권한을 부여하는 과제를 다룹니다.

2. 방법론: 만장일치 오버라이드 (Unanimity Override)

본 논문은 만장일치 오버라이드라고 불리는 프로토콜 수준의 순서 결정 규칙을 제안합니다. 핵심 직관은 두 트랜잭션 쌍에 관련된 모든 애플리케이션이 그들의 상대적 순서에 동의한다면, 프로토콜이 그 합의를 존중해야 한다는 것입니다. 만약 애플리케이션들이 서로 의견이 다르거나 결과적으로 선호도가 순환(cycle)을 형성하면, 폴백(fallback) 메커니즘이 충돌을 해결합니다.

메커니즘

알고리즘은 두 가지 주요 단계로 작동합니다.

1. 만장일치 관계 ($\succ_u$): 트랜잭션 $x_i \succ_u x_j$인 경우, 즉 $x_i$와 $x_j$ 모두와 상호작용하는 모든 애플리케이션이 $x_i$를 $x_j$보다 상위에 랭크하고, 적어도 하나의 애플리케이션이 $x_i$를 엄격하게 선호할 때, 방향성 관계가 구축됩니다.

   • 이 관계는 일반적으로 불완전하며(일부 쌍은 순위가 매겨지지 않음), 비이행적(non-transitive)입니다(순환이 발생할 수 있음).
   • 순환은 특히 트랜잭션이 여러 "의견을 가진(opinionated)" 애플리케이션(선호도를 표현한 애플리케ка이션)과 상호작용할 때 발생합니다.

2. 순환 파괴 (Fallback): 전체 실행 순서를 복구하기 위해 프로토콜은 순환을 깨야 합니다. 본 논문은 강등(demotion) 규칙을 도입합니다.

   • 순환 구성 요소 (Cyclic Components): 알고리즘은 만장일치 그래프에서 극대 강결합 컴포넌트(maximal strongly connected components)를 식별합니다.
   • 강등: 순환 구성 요소 내에서, 규칙은 "강등할" 트랜잭션 집합을 선택합니다. 결정적으로, 다중 의견 트랜잭션(2개 이상의 의견을 가진 애플리케이션과 상호작용하는 트랜잭션)만이 강등 대상이 될 수 있습니다.
   • 선택 로직: 폴백은 컴포넌트가 비순환(acyclic) 상태가 될 때까지 가장 낮은 "기본 순서(default order)" 값(예: 가장 낮은 우선순위 수수료)을 가진 다중 의견 트랜잭션을 반복적으로 강등합니다.
   • 복구된 관계 ($\tilde{\succ}_u$): 강등된 트랜잭션들은 해당 순환 내의 만장일치 비교에서 제외되며, 컴포넌트 내의 비강등 트랜잭션들보다 아래에 배치됩니다. 이들의 상대적 순서는 기본 순서에 의해 결정됩니다.
   • 완료: 결과적으로 얻어진 비순환 부분 순서는 역-칸(reverse-Kahn) 위상 정렬을 사용하여 전체 실행 순서($\succ_e$)로 확장되며, 이때 레이어 내의 동점 상황은 기본 순서를 사용하여 해결합니다.

3. 위협 모델

본 분석은 강력한 형태의 검열 저항성(트랜잭션을 억류할 수 없음)을 가정합니다. 공격자는 다음과 같은 행위를 할 수 있는 플레이어로 모델링됩니다:

• 임의의 선호도를 가진 새로운 애플리케이션을 배포함.
• 특정 속성(예: 수수료, 대상 애플리케이션)을 가진 트랜잭션을 블록에 주입함.
• 최악의 시나리오(예: 블록 생성자 역할)에서 기본 순서($U_d$)를 제어함.
• 공격자는 기존의 정직한 트랜잭션을 수정하거나 기존의 정직한 애플리케이션의 선호도를 변경할 수 없습니다.

4. 주요 결과 및 보장

본 논문은 공격자가 기본 순서를 제어하는 최악의 시나리오를 포함하여, 실행 가능한 모든 공격자 전략에 대해 유효한 두 가지 주요 보장 사항을 도출합니다.

보장 1: 단일 의견 보장 (The Single-Opinion Guarantee)

트랜잭션 $x$가 정확히 하나의 의견을 가진 애플리케이션과 상호작용하는 경우(단일 의견 트랜잭션), 그리고 해당 애플리케이션이 $x$를 다른 트랜잭션 $y$(다른 애플리케이션과 상호작용할 수 있음)보다 엄격하게 선호한다면, $x$는 $y$보다 먼저 실행됩니다.

• 근거: $x$는 단일 의견 트랜잭션이므로, 다른 애플리케이션은 $(x, y)$ 쌍에 대해 어떠한 선호도도 표현할 수 없습니다. 따라서 만장일치 랭킹은 해당 단일 애플리케이션의 선호도와 일치하게 됩니다. 폴백 규칙은 단일 의견 트랜잭션을 절대 강등하지 않으므로, 이 선호도는 최종 실행 순서에서도 보존됩니다.
• 의의: 이는 격리된 롤업의 보장 사항을 베이스 레이어로 확장합니다. 애플리케이션은 자신의 핵심 트랜잭션(예: 오라클 업데이트 또는 취소)이 해당 특정 애플리케이션하고만 상호작용하도록 보장함으로써, 트랜잭션의 일부가 선호가 없는 계약을 건드리더라도 이를 보호할 수 있습니다.

보장 2: 게이티드 영역 보장 (The Gated Region Guarantee)

**게이티드 영역(gated region)**이라 불리는 트랜잭션 집합 $X^*$가 존재하며, 이는 재정렬 공격으로부터 보호됩니다. 트랜잭션이 $X^*$에 속하는 조건은 다음과 같습니다:

1. $X^*$ 외부의 어떤 트랜스잭션(기존에 존재했거나 공격자가 주입할 수 있는 것 모두 포함)도 이를 만장일치로 상위에 랭크할 수 없다.
2. $X^*$에 국한된 만장일치 관계의 서브그래프는 비순환(acyclic)이다.

• 결과: $X^*$의 멤버 중 누구도 강등되지 않습니다. 결과적으로, 만약 $X^*$에 속한 트랜잭션이 다른 트랜잭션보다 만장일치로 상위에 랭크된다면, 공격자가 트랜잭션을 주입하거나 기본 순서를 제어하더라도 해당 트랜잭션이 먼저 실행됩니다.
• 응용: 이는 지정된 주소로부터의 오라클 업데이트나, 관련 시장 모두에 의해 가장 높게 랭크된 취소 주문 등을 보호합니다. 단, "게이트"(해당 트랜잭션을 추월할 수 있는 트랜스액션 집합)가 공격자에 의해 돌파될 수 없어야 합니다.

취약점: 다중 의견 트랜잭션

본 논문은 다중 의견 트랜잭션(2개 이상의 의견을 가진 애플리케이션과 상호작용)이 재정렬 공격에 취약한 유일한 대상임을 밝힙니다. 공격자는 타겟이 되는 다중 의견 트랜잭션을 포함하는 순환을 구성하고, 트랜잭션을 주입하여 폴백 과정에서 해당 트랜잭션이 강등되도록 강제할 수 있습니다. 그러나 본 논문은 대상이 단일 의견 트랜잭션인 경우 이러한 공격이 불가능하다고 명시합니다.

5. 벤치마크와의 비교

• 공격자가 제어하는 기본 순서 대비: 만장일치 오버라이드는 공격자가 블록 순서에 대한 완전한 통제권을 갖는 시스템에 비해 가역적인(reversible) 트랜잭션 쌍의 집합을 엄격하게 줄여줍니다.
• 우선순위 수수료 순서 대비: 비교 방식이 미묘합니다. 만장일치 오버라이드는 수수료와 무관하게 단일 의견 및 게이티드 트랜잭션을 보호합니다. 그러나 보호받지 못하는 다중 의견 트랜잭션의 경우, 공격 비용(예: 프런트 러닝)은 순환의 구체적인 토폴로지와 수수료 구조에 따라 더 높거나 낮을 수 있습니다. 본 논문은 만장일치 오버라이드 하에서도 그리핑(griefing) 공격(경쟁자에게 피해를 주기 위해 정직한 트랜잭션을 재정렬하는 것)은 가능하지만, 순수 우선순위 수수료 순서 하에서는 불가능하다는 점을 언급합니다.

6. 의의 및 범위

본 논문은 블록체인의 결합성을 희생하지 않으면서 애플리케이션 설계 공간을 확장하는 메커니즘을 제공한다고 주장합니다.

• 보장 유지: 애플리케이션은 별도의 체인이나 롤업으로 격리되지 않고도 순서 선호도(예: 스왑 전 오라클 업데이트, 거래 전 취소 등)를 강제할 수 있습니다.
• 인센티브 정렬: 메커니즘은 송신자에게 어떤 트랜잭션이 안전한지를 미리 알려줍니다. 예를 들어, 온체인 경매에서 입찰자들은 자신이 강등되지 않도록 입찰을 단일 의견 트랜잭션으로 유지하도록 인센티브를 받게 되며, 이를 통해 경매가 의도대로 작동하도록 보장합니다.
• 이론적 기여: 본 연구는 트랜잭션 순서 결정과 사회 선택 이론(social choice theory)을 연결합니다. 만장일치 관계가 비이행적이라는 점(이는 애로우의 불가능성 정리의 결과임)을 인정하고, 완전하고 비순환적인 실행 순서를 달성하기 위해 "무관한 대안으로부터의 독립성(independence of irrelevant alternatives)"을 희생하는 특정 파레토 집계 규칙을 제안합니다.

논문은 마지막으로 상호작용 집합(트랜잭션이 접하는 애플리케이션들)의 정의가 실무적인 과제임을 언급합니다. 본 논문은 선언된 상호작용(검증하기 쉽지만 다중 의견 상태를 과대평가할 가능성이 있음)과 실제 상호작용(더 강력한 보장을 제공하지만 일관성을 위한 고정점 해법이 필요함) 사이의 트레이드오프를 논의합니다. 현재의 분석은 상호작용 집합이 주어진 것으로 가정합니다.