This uses the CSS08 method to find a string within a given set of strings, and produce a Zero-Knowledge Proof (ZKP) of this. In this case, we will use London post codes as a set, and then prove that we have a post code in the set. For this, we convert the strings into a 64-bit integer using a hash of the string, and then just using the first eight bytes of the hash.
Set Membership and Range Proofs with strings in Golang (CSS08) |
Method
Let's say that you have to pay a fine if you parked in a certain area of London. But, you have a permit that codes the areas of E1 1LJ, E1 1AA, E1 1AB, and E1 1AE, and where you parked your car in E1 1AE. How can you prove to the council that you have a valid parking permit for the place you parked without giving away where you parked?
For this, we can create a Zero Knowledge Proof (ZKP) for set membership. In this case, we have a set of valid parking places of "E11LJ E11AA E11AB E11AE", and then create a ZKP for the location of "E11AE". The proof will show that you have a postcode which is contained within the set without revealing it.
With this, Jan Camenisch et al created a method where we can prove that we have a value in a set of values, and without giving our value away [1]. The paper was produced in 2008, and is often referred to as CSS08. With this, we provide a zero-knowledge proof that σ is included in a discrete set Φ. This set is represented as 64-bit integers, and could thus be hashed version of the string.
We can convert a string into a 64-bit integer by taking a SHA-256 hash, and then using eight bytes to produce a signed 64-bit integer:
func StringToInt64(A string) int64 { var ret int64 h := sha256.New() h.Write([]byte(A)) bs := h.Sum(nil)[:8] // Just use 64 bits buf := bytes.NewBuffer(bs) binary.Read(buf, binary.BigEndian, &ret) if ret < 0 { ret = -ret } // Make postive return ret }
We can then take a string array for the post codes and then parse these between spaces, and convert these into a 64-bit integer array to define our set:
func StringToIntInt64(A string) []int64 { strs := strings.Split(A, " ") ary := make([]int64, len(strs)) for i := range ary { ary[i] = StringToInt64(strs[i]) } return ary }
The code is then:
package main import ( "bytes" "crypto/rand" "crypto/sha256" "encoding/binary" "fmt" "os" "strings" "github.com/i0xdecaf/zkrp/ccs08" "go.dedis.ch/kyber/v3/pairing/bn256" ) func StringToInt64(A string) int64 { var ret int64 h := sha256.New() h.Write([]byte(A)) bs := h.Sum(nil)[:8] // Just use 64 bits buf := bytes.NewBuffer(bs) binary.Read(buf, binary.BigEndian, &ret) if ret < 0 { ret = -ret } // Make postive return ret } func StringToIntInt64(A string) []int64 { strs := strings.Split(A, " ") ary := make([]int64, len(strs)) for i := range ary { ary[i] = StringToInt64(strs[i]) } return ary } func main() { tofind := "E11AE" set := "E11LJ E11AA E11AB E11AE" argCount := len(os.Args[1:]) if argCount > 0 { tofind = os.Args[1] } if argCount > 1 { set = os.Args[2] } s := StringToIntInt64(set) p, _ := ccs08.SetupSet(s) fmt.Printf("To prove: %s [%d]\n", tofind, StringToIntInt64(tofind)) fmt.Printf("Set: %v\n", s) r, _ := rand.Int(rand.Reader, bn256.Order) proof_out, err := ccs08.ProveSet(StringToInt64(tofind), r, p) if err != nil { fmt.Printf("Error %s", err.Error()) return } result, err2 := ccs08.VerifySet(&proof_out, &p) if err2 != nil { fmt.Printf("Error %s", err.Error()) return } if result == true { fmt.Printf("\nProof that %s is in [%s]\n\n", tofind, set) } else { fmt.Printf("\nDid not find value in array\n") } fmt.Printf("Proof: C= %s\n", proof_out.C) fmt.Printf("Proof: D= %s\n", proof_out.D) fmt.Printf("Proof: V= %s\n", proof_out.V) }
Now, when we can try if E11AB is included in a set of [E11LJ E11AA E11AB E11AE]:
To prove: E11AB [[4430824517528255324]] Set: [1281183710520809036 5058162997375079209 4430824517528255324 2546757751935566498] Proof that E11AB is in [E11LJ E11AA E11AB E11AE] Proof: C= bn256.G2((7509873101214563597163683780190650039892638744018480009533152639528421573588,4475718032506726237139207880503469751673889912137360720800657351782230168130), (9188851371211643606407750017586881453211197241295535426263957389554181084227,18992014779931465783960663663280212683899890522293147279021309024382333571389), (6879391832489960392949975993929586748964605278079293556349212526397655394163,3844085117072733930522556927617194359937237558518477575268041663481016124684)) Proof: D= bn256.G2((19355457211851888432977175934410856791524853651139502739322367817795174382173,8806361547031016666199222727470212815571941949136321034587808231739030579132), (20336671890284777311594726186351805529212458788694915453274566302607164394586,5086717128969460245852049948120151339215585051883016476940954689933201622563), (0,1)) Proof: V= bn256.G2((15941655410179962564251634815483114091181494694542018383163679157355504337508,10641174239565692007167712294782899033411349507595365405311563271413378499800), (2517555212710176931884574117195971314655042724175768947683110308453733308529,8707140745037179280144535396889037601103996382682310712101145144167941001091), (8370535292913395075061781860418767351958837960139306760022823624996857342071,3095104344669839604671953292680082217798648219197010648729282314038918857078))
Now, when we can try E11AD, we can see that we cannot create a valid proof:
To prove: E11AD [[5797095357436850670]] Set: [1281183710520809036 5058162997375079209 4430824517528255324 2546757751935566498] Error Could not generate proof. Element does not belong to the interval.
The method is described with discrete logarithms as [1]:
Reference
[1] Camenisch, J., Chaabouni, R., & Shelat, A. (2008, December). Efficient protocols for set membership and range proofs. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 234–252). Berlin, Heidelberg: Springer Berlin Heidelberg.
[2] https://github.com/0xdecaf/zkrp