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 subsequently sustaining its present safety ensures. We use a identified trick to take action: multi-scalar multiplication, which is precisely designed to present this type 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 extra computation overhead to verifying signatures produced by FROST vs single-party.
Nonetheless, when performing FROST signing, signers should carry out a linear variety of group aspect multiplications, proportionate to the variety of signers, as proven beneath (see the FROST specification for particulars).
If carried out 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 further computational overhead is marginal. Nonetheless, we want to scale 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 primary p and P an elliptic curve level, an abelian group aspect; factors will 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 quite 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 will be computed with 3 additions:
2P = P + P
4P = 2P + 2P
5P = 4P + P
With the intention 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 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 remark that you just do some operations on all the factors on the identical time. For instance, you’ll be able to compute 3P + 3Q with solely 3 additions:
P + Q
2(P + Q)
2(P + Q) + (P + Q)
Interleaved wNAF
The NAF (non-adjacent kind) is a method 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 simple as a degree addition, and the NAF has fewer non-zero components, 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 kind 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 kind.
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 will be precomputed upfront as soon as, as an alternative of being computed on-the-fly. Nonetheless, that’s not helpful for FROST: we’ll describe an alternate answer later on this submit.
Different algorithms akin to Pippenger and Bos-Coster will be extra environment friendly than the interleaved wNAF, however they’re extra advanced to implement. We are going to finally look into them. (We largely 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 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 celebration computes the group dedication primarily based on the nonce commitments despatched by every i-th signer within the first spherical of the signing protocol. This group dedication can also be computed by the coordinator within the closing combination 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 to compute a multiplication of various elliptic curve aspect bases (the nonce commitments from every participant) by a various scalar (the binding issue). Beforehand, we’d do a variable-base scalar multiplication for every participant, after which add the end result to an accumulator elliptic curve group aspect. Nonetheless, we are able to 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 end result to the accumulator, to end result within the full group dedication.
As a result of we already had a variable time multi-scalar multiplication implementation in our code base, this modification solely touched just a few 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 combination 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 entails a rearrangement of equation phrases within the era of the group dedication. The pace up is on the market with any multi-scalar multiplication implementation, variable-time or constant-time. The underlying elliptic curve group software program implementation utilized by your FROST implementation would possibly have already got this optimization accessible.
Evaluating Optimized FROST to FROST Variants
There at the moment are a number of completely 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. Nonetheless, 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) aside from unforgeability. Consequently, 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 total execution of the FROST protocol is critical, as a result of it brings the efficiency overhead of FROST nearer to those alternate options, whereas retaining stronger safety properties.
Versus making breaking modifications to the protocol itself, we use identified optimization tips beneath the hood to hurry up our implementation. Making protocol modifications requires re-analysis and new safety proofs, so such modifications will not be achieved evenly. Fortunately, on this case, we are able to get the most effective 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 at the moment are accessible in frost-core, frost-ed25519, frost-ed448, frost-p256, frost-ristretto255, and frost-secp256k1 as of 0.3.0 on crates.io!
