Randomness on the blockchain (II) project analysis

This article is a continuation of the randomness (1) of the previous article [study] blockchain . As part of the random series on the blockchain, this article describes the current mainstream random number protocols for blockchain projects, such as Algorand, Cardano, Dfinity, and Randao, and analyzes how they use the first part. The random number protocol cores introduced and their combinations.

Application in blockchain projects:

This chapter introduces the following four projects: Algorand, Cardano, Dfinity, and Randao, respectively, how to build a random number generation protocol using the three basic schemes described above. Note that this article does not specifically explain the consensus algorithms of these four projects. It only introduces the most basic framework to help readers understand the connection between consensus protocols and random number algorithms.

Algorand:

The Algorand [1] project uses a PoS-based hybrid consensus protocol, and its consensus process utilizes random lottery. The seed on which its random lottery depends, in essence, is generated by taking the first t (t = 1) inputs, the first way corresponding to the v3.0b version. As shown in Figure 1, Algorand's consensus process requires that the node first draw locally, that is, a verifiable deterministic random number calculated locally by the node through a Verifabale Random Function (VRF). VRF can be seen as a special pseudo-random number generator. It should be added that the "determination" here means that such a random number cannot be manipulated by the user because the input is uniquely determined not to be controlled by the user. This is because the input is based on the public information of the previous round of random number generation process and each node's own private key. The private key can be verified by the public key; public information is visible to everyone, uniquely determined, and can be verified by others.

• BAP-2: The first UTXO-based asset standard
• Will the large-scale adoption of Bitcoin fundamentally change the financial system?
• Is it blowing leather, or is it really stock? John McAfee postpones the announcement of Nakamoto’s identity

After the local lottery gets the local random number, everyone will immediately know if they are selected (whether the result falls within certain intervals). After that, the selected person broadcasts the lottery result, the proof and the candidate block to the whole network node, and selects the candidate block according to the quality of the block, and determining which block is of higher quality requires a Byzantine consensus. At this time, it is necessary to conduct another round of local lottery. All nodes will know for themselves whether they are selected to do BA* (a Byzantine type consensus agreement), that is, vote for the highest quality candidate block that they think is the best. For many rounds, a local draw will be repeated each round to increase security. It can be seen that the essence of the Algorand consensus is that each of us generates a certain random number. But we end up with only a random number, so that we can decide which block will be accepted by the whole network based on the last unique random number. The solution at this time is to take one of the many alternative results according to certain rules, by agreeing through the Byzantine consensus.

Figure 1: Algorand's consensus agreement

Figure 2: VR

Cardano:

Cardano [2] is a project based on Ouroboros [3] that uses a PoS-based consensus protocol. Ouroboros This paper presents a framework for proving a secure PoS protocol, but does not give a concrete implementation, implemented by Cardano. So here is a specific explanation of Cardano's specific approach to engineering. The approach adopted by Cardano is also in the three ways mentioned in the first article. As shown in Figure 4, its solution is actually a secret sharing + commitment without distributors. Figure 3 briefly describes its consensus protocol, which initializes a random number in its Genesis Block so that it can use the determined lottery algorithm to use this random number as a random beacon to determine who's block will be later. Accepted in slot. The number of slots is fixed, so there may be more than one node in the slot that is being drawn, or there may be no nodes being drawn. The specific solution is beyond the scope of this article. So, how is the initialized random number generated? The Cardano protocol first adopted the standard promise-revelation scheme, but there was an additional step to make the random number a publicly verifiable Secret Sharing (PVSS) without a distributor. That is, the fragments are distributed and the random number is revealed after the broadcast is proved. At this time, there may be participants who will run without revealing the random number, but it does not matter. At this time, the remaining participants can recover the random number of the participants who ran the road through the broadcast shard. Therefore, this is a random number generation mechanism with a certain degree of redundancy, but at the same time brings a certain robustness. Through this mechanism, as long as the malicious node does not exceed half, a random number can be generated.

Figure 3: Cardano's Consensus Agreement

Figure 4: Cardano's DRB model

Dfinity:

Dfinity [4]'s consensus algorithm is very similar to Algorand. As shown in Figure 5, the protocol also needs to elect a committee. The committee runs the Distributed Randomness Beacon (DRB) protocol to get the random number seed. As for this agreement, we will talk about it later. In order to clarify the basic steps of the consensus agreement, we first assume that the DRB protocol can achieve these functions. With this random number seed, plus each node's own private key, each node can calculate its ranking by running a verifiable random function (VRF) (this is the same as Algorand). At the same time, since all nodes are grouped, the group to which each node should be assigned is also determined by the random number seed. In all groups, a random group of seeds (previous round) was again randomly selected to be called a committee of the round. After each node has its own node ranking, all nodes can submit candidate blocks and broadcast to all nodes, but in the process of broadcasting, the honest node will give the highest value it has received so far according to the ranking. The block signature, after signing, is broadcast to all nodes. If a block gets more than 1⁄2 legal signature, this block is called a verified block. Once the honest node receives the verified block, this round will end immediately and broadcast this verified block to all other nodes.

Figure 5: Dfinity's Consensus Agreement

Thus, the random number seed generated by the DRB protocol is crucial. The DRB protocol used by Dfinity is actually the third method of v3.0b – distributed key generation + threshold signature. First, there must be a DKG protocol to generate a total key pair and a key pair share that meet certain requirements. This protocol can also be a (t, n) threshold. Through this agreement, everyone gets the key pair share, but no one knows what the total private key is. Each node uses its own private key share to sign the random number and round of the previous round. After signing the name, the signature result is broadcast, and each node can verify each signature with the total public key. The recovery algorithm of the threshold signature then recovers the total signature of this round using t signatures (equivalent to the result of direct signature using the total key pair). The algorithm of the whole process is completely determined. The only uncertainty is that each node does not know what the private key share of other nodes is. The more special aspect of Dfinity is the use of BLS-based threshold signatures, which have two advantages over other threshold signature schemes. The first benefit is a purchase, free for life. The protocol only needs to run the DKG once in the initial stage for key generation. In the later stage, only n individuals need to submit a valid signature to generate a random number, and the protocol can be run. This process is asynchronous. The second benefit is certainty, no matter which t commits, the last generated random number is the same deterministic result, no node can manipulate the final result (without exceeding the security boundary).

Figure 6: Dfinity's DRB model

Randao:

Randao [5] is an item based on the Ethereum contract for generating random numbers available for smart contracts on the chain. It uses the v3.0a solution. Each person submits a deposit of m ETHs when submitting the promise, revealing that the process will last for w blocks. There are three things to explain here. The first point is that multiple promises of the same address only accept the first time. The second point is that there is a minimum number of commitments submitted by the entire network. If the maximum number is not collected, the entire agreement will end in a failed state and then restart. The third point is that the deposit of the address not revealed on time will be confiscated, and once someone does not reveal it, the agreement will end in a failed state, in order to ensure the fairness of the random number. The final step of the agreement is Randao's special addition – the return of the deposit, the step of rewarding the participants, with the aim of giving incentives and building an ecology.

Figure 7: Randao's DRB model

Random numbers and consensus:

Random number generation and the consensus agreement are inextricably linked, mainly reflected in the following two points.

One of the ways to prevent witch attacks is unpredictable random draws. Whether it is PoW or PoS, we can understand it as a method of random lottery. Regardless of how the consensus agreement on the public chain is designed, including Bitcoin, it is somehow random. The miners competed in the PoW, making the blockers uncertain, thus preventing witch attacks by masquerading a large number of nodes.

The random number security on the blockchain depends on the consensus protocol. Taking Randao as an example, the attack against Fomo3D is also valid for Randao. Due to the characteristics of the Ethereum incentive mechanism and the consensus agreement, the miners prioritize the high transaction costs, so the attacker can use the Mensorship Attack to artificially adjust the transactions included in the package, or create a high-cost junk transaction. It consumes the block's Gas Limit and blocks other people's specific transactions from going up. When Randao is about to calculate a result that is not ideal, you can force the termination of the agreement in this way, so that the innocent node suffers losses and you profit from it. Although such a method is sometimes costly, such an attack still has the possibility of being ignored, and the reason why such an attack is established is actually rooted in the design of the consensus agreement. Another example is Grinding Attack. Fomo3D uses a hash value of the previous block as a seed to generate a random number. In this case, the miners can experiment with all the possibilities of block organization and then choose a package that deals in the best way for them. This type of attack is Grinding Attack. Although such an attack has a certain cost, if the benefits involved in the random number are sufficient, such as in some gambling games, it is very easy for the miner to profit from it.

Therefore, the generation of random numbers on the blockchain requires a context, and a given scenario must be given. In the case of Randao, if its generation of a random number is only related to 0.01 ETH, then the attacker will not have enough reason to destroy its fairness. If the deposit is not enough, then Randao may be unsafe.

References [1] Gilad, Yossi, et al. “Algorand: Scaling byzantine agreements for cryptocurrencies.” Proceedings of the 26th Symposium on Operating Systems Principles . ACM, 2017.

[2] “Cardano Settlement Layer Documentation.” Cardano. Web. 21 Apr. 2019.

[3] Kiayias, Aggelos, et al. “Ouroboros: A provably secure proof-of-stake blockchain protocol.” Annual International Cryptology Conference . Springer, Cham, 2017.

[4] Hanke, Timo, Mahnush Movahedi, and Dominic Williams. “Dfinity technology overview series, consensus system.” arXiv preprint arXiv:1805.04548 (2018).

[5] Youcai Qian. “Randao: Verifiable Random Number Generation.” Randao. Web. 21 Apr. 2019.

Author: Qiu Fei Yang

Original: NPC Source Plan

We will continue to update Blocking; if you have any questions or suggestions, please contact us!