by Deirdre Connolly, Conrado Gouvea
We optimized our implementation of FROST by upwards of fifty% over the trivial implementation, with out altering the protocol and due to this fact sustaining its current safety ensures. We use a identified trick to take action: multi-scalar multiplication, which is precisely designed to provide this sort of efficiency speedup.
Within the FROST threshold signing protocol, we carry out many elliptic curve operations for key era, signing, and signature verification. As a result of FROST is a Schnorr threshold signing scheme, the signature that’s produced is appropriate with single-party Schnorr signature verification. As such, there isn’t any further computation overhead to verifying signatures produced by FROST vs single-party.
Nevertheless, when performing FROST signing, signers should carry out a linear variety of group ingredient multiplications, proportionate to the variety of signers, as proven beneath (see the FROST specification for particulars).
If applied trivially, the computational overhead of FROST signing grows computationally costlier as extra events are concerned. When the variety of events is small, which is usually the case for threshold signing, (i.e. 2-out-of-3 or 3-out-of-5) this additional computational overhead is marginal. Nevertheless, we want to cut back the variety of costly elliptic curve operations wherever attainable.
Multi-scalar Multiplication?
Within the context of elliptic curves, a scalar multiplication is written as kP the place okay is an integer mod a main p and P an elliptic curve level, an abelian group ingredient; factors may be added or subtracted. With solely these operations it’s attainable to compute kP. The naïve method can be to easily add okay copies of P along with k-1 additions, however there are extra environment friendly approaches that take a lot of additions within the order of log(okay). These undergo the bits of the scalar, doubling the purpose for each bit and including the purpose P if the bit is 1. For instance, 5P may be computed with 3 additions:
2P = P + P
4P = 2P + 2P
5P = 4P + P
So as to pace up FROST signing, we should do extra environment friendly level multiplications with respect to a number of variable base factors, which is named multi-scalar multiplication. It consists of computing the sum aP + bQ + … + dS for some variety of factors and scalars. It may be naïvely computed by doing every scalar multiplication after which summing all of them up. Fortunately, we’ve got a number of algorithms at our disposal that may do higher.
Algorithms to Optimize Multi-scalar Multiplication
A lot of the multi-scalar multiplication algorithms depend on the statement that you simply do some operations on all the factors on the identical time. For instance, you may compute 3P + 3Q with solely 3 additions:
P + Q
2(P + Q)
2(P + Q) + (P + Q)
Interleaved wNAF
The NAF (non-adjacent type) is a strategy to encode the scalar with digits -1, 0, and 1 (as an alternative of the common bits 0 and 1). That is helpful as a result of level subtraction is as straightforward as some extent addition, and the NAF has fewer non-zero parts, which pace up the purpose multiplication algorithm (recall that there’s a level addition for each non-zero digit). The wNAF is a windowed model of the NAF (e.g. a 2NAF can have digits -3, -1, 0, 1, and three). We’ve been utilizing an interleaved width-w non-adjacent type in our scalar implementation to assist multi-scalar multiplication. We pre-populate a lookup desk of multiples of the factors being multiplied (e.g. P, 3P and 5P for 3NAF), that are then used so as to add the non-zero phrases of the scalar being multiplied within the non-adjacent type.
Interleaved wNAF is usually used the place a part of the factors are mounted, after which a bigger window is used for these and their desk may be precomputed upfront as soon as, as an alternative of being computed on-the-fly. Nevertheless, that’s not helpful for FROST: we’ll describe another answer later on this submit.
Different algorithms similar to Pippenger and Bos-Coster may be extra environment friendly than the interleaved wNAF, however they’re extra advanced to implement. We are going to finally look into them. (We principally went for interleaved wNAF as a result of we already had an implementation of it utilized in batch verification!)
Optimizing FROST
In our FROST libraries, we’ve got already used a variable-time multi-scalar multiplication implementation to confirm batches of Schnorr signatures multi functional go. We now describe how we used this multi-scalar multiplication implementation to hurry up how signers generate the group dedication R when performing the second spherical of FROST signing.
As a reminder, in the course of the second spherical of the FROST signing protocol, every occasion computes the group dedication based mostly on the nonce commitments despatched by every i-th signer within the first spherical of the signing protocol. This group dedication can be computed by the coordinator within the remaining mixture step, in any case signing contributors have created and despatched their signature shares.
Computing this group dedication is a ripe alternative to make use of multi-scalar multiplication, as a result of we’ve got to compute a multiplication of various elliptic curve ingredient bases (the nonce commitments from every participant) by a various scalar (the binding issue). Beforehand, we might do a variable-base scalar multiplication for every participant, after which add the consequence to an accumulator elliptic curve group ingredient. Nevertheless, we will restructure our algorithm to build up the hiding commitments, and save the variable base multi-scalar multiplication of the binding commitments and the binding issue scalar to the top, in a single shot. Then we add the consequence to the accumulator, to consequence within the full group dedication.
As a result of we already had a variable time multi-scalar multiplication implementation in our code base, this variation solely touched a couple of strains of code, however resulted in an over 50% pace up on the excessive values of threshold and max attainable contributors. The pace up was seen within the second spherical computation and the ultimate mixture step, as each are computing the group dedication.
This optimization is compliant with the FROST specification, because the change to make use of multi-scalar multiplication solely includes a rearrangement of equation phrases within the era of the group dedication. The pace up is obtainable with any multi-scalar multiplication implementation, variable-time or constant-time. The underlying elliptic curve group software program implementation utilized by your FROST implementation may have already got this optimization accessible.
Evaluating Optimized FROST to FROST Variants
There are actually a number of totally different variants of FROST within the literature, all that supply speedups with respect to the overhead of the group dedication. Notably, FROST2 permits for fixed overhead when computing the nonce, and one other variant introduced within the context of ROAST improves on the bandwidth that’s despatched from the coordinator to every signing participant. Nevertheless, FROST2 achieves weaker safety than FROST, and the variant within the ROAST paper has not been demonstrated to have any stronger notion of safety (i.e. TS-UF-1 and better) apart from unforgeability. In consequence, we selected to maintain the CFRG draft and our implementation pinned to the unique FROST design.
Utilizing multi-scalar multiplication to optimize computing the group dedication over the complete execution of the FROST protocol is critical, as a result of it brings the efficiency overhead of FROST nearer to those options, whereas retaining stronger safety properties.
Versus making breaking modifications to the protocol itself, we use identified optimization methods below the hood to hurry up our implementation. Making protocol modifications requires re-analysis and new safety proofs, so such modifications will not be finished calmly. Fortunately, on this case, we will get the perfect of each worlds: efficiency that’s higher than the trivial implementation of FROST (i.e. from linear overhead within the variety of signers to shut to fixed), with out having to compromise on the safety or flexibility of the scheme.
These optimizations are actually accessible in frost-core, frost-ed25519, frost-ed448, frost-p256, frost-ristretto255, and frost-secp256k1 as of 0.3.0 on crates.io!