NETSoon

Docs Protocol

Ordering and selection

Algorithm 4. How the transactions of all accepted blocks of a slot become one order, and how a deterministic four-track schedule decides which of them execute.

No proposer orders a slot. Every validator takes the transactions of the slot's accepted blocks, removes duplicates, sorts them by one fixed rule and fills a virtual execution schedule with them. Every validator gets the same xblock, and the proposers have no say in it. To get ahead of a transaction, one has to outbid it.

Removing duplicates

A user may send one transaction to several proposers (n > 1), or resend it to a later window. The merge first removes duplicates:

  • Plain transactions are identified by the hash of their signed message. Copies with the same message are one transaction; one copy is kept.
  • Private transactions (t > 1) are identified by their transaction ID, the commitment in their public header. The fragments different proposers included are collected under that ID, and the transaction is kept once.
  • Earlier slot wins. If the same transaction is included in two slots, only the copy in the earlier slot counts. A transaction already executed in an earlier slot is recognized by its message hash and dropped.
  • Incomplete private transactions wait in the fragment cache until their t-th fragment is accepted, then join the slot in which it was. See Threshold transactions.

The order

SortTxs orders a slot's transactions by:

  1. priority fee per compute unit, decreasing,
  2. compute limit, increasing,
  3. transaction hash, increasing.

The order depends only on the transactions themselves. Which proposer carried a transaction, and when it arrived inside the slot, do not matter: what counts is the slot a transaction lands in.

Slot capacity

Every transaction declares a compute limit cu and the set acc of writable accounts it touches. If its execution exceeds cu, it is canceled and still pays its fees.

A slot's capacity is a virtual parallel schedule of m = 4 execution tracks, each holding at most bcu = 2,000,000 compute units, 8,000,000 per slot across the four tracks,. bcu bounds how long replaying a slot takes. Validators fill the schedule deterministically, walking down the merged order:

  • A transaction is placed at the earliest time on any track at which it overlaps no earlier transaction (in the merged order) that writes one of its accounts, and at which it still finishes by bcu. If several tracks are free at that time, the lowest-numbered track is used.
  • This can leave gaps. A later transaction may fill a gap, as long as no conflicting earlier transaction starts after it.

A transaction that does not fit is not selected for the slot. A transaction whose priority fee cannot be charged without touching its fee payer's reserve is skipped and still pays its inclusion fee.

Priority inversion

Filling gaps can let a lower-priority transaction run before a higher-priority one it conflicts with. If tx1 outbids tx2 but conflicts with many transactions, including some on its own track, tx1 may fit only late in the schedule, while tx2, with few conflicts, fits an earlier gap. This is accepted: tx1 paid for its position relative to the transactions it conflicts with, and forbidding the inversion would let one transaction destroy the slot's parallelism.

Deterministic, not optimal

The greedy schedule does not always fit the most transactions. That is unavoidable: deciding whether transactions on disjoint accounts with compute limits summing to exactly m · bcu all fit on m tracks is NP-complete. What matters is that the schedule is deterministic and follows the merged order, so every validator selects the same transactions, and higher-priority transactions are placed first.

Execution

The virtual schedule decides which transactions execute in a slot, not how. Actual execution may be faster: if a transaction uses fewer compute units than it declared, later transactions may start earlier. The one requirement is that every pair of transactions writing a common account executes in merged order; then the result is the same however execution is parallelized. Acrux executes the selected list through the Solana Virtual Machine.

Algorithm 4

text
 1: function SelectTxs(txs)
 2:   txList ← [ ]
 3:   spaces ← {(0, bcu, 1), …, (0, bcu, m)}            free locations: start, end, track
 4:   scheduled ← ∅                                     position, length, accounts, track
 5:   txs ← SortTxs(txs)                                by priority
 6:   for tx ∈ txs do                                   in order
 7:     newSpaces ← ∅
 8:     placed ← false
 9:     if VM.chargePriorityFee(tx) failed then
10:       placed ← true                                 skip tx, still charge for inclusion
11:     end if
12:     while not placed and spaces ≠ ∅ do
13:       (start, end, ℓ) ← min spaces
14:       spaces ← spaces \ {(start, end, ℓ)}
15:       stxs ← sortBy(scheduled ∪ {(0, 0, ∅, ℓ)}, (pos, len, ·, ·) ↦ pos + len)
16:       for (pos, len, ·, ·) ∈ stxs do
17:         newPos ← max{start, pos + len}
18:         C ← {(p, l, ·, ·) ∈ stxs : p + l > newPos ∧ p < newPos + tx.cu}
19:         busyAcc ← {a : (·, ·, a, ·) ∈ C}
20:         S ← FindSpace(tx, newPos, (start, end, ℓ), busyAcc)
21:         if S ≠ {(start, end, ℓ)} then
22:           scheduled ← scheduled ∪ {(newPos, tx.cu, tx.acc, ℓ)}
23:           txList ← txList ∪ {tx}
24:           placed ← true
25:           break
26:         end if
27:       end for
28:       newSpaces ← newSpaces ∪ S
29:     end while
30:     if placed then
31:       VM.chargeInclusionFee(tx)
32:     end if
33:     spaces ← spaces ∪ newSpaces
34:   end for
35:   txList ← SortTxs(txList)
36:   return txList
37: end function

38: function FindSpace(tx, pos, (start, end, ℓ), busyAcc)    returns new spaces
39:   if end − pos < tx.cu or tx.acc ∩ busyAcc ≠ ∅ then
40:     return {(start, end, ℓ)}
41:   end if
42:   S ← ∅
43:   if pos > start then S ← S ∪ {(start, pos, ℓ)}
44:   if pos + tx.cu < end then S ← S ∪ {(pos + tx.cu, end, ℓ)}
45:   return S
46: end function

The returned list is sorted again by SortTxs, so the xblock executes in merged order. The line-by-line map from this listing to acrux-node's code is on /spec.

Where to see it

Every slot's merged order, with each transaction's priority, compute limit and carrying proposers, and its four-track schedule with the gaps, is on the slot's page at /net/slot/[slot].