In Our Flawed and Untrusted World … Welcome to the Wonderful World of Range Proofs … And Instant…

In Our Flawed and Untrusted World … Welcome to the Wonderful World of Range Proofs … And Instant Auditing

Towards a bulletproof world of cybersecurity

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 thing. 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 great 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.

A demo of bulletproofs are give here.

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 setup for blockchain integration.
• No need to setup 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.

Come and chat …

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 focused 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.