Proving a Number Is In A Given Range Without Revealing The Number: Meet Bulletproofs
Proving a Number Is In A Given Range Without Revealing The Number: Meet Bulletproofs
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 anonymised 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 is the Pedersen Commitment in action, and where Eve committed to a value and then blinded 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 considerable amount of effort and space was taken up with the commitments. And so bulletproofs have been created to considerably reduce the size of the proof of the transaction.
Bulletproofs was 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 “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
The outline code is [here]:
For a range proof of 0 to 2⁸ (n=8) we get proven for a value of 250 [here]:
v=250, n=8
Range between 0 and 256
It has been proven!
Proof: 86b6330a5dd63d606c65fad5770baaeb2ed6e281e1dc2988e4ffe8ccc62986acc982e0061deace9019e736d4a1a79269faf7395a3bcd4ad49f11a866da1f7a7c7efd0ac61b55d0fdaab8c3015c691a7e78485572f0d5ecc842db8c8c9bb1758c993f1f4829d24a5bf8fb2a6601efcd278ab5bcaf92bcd798d161e7a7b74a13e96a1e402fc5c8924d0702f2851e5b178aac79d4fa8d805eaab4dae1d388016b061a718ebed42b89d38b698062c172c17d39cd0d324287185ffa32d18e3c24a50dbedd697e7e3267eb83aef6638a8850dcfcf8caa3a5ab67fd33f805e7a341e30197d218e476e7cd5ee4da31c39ed183d367a3dc1d4d9ea1639e7dd0c34332aa066fb170ed8b8e7815b6600c39619ab82e28cbf141ef00d1faad51b9d98542160d6a1e04171b2f1d4e41c3a543a5e988aaaab12df1b29e85e57b45f0faed2819c39d85737af8955bdf8be26e0908834b4b75ba1c259743627c957f27162906c4a77dc759010e29ae88cf76ae4975892c678107ffcc2513ff270c3ced4af713db9d1ee72d85557c1b672e9efdfef8b4b53c26cad2294c9ef259c3cf4c5f97bca3895394474595862e96143145d1cc20dc14f6f7e5b6c2fd6744c4fbd3a8547f0e3c315d17724b30b0a26e0e4d7ba05e6ae706d2369e30af08e51a320260819545e8
For a range proof of 0 to (2⁸) we get not proven for a value of 260 [here]:
v=260, n=8
Range between 0 and 256
It has NOT been proven!
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. A demo of bulletproofs is here: