tags | title |
---|---|
papers polynomials boneh-lynn-shacham bls interpolation fast-fourier-transform fft |
Fast and Scalable BLS Threshold Signatures |
{: .info}
tl;dr: We use
The question of scaling threshold signatures came to us at VMware Research after we finished working on SBFT1, a scalable Byzantine Fault Tolerance (BFT) protocol that uses BLS threshold signatures2.
We recently published our work3 in IEEE S&P'20. Our work also address how to scale the necessary distributed key generation (DKG) protocol needed to bootstrap a BLS threshold signature scheme. We present these results in another post.
A prototype implementation is available on GitHub here.
Let
In this post, beyond basic group theory for cryptographers4, I will assume you are familiar with a few concepts:
-
Bilinear maps5. Specifically,
$\exists$ a bilinear map$e : \G_1 \times \G_2 \rightarrow \G_T$ such that:$\forall u\in \G_1,v\in \G_2, a\in \Zp, b\in \Zp, e(u^a, v^b) = e(u,v)^{ab}$ -
$e(g_1,g_2)\ne 1_T$ where$g_1,g_2$ are the generators of$\G_1$ and$\G_2$ respectively and$1_T$ is the identity of$\G_T$
-
BLS signatures2. Specifically,
- Let
$H : \{0,1\}^* \rightarrow \G_1$ be a collision-resistant hash-function (CRHF) - The secret key is
$s\in_R \Zp$ and the public key is$g_2^s\in \G_2$ -
$\sigma = H(m)^s \in \G_1$ is a signature on$m$ under secret key$s$
- To verify a signature, one checks if
$e(H(m), g_2^s) = e(\sigma, g_2)$
- Let
-
$(t,n)$ BLS threshold signatures6. Specifically,-
Shamir secret sharing7 of secret key
$s$ - i.e.,
$s = \phi(0)$ where$\phi(X)\in \Zp[X]$ is random, degree$t-1$ polynomial -
Signer
$i\in\{1,2,\dots, n\}$ gets his secret key share$s_i = \phi(i)$ and verification key$g^{s_i}$ - Nobody knows
$s$ , so cannot directly produce a signature$H(m)^s$ on$m$ - Instead,
$t$ or more signers have to co-operate to produce a signature - Each signer
$i$ computes a signature share or sigshare$\sigma_i = H(m)^{s_i}$ - Then, an aggregator:
- Collects as many
$\sigma_i$ 's as possible
- Verifies each
$\sigma_i$ under its signer's verification key: Is$e(H(m),g_2^{s_i}) = e(\sigma_i, g_2)$ ? - ...and thus identifies
$t$ valid sigshares - Aggregates the signature
$\sigma = H(m)^s$ via "interpolation in the exponent" from the$t$ valid sigshares (see next section).
- Collects as many
-
Shamir secret sharing7 of secret key
A good source for this is Berrut and Trefethen8.
Let
How can we recover or interpolate
We can use Lagrange's formula, which says:
\begin{align} \phi(X) &= \sum_{j\in T} \Ell_j^T(X) \phi(j)\label{eq:lagrange-sum} \end{align}
The
\begin{align} \Ell_j^T(X) &= \prod_{\substack{k\in T\\k\ne j}} \frac{X - k}{j - k}\label{eq:lagrange-poly} \end{align}
The key property of these polynomials is that
{: .info}
We are artificially restricting ourselves to evaluations of
As explained before, aggregating a
In our paper3, we adapt well-known, fast polynomial interpolation algorithms9 to do this in
First, I'll describe the naive, quadratic-time algorithm for aggregation. Then, I'll introduce the quasilinear-time algorithm, adapted for the "in the exponent" setting.
Having identified
For this, the aggregator computes all the
{: .error}
Computing a single
The final step consists of several exponentiations in
\begin{align}
\prod_{j\in T} \sigma_j^{\Ell_j^T(0)} &= \prod_{j\in T} \left(H(m)^{s_j}\right)^{\Ell_j^T(0)}\\
&= \prod_{j\in T} H(m)^{\Ell_j^T(0) s_j}\\
&= H(m)^{\sum_{j\in T}{\Ell_j^T(0) s_j}}\\
&= H(m)^{\sum_{j\in T}{\Ell_j^T(0) \phi(j)}}\\
&= H(m)^{\phi(0)} = H(m)^s = \sigma
\end{align}
This last step takes
This naive algorithm works quite well, especially at small scales, but the performance deteriorates fast, as computing the
{: .info}
The
The BLS threshold signature aggregation code was implemented using libff and libfqfft and is available on GitHub here. We used various optimizations using roots-of-unity to speed up this naive implementation.
This is going to get a bit mathematical, so hold on tight. Everything explained here is just a slight modification of the fast polynomial interpolation techniques explained in "Modern Computer Algebra"9.
We'll refer to
Notice that each Lagrange coefficient can be rewritten as a numerator divided by a denominator.
All
First, we define a vanishing polynomial
Similarly, let
Second, we rewrite the Lagrange polynomials using these vanishing polynomials.
\begin{align}
\Ell_j^T(X) &= \prod_{\substack{k\in T\\k\ne j}} \frac{X - k}{j - k}\\
&= \frac{\prod_{\substack{k\in T\\k\ne j}}(X - k)}{\prod_{\substack{k\in T\\k\ne j}}(j - k)}\\
&= \frac{V_{T\setminus\{j\}}(X)}{V_{T\setminus\{j\}}(j)}
\end{align}
As a result, we can rewrite the Lagrange coefficients as: \begin{align} \Ell_j^T(0) &= \frac{V_{T\setminus\{j\}}(0)}{V_{T\setminus\{j\}}(j)} \end{align}
Finally, we note that computing all numerators
-
Computing
$V_T(0)$ in$\Theta(t)$ time -
Dividing it by
$-j$ for all$j\in T$ , also in$\Theta(t)$ time
(It is a bit more difficult to) notice that the denominator
First, let us see what
If we apply the product rule of differentiation, we get:
\begin{align}
V_T'(x) &= \big[(x-1)(x-3)\big]'(x-9) + \big[(x-1)(x-3)\big](x-9)'\\
&= \big[(x-1)'(x-3) + (x-1)(x-3)'\big](x-9) + (x-1)(x-3)\\
&= \big[(x-3)+(x-1)\big](x-9) + (x-1)(x-3)\\
&= (x-3)(x-9) + (x-1)(x-9) + (x-1)(x-3)\\
&= V_{T\setminus\{1\}}(x) + V_{T\setminus\{3\}}(x) + V_{T\setminus\{9\}}(x)
\end{align}
In general, for any set
{: .info} We leave proving this as an exercise. The example above should give you enough intuition for why this holds.
Second, notice that
V_T'(3) &= 0 + (3-1)(3-9) + 0 = V_{T\setminus\{3\}}(1)\\
V_T'(9) &= 0 + 0 + (9-1)(9-3) + 0 = V_{T\setminus\{9\}}(1)
\end{align}
We can easily prove this holds for any set
&= V_{T\setminus\{j\}}(j) + \sum_{k \in T\setminus\{j\}} V_{T\setminus\{k\}}(j)\label{eq:vtprimeofj}\\
&= V_{T\setminus\{j\}}(j) + \sum_{k \in T\setminus\{j\}} 0\label{eq:vtprimeofj-zero}\\\
&= V_{T\setminus\{j\}}(j)
\end{align}
In other words, this means the denominator of the $j$th Lagrange coefficient
{: .info}
If you missed the transition from Equation \ref{eq:vtprimeofj} to Equation \ref{eq:vtprimeofj-zero} recall that
The road so far (to fast BLS threshold signature aggregation):
- Compute all numerators in
$O(t)$ time - Compute the vanishing polynomial
$V_T(X)$ in$O(t\log^2{t})$ time. How?- Build a tree!
- Each leaf stores a monomial
$(X-j)$ , for all$j\in T$ - The parent of two nodes stores the product of their children's polynomials
- As a result, the root will store
$V_T(X)$ - (See an example figure below for
$T=\{2,4,5,8,9,13,16,20\}$ .)
- Compute its derivative
$V_T'(X)$ in$O(t)$ time. How?- Rewrite
$V_T(X)$ in coefficient form as$V_T(X) = \sum_{i=0}^{|T|} c_i X^i$ - Then,
$V_T'(X) = \sum_{i=1}^{|T|} i \cdot c_i \cdot X^{i-1}$
- Rewrite
- Evaluate
$V_T'(X)$ at all points in$T$ . Let's see how!
{: .info}
Here we are computing
We want to evaluate
To understand how a multipoint eval works, first you must understand two things:
- The polynomial remainder theorem, which says
$\forall$ polynomials$\phi$ and$\forall j$ ,$\phi(j) = \phi(X) \bmod (X-j)$ , where$\bmod$ is the remainder of the division$\phi(X) / (X-j)$ .- We'll refer to these operations as "modular reductions."
- Recursion!
A multipoint eval computes
{: .info}
Each node
Each path in the tree corresponds to a sequence of modular reductions applied to
{: .info} My explanation here is in many ways inadequate. Although the figure should be of some help, you should see "Modern Computer Algebra", Chapter 109 and our paper3 for more background on polynomial multipoint evaluations.
By reasoning about the degrees of the polynomials involved in the tree, one can show that at most
In practice, a multipoint eval requires implementing fast polynomial division using FFT. Next, we explain how to avoid this and get a considerable speed-up.
If we pick the signer IDs to be roots of unity rather than
This is actually the route we take in our paper3, since a single FFT will be much faster than a polynomial multipoint evaluation which requires multiple polynomial divisions, which in turn require multiple FFTs. You can see the performance boost and scalability gained in the figure below.
{: .info}
The
Again, the code is available on GitHub here.
We showed how existing algorithms for polynomial interpolation can (and should) be used to speed up and scale BLS threshold signatures. In fact, these techniques can be applied to any threshold cryptosystem whose secret lies in a prime-order finite field with support for roots of unity.
Footnotes
-
SBFT: A Scalable and Decentralized Trust Infrastructure, by G. Golan Gueta and I. Abraham and S. Grossman and D. Malkhi and B. Pinkas and M. Reiter and D. Seredinschi and O. Tamir and A. Tomescu, in 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), 2019, [PDF]. ↩
-
Short Signatures from the Weil Pairing, by Boneh, Dan and Lynn, Ben and Shacham, Hovav, in Journal of Cryptology, 2004 ↩ ↩2
-
Towards Scalable Threshold Cryptosystems, by Alin Tomescu and Robert Chen and Yiming Zheng and Ittai Abraham and Benny Pinkas and Guy Golan Gueta and Srinivas Devadas, in 2020 IEEE Symposium on Security and Privacy (SP), 2020, [PDF]. ↩ ↩2 ↩3 ↩4
-
Introduction to Modern Cryptography, by Jonathan Katz and Yehuda Lindell, 2007 ↩
-
Pairings for cryptographers, by Steven D. Galbraith and Kenneth G. Paterson and Nigel P. Smart, in Discrete Applied Mathematics, 2008 ↩
-
Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme, by Boldyreva, Alexandra, in PKC 2003, 2002 ↩
-
How to Share a Secret, by Shamir, Adi, in Commun. ACM, 1979 ↩
-
Barycentric Lagrange Interpolation, by Berrut, J. and Trefethen, L., in SIAM Review, 2004 ↩
-
Fast polynomial evaluation and interpolation, by von zur Gathen, Joachim and Gerhard, Jurgen, in Modern Computer Algebra, 2013 ↩ ↩2 ↩3 ↩4
-
Introduction to Algorithms, Third Edition, by Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford, 2009 ↩