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.
Bulletproofs in Rust |
Code
First we create the Rust project with:
cargo new bulletproof
We then go into the bulletproof folder, and add the following to the cargo.toml file:
[package] name = "bulletproof" version = "0.1.0" authors = ["billatnapier"] [dependencies] curve25519-dalek = "1.2.3" merlin="1.3.0" bulletproofs="1.0.4" rand= "0.6.0" hex="0.4.0"
Next we go into the src folder, and edit the main.rs file with:
extern crate rand; use rand::OsRng; extern crate curve25519_dalek; use curve25519_dalek::scalar::Scalar; extern crate merlin; use merlin::Transcript; extern crate bulletproofs; use bulletproofs::{BulletproofGens, PedersenGens, RangeProof}; extern crate hex; use std::env; fn main() { // Generate a secret value let mut secret = 1037578891; let mut nbits= 32; let args: Vec < String > = env::args().collect(); if args.len()> 1 { secret = args[1].clone().parse::<u64>().unwrap(); } if args.len()> 2 { nbits= args[2].clone().parse::<usize>().unwrap(); } // Pedersen commitments let ped_commits = PedersenGens::default(); // Generators for Bulletproofs, valid for proofs up to 64 bits let bullet_gens = BulletproofGens::new(64, 1); // blinding factor let mut csprng: OsRng = OsRng::new().unwrap(); let blinding_factor = Scalar::random(&mut csprng); // Create transcript let mut prover_ts = Transcript::new("Test".as_bytes()); // Implement an n-bit rangeproof let (proof, commitment) = RangeProof::prove_single( &bullet_gens,&ped_commits,&mut prover_ts,secret,&blinding_factor, nbits,).expect("Oops!"); println!("Secret:\t{}",secret); println!("Bits:\t{}. Range: 0 to {}",nbits,u128::pow(2,nbits as u32)); // Verify the proof let mut verifier_ts = Transcript::new("Test".as_bytes()); let rtn = proof.verify_single(&bullet_gens, &ped_commits, &mut verifier_ts, &commitment, nbits); if rtn.is_ok()==true { println!("++++ Proven!!!"); } else { println!("---- Not Proven!!!"); } println!("\n\nCommitments:\t{}",hex::encode(commitment.as_bytes())); println!("Proof:\t{}", hex::encode(proof.to_bytes())); }
Finally we simply build with:
cargo build
For a proof for 110 for 8 bits:
cargo run 110 8
Testing
The following is a valid proof:
Secret: 110 Bits: 8. Range: 0 to 256 ++++ Proven!!! Commitments: 84209ac579b373a9698c7e068a376f423355d0874956fb7c76cdd8772cf24354 Proof: 44d0ed5b7a67a4bbadf6a64f1eed2bb307c627c4e2aae73798dbed7014314e69b402ff48380a11f179722d99982462689174057745ff0e5cbb0e1ab8e932564860b419a1a69486256f5ef4f88dcc846e35b875a3aec0732aebbaac7487a56114e8629b67766888b703c5b734514a26b5c0f18e42847ddde7ef415123f9e83b1c64fee1fb39faa6efc3c784ea957318423de8fd9afe79516c7250b097fe44d90ef2e142a6993c9d6e1bd9cf55a45999977cfb67c4233c9b41b113d40a7cd0ed0aa12186bd1551b831815402ca5c93208d219c5d34ea4f8cba6428d28b0eb3ec07969c3c9cdbefdca441be47c305a9824b491346e973b02186d97eaacdc5548263acc27e373a0f374653c28cbf879c594070f04a3fb1b99c20a3da4087f254316ce4f0a39fa241befc2e4c1633b83e8ef4e806534703d18a165a0a3d6a5491e93f4456068daa21c936b6ffb98c5fa35abb8165bfb50afd7ebdbcce4c2ac8a2ad5670b1024a9647051a360dae9335aa510e9c42bcfaba73d1ba8a99112a851a27477ecc1378f3b1b1ca51f0bc386445c834195765e2591168a2149c1822a0c4603d71c3398bf2af2ab33066e35e7adb2b5400973161775a9b9dd123415ae69fb10f33a3aaba42b0134bad0ce5a6a5576455b7b1563fe1c97fe05bed6e5c4ab07302
and not proven:
Secret: 310 Bits: 8. Range: 0 to 256 ---- Not Proven!!! Commitments: 5ce5f19103e26c4ba42cc4a127cc3b2d289e1f5fa9c510f1c473ff75a10a623f Proof: 62c415f03e9de164aafcc763634a6bae693b71ab6a8d71cd43cc6f884c7334530c18d876917d346d2e79540c1f016df91a9c2d002d122671f7385349f1921d2cf073826158098826aa766aff182294cb77f2d161a3e4807ac204d60100364b257c0d6ab18730ffa2e54f7b0b2e6cd4804087ce7d885ebc49adf2fd483c474820e67609db7cc329430c6e74574a59a8ca34963f166ecf5c218800ebec2773080f25b91a4b8d016d2a4fabcae4efe621220de51c78dea6e96a3f8b6c2ec795370af580dd52468afa337fb1a9750d7073c8c8ccc1bdbe4457d1c5584a5efc34290b3afea862ce08d3a660b7f9e75837cbeb7a8a23a24f898066b4fc6ee5b085c26efa92e44193ceaa76883bcab77c653566ef77b09f92046f2bc049ab2e749cfc08b88b675222ddcbb9150712959d4beabc6a386f654b471c445411c0dc2fceb81784330f89582c23a279fb6061ac170d5d2ec35235788c0c56f5bb3b852360d70c0697d5799c3aaf00b2bccf43797a165cacae59fe976b8437c76e5b645c19d108a43c1a5d3dc6d3c24fd6d632bbeaf9f67cc3ba2eaf87d00b56c3496634a5d020fb1cf314e8cfad20fda58cfb98d02be6f70f70bd54b22fc95b0249c4a6cfe3078e55397e2c6ba4e520876ad50ff78719c4ad24eff85ad5fcc741223d40910a00