Verifiable random commitments or public keys

#1

We make extensive use of verifiable random functions (VRFs) in PoS designs, so that nodes can produce randomness along with a proof that they did not bias the randomness. RANDAO’s hash chains are VRFs with domain a bounded series of singletons, as reveals happen in order.

Publicly verifiable secret sharing (PVSS) is a multiparty VRF with a singleton domain. Alone verifiable secret sharing (VSS) might not be considered a VRF because its only verifiable to the participants, but dfinity uses VSS to make a VRF key, and afaik restores public venerability afterwards somehow to get a threshold VRF.

We do not normally describe these constructions as VRFs because they have strange domains. Instead, we normally use VRF to describe any signature scheme in which part of the signature can reasonably be considered a PRF, with say at least 128 bits of entropy, but is completely determined by the message and public key.

BLS signatures and RSA-FDH are VRFs, while Schnorr signatures like Ed25519 and RSA-PSS are not VRFs because they use randomness supplied by the signer. There are also faster VRFs like NSEC5 and V(X)Ed25519 based on the DLOG and ROM assumptions, which do require randomness supplied by the signer, but to produce a Schnorr proof of correctly computing another deterministic value of the message and public key.

Question: Is there a VRF based around Rabin signatures? Almost surely no since Rabin signatures use considerable randomization, but if so, it might be the fastest VRF available, without aggregation or batching.

In all the signature-like VRFs, the deterministic value of the message m and public key takes the form s*H(m) in additive notation (or H(m)^s in multiplicative notation) where s is the secret key and H is a hash function mapping into some appropriate group.

We could make a two-signer VRF using an ECDH along with the DLEQ proofs from CloudFlare’s OPRF construction in PrivacyPass, so again assuming on DLOG and ROM. Again the deterministic value looks like x*y*H(m).

Question: At present, all protocols employing VRF must be designed to remain secure after this s*H(m) part gets revealed. What if the VRF output should be kept secret? Can a VRF output only a commitment instead of the actual value?

Imagine we have some mapping f that maps group elements like s * H(m) back into secret keys aka scalars. If our VRF outputs the public key or “Pederson hash” commitment f(s * H(m)) G then we can sign things with this output, and our VRF can give us another VRF key in particular.

There are cool forward-security applications for such a construction: Right now, validators have VRF keys that rotate eventually, but must not rotate too fast or else they admit bias or even collapses the system to proof-of-work. If VRFs can yield VRFs, then we can have forward-secure VRFs in which validators can erase their VRF keys much more quickly, and reduce their exposure to slashing when nodes get hacked, etc.

We mentioned threshold collaborative randomness scheme based on VSS and PVSS above, but a recent ethresear.ch thread proposes another “synchronous” collaborative randomness scheme. We could generalize this to DAGs with higher input and output degree, which yields an array of “synchronous” randomness schemes, likely even covering threshold schemes.

As written, it requires a two-signer VRF whose output is a public key for the VRF. I have proposed two schemes for doing this inspired by curve cycles and suggested a direction for one more conventional scheme:

First, if we accept using zkSNARKs, then we could prove both the ECDH and the subsequent commitment on the curve JubJub, with the verification zkSNARKs running BLS12-381. ZCash has verification of scalar multiplications of a constant on JubJub down to 4.2 constraints per bit of the scalar, but the ECDH with a variable point presumably takes more, so this sounds okay but not actually “fast”, and verification costs some pairings.

Second, we could go faster by fixing the height and building some tower of curves, so that each layer boils down to the PrivacyPass DLEQ proof of an ECDH, but verified by bulletproof or similar on the “parent” curve. If I understand then both c and s could be a public input here, so this likely gives an extremely fast solution, and maybe batches well. We could likely speed this up by doing one PrivacyPass DLEQ proof for our key plus a blinding factor B together with the other party’s key, and then doing a verification of the curve addition on the parent curve, as described below. ZCash has conditionally adding a constant down below 5 quadratic constraints, so we might rebuild the proof around a table for B. In this, we’d do elliptic curve arithmetic on many different curves though, likely using Weierstrass arithmetic from the AMCL library, so ugly but still far faster than zkSNARKs, especially for verification.

Third, we can likely make this go fast-ish without any exotic curve constructions using an additive blinding: We let f denote some collision resistant mapping of curve points into scalars. We have commitments A_i = a_i G for i=1,2 so if our 1st participant is honest, they can reveal and f(a_1 a_2 G) along with

  • some B = b A_2 with b random,
  • a NIZK that (a_1 + b) A_2 is the ECDH of A_1 + B and A_2, and
  • a NIZK that the revealed value (b+a_1) A_2 represented as f((b + a_1) A_2) G is the curve addition of two hidden values a_1 A_2 with a commitment f(a_1 A_2) G, and b A_2 encoded as f(b A_2) G for which b A_2 is also the ECDH of B and A_2.

Importantly, we’re only representing f and the curve addition in the NIZK here, which while nasty, sound much more efficient than attempting to represent a scalar multiplication. Again we’d verify addition by treating B as constant and making a table. We should likely replace f with some encoding of the curve point as multiple scalars, maybe like 14 or more since our addition formula has degree six, or maybe some CRT trick improves that. I think doing this encoding badly technically exposes bits from a_1 A_2, so maybe another layer of blinding is required.

Question: How do we optimize this second NIZK? Or find another better scheme? Can we anywhere near the speed of the tower of curves construction?

There is a fourth construction based on zkSTARKs that might work as part of a zkSTARK based chain, but the huge size sounds problematic for stand alone use cases like those discussed here.

1 Like

#2

Just a crazy though: We could maybe represent the VRF itself on multiple curves over the same base field, but use the same secret key, so pk = (sk * G_1, sk * G_2, ...). We can now do the base field arithmetic natively in each curve and appeal to the Chinese remainder theorem to know that only one integer mod l_1 l_2 ... satisfies those equations. We’d explicitly place the base field order into the computation, but do a single range proof that any given term had a very small quotient mod the base field’s order. We’d also do a separate proof that the output commitment was correct on each curve.

0 Likes

#3

Anca Nitulescu suggested using a curve with base field not of prime order, or possibly even binary. I’d kinda considered binary but not really, and I know little about say base fields of non-binary composite order, like say two big primes. Anyways the issues are to evaluate the security trade offs in using such base fields, and to think about the requires range proofs, so not sure if this beats my CRT idea in performance, but it looks simpler and cleaner, as initial conditions for my idea are hard to verify.

As for the collaborative prng idea posted to ethresear.ch, Michele Orru suggested replacing the ECDH with some secret sharing scheme because multiplying polynomial evaluations and then reconstructing is equivalent to reconstructing and then multiplying the polynomials, so say a (1,2)-threshold scheme becomes a (2,4)-threshold scheme, etc. We should think about VSS and PVSS to actually do this though because we want both a publicly verifiable curve point output at each layer as well as its scalar as a private output. In the end though, we’d obtain a secret sharing scheme with tiered reveals structured such that any subtree contains a revealer at each level, which sounds believable.

0 Likes

#4

I found yet another application for VRFs yielding keys when implementing the 3-round multi-signature scheme from “Simple Schnorr Multi-Signatures with Applications to Bitcoin” from by Gregory Maxwell, Andrew Poelstra, Yannick Seurin and Pieter Wuille for our schnorr-dalek crate.

In fact, these authors initially proposed a 2-round multi-signature scheme, but the security arguments were found lacking in “On the Provable Security of Two-Round Multi-Signatures” by Manu Drijvers, Kasra Edalatnejad, Bryan Ford, and Gregory Neven. We need the extra round trip for an initial commit phase for the signature’s R value, which helps prevent rogue signature attacks.

We could build another 2-round multi-signature scheme by producing this R value with a VRF. R = r B is a curve point for which the signer must know the discrete log r, so precisely the problem discussed in this post. :slight_smile:

0 Likes

#5

Andrew Polestra and I just had an interesting conversation about this at Real World Crypto. It turns out they’re already working on a security proof for my last comment. woot! :slight_smile:

In fact, they already have another curve on top of secp256k1, which actually just swaps the curve orders, although note that bullet proofs verifying bullet proofs sucks. We should aim for another Edwards curve built on top of Ed25519 soon-ish and implementing the ZK VRF described above.

Christopher Allen is interested too. And I started an issue for us.

1 Like

#6

In polkadot and schnorkel, we should support mBCJ signatures from pages 21 and 21 of https://eprint.iacr.org/2018/417.pdf because they are currently the only two-round multi-signature without pairings. It complicates verification to support more signature schemes, but hey.

0 Likes

#7

I just learned about On cycles of pairing-friendly elliptic curves by Alessandro Chiesa, Lynn Chua, and Matthew Weidner. It produces many constraints on cycles of elliptic curves use for chain history verification via Proof Carrying Data.

In particular, section 7 argues you need curves without cofactors using the Hess bound. A higher genus curve has a much worse Hesse bound, so I’m curious if hyper elliptic curves might provide better curve cycles.

Also, I still think one should look for curve cycles in which some but not all support pairings, but all the curves offer reasonable security. If so, you could use SNARKs when pairings exist, but use another zero-knowledge proof technique for the curve that lack pairings. We’d exploit the less efficient zero-knowledge proofs only as a mechanism to produce a proof of verifying a SNARK that can itself be checked in a SNARK, never actually send them over the wire.

0 Likes