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 (R,S), and also a "Statement". In this case, we will hash our messages to a challenge value, and then use a Schnorr zero knowledge proof method to prove the knowledge of four strings, without revealing these strings.
Schnorr Proof for ZKP (with Kryptology and Golang) for four strings |
Proving
For this, we will use the Schnorr proof. Initially, Bob has a secret value of \(x\) and which could be his private, and sends Alice the value of:
\(X=x.G\)
and which could be his public key. If we have a secret messages of: \(m_1\), \(m_2\), \(m_3\) and \(m_4\). He then hash each of these messages:
\(M_1=Hash(m_1)\)
\(M_2=Hash(m_2)\)
\(M_3=Hash(m_3)\)
\(M_4=Hash(m_4)\)
We then produce:
\(C=H( M_1 || M_2 || M_3 || M_4 || X)\)
and where H() is a hash function, and "||" is a concatenation of the bytes. Bob then creates a random value of \(k\) to produce:
\(R=k.G\)
and where \(G\) is a base point on a curve. Next he creates:
\(S=k+x.C\)
Bob now passes the statement \(R\) 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 will know the hashes of the messages and can now compute:
\(C'=H(M_1 || M_2 || M_3 || M_4 || X)\)
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" crand "crypto/rand" "fmt" "os" "github.com/coinbase/kryptology/pkg/core/curves" "github.com/coinbase/kryptology/pkg/zkp/schnorr" "golang.org/x/crypto/sha3" ) func main() { message1 := "Alice" message2 := "Bob" message3 := "Carol" message4 := "Dave" argCount := len(os.Args[1:]) if argCount > 0 { message1 = os.Args[1] } if argCount > 1 { message2 = os.Args[2] } if argCount > 2 { message3 = os.Args[3] } if argCount > 3 { message4 = os.Args[4] } curve := curves.K256() G := curve.Point.Generator() x := curve.Scalar.Random(crand.Reader) X := G.Mul(x) m1 := sha3.New256().Sum([]byte(message1)) // m2 := sha3.New256().Sum([]byte(message2)) // m3 := sha3.New256().Sum([]byte(message3)) // m4 := sha3.New256().Sum([]byte(message4)) // hash := sha3.New256() _, _ = hash.Write([]byte(m1)) _, _ = hash.Write([]byte(m2)) _, _ = hash.Write([]byte(m3)) _, _ = hash.Write([]byte(m4)) _, _ = hash.Write([]byte(X.ToAffineUncompressed())) C := hash.Sum(nil) prover := schnorr.NewProver(curve, nil, C) random_seed := curve.Scalar.Random(rand.Reader) proof, _ := prover.Prove(random_seed) fmt.Printf("\nMessage 1: %s\n", message1) fmt.Printf("Message 2: %s\n", message2) fmt.Printf("Message 3: %s\n", message3) fmt.Printf("Message 4: %s\n", message4) fmt.Printf("Public key (X): %x\n", X.ToAffineUncompressed()) fmt.Printf("\nProof Statement: %x\n", proof.Statement.ToAffineCompressed()) fmt.Printf("Proof R: %x\n", proof.C.Bytes()) fmt.Printf("Proof S: %x\n", proof.S.Bytes()) err := schnorr.Verify(proof, curve, nil, C) if err == nil { fmt.Printf("ZKP has been proven") } else { fmt.Printf("ZKP has NOT been proven") } fmt.Printf("\n\n== Now trying the wrong message ==") hash = sha3.New256() _, _ = hash.Write([]byte("Test")) C = hash.Sum(nil) proof, _ = prover.Prove(random_seed) err = schnorr.Verify(proof, curve, nil, C) if err == nil { fmt.Printf("\nIncorrect hash is proven with incrrect message (bad) ") } else { fmt.Printf("\nZKP has NOT been proven with incorrect message (good)") } }
Sample run
A sample run is:
Message 1: Bob Message 2: Alice Message 3: Carol2 Message 4: Dave Public key (X): 04c4b73d4a2cd0b56613ef63ce09264a7d5eae4cc339f986f2239bedbc71e00bd34b7939025947e1f2523bf63cb557c1b14ccb6164fb3ae78a2544919a23ccd323 Proof Statement: 026f8d3e7d92ff565cd0dd2aa372e3497287bf7194797996c7bcedc3d021c06ad2 Proof R: 95a875e028a54d9237f993da47859ec3a478f0f7b10de7f85f2cb8d1572b61b2 Proof S: cddc5f862affaa56fc5d0613db3b13d7c0bbf68691cb5a2f404f4947845b4c0d ZKP has been proven == Now trying the wrong message == ZKP has NOT been proven with incorrect message (good) == Now trying the wrong message == ZKP has NOT been proven with incorrect message (good)
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.