VRFs for secp256k1?

[ChristopherA]

Is anyone working on, or considering adding VRF support to secp256k1-zkp?

There is a fork of libsecp at https://github.com/aergoio/secp256k1-vrf that implements it. (/cc by @aergoio @kroggen)

from: README.md#verifiable-random-function-vrf:

This library has an implementation of an ECVRF based on the IETF draft 05 using the secp256k1 curve, SHA256 as hash function and try-and-increment as hash to curve method (cipher suite SECP256K1_SHA256_TAI). The cipher suite code used is 0xFE for compatibility with other implementations.

It was implemented as a fork because the parent library does not export the required functions.

There are many interesting use case for VRFs (Verifiable Random Functions [original paper]), but for our @BlockchainCommons roadmap, we would like to see use it in a similar way that CONIKS [pdf], Key Transparency [design doc] [slides] & Kademilia [paper] use them for private commitments. We can't use Schnorr signatures as they are do not guarantee uniqueness of the signature because of the random nonce requirements (sidenote: @sipa does Musig-DN qualify as a VRF?).

Other uses for VRFs are: random oracles, non-interactive lottery systems, updatable zero-knowledge databases, Resettable zero-knowledge proofs, L2 e-cash, rotatable Decentralized Identifiers (DIDs), and more.

Our challenge is that we also want to support MUSIG2 now and FROST when it gets finished here, but likely before they will likely be merged into the upstream master. We don't want to have to support 2 forks of the secp256k1 upstream master, so would really like to see VRFs in THIS fork. We don't want to support draft-irtf-cfrg-vrf-11 because it is 25519, not curve secp256k1.

/cc @jesseposner @wolfmcnally @kanzure @maaku

Some other related links:

• What is the difference between signatures and VRF? | Stack-Exchange Cryptography
• CONIKS vs Key Transparency vs Certificate Transparency vs Blockchains | okTurtles Blog

[real-or-random]

(sidenote: @sipa does Musig-DN qualify as a VRF?).

The part that generates nonces is a VRF, but it's stronger than normal VRFs: It's a "VRF-in-the-scalar": The resulting group element / nonce is random and the one evaluating the VRF knows its Dlog (and is the only one who knows it). This makes it very complex and inefficient, and the VRF from https://eprint.iacr.org/2017/099 (the one in the IETF draft and https://github.com/aergoio/secp256k1-vrf) is a much better choice.

We don't want to have to support 2 forks of the secp256k1 upstream master, so would really like to see VRFs in THIS fork.

Yeah, this is a problem. :/ It would be really nice to a "more modular" module system that makes it easier to combine multiple extensions of secp256k1.

[apoelstra]

I am not opposed in principle to pulling in a VRF. In theory, we could even do so without more than a cursory review from the library maintainers (e.g. to check that the code was laid out properly and didn't affect things outside of its module). But that's a larger discussion about how this project ought to be run.

Upstream in libsecp there's been a lot of discussion about how to have a more modular module system, but I don't know that we've come up with a solution that we can start working toward.

[real-or-random]

But that's a larger discussion about how this project ought to be run.

Yeah, I feel we should have this discussion. One standpoint is that this is a library for Elements ecosystem, and that we should commit only to modules that are relevant within that ecosystem. This may mean that we want a VRF module or that we don't want it, but I'm not even sure if we have a clear policy on the purpose of the library.

[ChristopherA]

I know that from my perspective that this repo has become a default staging ground for doing the first implementation of important crypto that might eventually go into Bitcoin Core, but also for items needed by Core Lighting, Liquid, or Green Address. That was I thought the original intent of Elements was it could be used for lots of things, not only Liquid.

I also feel some contributors here participate here not necessarily to support Liquid, but instead because it has this history of being a staging ground.

Of course this is a Blockstream-run repository, but if you decide you don't want to use it as a staging/proving ground for various important cryptographic elements, let the community know. But staging/proving ground is its current reputation.

[ChristopherA]

Related to the "big picture" question is the request for basic adapter signature support in #191 from @wolfmcnally.

[real-or-random]

I know that from my perspective that this repo has become a default staging ground for doing the first implementation of important crypto that might eventually go into Bitcoin Core, but also for items needed by Core Lighting, Liquid, or Green Address. That was I thought the original intent of Elements was it could be used for lots of things, not only Liquid.

I agree with this observation but I'm not sure if I'm satisfied with it. I think we'd need to see how the very related upstream discussion evolves: bitcoin-core/secp256k1#997 (comment) If the way forward is to have Bitcoin-related features in upstream directly (even as PR or experimental) module, then we wouldn't need this library here as a staging ground, and it could move its focus towards Elements again.

[wolfmcnally]

I'm not normally one to suggest forks, but there does seem to be some utility in having a "skunkworks" version of libsecp256k1 that isn't bound to only serving a specific project (including Bitcoin Core) but more the community at large.