From idea to implementation: we modify the existing digital signature scheme on elliptic curves to make it deterministic, providing on its basis functions for obtaining verifiable pseudo-random numbers within the blockchain.

Idea

In the autumn of 2018, the first smart contracts were activated on the Waves blockchain,immediately raising the question of obtaining pseudo-random numbersthat can be trusted.

Pondering this issue, I ultimately concluded: any blockchain is a closed system, and it is impossible to obtain a trusted source of entropy within it.

However, one idea appealed to me: if a random oracle signs user data using a deterministic algorithm, the user can always verify such a signature with the public key and will be assured that the value obtained is unique. The oracle, regardless of its intentions, cannot change anything; the algorithm produces a definitive result. Essentially, the user records the result but does not know it until the oracle publishes it. This means there is no need to trust the oracle at all, but one can verify the result of its work. Therefore, in case of successful verification, such a signature can be considered a source of entropy for pseudo-random numbers.

The Waves blockchain platform uses a EdDSA variant propertiessigning scheme. In this scheme, the signature consists of values R and S, where R depends on a random value, and S is computed based on the message being signed, the private key, and the same random number as R. Thus, there is no unique dependency; for the same user message, there can be multiple valid signatures.

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

However, as it turns out, making it deterministic is indeed possible.

I had high hopes for the verifiable random function (VRF)., but after studying the material, this option had to be discarded. Although the VRF offers a deterministic signature and its proof, there is a peculiar aspect in the algorithm that opens a loophole for oracle manipulation. Specifically, during the calculation of the value k (section 5.1) a private key is used, which remains unknown to the user, meaning the user cannot verify the accuracy of the k computation; therefore, the oracle can use any desired value of k and simultaneously maintain a database of correspondences between k and signed data to always be able to recompute the correct result from the VRF's perspective. If you see a raffle based on VRF without revealing the private key, you might think about the need to either disclose the key or exclude it from the k calculation, as the private key would automatically be unveiled upon the appearance of the first signature. In general, as already mentioned, a bizarre scheme for a random oracle.

After some contemplation and getting the support of local analysts, a working scheme for VECRO emerged.

VECRO stands for Verifiable Elliptic Curve Random Oracle, which in English means a verifiable random oracle on elliptic curves.

It turned out to be quite simple; to achieve determinism, the value of R must be fixed before the appearance of the message to be signed. If R is fixed and forms part of the signed message, which additionally guarantees the fixation of R in the message itself, the S value can be uniquely determined by the user message and, therefore, can be used as a source for pseudorandom numbers.

In such a scheme, it doesn't matter how R is fixed, that remains the oracle's responsibility. What is important is that S is uniquely defined by the user, but its value remains unknown until the oracle publishes it. Just as we wanted!

Speaking of fixed R, note that reused R When signing various messages, it unequivocally reveals the private key in the EdDSA scheme. For the owner of the oracle, it becomes critically important to eliminate the possibility of reusing R for signing different user messages. In other words, during any manipulations or collusion, the oracle will always risk losing its private key.

In total, the oracle must provide users with two functions: initialization, which fixes the value of R, and signing, which returns the value of S. The pair R, S represents a standard verifiable signature of a user message containing a fixed value of R and arbitrary user data.

It could be argued that this scheme for blockchain is nothing more than a typical commit-reveal scheme.Essentially, yes, it is. However, there are several nuances. First, the oracle always operates with the same key in all operations, which is convenient for use in contracts. Second, there is a risk of the oracle losing its private key due to incorrect behavior; for example, if the oracle allows result sampling, it only takes two samples to learn the private key and gain full access to the wallet. Third, a natively verifiable signature on the blockchain, which serves as a source of randomness, is quite elegant.

For six months, the idea of implementation was nurtured in my mind until finally motivation appeared in the form of a grant from Waves Labs.With a large grant comes great responsibility, which means the project must proceed!

Implementation

Thus, in this project, VECRO was implemented on the Waves blockchain in a request-response mode using transfer transactions between the user and the oracle. The oracle's account has a script that strictly monitors operations according to the logic described above. The oracle's transactions undergo verification, restoring the entire chain of interactions with the user. All four transactions participate in verifying the final value, with the smart contract threading them onto a strict verification path, step by step checking all values and leaving no room for any manipulation.

Once again, to clarify and make it clearer: the oracle does not simply operate according to the proposed scheme. Its operation is fully controlled at the blockchain level by the established script. locked by a smart contract. A step to the left, and the transaction simply won't go through. So, if the transaction has entered the blockchain, the user doesn't even need to verify anything, as hundreds of nodes in the network have already checked it all.

Currently, there is one VECRO launched on the Waves mainnet (you can launch your own, it's not difficult, just take a look at the configuration example). The current code runs on PHP (on WavesKit, which I mentioned earlier To use the oracle service, you need to:).

Fix R;

Send a minimum of 0.005 Waves to the oracle alias init@vecr;
- Receive R-code in the attachment field in the transfer of 1 R-vecr token from the oracle to the user;
- Obtain a signature;
Send a minimum of 0.005 Waves to the oracle alias random@vecr, and also MUST specify in the attachment field the previously obtained R-code and additional user data;
- Receive S-code in the attachment field in the transfer of 1 S-vecr token from the oracle to the user;
- Use the S-code as the source of pseudorandom numbers.
Nuances of the current implementation:

Waves sent to the oracle are used as a fee for the reverse transaction to the user, up to a maximum of 1 Waves;

R-code is the concatenation of the byte of the symbol ‘R’ and the 32-byte value R in base58 encoding;
R-code in the attachment must be first, user data follows the R-code;
S-code is the concatenation of the byte of the symbol ‘S’ and the 32-byte value S in base58 encoding;
S is the result of the modular division, so S cannot be used as a complete 256-bit pseudorandom number (this number can be considered at most a 252-bit pseudorandom number);
The simplest option is to use the hash of the S-code as a pseudorandom number.
Example of obtaining S-code:

Initialization: