1
$\begingroup$

I'm working on a small blockchain project and I came across the idea of using zero knowledge proofs to enforce anonymity. I think I generally understand the idea, but I'm unable to find an explanation of a reliable way to implement this system with a protocol like HTTP.

For example, given the classic sudoku example, where you have found the solution to the puzzle and want to prove to someone that you know the solution, without showing the solution, you can just create a mapping where you shuffle the numbers. Whenever the person asks for a row, you show them the row they asked for, with the valid numbers.

My question is: If you are implementing this in HTTP and one server is trying to prove to the other that it knows the answer, when the verifier asks for a row via HTTP, cant the prover just provide a fake row of the numbers 1-9? The prover would only need to generate a random combination of the numbers, making sure theyre all only used once, and the prover would deem this as valid.

I must be missing something here, but I fail to see how this could possibly be implemented between two servers. Any help would be tremendously appreciated

Improve this question
$\endgroup$
2
  • $\begingroup$ The focus on HTTP is a bit odd. Any solution that exists with HTTP could be implemented on FTP, SMS, etc., and vice versa. $\endgroup$
    – Acccumulation
    Jan 30, 2018 at 22:11
  • $\begingroup$ Right, I'm just trying to understand it in terms of a communication protocol, and http happens to be the simplest to use within a question/explanation $\endgroup$
    – Alex Dovzhanyn
    Jan 31, 2018 at 2:48

2 Answers 2

Reset to default
4
$\begingroup$

Yes, you are missing something. :)

The trick is that the prover commits to the number in each square individually.

The verifier doesn't always get a row, column or block. The verifier choses to see one of those or the permutation of the original puzzle.

If the verifier choses the permutation he can check if the revealed number are indeed a permutation of the original puzzle, if he choses a row or column he checks if all the numbers from one to nine are in it.

Since the prover does not know what is requested he has to commit to a valid filled Sudoku field to make sure that the numbers in each row, column and block are the numbers from one to nine. Since the permutation could be selected it must also be a solution to the initial problem.

Note that you have to repeat this process many times to get security because the prover could guess what the verifier will ask for. In every iteration a new puzzle must be chosen and the verifier must select which part to query independently at random.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So the prover sends the verifier the entire puzzle, just with the numbers shuffled, essentially? And then the verifier can check any parts of the puzzle as being valid? I'm still unsure as to how this commitment would work, in terms of going multiple rounds. Because if we assume that each round consists of an HTTP request, doesnt that mean that the verifier sends a request to the prover, with the request for the data they want to check, and when this happens, the prover knows what data is going to be checked, so they can make sure that the subset of data they send back is valid? $\endgroup$
    – Alex Dovzhanyn
    Jan 30, 2018 at 14:01
  • $\begingroup$ @AlexDovzhanyn I've expanded the answer regarding your last point. Also note that the prover does not send a shuffled version of the numbers but only commits to it! The verifier can then ask for one of the four options and will get the permuted version. The verifier must then check that the solution is good and that it fits the commitment that he received earlier. $\endgroup$
    – Elias
    Jan 30, 2018 at 21:07
0
$\begingroup$

The key with this problem is that, in real life, the verifier can see that when they pick a selection (square, column or row) they can see that the prover takes the correct number locations (still hidden at this point) then shuffles and shows those locations. Back in the crypto world we have to do this via a commitment scheme to enforce locations of each number. This involves the prover creating a commitment on every number which hides the values but binds them so they can only represent one number each. This is shown to the verifier and they can then choose their selection. To shuffle, the prover can use a 'mixer' (from electronic voting) to permute the order in such a way that he can prove they are the same. Then he releases the nonce values to the commitments such that they can be opened and checked by the verifier.

Improve this answer
$\endgroup$
3
  • $\begingroup$ How are we able to have the prover 'commit'? Could you point me in the direction of an article or blig post where I can learn more about that? $\endgroup$
    – Alex Dovzhanyn
    Jan 30, 2018 at 13:56
  • $\begingroup$ Of course, they are called commitment schemes. $\endgroup$
    – Jackoson
    Jan 30, 2018 at 19:54
  • $\begingroup$ The Wikipedia article is quite good but also Google links to a good set of notes from NYU. $\endgroup$
    – Jackoson
    Jan 30, 2018 at 19:56

Your Answer

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

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