Hybrid PoS + PoW consensus based on stochastic network contraction

The fundamental reason leading to the excessive transaction latency in today’s blockchains is the transmission overhead in a P2P network cannot scale with the number of nodes. The problem is inherent to the P2P based PoW consensus since every transaction is to be broadcast to the whole network. In fact, the latency has to worsen as long as the number of nodes increases. The recently proposed lightning network is devised to solve the above problem. What it does, however, is no more than creating a private channel for the payer, receiver and transferring nodes so that transaction can be completed once a consensus is reached. Such a process lacks a guarantee for the safety, especially when the channel is under malicious attacks, because it takes place off the blockchain.

Random clustering based PoS + PoW consensus

An effective out-of-box solution is to introduce a hierarchy into the P2P network so that the broadcast overhead can be contained. The key idea is to contract a network into smaller ones (i.e., create a hierarchy) and perform PoW computation in the contracted network with fewer Honest node Super node Delegate node Proof of Work Random clustering based on PoS and others Delegation Network nodes. The basic idea of Metrx AI’s proprietary algorithm is illustrated in Figure. The hierarchy is created with a distributed random clustering process without centralized control. When the clustering is completed, each node will have a delegate for itself. The selected representatives constitute a new network, coined as delegation network, which has an adjustable number of nodes. Then the transaction is only broadcasted inside the delegation network. The PoW is allocated to the delegate nodes and one such node can further partition its work into smaller jobs and assign these jobs to the nodes voting for it. Note that the clustering is iteratively performed. The probability of a node to be selected as a delegate is proportional to its PoS and other factors. The distributed random clustering based consensus algorithm of Metrx AI is designed as follows.

1. A node determines whether it wants to be affiliated with another node based on PoS or other factors.

2. The node sends a request to neighboring nodes asking them to join it as a cluster, together with a link list of proof certificates to sign on and a request for deposit. If other nodes agree to join the cluster, the certificate will be used for verification and they will be marked as “affiliation committed”. If they do not agree, they will be marked as “competitors” and will not receive information from this cluster.

3. After becoming affiliated to a cluster, a node calculates the connectivity of neighboring nodes and elects a group of candidates according to certain rules. With a random method the best candidate will be elected and the respective message is distributed to other nodes.

4. When one node has an enough number of affiliated nodes, it will be marked as “fullyloaded”. Such nodes will compete to incorporate other clusters.

5. Nodes will send invitations to neighboring nodes, asking the latter to join them. Through a multi-signature mechanism, they jointly generate a random seed, which can be used to initialize a Markov Chain procedure. An independent third party will judge who wins the competition by looking at the seed, public and private keys published by both parties, and the results of Markov computing. Both parties have to confirm the result and put a signature on the result, which is then published for book-keeping.

6. Nodes will keep incorporating others until they become “fully-loaded”(meaning when the number of nodes reaches 255 or exceeds the total number of nodes N/128 in the previous round) or until all other nodes in its neighboring area are fully-loaded. It will then be marked “isolated”.

7. When there are only “fully-loaded” and “isolated” nodes in the network, the next round of absorption starts. “Fully-loaded” will only absorb “isolated” nodes and vice versa. “Fully-loaded” nodes will become “Super” nodes (meaning they have more than 2^16 nodes in the respective cluster, or more than the total number of nodes N/128 in the previous round), or “Isolated Super Absorbing Nodes (meaning the number of nodes falls below 32768, or there are less than 128 “fully-loaded” nodes left).

8. When there are more than 255 “Super” nodes or “Isolated Super Absorbing” nodes, a next round of absorption begins and nodes will become core nodes, meaning they have more than 2^24 nodes in the respective cluster, or have more than the total number of nodes N/128 in the previous round. When the number of core nodes exceeds the total number of nodes N/128 in the previous round, the absorption process ends. The above procedure continues until there are less than 255 clusters. The super nodes of these clusters then become “delegate nodes”.