This proposal describes an alternative to Tickets for solving the problem of one transaction blocking another due to the sequence number ordering.
Instead of preemptively designating account sequence numbers to be used at a later time (using tickets), XRP Ledger can allow account transactions to happen out of sequence order.
The most important role of the Sequence number is that it makes each transaction on an account unique.
We can ensure that no sequence number is used more than once by storing what sequence numbers have been skipped for an account. An account would have:
- An account sequence representing the highest validated transaction sequence number + 1
- An optional (ordered) array of pairs of sequence numbers. Each pair represents a range of skipped sequence numbers
Example: account rABC has had transaction sequences 1, 2, 4, 8, 16 validated. Its account sequence is 17. Its list of skipped sequence numbers contains the following ranges (low, high):
- (3, 3)
- (5, 7)
- (9, 15)
When processing new transactions, rippled's checkSeq logic would check that the transaction section is either >= the account sequence or falls within one of the ranges of skipped sequences.
The following pseudo code describes the effects of a new transaction on the account's sequence-related data:
if (txSeq == accountSeq)
++accountSeq
else if (txSeq > accountSeq) {
accountSeq = txSeq + 1
addSkippedSeqRange(accountSeq /*low*/, txSeq-1 /*high*/)
}
else // txSeq < accountSeq (accountSeq remains unchanged)
removeSkippedSeq(txSeq)
removeSkippedSeq can result in adjusting the low or high of a range, splitting one range into two ranges, or deleting a range (and possibly the entire list of ranges).
Example (continued): account rABC has transactions with sequences 3, 7, 13, 17, and 19 validated in a single ledger (they're applied in sequence order). The account sequence would then be 20. The skipped ranges would be:
- (5, 6)
- (9, 12)
- (14, 15)
- (18, 18)
The account's reserve could be raised for each range of skipped sequences stored in the list.
Because this would be bad news for anyone who has signed a transaction with an seemingly impossibly high sequence (without specifying a LastLedgerSequence), this should probably be opt-in via an account root flag and/or transaction flag. Users who opt in but care about transaction ordering can utilize AccountTxnId.
How
Ranges of skipped sequences can be implemented very similarly to SignerLists.
The SignerList ledger object has an array (sfSignerEntries) of objects (sfSignerEntry), which consist of sfAccount and sfSignerWeight.
The optional sfSkippedSeqs on an account root could be an array of objects, which consist of range start and range end values.
See: https://github.com/wilsonianb/rippled/commit/8ce111081ecbc4926b1c3bbceafcbca14ba7bf07
SignerLists' reserve requirements could also be used here.
Just as SignerLists are limited to a maximum of eight entries, an account's number of ranges can be limited to whatever size array we're comfortable searching and modifying. Limiting the number of ranges also ensures a maximum possible reserve requirement for having skipped sequences.
Open Questions
How to store skipped ranges?
- in an array (with a maximum size)
- if so, what maximum size should be used?
- Is it ok to search the array twice? (in both checkSeq and setSeq)
- a better data structure (such as B+ tree) that would be more complex to implement
How to opt in?
- account flag - one time, but makes a previously signed tx with a high sequence (and without LastLedgerSequence) be valid
- transaction flag - obvious which transactions can cause reserve to increase, but requires forethought (unless you just set
- that flag on all your transactions, in which case why not just set an account flag)
- new transaction that can specify the number of allowed skipped ranges
- if so, should the reserve automatically be raised to (cost per range * maximum number of allowed ranges) to avoid confusing user with reserve rules (at the risk of disincentivizing opting in due the high reserve requirement).