How Do You Prove You Know The Answer, Without Revealing The Answer?

How Do You Prove You Know The Answer, Without Revealing The Answer?

zkSnark gives us proof

As a teacher you mark your student’s work, but where they give away the answer each time. So can we find a method to prove that a student has finished their coursework, without them telling you the answer. So let’s say we have Peggy the student and Victor the teacher. Victor sets Peggy a problem:

“Prove to me that you know the value of x for x²+5x-150=0, but don’t tell me the answer!”

Peggy scratches her head. She knows that x²+5x-150=0 is (x-15)(x+10)=0, and can solve this for x=15 or x=-10. But she cannot tell Victor the answer. Well, she needs to create a proof of correctness.

Here is the proof for x=10, x²+5x-150=0:

How do we do it? Well, crypto pairing for zero-knowledge proofs supports this.

Zero-knowledge Proofs

We give away too much of our data. Why should we give away our password every single time that we log into a system. Why can’t we just prove that we still know it? Thus Victor (the verify) can prompt Peggy (the prover) with a puzzle, and where she can show that she can solve it. This is the method that zero knowledge proof (ZKP) uses to prove things. In this case we will use the method used by zk-SNARKs to prove that we still know a secret. This method is used in blockchain methods to anonymise transactions. In this we use the pairing property (e()) of:

e(aU,bV) = e(U,abV) = e(U,V)^{ab} = e(bU,aV)

First we have two elliptic curves (G1 and G2). Crypto pairs can then be used to prove that Peggy still knows a secret. For this we may have a quadratic equation of:

x²+5x−150=0

Then, we will ask Peggy to prove that she knows the value of x. In this case, the solution is x=15 or x=−10. Now Peggy has to pass something to Victor to prove that she knows the solution, without giving away the value.

For this we have a point on an elliptic curve of G, and use the pairing property of (and where e() is the pairing function):

e(G,G)^k=1

and thus:

e(G,G)^{x²+5x−150}=1

In pairing this then becomes:

e(G,G)^{x2^} (G,G)^{5x} e(G,G)^{−150}=1

and which becomes:

e(xG,xG) e(xG,5G) e(G,−150G)=1

Peggy will then provide xG and Victor will check the pairings multiplied equals unity. If real life x will be a large value, and it will not be possible to determine x from xG.

The outline coding using the library from the gsnark library [here] is:

A sample run is [here]:

-12 =x^3 + (-3) x + (-10) when x= 1

Proof: &{{[2675658996782286732 8914725834961326762 13447480635561102629 17946381993026357171 13999854648367502125 45984963968108606] [12436099469856088005 9476267384122043601 1473904065594197110 1856969899058675802 8558075317656655462 120264009124913042]} {[13009199714519461133 11144420394545007472 9518163973024256862 17990757860837992915 9557229965428639720 14442379772686021] [6958436928058547774 7115083387299807185 17495458330385439451 10656561640959987832 1331293918824267611 54193300516895449]} {{[516848653940528355 9960425841574927652 5302473275361053517 457295650691531379 9736863588490620470 60884129589037391] [8737861606191359736 9146941305537024805 7734269607322910088 1455444471768871536 11061844635811516102 26691571454434682]} {[6598268733689889709 14849969620105935699 135189537366654044 4091349966081677994 7668200215144098765 48853293321301083] [12438266814412970556 13981091221663188431 15767719380617845524 3596523800781485162 1624406842663105729 45539061396846750]}}}
Verified: true

If we try an incorrect value, such as x=5, we get a not proven result:

-13 =x^3 + (-3) x + (-10) when x= 1

No proof!

Conclusions

We have many things in life where we have to prove things, but we perhaps give away too much of our data, so crypto pairing comes to our rescue.