frost/performance.md

FROST Performance

What is FROST?

FROST is a threshold Schnorr signature scheme invented by Chelsea Komlo (researcher at the Zcash Foundation) and Ian Goldberg, and in the process of becoming an IETF RFC. Threshold signatures allow a private key being split into shares given to multiple participants, allowing a subgroup of them (e.g. 3 out of 5, or whatever threshold specified at key generation) to generate a signature that can be verified by the group public key, as if it were signed by the original unsplit private key. It has many applications such as allowing multiple entities to manage a cryptocurrency wallet in a safer and more resilient manner.

Currently, the RFC is close to completion, and we also completed a Rust implementation of all ciphersuites specified in the RFC, and are now doing final cleanups and improvements prior to the first release of the crates (which will soon be audited).

Benchmarking and investigating the Aggregate step

When we presented FROST at Zcon 3, we were asked how FROST performed in larger settings, such as a 667-of-1000 signers. (This is motivated by a mechanism proposed by Christopher Goes for bridging Zcash with other ecosystems using FROST.) We set out to benchmark our Rust implementation, and were a bit surprised about one particular step: “Aggregate”.

The FROST scheme can be split into steps. The first one is Key Generation, which only needs to be done once, while the rest are carried out each time the group wishes to generate a new signature. In Round 1, the participant generates commitments which are broadcast to all other participants via a Coordinator. In Round 2, using these commitments and their respective key shares generated during Key Generation, they produce a signature share which is sent to the Coordinator. Finally, the Coordinator carries out the final step, Aggregate, which produces the final signatures from all the signatures shares received.

The benchmark for the Ristretto255 suite looked like the following. (Benchmarks were run on an AMD Ryzen 9 5900X 3.7GHZ, Ubuntu 22.04, Rust 1.66.0.)

(Note that Round 1 and 2 timings in this post refer to per-signer timings, while Key Generation and Aggregate are performed by the Coordinator.)

It was expected that the timings would increase with the larger number of participants (with the exception of Round 1, which does not depend on that number), but the Aggregate timings appeared too high, surpassing 400ms for the 667-of-1000 case (which may not seem much but it’s unusual for a signing procedure).

We intended to investigate this but it was not necessary. Coincidentally, while the RFC was in the last call for feedback, Tim Ruffing pointed out that Aggregate can be sped up significantly. Originally, it was specified that each share received from the participants should be verified (each signature share can be verified separately to ensure it is correct) and then aggregated. Tim’s observation is that the shares can be simply aggregated and the final signature verified with the group public key. If the verification fails, then it’s possible to find which participant generated an incorrect share by verifying them one by one (if desired). This greatly speeds up the case where all shares are correct, which should be the most common.

This is how the Ristretto255 timings look like with that optimization implemented:

Now the Aggregate performance is very similar to the Round 2 step, which makes sense since they have a very similar structure.

Here’s the Aggregate performance comparison for all ciphersuites, in three different scenarios:

Examining overall performance

With the benchmark machinery in place (we used criterion.rs) we can provide benchmark results for all supported ciphersuites in different scenarios. These all use the optimization described above.

The same data in table format:

ed448

	Key Generation with Dealer	Round 1	Round 2	Aggregate
2-of-3	1.56	0.51	0.75	1.39
7-of-10	4.65	0.53	2.36	2.88
67-of-100	46.05	0.52	21.04	20.37
667-of-1000	693.45	0.53	211.68	197.00

ristretto255

	Key Generation with Dealer	Round 1	Round 2	Aggregate
2-of-3	0.24	0.08	0.13	0.22
7-of-10	0.71	0.08	0.42	0.47
67-of-100	7.61	0.08	3.77	3.40
667-of-1000	179.43	0.08	38.32	32.54

p256

	Key Generation with Dealer	Round 1	Round 2	Aggregate
2-of-3	0.56	0.18	0.33	0.58
7-of-10	1.71	0.19	1.08	1.24
67-of-100	16.51	0.18	10.03	9.38
667-of-1000	206.85	0.19	97.49	90.82

secp256k1

	Key Generation with Dealer	Round 1	Round 2	Aggregate
2-of-3	0.26	0.09	0.15	0.25
7-of-10	0.78	0.09	0.48	0.52
67-of-100	7.50	0.09	4.41	3.82
667-of-1000	123.74	0.09	46.11	37.48

ed25519

	Key Generation with Dealer	Round 1	Round 2	Aggregate
2-of-3	0.24	0.08	0.12	0.22
7-of-10	0.73	0.08	0.39	0.45
67-of-100	7.70	0.08	3.64	3.28
667-of-1000	181.45	0.08	36.92	31.88

The time-consuming part of each step is elliptic curve point multiplication. Here’s a breakdown:

• Key Generation with Trusted Dealer:

  • One base point multiplication to derive the group public key from the group private key;
  • One base point multiplication per MIN_PARTICIPANTS to derive a commitment for each polynomial coefficient;
  • One base point multiplication per MAX_PARTICIPANTS to derive their individual public keys.

• Round 1:

  • Two base point multiplications to generate commitments to the pair of nonces.

• Round 2:

  • One point multiplication per NUM_PARTICIPANTS to compute the group commitment.

• Aggregate:

  • One point multiplication per NUM_PARTICIPANTS to compute the group commitment. If the Coordinator is also a participant, they could reuse the value from Round 2, but we didn’t assume that in our benchmark (and our implementation does not support this for now);
  • One base point multiplication and one general point multiplication to verify the aggregated signature;
  • Verifying all shares (i.e. in our original approach, or to find a corrupt signer if the aggregated signature failed) additionally requires one base point multiplication and two general point multiplications per NUM_PARTICIPANTS to actually verify the share.