Cross-shard Routing

Inter-committee routing

Transactions can be processed in a committee or in multiple committee’s in a blockchain. Either the co-ordination across shards could be client driven or driven by the network itself. If the network drives the committee where a transaction needs to be executed then we need good committee routing methods.

Prior inter-committee routing methods have included a strawman scheme – which is a fully connected network where every nodes knows the IP of every other node. This scheme has obvious privacy concerns as all IPs are known, it’s easier to do a DoS attack. Such a scheme is not scalable since all nodes must know and broadcast to every other node, especially when the network has tens of thousands of nodes.

Another structure is using reference committee for transaction routing, this creates centralized hub within the network and creates bottlenecks for the overall network.

In Harmony, and as discussed in RapidChain 1, we use Kademlia routing 3 which allows each committee or shard to maintain a routing table of logN records, where N is the number of committees. Each routing will take up to logN steps. For example, in a network with 2^5 committees, each committee needs to route a message 5 times to reach the desired/destination committee.

In this scheme, each node stores info about all nodes in the same committee and an additional log(logN) nodes info of other logN committee. In a network of 2^8 committees, each node stores info about log 8, or 3 nodes, from each neighbor logN number of committee.

Thus, for inter-committee transactions, all nodes in the sender committee try to send messages to the receiver committee (where they will be processed) via Kademlia routing with no neccessity of central leader. Nodes in the receiver committee broadcast messages to other members in the committee using information dispersal algorithm (IDA)-gossip protocol to speed up the block propagation in the receiver committee.