Unbounded Blocks on Solana

[cavemanloverboy]

A Path to Unbounded Blocks on Solana

We propose to deliver an abundance of blockspace to Solana in 2027 with a 2-step approach:

• A path to 500M cost unit blocks (200ms normalized)
• A path to unbounded blocks

The first objective is merely a conservative stepping stone toward unbounded blocks. To get unbounded blocks in 2027, we need to fix a few things first.

Problems

At the current 300ms slot time parameters, we are limited to blocks with a 75M cost unit limit and a 30M per-account cost unit limit (40% of 75M).

Today, most of the compute demand can be handled with a single core on the latest agave (master)
https://x.com/alessandrod/status/2098769223829143824?s=46 and we should prepare to increase block limits. However, the current "sequential" limit, which is aiming to ameliorate the worst-case fully-serialized block execution time, is fake. It is possible to construct a dependency graph which is fully serial that consumes the entire global limit via a daisy chain:

[A] → [A] → [A] → [A]
                    \
                   [AB]
                      \
                       [B] → [B] → [B] → [B]

The write-account cap only charges the As together and the Bs together. That is a single critical path: A → A → A → A → AB → B → B → B → B. This technique can be extended to an arbitrary number of accounts C, D, E... to reach the global limit on a single serial chain.

Increasing the global limit without addressing this limitation is a recipe for disaster, in my humble opinion. Lowering the 40% writable threshold (e.g. to 20%) when increasing the global limit does not address this issue, as this serialization can still be performed with more daisy chained accounts (unintentionally or adversarially).

Dependency Graphs

A block consists of transactions with requests to read and write lock specific accounts. To add a tight bound the worst-case serial execution time, we need to add a direct constraint on the dependency graph constructed by the block.

A dependency DAG links an earlier tx → a later tx when they share an account and at least one writes it. Read-read is the same subgraph but has no link (they run in parallel). Transactions that never share such an account sit in a separate independent subgraph. Serial cost is the cost of the critical path in a subgraph (sum of node cost units), not the sum of every node.

Let's first define some notation then we can show an example. A transaction T with cost C that write-locks accounts a, b and read-locks accounts c, d is written as T(C; w a, w b, r c, r d).

Example: Consider a block with transactions A(100; w a), B(100; w b), C(100; r a, r b), D(1000; r a, r b), E(100; w a), F(1000; w b), G(100; r b), and H(100; w c). This block has two independent subgraphs: {A,B,C,D,E,F,G} and {H}. In the first subgraph, even though C and D only read-lock a and b, they still block the execution of E and F. Since C and D can run in parallel, we only care about the longer of the two, which is D at 1000 cost units. The critical path is therefore A|B → D → F → G at 100+1000+1000+100 = 2200. The transaction C is omitted from that path because it is the cheaper parallel read. H only locks c, so it is its own subgraph at 100.

  +-----------+              +-----------+         +-----------+
  | A     100 |              | B     100 |         | H     100 |
  | w a       |              | w b       |         | w c       |
  +-----+-----+              +-----+-----+         +-----------+
        |   \                  /   |
        |    \                /    |
        |     \              /     |
        |      \            /      |
        |       \          /       |
        |        \        /        |
        |         \      /         |
        |          \    /          |
        |           \  /           |
        |            \/            |
        |            /\            |
        |           /  \           |
        |          /    \          |
        |         /      \         |
        |        /        \        |
        |       /          \       |
        |      /            \      |
        |     v              v     |
        v                          v
  +-----+-----+              +-----+-----+
  | C     100 |              | D    1000 |
  | r a, r b  |              | r a, r b  |
  +-----+-----+              +-----+-----+
        |   \                  /   |
        |    \                /    |
        |     \              /     |
        |      \            /      |
        |       \          /       |
        |        \        /        |
        |         \      /         |
        |          \    /          |
        |           \  /           |
        |            \/            |
        |            /\            |
        |           /  \           |
        |          /    \          |
        |         /      \         |
        |        /        \        |
        |       /          \       |
        |      /            \      |
        |     v              v     |
        v                          v
  +-----+-----+              +-----+-----+
  | E     100 |              | F    1000 |
  | w a       |              | w b       |
  +-----------+              +-----+-----+
                                   |
                                   v
                             +-----+-----+
                             | G     100 |
                             | r b       |
                             +-----------+

  subgraph {A,B,C,D,E,F,G}: A|B → D → F → G = 2200
  subgraph {H}            : H               =  100

The cost of this critical path is what we are defining as the subgraph's serial_cost.

Graphs on Mainnet today

With that definition, we can look at the graphs people are constructing on mainnet to inform what constraint we should add. We collected data in the slot range 446229018..=446501653.

On this range, we look at the longest serial_cost of any subgraph on a per-slot basis. We see that these are under the 30M writable-account cap ~95% of the time (p50 ≈ 8.5M, p95 ≈ 31M), but we still observe p99 ≈ 40M, p99.9 ≈ 49M, max ≈ 60M.

There are many disjoint dependency subgraphs on Solana in each slot, with most of them being much smaller than this tho:

Proposal: Road to unbounded blocks

To be a bit more precise, what we propose here is to take the post-execution serial_cost of each subgraph and reject blocks with a subgraph that has some serial_cost greater than some limit. Based on the data above, virtually every subgraph today would be accepted if we had a max_serial_cost set at 50M cost units.

With a max_serial_cost of 50M, we can comfortably increase the global limit without increasing the expected serial execution time of blocks and without hindering any activity on Solana. That is, any additional compute requested in a block must necessarily belong to a different subgraph that can be executed in parallel, which itself is also at or below the max_serial_cost. So, we can scale the global limit by some desired parallelism capacity. If we want to, for example, have 10 executor threads always active during replay with a max_serial_cost of 50M, we can bump the limit to 500M cost units.

These numbers are derived at the current 300ms slot limits. For a concrete proposal, let's consider the 200ms cost limit, which will terminate at a global 50M global cost unit limit. We shall scale these serial subgraphs to a max_serial_cost of 35M. Additionally, we want to scale this global limit gradually.

So, we propose four gates to increase the global cost limit while keeping max_serial_cost fixed at 35M, followed by a gate which removes the limit entirely

• Increase global cost unit limit from 50M to 100M.
• Increase global cost unit limit from 100M to 200M.
• Increase global cost unit limit from 200M to 350M.
• Increase global cost unit limit from 350M to 500M.
• Remove global cost unit limit (keep max_serial_cost)

This proposal will allow us to stress test highly parallel loads on Solana in production before removing the cap entirely. If there are performance issues that are unearthed at a particular gate, we are free to stop the gates and fix them before proceeding. Once we are confident we can handle highly parallel loads, we can remove the limit entirely and rely on Alpenglow timeouts. It is worth noting that there is a maximum number of transactions in a block; an implicit limit is derived from the number of shreds in a block. We can discuss (in this discussion) how we want to deal with this, if at all. It may be nice to leave them in there and constrain ingress/egress requirements for Solana, or perhaps move those up independently.

Note

The nice thing about moving to a max_serial_cost which is larger than the current writable account limit is that it actually makes it possible for users to serially access state for longer within a block while having a stronger bound on worst execution time.