KIP 245: Transaction Bundle

Abstract

This KIP introduces a transaction bundling mechanism that 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 timeout restrictions, ensuring that all transactions within the bundle are 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 proposers can reorder transactions to generate bundles and inject transaction generators into 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 just 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

The module consists of utility pure functions. Data structures are defined as follows:

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

type TxOrGen struct {
	concreteTx  *types.Transaction
	txGenerator TxGenerator
	Id          common.Hash
}

type Bundle struct {
	// each element can be either *types.Transaction, or TxGenerator
	BundleTxs []*TxOrGen

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

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.
    ExtractTxBundles(txs []*types.Transaction, prevBundles []*Bundle) []*Bundle
}

Bundle Generation Logic

Each module’s bundling mechanism can be pipelined. Each module must ensure that it does not disrupt 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 ]

Handling Bundle Failure

Rollback

Originally, a snapshot is generated before executing each transaction. For bundles, we take a snapshot before executing a bundle, and if any transaction fails, we 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)
    return
append all txs and receipts in bundle to env.txs and env.receipts

Pop transactions

Currently, if transaction execution fails, there are cases when all dependent transactions are removed (from ApplyTransactions loop) as they cannot be executed in this block. Such cases include gas limit reached, too high nonce, unsupported transaction type, etc. Likewise, if a transaction in a bundle fails to execute, all dependent transactions must be removed. Transactions are dependent if they have the same sender, or they are in the same bundle.

An example of chained pops:

txs     = [ G1 A.T1 B.T1 A.T2 B.T2 C.T1 ]
bundle  = [ G1 A.T1 ]
bundle2 = [ B.T1 A.T2 ]
bundle3 = [ B.T2 C.T1 ]

On A.T1 revert, initially two transactions are popped (`pop(txs, 2)`), followed by recursively popping dependents, which eventually results in: txs = [ ]

Delaying Timeout

EVM cancel due to timeout must be delayed if the transaction currently being executed is in a bundle.

JSON-RPC API

kaia_sendRawTransactions

The following JSON-RPC method for the Kaia node should be added.

• Description: Sends multiple transactions at once.
• Parameters:
  • txList - a list of RLP-encoded transactions (e.g., [RlpEncodedTx1, RlpEncodedTx2]).
• Returns:
  • hashList - a list of transaction hashes.

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 negatively impact 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.

Handling Conflicts

Bundles can have conflicts when (1) a transaction belongs to multiple bundles, or (2) multiple bundles have the same TargetTxHash. Defining how to handle conflicts is out of scope. There can be some options, such as disregarding all bundles if conflict is found, or introducing priority to bundles to resolve conflicts.

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, may be removed, 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

• Transaction Overlap Across Bundles: a transaction belongs to 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

• Duplicate TargetTxHash: two bundles have the same TargetTxHash.

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 are waived via CC0.