Score:2

Commit the output of verifiable random functions

jp flag

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.

Chris Peikert avatar
in flag
What constraints are there on $com_y$? We could always define $com_y=0$, which is trivial to prove “correct.”
Chenghong avatar
jp flag
@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) https://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?
Chris Peikert avatar
in flag
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$.
Score:1
es flag

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.

Chenghong avatar
jp flag
I appreciate your excellent answer, that really helps. I'll try to make some analysis myself based on your solution as well.
knaccc avatar
es flag
@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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.