The environment we live in is full of randomness. The concepts of luck, probability and fate have long been associated with randomness. All things that humans cannot understand or predict tend to be classified as random.
However, although humans have been exposed to all kinds of random things and are familiar with randomness, it is still difficult to translate it into something that computers can use. When we talk about randomness in computer systems, what we really mean is
A very powerful
Random numbers play an important role in privacy technology and cryptography. Surprisingly, it provides a simple but powerful encryption scheme by generating a random number to perform XOR on a message. Even the simplest form of private communication between two parties (i.e., symmetric encryption schemes in which both parties share the key in advance) requires that the shared key be random. If the shared key is not random, encryption is useless, because anyone who knows the key generation algorithm can determine the key and then decrypt the message.
The importance of random numbers is not only reflected in the establishment of secure communication channels, but also in the confirmation of communication objects. If multiple people are trying to communicate with each other over channels with limited bandwidth, random numbers can be used to determine the reasonable order in which the channels carry messages.
Random numbers are useful in helping groups or computers reach a consensus. Random consensus protocols are one such example. This article will explore the role of random numbers in blockchain.
Blockchain is a successful case of multiple parties trying to agree on some kind of update of the global perspective. Updates are usually done in a round, that is, in a periodic discrete time interval.
On the Internet, consensus is limited by the fact that there is a limit to the number of messages that can be sent in a given period of time (throughput) and the time that messages must take to be sent (latency). The goal of any blockchain consensus agreement is to reach a consensus agreement within the limits described above. There are thousands of nodes on the public chain that participate in the maintenance of the blockchain, and if each node needs to send messages and get feedback from all the other nodes, the network’s limitations can greatly increase the cost of reaching consensus. This is because of the large number of messages sent over the network in one round. Therefore, to ensure consensus, communication schemes need to be optimized by reducing the number of messages sent over the Internet.
The way bitcoin achieves this agreement (satoshi Consensus) is through use
PoW can be used as a mechanism to limit the number of messages delivered on a network
In theory, any consensus mechanism that tries to replace PoW would need to find a way to limit the number of messages passed over the network. Most proof-of-stake (PoS) protocols solve this problem by selecting a group of verifiers (nodes that maintain and manage the blockchain) to form a sub-committee based on the number of tokens held by the verifier. The group of verifiers can then communicate with each other and reach a timely agreement within network limits.
Of course, in order to fairly elect subcommittee members and ensure that no one knows their identity in advance, the algorithm must incorporate some fair, unbiased random number source. Once the group of verifiers has agreed on the next block, that block is broadcast to everyone in the network.
The ideal random source for the PoS protocol for subcommittee elections must be unbiasable, that is, no one can change the random seed at will. In order to be non-dominant, randomness protocols need to ensure two things:
I) Random functions always generate some random numbers;
Ii) Random numbers generated by random functions are not manipulated
(Note: we will explore the tradeoff between I) and ii) and how it relates to the network synchronization model in a future blog post)
None of the subcommittee election protocols we analyzed at Mechanism Labs (a Twitter account) met either of those two points. Therefore, given the above trade-offs, the blockchain consensus protocol should use a random number source that can generate random numbers continuously, rather than a random number source that can only generate non-disposable random numbers once. Because the blockchain protocol needs to ensure that the blockchain keeps growing and that random sources don’t become bottlenecks. Even for protocols that favor consistency, random number sources should not be the cause of blockchain stagnation. In any case, the random number source should ensure that the protocol can focus on other attacks, such as DoS attacks on sub-committees of examiners to stall the blockchain, etc.
If the blockchain stops completely due to a deviation in the random number output from the random function, then the social layer has to pay a huge coordination cost to restart the blockchain. This would require the community to reach an agreement on what the blockchain actually is through external social media platforms, which would be a very time-consuming discussion that would cost as much as resolving the DAO hack in the first place. The massive cost of the social layer will shake community confidence in the security chain block, but as long as the deviation is very small, and you have to recover from a state of deviation mechanism, then several rounds of small deviation affect block chain security is relatively weak, because the public block chain agreement each round to verifier all rewards are relatively few. The deviations in the random function must be significant for the verifier to cheat the protocol to make money and reduce the security of the blockchain protocol during each cycle or period (each cycle) of the subcommittee election.
On the other hand, lottery games that use random numbers must ensure that the random number source is never manipulated, because even a slight deviation can completely change the winning result. The impact of tampering with lottery results is huge, given the large amount of immediate rewards the winner can receive. Thus, this lottery game favors functions that generate nondominating random numbers once, even if it means that the output of the random function sometimes stops.
This paper will discuss the importance of impartial and unbiased random data source in the context of blockchain protocol design. In the following article, when we consider immutable protocols, we tend to favor protocols that cannot be aborted.
Should satisfy I) not be dominated, and ii) only show random seeds at the start of a new round
Since subcommittee elections take place each round (or period), the time required between the release of the random number output by the random function and 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 verifier has been selected. If this output is hidden, an attacker attempting to attack the blockchain protocol will not know the selected verifier in advance. The length of this time range determines the protocol’s ability to withstand attacks. A stronger attacker, one with more computing power and resources to attack the network, can calculate the chosen verifier in a short time. If the attackers had enough time, they would determine which validators were elected by running the algorithm used by the election committee and the seed of random numbers given for that round, and then conduct a denial of service (DoS) attack on the validators selected for that round, resulting in a blank block and making no progress for that round. Even stopping one round is devastating for blockchain. Imagine what bitcoin would be like if no one in the world could make any transactions for a few hours! Therefore, nodes that are capable of resisting DoS attacks should become verifiers first. 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 have dissected in our meta-analysis of alternative consensus protocols, we will discuss in technical detail the various random number generation mechanisms below.
Tendermint
The Tendermint uses a certain revolving agreement scheme to select proposers; The protocol is not random. Proposers are selected based on a heapsort algorithm based on voting power and the number of times the validator has been selected. An attacker can only interfere with the protocol by adding or deleting rights, but this intervention does not take effect immediately because it takes a long time for the verifier to remove or add rights to the system. However, an attacker can plan much longer in advance how to manipulate the proposer’s choice.
Using deterministic random algorithms means that random seeds are published well in advance of each round and proposers can be identified in advance.
Algorand
Algorand’s random number scheme is as follows: Was elected to the every verifier v use formula < seedr, PI > please VRFskv (seedr – 1 | | r) to calculate r wheel seeds, including SKV key is verifier v, seedr – 1 is a former round of random seed.
VRF is used to prove that the blocks accepted in round R-1 contain PI and the seeds of round R. If the given type VRF (variable refrigerant flowrate) prove that failed to validate a given seed, is everyone to calculate the seeds of a new round of H (seedr – 1 | | r), in which H is the hash function. This means that each verifier’s key must be selected in advance to ensure that they cannot interfere with random seeds.
When the network is not well synchronized, the attacker takes full control of the messaging link, so it can remove proposed blocks and force users to support blank blocks, thereby calculating the random seed for future elections. So Algorand asks
Only when a block is proposed will a new random number seed be generated, along with a public VRF proof that can be verified. This ensures that proposers and random seeds are not leaked ahead of time, and Algorand is able to resist DoS attacks against proposers, even when nodes are offline or even instantaneously corrupted.
Dfinity
For most protocols, the attacker usually aborts the protocol to invoke the fallback mechanism to manipulate random numbers. However, the threshold scheme used by Dfinity is not manipulable, because the principle of choosing the threshold is to ensure that an attacker cannot prevent the generation
It is important to note that in any BLS scheme, as long as the attacker has more than 50% margin, they can manipulate the final signature and random number. However, if one attacker owns such a large share of the equity, other types of attacks can also occur, which violates the basic assumptions of the Dfinity protocol.
Once the honest verifier enters round R, the random seed is revealed. Although the time difference between an honest verifier and the start of a new round is small, it is long enough for an attacker with substantial computing resources to identify the proposer and launch a DoS attack on it. That’s why Dfinity can only deal with mild attackers and not with instant paralysis.
Thunderella
In the scheme of random number predictor instantiated by hash function, the proposer will determine it according to the following formula: H_nonce(PK,q) < Dp, where H is the hash function used as the random number predictor, PK is the public key of the verifier, Q is the given iteration time, and nonce is the entropy source of the hash function. The Nonce is selected by the proposer of the previous block. The difficulty parameter D_p is set so that within a single iteration time, the probability that a committee member will be selected as a proposer is W.
If an attacker proposes a block, she can manipulate the Nonce value that generates entropy for the next round of hash function, thus influencing the choice of the proposer for the next block. 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 of the next round, but also to select the proposer of the next r rounds. This makes it computationally difficult for an attacker to force a change in the nonce value to become the proposer for the next r rounds. Although this strategy only loses polynomial security, it has the downside of predictability (also discussed below). This scheme can only deal with slow adaptive attackers.
In the above algorithm, when the same nonce value is repeatedly used to feed the hash function seeds, the attacker will be able to predict in advance who is the proposer. Because the same nonce value is used as entropy repeatedly in a period, random seeds are leaked before a new round begins, allowing an attacker to corrupt the proposer or perform DoS attacks.
Casper FFG
The Casper FFG project uses a random number scheme based on the following algorithms:
At the beginning of a period, each verifier promises H (H (H (.. Sv)))), where S is the seed of the verifier’s promise. R is assigned the xOR operation of R with the preimage of the inner layer of hash (R := R⊕ pre-image of the inner layer of hash). In a round, the verifier can create or abort a block.
If random numbers are not generated in the fallback mechanism, this can be more of a problem than predictable or manipulable random numbers, because you will no longer need 1/3 of the malefactors to abort the protocol, one person is enough.
The validator who is the current proposer knows the random seed for the next round.
Random numbers are an important part of cryptography and blockchain. Bad random number schemes can undermine blockchain security by: I) stopping the blockchain protocol; Ii) Lead to centralization. Therefore, exploring the role of randomness in the blockchain protocol is a top priority when it comes to understanding blockchain security!
The original link: https://www.tokendaily.co/blog/randomness-in-blockchains author: Aparna Krishnan translation & editing: Zhe sister & sword articles: the etheric fang lovers (https://ethfans.org/ajian1984/articles/35994)Copy the code