Rebuilding A Flawed Data World with Zero Knowledge

We live in an almost untrusted data world!
Photo by Etienne Girardet on Unsplash

Rebuilding A Flawed Data World with Zero-Knowledge

We live in an almost untrusted data world!

We live in a flawed and untrusted financial world!

So, let me pose a difficult question first, and I’ll answer it at the end:

“Prove to me that the [UK] currently — at this point in time — has economic stability in its financial infrastructure!”

You can insert your own country within the brackets, or any organisation or ranges of organisations that you want. Before you call up your auditors and get your accountants primed, let’s meet Angry Bob and Angry Alice …

Meet Angry Bob and Angry Alice

Bob applies for a loan from Alice The Lender, and she asks him for his salary. Bob says, “I don’t want to tell you that!”, and she says, “Well, you’re not getting a loan!”, and so Bob says that his salary is “One trillion dollars per year”, and Alice hangs up the phone. He calls her up again, and says sorry, and then says that his salary is “… somewhere between $60,000 and $100,000. Is that okay?”. Alice replies that this is fine and that his loan has been approved. “Can you now tell me your password?”, she says. Bob now hangs up the phone and goes to lie down in a dark room.

In this new information world, why do we have to continually prove the same things, and why do we continually give away so much of our private things?

Our rights … not theirs

We need a world which uses Zero-knowledge Proofs (ZKP) and where people can create their own signatures to prove things, without continual prompting and asking for things. If I am over 18, I should provide it once, and then show whoever I want. If I have enough money in my account to pay for something, I can prove this to a merchant, without me having to go and check with my bank. With ZKP, Peggy (the Prover) must prove something to Victor (the Verifier). We could get them to interact, and then at the end of their conversation, Peggy would have proven something to Victor. In a non-interactive method, Peggy does not have to interact with Victor, and where she can prove it without this interaction. This is normally achieved with the Fiat-Shamir heuristic [here].

But we should have rights in the increasingly flawed digital world.

A flawed world?

Sometimes something comes along and it shakes our existing thinking. In a paper at the end of 2017, a research team showed the world how it could enact on-line in a trusted and privacy-preserving way [paper]:

Basically, their method defined a way that Bob can prove that his secret value — and or his encrypted value — is within a given range. For this, he might be applying for an online loan and does not want to reveal his salary. Bob would then be able to create a range proof for Alice The Lender and show that his salary was between $60,000 and $100,000. The challenge for this proof would not have to be set up by Alice, as Bob just sends the proof, and she checks it. If there were an inquiry related to his tax status, he could forward this signature to show the range of his salary to them too.

In a perfect world, Bob could merge these range proofs into a single signature, and present when required. For example, if the lender wanted to check that his balance has at least $100, he could add this to his signature, and send to Alice.

Within cryptocurrency trading, this is useful, as we can check whether someone has enough funds in their account before the transaction can be verified, but not actually reveal how much they have in their account. The proof is then that the sum of all the inputs (the money in) is greater than the sum of all the outputs (the money out). This proves that there are Unspent Transaction Outputs (UTXOs) — and that there are enough funds in a given account. One task of the miners in Bitcoin is then to prove that the inputs are greater than the outputs. For this, a user provides a signature for the transaction to prove there are enough unspent credits to cover the transaction, and then the miners check this and the current balance:

So Why Bulletproofs?

Before the Bulletproof paper, the size of this proof is linear to the number of inputs. Previous work on Confidential Transactions (CTs) focused on the Pedersen Commitment method [here] to preserve the confidentiality of the transaction (using Zero-Knowledge Proofs), but still prove that the sum of the inputs was greater than the sum of the outputs. The signature then is created to verify that the sum of the inputs is greater than the outputs and that the transaction values are between 0 and 2^n [0,2^n]. The signature of this grows linearly with the value of n, and there is a general worry that existing CT methods will overload our blockchains, with most of the data within a transaction used up with a range proof.

Our checking model — and using anonymised transaction values — becomes:

With Bulletproofs we have a much smaller proof and where we can even merge range signatures together, and also never reveal any user secrets. A bulletproof only grows logarithmically in size with the number of outputs and range proof’s size. After implementation, Monero has seen an 80% reduction in transaction size, and which has also led to a significant reduction in the transaction fees.

Let’s have a party

In many things in our world, we often need to prove things that involve many people. Let’s say that Bob is applying for a loan from Alice, and now needs to prove that he has a salary of between $60,000 and $100,000, and that his employer — Trent — has at least $1million in the bank For this we can integrate MPC (Multi-party Computation) and where Bob and merge his proof with Trent into a single bulletproof signature to Alice, and she can check it. Bob or Alice does not know how much Trent has in the bank, and Alice cannot see what Bob’s salary is, but she can prove that things are correct from a single — and short — bulletproof signature.

A trusted setup or not?

One of the best methods for range proofs was proposed by Jan Camenisch et al in 2008. This involves Peggy committing to a secret value, and then proves this to Victor with ZKP that the bits are the same, and where each commitment will have another signature. Some sample code which integrates into the Ethereum blockchain is [here]. The example defined in this code is where the check whether someone is over 18 years old, and is based in the EU (without giving away their age and their location).

While this works well, it can lead to lengthy signatures for different ranges, and also requires a trusted setup. With Bulletproofs we can merge signatures, and where it does not require an initial trusted setup. Peggy thus does not need to set the bulletproof up with Victor, and can basically just pass the signature when required.

So what’s so special?

So what’s so special about Bulletproofs:

  • Significant reduction in the size of the signature as opposed to other CT methods (such as zk-SNARKs and zk-STARKs).
  • Significantly reduced transaction fees with shorter signatures.
  • Supports MPC (Multiparty Computation) and where many parties can come together to create a single range proof, without revealing their secrets.
  • Allow for the aggregation of range proofs and produces a single, and short, signature.
  • Fast verification of proofs (and which are faster than most range proof methods, but still slower than zk-SNARKs).
  • Design to be set up for blockchain integration.
  • No need to set up a trust infrastructure. This often involves creating an initial set of encryption keys which are then used for trusted signatures. These keys should be used only once, and then deleted. If these keys are not deleted, there is a risk to future trustworthiness of the whole infrastructure.

What will this mean for the stability of our financial world?

Our current financial world is built on 20th Century methods and has little in the way of trust. Our auditing system, too, is still focused on old ways of thinking.

Over the past few decades, we have seen banks fail, and cryptocurrency exchanges crashing. With bulletproofs, we can ask our financial institutions to prove that they have liquidity … “Prove that you have more than $1 billion of liquidity”, and if they failed to prove this, we would quickly move to audit them. Fraud on a large-scale basis would thus be detected in seconds.

In the end, we can say, “Prove to me that the UK has economic stability in its financial infrastructure!”, and our financial institutions can come together, and prove this, without actually revealing their current financial status. And so bulletproofs could prove us with a way for the sharing of information, without having to give our secrets away.

Rust implementation

Rust is one of the most secure and robust programming languages around, so let’s create a simple demo. 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 [here]:

[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::<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

The following is a valid proof [here]:

Secret:	110
Bits:	8. Range: 0 to 256
++++ Proven!!!

Commitments:	84209ac579b373a9698c7e068a376f423355d0874956fb7c76cdd8772cf24354
Proof:	44d0ed5b7a67a4bbadf6a64f1eed2bb307c627c4e2aae73798dbed7014314e69b402ff48380a11f179722d99982462689174057745ff0e5cbb0e1ab8e932564860b419a1a69486256f5ef4f88dcc846e35b875a3aec0732aebbaac7487a56114e8629b67766888b703c5b734514a26b5c0f18e42847ddde7ef415123f9e83b1c64fee1fb39faa6efc3c784ea957318423de8fd9afe79516c7250b097fe44d90ef2e142a6993c9d6e1bd9cf55a45999977cfb67c4233c9b41b113d40a7cd0ed0aa12186bd1551b831815402ca5c93208d219c5d34ea4f8cba6428d28b0eb3ec07969c3c9cdbefdca441be47c305a9824b491346e973b02186d97eaacdc5548263acc27e373a0f374653c28cbf879c594070f04a3fb1b99c20a3da4087f254316ce4f0a39fa241befc2e4c1633b83e8ef4e806534703d18a165a0a3d6a5491e93f4456068daa21c936b6ffb98c5fa35abb8165bfb50afd7ebdbcce4c2ac8a2ad5670b1024a9647051a360dae9335aa510e9c42bcfaba73d1ba8a99112a851a27477ecc1378f3b1b1ca51f0bc386445c834195765e2591168a2149c1822a0c4603d71c3398bf2af2ab33066e35e7adb2b5400973161775a9b9dd123415ae69fb10f33a3aaba42b0134bad0ce5a6a5576455b7b1563fe1c97fe05bed6e5c4ab07302

and not proven [here]:

Secret:	310
Bits:	8. Range: 0 to 256
---- Not Proven!!!

Commitments:	5ce5f19103e26c4ba42cc4a127cc3b2d289e1f5fa9c510f1c473ff75a10a623f
Proof:	62c415f03e9de164aafcc763634a6bae693b71ab6a8d71cd43cc6f884c7334530c18d876917d346d2e79540c1f016df91a9c2d002d122671f7385349f1921d2cf073826158098826aa766aff182294cb77f2d161a3e4807ac204d60100364b257c0d6ab18730ffa2e54f7b0b2e6cd4804087ce7d885ebc49adf2fd483c474820e67609db7cc329430c6e74574a59a8ca34963f166ecf5c218800ebec2773080f25b91a4b8d016d2a4fabcae4efe621220de51c78dea6e96a3f8b6c2ec795370af580dd52468afa337fb1a9750d7073c8c8ccc1bdbe4457d1c5584a5efc34290b3afea862ce08d3a660b7f9e75837cbeb7a8a23a24f898066b4fc6ee5b085c26efa92e44193ceaa76883bcab77c653566ef77b09f92046f2bc049ab2e749cfc08b88b675222ddcbb9150712959d4beabc6a386f654b471c445411c0dc2fceb81784330f89582c23a279fb6061ac170d5d2ec35235788c0c56f5bb3b852360d70c0697d5799c3aaf00b2bccf43797a165cacae59fe976b8437c76e5b645c19d108a43c1a5d3dc6d3c24fd6d632bbeaf9f67cc3ba2eaf87d00b56c3496634a5d020fb1cf314e8cfad20fda58cfb98d02be6f70f70bd54b22fc95b0249c4a6cfe3078e55397e2c6ba4e520876ad50ff78719c4ad24eff85ad5fcc741223d40910a00

Conclusions

If you are interested in anything that is discussed here, then contact us in our Blockpass ID Lab — the first fully-funded research lab in the world which focuses on identity — as we want to collaborate and build a more trusted world, and which puts the rights of those involved at the core of this new world.

The way we audit needs to change and to not spend months pouring over financial statements and spreadsheets. We need ways to prove and merge and share information — and stop giving away all our secret information — and bulletproofs provide another piece of the jigsaw.

I leave you with one word … Trust!