This article give a brief summary of the idea of Kadcast on broadcasting information in a structured blockchain networks.
1 – Introduction
Blockchain network is a peer-to-peer one, and often it is unstructured, which means that the connections do not follow any pattern (they are all random). Hence, it makes the broadcasting of messages inefficient and slow. Inefficiency may lead to severe problems in security as well as affect the fairness of consensus of the blockchain networks.
Let have a look at a traditional protocol of broadcasting a message. When a node wants to broadcast a new block in an unstructured network, it will first set up TCP connections to part or all of its neighbors. Then, the block will be broadcasted through the links to the neighbors. The neighbors will then store and verify the block before it repeats the same protocol on its neighbors.
The traditional protocol introduces a considerable amount of redundancy (superfluous messages). As we can see in the figure above, the blue lines are the only connections that we need to reach 100% coverage when broadcasting a new block. This protocol has also increased the information propagation delay in the network.
Therefore, we can see an apparent optimization problem here. How can we reduce the number of messages needed to be sent across the network? How to reduce the information propagation delay when broadcasting? Since we are broadcasting in an unstructured network, the pattern is unpredictable. Hence, it isn’t easy to find a solution.
There have been many attempts to tackle this problem. One method is to use Request-Response message when broadcasting a new block. The node that wants to broadcast the message will send a request message first to see if its neighbors want to have that new block. However, this will add one RTT per-hop and so increasing the propagation delay. Moreover, the unsolicited blocks method is preferable over this method. Another way to improve the system efficiency is to reduce the size of the block being sent. Several techniques can be mentions, such as Compact Blocks, Xtreme Thinblocks, and Graphene. These methods, however, are orthogonal with the Kadcast way to tackle the problem.
2 – Kadcast Protocol
Kadcast stands for Kademlia Broadcast. As the name implies, the Kadcast protocol uses structured overlay topology of Kademlia to broadcast messages.
Kademlia is nothing more than a data structure that is efficient for information store and lookup. Specifically, Kademlia is a Distributed Hash Table for UDP-based peer-to-peer network.
In Kademlia, each node is identified by an L-bit address, which is called NodeID. The NodeID will determine the node position in a binary routing tree that builds Kademlia’s structure. Given NodeIDs of any two nodes, if we apply the XOR operation on them, we will get the distance between those two nodes. Based on that distance from a given node, the neighbor nodes are categorized in L buckets (each bucket may contain up to k nodes) of that node.
The figure above is a visualization of a 4-bit address space Kademlia tree. Note that this tree is never constructed and used only for model visualization.
The node that wants to broadcast the message will delegate the broadcast responsibilities for subtrees (each bucket area) with decreasing height. Then, we recursively repeat the same protocol within the delegated area.
When miner initiates block broadcast, it is responsible for the whole tree with the height equals L (number of buckets). Then, the miner picks a random peer in each bucket and delegates broadcast responsibility to that peer. The miner assigns a new height for the delegated peer. When receiving the delegated message, the peer repeats the process within its buckets.
3 – Improvements
One key thing about the Kadcast protocol is that it is UDP-based rather than TCP-based, like most blockchain systems. Therefore, there is a chance that the message may be lost, corrupted or random failure during the transmission. This introduces the problem of reliability.
As mentioned above, the problem of reliability may affect system broadcasting coverage. Therefore, the parallelization method is introduced to improve the reliability. Now, instead of picking just one delegate per bucket, we pick n delegates per bucket. This will increase the probability that a message is received in a bucket area and also protect the network against random failures.
One other improvement to prevent package corruption is to use Forward Error Correction (FEC). The FEC allows us to recover the corrupted message during transmission.
4 – Security
To prevent the possibility of Sybil and Eclipse attack, the Kadcast Protocol needs to implement a way to make the NodeID creation process randomly and uniformly. This helps to prevent the chance that the attacker spawn adversary nodes near the victim node. If the attacker can select the spawning location, it will increase the chance they receive the broadcast delegate responsibility. As a result, the adversary nodes may refuse to broadcast and obstruct the block construction in the network.
The ID is choosing by using the Hash function on the IP address. Therefore, it will be harder to generate the ID at a specific location. However, IP Spoofing may be a problem. To prevent this from happening, the author implements a cryptographic puzzle in the ID creation protocol. Any new node that wants to join the network has to find a nonce that satisfies a condition (similar idea to proof-of-Work in Bitcoin). Then, the nodes in the system will verify the newly created ID.
5 – Conclusion
Broadcast in unstructured peer-to-peer network is inefficient and slow. Kadcast is a novel method of using a structured overlay network topology (Kademlia) to solve the problem of inefficient message broadcasting. The Kadcast protocol brings improvement to the traditional way for transmitting message.