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.