Bulletproofs is an efficient zero-knowledge method, and which allows us to provide proof that we have a value between 0 and \(2^n\). Bulletproofs were created in 2017 by Stanford’s Applied Cryptography Group (ACG) [paper]. They define a zero-knowledge proof and where a value can be checked to see it lies within a given range. The name of “bulletproofs” is defined as they are short like a bullet, and with bulletproof security assumptions. In the following we define the size of the bit vector and then check to see if a value is in that range — a range proof. If the bit vector is 8 bits long, then we will prove that the value lies between 0 and 255. A value larger than this will fail. The test is thus whether \(x \in [0,2^{n}−1]\), and where \(n\) is the number of bits in the bit vector [article]
Implementing Bulletproofs in Kryptology and Golang |
Outline
Our digital world gives away too many of our secrets, and really it doesn't have to. Every time we prove our password, we have to pass it to a service, and which then validates it. Why does the system have to store our secret? Why can't have a little puzzle to solve, and which can only be solved if we know our secret? And so, with zero-knowledge proofs (ZKPs) we can.
With ZKPs, Bob initially registers a blinded value of his secret. No-one will be able to know his secret from the blinded value. When Bob to prove that he knows his password, Alice sends a challenge to him, and then he computes an answer which proves he knows his secret. This is known as an interactive ZKP, and requires some form of handshaking of data between Bob and Alice. A basic interactive version using elliptic curve cryptography is [here]:
In this case, Bob has a secret (x) and creates two elliptic curve points (\(xG\) and \(xH\)), and sends these to Alice. Alice then sends Bob a scalar value (\(c\)), and he then selects a random scalar (\(v\)). Next, he computes \(r\), and sends \(r\), \(vG\) and \(vH\) to Alice. She then does a quick check with the values she has and the values that Bob has sent, and can prove that Bob knows \(x\).
But, Bob could also generate his own challenge and answer, and gives it to Alice. Alice then checks that the challenge Bob has created is a fair one - and that Eve could not have faked - and that the answer is correct. This is a non-interactive ZKP (NI-ZKP) and cuts down on the overhead of the interaction between Bob and the service. In this version, Bob still generates a random value (\(v\)), but now generates his own challenge (\(c\)) and which Alice can also compute. This challenge is still much the same as the previous version, but is a hash of all the values that he previous sent:
The challenge is then the hash of xG, xH, vG and vH. As Alice knows all these values, she checks the proof is correct (with \(r\), \(vG\) and \(vH\), along with Bob's registered commitments of \(xG\) and \(xH\)). If the proof checks out, she will know that Bob still knows his password, and would then allow him to log in. In this case, Alice has not prompted for anything, but Bob has given her the proof she needs.
Meet Merlin
The actual interaction details between Bob and Alice can be a little vague, so Henry de Valence created the Merlin protocol. This protocol aims to automate the Fiat-Shamir method by creating a non-interactive proof, through interactive methods. With this, we then create two domains - for Bob and Alice - and create all the required challenges and requests. Thus, for the first time, we now have a library that can robustly generate challenges and responses for both Bob and Alice.
One of the first implementations of Merlin is within Bulletproofs, and where a Bulletproof allows us to create a proof that an integer value (x) is between 0 and \(2^n\). We can use this method within privacy-preserving cryptocurrency, and where we can prove that Bob has enough UXTOs (unspent transaction outputs) to pay for something, and without revealing any of his transactions.
In the following, we create a Merlin transcript with a new session label ("test"), and then feed it into a Bulletproof proof that a value (\(v\)) is in the range of 0 to \(2^n\):
The outline code is:
package main import ( crand "crypto/rand" "fmt" "math" "os" "strconv" "github.com/coinbase/kryptology/pkg/bulletproof" "github.com/coinbase/kryptology/pkg/core/curves" "github.com/gtank/merlin" ) func powInt(x, y int) int { return int(math.Pow(float64(x), float64(y))) } func main() { curve := curves.ED25519() n := 8 v_val := 220 argCount := len(os.Args[1:]) if argCount > 0 { n, _ = strconv.Atoi(os.Args[1]) } if argCount > 1 { v_val, _ = strconv.Atoi(os.Args[2]) } prover, _ := bulletproof.NewRangeProver(n, []byte("rangeDomain"), []byte("ippDomain"), *curve) v := curve.Scalar.New(v_val) gamma := curve.Scalar.Random(crand.Reader) g := curve.Point.Random(crand.Reader) h := curve.Point.Random(crand.Reader) u := curve.Point.Random(crand.Reader) transcript := merlin.NewTranscript("test") proof, _ := prover.Prove(v, gamma, n, g, h, u, transcript) fmt.Printf("v=%d, n=%d\n", v_val, n) fmt.Printf("Range between 0 and %d\n", powInt(2, n)) if proof != nil { fmt.Printf("It has been proven!") } else { fmt.Printf("It has NOT been proven!") } }
Sample run
For a range proof of 0 to \(2^8\) we get proven for a value of 250:
v=250, n=8 Range between 0 and 256 It has been proven! Proof: 86b6330a5dd63d606c65fad5770baaeb2ed6e281e1dc2988e4ffe8ccc62986acc982e0061deace9019e736d4a1a79269faf7395a3bcd4ad49f11a866da1f7a7c7efd0ac61b55d0fdaab8c3015c691a7e78485572f0d5ecc842db8c8c9bb1758c993f1f4829d24a5bf8fb2a6601efcd278ab5bcaf92bcd798d161e7a7b74a13e96a1e402fc5c8924d0702f2851e5b178aac79d4fa8d805eaab4dae1d388016b061a718ebed42b89d38b698062c172c17d39cd0d324287185ffa32d18e3c24a50dbedd697e7e3267eb83aef6638a8850dcfcf8caa3a5ab67fd33f805e7a341e30197d218e476e7cd5ee4da31c39ed183d367a3dc1d4d9ea1639e7dd0c34332aa066fb170ed8b8e7815b6600c39619ab82e28cbf141ef00d1faad51b9d98542160d6a1e04171b2f1d4e41c3a543a5e988aaaab12df1b29e85e57b45f0faed2819c39d85737af8955bdf8be26e0908834b4b75ba1c259743627c957f27162906c4a77dc759010e29ae88cf76ae4975892c678107ffcc2513ff270c3ced4af713db9d1ee72d85557c1b672e9efdfef8b4b53c26cad2294c9ef259c3cf4c5f97bca3895394474595862e96143145d1cc20dc14f6f7e5b6c2fd6744c4fbd3a8547f0e3c315d17724b30b0a26e0e4d7ba05e6ae706d2369e30af08e51a320260819545e8
For a range proof of 0 to \(2^8\) we get not proven for a value of 260:
v=260, n=8 Range between 0 and 256 It has NOT been proven!