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 recognized 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 suitable 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 component multiplications, proportionate to the variety of signers, as proven under (see the FROST specification for particulars).
If applied trivially, the computational overhead of FROST signing grows computationally dearer as extra events are concerned. When the variety of events is small, which is often the case for threshold signing, (i.e. 2-out-of-3 or 3-out-of-5) this additional computational overhead is marginal. Nevertheless, we wish to scale back the variety of costly elliptic curve operations wherever doable.
Within the context of elliptic curves, a scalar multiplication is written as kP the place okay is an integer mod a major p and P an elliptic curve level, an abelian group component; factors will be added or subtracted. With solely these operations it’s doable to compute kP. The naïve method could be to easily add okay copies of P along with k-1 additions, however there are extra environment friendly approaches that take plenty 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
In an effort to velocity up FROST signing, we should do extra environment friendly level multiplications with respect to a number of variable base factors, which known as 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 the entire 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)
The NAF (non-adjacent type) is a solution 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 some extent addition, and the NAF has fewer non-zero components, which velocity 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 have now been utilizing an interleaved width-w non-adjacent type in our scalar implementation to help 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 commonly used the place a part of the factors are fastened, 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. Nevertheless, that isn’t helpful for FROST: we are going to describe another resolution later on this put up.
Different algorithms resembling Pippenger and Bos-Coster will be extra environment friendly than the interleaved wNAF, however they’re extra advanced to implement. We’ll 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!)
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, throughout 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 ultimate mixture step, in spite of everything signing members 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 component 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 outcome to an accumulator elliptic curve group component. Nevertheless, 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 tip, in a single shot. Then we add the outcome to the accumulator, to outcome within the full group dedication.
As a result of we already had a variable time multi-scalar multiplication implementation in our code base, this alteration solely touched just a few traces of code, however resulted in an over 50% velocity up on the excessive values of threshold and max doable members. The velocity 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 entails a rearrangement of equation phrases within the era of the group dedication. The velocity 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 obtainable.
Evaluating Optimized FROST to FROST Variants
There at the moment are a number of totally different variants of FROST within the literature, all that provide 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 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 recognized optimization tips underneath the hood to hurry up our implementation. Making protocol modifications requires re-analysis and new safety proofs, so such modifications are usually not accomplished evenly. Fortunately, on this case, we are able to 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.