With zero knowledge proofs, we can take a secret, and then create a proof for it, without revealing the secret. In this case we create a Schnorr proof which is (c,s), and also a "Statement". This statement relates to the knowledge of the point discrete log of the proof point. In this case we have a secret of \(x\) and then create a hash of this to get \(X\). Next we convert this to an elliptic curve point of \(Y=X.G\). This is then the statement that Bob and register with Alice. When registered, Bob produces a proof of the knowledge of \(x\) by generating a proof with \(C\) and \(S\).
Schnorr Proof for ZKP (with Kryptology and Golang) |
Proving
If we have a secret \(x\), Bob first takes a hash of this:
\(X=Hash(x)\)
Bob then computes a statement (\(Y\)) of:
\(Y = X.G\)
and where \(G\) is the base point on the curve. This statement value can be registered with Alice, and Bob can now prove it with (\(C,S\)).
To create a proof, Bob generates a random value (\(k\)) and generates a random point:
\(R=k.G\)
Next Bob generates a value of \(C\) by taking a hash of the following byte values:
\(C=H(X || G || Y || R)\)
\(S=k + x.G\)
Bob now passes the statement (\(Y\)), \(C\) and \(S\) to Alice as a proof.
Verifying
First Alice computes:
\(G_S = S.G\)
and next:
\(X_C = Y \times (-C)\)
and then recovers R from::
\(R = G_S + X_C\)
Alice now can compute:
\(C'=H(X || G || Y || R)\)
and which check this against the \(C\). If they are the same, the proof has been verified. This works because:
\(R = G_S + X_C = S.G + Y \times (-C) = (k+x.C).G - k.G.C = k.G\)
Coding
The outline code is:
package main import ( "crypto/rand" "fmt" "math" "os" "github.com/coinbase/kryptology/pkg/core/curves" "github.com/coinbase/kryptology/pkg/zkp/schnorr" "golang.org/x/crypto/sha3" ) func powInt(x, y int) int { return int(math.Pow(float64(x), float64(y))) } func main() { curve := curves.K256() message := "Test" name := "K256" argCount := len(os.Args[1:]) if argCount > 0 { name = os.Args[1] } if argCount > 1 { message = os.Args[2] } if name == "K256" { curve = curves.K256() } else if name == "P256" { curve = curves.P256() } uniqueSessionId := sha3.New256().Sum([]byte(message)) prover := schnorr.NewProver(curve, nil, uniqueSessionId) secret := curve.Scalar.Random(rand.Reader) proof, _ := prover.Prove(secret) fmt.Printf("Message to prove: %s\n", message) fmt.Printf("Curve: %s\n", curve.Name) fmt.Printf("\nProof Statement: %x\n", proof.Statement.ToAffineCompressed()) fmt.Printf("Proof C: %x\n", proof.C.Bytes()) fmt.Printf("Proof S: %x\n", proof.S.Bytes()) err := schnorr.Verify(proof, curve, nil, uniqueSessionId) if err == nil { fmt.Printf("ZKP has been proven") } else { fmt.Printf("ZKP has NOT been proven") } }
Sample run
For P256 and a message of "Test 123":
Message to prove: Test 123 Curve: P-256 Proof Statement: 038e1abb750975191287dcf7df8d9026cf78ea49763c50d395fe57bc168d973df9 Proof C: cecc95d5efaabeb9f10d924f14696551ba2d53b10c39764cc2bcdc777f903869 Proof S: 5bb571b6e55242b4a5110d164d8785c3677be6b48c2006c50c8317a367acbb8b ZKP has been proven
Note that the Proof statement is an elliptic curve point in a compressed format. We with we compress the point, by only storing the x-axis value, and whether the y-axis point is odd or even. A compressed point that starts with a "03" is an odd value, or "02" for an even value. For a compressed point, we do not need to store the y-axis point, as we can derive this from the x-axis point. A "04" identifies a uncompressed point for sepc256k1 and P256.