Introduction

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

As in the case of the concept of an absolutely secure cipher from cryptography, real protocols “Publicly Verifiable Random Beacon” (hereinafter PVRB) only try to get as close as possible to the ideal scheme, because in real networks in its pure form, it is not applicable: it is necessary to agree strictly on one bit, there must be many rounds, and all messages must be ideally fast and always delivered. Of course, this is not the case in real networks. Therefore, when designing PVRB for specific tasks in modern blockchains, in addition to the impossibility of controlling the resulting randomness and cryptographic strength, many more purely architectural and technical problems arise.

The blockchain itself is essentially a communication medium for PVRB, where messages = transactions. This allows you to partially abstract from network problems, non-delivery of messages, problems of middleware - all these risks are assumed by the decentralized network, and its main value for PVRB is the inability to recall or spoil an already sent transaction - this does not allow participants to refuse to participate in the protocol, unless they have launched a successful attack on the consensus. This level of security is acceptable, so PVRB should be exactly as resistant to collusion by participants as the main chain of the blockchain. Also, it hints that PVRB should be part of the consensus, if the network has agreed on the main blockchain, let it agree on the only fair resulting random at the same time. Or, PVRB is just a standalone protocol implemented by a smart contract that works asynchronously with respect to the blockchain and blocks. Both methods have their advantages and disadvantages, and the choice between them is extremely non-trivial.

Two ways to implement PVRB

Let us describe in more detail two options for implementing PVRB - a standalone version that works using a blockchain-independent smart contract, and consensus-integrated - built into a puncture, according to which the network agrees on a chain of blocks and included transactions. In all cases, I will be referring to the popular blockchain engines: Ethereum, EOS, and everything similar to them in terms of hosting and processing smart contracts.

standalone contract

In this version, PVRB is a smart contract that accepts transactions of random producers (hereinafter referred to as RP), processes them, combines the results, and, as a result, comes to some value that any user from this contract can receive. This value may not be stored directly in the contract, but may be represented only by data from which one and only one value of the resulting random can be deterministically obtained. In this scheme, RPs are the users of the blockchain, and anyone can be allowed to participate in the generation process.

The standalone-contract option is good:

• portability (contracts can be dragged from blockchain to blockchain)
• ease of implementation and testing (contracts are convenient to write and test)
• convenience in the implementation of economic schemes (it is easy to make your own token, whose logic serves the purposes of PVRB)
• the ability to run in already running blockchains

It also has disadvantages:

• strong restrictions on resources in computing, the volume of transactions and storage (in other words, cpu / mem / io)
• restrictions on operations within the contract (not all instructions are available, it is difficult to include external libraries)
• inability to organize messaging faster than transactions are included in the blockchain

This option is suitable for implementing a PVRB that needs to be run on an already existing network that does not contain complex cryptography and does not require a lot of interactions.

consensus-integrated

In this variant, PVRB is implemented in the code of the blockchain node, embedded or works in parallel with the exchange of messages between the nodes of the blockchain. The results of the protocol are written directly to the produced blocks, and the protocol messages are sent over the p2p network between the nodes. Since the protocol results in numbers to be written in blocks, the network must come to a consensus about them. This means that PVRB messages, like transactions, must be validated by nodes and included in blocks so that any network member can validate compliance with the PVRB protocol. This automatically leads us to the obvious solution - if the network agrees in consensus about the block and transactions in it, then PVRB should be part of the consensus, and not a stand-alone protocol. Otherwise, it is possible that the block is valid from the point of view of consensus, but the PVRB protocol is not followed, and from the point of view of PVRB, the block cannot be accepted. So if the “consensus-integrated” option is chosen, PVRB becomes an important part of the consensus.

Describing the implementation of PVRB at the level of consensus in the network, in no case can one bypass the issues of finality. Finality is a mechanism used in deterministic consensus to commit a block (and the chain leading to it) that is final and will never be thrown out even if a parallel fork occurs. For example, in Bitcoin there is no such mechanism - if you publish a chain of greater complexity, it will replace any less complex one, regardless of the length of the chains. And in EOS, for example, the so-called Last Irreversible Blocks are final, which appear on average every 432 blocks (12*21 + 12*15, pre-vote + pre-commit). This process is essentially waiting for 2/3 block-producers (hereinafter BP) signatures. When forks appear that are older than the latest LIB, they are simply discarded. This mechanism allows you to guarantee that the transaction is included in the blockchain and will never be rolled back, no matter what resources the attacker has. Also, the final blocks are blocks signed by 2/3 BP in Hyperledger, Tendermint and other pBFT-based consensus. Also, to ensure finality, it makes sense to make the protocol an add-on over consensus, since it can work asynchronously with the production and publication of blocks. Here is a good article about finality in Ethereum.

Finality is extremely important for users who, without it, may fall victim to a “double spend” attack, when BP “holds” blocks and publishes them after the network has “seen” a good transaction. If there is no finality, then the published fork replaces the block with the “good” transaction with another one from the “bad” fork, in which the same funds are transferred to the address of the attacker. In the case of PVRB, the requirements for finality are even tougher, since building forks for PVRB means that the attacker can prepare several variants of randomness in order to publish the most profitable one, and limiting the time of a possible attack is a good solution.

Therefore, the best option is to combine PVRB and finality into one protocol - then the finalized block = finalized random, and this is exactly what we needed to get. Now players will receive a guaranteed random in N seconds, and they can be sure that it is impossible to roll it back or replay it again.

The consensus-integrated option is good:

• the possibility of asynchronous implementation in relation to the production of blocks - blocks are produced as usual, but in parallel with this, the PVRB protocol can work, which does not randomize every block
• the ability to implement even heavy cryptography, without the restrictions imposed on smart contracts
• the ability to organize messaging faster than transactions are included in the blockchain, for example, part of the protocol can work between nodes without propagating messages across the network

It also has disadvantages:

• difficulties in testing and development - you will have to emulate network errors, missing nodes, network hard forks
• Implementation bugs require a hard fork of the network

Both ways of implementing PVRB have the right to life, but implementation on smart contracts in modern blockchains is still quite limited in computing resources, and any transition to serious cryptography is often simply impossible. And we need serious cryptography, as will be demonstrated later. Although this problem is clearly temporary, serious cryptography in contracts is needed to solve many problems, and gradually it appears (for example, system contracts for zkSNARKs in Ethereum)

Blockchain, which provides a transparent and reliable protocol messaging channel, does not do this for free. Any decentralized protocol must take into account the possibility of a Sybil attack, any action can be done by the coordinated forces of many accounts, therefore, when designing, it is necessary to take into account the ability of attackers to create an arbitrary number of protocol participants acting in collusion.

PVRB and block variables.

I was not lying when I said that no one has yet implemented a good PVRB, tested by many gambling applications, in blockchains. Why then such a number of gambling applications in Ethereum and EOS? It surprises me as well as you, well, where did they get so many “persistent” randoms in a completely deterministic environment?

A favorite way to get random on the blockchain is to take some “unpredictable” information from the block, and based on it make random - just by hashing one or more values. Good article about the problems of such schemes here. You can take any of the “unpredictable” values ​​in the block, such as the block hash, the number of transactions, the complexity of the network, and other values ​​unknown in advance. Then hash them, one or more, and, in theory, you should get a real random. You can even add to the wihitepaper that your schema is “post-quantum secure” (since there are quantum-proof hash functions :)).

But even post-quantum secure hashes are not enough, alas. The secret lies in the requirements for PVRB, I recall them from the previous article:

1. The result must have a provably uniform distribution, i.e. based on provably secure cryptography.
2. None of the result bits can be controlled. As a consequence, the outcome cannot be predicted in advance.
3. You cannot sabotage the generation protocol by not participating in the protocol or by overloading the network with attacking messages
4. All of the above must be resistant to collusion by the allowable number of dishonest participants in the protocol (for example, 1/3 of the participants).

In this case, only requirement 1 is met, and 2 is not. By hashing unpredictable values ​​from the block, we get a uniform distribution and good randoms. But BP has at least the option to “publish a block or not”. Thus, BP can at least choose from TWO random options: “his own” and the one that will turn out if someone else makes the block. BP can “peep” in advance what will happen if it publishes a block, and simply decides whether to do so or not. Thus, playing “even-odd” or “red/black” roulette, for example, he can publish a block only if he sees a win. It also makes the strategy of using, for example, a hash of a block “from the future” unworkable. In this case, they say that “the random will be used, which is obtained by hashing the current data and the hash of the future block with a height, for example, N + 42, where N is the current block height. This strengthens the scheme a little, but it still allows BP, albeit in the future, to choose whether to hold the block or publish.

Soft BP in this case becomes more complicated, but not much. It’s just that when validating and including a transaction in a block, there is a quick check whether there will be a win, and, possibly, the selection of one transaction parameters in order to get a high probability of winning. At the same time, it is almost impossible to catch a smart BP for such manipulations, each time you can use new addresses, and win a little, without arousing suspicion.

So methods using information from the block are not suitable for the role of a universal implementation of PVRB. To a limited extent, with limits on bet sizes, limits on the number of players and/or KYC registration (to prevent one player from using multiple addresses), these schemes may work for smaller games, but nothing more.

PVRB and commit-reveal.

Okay, thanks to hashing and at least the relative unpredictability of the block hash and other variables. If you solve the problem of front-running miners, something more suitable should turn out. Let's add users to this scheme - let them also influence randomness: any technical support employee will tell you that the most random in IT systems is user actions 🙂

A naive scheme, when users simply send random numbers, and the result is calculated as, for example, a hash of their sum, is not good. In this case, the last player can choose his own random to control what the result will be. Therefore, the very widely used commit-reveal pattern is used. Participants first send hashes from their randoms (commits), and then open the randoms themselves (reveals). The “reveal” phase begins only after the necessary commits have been collected, so participants can send exactly the random hash from which they sent earlier. Now we blind all this with the parameters of the block, and it’s better to take it from the future (random can be recognized only in one of the future blocks), and voila - the random is ready! Now any player influences the resulting randomness, and can “defeat” the malicious BP by blocking it with his own, unknown in advance, randomness ... You can also add protection against protocol sabotage by not opening it at the reveal stage - simply by requiring a certain amount to be applied to the transaction when committing — an insurance deposit, which will be returned only during the reveal procedure. In this case, making a commit and not making a reveal would be unprofitable.

It was a good attempt, and such schemes are also found in gaming DApps, but alas, this is again not enough. Now the result can be influenced not only by the miner, but also by any participant in the protocol. It is still possible to control the value itself, with less variability and for money, but, as in the case of the miner, if the results of the draw are more valuable than the participation fee in the PVRB protocol, then random-producer (RP) can decide whether to reveal and can still choose from at least two random options.
On the other hand, it became possible to punish those who commit and do not reveal, and this scheme will still come in handy. Its simplicity is a serious advantage - more serious protocols require much more powerful calculations.

PVRB and deterministic signatures.

There is another way to force the RP to provide a pseudo-random number that it cannot influence if it is provided with a “preimage” - this is a deterministic signature. Such a signature is, for example, RSA, and is not ECS. If the RP has a pair of keys: RSA and ECC, and it signs some value with its private key, then in the case of RSA it will get ONE AND ONLY ONE signature, and in the case of ECS it can generate any number of different valid signatures. This is because signature ECS uses a random number chosen by the signer, and can be chosen arbitrarily, allowing the signer to choose one of several signatures. In the case of RSA: “one input value” + “one key pair” = “one signature”. It is impossible to predict what signature another RP will get, so PVRB with deterministic signatures can be organized by combining the RSA signatures of several participants who signed the same value. For example - the previous random. In such a scheme, a lot of resources are saved, because. signatures are both a confirmation of the correct behavior according to the protocol and a source of randomness.

However, even with deterministic signatures, the schema is still vulnerable to the “last actor” problem. The last participant can still decide whether to publish the signature or not, thereby controlling the result. You can refine the scheme, add block hashes to it, make rounds so that the result could not be predicted in advance, but all these tricks, even taking into account many improvements, still leave the problem of the influence of one participant on the collective result in an untrusted environment unsolved and can only work under economic and time constraints. In addition, the size of RSA keys (1024 and 2048 bits) is quite large, and the size for blockchain transactions is an extremely important parameter. Apparently in a simple way to solve the problem will not work, let's move on.

PVRB and secret sharing schemes

There are schemes in cryptography that can allow a network to negotiate one and only one value of PVRB, and such schemes are resistant to any malicious actions by some of the participants. One useful protocol worth familiarizing yourself with is Shamir's Secret Sharing Scheme. It serves to divide a secret (for example, a secret key) into several parts, and distribute these parts to N participants. The secret is distributed in such a way that M parts out of N are enough to restore it, and these can be any M parts. If on the fingers, then having a graph of an unknown function, the participants exchange points on the graph, and after receiving M points, the entire function can be restored.
A good explanation is given in wiki and playing with it practically in order to play the protocol in the head is useful on demo page.

If the FSSS (Fiat-Shamir Secret Sharing) scheme were applicable in its pure form, it would be an indestructible PVRB. In its simplest form, the protocol might look like this:

• Each participant generates their own random and distributes shares from it to other participants
• Each participant reveals his part of the secrets of the other participants
• If a participant has more than M shares, then the number of this participant can be calculated, and it will be the only one, regardless of the set of opened participants
• The combination of opened randoms is the desired PVRB

Here, an individual participant no longer influences the results of the protocol, except for cases when the achievement of the randomness threshold depends on it alone. Therefore, this protocol, in the presence of the necessary share of those working on the protocol and available RPs, works by implementing the requirements for cryptographic strength, and being resistant to the “last actor” problem.

This could be ideal, this PVRB scheme based on Fiat-Shamir secret sharing is described, for example, in this article. But, as mentioned above, if you try to apply it directly in the blockchain, there are already technical limitations. Here is an example of a test implementation of the protocol in the EOS smart contract and the most important part of it is the verification of the published share participant: code. It can be seen from the code that proof validation requires several scalar multiplications, and the numbers used are very large. At the same time, you need to understand that in blockchains, verify occurs at the moment when the block-producer processes a transaction, and in general, any participant should easily check the correctness of the protocol, so the requirements for the speed of the verify function are very serious. In this option, the option turned out to be inoperable, since the verification did not fit into the transaction limit (0.5 sec).

Verification efficiency is one of the most important requirements for the use of any advanced cryptographic schemes in the blockchain. Creation of proofs, preparation of messages - these procedures can be taken off-chain and performed on high-performance computers, but verification cannot be bypassed - this is another important requirement for PVRB.

PVRB and threshold signatures

Having become acquainted with the secret sharing scheme, we have discovered a whole class of protocols, united by the “threshold” keyword. When the disclosure of some information requires the participation of M honest participants out of N, and the set of honest participants can be an arbitrary subset of N, one speaks of "threshold" schemes. It is they who allow you to deal with the “last actor” problem, now if the attacker does not reveal his part of the secret, another honest participant will do it for him. These schemes allow one and only one value to be negotiated, even if the protocol is sabotaged by some of the participants.

The combination of deterministic signatures and threshold-schemes allowed us to develop a very convenient and promising scheme for implementing PVRB - these are deterministic threshold-signatures. Here article about various uses of threshold signatures, and here's another good one longread from dash.

The last article describes BLS signatures (BLS stands for Boneh-Lynn-Shacham, here article ), which have a very important and extremely convenient quality for programmers - BLS public, secret, public keys and signatures can be combined with each other using simple mathematical operations, while their combinations remain valid keys and signatures, making it easy to aggregate many signatures in one and many public keys into one. They are also deterministic and give the same result on the same input data. Due to this quality, combinations of BLS signatures are themselves valid keys, which allows the implementation of an option in which M of N participants produce one and only one signature that is deterministic, publicly verifiable, and unpredictable until it is opened by the Mth participant. .

In a scheme with threshold BLS signatures, each participant signs something using BLS (for example, the previous random), and the common threshold-signature is the desired random. The cryptographic properties of BLS signatures satisfy the requirements for the quality of randomness, the threshold part protects against the “last-actor”, and the unique combinability of keys allows you to implement many more interesting algorithms that allow, for example, effectively aggregating protocol messages.

So if you are building a PVRB on your blockchain, you are very likely to end up with the BLS threshold signatures scheme, several projects are already using it. For example, DFinity(here a benchmark that implements the scheme, and here an example implementation of verifiable secret sharing), or Keep.network (here are their random beacon yellow paper, But example smart contract serving the protocol).

PVRB implementation

Unfortunately, we still do not see a ready-made protocol implemented in PVRB blockchains that has proven its security and stability. Although the protocols themselves are ready, technically applying them to existing solutions is not easy. For centralized systems, PVRB does not make sense, while decentralized ones are strictly limited in all computing resources: CPU, memory, storage, I / O. Designing PVRB is a combination of different protocols in order to still mold something that fits all the requirements for at least some kind of viable blockchain. One protocol computes more efficiently, but requires more messages between RPs, while the other requires extremely few messages, but creating a proof can be a task for tens of minutes or even hours.

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

• Cryptographic strength. Your PVRB must be strictly unbiasable, with no way to control a single bit. In some schemes this is not the case, so call a cryptographer
• The “last actor” problem. Your PVRB must be resistant to attacks where the attacker who controls one or more RPs can choose one of two outcomes.
• Protocol sabotage problem. Your PVRB should be resistant to attacks when an attacker who controls one or more RPs decides whether to be random or not and can be guaranteed or with a given probability to influence this
• Message count problem. Your RPs should send as few messages as possible to the blockchain and avoid synchronous actions such as “I sent some information, waiting for a response from a specific participant” situations as much as possible. In p2p networks, especially geographically dispersed, you should not count on a quick response
• The problem of computational complexity. Verification of any step of the PVRB on-chain should be extremely easy, as it is performed by all full network clients. If the implementation is done using a smart contract, then the speed requirements are very strict
• The problem of accessibility and liveness. Your PVRB should strive to be resilient to situations where part of the network becomes unavailable for a while and part of the RP just stops working
• Trusted setup and initial key distribution problem. If your PVRB uses the primary protocol setup, then this is a separate big and serious story. Here example. If the participants must communicate their keys to each other before starting the protocol, this is also a problem if the composition of the participants changes
• Development problems. Availability of libraries in the required languages, their security and performance, publicity, complex tests, etc.

For example, threshold BLS signatures have a significant problem - before starting to work, participants must definitely distribute keys to each other by organizing a group within which threshold will work. This means that at least one exchange round in the decentralized network will have to wait, and given that random generated, for example, is needed in games, almost in real time, this means that protocol sabotage is possible at this stage, and the advantages of the threshold scheme are lost. . This problem is already simpler than the previous ones, but still requires the development of a separate procedure for the formation of threshold groups, which will have to be protected economically, at the expense of deposits and withdrawal of funds (slashing) from participants who do not follow the protocol. Also, BLS verification with an acceptable level of security simply does not fit, for example, in a standard EOS or Ethereum transaction - there is simply not enough time for verification. The contract code is WebAssembly or EVM, executed by a virtual machine. Cryptographic functions are not implemented natively (yet), and work dozens of times slower than conventional cryptographic libraries. Many protocols do not meet the requirements simply based on the size of the keys, for example, these are 1024 and 2048 bits for RSA, 4-8 times larger than the standard transaction signature in Bitcoin and Ethereum.

The presence of implementations in different programming languages ​​also plays a role - which are few, especially for new protocols. The consensus integration option requires writing a protocol in the platform language, so you will have to look for Go code for geth, Rust for Parity, C ++ for EOS. Everyone will have to look for JavaScript code, and since JavaScript and cryptography are not very close friends, WebAssembly will help, which now definitely claims to be the next important Internet standard.

Conclusion

I hope in the previous article I managed to convince you that the generation of random numbers on the blockchain is critical for many aspects of the life of decentralized networks, and with this article I showed that this task is extremely ambitious and difficult, but good solutions already exist. In general, the final design of the protocol is possible only after conducting massive tests that take into account all aspects from setup to failure emulation, so you are unlikely to find ready-made recipes in whitepapers of teams and in articles, and we will definitely not decide in the next year or two write "do so, so exactly right."

So far, for our PVRB in the development blockchain Haya, we settled on the use of threshold BLS signatures, we plan to implement PVRB at the consensus level, since verification in smart contracts with an acceptable level of security is not yet possible. It is possible that we use two schemes at once: first, expensive secret sharing to create a long-term random_seed, and then we use it as the basis for high-frequency random generation using deterministic threshold BLS signatures, we may limit ourselves to only one of the schemes. Unfortunately, it is impossible to say in advance what the protocol will be, the only good news is that, as in science, in engineering problems, a negative result is also a result, and each new attempt to solve the problem is another step for the research of everyone involved in the problem. To meet the requirements of the business, we are solving a specific practical problem - providing game applications with a reliable source of entropy, so we also have to pay attention to the blockchain itself, in particular, the finality of the chain and the governance of the network.

While we don’t yet see a proven persistent PVRB in blockchains that has been used for enough time to be tested by real applications, multiple audits, loads, and of course, real attacks, but the number of possible paths confirms that a solution exists, and which one one of these algorithms will eventually solve the problem. We will be happy to share the results and thank other teams who are also working on this issue for articles and code that allow engineers not to step on the same rake twice.

So, when you meet a programmer designing a decentralized random, be attentive and caring, if necessary, provide psychological assistance 🙂

Source: habr.com