3
$\begingroup$

The problem setting is as follows. Suppose there exists a public input $x$ and the prover evaluates $y \gets VRF_{sk}(x)$, but the prover does not wish to reveal the output $y$. My question is would it be possible to let the prover publishes the commitment of $y$, say $com_y$, then proves that the committed value of $com_y$ is correctly generated by evaluating the VRF using the secret key $sk$ and the public input $x$?

I appreciate your help.

Improve this question
$\endgroup$
3
  • $\begingroup$ What constraints are there on $com_y$? We could always define $com_y=0$, which is trivial to prove “correct.” $\endgroup$
    – Chris Peikert
    Commented Jan 14, 2022 at 0:32
  • $\begingroup$ @ChrisPeikert, thanks for the comment, that's really a good point. I hadn't thought much of the constraints for $com_y$ though. Actually, I was reading the paper (LegoSNARK) eprint.iacr.org/2019/142, which is about commit-and-prove zksnark. They can prove statements about values that are committed. So I was wondering if we could do the same thing for VRFs? $\endgroup$
    – Chenghong
    Commented Jan 14, 2022 at 14:53
  • $\begingroup$ Those are proofs about the values “inside” the commitment $com_y$, not about $com_y$ itself. In the VRF setting, notice that the VRF public key itself is a commitment to the function output $y$ (and even all outputs at once!), because one can prove that $y$ is correct in the usual way. But this inherently requires revealing $y$. $\endgroup$
    – Chris Peikert
    Commented Jan 14, 2022 at 16:11

1 Answer 1

Reset to default
1
$\begingroup$

To make a simplification, the ECVRF described in draft-irtf-cfrg-vrf-02 will use a key-pair $(x, Y=xG)$ and take an input $\alpha$. It will return $P = xH$, where $H = H_p(Y \mathbin\|\alpha)$, along with a Schnorr-based discrete-log-equivalence (DLeq) proof demonstrating that $P$ shares the same private key $x$ with $Y$ on generator points $H$ and $G$ respectively. This therefore proves that $P$ was correctly calculated as $xH$. $H_p()$ means to create a hash resulting in an EC point, which is what the linked document refers to as $\texttt{ECVRF_hash_to_curve}$. $G$ refers to a well-known base point for the curve.

A modified $\texttt{ECVRF_prove}$ function can be created for the purposes of generating a commitment. It will pick a uniform random blinding factor $b$, and will return $B = bG$ and $P' = x(H+B)$ instead of $P = xH$. It will return a DLeq proof that will demonstrate that $P'$ shares the same private key $x$ with $Y$ on generator points $(H+B)$ and $G$ respectively, and thus prove that $P'$ has been calculated as expected.

A modified $\texttt{ECVRF_verify}$ function can be created to verify the commitment. It will take $B$ as an additional argument, so that it can verify that the DLeq proof operates with the generator $(H+B)$ instead of $H$.

After this modified verification, the verifier knows for sure that $P' = x(H+B) = xH + xB$. Since $x$ is private, the verifier cannot calculate $xB$ in order to determine the committed value $xH$. This also means it's impossible for a verifier to try to discover whether this is a commitment to any specific $xH$ value.

The prover can open the commitment by revealing $xB$ and providing a DLeq proof that $xB$ and $Y$ share the same private key $x$ on the generator points $B$ and $G$ respectively. Since the verifier knows for sure that $P'==x(H+B)$, and also knows for sure that $xB$ is calculated correctly (due to the DLeq proof), the verifier knows for sure that the correct value of $xH$ can be calculated as $P'-xB$.

The $xH$ value which was committed to will be identical to the $xH$ value that would have been produced by the original unmodified $\texttt{ECVRF_prove}$ function.

Note that after the commitment is opened, a verifier can only use the modified $\texttt{ECVRF_verify}$ function to check the correct value of $xH$ has been provided. If for any reason a verifier needs a separate proof that can be used with the original unmodified $\texttt{ECVRF_verify}$ function, this additional proof can be provided by the prover at the same time that the commitment is opened.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I appreciate your excellent answer, that really helps. I'll try to make some analysis myself based on your solution as well. $\endgroup$
    – Chenghong
    Commented Jan 13, 2022 at 18:30
  • $\begingroup$ @Chenghong no problem. I'd be very interested if you could provide some context as to how these commitments might be more useful than just a simple hash commitment for which a proof of correctness is instead provided later when it is opened by the prover. $\endgroup$
    – knaccc
    Commented Jan 13, 2022 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.