수십 년 동안 분산 시스템, 특히 비잔틴 합의 및 상태 머신 복제(SMR) 연구는 일관성과 Liveness 이라는 두 가지 주요 목표에 집중되어 왔습니다. 일관성은 모든 노드가 동일한 트랜잭션 순서에 동의하는 것을 의미하며, Liveness 시스템이 새로운 트랜잭션을 지속적으로 추가하도록 보장합니다. 하지만 이러한 속성은 악의적인 행위자가 트랜잭션을 수신한 후 순서를 변경하는 것을 막지는 못합니다.
퍼블릭 블록체인에서 기존 합의 보장의 이러한 간극은 심각한 문제로 대두되었습니다. 검증자 , 블록 생성자 또는 시퀀서는 블록 순서 지정에서 자신의 특권적인 역할을 금전적 이익을 위해 악용할 수 있는데, 이를 MEV(Maximal Extractable Value) ( MEV )라고 합니다. 이러한 조작에는 수익성 있는 선행매매, 후행매매, 그리고 거래 샌드위치가 포함됩니다. DeFi 애플리케이션에서 거래 실행 순서는 유효성 또는 수익성을 결정하기 때문에, 거래 순서의 무결성은 공정성과 신뢰를 유지하는 데 매우 중요합니다.
이러한 심각한 보안 허점을 해결하기 위해 거래 순서 공정성이 세 번째 필수 합의 속성으로 제안되었습니다. 공정 순서 프로토콜은 거래의 최종 순서가 도착 시간(또는 수신 순서)과 같은 외부적이고 객관적인 요인에 따라 결정되도록 하며, 적대적인 순서 변경에 대한 저항성을 보장합니다. 블록 제안자가 거래 순서를 변경할 수 있는 권한을 제한함으로써, 이러한 프로토콜은 블록체인을 투명하고 예측 가능하며 MEV(Medium Value)에 대한 저항성을 강화합니다.
콩도르세의 역설과 이상적 공정성의 불가능성
공정성에 대한 가장 직관적이고 강력한 개념은 수신-순서-공정성(ROF) 입니다. 비공식적으로 "먼저 수신되면 먼저 출력된다"로 정의되는 ROF는 충분한 수의 트랜잭션 (tx) 이 다른 트랜잭션 (tx′) 보다 먼저 대다수 노드에 도착하면, 시스템은 실행을 위해 tx를 tx′ 보다 먼저 주문해야 함을 의미합니다.
그러나 모든 노드가 즉각적으로 통신할 수 있다고 가정하지 않는 한, 보편적으로 인정되는 "질서 공정성"을 달성하는 것은 근본적으로 불가능합니다. 즉, 즉각적으로 동기적인 외부 네트워크에서 작동한다는 가정이 전제되지 않는 한 말입니다. 이러한 불가능성은 사회 선택 이론, 특히 콩도르세 역설과의 놀라운 연관성에서 비롯됩니다.
콩도르세 역설은 모든 개별 노드가 거래의 내부 순서를 이행적으로 유지하더라도 시스템 전체의 집단적 선호가 비이행적 순환으로 이어질 수 있음을 보여줍니다. 예를 들어, 대다수의 노드가 B 보다 먼저 거래 A를 받고, 대다수의 노드가 C 보다 먼저 B를 받고, 대다수의 노드가 A 보다 먼저 C를 받는 경우가 있습니다. 따라서 세 가지 다수 선호도는 순환 고리( A → B → C → A )를 형성합니다. 즉, 거래 A, B, C의 단일하고 일관된 순서로는 모든 다수 선호도를 동시에 충족할 수 없습니다.
이 역설은 비동기 네트워크 에서 수신 순서 공정성(Receive-Order-Fairness)을 완벽하게 달성하는 것이 불가능한 이유를 보여줍니다. 외부 네트워크 지연이 너무 길 경우, 심지어 공통 클럭을 공유하는 동기 네트워크 에서도 마찬가지입니다. 이러한 불가능성은 배치 순서 공정성(Batch Order Fairness)과 같은 더 약한 공정성 정의의 채택을 불가피하게 만듭니다.
헤데라(Hedera) 해시그래프와 중간 타임스탬핑의 결함
해시그래프 합의 알고리즘을 사용하는 헤데라(Hedera) 수신 순서 공정성(ROF)이라는 강력한 개념을 구현하고자 합니다. 헤데라는 각 거래에 해당 거래에 대한 모든 노드의 로컬 타임스탬프의 중간값으로 계산된 최종 타임스탬프를 할당함으로써 이를 구현합니다.
하지만 이는 본질적으로 조작되기 쉽습니다. 단일 적대적 노드가 로컬 타임스탬프를 의도적으로 왜곡하여 두 거래의 최종 순서를 뒤집을 수 있는데, 이는 모든 정직한 참여자가 올바른 순서로 거래를 수신했음에도 마찬가지입니다.
다섯 개의 합의 노드(A, B, C, D, E)가 있고 노드 E가 악의적인 행동을 하는 간단한 예를 생각해 보겠습니다. tx₁과 tx₂라는 두 거래가 네트워크에 브로드캐스트됩니다. 모든 정직한 노드는 tx₂보다 먼저 tx₁을 수신하므로, 예상되는 최종 순서는 tx₁ → tx₂가 됩니다.
이 예에서 적대자는 tx₁에 더 늦은 타임스탬프(3)를 할당하고 tx₂에 더 이른 타임스탬프(2)를 할당하여 중앙값을 왜곡합니다.
프로토콜이 중앙값을 계산하는 경우:
tx₁의 경우 타임스탬프 (1, 1, 4, 4, 3)은 중앙값 3을 생성합니다.
tx₂의 경우 타임스탬프 (2, 2, 5, 5, 2)는 중앙값 2를 생성합니다.
tx₁(3)의 최종 타임스탬프가 tx₂(2)의 타임스탬프보다 크기 때문에 프로토콜은 tx₂ → tx₁을 출력하여 모든 정직한 노드에서 관찰되는 실제 순서를 반대로 합니다.
이 장난감 예제는 중요한 결함을 보여줍니다. 중간 함수는 중립적으로 보이지만 역설적으로 불공정성의 실제 원인입니다. 단 한 명의 부정직한 참가자라도 이를 악용하여 최종 거래 주문에 편향을 줄 수 있기 때문입니다.
결과적으로, 해시그래프가 자주 강조하는 "공정한 타임스탬핑"은 놀라울 정도로 공정성이 취약한 개념입니다. 해시그래프 합의 수신 순서의 공정성을 보장하지 못하며, 암호화 보장보다는 허가된 검증자 집합에 의존합니다.
실질적인 보장 달성
그러나 콩도르세가 보여준 이론적 불가능성을 회피하기 위해, 실제적인 공정한 순서 체계는 어떤 식으로든 공정성의 정의를 완화해야 합니다.
Aequitas 프로토콜은 블록 순서 공정성(BOF) 또는 배치 순서 공정성 기준을 도입했습니다. BOF는 충분한 수의 노드가 다른 트랜잭션 tx′보다 먼저 트랜잭션 tx를 수신할 경우, tx는 tx′보다 이전 또는 동시에 블록 에 전달되어야 한다고 규정합니다. 즉, 정직한 노드는 tx 이후 블록 에 tx′를 전달할 수 없습니다. 이는 ROF의 요건인 "이전에 전달되어야 함"에서 "이후에 전달되어야 함"으로 규칙을 완화합니다.
세 개의 합의 노드(A, B, C)와 세 개의 거래(tx₁, tx₂, tx₃)를 고려해 보겠습니다. 세 노드 중 최소 두 개(과반수)가 해당 거래를 먼저 관찰하면 해당 거래는 "이전에 수신된" 것으로 간주됩니다.
만약 우리가 세계 질서를 결정하기 위해 다수결 투표를 적용한다면:
tx₁ → tx₂ (A와 C가 합의)
tx₂ → tx₃ (A와 B가 합의)
tx₃ → tx₁ (B와 C가 합의)
이러한 선호도는 tx₁ → tx₂ → tx₃ → tx₁이라는 순환 고리를 생성합니다. 이 상황에서는 모든 사람의 의견을 동시에 만족시킬 수 있는 단일 주문이 없으므로, 엄격한 ROF를 달성하는 것은 불가능합니다.
BOF는 충돌하는 모든 트랜잭션을 하나의 일괄 처리 또는 블록 으로 묶어 하나의 트랜잭션을 다른 트랜잭션보다 먼저 처리하도록 강제하는 대신, 이를 해결합니다. 프로토콜은 다음과 같이 간단히 출력합니다.
블록 B₁ = {tx₁, tx₂, tx₃}
즉, 프로토콜 관점에서 세 거래 모두 동시에 발생한 것처럼 처리됩니다. 블록 내부에서 결정론적 타이브레이커(예: 해시 값)가 정확한 실행 순서를 결정합니다. 이를 통해 BOF는 모든 거래 쌍의 공정성을 보장하고 최종 거래 로그를 모든 사용자에게 일관되게 유지합니다. 각 거래는 이전 거래보다 늦지 않게 처리됩니다.
이 작지만 중요한 조정을 통해 프로토콜은 충돌하는 트랜잭션을 동일한 블록 이나 배치로 그룹화하여 트랜잭션 순서가 충돌하는 상황을 처리할 수 있습니다. 중요한 점은 모든 노드가 단일 선형 트랜잭션 시퀀스에 동의해야 하므로, 이로 인해 부분적인 순서가 발생하지 않는다는 것입니다. 각 블록 내의 트랜잭션은 실행을 위해 고정된 순서로 정렬됩니다. 이러한 충돌이 발생하지 않는 경우에도 프로토콜은 더 강력한 ROF(Return Of Transactions) 특성을 유지합니다.
Aequitas는 BOF를 성공적으로 달성했지만, 심각한 한계에 직면했습니다. 특히 통신 복잡성이 매우 높고 약한 활성도(weak Liveness) 만 보장할 수 있다는 점입니다. 약한 Liveness 는 거래의 전달이 해당 거래가 속한 Condorcet 사이클 전체가 완료된 후에만 보장됨을 의미합니다. 사이클이 "연쇄적으로 연결"될 경우, 이 과정에 지나치게 오랜 시간이 걸릴 수 있습니다.
테미스 프로토콜은 동일한 강력한 BOF 속성을 강화하기 위해 도입되었지만, 통신 복잡성은 개선되었습니다. 테미스는 배치 언스풀링, 지연된 순서 지정, 그리고 더욱 강력한 배치 내 보장이라는 세 가지 기술을 사용하여 이를 달성합니다.
표준 형태에서 Themis는 각 참여자가 네트워크의 다른 대부분의 노드와 메시지를 교환하도록 요구합니다. 필요한 통신량은 네트워크 참여자 수의 제곱에 따라 증가합니다. 그러나 최적화된 버전인 SNARK-Themis에서는 노드가 다른 모든 참여자와 직접 통신할 필요 없이 간결한 암호화 증명을 사용하여 공정성을 검증합니다. 이를 통해 통신 부하가 선형적으로 증가하도록 줄여 대규모 네트워크에서도 Themis를 효율적으로 확장할 수 있습니다.
합의 에 참여하는 다섯 개의 노드(A~E)가 tx₁, tx₂, tx₃라는 세 개의 트랜잭션을 수신한다고 가정합니다. 네트워크 지연 시간으로 인해 각 노드의 로컬 순서는 다음과 같이 다릅니다.
Aequitas에서처럼 이러한 선호도는 Condorcet 사이클을 생성합니다. 하지만 전체 사이클이 해결될 때까지 기다리는 대신, Themis는 배치 언스풀링이라는 방법을 사용하여 시스템이 계속 작동하도록 합니다. 이 방법은 사이클에 포함된 모든 트랜잭션을 식별하고 이를 강력 연결 구성 요소(SCC)라는 하나의 집합으로 그룹화합니다. 이 경우 세 트랜잭션은 모두 동일한 SCC에 속하며, Themis는 이를 Batch B₁ = {tx₁, tx₂, tx₃}라는 레이블이 붙은 진행 중인 배치로 출력합니다.
이를 통해 Themis는 Batch B₁의 내부 주문이 완료되는 동안에도 네트워크가 새로운 거래를 계속 처리할 수 있도록 합니다. 이를 통해 시스템이 계속 작동하고 지연을 방지할 수 있습니다.
개요:
거래 순서에서 완벽한 공정성이라는 개념은 간단해 보일 수 있습니다. 네트워크에 먼저 도달한 거래가 먼저 처리되어야 합니다. 그러나 콩도르세의 역설이 보여주듯이, 이러한 이상은 실제 분산 시스템에서는 성립할 수 없습니다. 서로 다른 노드는 서로 다른 순서로 거래를 보고 있으며, 이러한 관점이 충돌할 경우, 어떤 프로토콜도 타협 없이는 보편적으로 "올바른" 단일 시퀀스를 구축할 수 없습니다.
헤데라의 해시그래프는 중간값 타임스탬프를 사용하여 이러한 이상적인 방식을 구현하려 했지만, 이러한 접근 방식은 증명보다는 신뢰도에 더 의존합니다. 부정직한 참여자 한 명이 중간값을 왜곡하고 거래 순서를 뒤집어 "공정한 타임스탬핑"이 진정으로 공정하지 않음을 드러낼 수 있습니다.
Aequitas와 Themis와 같은 프로토콜은 달성 가능한 것과 불가능한 것을 명확히 구분함으로써 논의를 진전시킵니다. 불가능한 것을 쫓는 대신, 실제 네트워크 환경에서도 질서 무결성을 유지하는 방식으로 공정성을 재정의합니다. 여기서 드러나는 것은 공정성의 거부가 아니라 진화입니다. 이러한 진화는 인지된 공정성과 증명 가능한 공정성 사이에 명확한 경계를 그립니다. 이는 탈중앙화 시스템에서 진정한 거래 순서 무결성은 평판, 검증자 신뢰 또는 허가된 제어에 의존할 수 없음을 보여줍니다. 프로토콜 자체에 내장된 암호화 검증을 통해 얻어져야 합니다.
본 기사에는 투자 조언이나 추천이 포함되어 있지 않습니다. 모든 투자 및 거래는 위험을 수반하며, 독자는 결정을 내리기 전에 스스로 조사해야 합니다.
본 기사는 일반적인 정보 제공을 목적으로 작성되었으며, 법률 또는 투자 자문으로 해석되어서는 안 됩니다. 본 기사에 표현된 견해, 생각, 의견은 저자 개인의 것이며, 코인텔레그래프의 견해와 의견을 반드시 반영하거나 대표하는 것은 아닙니다.
코인텔레그래프는 본 기사의 내용이나 여기에 언급된 어떤 상품도 보증하지 않습니다. 독자는 언급된 상품이나 회사와 관련하여 어떠한 조치를 취하기 전에 스스로 조사해야 하며, 자신의 결정에 대한 전적인 책임을 져야 합니다.
