KIP 245: Transaction Bundle

Abstract

This KIP introduces a transaction bundling mechanism; it enables all-or-nothing atomicity on multiple transactions, provides timeout exemption, and facilitates injection of proposer-signed transactions.

Motivation

The upcoming features in Kaia require a systematic approach that supports the following:

• atomicity of multiple transactions and removal of transactions on failure,
• timeout exemption to enhance atomicity,
• injecting transactions from proposers.

Specification

Bundle properties

Transaction bundling has three properties: atomicity, timeout exemption, and proposer injection.

Atomicity

A transaction bundle enables them to be executed atomically, meaning that all transactions within the bundle are processed together as a single unit. This atomicity ensures that either all transactions in the bundle are successfully executed, or none of them are included in the block —- an all-or-nothing guarantee.

bundle = [ Tx1, Tx2, Tx3 ]
if all succeeded:
  insert Tx1, Tx2, Tx3 to block.
else: # any failed
  discard Tx1, Tx2, Tx3.

Timeout Exemption

Ethereum enforces a per-block gas limit, while Kaia enforces a per-block execution time limit (currently set as 250ms). The timer starts when the proposer starts executing transactions. If the total execution time reaches 250ms while a transaction is being processed, the execution halts immediately and that transaction, along with any remaining transactions, is discarded.

A transaction bundle is exempt from the timeout event, ensuring that all transactions within the bundle is fully processed.

bundle = [ Tx1 Tx2 Tx3 ]
if timeout occurred during execution of the bundle:
  defer the timeout handler until Tx3 has finished executed

Proposer injection

Block proposer can inject transaction generators in the bundle during its creation. The rationale is that after a bundle rollback, the nonces of proposer-generated transactions must be updated. A transaction generator facilitates lazy transaction generation, allowing transactions to be created dynamically right before execution.

bundle = [ G1 Tx1 Tx2 Tx3 G2 ]
Before executing G1 and G2, execute `G1(nonce)` and `G2(nonce)` respectively to get actual transactions

Builder Module

Module Interface

We define kaiax/builder interface:

type TxGenerator func(nonce uint64) (*types.Transaction, error)

struct bundle {
    // each element can be either *types.Transaction, or TxGenerator
    BundleTxs []interface{}

    // BundleTxs is placed AFTER the target tx. If empty hash, it is placed at the very front.
    TargetTxHash  hash
}

interface Builder {
    // IncorporateBundleTx does the followings:
    func IncorporateBundleTx(txs []tx, bundles []bundle) []tx

    // Arrayify flattens txs in heap into an array
    func Arrayify(heap) []tx

    func IsConflict(prevBundles []bundle, bundles []bundle) bool
}

We define the user interface of the bundling feature (e.g., Gasless module):

interface TxBundlingModule {
    // The function finds transactions to be bundled.
    // New transactions can be injected.
    // returned bundles must not have conflict with `prevBundles`.
    // `txs` and `prevBundles` is read-only; it is only to check if there's conflict between new bundles.
    func ExtractTxBundles(txs []tx, prevBundles []bundle) []bundle
}

Bundle Generation Logic

Each module’s bundling mechanism can be pipelined. Each module must ensure that it does not break the previous bundle (prevBundles). Specifically,

• Each module must ensure that a transaction does not belong to more than two bundles.
• Each module can only append transactions to prevBundles.
• Each module must not change TargetTxHash of prevBundles.

// work.ApplyTransactions()

# txs are sorted by price and nonce and timestamp by arrayifying `txs *types.TransactionsByPriceAndNonce`
txs = arrayify(txs) # [ tx1 tx2 ... ]
bundles = []
modules = [ m1 m2 ... ] # modules that implement TxBundlingModule

for module in modules:
  bundles.append(module.ExtractTxBundles(txs, bundles))
builder.IncorporateBundleTx(txs, bundles) []tx

For example, if Gasless module and Auction module are involved in generating bundles:

unsorted txs: [ 2 4 T 1 3 A S ]
- A: GaslessApproveTx
- S: GaslessSwapTx
- T: AuctionTargetTx
- LG: LendTxGenerator
- BG: BackrunTxGenerator

bundles = []

   after executing gasless.ExtractTxBundles(txs, bundles)

bundles = [ bundle{BundleTxs=[LG, A, S], TargetTxHash=3} ]

   after executing auction.ExtractTxBundles(txs, bundles)

bundles = [ bundle{BundleTxs=[LG, A, S], TargetTxHash=3},
            bundle{BundleTxs=[BG],       TargetTxHash=S},
            bundle{BundleTxs=[T, BG],    TargetTxHash=2},
          ]

txs after incorporating bundles:     [ 1 2 [ T BG ] 3 [ LG A S BG ] 4 ]

Bundle Rollback

Failed Execution

Originally, snapshot is generated before executing each transaction. For bundles, we take a snapshot before executing a bundle, and when any transaction fails, recover the state to the last snapshot.

// work.commitBundleTransaction(bundle, ...)
preBundleSnapshot = env.state.Snapshot()
for tx in bundle:
  ApplyTransaction(tx)
  if tx failed:
    RevertToSnapshot(preBundleSnapshot)
  else if tx is the last in bundle:
    append all txs and receipts in bundle to env.txs and env.receipts

Delaying Timeout

Timeout handler must be delayed if currently executing a bundle.

// work.ApplyTransactions(txs, ...)
case <-blockTimer.C:
  while bundle is in execution: // spinlock
    no operation (pass)

  timeout = true
  atomic.StoreInt32(&abort, 1)

Rationale

Rollback cost

State rollback costs O(N), where N is the number of state writes. Hence, the cost of bundle rollback is equivalent to the sum of rollback costs for each individual transaction. As a result, this does not exacerbate the block generation performance.

Indefinite Timeout

Due to the timeout exemption, there is a concern that a transaction in a bundle could run indefinitely, potentially causing a consensus delay. However, transactions within a bundle are standardized, ensuring reasonably predictable operations. Also, Kaia has computation cost limit per transaction which limit the execution time of transaction, ensuring it does not run indefinitely. Each module must ensure that transactions included in a bundle are not resource-intensive.

Backward Compatibility

Transaction Ordering

Generation of a bundle inevitably leads to transaction reordering. Although transactions are initially sorted by price, nonce, and timestamp, the bundling process can alter this order. During bundling, transactions may be reordered to meet specific bundle constraints, removed if conflicts are detected, or even new transactions may be injected. It is important to note that this does not violate KIP-162. Similar to EIP-1559, the ordering of transactions based on the gas tip is more of a recommendation than a requirement.

Test Cases

Bundle Conflict

• Overlapping BundleTxs: a transaction belonging in more than one bundle.

txs = [ 1 2 3 4 ]
  module1.ExtractTxBundles() -> {[ 1 2 ], target=empty}
txs = [ [ 1 2 ] 3 4 ]
  module2 wants to make a bundle {[ 1 3 ], target=empty} -> not allowed
txs = [ [ 1 2 ] 3 4 ]
  module3 wants to make a bundle {[ 2 3 4 ], target=empty} -> not allowed

• TargetTxHash must not break other bundle

txs = [ 1 2 3 4 ]
  module1.ExtractTxBundles() -> {[ 1 2 ], target=empty}
txs = [ [ 1 2 ] 3 4 ]
  module2 wants to make a bundle {[ 3 4 ], target=1} -> not allowed
txs = [ [ 1 2 ] 3 4 ]
  module3 wants to make a bundle {[ 3 4 ], target=2} -> allowed
txs = [ [ 1 2 ] [ 3 4 ] ]

References

• EIP-1559

Copyright

Copyright and related rights waived via CC0.