From idea to implementation: we modify the existing digital signature scheme on an elliptic curve so that it is deterministic, and on its basis we provide the functions of obtaining pseudo-random numbers checked within the blockchain.

Idea

In the autumn of 2018, the first smart contracts were activated in the Waves blockchain, immediately a question arose about the possibility of obtaining pseudo-random numbers that can be trusted.

Breaking head over this question, I finally came to the conclusion: any blockchain is a cell, it is impossible to get a trusted source of entropy in a closed system.

But I still liked one idea: if a random oracle makes the user data signature using a deterministic algorithm, the user will always be able to verify such a signature using the public key and will be sure that the obtained value is unique. The Oracle, with all the desire, cannot change anything; the algorithm produces an unambiguous result. In fact, the user records the result, but does not know it until the oracle publishes it. It turns out that you can not trust the oracle at all, but check the result of his work. Then, in case of successful verification, such a signature can be considered as a source of entropy for a pseudo-random number.

The Waves blockchain platform uses the EdDSA signature scheme version Ed25519 . In this scheme, the signature consists of the values ​​of R and S, where R depends on a random value, and S is calculated based on the message being signed, the private key and the same random number as R. It turns out that there is no one-to-one dependency for the same custom message there are many valid signatures.

Obviously, such a signature cannot be used in its pure form as a source of pseudo-random numbers, since it is non-deterministic and, therefore, can be easily manipulated by the oracle.

But, as it turned out, making it deterministic is actually possible.

I had high hopes for a random function being tested (VRF) , but after studying the hardware, I had to give up this option. Although VRF offers a deterministic version of the signature and its proof, there is a strange place in the algorithm that opens up a black hole for manipulating the oracle (this is a false statement, see Update ). Namely, when calculating the value of k ( section 5.1 ), the private key is used, which remains unknown to the user, which means the user cannot verify the correctness of the calculation of k, so the oracle can use any k value he needs and simultaneously maintain a database of correspondences k and the data being signed to always be able to recalculate the VRF-correct result. You will see a drawing based on VRF without disclosing the private key, you can pomnichat: indicate the need to either unlock the key, or exclude it from the calculation of k, then the private key will automatically open itself when the first signature appears. In general, as already mentioned, a strange scheme for a random oracle.

After a little thought and enlisting the support of local analysts, the VECRO scheme of work was born.

VECRO is an abbreviation of Verifiable Elliptic Curve Random Oracle, which in Russian means the checked random oracle on elliptic curves.

Everything turned out to be quite simple, to achieve determinism, it is necessary to fix the value of R before the appearance of the message being signed. If R is fixed and is part of the message being signed, which additionally ensures that R is fixed in the message itself, the value of S is uniquely determined by the user message and, therefore, can be used as a source for pseudo-random numbers.

In such a scheme, no matter how fixed R, it remains in the area of ​​responsibility of the oracle. It is important that S is uniquely defined by the user, but its value is not known until the oracle publishes it. Everything we wanted!

Speaking of fixed R, note that the reused R when signing different messages uniquely reveals the private key in the EdDSA scheme. For the owner of the oracle, it becomes extremely important to exclude the possibility of reusing R for signing different user messages. That is, with any manipulation or collusion, the oracle will always risk losing its private key.

Total, the oracle should provide users with two functions: initialization, which fixes the value of R, and a signature, which returns the value of S. At the same time, the pair R, S is the usual checked signature of the user message containing a fixed value of R and arbitrary user data.

It can be argued that this scheme for the blockchain is nothing more than the usual commit-disclosure scheme . In fact, yes, it is she. But there are a few nuances. First, the oracle always works with the same key in all operations, for example, it is convenient to use it in contracts. Secondly, there is a risk of losing the private key by the oracle if the behavior is incorrect, for example, the oracle allows you to sample the result, then just two samples are enough to find out the private key and get full access to the wallet. Thirdly, the signature that is natively checked in the blockchain, which is a source of randomness, is beautiful.

For half a year the idea of ​​realization was warming in my head, until finally the motivation in the form of a grant from Waves Labs appeared . With a big grant comes a big responsibility, it means the project to be!

Implementation

So, in this project, VECRO was implemented on the Waves blockchain in the request-response mode using transfer transactions between the user and the oracle. At the same time, a script is installed on the oracle account, which controls the operation strictly in accordance with the logic described above. Oracle transactions are tested with the restoration of the entire chain of user interaction. All four transactions are involved in the verification of the final value, a smart contract strings them onto a strict verification thread, checking all values ​​step by step and leaving no room for any manipulations.

Once again, to postpone and be clearer. Oracle does not just work on the proposed scheme. His work is fully controlled at the blockchain level by a tightly installed smart contract . Step to the left, and the transaction simply will not pass. So, if the transaction hit the blockchain, the user doesn’t even have to check anything, hundreds of network nodes have already checked everything for him.

Currently, one VECRO is running in the main Waves network (you can run your own, it’s not difficult, just look at the configuration example ). The current code works in PHP (in WavesKit , which I mentioned earlier ).

In order to use the service of the oracle, you must:

• Fix R;
  
  • Send at least 0.005 Waves to the oracle alias init @ vecr;
  • Get the R-code in the attachment field in the 1 R-vecr token transfer from the oracle to the user;
• Get a signature;
  
  • Send at least 0.005 Waves to the random @ vecr alias of the oracle, and also MUST indicate in the attachment field the previously received R-code and additional user data;
  • Get S-code in the attachment field in the 1 S-vecr token transfer from the oracle to the user;
• Use S-code as the source of a pseudo-random number.

Nuances of the current implementation:

• Sent to the Waves oracle are used as a commission for a reverse transaction to the user, up to a maximum of 1 Waves;
• R-code is the concatenation of the 'R' character byte and the 32-byte R value in base58;
• R-code in the attachment should be the first, user data comes after R-code;
• S-code is the concatenation of the 'S' character byte and the 32-byte S value encoded in base58;
• S is the result of modulo division, so you cannot use S as a full 256-bit pseudo-random number (this number can be considered a maximum of 252-bit pseudo-random number);
• The simplest option is to use the hash from S-code as a pseudo-random number.

S-code receiving example:

• Initialization: https://wavesexplorer.com/tx/8gc8jwM7JrPNehoDs7NVyos7BsufYktvkwVW1B6FAY6
• Getting R-code: https://wavesexplorer.com/tx/9eB25SbzEwvHEbm8pcKj7MGDrYv1u3Fxpj696FkJ96hd
• Query the result of the R-code signature and “random” user data: https://wavesexplorer.com/tx/6faoFJobEsugDFYmYmfsbtQYABmckNuE2kevaLh7ifzz
• Getting S-code: https://wavesexplorer.com/tx/C5VrFLQcprbA1KXAToaNvMP4Kg2rq43NkwWuADAA7wXX

From a technical point of view, the oracle is fully operational, you can safely use it. From the point of view of use by an ordinary user, there is not enough user-friendly graphical interface, this will have to wait.

I will be glad to answer questions and accept comments, thank you.

Update of May 8, 2019

Was wrong about the VRF. Yes, indeed, the ECVRF signature cannot be used as a source of a pseudo-random number, but it is not used for this purpose. The signature is needed to construct a proof of the unambiguity of the Gamma value ( section 5.3 , step 6). But the value tested with the signature Gamma already participates as a source of a pseudo-random number ( section 5.2 , step 5). Thanks to Oleg Taraskin Crittografo for pointing out at this point, I admit my mistake. ECVRF has the full right to life.

Unfortunately, there is still no possibility to use ECVRF at the Waves blockchain level, due to the lack of the necessary mathematical apparatus in smart contracts.

When this functionality or RSA support becomes available, you can write new oracles. As for the VECRO scheme, it in any case occupies its own niche and allows you to work without any additional functionality.