Overlay Networks and Multicast Messages
Last updated
Last updated
In multi-blockchain systems like Green Meta, even full nodes are typically interested in receiving updates (i.e., new blocks) only for certain shard chains. To achieve this, a special cover (sub)network is established within the Green Meta network, with one per shard chain, built on top of the ADNL protocol. Therefore, it is necessary to construct an arbitrary cover subnet that is open to any willing participant node. The special gossip protocol based on ADNL operates within these Overlay Networks, specifically for broadcasting arbitrary data within the subnet.
1. Overlay Networks
Overlay (sub)networks are simple networks within large-scale networks. Typically, only a subset of nodes in a larger network participates in the overlay subnet, and these nodes (physical or virtual) are connected through a limited number of "links" that are part of the overlay subnet. In this manner, if the encompassing network is represented as a graph (in the case of datagram networks, a complete graph can be used, such as ADNL), any node can easily communicate with any other node. The overlay network is a subgraph of this graph. In most cases, overlay networks are constructed using protocols based on the larger network. It can either use the same addresses as the larger network or employ custom addresses.
2. Overlay Networks in Green Meta
Overlay Networks in Green Meta are built on top of the ADNL protocol and use 256-bit ADNL abstract addresses as addresses within the overlay network. Each node typically chooses one of its abstract addresses to double as its address within the Overlay Network. Unlike ADNL, Green Meta Overlay Networks generally do not support sending datagrams to arbitrary other nodes. Instead, they establish some "semipermanent links" (referred to as "neighbors" in the context of the overlay network under consideration) between certain nodes, and messages are usually forwarded along these links (i.e., from a node to one of its neighbors). In this way, the Overlay Network in Green Meta is a (usually non-full) subgraph within the (complete) graph of the ADNL network. Dedicated peer ADNL channels can be used to establish links with neighbors in the overlay network. Each node in the Overlay Network maintains a neighbor list (relevant to the overlay network) containing their abstract addresses (used to identify them within the overlay network) and some link data (e.g., ADNL channel for communication with them).
3. Private and Public Overlay Networks
Some Overlay Networks are public, meaning any node can join them freely. Others are private, allowing only certain nodes to be admitted (e.g., nodes that can prove their identity as validators). Some private Overlay Networks may even be known to the general public, but information about this Overlay Network is only available to trusted nodes. For example, it may be encrypted with public key cryptography, and only nodes with the corresponding private key can decrypt this information.
4. Centrally Controlled Overlay Networks
Some Overlay Networks are centrally controlled by one or more centralized authorities or a set of well-known public keys' owners. Others are decentralized, meaning there is no specific node responsible for them.
5. Joining Overlay Networks
When a node wants to join an Overlay Network, it first needs to know its 256-bit network identifier, typically equal to the sha256 of the Overlay Network description - a TL-serialized object that may include, for example, the central authority (i.e., its public key, possibly an abstract address) for the Overlay Network it is related to, the string representing the Overlay Network's name if it's associated with Green Meta blockchain shard identifiers, and so on.
Sometimes the Overlay Network description can be recovered from the network identifier by performing a lookup in the Green Meta DHT. In other cases (e.g., for private Overlay Networks), the network identifier must be obtained.
6. Finding a Member of an Overlay Network
Once a node knows the network identifier and description of the Overlay Network it wants to join, it needs to find at least one node that belongs to that network. This is also required for nodes that don't want to join the Overlay Network but only communicate with it; for example, there may be an Overlay Network dedicated to collecting and propagating specific shard chain transaction candidates, and a client may want to connect to any node in that network to propose transactions.
The method for locating members of an Overlay Network is defined in the network's description. Sometimes (especially for private networks), it must be already known which member nodes can be joined. In other cases, some nodes' abstract addresses are included in the network description. A more flexible approach is to indicate only the central authority responsible for the network in the network description and then obtain abstract addresses by the value of certain DHT keys signed by that central authority. Finally, truly decentralized public Overlay Networks can utilize a "distributed flow tracker" mechanism, which can also be implemented with the help of the Green Meta DHT.
7. Finding More Members of an Overlay Network
Creating links. Once a node finds one node belonging to the Overlay Network, it can send a special query to that node, requesting a list of other members, such as the queried node's neighbors or their random selection. This allows joining members to populate their "adjacency" or "neighbor list" about the Overlay Network by selecting some newly discovered network nodes and establishing links to them (i.e., using dedicated ADNL point-to-point channels as outlined). Afterwards, a special message is sent to all neighbors indicating that the new member is ready to work within the Overlay Network. The neighbors include the links to the new member in their neighbor list.
8. Maintaining the Neighbor List
Overlay Network nodes must periodically update their neighbor lists. Some neighbors, or at least their links (channels), may become unresponsive, and in such cases, these links need to be marked as "suspended." Attempts must be made to reconnect to such neighbors, and if these attempts fail, the links must be destroyed.
On the other hand, each node sometimes requests its neighbor list (or their random selection) from randomly chosen neighbors and utilizes it to partially update its own neighbor list by adding some newly discovered nodes and removing some old ones, whether randomly or depending on their response time and datagram loss statistics.
9. Overlay Network as a Random Subgraph
The Overlay Network is a random subgraph within the ADNL network. If the degree of each point is at least 3 (if each node is connected to at least three neighbors), it is known that the random graph is connected with a probability close to 1. More precisely, the probability of a disconnected random graph with n vertices is exponentially small, and if n ≥ 20, this probability can be completely ignored. (Of course, this does not apply to the case of global network partitioning when nodes from different shards have no opportunity to get to know each other.) On the other hand, if n is less than 20, requiring each vertex to have, for example, at least ten neighbors is sufficient.
10. Green Meta Reduces Latency
Green Meta Overlay Networks optimize the "random" network graph generated by previous methods. Each node attempts to retain at least three neighbors with the minimum round-trip time and rarely changes this "fast neighbors" list. At the same time, it also keeps at least three fully random "slow neighbors," ensuring that the Overlay Network graph always contains a random subgraph.
This is necessary to maintain connectivity and prevent the Overlay Network from splitting into several disjoint subnet regions. It also selects and retains at least three "intermediate neighbors" with intermediate round-trip times, bounded by a certain constant (actually a function of the round-trip times of fast and slow neighbors). In this way, the graph of the Overlay Network is still optimized for lower latency and higher throughput while maintaining sufficiently good connectivity.
11. Gossip Protocol in Overlay Networks
Overlay Networks are commonly used to run one of the gossip protocols, which achieve certain global objectives while allowing each node to interact only with its neighbors. For example, there are gossip protocols that can construct an approximate list of all members in a (not too large) cover network or compute an estimate of the number of members in an (arbitrarily large) cover network using only a quantized amount of storage per node.
12. Overlaying the Network as Broadcast Domain
The most important gossip protocol running in Overlay Networks is the broadcast protocol, which aims to propagate broadcast messages generated by any node in the network or possibly by one of the specified sender nodes to all other nodes. There are actually several broadcast protocols optimized for different use cases. The simplest relays newly received broadcast messages to all neighbors that have not yet sent a copy of the message themselves.
13. More Complex Broadcast Protocols
Some applications may require more complex broadcast protocols. For example, for broadcast messages of large size, it makes sense to send the hash of the message (or a set of hashes of new messages) to neighbors instead of sending the newly received messages themselves. After knowing the hashes of previously unseen messages, neighbors can request the messages themselves, for example, using a reliable large datagram protocol (RLDP) for transmission. This way, new messages are downloaded from only one neighbor.
14. Checking Connectivity of Overlay Networks
If there are known nodes that must be present in the cover network, such as the "owner" or "creator" of the cover network, the connectivity of the cover network can be checked. Then, the discussed node periodically broadcasts short messages containing the current time, a sequence number, and its signature. Any other node can determine that it is still connected to the cover network if it recently received such a broadcast. This protocol can be extended to the case of several well-known nodes; for example, they all will send such broadcasts, and all other nodes will expect to receive broadcasts from more than half of the well-known nodes. In the case of a cover network used for propagating new blocks (or just block headers) of a specific shard chain, a good way to check connectivity for nodes is to track the most recent blocks received so far. Since blocks are typically generated every five seconds, if no new block has been received for more than 30 seconds, the node may have become disconnected from the cover network.
15. Streaming Broadcast Protocol
Finally, there is a streaming broadcast protocol for Green Meta Overlay Networks, for example, used to predict block candidates among validators in certain shard chains ("shard chain task groups") and, of course, to create a private cover network for this purpose. The same protocol can be used to propagate new shard chain blocks to all full nodes of that shard chain.
The protocol overview: a new (large) broadcast message is split into, for example, N blocks of one thousand bytes each; these blocks are increased to a sequence of M ≥ N blocks using erasure codes such as Reed-Solomon or fountain codes (e.g., RaptorQ codes), and these M blocks are streamed to all neighbor nodes in ascending order.
Participating nodes collect these blocks until they can reconstruct the original large message (which requires successfully receiving at least N blocks), then they instruct their neighbors to stop sending new blocks of the stream since these nodes can now generate subsequent blocks themselves, having a copy of the original message. These nodes continue to generate subsequent blocks of the stream and send them to their neighbors unless the neighbors indicate they no longer need them. In this way, nodes do not need to fully download the large message before further propagation, minimizing broadcast latency.
16. Building New Overlay Networks Based on Existing Ones
Sometimes it is not desired to build a cover network from scratch. Instead, one or more previously existing Overlay Networks are known, and it is expected that the membership of the new cover network significantly overlaps with the combined membership of these Overlay Networks.
An important example arises when a Green Meta shard chain is split into two, or two sibling shard chains are merged into one. In the first case, a cover network for propagating new blocks to full nodes must be built for each new sub-chain; however, it can be expected that each of these new Overlay Networks includes members that are already part of the block propagation network of the original shard chain (including approximately half of its members). In the second case, the cover network for propagating new blocks of the merged shard chain will approximately include the union of members from the two Overlay Networks associated with the merged sibling chains. In this case, the description of the new cover network can include explicit or implicit references to the relevant existing Overlay Networks. Nodes wishing to join the new cover network can check if they are already a member of any of these existing networks and query their neighbors in those networks if they are also interested in the new network. In case of affirmative replies, new point-to-point channels can be established with those neighbors, and they can be included in the neighbor lists of the new cover network. This mechanism does not entirely replace the general mechanism; instead, they both run in parallel to populate neighbor lists. This is done to prevent inadvertently splitting the new cover network into several disconnected subnets.
17. Overlay Networks within Overlay Networks
Another interesting case is the implementation of Green Meta Payments (i.e., the "lightning network") for instant off-chain value transfers. In this case, a cover network containing all transit nodes of the lightning network is first built. However, some of these nodes have established payment channels in the blockchain, and besides any "random" neighbors chosen by the general cover network algorithm, they must always be neighbors within that cover network. The "permanent links" to these neighbors with established payment channels are used to operate specific lightning network protocols, effectively creating a cover subnet (not necessarily connected if problems occur) within the encompassing(most-commonly-connected)cover-network.
