Protocol changes for transaction propagation

[NikVolf]

Problem

Currently, network protocol does not allow us to announce new transaction hashes or query transactions by hash from the given peer. This leads to the problem where we just send all transactions to all peers using existing /transactions/1 protocol and supplying transaction data with it. Due to possibility that substrate can be used in some degenerate network topologies we also can't choose some subset of peers to propagate transactions only to them (so that they do the same and eventually all peers get all transactions - this will work only on well-connected network with normal topology).

Transferring all transaction data to all peers is very costly in terms of traffic, thus we need to alter the protocol to allow on-demand requests of transaction data and new transactions hashes announcement.

Required changes

1. Extend transactions protocol to /transactions/2 and add announce transaction hashes message to it. Announce is just a collection of hashes.
2. Add request-reply protocol for transaction data. Peer provides transaction hash and receives transaction data.

How propagation works now

1. We receive transaction from some source (RPC, network, offchain).
2. We propagate this transaction to all peers using /transactions/1 protocol.

How propagation should work with this change

1. We receive transaction from some source (RPC, network, offchain).
2. We propagate this transaction to max(5, sqrt(peer_count)) peers using /transactions/1 protocol.
3. We announce this transaction hash to all peers using /transactions/2 protocol.
4. We are able to serve request for individual (or batches of) transaction hashes from any peer.

[NikVolf]

cc @bkchr @tomusdrw @tomaka

[tomaka]

The change from /transactions/1 to /transactions/2 requires paritytech/substrate#6605

[tomusdrw]

Prior work which I think we should really consider: https://arxiv.org/pdf/1905.10518.pdf (mentioned by @burdges some time ago). Especially: "Low-fanout flooding":

To meet our scalability goal (R1), we limit the flooding done by
public nodes to eight outbound connections even if the total number
of these connections is higher. this way, increasing connectivity
does not increase transaction dissemination cost proportionally.
the decision to relay through outbound connections, but not the
inbound ones, was made to defend against timing attacks

Having the set reconciliation protocol also allows to improve block propagation (separate issue), where instead of sending a full block with all transactions over the wire, we only send the header + transaction hashes (since we know the recipient has the full transactions).
More: https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki#HeaderAndShortIDs
or Arweave's Blockshadow

[NikVolf]

We discussed it few times with @burdges already, and (I think) came to conclusion that with our projected TPS and block time this won't work as well as in Bitcoin (due to a lot of large reconciliations needed) or require huge adaptation which research team must first do and experiment on.

[tomusdrw]

Which part do you mean exactly? Limiting flooding to fixed number of peers (or at least putting an upper bound) seems reasonable to me (same as block shadows). With set reconciliation, I agree, we can simply use the hash-announce and request-by-hash thing proposed here (which is based on eth EIP afaict).

[NikVolf]

Which part do you mean exactly?

reconciliation stuff from paper, algorithm non-linear on number of mempool updates (which essentially is TPS)

[stale]

Hey, is anyone still working on this? Due to the inactivity this issue has been automatically marked as stale. It will be closed if no further activity occurs. Thank you for your contributions.

[tomusdrw]

Hey, is anyone still working on this?

No, but would be cool to see someone working on this. Happy to help and guide.