A random oracle based on a digital signature on the blockchain

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



    Idea


    In the fall of 2018, the first smart contracts were activated on the Waves blockchain , immediately the question arose about the possibility of obtaining pseudorandom numbers that you can trust.


    Breaking the head 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 a random oracle will make the signature of user data a deterministic algorithm, then the user will always be able to verify such a signature with the public key, and will be sure that the received value is unique. The oracle, with all the desire, is not able to change anything, the algorithm produces a clear result. In fact, the user captures 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 its work. Then, in the case of a successful verification, such a signature can be considered a source of entropy for a pseudo-random number.


    The Waves blockchain platform uses the EdDSA signature scheme, a variant of 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 on the basis of 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 A custom message has many valid signatures.


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


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


    I had high hopes for a tested random function (VRF) , but having studied the materiel, I had to refuse this option. Although VRF offers a deterministic version of the signature and its proof, the algorithm has a strange place that opens 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, that means the user cannot verify the correctness of the calculation of k, then the oracle can use any value of k that he needs and at the same time maintain a database of matches of k and the signed data, so that he can always be able to recalculate the result correct from the point of view of VRF . You will see a VRF-based draw without disclosing the private key, you can think of it: point out the need or open 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.


    With a little reflection and enlisting the support of local analysts, the VECRO workflow was born.


    VECRO is an abbreviation for Verifiable Elliptic Curve Random Oracle, which in Russian means a 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 a signed message. If R is fixed and is part of a signed message, which additionally guarantees that R is fixed in the signed message itself, the value of S is 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, it remains in the oracle’s area of ​​responsibility. It is important that S is uniquely determined by the user, but its value is unknown until the oracle publishes it. Everything as we wanted!


    Speaking of fixed R, note that reused R when signing various 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 to sign different user messages. That is, during any manipulation or conspiracy the oracle will always risk losing his private key.


    In total, the oracle must provide users with two functions: initialization, which fixes the value of R, and a signature, which returns the value of S. Moreover, the pair R, S is a regular verified 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 a normal commit-disclosure scheme . In fact, yes, that's her. But there are a few nuances. Firstly, the oracle always works with the same key in all operations, for example, it is convenient to use 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 do only two tests to find out the private key and get full access to the wallet. Thirdly, the signature that is natively verified in the blockchain, which is a source of randomness, is beautiful.


    For half a year, the idea of ​​implementation was in my head, until finally there was a motivation in the form of a grant from Waves Labs . With a large grant, great responsibility comes, which 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 that monitors the operation strictly in accordance with the logic described above. Oracle transactions are verified to restore the entire user interaction chain. All four transactions participate in the verification of the final value, the smart contract strung them onto a strict verification thread, step by step checking all the values ​​and leaving no room for any manipulations.


    Once again, to be postponed and made more clear. The oracle does not just work according to the proposed scheme. Its work is fully controlled at the blockchain level by a tightly established smart contract . A step to the left, and the transaction simply will not work. So, if the transaction fell into the blockchain, the user does not even need to check anything, hundreds of network nodes have already checked everything for him.


    Currently, one VECRO is running in the Waves main 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 talked about earlier ).


    In order to use the oracle service you must:


    • Fix R;
      • Send a minimum of 0.005 Waves to the oracle alias init @ vecr;
      • Get the R-code in the attachment field in the transfer of 1 R-vecr token from the oracle to the user;
    • Get a signature
      • Send a minimum of 0.005 Waves to the oracle alias random @ vecr, and ALWAYS 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 a pseudo-random number source.

    The nuances of the current implementation:


    • Waves sent to the 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 byte of the 'R' character and the 32-byte base58 encoded R value;
    • R-code in attachment should be the first, user data comes after R-code;
    • S-code is the concatenation of the byte of the 'S' character and the 32-byte base58 encoded S value;
    • S is the result of modulo division; therefore, S cannot be used as a full-fledged 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.

    An example of obtaining S-code:



    С технической точки зрения, оракул полностью готов к работе, можете смело им пользоваться. С точки зрения использования рядовым пользователем, не хватает удобного графического интерфейса, этого придётся подождать.


    Буду рад ответить на вопросы и принять замечания, спасибо.


    Update от 8 мая 2019


    Was wrong about 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. A signature is needed to build a proof of the uniqueness of the Gamma value ( section 5.3 , step 6). But the Gamma value verified using the signature is already participating 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 every right to life.


    Unfortunately, there is still no opportunity 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, in any case, it occupies its own niche and allows you to work without any additional functionality.

    Tags:

    Also popular now: