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

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

As a teacher you mark you 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 MIRACL library [here] is

package main

import (

	"fmt"
	"github.com/miracl/core/go/core"
	"github.com/miracl/core/go/core/BN254"
	"math/rand"
	"time"
	"os"
	"strconv"
)

func Abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
func FP12toByte(F *BN254.FP12) []byte {

	const MFS int = int(BN254.MODBYTES)
	var t [12 * MFS]byte

	F.ToBytes(t[:])
	return(t[:])
}

func randval() *core.RAND {

    s1 := rand.NewSource(time.Now().UnixNano())
    r1 := rand.New(s1)

    rng := core.NewRAND()
    var raw [100]byte
    for i := 0; i < 100; i++ {
       raw[i] = byte(r1.Intn(255))
    }
    rng.Seed(100, raw[:])
    return rng
}

func main() {

	x:=7
	a:=-1
	b:=-42

	argCount := len(os.Args[1:])

        if (argCount>0) {x,_= strconv.Atoi(os.Args[1])}
        if (argCount>1) {a,_= strconv.Atoi(os.Args[2])}
        if (argCount>2) {b,_= strconv.Atoi(os.Args[3])}

	G1:= BN254.ECP_generator() 
	G2:= BN254.ECP2_generator() 
	
	xG1:=G1
	xG2:=G2
 
	xGa:=G2 
	xGb:=G2 

	// Equ: x^2 + ax + b = 0

	if (x < 0) { 
		xG1 = BN254.G1mul(G1,BN254.NewBIGint(Abs(x))); xG1.Neg()
		xG2 = BN254.G2mul(G2,BN254.NewBIGint(Abs(x))); xG2.Neg()
	} else {
		xG1 = BN254.G1mul(G1,BN254.NewBIGint(x))
		xG2 = BN254.G2mul(G2,BN254.NewBIGint(x));
	}	



	if (a < 0) { 
		xGa = BN254.G2mul(G2,BN254.NewBIGint(Abs(a))); xGa.Neg()
	} else {
		xGa = BN254.G2mul(G2,BN254.NewBIGint(a)) 
	}

	if (b<0) { 
		xGb = BN254.G2mul(G2,BN254.NewBIGint(Abs(b))); xGb.Neg()
	} else {
		xGb = BN254.G2mul(G2,BN254.NewBIGint(b)) 
	}


	if (b < 0 && a < 0) { 
		fmt.Printf("\nEqn: x^2 - %d x - %d\n",Abs(a),Abs(b)) 
	} else if (b < 0) { 
		fmt.Printf("\nEqn: x^2 + %d x + %d\n",a,Abs(b)) 
	} else if (a < 0) { 
		fmt.Printf("\nEqn: x^2 + %d x + %d\n",Abs(a),b) 
	} else {
		fmt.Printf("\nEqn: x^2 + %d x + %d\n",a,b) 
	}

	fmt.Printf("\nxG1: %s\n",xG1.ToString()) 
	fmt.Printf("\nxG2: %s\n",xG2.ToString()) 
	fmt.Printf("\nxGa: %s\n",xGa.ToString()) 
	fmt.Printf("\nxGb: %s\n",xGb.ToString()) 


	pair1:=BN254.Ate(xG2,xG1);  pair1=BN254.Fexp(pair1)
	pair2:=BN254.Ate(xGa,xG1);  pair2=BN254.Fexp(pair2)
	pair3:=BN254.Ate(xGb,G1);  pair3=BN254.Fexp(pair3)

	fmt.Printf("\nPair 1 - first 20 bytes:\t0x%x\n",FP12toByte(pair1)[:20])
	fmt.Printf("\nPair 2 - first 20 bytes:\t0x%x\n",FP12toByte(pair2)[:20])
	fmt.Printf("\nPair 3 - first 20 bytes:\t0x%x\n",FP12toByte(pair3)[:20])

	pair1.Mul(pair2)
	pair1.Mul(pair3)

	


	fmt.Printf("\nPair Result - first 20 bytes:\t0x%x\n",FP12toByte(pair1)[:20])
	if (pair1.Isunity()){  fmt.Printf("\n\nYou have proven you know the value of x") } else {
		fmt.Printf("\n\nYou have NOT proven you know the value of x") 
	}


}

A sample run is [here]:

x =  10
Eqn: x^2 + 5 x - 150

xG1: (1d81c5f7b8a95b5ffd3f9fcd5dff149db117f7de1f506778bc80445a4ed65dd5,1ff80bdb89865d0a991d4e5173a4b9fd64c54ecf497a475a664953068a2bbebb)

xG2: ([1f12610564860a549be92c5eb1d4a41e92ecbaddfcefc0b4b0ed1b55bd25f5cb,0d12b5189df313f7734387b656d4ad97d24a8f1379725614b91d47125633b7f7],[12455101611cf3bb8b994e204715e8c03cec19354be2c92d9442259b31b95df5,02519e8928ae32c2a754e3bb771aeab713b1d1267fde8e541f68bd76c4a71dac])

xGa: ([0b1d84f4d56634326a9c59f8161dd78be24b56b48a728012afea461f9191d674,21c158326bd5f7b921e22d5a528740d1fa40d4ad5924ab1d11c56a9f0a80b0c4],[0070bea4ee500dced8932db3b13554cdb986169e1a1180575562c32a6697afc4,20164c93784ca3c6b1db4fde1f24b8063a7a26b61ab465944ddffa3ce9cba6e5])

xGb: ([171b921d4647c875f6c9c83458398dadb33698ff1685e725e33896874e09ea64,0fe8a1be33511d71daf62eb12a482e100f154ac7fc91ba6dc570cee816f9c98d],[14fc915ed98153ce5161eb28b7a541c45a6b45a20e843f689eb4d8ad68bc1dc7,20a8af20af7926cd2142838a51ce6a5bc6562070465c36cd09a8bfee807d6300])

Pair 1 - first 20 bytes: 0x1c2ffec03e2b54b6b13cbe254df0ed5be55b4e37
Pair 2 - first 20 bytes: 0x217d808aa71d03b1361c6baefae8186b6198fb6c
Pair 3 - first 20 bytes: 0x1453b8795a6681967c1e865c33e42f18b3620447

Pair Result - first 20 bytes: 0x0000000000000000000000000000000000000000

You have proven you know the value of x

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

x =  5
Eqn: x^2 + 5 x - 150

xG1: (23edc69a751b579a14bc178029c6a6776a17fab345de03331bd905985b94daf0,215f727b315191c38806742b359c1aa7ebc35f65f5632eb8e9e6602f8890706b)

xG2: ([0b1d84f4d56634326a9c59f8161dd78be24b56b48a728012afea461f9191d674,21c158326bd5f7b921e22d5a528740d1fa40d4ad5924ab1d11c56a9f0a80b0c4],[0070bea4ee500dced8932db3b13554cdb986169e1a1180575562c32a6697afc4,20164c93784ca3c6b1db4fde1f24b8063a7a26b61ab465944ddffa3ce9cba6e5])

xGa: ([0b1d84f4d56634326a9c59f8161dd78be24b56b48a728012afea461f9191d674,21c158326bd5f7b921e22d5a528740d1fa40d4ad5924ab1d11c56a9f0a80b0c4],[0070bea4ee500dced8932db3b13554cdb986169e1a1180575562c32a6697afc4,20164c93784ca3c6b1db4fde1f24b8063a7a26b61ab465944ddffa3ce9cba6e5])

xGb: ([171b921d4647c875f6c9c83458398dadb33698ff1685e725e33896874e09ea64,0fe8a1be33511d71daf62eb12a482e100f154ac7fc91ba6dc570cee816f9c98d],[14fc915ed98153ce5161eb28b7a541c45a6b45a20e843f689eb4d8ad68bc1dc7,20a8af20af7926cd2142838a51ce6a5bc6562070465c36cd09a8bfee807d6300])

Pair 1 - first 20 bytes: 0x0992fbe1be5fa730dd57a1cb271d0b509d3bca98
Pair 2 - first 20 bytes: 0x0992fbe1be5fa730dd57a1cb271d0b509d3bca98
Pair 3 - first 20 bytes: 0x1453b8795a6681967c1e865c33e42f18b3620447

Pair Result - first 20 bytes: 0x1c2ffec03e2b54b6b13cbe254df0ed5be55b4e37

You have NOT proven you know the value of x

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.