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 current safety ensures. We use a recognized trick to take action: multi-scalar multiplication, which is precisely designed to provide 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 is no such thing as a further 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 ingredient 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 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 cut 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 primary p and P an elliptic curve level, an abelian group ingredient; factors may 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 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
As a way 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, now we have 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 the entire factors on the similar time. For instance, you possibly can compute 3P + 3Q with solely 3 additions:
P + Q
2(P + Q)
2(P + Q) + (P + Q)
The NAF (non-adjacent type) is a strategy to encode the scalar with digits -1, 0, and 1 (as a substitute of the common bits 0 and 1). That is helpful as a result of level subtraction is as straightforward as a degree addition, and the NAF has fewer non-zero parts, 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). Now we have 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 commonly used the place a part of the factors are fastened, after which a bigger window is used for these and their desk may be precomputed prematurely as soon as, as a substitute of being computed on-the-fly. Nonetheless, that isn’t helpful for FROST: we’ll describe an alternate answer later on this publish.
Different algorithms akin to Pippenger and Bos-Coster may be extra environment friendly than the interleaved wNAF, however they’re extra advanced to implement. We’ll ultimately 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, now we have already used a variable-time multi-scalar multiplication implementation to confirm batches of Schnorr signatures multi function 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, through the second spherical of the FROST signing protocol, every occasion 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 last combination step, in any case signing individuals 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 now we have 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 outcome to an accumulator elliptic curve group ingredient. 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 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 variation solely touched just a few strains of code, however resulted in an over 50% velocity up on the excessive values of threshold and max doable individuals. The velocity 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 includes 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 would possibly 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 offered 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. 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 important, as a result of it brings the efficiency overhead of FROST nearer to those options, whereas retaining stronger safety properties.
Versus making breaking adjustments to the protocol itself, we use recognized optimization methods underneath the hood to hurry up our implementation. Making protocol adjustments requires re-analysis and new safety proofs, so such adjustments will not be executed frivolously. Fortunately, on this case, we are able to get one of the best 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.