Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "what is the role of random numbers in blockchain". In the operation process of actual cases, many people will encounter such difficulties. Next, let Xiaobian lead you to learn how to deal with these situations! I hope you can read carefully and learn something!

The importance of random numbers is not only reflected in the establishment of secure communication channels, but also in the identification of communication objects. If multiple people attempt to communicate with each other over bandwidth-limited frequency channels, random numbers can be used to determine the proper order in which the frequency channels carry messages.

Random numbers can be effective in helping groups or computers reach agreement or consensus. Random consensus protocols are one such example. This article will explore the role of random numbers in blockchain.

A blockchain is a successful example of a multiparty attempt to agree on some update to the global perspective. Updates are usually done in one round, that is, at a periodic discrete time interval.

On the Internet, there is an upper limit on the number of messages sent in a given time period (i.e. throughput) and it takes a certain amount of time to send a message (i.e. delay), which imposes certain restrictions on consensus. The goal of any blockchain consensus protocol is to reach a consensus agreement within the limits mentioned above. There are thousands of nodes on the public chain involved in the maintenance of the blockchain, and if each node needs to send messages to all the other nodes and get feedback from them, the limitations of the network will greatly increase the cost of reaching consensus. This is because the number of messages sent over the network in a round time is too large. Therefore, in order to ensure consensus, it is necessary to optimize the communication scheme by reducing the number of messages sent on the Internet.

Bitcoin achieves this protocol (Nakamoto Consensus) by using Proof of Work (PoW) as a random number source to determine which block will be added to the blockchain in each round, thereby reducing the cost of message delivery. Because the problems set by PoW are algorithmically very difficult to solve, only the first to solve them can add their blocks to the ledger. Since the probability of multiple people solving a puzzle at the same time is very low, PoW can be used as a mechanism to limit the number of messages passed through the network.

In theory, any consensus mechanism that attempts to replace PoW would need to find a way to limit the number of messages the network can deliver. Most Proof of Stake (PoS) protocols address this problem by selecting a group of validators (nodes that maintain and manage the blockchain) to form a subcommittee based on the number of tokens held by the validator, and then this group of validators can communicate with each other within the limits of the network and reach agreement in time.

Of course, in order to fairly elect subcommittee members and ensure that no one knows their identities in advance, the algorithm must be able to incorporate some fair and unbiased random number source. Once the group of verifiers agree on the next block, that block is broadcast to everyone in the network.

The ideal random number source for subcommittee elections in PoS protocols must be undisposable, i.e., no one can change the random seed at will. In order to achieve non-governance, a randomness protocol needs to ensure the following two things:

Random functions always generate random numbers;

Random numbers generated by random functions are not manipulated

(Note: we will explore the tradeoffs between i) and ii) and how they relate to the network synchronization model in a later blog post.)

None of the subcommittee election protocols we analyzed on Mechanism Labs (a Twitter account) met the two points mentioned above. Therefore, given the trade-offs described above, blockchain consensus protocols should use random number sources that generate random numbers continuously, rather than random number sources that generate non-disposable random numbers only once. Because blockchain protocols need to ensure that the blockchain keeps growing and does not allow random number sources to become bottlenecks. Even if it is a protocol that prefers consistency, the random number source should not be the cause of blockchain stagnation. In any case, the random number source should ensure that the protocol is able to focus on other attacks, such as DoS attacks on small committees of verifiers that stall the blockchain, etc.

If the blockchain stops completely due to a deviation in the random number output of the random function, the social layer will have to pay a huge coordination cost to restart the blockchain. This would require the community to reach agreement on what blockchain actually is via external social media platforms, which would be a time-consuming discussion that could cost as much as solving the DAO hack in the first place. The huge cost of the social layer can also shake community confidence in blockchain protocol security, but as long as the deviation is very small and there is a mechanism to recover from the deviation state, then the impact of a few rounds of small deviation on blockchain security is relatively weak, because the public blockchain protocol gives verifiers all the protocol rewards per round. For each round or period (every few rounds) of subcommittee elections, the bias in the random function must be significant enough for the verifier to profit from spoofing the protocol and reducing the security of the blockchain protocol.

In another area, lottery games that use random numbers must ensure that the random number source is absolutely not manipulated, because even a slight deviation can completely change the winning result. Since the winner can receive a large amount of instant rewards, the impact of tampering with lottery results is huge. Thus, this lottery game favors functions that generate non-disposable random numbers once, even if this means that the output of the random function sometimes stops.

This article will explore the importance of unbiased random number sources in the context of blockchain-based protocol design. In the following articles, when we consider tamper-proof protocols, we prefer protocols that cannot be aborted.

An ideal committee election scheme should i) not be dominated and ii) show random seeds only at the beginning of a new round. Random functions must be irdeflectable as defined above. If random numbers are manipulated (and there is a reward allocation mechanism in the agreement), it will result in unfair reward allocation. Inappropriate reward allocation means that some people will receive more generous rewards. Since only those with rights can become validators, and voting rights are proportional to the rights that validators have, unfair distribution will result in blockchain control ending up in the hands of only a few validators. Thus, the degree to which the protocol is not manipulable determines whether someone can maintain part of the network as a verifier for a long time. On the other hand, how early the seed is revealed before a new round begins determines who can become part of the network first. Thus, the above two attributes will determine the degree of decentralization of the blockchain.

Since subcommittee elections occur in each round (or period), the time taken from the publication of the random number output of the random function to the start of that round (or period) is critical. In this time range, the attacker can use the random number output by the random function to know which verifiers are selected. If this output is hidden, an attacker attempting to attack the blockchain protocol will not be able to know the chosen verifier in advance. The length of this time frame determines the protocol's ability to withstand attacks. The stronger attacker, i.e., the one with more computing power and resources to attack the network, can compute the selected verifier in a short time. If the attacker has enough time, they will determine which validators are selected by running the algorithm used by the election committee and the random number seed given for the round, and then conduct a denial of service (DoS) attack on the selected validators of the round, resulting in the generation of blank blocks that make no progress in the round. For blockchain, even stopping a round can be devastating. Imagine what Bitcoin would be like if no one in the world could make any transactions within a few hours! Therefore, nodes capable of withstanding DoS attacks should be the first to become verifiers. In addition, showing seeds in advance also means that consensus protocols can only deal with weaker attackers, which weakens the decentralized nature of blockchain.

Based on the use cases of different blockchain protocols that we analyzed in our meta-analysis of alternative consensus protocols, we will describe the mechanisms for generating various random numbers from a technical point of view.

Tendermint

Tendermint uses a deterministic round-robin protocol scheme to select proponents; the protocol is not random. Proposers are selected by a heap sorting algorithm based on voting rights and the number of times verifiers are selected. An attacker can only interfere with the protocol by adding or removing entitlements, but such interference is not immediately effective because it takes a long time for a verifier to remove or add entitlements to the system. Nevertheless, the attacker has more time to plan ahead how to manipulate the proposer's choices.

The use of deterministic random algorithms means that random seeds are announced well before each round, and proponents can be identified in advance.

Algorand

Algorand's random number scheme is as follows: Each verifier v selected as a proposer uses the formula

← VRFskv (seedr−1|| r), where skv is the key of verifier v and seedr-1 is the random seed of the previous round.

VRF is the seed used to prove that the blocks accepted in round r-1 contain π and round r. If a given VRF proof fails to verify a given seed, then each person computes a new round of seed H(seedr−1).|| r), where H is a hash function. This means that each verifier's key must be chosen in advance to ensure that they cannot tamper with the random seed.

When the network is not well synchronized, the attacker takes full control of the messaging link (proofread: it feels like saying "asynchronous" hypothesis here), so he can delete the proposed block and force the user to support the blank block, thus calculating the random seed for future elections. Thus, Algorand requires the weak synchronization hypothesis that strong synchronization of length s (s < u) must exist for each period of length u to guarantee the protocol's non-maneuverability. As long as s is large enough to generate at least one honest block in time period b, an attacker v'choosing key skv' cannot manipulate the random seed of round r.

Only when a block is proposed will a new random number seed be generated and a public VRF proof be available for verification. This ensures that proposers and random seeds are not compromised in advance, while ensuring that Algorand can withstand DoS attacks against proposers, even in offline or even instant corruption modes.

Dfinity

For most protocols, attackers typically abort the protocol to invoke fallback mechanisms, thereby manipulating random numbers. However, the threshold signature scheme used by Dfinity is not manipulable, because the threshold is chosen to ensure that an attacker cannot abort the protocol by preventing the threshold signature from being generated (because the random number seed is derived from the threshold signature). Therefore the threshold t must be chosen according to the formula: t∈[f + 1, n - f], where f is the number of signatures controlled by the attacker, n is the total number of signatures in the scheme, and t is the signature threshold used to generate random numbers. This threshold was chosen to ensure that an attacker could neither predict the outcome of signature generation nor prevent signature generation.

It should be noted that in any BLS scheme, as long as the attacker has more than 50% of the margin, they can manipulate the final signature and random number. However, if an attacker has such a large stake, other types of attacks will occur, which violates the basic assumptions of the Dfinity protocol.

Once the honest verifier reaches round r, the random seed is revealed. Although the time difference between the entry of an honest validator and the official start of a new round is small, it is sufficient for an attacker with significant computing resources to identify the proposer and launch a DoS attack against it. This is why Dfinity can only deal with mild attackers and cannot deal with instantaneous paralysis.

Thunderella

In a hash function instantiated random number oracle scheme, the proposer will determine H_nonce(pk,q) < Dp, where H is the hash function used as a random number oracle, pk is the verifier's public key, q is the given iteration time, and nonce is the entropy source of the hash function. Nonce is selected by the proponent of the previous block. The difficulty parameter D_p is set such that the probability w that a committee member is selected as a proposer in a single iteration time.

If an attacker proposes a block, she can manipulate the nonce value that generates entropy for the next round of the hash function, thereby influencing the selection of the next block's proponent. However, in order to reduce the tamperability of the random number scheme, the same nonce value in the hash function is used not only to select the proposer for the next round, but also to select the proposer for the next r rounds. This makes it computationally difficult for an attacker to force a change in the nonce value to make himself the proposer for the next r rounds. Although this strategy only loses polynomial security, it has the drawback of predictability (discussed later). This scheme can only deal with slow adaptive attackers.

In the above algorithm, repeated use of the same nonce value to feed the hash function seed results in the attacker being able to predict in advance who the proposer is. Because the same nonce value is used repeatedly as entropy during a period, random seeds are leaked before a new round begins, allowing attackers to corrupt or DoS the proposer.

Casper FFG

Casper FFG plans to use a random number scheme based on the following algorithm:

At the beginning of a period, each verifier commits H (... Sv ))), where S is the seed promised by the verifier. R is assigned as the exclusive OR of R and the prime image in the hash function (R := R Pre-image of the inner layer of hash). During a round, the validator can create or abort a block.

If no random number is generated in the fallback mechanism, this may cause a bigger problem than predictable or manipulable random numbers, because you no longer need 1/3 of the bad guys to abort the protocol, 1 person is enough.

The verifier who is the current proposer is the one who knows the random seed for the next round.

Random numbers are an important part of cryptography and blockchain. Bad random number schemes undermine blockchain security by: i) stopping the blockchain protocol;ii) leading to centralization. Therefore, when analyzing the security of blockchain, exploring the role of randomness in the blockchain protocol is the most important!

The content of "What is the role of random numbers in blockchain" is introduced here. Thank you for reading. If you want to know more about industry-related knowledge, you can pay attention to the website. Xiaobian will output more high-quality practical articles for everyone!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.