Repository navigation
Amendment Proposal: Canonical Transaction Ordering #679
donovanhide
started this conversation in
XLS Proposals
Replies: 1 comment
|
Going to add this here, but I think looking at the ordering like in this XLS puts the ledger in a better place than simply fixing the issue that batch highlights. Batch-specific hardening - Change how Batch transactions are ordered (incorporate inner accounts / BatchSigners into the sort key) or increase the cost of failed outer Batches. This directly attacks the amplification vector that makes the current exploit cheap. I prefer the addressing this lower down than simply at the batch level. But left for completeness. |
0 replies
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
Canonical Transaction Ordering
1. Abstract
When$(A \oplus S) \oplus (B \oplus S) = A \oplus B$ . This algebraic invariant leaks relative transaction proximity prior to consensus close and is actively exploited on XRPL Mainnet using offline vanity
xrpldapplies a consensus transaction set to build a validated ledger,CanonicalTXSetorders transactions by a 3-tuple(accountKey, seqProxy, txID). AlthoughCanonicalTXSetis seeded with a 256-bit consensus salt (SetHash, the SHAMap root hash of the agreed transaction set),CanonicalTXSet::accountKeycombines the 20-byteAccountIDwith that salt using bitwiseXOR. BecauseXORis linear and has zero bit diffusion (no avalanche effect), the XOR difference between any two accounts is invariant under every possible salt:AccountIDtables to perform surgical front-running, back-running, sandwiching, and keyspace-spanning attacks.This specification proposes the$K$ funded accounts in the same ledger (see §9. Limitations and Non-Goals).
CanonicalOrderingamendment (featureCanonicalOrdering), which replaces theXORinCanonicalTXSet::accountKeywith a fast, dependency-free keyed pseudorandom function (SipHash-2-4over the 20-byteAccountIDkeyed by the consensus salt, followed by the 160-bitAccountIDas a collision-free tie-breaker).CanonicalOrderingcompletely eliminatesAccountIDprefix-grinding and deterministic adjacency advantages, ensuring that any two distinct accounts sort independently and uniformly across the ledger; however, it does not prevent an actor from probabilistically sampling multiple random positions by submitting transactions from2. Motivation
2.1. Current
CanonicalTXSetOrdering MechanicsDuring consensus ledger close (
RCLConsensus.cpp),xrpldconstructs aCanonicalTXSetinitialized with the 256-bit hash of the agreed transaction SHAMap (SetHash). Each transaction is inserted into a sorted tree underCanonicalTXSet::Key:accountKey(UInt256): Computed inCanonicalTXSet.cppby copying the 20-byteAccountIDinto the upper 20 bytes of a zeroed 32-byteUInt256buffer (beast::kZero) and XORing the buffer with the 32-bytesalt_:seqProxy(SeqProxy): The transaction'sSequenceorTicketSequence, ensuring that multiple transactions originated by the same account execute in sequence/ticket order.txID(UInt256): The transaction hash as a final tie-breaker.The design intent of
salt_(exposed viakey()and initialized withSetHash) is clear: becauseSetHashdepends on the entire set of agreed transactions in the ledger, it is unknown while independent transactions are being submitted to the open ledger, preventing a single static account from grinding anAccountIDthat always sorts first.2.2. The Vulnerability:
XORIs an MSB Prefix IsometryWhile$S$ , it completely preserves the relative distance between any two accounts $A$ and $B$ :
XORhides the absolute position of a single account under an unknown saltSpecifically, under big-endian lexicographical comparison (
base_uint::compare):k-Bit Prefix):If account
Suppose
Because
XORpermutes them-bit prefixes bijectively, a set ofm-bit prefixes (000...through111...) is guaranteed (100%) to place exactly one account into each2.3. Amplification by XLS-56 (
Batch) and Same-Ledger JIT Account CreationTwo protocol features turn this mathematical property into a low-reserve, surgical exploit:
BatchFee-Payers (BatchSigners):Under XLS-56 (
Batch),CanonicalTXSetorders an outerBatchtransaction solely by its outer fee-payer (batch.Account), ignoring the innerRawTransactionsaccounts andBatchSigners. An arbitrage bot can keep all of its trustlines, tickets, and capital (orChecks) on a single permanent worker accountWand wrap the same innertfAllOrNothingtransactions (referencing the same inner tickets onW) inside multiple outerBatchtransactions submitted by throwaway vanity fee-payer accountsBatchsigning (serializeBatch) commits to the outerAccountandSequence,Wco-signs each outerBatchcopy separately viaBatchSigners:Batchwhose fee-payertesSUCCESS), while its innertfAllOrNothingtransactions fail theirDeliverMin/ price check (tec) and are discarded, leavingW's inner tickets unspent (seeidx 370in §2.4).Batchwhose fee-payerW's inner tickets.Batchalso recordstesSUCCESSat the outer level while its inner transactions fail inner ticket validation (tefNO_TICKET) and are discarded. Each outerBatchpays(2 + inner transactions + signers)fee units—for 5 inner transactions and 1BatchSigner, that is 8 fee units (80drops at the 10-drop minimum fee, or128drops at the bot's chosen 16 drops/unit).Maintaining
524,288 XRPin base reserves. Instead, attackers pre-compute16 MB,0 XRPreserve cost) and pre-mine deep 35–39 bit unfunded vanity pools against known high-volume market-maker addresses.When a target transaction from victim
transactions_proposedin ledgerL):1.0005 XRP(1.0 XRPbase reserve +500drops fee budget) to each00× 1,01× 3,10× 1,11× 1), and simultaneously broadcasts outerBatchtransactions fromSequence = Lin the same ledgerL.BatchfromterNO_ACCOUNTin Pass 0, remains inretriableTxs, and executes in Pass 1 after the funder's Pass-0Paymentcreates theAccountRootforSequence = L.2.4. Empirical Mainnet Evidence (Ledger
107855382)In XRPL Mainnet ledger
107855382, a retail account (r4NWb5AVMRBQaxYiUZzsYyz6ZiSBmHQ6a9) submitted aPayment(SendMax: 2,000 XRP) buyingXTOatTransactionIndex: 371, while a market maker (rBTwLga3i2gz3doX6Gva3MgEV8ZCD8jjah) was updating offers in the surrounding ledgers107855381(Sequence: ...768) and107855383(Sequence: ...769).In that single ledger (
107855382), 6 JIT-funder accounts (rh6o...,rfrW...,rwLm...,r9oU...,rNnn...,rJbL...) submitted 42Paymenttransactions of1.0005 XRP, creating 26 brand-new vanity accounts on the fly (CreatedNode: AccountRoot,Sequence: 107855382):Target 1: Bracketing Retail Victim
r4NWb5AVMRBQaxYiUZzsYyz6ZiSBmHQ6a9(idx 371)AccountID([0..4])AccountID107855382Executionr4NWb5AVMRBQaxYiUZzsYyz6ZiSBmHQ6a9e8e8c1b6...11101000 11101000 11000001idx 371(2,000 XRP -> XTO)r4NW5BrKyqXv8WLLdWpbf9MvrhXatj6Xkoe8e8d979...11101000 11101000 11011001idx 108;Batchatidx 370(inner txs discarded)r4NWkTAZYLgywnFfCGZybfpSjBN7s4CVP1e8e8e1eb...11101000 11101000 11100001idx 319;Batchatidx 372(WON+1,729.77 XRP)r4NWVPFRwvxnVcxbg6qavK9Xqo9nxn8KESe8e8aa64...11101000 11101000 10101010idx 109;Batchatidx 378(inner txs discarded)r4NWPJcEE1726XJBLj3YvLsuYuenTejyCke8e893f4...11101000 11101000 10010011idx 157r4NWrEpTxdX3TRAp7RRcFWHgHeh2KDD7P5e8e842ab...11101000 11101000 01000010idx 158r4NXdMTTammzigiFW6ngSYEjTgEWWwNJzBe8e99d6a...11101000 11101001 10011101idx 250Target 2: Deep 35–39 Bit Vanity Pool Against Market Maker
rBTwLga3i2gz3doX6Gva3MgEV8ZCD8jjahIn the same ledger (
107855382,idx 110..324, withidx 325topping up an already-existing account), the same 6 funders created 20 accounts (rBTwLgafyPYqr5SdQsygHVKHW9CBYkjBJe,rBTwLga3KhxkoenRmdZDPwwQxRXQ3sfMgA,rBTwLga39rpx2HFraoWEzfAkGPU3xvu5oj, etc.) sharing 35 to 39 bits (72a3de6b0...) withrBTwLga3i2gz3doX6Gva3MgEV8ZCD8jjah(72a3de6b0973...). In the very next ledger (107855383), two more JIT-funded vanity accounts sharing 36 bits (rBTwLgasqa1MJfks2QW5gAZeZhqqQBzuc1atidx 182) and 35 bits (rBTwLgaP4DoR3itCz3VmSnSVQL3LbzrDDfatidx 185) bracketedrBTwLga3i2gz3doX6Gva3MgEV8ZCD8jjah'sOfferCreateatidx 183.Additional on-chain examples of this vanity-prefix ordering exploit—specifically targeting new AMM pool launches (
r4PCdxLajHQ...,rNdzqzavK9...,rsxiNgEqM...) to deterministically snipe the first buy position—were also independently reported in XRPL-Standards Discussion #670.3. Specification
This amendment (
CanonicalOrdering/featureCanonicalOrdering) does not introduce or modify any serialized types (SType), ledger entry types, transaction types, permissions, or RPC methods. It modifies only the consensus transaction-set ordering key computation inCanonicalTXSet::accountKey.3.1. Requirements for
CanonicalTXSet::accountKeyTo eliminate prefix-matching and keyspace-spanning exploits while preserving
CanonicalTXSetinvariants, the replacementaccountKey(account)function MUST satisfy:salt_(SetHash), any two distinct accountsCanonicalTXSetgroups transactions byaccountKeyso that same-account transactions execute inSeqProxyorder, two distinct 20-byteAccountIDs MUST NOT produce the same 256-bitaccountKey.3.2. Construction:
SipHash-2-4+AccountIDTie-BreakerWhen the
CanonicalOrderingamendment (featureCanonicalOrdering) is enabled,CanonicalTXSet::accountKeyMUST compute a 64-bitSipHash-2-4digest of the 20-byteAccountIDkeyed by the first 128 bits ofsalt_(SetHash), place that 64-bit digest in the most significant 8 bytes (big-endian) of the 256-bit key, and copy the raw 20-byteAccountIDinto bytes8..28(with bytes28..32zeroed):0..8(uint64big-endian): The 64-bitSipHash-2-4output provides 64 bits of cryptographically avalanched ordering keyed by the consensus salt.8..28(20 bytes): The raw 20-byteAccountIDguarantees strict injectivity, ensuringSipHash-2-4prefix.28..32(4 bytes):0x00000000.3.3. Exact
SipHash-2-4Parameterization for 20-ByteAccountIDLet
saltbe the 32-byteCanonicalTXSetsalt (salt_), and letaccountbe the 20-byteAccountID:uint64):AccountIDwith Standard SipHash Length Padding):0x14) into the most significant byte (bits56..63) of the final 64-bit wordaccount[16..20]) in bits0..31and zeros in bits32..55, follows the standard SipHash padding specification withAccountIDis fixed at 20 bytes, retaining(20 << 56)ensures that this construction is 100% bit-for-bit compatible with standardSipHash-2-4libraries across all languages.SipRoundsSipRounds4. Rationale
4.1. Why
SipHash-2-4Over Non-Cryptographic Hashes (xxHash,MurmurHash3,wyhash)xrpldalready includesXXH3_64bits(beast::Xxhasher) for in-memory hash tables. However, non-cryptographic or universal hashes (xxHash,MurmurHash3,wyhash,CityHash) MUST NOT be used forCanonicalTXSet::accountKey. Because they are not cryptographic PRFs, they exhibit seed-independent (universal) differentials or linear structure that allow offline solvers to construct pairs ofAccountIDs that collide or remain adjacent across a high fraction of salts, or to recover key bits when hash ordering is publicly observable (see §1 and §7.3–§7.4 of Aumasson & Bernstein).SipHash-2-4was specifically designed as a fast, short-input cryptographic PRF with a 128-bit key and zero key-expansion overhead ("key agility", §1 and §3 of Aumasson & Bernstein). Because a 64-bit PRF is not itself collision-resistant (§3), appending the 20-byteAccountIDin bytes8..28provides unconditional 256-bit injectivity.4.2. Why
SipHash-2-4+AccountIDTie-Breaker Oversha512HalfAn alternative cryptographic construction using an existing
xrpldprimitive issha512Half(salt_, account)(first 256 bits ofSHA-512over the 32-byte salt and 20-byteAccountID). Both constructions satisfy the cryptographic PRF requirement, andsha512Halfis a viable alternative if reusing OpenSSL'sSHA-512is preferred over adding ~40 lines of inlineSipHash-2-4arithmetic. However,SipHash-2-4followed by the 20-byteAccountIDoffers three advantages:sha512Halfproduces a 256-bit digest with aAccountIDin bytes8..28guarantees zero collisions, sinceSipHash-2-4on a fixed 20-byte input has a theoretical lower bound of 49 cycles on a 3-ALU core (§6.1 of Aumasson & Bernstein) and executes with a single-call serial latency of~13–15 ns(~60 CPU cycles on Apple M4 Max) in 4 scalar registers with zero branches and zero OpenSSL EVP context overhead, compared to~100 nsforsha512Half.SipHash-2-4algorithm for a 20-byte input is 40 lines of standard integer arithmetic (ADD,XOR,ROL), making cross-language consensus implementations trivial to verify.4.3. Why Direct Computation Over
std::unordered_mapMemoisationBecause an account may submit multiple transactions in the same ledger, one might consider memoising
accountKey(account)in a per-ledgerstd::unordered_map<AccountID, UInt256>. In practice, memoisation is slower and more complex than direct computation:SipHash-2-4directly on 20 bytes takes 10SipRounds in 4 CPU registers (~13–15 nsserial latency, or~4.6 nspipelined throughput) with zero heap allocations.AccountIDinstd::unordered_maprequires hashing the 20-byteAccountIDanyway (XXH3_64bits) to find the bucket, chasing a heap node pointer on hits, and callingoperator new(malloc) plusSipHash-2-4on every first-seen account in the ledger (~25–30 nsaverage per transaction across a ledger with 60% unique accounts, plus hundreds of heap allocations per ledger).4.4. Scope of Fix: Closing the
AccountIDPrefix ChannelWhile XLS-56 ($K$ funded accounts to sample $K$ random positions—are detailed in §9.
Batch) fee-payer wrapping and same-ledgerPaymentaccount creation amplify the profitability of prefix grinding, the root cause of the prefix-matching exploit is the linearity ofXORinCanonicalTXSet::accountKey. ReplacingXORwith a keyed PRF removes theAccountIDprefix-matching and deterministic keyspace-partitioning channel for all transaction types without restricting legitimateBatchsponsorship or account creation workflows. Residual vectors that do not rely onAccountIDprefix grinding—such as submitting transactions from5. Backwards Compatibility
Because
CanonicalTXSetdetermines the execution order of transactions when validators and nodes build a new ledger from an agreed consensus transaction set (RCLConsensus.cpp), changingCanonicalTXSet::accountKeyis consensus-critical and MUST be gated behind theCanonicalOrdering(featureCanonicalOrdering) amendment:CanonicalOrderingactivation: Consensus ledger construction MUST preserve the legacyXORbehavior (ret ^= salt_) inCanonicalTXSet::accountKeyso all nodes agree on transaction execution order.CanonicalOrderingactivation: Consensus ledger construction MUST pass the amendment state (prevLedger.ledger->rules().enabled(featureCanonicalOrdering)) toCanonicalTXSetso thatCanonicalTXSet::accountKeyuses theSipHash-2-4construction (§3.2–§3.3).buildLedger(LedgerReplay const&, ...)inBuildLedger.cpp) applies transactions in their recordedorderedTxns()sequence and does not useCanonicalTXSet. Similarly,LedgerMaster::heldTransactions_is a local open-ledger retry buffer salted with the publicparentHashrather than a consensus structure, and is not governed by this amendment.6. Test Plan
6.1. Deterministic Unit Test Vectors
Implementations MUST verify
CanonicalTXSet::accountKeyagainst the following test vectors using the 32-byte salt:and the four Mainnet accounts from ledger
107855382(§2.4):AccountIDHexXORKey ([0..8])SipHash-2-4accountKey(32 Bytes)r4NWb5AVMRBQaxYiUZzsYyz6ZiSBmHQ6a9)e8e8c1b68723f539309d7b18a42fed80c51fd68672d7bd989c6e756f...9da98777e6e2781ae8e8c1b68723f539309d7b18a42fed80c51fd68600000000r4NW5BrKyqXv8WLLdWpbf9MvrhXatj6Xko)e8e8d979bd6ed3e584193a8d7b5ba25fe593f1b372d7a557a62353b3...48c4605177a7d6fce8e8d979bd6ed3e584193a8d7b5ba25fe593f1b300000000r4NWkTAZYLgywnFfCGZybfpSjBN7s4CVP1)e8e8e1eb952274c814dfe8b700f3bc5467ff2f7c72d79dc58e6ff49e...f4f6d66436882cace8e8e1eb952274c814dfe8b700f3bc5467ff2f7c00000000r4NWVPFRwvxnVcxbg6qavK9Xqo9nxn8KES)e8e8aa643ef38520f812a0e3dd1c8a3fb136f39472d7d64a25be0576...d9c1f535e7857949e8e8aa643ef38520f812a0e3dd1c8a3fb136f39400000000Notice how under legacy
XOR, all four accounts remain clustered inside the narrow 17-bit prefix72d7..., whereas underSipHash-2-4their 64-bit prefixes (48c4...,9da9...,d9c1...,f4f6...) are uniformly dispersed across the 256-bit keyspace.6.2. Implementation Test Suite (
CanonicalTXSet_test.cpp)The
xrpldunit test suite MUST include:CanonicalTXSetconstructed withcanonicalOrdering = falseproduces the legacyXORordering, and withcanonicalOrdering = trueproduces theSipHash-2-4ordering matching the §6.1 test vectors.AccountID(with varyingSequenceandTicketSequencevalues, as well aspopAcctTransaction) continue to execute strictly inSeqProxyorder whencanonicalOrderingis enabled.SetHashsalts is uniformly distributed rather than invariant.7. Reference Implementation
In
include/xrpl/ledger/CanonicalTXSet.h, add abool canonicalOrdering_ = falsemember initialized by the constructor:In
src/xrpld/app/consensus/RCLConsensus.cpp, pass the amendment state when constructingretriableTxs:CanonicalTXSet retriableTxs{ result.txns.map->getHash().asUInt256(), prevLedger.ledger->rules().enabled(featureCanonicalOrdering)};In
src/libxrpl/ledger/CanonicalTXSet.cpp, implementCanonicalTXSet::accountKeyusing alignment- and aliasing-safeboost::endianloads (base_uintis 4-byte aligned, soreinterpret_cast<std::uint64_t const*>must not be used):8. Security Considerations
8.1. Ordering Probabilities: Legacy
XORvs.SipHash-2-4Consider a target transaction from victim account$V$ in a ledger containing $N$ other independent accounts (e.g., $N = 590$ in ledger $K$ distinct accounts $B_1, \dots, B_K$ :
107855382), where an attacker submits transactions fromXOR(with Offline Prefix Table)SipHash-2-4idx V ± 1):Specifically:
XOR, choosingSipHash-2-4, the sort keys ofXORrequires submittingSipHash-2-4.idx V ± 1) Drops fromSipHash-2-4, allAccountIDprefixes no longer correlate withaccountKeyproximity, JIT-funding a vanity account matching a victim'sAccountIDprefix confers zero positional advantage over using any existing pre-funded account.8.2. Denial-of-Service and CPU Overhead
CanonicalTXSet::accountKeyis called once perinsert(and once perpopAcctTransaction) onCanonicalTXSet.~13–15 ns(~60 CPU cycles) of single-call serial latency, a ledger containing2,000transactions incurs~30 microseconds(0.03 ms) of total CPU time—less than0.001%of a 3.5-second ledger window, with zero heap allocations.CanonicalOrderingintroduces no denial-of-service vector during consensus ledger application.9. Limitations and Non-Goals
CanonicalOrderingis a targeted cryptographic fix forCanonicalTXSet::accountKey. It eliminates zero-cost offlineAccountIDgrinding and deterministic adjacency, turning transaction ordering into a uniform random permutation across accounts. However, implementers and users should understand what this proposal does not prevent:9.1. Probabilistic Multi-Account Position Sampling ("Sybil / Account Spam")
Replacing$K$ ordinary pre-funded accounts (requiring $K \times 1\text{ XRP}$ in base reserves) and submit $K$ transactions in the target ledger:
XORwithSipHash-2-4does not make front-running or back-running impossible. Instead of farming special vanityAccountIDs offline to guarantee adjacency, a well-capitalized actor can maintainSipHash-2-4reduces their competition to a lottery proportional to transaction count (FeeEscalation).9.2. Risk-Free Multi-Submission Amplification via XLS-56 (
Batch)As described in §2.3, XLS-56 ($K$ distinct outer fee-payer accounts to wrap the exact same inner
Batch) orders an outerBatchtransaction solely by its outer fee-payer (batch.Account), and allowstfAllOrNothingtrade co-signed by a single worker accountWusing a shared innerTicketSequence:CanonicalOrdering, an attacker can still submitBatchtransactions fromDeliverMin/ limit guard such that inner transactions fail with ateccode beforetefNO_TICKETafter the first winningBatchexecutes afterBatchtransactions cost only their outerBatchtransaction fees (CanonicalOrdering: MitigatingBatchmulti-submission amplification requires changes toBatchsemantics—such as deriving aBatchtransaction'sCanonicalTXSetsort key from the union of itsBatchSigners/ innerAccounts, or burning inner tickets / charging higher fees on failedBatchexecutions—which are orthogonal to theCanonicalTXSet::accountKeyPRF construction and should be evaluated in a separateBatch-specific proposal.9.3. Two-Pass (
ter) Execution DeferralWhen
xrpldapplies a consensus transaction set (BuildLedger.cpp), transactions that return a retryableterresult in Pass 0 (terNO_ACCOUNT,terPRE_SEQ,terPRE_TICKET) remain inretriableTxsand are re-applied in Pass 1. An actor who intentionally structures a transaction (or a funding + spending pair across two accounts) so that the spending transaction returnsterin Pass 0 and executes in Pass 1 can still guarantee execution after all Pass-0 transactions, regardless of howCanonicalTXSet::accountKeyis hashed.9.4. Low-Entropy Consensus Salt Grinding
SipHash-2-4takes a 128-bit keySetHash. BecauseSetHashis a deterministic digest of the agreed consensus transaction set rather than an external threshold random beacon, its unpredictability is bounded by the entropy of the other transactions arriving during the ledger window. During normal Mainnet activity with hundreds of concurrent independent transactions,SetHashis unpredictable at submission time; however, on an otherwise empty or completely static ledger, an actor could grind their own transaction fields offline to influenceSetHash.10. Acknowledgements
The author thanks Google Argon and Anthropic Claude for their contributions to the empirical on-chain forensic analysis, cryptographic construction evaluation, test vector verification, and specification drafting.
All reactions