From idea to implementation: we modify the existing elliptic curve digital signature scheme to be deterministic, and based on it we provide functions for obtaining pseudo-random numbers verified within the blockchain.
Idea
In the fall of 2018, the Waves blockchain included , immediately the question arose about the possibility of obtaining you can trust.
Puzzling over this issue, 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 will make the signature of user data by a deterministic algorithm, then the user will always be able to verify such a signature using the public key, and will be sure that the resulting value is unique. The oracle, with all its desire, is not able to change anything, the algorithm produces an unambiguous result. Basically, the user captures the result, but doesn't know it until the oracle publishes it. It turns out that you can not trust the oracle at all, but check the result of its work. Then, in case of successful verification, such a signature can be considered a source of entropy for a pseudo-random number.
The Waves blockchain platform uses a signature scheme option . In this scheme, the signature consists of the values ββ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 dependence, for the same user message, there are many valid signatures.
Obviously, in its pure form, such a signature cannot be used 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, it is actually possible to make it deterministic.
I had high hopes for , but having studied the materiel, this option had to be abandoned. Although VRF offers a deterministic version of the signature and its proof, there is a strange place in the algorithm that opens a black hole for oracle manipulation. Namely, when calculating the value of k () a private key is used that remains unknown to the user, which means that the user cannot check the correctness of the calculation of k, which means that the oracle can use any value of k that he needs and at the same time maintain a database of matches k and signed data in order to always be able to re-compute the correct result from the point of view of VRF . If you see a draw based on VRF without revealing the private key, you can be smart: indicate the need to either reveal the key, or exclude it from the calculation of k, then the private key will automatically reveal itself when the first signature appears. In general, as already mentioned, a strange scheme for a random oracle.
After a little thought and with the support of local analysts, the VECRO scheme was born.
VECRO is an abbreviation for Verifiable Elliptic Curve Random Oracle, which in Russian means a verifiable random oracle on elliptic curves.
Everything turned out to be quite simple, in order to achieve determinism, it is required to fix the value of R before the signing message appears. If R is fixed and is part of the message to be signed, which additionally guarantees that R is fixed in the message to be signed, the value of S is uniquely determined by the user's message and can therefore be used as a source for pseudo-random numbers.
In such a scheme, it does not matter how R is fixed, it remains the 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 when signing various messages, it unambiguously reveals the private key in the EdDSA schema. It becomes critical for the oracle owner to ensure that R is not reused to sign different user messages. That is, with any manipulation or collusion, the oracle will always risk losing its private key.
In 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. In this case, the pair R, S is the usual verifiable signature of a 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 . Basically, yes, she is. But there are several nuances. Firstly, 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 due to incorrect behavior, for example, the oracle allows you to make samples of the result, then it is enough to make only two samples to find out the private key and get full access to the wallet. Thirdly, a signature natively verified in the blockchain, which is a source of randomness, is beautiful.
For six months, the idea of ββββimplementation flickered in my head, until finally motivation appeared in the form . With a big grant comes a big responsibility, so the project will be!
implementation
So, in this project on the Waves blockchain in a 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 work strictly in accordance with the logic described above. Oracle transactions are verified with the restoration of the entire chain of interaction with the user. All four transactions are involved in checking the final value, the smart contract strings them on a strict verification thread, checking all the values ββstep by step and leaving no room for any manipulations.
Once again, to put it off and be clearer. The oracle does not just work according to the proposed scheme. Its work is fully controlled at the blockchain level by the established . A step to the left, and the transaction simply fails. So, if a transaction has entered the blockchain, the user does not even need to check anything, hundreds of network nodes have already checked everything for him.
There is currently one VECRO running on the Waves mainnet (you can run your own, it's not difficult, just ). The current code works in PHP (on , about which ).
In order to use the oracle service, you must:
- Fix R;
- Send at least 0.005 Waves to oracle alias init@vecr;
- Get R-code in attachment field in transfer 1 R-vecr token from oracle to user;
- Get a signature;
- Send at least 0.005 Waves to the oracle alias random@vecr, and also MUST indicate the previously received R-code and additional user data in the attachment field;
- Get the S-code in the attachment field in the transfer of 1 S-vecr token from the oracle to the user;
- Use S-code as pseudo-random number source.
Nuances of the current implementation:
- The 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 'R' character byte and the base32 encoded 58-byte R value;
- R-code in attachment must come first, user data comes after R-code;
- S-code is the concatenation of a byte of the character 'S' and a 32-byte base58 encoded value of S;
- 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 a hash from S-code as a pseudo-random number.
An example of obtaining an S-code:
- Initialization:
- Getting R-code:
- Request R-code signing result and user data βrandomβ:
- Getting S-code:
From a technical point of view, the oracle is completely ready for work, you can safely use it. From the point of view of use by an ordinary user, a convenient graphical interface is missing, this will have to wait.
I will be glad to answer questions and accept comments, thank you.
Source: habr.com