Transaction Ordering Rule

(Summary) CTOR이 적합한 이유

• Block emission is more efficient (블록 배출시 더 효율적)

• Block propagation is more efficient (블록 전파시 더 효율적)

• Software implementations are simplified (소프트웨어 구현의 단순화)

• Proofs of transaction inclusion are improved (트랜잭션 포함 증명이 향상됨)

• Opt-in locality between participants becomes possible (참여자 간의 지역 선택이 가능해짐)

• Potential attack vectors are mitigated (잠재적인 공격 경로의 완화)

• Block Validation

• Transaction Ordering

1. Block Validation의 변화

for tx in transactions:
    remove_utxos(tx.inputs)
    add_utxos(tx.outputs)

1-1. 동시 유효성검사(concurrent validation)의 필요성

• TTOR이 정확하게 되고 있는지 확인하는 추가적인 코드가 필요하게 된다. → TTOR은 동시 유효성검사에 방해가된다.

• 최악의 경우 하나의 스레드만이 활성화된다.(종속 트랜잭션들이 길게 연결된 블록일 경우)

1-2. 동시 유효성검사를 위한 변화 - OTI

• 트랜잭션의 순서와 관계없이 처리 가능해짐.

• 하나 대신 두 개의 반복문을 사용하여도 성능이 특별히 더 나빠지지 않음.

• O(log2(n))를 전송하는 정렬된 세트를 유지

• embarrassingly parallel: 병렬 작업간에 의사소통이나 결과에 대한 의존성이 없음

for tx in transactions:
    add_utxos(tx.outputs)
for tx in transactions:
    remove_utxos(tx.inputs)

2. 트랜잭션 정렬 규칙의 변화

2-1. TTOR(topological trasaction ordering rule)

2-2. CTOR(Canonical Transaction Ordering Rule)으로의 변화

• 표준 정렬 규칙을 갖게됨 (canonical:표준의)
비트코인 캐시는 2018년 11월 하드포크 때 CTOR(Canonical Transaction Ordering Rule)으로 변경.
모든 블록 내의 트랜잭션의 순서가 고정되어 오직 하나의 유효한 ordering rule을 가지며, 이후 이 정렬 규칙을 벗어나는 블록은 무효한 것으로 간주된다.

• txid 기반의 사전식 정렬
이 하드포크에 의해 선정된 표준 정렬(canonical ordering)은 사전식 정렬(dictionary ordering,lexicographic)으로, 맨앞에 와야하는 coinbases를 제외하고는 트랜잭션 ID를 기준으로 정렬한다.
• 예시 : txid가 첫번째 순서여야하는 코인베이스를 제외하고 사전식 순서로 정렬되어있음을 확인 가능.
• "coinbase first, then ascending lexicographic order based on txid".

• Any Ordering Rule(AOR): 정렬 제한을 없애는(코인베이스 제외) 규칙
AOR은 실제 적용된 것은 아니지만, TTOR에서 CTOR로 전환하기 위한 두 단계에서 나타난다.
1. (TTOR→AOR) : 인과적 정렬 규칙 제거 (removing the old causal rule.)
2. (AOR → CTOR) : 모든 블록의 트랜잭션 정렬 방법을 고정하는 새로운 규칙 추가 (adding a new rule that fixes the ordering of all transactions in the block.)
실제로는 one step 이나, 다른 요소들이 이 변화에 영향을 받는 방식을 명확하게 하기위해 두 단계로 나누어서 설명할 수 있다. 예를 들어, 1단계까지만 진행된 AOR상태는 CTOR추가 전이지만, OTI알고리즘을 추가하여 유효성 검사의 병렬처리가 가능한 상태를 의미한다.

2-3. CTOR 도입의 장점

• CTOR은 TTOR보다 구현이 간단하다.(특정 순서를 확인하는 것보다, 유효한 순서가 존재한다는 것을 증명하는 것이 더 쉽다.)

• 블록 템플릿 생성 시간이 줄어든다.(과거에는 마이너가 트랜잭션의 유효한 순서를 확인하는 CPFP코드가 블록 템플릿 생성 시간의 약 70퍼센트를 차지했으므로, 블록 템플릿 생성 시간이 줄어들 것이다.)

• 블록 전파(Block propagation) 과정이 매우 쉬워진다.
• 블록전파에서 스트레스 테스트 동안 20mb이상의 큰 블록에서는 네트워크를 통해 전파되기위해 몇분이 걸릴것이고, 전파 지연은 마이닝 인센티브와 경제를 복잡하게 하는 고아블록률의 증가로 이어진다.
• 데이터 모델을 집합(순서 정보가 필요 없음)으로 간소화함으로써 set reconciliation이라 통칭되는 알고리즘을 블록체인으로 가져온다. 이로써 효율적인 블록 전파를 적용할 수 있게 된다.(예 : Graphene) 이러한 결과는 참가자가 대역폭 용량을 최대한 활용하고 새로운 블록을 방출하기 전에 가능한 한 많은 정보를 전파 할 수 있기 때문에 중요하다.
• Graphene에서 TTOR을 유지하면서 정렬 정보의 크기를 줄이려면, 채굴자는 트랜잭션 정렬 방법을 canonical ordering으로 선택해야하며, graphene 프로토콜은 하드코딩되어 이런 종류의 순서가 1 byte로 전송될 수 있다. 그러나 graphene이 순서를 감지하고 재구성 할 수 있어야 하므로 상당한 기술적 부담을 더한다. 순서를 재구성하는 정렬 알고리즘이 효율적으로 병렬화 가능할 것인지는 분명하지 않다.
• CTOR의 적용은 이 모든 것에서 쉬운 해결방안이다. 오직 하나의 순서만 존재하므로 순서 정보가 필요 없다. 또한 토폴로지 정렬보다 비교정렬을 통해 병렬적으로 복구되기가 더 좋다. graphene의 코드베이스를 단순화하며, 다양한 정렬 인코딩 지원을 고려할 필요성을 제거하고, 메커니즘 최적화에 집중할 수 있다.

• 전체 블록을 처리하지 않고 트랜잭션을 찾았는지 여부를 식별 할 수있는 가능성을 제공한다. 체인이 없는 소프트웨어일 경우 유용하다.

• non-deterministic block validation time as attack vector(공격 벡터의 비결정적 블록검증시간)에 대처가 가능해진다.
• 악의적인 마이너가 블록을 게시할때 검증이 느린 트랜잭션 순서를 사용하는 공격 가능성을 제거한다.

• 참여자간의 지역 선택이 가능해진다. (아래 확인)

• 블록 유효성 검사에서 중간 상태에 대해 걱정할 필요 없다. CTOR은 블록 검증을 완벽하게 병렬으로 보장한다.
• 이더리움의 확장성은 많은 중간 단계를 갖는 어려움을 겪는다. 모든 트랜잭션 마다 부분적으로 상태를 저장하여, embarrassingly parallel을 불가능하게 한다.
→ 사실 embarrassingly parallel은 CTOR 하드포크 없이 OTI 만으로도 가능하지만 CTOR의 적용은 미래를 위한 것이다. (아래 확인)
 

참여자간의 지역 선택

3. 전망

• 가까운 장래 : 블록검증을 위한 성능 차이를 보여주지는 않을 것이나(현재 블록유효성 검사는 bitcoin cash의 제한 요소가 아니므로), graphene 프로토콜을 간단하고 즉각적으로 향상 시킬 수 있다. 이는 (블록 전파)스케일링 병목현상에 영향을 미친다.

• 중기적 : 동시처리로 전환하려는 소프트웨어는 OTI와 같은 임의 순서 알고리즘을 사용하려고 할 것이다. 동시 유효성 검사에서 순서 지정 규칙을 적용하기 위해 일부 코드 추가가 필요할 수 있지만, TTOR/ AOR / CTOR의 성능차이는 여전히 존재하지 않는다.

• 장기적 : 이것을 신경 쓰기에는 너무 이르지만, sharded UTXO 데이터베이스를 가진 전체 노드에는 CTOR가 이점을 보여줄수 있다.
• 비트코인 캐시 블록의 크기가 커지면서, 언젠가는 샤딩을 포함한 고급 서버 아키텍처로의 확장이 필요할 것이다. 이 규모에서는 TTOR이 도움되지 않을것이며, CTOR은 성능 최적화로 이어질수도, 아닐수도 있으며, 더 나은 트랙잭션 정렬 방식이 발견되어 적용 될 수도 있다.

가역성과 기술적 부채(Reversibility and technical debt)

4. bitcoin ABC 코드의 변화

src/validation.cpp : 트랜잭션 정렬의 주된 변화

• ConnectBlock 함수
• 이전엔 하나의 loop를 가짐: 각 트랜잭션을 순서대로 처리하고 소비된 트랜잭션 출력을 삭제, 새로운 트랜잭션을 추가하는 반복문, TTOR과만 호환
• 하드포크이후 : 2개의 loop OTI 알고리즘을 사용하며, 정렬 조건이 없다.

• ApplyBlockUndo 함수 : 고아 블록을 취소하기 위해 사용되는 함수
• 어떤 순서로든 정렬하며 작업하도록 변경

• ContextualCheckBlock 함수
• direct check on sorting order을 포함하게 되었다. (CTOR을 시행하는 유일한 코드)

mining(src/mining.cpp)

• CreateNewBlock 함수는 트랜잭션을 CTOR에 따라 정렬한다.

src/txmempool.cpp

• 고아 블록이 되었을때, 해당 블록의 트랜잭션은 addForBlock 함수를 사용하여 mempool로 돌아간다.

References