0xMiden / 0xMiden/protocol

Skip expired transactions in batches instead of invalidating the batch

Open
#1,450 0 comments 1 reaction 0 assignees View on GitHub
kernels
Dominant language
Rust
Stars
132
Forks
167
Avg merge
1d 23h
Merged PRs (30d)
110

Description

This summarizes an idea from @bobbinth.

#### Problem

Currently, the batch expiration is set to the minimum of all transaction expirations in the batch. This can lead to an entire batche being invalidated and not included in a block just because a single transaction has expired. This might cause batch builders to not include transactions that are about to expire to avoid this situation. Removing this situation completely would be beneficial for batch builders.

#### Proposed Change

Instead of requiring that batches do not contain expired transactions at block construction time, change the logic so that expired transactions are skipped, specifically:

* When building a block from batches, check all transactions in all batches for expiration.
* If a transaction is expired skip it _and_ all of its dependent "children" transactions.

#### Benefits

* Reduces the risk of a whole batch being invalidated due to one short-lived transaction.
* Allows batch builders to include more transactions without being overly conservative about expiration windows.
* Improves UX by lowering the risk of transactions being excluded due to overly aggressive batch builder settings.

#### Drawbacks

* Currently, each batch aggregates the individual account updates from transactions into a single batch account update. This way, the block does not have to deal with each transaction individually. With the proposed changes, the block would now have to deal with individual transactions in order to determine which transaction is expired.
* If a transaction is expired, then the block would have to aggregate each transaction's account update which would duplicate work with the batch kernel. It would also require having each transaction's account update as part of the batch, which is not the case currently.
* It might be possible to take a rather coarse approach and have logic like "if any transaction against account X is expired, skip the entire batch account update for account X", though this is not optimal. It also assumes that the transaction header's include the expiration block number, which they currently don't and that the block can verify its correctness somehow. This may already be solved by checking the correctness of a batch kernel proof, since the expiration block number is an output of the transaction kernel which is recursively verified in the batch kernel, but it would be good to double check that. Overall, this option would be possible at fairly little cost while not being optimal.

#### Considerations

* Adds complexity to the in-kernel block building logic, particularly in determining and skipping "child" transactions.
* Might be better suited for a later iteration of the MASM block kernel since complexity is already a concern for the very first implementation. In particular, if we add this to the Rust kernel now, we might want to have feature parity with the first MASM batch kernel so we may want to hold off on this now.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.