Rust and Bulletproofs … Towards A More Trusted and Private Digital World
Rust and Bulletproofs … Towards A More Trusted and Private Digital World
What’s the most secure and robust programming language around? Well, it’s most likely to be Rust. It is a programming language that does extensive checks on the code, and which tries to overcome the problems caused by C and C++. With Rust, you can still use pointers, but they are implemented in a robust way. So let’s implement a zero-knowledge method known as Bulletproofs in Rust, and see if we can demonstrate their operation.
A demo of the method we will illustrate is here:
https://asecuritysite.com/rust/rust_bullet
Introduction
We live in a 1980s viewpoint of data.
Very little of our data transactions and logs can be truly trusted. Along with this, we also reveal a great deal of information in the records that we keep.
We thus need to move to a more trusted world, and where we can trust each transaction, but make sure they are privacy-preserving. We now see cryptocurrencies rushing to protect the details of transactions — such as with Ethereum using zkSnarks, Monero implementing Ring Signatures and Bulletproofs, and Bitcoin looking towards Mimblewimble. Our ledger will thus increasingly look like an anomyised list of transactions, and where the sender, the receiver and the transaction detail will be anonymised. At the core of much of this work is the CT (Confidential Transaction) and where we use Pedersen Commitments to blind the data.
Overall our data world of the future could look like this, and where we have an anonymised lowest layer, and then reveals parts of it to implement things like finance and health care:
Only with the special secrets — the blinding factors — will we reveal the details. But we need to make sure that the transactions are still valid before they are enacted. For this we look to Bulletproofs as an efficient way of making sure that blinded transactions are still valid
Eve does Pedersen
Right. Eve The Magician asks the audience for a value of G, and Carol shouts out “5”. Eve then asks Alice to think of a number (a) and multiply the two values together to give y:
y = aG
“Don’t tell me the result”, says Eve. She now asks for another number from the audience, and they shout out “7”. Eve writes something on a piece of paper, and shouts out that her answer is “38”. She turns to Alice and asks her for the result of her calculation, and she says that y is “10”. The audience are worried that Eve has failed in her trick.
“But”, she says, “my card says a value of ‘4’”, and she shows this to the audience, “Now please calculate z, and which is aG + bH”. What is the value that you get?”. Alice calculates and shows her calculation:
“38”
“And that is the answer that I showed you before I knew Alice’s value”, says Eve to great applause. This the Pedersen Commitment in action, and where Eve committed to a value, and then blinding her guess. She then revealed her blinding factor, and showed that she knew the answer all along.
In this case Alice’s secret was “2” and Eve’s blinding factor was “4”, so Eve got:
z = aG + bH = 2*5 + 4 * 7 = 38
Eve knew that Alice was going to pick “2” (don’t ask why, as she is a magician), so she blinded it with “4”, and was able to show that she knew Alice’s value.
This is known as Pedersen Commitment — or nothing up my sleeve (NUMS) — and where we produce our commitment and then show the message that matches the commitment. In its core form, we can implement a Pedersen Commitment in discrete logs [here]. But blockchain, IoT, Tor, and many other application areas, now use elliptic curve methods, so let’s see if we can make a commitment with them.
Adding a blinding value
For this, we can obscure the values in a transaction by adding a blinding value. Let’s say that we have a transaction value of v, we can now define this as a point on the elliptic curve (H) as:
v×H
If we have three transactions (v1, v2 and v3), we can create a sum total of:
Total=v1×H+v2×H+v3×H=(v1+v2+v3)×H
We can thus determine the sum of the transactions. But we could eventually find-out the values of v1, v2 and v3, as they would always appear as the same value when multiplied by H. We can now add a blinding factor by adding a second point on another elliptic curve (G) and a private key (r). A transaction value is then (as defined as a Pedersen Commitment):
C = v×H+r×G
Let’s say that Bob has two input values (v1 and v2) and one output value (v3), and where v3= v1+v2. We can then create a blinding factor for each transaction:
C = (ri1×G+vi1×H)+(ri2×G+vi2×H)=(ro3×G+vo3×H)
Then:
ri1+ri2=ro3
In this case if we can prove this, we have proven that the inputs are equal to the outputs.
Bulletproofs and rangeproofs
Now, the size of Pedersen Commitments just keeps increasing for the number of transactions we are blinding. This was keenly felt by Monero, and where a consider amount of effort and space were taken up with the commitments. And so bulletproofs have been created to considerably reduce the size of the proof of the transaction.
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 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∈[0,2^n−1], and where n is the number of bits in the bit vector.
Coding
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 [here]:
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::().unwrap(); }
if args.len()> 2 { nbits= args[2].clone().parse::
().unwrap(); }// Pedersen commitments
let pc_gens = 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, committed_value) = RangeProof::prove_single(
&bullet_gens,
&pc_gens,
&mut prover_ts,
secret,
&blinding_factor,
nbits
).expect("A real program could handle errors");
println!("Secret:\t{}",secret);
println!("Bits:\t{}. Range: 0 to {}",nbits,u64::pow(2,nbits as u32));
println!("\nCommitted value:\t{}",hex::encode(committed_value.as_bytes()));// Verify the proof
let mut verifier_transcript = Transcript::new("Test".as_bytes());let (proof, committed_value) = RangeProof::prove_single( &bullet_gens,&pc_gens,&mut prover_ts,secret,&blinding_factor, nbits).expect("Oops!");if rtn.is_ok()==true { println!("Proven!!!"); }
else { println!("Not Proven!!!"); }// println!("Proof:\t{:?}",proof);
}Finally we simply build with:
cargo build
For a proof for 110 for 8 bits [here]:
cargo run 110 8
The following is a valid proof [here]:
Secret: 110
Bits: 8. Range: 0 to 256
Committed value: 8867d1637fe92cd18fcb8f85679efdc39ee764bfc1e5a7593b0009bceee19a15
Proven!!!
and not proven [here]:
Secret: 310
Bits: 8. Range: 0 to 256
Committed value: 3e58da797b4c88eb4ca24500af0833917a17ac6e6d6b826bacd58834d744424c
Not Proven!!!
If you are coding with Rust, I highly recommend using Visual Studio Code:
Conclusions
We need to move to a more trusted world, and agree that the old data model of our world is finished. Our new model will integrate trust into our transactions, and break away from our centralised viewpoint of the world.
Here are more Rust coding examples:
https://asecuritysite.com/rust/
My site is free to access. Please help support its development: