Owners: Ximin Luo
Other authors: Fatemeh Shirazi, Rob Habermeier
To recap, Polkadot consists of a unique relay chain interacting with many different parachains and providing them with security services. These require the following network-level functionality, generally for distribution and availability:
As with all blockchain-like protocols, the relay chain requires:
accepting transactions from users and other external data (collectively known as extrinsic data), and distributing them
distributing artefacts of the collation subprotocol
distributing artefacts of the finalisation subprotocol
synchronising previously-finalised state
As an important special case, parachains may choose to implement themselves according to the above structure, perhaps even re-using the same subprotocols. Part of the Polkadot implementation is architected as a separate library called substrate for them to do just this.
For interaction between the relay chain and the parachains, we require:
accepting parachain blocks from parachain collators
distributing parachain block metadata including validity attestations
distributing parachain block data and making these available for a time, for auditing purposes
For interaction between parachains, we require:
distributing messages between parachains, specifically from the relevant senders to the relevant recipients
For each of the above functionality requirements, we satisfy them with the following:
1(b), 1(c), 2(b) - artefacts are broadcast as-is (i.e. without further coding) via Bounded gossip - see also Block production broadcast and Consensus broadcast for details specific to those protocols.
1(a), 1(d) - effectively, a set of nodes provide the same distributed service to clients. For accepting extrinsics or blocks, clients send these directly to the serving node; for synchronisation, clients receive verifiable data directly from the serving node.
2(a) - this is another type of distributed service, but is a special case from the previous type due to information travelling across a trust boundary, see Parachain networking.
2(c) - special case, see Availability and Validity. Briefly, data is erasure-encoded and different recipients each receive a small part of the whole data; pieces are sent directly via QUIC over a topology custom-designed for this purpose.
3(a) - special case, see Cross-chain messaging. Briefly, messages are transferred from the sending parachain to the recipient parachain via validators who act as proxies; in the process outboxes containing messages to many recipients, are assembled into inboxes containing messages from many senders.
Message keys and sizes¶
The following message types are expected to be arbitrarily-large in size and not suitable to be sent directly in a single transmission:
P-block? (~1 MB)
P-block-PoV (~10 MB)
R-block (~1 MB)
All other message types are expected to be fairly small (<10 KB) and are suitable to be sent in a single transmission (even if the physical network performs fragmentation).
It may be beneficial to break these messages types up into chunks, or at the very least they must be sent down a different stream so that they do not block smaller message types, which tend to be more urgent.
The following message types are expected to contain an arbitrary number of members and not be keyable to an indexable structure (e.g. blocks in a chain can be keyed by height, pieces of an erasure coding can be keyed by x-coord):
In order to deduplicate them while gossiping, a more formal or rigorous set-reconciliation protocol will be needed, perhaps involving bloom filters.
TODO: consider the above issues and propose something concrete
We treat the goals of our networking protocols as black-boxes. While gossip may not be the most efficient way to implement many of them, it will fulfill the black-box functionality.
In some cases, we will be able to gossip only among a known set of nodes, e.g., validators. In the case that we are not, the design of the gossip protocol will differ from a classical gossip protocol substantially. For these cases, we introduce the notion of a bounded gossip protocol.
We have the following requirements for nodes:
Nodes never have to consider an unbounded number of gossip messages. The gossip messages they are willing to consider should be determined by some state sent to peers.
The work a node has to do to figure out if one of its peers will accept a message should be relatively small
A bounded gossip system is one where nodes have a filtration mechanism for incoming packets that can be communicated to peers.
Nodes maintain a “propagation pool” of messages. When a node would like to circulate a message, it puts it into the pool until marked as expired. Every message is associated with a topic. Topics are used to group messages or encode metadata about them. They are not sent over the wire, but are rather determined by the contents of the message.
We define a node’s peer as any other node directly connected by an edge in the gossip graph, i.e. a node with which the node has a direct connection. The node’s peers may vary over time.
For every peer \(k\), the node maintains a filtration criterion \(allowed_k(m) \rightarrow bool\)
Whenever a new peer \(k\) connects, all messages from the pool (filtered according to \(allowed_k\) ) are sent to that peer.
Whenever a peer places a new message \(m\) in its propagation pool, it sends this message to all peers \(k\) where \(allowed_k(m) \rightarrow true\).
Nodes can additionally issue a command \(propagateTopic(k,t)\) to propagate all messages with topic \(t\) to \(k\) which pass \(allowed_k\).
Multiple bounded-gossip protocols can be safely joined by a short-circuiting binary OR over each of the \(allowed_k\) functions, provided that they do not overlap in the topics that they claim.
Note that while we cannot stop peers from sending us disallowed messages, such behavior can be detected, considered impolite, and will lead to eventual disconnection from the peer.