Parallel transaction execution in Substrate

[nazar-pc]

I'd like to start a follow-up discussion to https://github.com/paritytech/ink/discussions/1101 with a narrower goal of having support for parallel transaction execution in Substrate. Not necessarily parallel transaction execution itself, but means to achieve it at least.

I understand that Polkadot went with parallelization (effectively) using parachains, but the general concept is still useful and applicable even there.

I'm curious what community thinks about this and seeking for help in establishing more concrete set of implementation tasks that would make something like this possible.

Likely related issues:

• Runtime worker threads  #1459
• Lock-free state cache #9320

Specifically I want to propose an idea that doesn't require complex memory models described in #1459.

Background

If the goal is to have many transactions to run in parallel, the primary thing needed to guarantee that they will not touch state that may result in conflicts. Solana requires transaction to specify state of which account it will touch (read and writes can be specified explicitly). Thus during transaction execution it is possible to run non-conflicting transactions concurrently without any chance of conflicts, no need to do complex analysis or resort to speculative execution [one] [two].

Proposal

For that to become possible in Substrate a few things are necessary (as far as my knowledge allows to describe them right now):

• support for transaction annotation
  • for this proposal ability to express restrictions for state trees (or individual storage keys) that will be read/written
  • however I think this should be both optional and generic, such that other interesting capabilities can be added later
• ability to restrict state access per transaction
  • specifically, based on transaction annotation mentioned above, if during transaction execution state outside of annotated scope is touched, transaction execution must fail
• ability to adjust fees based on amount of storage touched
  • specifically here based on amount of state potentially accessible by transaction, meaning transaction that doesn't contain any restricting scope will be billed 100% fee, but if some transaction specified it will only read and write one specific storage key allowing to avoid conflicts with other transactions, it should be heavily discounted for creating opportunities for parallel execution
• executor should execute transactions, taking above annotations into consideration
  • specifically given this framework the final state root will not change whether parallel execution actually happens or not (assuming no fee discounts are applied of course)
  • this allows to start iterating with simple executor that does sequential execution and advance to executor that can build a DAG of non-conflicting transactions that can be run concurrently using some kind of thread pool (Solana mentions SIMD and massively parallel execution of identical transactions on GPUs, which is not something I suggest here, but useful for context)
• utilities/APIs would be necessary to make this more usable, possible options include
  • dry-run execution to see what state is touched
  • annotation of pallet calls and smart contracts with metadata that can instruct user-facing tools about the selection of storage keys affected

Usefulness

This is a limited and specific notion of parallel transaction execution, but it is very useful nevertheless. Think about balance transfer between Alice and Bob. If the total supply of coin doesn't change, their transfer just means editing two number and there is no reason for Dave and Charlie to be unable to do a similar balance transfer at the same time.

[burdges]

We never proposed speculative execution in #1459 really. We proposed state access unification rules that operated upon fairly explicit subblocks, which the host optionally runs in multiple threads.

We both proposed that PVFs could spawn some worker threads with separate state access caches, but we only give them synchronization primitives that provably enforce determinism (Jeff) or were restricted to closely audited code (Gav). We'd structure blocks into subblocks that ran in these separate threads, meaning the PVF would create threads by invoking a subblock entry point, so subblocks would be our annotations.

It's fairly clear that solana's per tx annotation are a memory model that enforce consistency in synchronization, but imho solana's per tx annotations sound less efficient and less flexible than simply structuring the tx into subblocks.

Also, there exists a third proposal where all tx read state from before their thread was spawned, or from their own write cache, meaning earlier tx cannot modify the behavior of later tx in the same block. It's incompatible with "smart contract" chains, but increasingly we realize "smart contracts" make little sense.

In this vein, there exist lovely designs in which different aspects of the same tx run in different threads, which becomes far more efficient, and incredible unfriendly to smart contracts.

[nazar-pc]

Speculative execution was related to two papers with Ethereum studies (just edited with one more link to paper with Microsoft Research's Forerunner).

Can you elaborate on this?:

increasingly we realize "smart contracts" make little sense

I think smart contracts are a helpful construct and calling one from another is a powerful tool as well. This thread is about enabling additional capabilities in Substrate, whether particular chain uses them or not is up to the architects, but some things are not really possible in Substrate right now and I'd like to figure out how to change that.

[burdges]

Yes, we'll always support chains doing smart contract languages of course, but smart contracts limit your optimizations, MEV defenses, etc. In particular, polkadot can benefit form whole block optimizations like SnarkPack or block MEV defenses like a block fixing one common buy & sell price for all uniswap tx. It's harder for smart contract chains to do whole block optimizations, so aggressively exploiting this advantage makes sense.

As a case in point, we're talking about somewhat whole block approaches to thread unification in #1459 while solana's scheme sounds tx local and less efficient. I suppose speculative execution also arises because of smart contract.

Anyways..

It'll turn out simpler if we simply design threading primitives with limited synchronization primitives for which we then argue soundness.

[nazar-pc]

My impression is that it'll be really hard for smart contract developers to face multi-threaded world with synchronization primitives, thus the idea of going with approach that results in potentially more limiting, but at the same time easier to reason about.

MEV in our protocol is basically a non-issue due to separating consensus from execution: execution nodes don't define the order and consensus nodes can only decide to include or not include a few large batches of transactions, but no way to impact order of individual transaction without shuffling everything in the process.

[burdges]

We'd do the synchronization work in the block producer, so smart contract authors never see those parts.

At an architectural level, we must enforce determinism in substrate's host, but transactions only exist in the runtime, making roughly #1459 essential for any proposal.

Afaik any sane solution also annotates which tx, from which the runtime figures out what tx run in which thread, but I'm also suggesting these annotations look like parallel subblocks, not metadata on individual tx.

[nazar-pc]

You're looking at it from Polkadot or more traditional blockchain side of things where block producer needs to validate transactions, create a block, run it and broadcast it.

With decoupled execution we have in Subspace (standalone blockchain), block producers (farmers) neither validate individual user transactions nor they run those (unless there is a fraud proof), they just don't have enough CPU/RAM/disk speed. They do provide ordering though, so execution (by executors, another kind of nodes responsible for validating and running transactions) is fully deterministic.

So I think I roughly understand what you're saying, but that is not the design our blockchain conforms to.

[nazar-pc]

If I'm reading code correctly, this might be implemented in two ways without modifying Substrate itself:

1. Using custom SignedExtension, but that'll mean no support from Polkadot.js apps whatsoever (and even from Polkadot.js API since it seems to have known options like nonce already hardcoded there, though I may misinterpret it)
2. Using wrapper pallet (like pallet-utility what wraps other calls), which will have extra argument(s) in addition to inner call, then Executive wrapper (that we already have in our chain regardless) will have to be teached to read into that call specifically and extract info to build its DAG of non-conflicting transactions

1) seems like a proper solution and 2) as a hack, but at the same time having full support from both Polkadot.js apps and API is HUGE.

Thoughts?