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.
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.
a and b? I'm wondering if there is a way to prove a is greater than b without knowing b?
$\endgroup$
Commented
Jun 13, 2021 at 19:06
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.
c they will be able to figure out a and b? Maybe I have miss-understood something.
$\endgroup$
Commented
Jun 13, 2021 at 18:59
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.
