Random numbers and decentralized networks: implementation

function getAbsolutelyRandomNumer() {
return 4; // returns absolutely random number!
}

As many cryptographic concepts, "Publicly Verifiable Random Beacon" protocols (or PVRB for short) are only approaching the ideal scheme, and cannot avoid fundamental restrictions. The ideal scheme is not applicable in real networks: there should be a consensus about the only bit in a round, the number of rounds, and network messages that must be fast and always delivered. It's not the case for real networks. Custom PVRB solution development for modern blockchains involves many architectural and technical problems other than inability to control random number generation and strength of cryptographic algorithms.

Blockchain as such is a communication medium for PVRB, where messages=transactions. For now, we can forget about network problems, message non-delivery, intermediate software issues - all these risks are handled by the decentralized network. PVRB benefit from its inability to rollback or spoil an already sent transaction, plus participants cannot refuse to participate in the protocol, unless they successfully attacked the network consensus. Since the level of security is acceptable, PVRB must be resistant to collusion between participants as much as the main chain of the blockchain. There is a hint that PVRB should be part of a consensus; if the network agrees on the main chain, it shall also agree on correct resulting random numbers. Otherwise, PVRB is just a standalone protocol supported by a smart contract, working asynchronously with blockchains and blocks. Both methods have their advantages and disadvantages, and the choice between them is quite difficult.

We will describe in more detail two options: a standalone version based on a blockchain-independent smart contract, and a consensus-integrated one, embedded into the protocol (the network agrees on transactions and blocks to be included). For each case, I will refer to the popular blockchains: Ethereum, EOS, and those having a similar way to store and process smart contracts.

Here PVRB is a smart contract that accepts transactions from random producers (hereinafter RP), processes them, combines the results, and eventually generates some value that any contract user can receive. This value may not be stored directly in the contract but have data representation and thus allow to determine the only value of the resulting randomness. In this scheme RPs are blockchain users, and anyone can participate in the generation process.


The standalone contract option looks good due to:

• portability (contracts can be "dragged" between blockchains)
• easy implementation and testing (it is convenient to write and test contracts)
• convenient economic schemes (it is easy to create your own token with PVRB-specific logic)
  
• applicable to working blockchains
  

It also has disadvantages:

• strong restrictions on consumed computing resources: transaction complexity, volume, network speed and blockchain storage (in other words, traditional cpu/mem/io/storage)
  
• restrictions on internal contract machine instructions (not all instructions are available, it is difficult to connect external libraries)
  
• messaging cannot be faster than the speed of transactions being included in the blockchain
  

This option is suitable in case we want to run PVRB in an existing network that does not contain complex cryptography and does not require a large number of interactions.

Here PVRB is embedded in a blockchain node code or works in parallel with blockchain node messaging. Protocol results are directly written into produced blocks, whereas protocol messages are sent across p2p network between the nodes. Since the protocol numerical results need to be written in blocks, the network must come to a consensus on them. This means that PVRB messages, as well as transactions, must be validated by the nodes, and included in the blocks (so that any member of the network could verify compliance with the PVRB protocol). This automatically leads us to the obvious solution - if the network reaches a consensus on a block and its transactions, then PVRB should be part of a consensus, not a standalone protocol. Otherwise, the block is valid in terms of consensus, but since PVRB protocol is not followed, the block cannot be accepted. So, if the "consensus-integrated" option is chosen, PVRB becomes an important part of the consensus.

Speaking about PVRB implementations on a network consensus level, finality issues cannot by any means be avoided. Finality is a mechanism used in deterministic consensuses, it fixes a "finalized" block (and a chain leading to it) that will never be discarded even in case of a parallel fork. For instance, Bitcoin does not have such mechanism - if you publish a chain with more complexity, it will replace any other chains with less complexity, irrespective of a chain "age" and length. In EOS, for example, there are so-called Last Irreversible Blocks that are considered finalized. They appear on average every 432 blocks (12*21 (pre-vote) + 12*15 (pre-commit)). This process in fact involves waiting until 2/3 of block producers (or BPs) put their signatures on these LIB blocks. Forks that are older than the last LIB are simply discarded. This mechanism guarantees that the transaction is included in the blockchain and will never be rolled back, no matter what resources the attacker has. Moreover, the blocks signed by 2/3 of BPs in Hyperledger, Tendermint and other pBFT-based consensuses, are also considered final. It makes sense to develop a protocol ensuring finality as a consensus add-in, since it is able to work asynchronously with block production and publication. Here is a good article about Ethereum finality.

Finality is crucial for users who are potential victims of a "double spend" attack - when a BP "holds" the blocks and publishes them after the network "sees" a good transaction. If there is no finality, then the published fork replaces the block with a "good" transaction with another one, from a "bad" fork, with the funds being transferred to the attacker's address. PVRB have tougher finality requirements, as fork construction means that the attacker can prepare several random number options and publish the most beneficial one. Thus, limiting the time of a possible attack is a good solution.

Therefore, the best option is to combine PVRB and finality in one protocol - then a finalized block will be equal to a finalized random number - that is exactly what we aim to obtain. From now players will get a guaranteed random number in N seconds and be sure that it is impossible to roll it back or replay it.


The consensus-integrated option looks good:

• possible asynchronous implementation in relation to block production - blocks are produced as usual, but PVRB protocol can work in parallel and produce random numbers for each block
  
• ability to implement even complex cryptography, without smart contract restrictions
  
• ability to organize messaging faster than the speed of transactions included in the blockchain, for example, a part of the protocol can function between nodes without network interactions

It also has disadvantages:

• difficulties in testing and development - you will have to emulate network errors, missing nodes, and network hardforks
  
• implementation errors require a network hardfork

Both ways of implementing PVRB are acceptable, but smart contracts in modern blockchains are still quite limited in terms of computing resources, that makes any serious cryptography close to impossible. But this situation is becoming better and better every year. We can mention pre-compiled system contracts for zkSNARKs in Ethereum as an example.

Blockchain providing a transparent and reliable protocol messaging channel is not free of charge. Any decentralized protocol must take into account possible Sybil attacks, any action can be made if coordinated by multiple accounts. While developing, bear in mind the attackers are able to create a collusion from an arbitrary number of protocol participants.

I didn't lie by saying that no one has yet (by spring 2019) implemented a good, strong PVRB in the blockchain and tested it in gambling applications. Where does such a number of gambling applications in Ethereum and EOS come from? I am just as surprised as you are: how there can be so many "strong" random numbers in a fully deterministic environment?

My "favorite" way to get random numbers in blockchain is to take some "unpredictable" information from the block and generate a random number on its basis - by simply hashing one or more values. A good article about possible flaws of such schemes can be found here. You can also choose any other "unpredictable" value in the block, for example, a block hash, a number of transactions, network complexity, and other unknown values. Then you hash one or some of them, and, in theory, obtain a good random number. You can even write in the white paper that your scheme is "post-quantum secure" (since there are quantum-proof hash functions :)).


Alas, even post-quantum secure hashes are not enough. The secret lies in PVRB requirements, I will quote from the previous article:

1. The result should have a provably uniform distribution, i.e. based on strong cryptography.
   
   
2. It is impossible to control any bit of the result. Therefore, the result cannot be predicted in advance.
   
   
3. It is impossible to sabotage the generation protocol by non-participation in the protocol or by overloading the network with attacking messages.
   
   
4. Everything stated above should be resistant to the collusion of an acceptable number of dishonest protocol participants (for example, 1/3 of the participants).
   

In this case, only the first requirement is met. By hashing unpredictable block values, we will get a uniform distribution and correct random numbers. BPs are at least able to decide whether to "validate a block or not" and choose from TWO random variants: "its own" one and the one generated if the block was made by someone else. A BP can cheat, withholding a block to see what happens next, and then decide whether to publish it or not. Thus, making an "even-odd" or "red/black" roulette bet, for instance, he can publish a block only in case of gain. There's also little sense in using parameters of a future block, for example, a hash of the block that only is going to be generated. In this case, they say that "randomness is obtained by hashing the current data and a future block with height equal to N+42, where N is a current block height". This slightly strengthens the scheme, but a BP will still be able to choose whether to hold or publish a block.

Performing such attacks in block producing software is not a complicated task. When validating and including a transaction in a block, there is a quick check to see if there will be a gain, and possible selection of a transaction parameter to increase winning probability. At the same time, catching a smart BP performing such manipulations is almost impossible, because each time he can use new addresses and win little by little without arousing suspicion.

So, the methods based on block data are not suitable for the role of universal PVRB implementation. In a short version with restrictions on bet sizes, number of players and/or KYC registration (in order to forbid a player use several addresses), these schemes work only for small games.

Well, at least we have hashing, an "almost unpredictable" block hash and other variables. If we manage to solve the issue of front-running miners, we might get something more worthy. Let's add users to this scheme and allow them to affect randomness results: any technical support employee will tell you that the most random matter in IT systems is user actions :)

A "naive" scheme where users simply send random numbers and the results are calculated via hashing their common product, is a bad scenario. In this case, the last player can choose his own random number to control the result. That is why it is better to use a well-known commit-reveal pattern. First, participants send hashes of their random numbers (i.e. "commits"), then submit the original random numbers ("reveals"). The "reveal" phase starts as soon as all necessary commits are collected, i.e. participants can only send a random number of the previously submitted hash. Now we will add block parameters - better to use those of a future block, as random numbers will appear only in one of the next blocks - and voila! Randomness is here! Now any player may affect the resulting randomness and is able to "defeat" a malicious BP by blocking it with its own unpredictable randomness... You can also increase protocol security by requesting some transaction fee for "commit" - a security deposit, that will be returned only during the "reveal" procedure. In this case, committing without revealing will be unprofitable.

It was a good attempt (such schemes are also used in different DApps). Alas, this is not enough again. Now, not only a miner can influence the result, but also any participant of the protocol. It is still possible to control a value, with less variables and for money, but as in the case with a miner, if the reward is more than PVRB protocol participation fee, then a randomness producer (RP) can decide whether to reveal and choose from at least two random number options.

Well, at least we have an opportunity to punish those who submit commits without reveals, and this scheme will be useful later. In addition, its simplicity is also a serious advantage, as more serious protocols require much more computations.

Deterministic signature is another good way to make an RP generate a pseudo-random number that it wouldn't be able to influence. For instance, RSA signature is one of them while ECS (Elliptic Curves signature) is not. If an RP has a pair of keys (RSA and ECS), and he signs some value with his private key, RSA allows to produce ONE unique signature, while ECS allows to generate any number of valid signatures. When creating an ECS signature, the signer may select a random number any way he likes, thus having an opportunity to choose one of several signatures. With RSA it's like "one input value" + "one key pair" = "one signature". It is impossible to predict another RP's signature, so PVRB with deterministic signatures can be structured by combining RSA signatures of several participants who have signed the same value, for instance, a previous random number. Such scheme saves a lot of resources because signatures serve both as confirmation of correct protocol behavior and the source of randomness.

However, deterministic signatures are not almighty and the scheme is still vulnerable to the "last actor" issue. The last participant can still decide whether to publish a signature or not, thereby controlling the result. We can refine the scheme, add block hashes, make rounds so that the result cannot be predicted in advance, but all these techniques will not solve the problem of the participant's influence on a collective result in an untrusted environment and are effective only in terms of economic and time constraints. In addition, an RSA key can be quite long ((1024 and 2048 bits) that is an extremely important parameter for blockchain transactions. Apparently, there's no simple way to solve this issue, let's move on.

There are cryptographic schemes that allow the network to negotiate a unique PVRB value, while staying resistant to any malicious actions of some participants. One of such useful protocols is Shamir's secret sharing. It serves to divide some secret (for example, a secret key) into several parts, and distribute these parts to N number of participants. The secret is distributed in a way that it is enough to have M parts from N to restore it, and these can be any M parts. To put it simply, having a graph of an unknown function, participants exchange points on the graph, and after receiving M points, the entire function can be restored (you need two points for linear function, three points for quadratic, etc...).

A good explanation is given in wiki; you can also try out the protocol in a real time mode at this demo page.


If the FSSS (Fiat-Shamir Secret Sharing) scheme could be applied in its pure form, PVRB would be invulnerable. In its simplest form, the protocol may look like this:

• Each participant generates a random number and distributes its shares to others
  
• Each participant reveals the secret parts of other participants
  
• If a participant has collected more M-shares, his number can be calculated. This number is unique irrespective of the "revealed" participants set
  
• The required PVRB is a combination of revealed random numbers
  

Here, an individual participant no longer affects the protocol results, except for a very rare ability to break protocol when randomness reveal threshold (M from N) depends exactly on him. Therefore, given that there is a necessary amount of available honest RPs following the rules, the protocol works in accordance with strong cryptography requirements and stays resistant to the "last actor" issue.

This could be an ideal option. The PVRB scheme based on Fiat-Shamir secret sharing is described, for example, in this article. As I have already mentioned above, if you try to apply it in the blockchain its pure form, technical restrictions inevitably come up. Here is an example of the protocol test implementation in the EOS smart contract, and the most important part of it is checking the published share of the participant: code. It is clear that proof validation requires several scalar multiplications, and the numbers are very large. At the same time, we should bear in mind that in blockchains the verify function is called when the block-producer processes a transaction. In general, any participant should easily verify correctness of the protocol, that's why speed requirements for the "verify()" function are very strict. Our scheme did not work out, since verification did not meet transaction time restriction (0.5 sec).

Verification efficiency is one of the most important requirements for any advanced cryptographic scheme in the blockchain. Proof and message creation can be taken off-chain and fulfilled by high-performance computers, but verification cannot be neglected - this is another important PVRB requirement.

Secret sharing scheme opens up a whole class of protocols united under the "threshold" umbrella. We can speak about "threshold" schemes when we need M honest participants from N to disclose some information, and the set of honest participants can be an arbitrary subset of N. They allow to deal with the issue of the "last actor": if the attacker does not reveal his part of the secret, another honest participant will do it instead. In turn, this enables us to agree on the only meaning, even if some participants are sabotaging the protocol.

Combining deterministic signatures and threshold-schemes, we get to develop a very convenient and promising PVRB scheme - deterministic threshold-signatures. Here's an article about various threshold-signatures and use cases, another good longread by Dash is available here.

The last article covers BLS public and private signatures and keys (BLS stands for Boneh-Lynn-Shacham, you can learn more here, that can be combined using simple mathematical operations - that comes in handy for developers. The combinations remain valid keys and signatures, making it easy to aggregate many signatures into one and many public keys into one. Their determinism allows to obtain the same result having the same input data. Due to this quality, BLS signature combinations become valid keys, which makes it possible for M honest participants from N total to produce the only signature that is deterministic, publicly verifiable, and unpredictable until revealed by the M participant .

In the BLS threshold signature scheme each participant signs something using BLS (for example, the previous random number) and sends his share to the blockchain. Cryptographic properties of BLS signatures satisfy randomness quality requirements, as the threshold-part protects against the "last-actor", and the unique compatibility of keys allows for many interesting algorithms (for example, ones that effectively aggregate protocol messages).

So, if you are building PVRB for your blockchain in spring-summer 2019, you will most likely come to the BLS threshold signatures scheme; several projects are already using it. For example, DFinity (here) a benchmarking tool that implements the scheme, and here is an example of verifiable secret sharing implementation), Keep.network (here is their random beacon yellowpaper, and here is an example of a smart contract servicing the protocol an example.

Unfortunately, there is still no real cryptographically strong PVRB blockchain protocol, which has proved its safety and stability in real DApps. In spite of the fact that the existing protocols are ready-made, it is not easy to apply them to existing solutions. PVRB is useless for centralized systems, whereas decentralized systems have strictly limited computing resources: CPU, memory, storage, I/O. Developing a PVRB involves combination of different protocols so that it can match at least one real viable blockchain. One protocol is more efficient for computations but may require more messages between RPs, another one needs a few messages but proof-creation takes dozens of minutes or even hours etc...


I will list the factors that you have to consider when choosing a high quality PVRB:

1. It should be cryptographically strong, i.e. strictly unbiasable, unable to give a control over a single bit or any statistical properties to anyone. For some schemes this is not the case, so you better address a cryptographer.
   
   
2. The "last actor" problem. Your PVRB must be resistant to the attacks when an attacker controlling one or several RPs can choose between two possible outcomes.
   
   
3. Protocol sabotage. Your PVRB must be resistant to attacks when an attacker controlling one or several RPs decides whether to generate a random number or not, and is able to affect random beacon production.
   
   
4. Number of messages. Your RPs should send a minimal amount of messages to the blockchain and avoid as much as possible synchronous actions such as "information sent, waiting for the response of a specific participant". You should not expect a quick response in p2p networks, especially from geographically distributed ones.
   
   
5. Computational complexity. On-chain verification of any PVRB stage should be easy, as it is performed by all full network clients. In case of a smart contract implementation, speed requirements are very strict.
   
   
6. Accessibility and liveness. Your PVRB should be resilient to possible network failures (i.e. when it's unavailable for some time and a part of RPs stopped working).
   
   
7. Trusted setup and initial key distribution. If your PVRB involves primary protocol setup, this may lead to certain problems. Here is an example. If participants have to tell each other their keys before starting the protocol - this is also a problem as the list of participants may change.
   
   
8. Development issues. Availability of libraries in the required languages, their security and performance, public accessibility, complex tests, etc.
   
   

For example, threshold BLS signatures have a significant bottleneck - before the start, participants must share the keys and organize a threshold group. This means that we will have to skip at least one round in a decentralized network, and, given that a random number is essential for games in real-time mode, there's high risk of protocol sabotage, and the advantages of the threshold scheme become useless. This problem is simpler than the previous ones but we still need to develop a separate threshold group procedure, that has to be economically-protected via deposits and funds withdrawal (slashing) of the participants who do not follow the protocol. Also, BLS verification with an acceptable security level overlaps a standard EOS or Ethereum transaction - there isn't enough time to do that. The contract code is executed by the virtual machine - WebAssembly or EVM. Cryptographic functions have not yet been implemented natively, and are many times slower than the ordinary cryptographic libraries. Many protocols simply do not meet key length requirements: for example, 1024 and 2048 bits for RSA. That is 4-8 times bigger than the standard Bitcoin and Ethereum transaction signature size.

There should also be implementations in different programming languages, which are not numerous, especially for new protocols. To integrate PVRB into consensus, we should write the code in the platform language, i.e. look for Go code for geth, Rust for Parity, and C++ for EOS. JavaScript code is even harder to find, and since JavaScript and cryptography are not on close terms, choose WebAssembly. It looks like becoming the next important Internet standard.