Adopting substrate for a DAG-based consensus

[MOZGIII]

Would anyone be interested in discussing what changes are required to be applied to the substrate to implement a tx/DAG-based system rather than (or together with) a blockchain? Avalanche-like, etc.

The issues I've encountered so far are:

• no clear understanding of the "main" chain makes mental model more complicated, and largely incompatible with existing state-interop mechanisms;
• in substrate, a good portion of existing abstractions work with the notion of a block, which is not a thing with tx/DAG-based - instead, the consensus can be run over individual extrinsics (aka transactions)
• runtime and other chain-global parameters have to have a place to live -they end up in the state either way

Generally speaking, it only makes sense to run the consensus when there's a conflict, i.e. when two or more conflicting extrinsics are concurrently introduced into the system and cannot be chosen between anyhow but via a picking one via a consensus (i.e. they're actually "racing" to be finalized, but have a common invariant that'd be invalid if both are finalized).

[burdges]

There are no transaction DAG analogs for major block level cryptographic optimizations, like pre-batching aka partial aggregation of Schnorr signatures and SNARKs, especially Groth16, and also IPP/MIPP/TIPP, which makes transaction DAGs a dead end performance wise. And transaction DAGs need more synchronization work too.

We've protocols in development like XCMP and Sassafras which vaguely parallel some block DAG ideas perhaps, but we never noticed any benefits of block DAG protocols like Blockmania though.

That said..

We welcome people with alternative ideas exploring our code base because good developers with fresh perspectives might contribute code quality improvements, but block DAGs sounds more relevant of course.

[burdges]

Assuming all transactions are Groth16 then naive pre-batching reduces CPU time by 2/3rds. SnarkPack claims an exponential speedup, but adds latency of like one block.

Schnorr pre-batching only reduced CPU time by half. IPPs could be used similarly to SnarkPack, but anyone who understand doing so would tell your transparent blockchains suck. ;)

There exist other CPU costs like Merkle proofs, but signature and SNARK verificartion costs should dominate performance under load.

All these optimizations achieve nothing if we already verifies all transactions in a memepool, but memepools were always a stupid idea. These fancy new transaction DAGs like Facebook's Narwhal and Tusk avoid the memepool by working in a centralized model.

We believe Sasssfras should eventually remove our memepools without centralization, although maybe harder than what Facebook does. I'd think if both Sassafras and pre-batching work, then we'll require less CPU than what Facebook proposes, while staying distributed. Yet, we'll require many lower level optimizations, and our larger complexity makes those harder to focus upon, so quite a long road..

[MOZGIII]

So, you're saying the bottleneck currently is in the CPU not coping with the crypto required to author a block?

Interesting paper about the Narwhal/Tusk, it states a hypothesis that I've assumed as an assumption, so I'll definitely read through it.

It's a different thing though, as the block is still eventually constructed, whereas Avalanche doesn't construct the block (or chain) at all - it's a completely DAG-powered state transition, rather than chain-powered state transition. My thinking is this change of structure dramatically changes the performance tradeoffs and the bottlenecks - there's much less contention on the non-conflicting data, and it can usually be finalized very efficiently. I guess the efficient TXs exchange would also make a difference there, but it's the metastability that brings the most performance gains.

UPD:

memepools were always a stupid idea

Could you elaborate?

[burdges]

I'm describing crypto tricks by which block producers partially merge signatures or SNARKs so that block verifiers run faster, which saves CPU if we've 1500 block verifiers, or if some block verifiers like polkadot validators matter more than parachain block producers. It saves some block space too, but block space matters less.

I'm mostly discussing tricks that cost block producers nothing, but SnarkPack costs block producers considerably CPU time so that verifiers run much much faster. It's unclear if we've enough verifiers for SnarkPack's trade off, but more naive pre-batching for Groth16 saves dramatically.

You can batch verify without pre-batching into blocks, and this saves almost as much CPU with Schnorr, but this archives less with Groth16. In particular, pre-batchingGroth16 avoids the expensive subgroup checks required in deserialization for curve points usable with Groth16.

[MOZGIII]

These fancy new transaction DAGs like Facebook's Narwhal and Tusk avoid the memepool by working in a centralized model.

Here you refer to Narwhal/Tusk being for permissioned systems? I'm not sure I follow otherwise.

UPD: I might be slow to respond cause I'm doing research as I go to properly understand what you meant.

[MOZGIII]

With a tx/DAG, one of the design aspects is usually that the consensus is leaderless and there are no blocks, so there's no such step (block authoring) to optimize... While I understand the block optimizations, it seems like we still have to do some work while validating the individual transactions when we accept them - but this work is the same regardless of whether there are blocks or no blocks.

Aggregation is cool though, a real improvement for the with-blocks scenario.

[AlistairStewart]

Well the issue is that substrate assumes that we have a state machine. In the state machine model, what a transaction does depends on the state and in an arbitrary way so we have no idea which transactions commute i.e. we end up with the same result whichever order they are in. A chain that uses the UTXO model is easy to adapt to a DAG - we only need to rule out double spends to show that transaction ordering does not matter.

Substrate's runtime stuff e.g. pallets are juat too specialised to this state machine model to work in a DAG. It might be possible to adapt the host to work with a DAG, but you'd probably need a completely custom runtime.

Of course Polkadot does have transaction parallelism on the parachain level. Parachain blocks basically do form a DAG. The state machines themselves form chains but things like XCMP form cross-links between parachains. That's how we do it.

[MOZGIII]

Well the issue is that substrate assumes that we have a state machine. In the state machine model, what a transaction does depends on the state and in an arbitrary way so we have no idea which transactions commute i.e. we end up with the same result whichever order they are in. A chain that uses the UTXO model is easy to adapt to a DAG - we only need to rule out double spends to show that transaction ordering does not matter.

I've investigated this topic in particular. It seems that, in general, the only required thing to do is to ensure that global invariants (double-spend in particular for the UTXO) are not broken. Looking at it in the context of ethereum-like smart contracts, it might be that the total order which is usually required for the TXs might not be required - only the TXs related to a particular contract address have to have a total order (this being the invariant). As long as that holds, it seems like, the overall state should converge regardless of the individual ordering of the TXs (i.e. txs concurrency is a thing in that model).

Substrate's runtime stuff e.g. pallets are just too specialized to this state machine model to work in a DAG. It might be possible to adapt the host to work with a DAG, but you'd probably need a completely custom runtime.

Yep, this is what I've discovered as well. I wonder if would be a good idea to extend substrate to decouple the runtime from the notion of blocks, i.e. to make it more generic.

Another idea I had is to emulate DAG nodes with blocks, thus making a chain without fork-selection logic or primary fork, etc. It's different from a real tx/DAG-based solution, but can still be lightwight enough.

Of course Polkadot does have transaction parallelism on the parachain level. Parachain blocks basically do form a DAG. The state machines themselves form chains but things like XCMP form cross-links between parachains. That's how we do it.

Yep, it's very similar to what I'd want to build but inside the substrate itself, rather than across many separate substrate-based chains. tx/DAG model that I have in mind for smart-contracts support conceptually seems very similar to cross-link communication, but we swap blocks with extrinsics and think of it as one system (or "chain"), rather than a number of chains. The idea is we can have a logical chain that we each run consensus for per smart contract. With Polkadot that would be per parachain if I get things right.