Alternative block gossiping protocols (Compact Blocks, XThinBlocks, Graphene)

[nazar-pc]

We are planning to implement some scalability technics to block gossiping in Subspace, currently planning to implement Graphene protocol.

Currently my personal opinion that the approach we should take is to bypass Substrate's block gossiping for this entirely and do that with custom gossip and request/response protocol.

I'm wondering, however, what Substrate maintainers think about this and whether some refactoring or abstractions would be desirable upstream that will help us achieve this? And maybe upstream Graphene protocol implementation itself for the rest of the community to enjoy.

[burdges]

We're always happy if folks experiment with substrate as a platform of course.

If I understand, graphene works operates upon transactions, not blocks. All nodes receive and verify most transactions. You then gossip graphene blocks by sending the header and doing set reconciliation on the transactions within the block.

Just fyi, Bitcoin uses BCH codes in their transaction gossip (more links). I do not know their performance characteristics, but presumably much better than bloom filters at Bitcoin's blockrate. Interestingly, if one has more CPU time then there exist protocols that massively out perform bloom filters on bandwidth, ala Mike Hamberg's RWC2022.

We could explore gossip via the reed-solomn erasure coding using by polkadot or via some rateless erasure code. It'd hurt CPU performance slightly, but it maybe share bandwidth better, prevent network level attacks, and maybe even help block producers stay anonymous after making their block (ditto bittorrent).

As a rule, we've never pushed for gossip optimizations like this for several reasons:

1. We expect relay chain validator resources to be more valuable than collator resources. We therefore optimize for relay chain performance but obviously relay chain performance cannot be improved by advanced knowledge of transactions. A relay chain validator should spend most cycles processing parachain blocks, of which it obviously lacks foreknowledge.

2. We need the execution unit to be whole blocks in polakdot because doing so permits far richer logic: A transaction could be valid when gossiped but invalid inside a specific block for many reasons, not all so cleanly separable. A block producer could transform a transaction when including it inside a block. zkAMMs would cause both issues for example.

3. We'll have sassafras to bypass memepools eventually, at which point user agents submit transactions directly to whatever upcoming block producer they choose (over Tor or a mixnet), so then even collators lack advanced knowledge of transactions. I think solana employs a simpler optimization, which makes them DoS vulnerable, but sassafras block producers stay anonymous, which protects them. zkAMMs benefit from sassafras too.

As an example of all three, we'll push whole block optimizations (2) that save relay chain resources (1). Among the cryptographic batching examples, I suppose schnorr half-aggregation only saves 32 bytes per transaction and 40% of signature verification time, but snarkpack saves maybe 100 bytes per transaction and 90%+ snark verification time. A priori, collators do not benefit, only validators do, but sassafras (3) lets collators benefit too.

Anyways..

I realize your case might not benefit from whole block optimizations, etc. so explore whatever sounds helpful. It'd maybe help some other parachain teams too, not really sure.

[nazar-pc]

We did some research (@rahulksnv to be specific) and decided that Graphene is the option we'll likely go with. We have considered Erlay and some other alternatives.

Our chain will have much higher throughput in terms of data bandwidth. To improve scalability we don't want to gossip transactions twice: once before the block is produced and second time as part of the full block.

We want to scale Subspace to the limits of underlying physical environment (CPU, disk, available throughput).

For this gossiping of transactions beforehand rather than only when the block is produced spreads out the network utilization a lot and reduces block propagation latency by a huge factor (compare many megabytes full block vs a few hundred bytes header of the block). Gossiping full blocks in such environment is a big problem because it is limiting block propagation and doesn't utilize bandwidth efficiently, gossiping transactions twice (once beforehand and second time as part of the block) is even worse because it wastes almost half of the bandwith unnecessarily.

With that context I think the optimizations we're pursuing in this particular context (there are others which may overlap better with Polkadot) are different from what you've described looking at the it through Polkadot lens.

[burdges]

we don't want to gossip transactions twice: once before the block is produced and second time as part of the full block.

Yes sassafras should achieve this too, but by sending the transaction only in the block, and never gossiping unbatched transactions, so then whole block optimizations should make sassafras more efficient than any solution that gossips transactions, assuming transactions require actual verification work.

If I understand your case, your transactions are simply data that never actually "does anything" and do not require checking, so graphene and sassafras should be mostly equivalent for you, and graphene is simpler.

In fact, I'd think your storage chain situation could achieve sublinear bandwidth via erasure coding, aka transaction neither appear in full in blocks nor get gossiped, just all nodes receive erasure coded chunks and merkle proofs, but this entails thinking about the threat model, etc.

[nazar-pc]

If I understand your case, your transactions are simply data that never actually "does anything" and do not require checking, so graphene and sassafras should be mostly equivalent for you, and graphene is simpler.

In one context transactions are bundled and checks are run on bundles, so ratio of data vs computation is heavily biased towards data. In the other case where execution happens, checks do happen, but we can't wait for a few seconds doing nothing and then trying to download a block as quickly as possible there or else we don't maximize bandwidth usage.

P.S. Subspace is not a storage chain, it just happens to be possible to store a lot of data on it once blockchain trilemma is resolved.
P.P.S. Is there a place to read what Sassafras actually is? I can't find it with search engine; it is mentioned in some places, there are even implementation PRs, but spec doesn't seem to exist in the wild or not discoverable at very least.

[bkchr]

I think this should be doable with its own req response protocol to just return the transaction hashes? (Didn't read the paper if they direcfly announce header + hashes)

[nazar-pc]

Different protocols have slightly different construction that can involve several roundtrips. I'm mostly curious if there is a desire in Substrate to have some kind of built-in abstraction for this or should we bypass it completely.

[bkchr]

I don't get it. Abstraction for what? We already have a protocol abstraction. Substrate doesn't need to care what kind of protocol you are running "downstream". If there are things that are blocking you, we can change them. For now, I would propose that you develop the protocol downstream.

[rahulksnv]

We already have a protocol abstraction. Substrate doesn't need to care what kind of protocol you are running "downstream". If there are things that are blocking you, we can change them. For now, I would propose that you develop the protocol downstream.

Currently, networking(ChainSync and friends) is tightly coupled with the block request handler.

Our initial design was to refactor this and add new procols. At a high level:

1. Introduce an abstraction of "block download manager" which talks to the individual protocol implementations
2. Network ChainSync talks to the block download manager
3. Implement new block relay protocols using /protocol-id/sync/{3, 4, …}, as parallel entities, at the same level as the current (full) block request handler which uses /protocol-id/sync/2. The new protocol implementations would be wrappers around libp2p::request_response::RequestResponse, just like the current block handler. This is where the protocol specific hand shake and other details reside. This would be completely abstracted from rest of the stack.

1, 2 are essentially refactoring of current stack, to allow modular/pluggable protocols. (3) would be the "downstream" implementation of new protocols like graphene.

In light of this, @bkchr please share your thoughts.

[bkchr]

Block request handler and chain sync is only coupled through the messages that are exchanged between them? Not more AFAIR,