Consensus Protocol V2

[lukewwww]

According to our recent discussions, we will implement the next version of the consensus protocol to further improve the network efficiency and availability, and strengthen the consensus security at the same time.

The V2 consensus protocol will be built on top of the V1 version, where the foundation setup is still selecting multiple nodes to execute the task, and verifying the task by comparing the results from multiple nodes. The improvements are:

Random sampling to select a small portion (10%) of the tasks to verify, instead of verifying every task. The rest of the tasks (90%) will be executed using only 1 node then, which dramatically improves the efficiency and availability:

1. More tasks could be executed given the same number of nodes.
2. The task is more likely to be successful when a small portion of the nodes are not functioning properly (timeout on every task).

Originally posted by @lukewwww in #1 (comment)

Secret selection of nodes. Only the selected node knows its task. No one else knows who are selected for a task, the selected node does not know who else are selected for its task.

This is actually a requirement to implement the improvement above, but also reduces the security risk left in the old consensus protocol.

1. It is harder to find out whether two of the attacking nodes are executing the same task.
2. Only the small portion (10%) of the tasks that are chosen to be verified are left to be attacked.

Node selection could be completed in O(1) time on-chain, which reduces the transaction cost when the network becomes large.

Originally posted by @lukewwww in #2

The implementation will be built on the idea of the secret sortition using VRF, which comes from Algorand, who has invented this method
to do a secret selection of the block producers, which is quite similar to our case:

https://medium.com/algorand/algorand-releases-first-open-source-code-of-verifiable-random-function-93c2960abd61

Two more things we need to implement on top of the original design:

1. Integrate the random sampling method to secretly select 1 or 3 nodes.
2. Integrate the QoS based selection probability into the secret selection.

[lukewwww]

Or there is a simpler solution:

First the blockchain selects 1 node to execute the task, after the node submits the commitment, the blockchain generates a random number to decide whether this task requires verification or not. If not, the node could just submit the result to the blockchain, and the task is finished. If verification is required, the blockchain will further select 2 more nodes to execute the task, and wait for them to submit commitments.

If we choose to verify 10% of the tasks, the 10% selected tasks requires ~2x the execution time as before, and the remaining 90% could be executed using 1 node only.