1
$\begingroup$

I understand that we can verify that given a private input a and a public input b that we can verify a is greater than b. But what if I want to keep both inputs private?

The context is a sealed auction where we need to verify who out of the private bidders has the highest bid. I haven't seen any examples of how this can be achieved but hopefully somebody on here can help point me in the right direction.

$\endgroup$
1
  • $\begingroup$ How about using some solution to Yao's millionaire problem. You can use SNARK's to prove the integrity of the inputs if required $\endgroup$ Jun 12 at 13:16
3
$\begingroup$

With zk-snarks, one would verify a proof that "is greater" relation holds for $(a, b)$ plaintext as a private input, and for commitment to $(a, b)$ as a public input. One would split both $a$ and $b$ into bits ("wires" in snarks parlance), and create a circuit with multiplication gates producing "true" or "false". Verilog circuits might be somewhat helpful here. Multiplication means R1CS system of equations representing the circuit, as the problem-specific part, and an input for a snark library implementing Groth16 proof system.

Having the circuit, one would produce two public keys, produce and verify a snark proof.

$\endgroup$
2
  • $\begingroup$ To generate this proof wouldn't you need to know the value of a and b? I'm wondering if there is a way to prove a is greater than b without knowing b? $\endgroup$
    – GeraldHost
    Jun 13 at 19:06
  • $\begingroup$ If you start with snarks as a requirement, you would supply proper witness to output a snark-proof. That means both 𝑎 and 𝑏 in plaintext. $\endgroup$ Jun 30 at 12:55
3
$\begingroup$

Assume there is a common secret $x$ that is used to conceal the value of $a$ and $b$, known only by the actors possessing $a$ and $b$. A verifier $c$ is a randomly picked number, and provided to the two parties possessing $a$ and $b$. Then, they calculate $ax-c$ and $bx-c$, and provide them to the verifier. The verifier then calculate the difference between $ax-c$ and $bx-c$, which is the result. In such case, because $ax-c$ and $bx-c$ is not definitely divisible by $x$, there are no ways of the verifier figuring $x$ out.

Note that there are problems with this protocol, as it requires interaction between the verifier and the two parties bearing $a$ and $b$.


EDIT: The actual possibility of the provers A and B counterfeiting their values

There are two cases of the identity of the verifier, which should be discussed separately. The first possibility, is that the verifier is the auctioneer. In this case, A and B would always attempt to counterfeit their value, since the auctioneer has no way of knowing the value of $x$. They would both do the same thing, not using their mutually known $x$, but something else. In such a case, their actions cancel each other out. However, if the verifier is a spectator, there are no reasons for them to counterfeit a value, and even if they do so, the spectator would always know. Therefore, the problem of counterfeiting a value is actually not existent.

$\endgroup$
2
  • $\begingroup$ Thanks dude that makes sense! Is there a way to do this without a common secret? because surely if both parties know the secret and the value of c they will be able to figure out a and b? Maybe I have miss-understood something. $\endgroup$
    – GeraldHost
    Jun 13 at 18:59
  • $\begingroup$ @GeraldHost I have added the information that you requested and clarified what I mean. Thanks for your feedback. $\endgroup$
    – Red Sun
    Jun 14 at 10:14
1
$\begingroup$

Is using ZK snark a requirement? This seems to be the millionaire problem: https://en.m.wikipedia.org/wiki/Yao%27s_Millionaires%27_problem

This is simpler than doing SNARKS, it's an interactive shared computation, doesn't have any trusted center or assume both inputs are protected by a shared secret (as in Red Sun's answer).

In a bidding scenario, they give commitments and run the millionaire protocol. There is no gain to any party by using a different value in the millionaire protocol than what is committed, if you win you will need to reveal commitment and pay and any treachery will be discovered. But also for the losing side, there seems to be limited value in not using the same value in commitment.

If you have a trusted person to do see the bids but you don't trust him to be fair, you can use ZK proofs for him to prove he was honest, but these don't address the issue of trusting the party not to reveal the bids. You need some sort of shared computation as in millionaires to ensure bid secrecy from all other parties.

$\endgroup$
3
  • $\begingroup$ I mentioned the same thing in the comment above. But zero knowledge proofs (like SNARK) can be used to prove that your private input to it is the same as the originally committed bid value for instance, in this case. $\endgroup$ Jun 13 at 11:33
  • $\begingroup$ But if you commit to a value, and then run millionare algorithm using a different one and win, you will still need to reveal your original value. and pay the exact amount you committed to. It seems you still need some shared computation. So I'm not sure what the ZK proof is needed for. $\endgroup$
    – Meir Maor
    Jun 13 at 12:14
  • $\begingroup$ Yes, but you don't need to reveal your bid if you lose $\endgroup$ Jun 13 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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