BBS+ signatures enable selective disclosure of the signed messages, meaning that we can show only part of the signed payload to the verifier and that the verifier does not get to see the signature.
This document is meant as a somewhat high level overview of how the scheme works (going to the lowest level for the brave souls), as there is no explanation of it in plain English. I assume that the reader has 0 knowledge of cryptography and how it works, however, if any part bores you, feel free to skip it and return back to it if you need it.
Groups allow us to do one way operations, so that if I give you some number, you don't know which number I used to get
to the number I have given you. For example:
More
You can think of groups as a set of numbers to which we can do some operation and the product of the operation is still part of this group. Groups that interest cryptographers are usually natural numbers modulus some big number. Let's take a group of 5 numbers as an example: 0, 1, 2, 3, 4 - we will throw away 0, because no one likes 0. If we use an operation such as exponentiation over 2, we will observe that we map each number to a new number, but we never repeat.
$2^1 \pmod 5 = 2$ $2^2 \pmod 5 = 4$ $2^3 \pmod 5 = 3$ $2^4 \pmod 5 = 1$ $2^5 \pmod 5 = 2$ $2^6 \pmod 5 = 4$ $2^7 \pmod 5 = 3$ - ...
So from above we can observe that we repeat after four elements and that we map 1 => 2, 2 => 4, 3 => 3, 4 => 1. The base 2 is called generator, because by using it, we can get every other element of the group (1, 2, 3, 4). The cool thing about this is that there is no logarithm to "reverse engineer" the exponent (without generating the whole group). The group above is called a cyclic group, because we can generate the same number of elements as we are moding by -> 5 (minus 1).
Mathematically we would write this as
Elliptic curve cryptography is the same shit, but different. Instead of exponentiation, we use point multiplication,
which we can compute efficiently. What do I mean by point multiplication? We have a generator
How exactly does this work? There are plenty of sources that explain this, for the purposes of this doc, just know that we add and multiply points instead of multiplying and exponentiating, but they have the same role respectively.
Formulas for the signature magic actually use multiplication and exponentiation. I don't know why, but I don't make the rules around here, just follow them.
Pairing friendly curves are curves that have some additional properties. Mainly, they allow us to "pair" two groups
together using some operation
We use BLS12-381, but we could use any other pairing friendly curve for this.
I'll first introduce the simpler BLS signatures, just for you to see how signing works. Signing is essentially just multiplication of a point by some number. So a basic BLS signature looks something like this:
- we have two groups
$G_{1}$ and$G_{2}$ with generators$g_{1}$ and$g_{2}$ -
$x$ is a private key -
$g_{2}^x \equiv w$ is a public key in$G_{2}$ -
$m$ is a message we want to sign represented as a point in$G_{1}$
To sign we just do
More
At first this might look like random shit thrown together... And it kind of is, at least from the eyes of whoever is verifying the signature. We can however expand the random letters and get the following:
$e(S, g_{2}) \equiv e(m, w)$ -
$e(m^x, g_{2}) \equiv e(m, g_{2}^x)$ - substitute the letters with how they were constructed -
$e(m, g_{2})^x \equiv e(m, g_{2})^x$ - this is the cool part of pairing friendly curves: we can extract the exponent out of parenthasis
But remember, as a verifier we are only shown
Now let's try to do this for multiple messages. I'll start with the basic version and add some details later:
-
$x$ is a private key -
$g_{2}^x \equiv w$ is a public key -
$M$ is a set of messages represented as numbers -
$H$ is a set of random points in$G_{1}$ that we will multiply by messages -
$|H| = |M|$ -> We generate the same number of random points as we have messages
First we will multiply the random points by messages and sum them together
and then also multiply them by generator
So how would we verify this? Well... First, we have to send a bit more information to the verifier, namely:
-
$w$ - BLS public key -
$H$ - Random bases -
$A$ - Signature value -
$M$ - Messages
With this info, the verifier can compute the value
More
If we write everything out, we will get the following
$e(A, w) \equiv e(b, g_{2})$ $e(b^{\frac{1}{x}}, g_{2}^x) \equiv e(b, g_{2})$ $e(b, g_2)^{\frac{1}{x} \times x} \equiv e(b, g_{2})$ $e(b, g_2) \equiv e(b, g_2)$
Now to the actual implementation. Most of the stuff above will remain the same, we will just add some additional parameters more or less.
So, the signer starts with:
-
$x$ is a private key -
$g_{2}^x \equiv w$ is a public key -
$M$ is a set of messages represented as numbers -
$H$ is a set of semi random points in$G_{1}$ which we will multiply by messages -
$h_{0}$ ,$e$ and$s$ are some random parameters -
$|M| + 1 = |H|$ - We added one more random point to$H$
Notice
The
The verifier will now get:
-
$w$ - BLS public key -
$A$ - Signature value -
$e$ and$s$ - Random parameters -
$M$ - Messages
He will then calculate
More
Mostly the same as above, the only difference is that now we have to add
$e(A, w \times g_{2}^e) \equiv e(b, g_{2})$ $e(b^{\frac{1}{x+e}}, g_{2}^x \times g_{2}^e) \equiv e(b, g_{2})$ $e(b^{\frac{1}{x+e}}, g_{2}^{x+e}) \equiv e(b, g_{2})$ $e(b, g_{2})^{\frac{1}{x+e} \times (x+e)} \equiv e(b, g_{2})$ $e(b, g_{2}) \equiv e(b, g2)$
We have now arrived at the hardest part of the scheme to understand, which is how do we prove the signature without showing it to the verifier and also how do we do this while only showing some of the messages the signer signed. I'll again start by a simplified version, which will not use zero knowledge proofs.
So now we have the signature, which is composed of:
-
$A = b^{\frac{1}{x + e}}$ - Signature value -
$s$ and$e$ - random values
To make the proof, we will first randomize
What exactly are we proving? Three things:
$e(A', w) \equiv e(\bar{A}, g_2)$ $\frac{\bar{A}}{d} \equiv A'^{-e} \times h_{0}^{r_{2}}$ $g_1 \times \prod_{i \in D} h_i^{m_i} \equiv d^{\frac{1}{r_1}} \times h_0^{-s'} \times \prod_{j \notin D} h_j^{-m_j}$
Where
So what does verifier need? Well, "too much", but we will give it to him anyway, for now. Our proof thus consists of:
-
$A'$ - ok -
$\bar{A}$ - ok -
$d$ - ok -
$M_{hidden}$ - nok (these are hidden messages after all) -
$-e$ - nok -
$r_2$ - nok -
$r_1$ - nok -
$s'$ - nok
Important thing to note here is that left side of all equations contains the data, which should be visible to the verifier.
Now for the brain fuck that are ZKP schemes. We want to hide all the "not ok" parts of the proof from the verifier. Well, all of them are exponents and there exists a non-interactive ZKP scheme - Fiat-Shamir.
What is Fiat-Shamir?
Alice wants to prove to Bob that she knows secret
- She picks random value
$r \in \mathbb{Z}_q^*$ and computes commitment$C = g^r$ - She computes challenge
$X = H(g, y, t)$ where$H$ is a hash function - She computes response
$v = r - s \times X$ . The result is proof (C, v) - Bob now checks if
$C \equiv g^v \times y^X$ .
This works, because:
... Yes, magic.
I will show how this is done for proving the 2. point, as it is shorter, but the same stuff applies to point 3.
Looking at the right side of this equation, everything is public except
First, prover will create a commitment by randomizing the bases:
For Fiat-Shamir we also need a challenge
Verifier now gets back the following proof (without point 3 for the sake of simplicity):
$A'$ $\bar{A}$ $d$ $C$ $responses = [r_x - (-e) \times X, r_y - r_2 \times X]$
To validate point 2, we have the following formula:
Basically commitment (sum of randomized bases) is equal to sum of bases multiplied by responses plus left side of the equation multiplied by the challenge.
More
Let's write everything out slowly:
$C = A'^{responses[0]} \times h_0^{responses[1]} \times (\frac{\bar{A}}{d})^X$ -
$C = A'^{r_x - (-eX)} \times h_0^{r_y - r_2X} \times (\frac{\bar{A}}{d})^X$ - substitute responses -
$C = A'^{r_x + eX} \times h_0^{r_y - r_2X} \times (\frac{A'^{-e} \times b^{r_1}}{b^{r_1} \times h_{0}^{-r_2}})^X$ - substitute$\bar{A}$ and$d$ -
$C = A'^{r_x + eX} \times h_0^{r_y - r_2X} \times (\frac{A'^{-e}}{h_{0}^{-r_2}})^X$ -$b^{r_1}$ cancels itself out -
$A'^{r_x} \times h_0^{r_y} = A'^{r_x + eX} \times h_0^{r_y - r_2X} \times (\frac{A'^{-e}}{h_{0}^{-r_2}})^X$ - substitute commitment$C$ -
$A'^{r_x} \times h_0^{r_y} = A'^{r_x + eX} \times h_0^{r_y - r_2X} \times (A'^{-e} \times h_{0}^{r_2})^X$ - resolve fraction -
$A'^{r_x} \times h_0^{r_y} = A'^{r_x + eX} \times h_0^{r_y - r_2X} \times A'^{-eX} \times h_{0}^{r_2X}$ - resolve exponentiation -
$A'^{r_x} \times h_0^{r_y} = A'^{r_x + eX - eX} \times h_0^{r_y - r_2X + r_2X}$ - collapse same bases $A'^{r_x} \times h_0^{r_y} = A'^{r_x} \times h_0^{r_y}$
Magic!
More generally, we could write:
-
$r^*$ - blinding factors -
$Z \equiv Y$ -$Y$ is of shape$\prod a_i^{b_i}$ $C = Y_{bases}^{r^*}$ -
$responses[i] = r_i^* - Y_{exponents[i]} \times challenge$ $$C = (\prod_{i=1}^{|responses|} Y_{bases[i]}^{responses[i]}) \times Z^{challenge}$$