From idea to implementation: modifying the existing elliptic curve signature scheme to be deterministic and providing functions on it to obtain verifiable within the blockchain pseudorandom numbers.

Idea

In the autumn of 2018, when first smart contracts were activated on the Waves blockchain, the topic of obtaining pseudorandom numbers in a trusted way arose naturally.

Thinking about it, I came to the conclusion that any blockchain is sort of a cage, and getting a trusted source of entropy in an enclosed system is impossible.

However, I liked one idea. If a random oracle signs user data with a deterministic algorithm, the user will always be able to verify such a signature by the public key to make sure that the obtained value is unique. The oracle wouldn't be able to make any changes because the algorithm comes up with a single-valued result. Basically, the user fixes the result but doesn't know it until it is published by the oracle. So, you may not trust the oracle at all, but still be able to verify the result of its operation. Then, in case of successful verification, such a signature can be a source of entropy for a pseudorandom number.

On the Waves blockchain, the signature scheme EdDSA variant Ed25519 is used. In that scheme, the signature consists of the values R and S. R is dependable on a random value and S is calculated on the basis of a signed message, a private key and the same random number as R. There is no unique dependence, and several valid signatures exist for the same user message.

Apparently, this kind of signature by itself cannot be used as a source of pseudorandom numbers because it is indeterminate and, therefore, can easily be manipulated by the oracle.

However, as it turns out, it's actually possible to make it deterministic.

My high hopes were set for the verifiable random function (VRF), but, after studying its specifics, i have to reject that option. Although VRF offers a determinate version of a signature and its proofs, the algorithm has an odd place that opens a black hole for manipulations by the oracle (this statement is wrong, see Update). Specifically, for calculating the value of k (section 5.1), a private key is used, which remains unknown to the user, so the user cannot verify the correctness of calculating k. As a result, the oracle can use any value of k that it needs and simultaneously run a database for correlations between k and signed data to be able to always re-calculate a correct result for VRF. If you see a VRF-based raffle without revealing the private key, you can show off and point to the need to either reveal the key or remove it from calculating k so it will automatically reveal itself after the first signature. Overall, as said above, this is an odd scheme for the random oracle.

Upon some reflection and with support from local analysts, a scheme for VECRO operation was born.

VECRO stands for the Verifiable Elliptic Curve Random Oracle. It turned out to be rather simple. To achieve determinacy, we need to fix the value of R before appearance of a message to be signed. If R is fixed and R is part of the message, which additionally guarantees that R is fixed before the message. The value of S is completely determined by a user message and, therefore, can be used as a source of pseudorandom numbers.

In a scheme of this kind, how exactly R is fixed is irrelevant and remains in the oracle's zone of responsibility. What is important is that S is completely determined by the user, but its value is not revealed until published by the oracle. This is exactly what we wanted!

Speaking of fixating R, note that re-usage of R for signing various messages completely reveals the private key in the EdDSA scheme. For the oracle's owner, it's vital to exclude re-usage of R for signing various user messages. I.e., in any manipulations or collusion, the oracle will always risk losing its private key.

So, the oracle will offer two functions to the user: initialization, which fixes the value of R and a signature, which returns the value of S. Meanwhile, the R, S pair is a regular verifiable signature for a user message containing a fixed value of R and the user's random data.

One can argue that for blockchain, this is nothing but a regular commit reveal scheme. Basically, that's what it is. But there are a few nuances. First, the oracle uses the same key in all transactions, which, for instance, is convenient for contracts. Second, there is a risk of losing a private key by the oracle because of incorrect performance. For instance, if the oracle facilitates tests of the result, just two tests will be sufficient to figure out the private key and get access to the wallet. Third, a natively verified signature on the blockchain, which is the source of randomness, is just beautiful.

For about six months, this idea was germinating, until a motivation to implement it arrived in the form of a grant from Waves Labs. With the great grant comes great responsibility, it means the project to be!

Implementation

VECRO was implemented on the Waves blockchain in the request/reply mode using transfer transactions between the user and the oracle. On the oracle's account, a script is set that controls operation strictly in accordance with logic described above. The oracle's transactions are verified by recreation of the entire chain of user interaction. All four transactions are involved in verifying the final value. A smart contract adds all of them to a strict verification thread, checking values step by step and leaving no room for any manipulations.

Let's try to put it in simple terms. The oracle doesn't just work under a proposed scheme. Its operation is fully controlled at the blockchain level by a dead-strict smart contract. Any tiny diversion would lead to transaction rejection. So, if the transaction is on the blockchain, users don't have to verify anything, as all verification has already been done by hundreds of the blockchain's nodes.

At the moment, one VECRO is operable on Waves' mainnet. You could actually launch yours: it's simple, just look at the configuration example. The current code works on PHP (on WavesKit, which I discussed earlier).

To use the oracle, you need to:

Fixate R;
- Send a minimum of 0.005 WAVES to the oracle's alias init@vecr;
- Receive an R-code in the attachment field in the 1 R-vecr token transfer from the oracle to the user;
Get a signature;
- Send a minimum of 0.005 WAVES to the oracle's alias random@vecr. You are also REQUIRED to enter in the attachment field the received R-code and additional user data;
- Receive an S-code in the attachment field in the 1 S-vecr token transfer from the oracle to the user;
Use the S-code as a source of pseudorandom numbers.

Nuances of current implementation:

WAVES sent to the oracle are used as fees for the return transaction to the user, up to the maximum of 1 WAVES;
R-code is a concatenation of the ‘R’ symbol byte and 32 bytes R value in the base58 coding;
R-code in the attachment has to precede user data;
S-code is a concatenation of the ‘S’ symbol byte and 32 bytes S value in the base58 coding;
S is the result of a modulo division and cannot be used as a proper 256 bit pseudorandom number (it can be considered a 252 bit pseudorandom number at most);
The easiest option is the use of S-code's hash as a source for pseudorandom number.

Examples of receiving S-code:

Initialization: https://wavesexplorer.com/tx/8gc8jwM7JrPNehoDs7NVyos7BsufYktvkwVW1B6FAY6
Receiving R-code: https://wavesexplorer.com/tx/9eB25SbzEwvHEbm8pcKj7MGDrYv1u3Fxpj696FkJ96hd
Request of signing R-code and user message with value “ random”: https://wavesexplorer.com/tx/6faoFJobEsugDFYmYmfsbtQYABmckNuE2kevaLh7ifzz
Receiving 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 an ordinary user, there is not enough user-friendly GUI, that will have to wait.

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

Update (May 8th, 2019)

I was wrong on VRF. Yes, it is true that the ECVRF signature cannot be used as a source of a pseudorandom number, but it is not used for this purpose. The signature is needed to prove the uniqueness of the Gamma value (section 5.3, step 6). And the verified value of Gamma will be used as a source of a pseudorandom number (section 5.2, step 5). Thanks to Oleg Taraskin Crittografo for pointing at this moment, I admit my mistake. ECVRF has the full right to live.

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

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

Random oracle based on blockchain digital signature