Verifiable Random Function (VRF) #706

Congrats for the great repo!

Here is a suggestion:

What about an implementation of a Verifiable Random Function using the secp256k1 curve?

Having a secure VRF in this library, or as a separate code that uses this library, would be a really useful piece of code.

The Algorand team created one using the ed25519 curve and sha512 in a forked libsodium repo. You can check it out here

I found implementations using secp256k1 and sha256 in other languages:

• Rust: vrf-rs
• Go: chain33
• Solidity: vrf-solidity

But none in C

The last version of IETF draft for VRFs (at this date) is draft-irtf-cfrg-vrf-05

Without an extremely clear understanding of at least some relevant applications its unlikely that this library could provide an acceptable safe interface-- e.g. does the hash_to_curve need to be constant time-- it's much slower, but necessary when the message/hash is secret from some parties. Otherwise this is a pretty low level primitive.

I'm not aware of any particular reason this function would be of interest to any of the regular contributors to the library.

It's very similar in structure/aim to the P(o)odle from JM since 2016: https://joinmarket.me/blog/blog/poodle/ -- JM's poodle has a small number of fixed messages an uses the resulting random value as a commitment to an unrevealed public key that no one else could compute, while the IETF VRF just leaves the 'message' as an input.

To save other contributors time in understanding what this even is, using conventional variable names:

• There is a prover with a keypair (x, xG) and a verifier which knows the public key (xG).
• The prover takes a message and emits a proof. Anyone with the proof and message and the pubkey can extract a consistent hash.
• The proof is proof of discrete log equivalence between the pubkey and a point (H) created by hashing the pubkey and the message. The challenge hash in the DLEQ is {H,xH,message,kG,kH} -- it does not commit to the pubkey except indirectly through H, the proof is xH,s,e -- (it's in e,s form).

Use of the e,s form probably was chosen because it saves 32 bytes (otherwise you'd have to send both nonces)... but it breaks batch validation which would otherwise work. Verifying requires a hash-to-curve and two independent multiexps.

If the message and pubkey were generated randomly the resulting hash is close to uniform (given kind of handwavy assumptions about the hash functions being used being uniform enough). The 'random value' is not close to uniform if the attacker can choose the message with knowledge of the pubkey, or the pubkey with knowledge of the message.

Functionally it's similar to just using a BLS signature as a hash, though bigger but faster to verify if you wouldn't otherwise be able to batch the BLS validation, probably slower if batching would be possible for BLS.

Unlike a BLS hash, this construction is not designated verifier sidechannel free. You can store a message in the nonce (you can either store a message in the secret key that can be decoded by someone who can derrive the nonce, or just grind sidechannel data into the nonce itself)... so I don't think it couldn't be used for the p2sh^2 anti-data-embedding trick.

In blockchains, VRFs can be used to prove that a generated random number is correct.

Example: selecting a node to be the next block producer without using proof-of-work.

Each node has its private/secret key and shares its public key with other nodes, so they can verify that the generated random number from a specific node is correct and it was not modified. Nodes calculate this random number using their private key and a publicly known seed, different at each round.

Using VRFs makes the process non-interactive: they do not need to exchange many messages to reach a consensus on some global random number.

In blockchains

It's not obvious from the name of this library but "the primary focus of its development has been for usage in the Bitcoin system" (from the README, emphasis added). I'm not aware of an application in Bitcoin-land that uses a VRF. There's the somewhat less focused secp256k1-zkp fork where a VRF may get merged if it's behind a sane API with a clear protocol description.

It's unclear to me why a 'blockchain application' wouldn't prefer to use:

(1) The hash of a BLS signature as it would be smaller, batch verifiable, simpler to implement from existing primitives and much easier to create a threshold random beacon (non-interactive multiparty, too). The BLS 'proof' also has no sidechannel which can be used to carry hidden data, which is important when the purpose of the verifyable hash is side-channel elimination.

Or (2) an alternative construction for this DLEQ which is batch verifyable but slightly larger.

Or, if proof sizes and speeds aren't much of an issue, (3) something like purify where the 'random value' is a EC point with a prover known discrete log-- which allows using it as a nonce in a single show signature ("leak your private key if you sign more than T times for a given VRF context").

I can totally believe that this construct would be the best fit for some application... but I would have to to have at least one full application in mind to make a good interface. And when I think of applications (or, rather, consider similar application's we've discussed in the past)-- other known/obvious constructions sound obviously better to me.

Is it obvious to anyone why the public key is included in the hash-to-curve instead of just the ordinary generator? Use of the public key in that hash prevents an optimization where many VRFs of the same message can share the same hash to curve and multiexp precomputation.

As far as I understand, batch verification is not of use in a case where there is no signature aggregation. Each selected node sends the generated random number + the proof. The receiver nodes only need to verify the proof from this single or few nodes.

It should not be single use too. Generating many random numbers should not reveal bits of the private key.

Anyway, it was just an idea of implementation of the IETF draft so it could be used in many different applications, not only on a specific use case.

For example, say you want to validate a million block history. With scalar validation you'll be doing two multiexps per block, but with batch validation you could do one big batch with all two million at once (or more realistically groups of a moderate amount at time for engineering reasons). Signature aggregation doesn't come into it. (though this sort of thing could also be batch validated along with signatures if they were constructed using the same curve)

It's not obvious from the name of this library but "the primary focus of its development has been for usage in the Bitcoin system" (from the README, emphasis added). I'm not aware of an application in Bitcoin-land that uses a VRF. There's the somewhat less focused secp256k1-zkp fork where a VRF may get merged if it's behind a sane API with a clear protocol description.

I agree. I'm closing this because there's no need for a VRF in the Bitcoin ecosystem currently. Let me stress that does not mean that there won't be a use case in the future. But I feel confident enough to speak for the maintainers and regular contributors that there is no interest in an implementation of a VRF currentluy. Feel free to object, of course.

And please feel free to discuss this further. The fact that the issue is closed does not mean that we can't discuss further.

For those interested, I implemented an elliptic curve based Verifiable Random Function (VRF) using a fork of this library here

It is in a fork because the required functions are not exported, otherwise it could be just a code dependent of this library.

The library is compiled under a different name, so both can be present on the same device.

It is based on the IETF VRF draft 05

Any review is welcome.