Library and benchmark program for Arctic and Shine

Ian Goldberg a8b6912320 README 8 kuukautta sitten
repro 477683a612 Reproduction script for Figure 7a in the paper 8 kuukautta sitten
src 6b436ac7c0 Use references, not copies, in the inner loop of gen 8 kuukautta sitten
Cargo.lock 1408d96080 Add Cargo.lock file 8 kuukautta sitten
Cargo.toml 55187fb080 Use itertools::combinations instead of rolling our own 8 kuukautta sitten
README.md a8b6912320 README 8 kuukautta sitten

README.md

Arctic: Lightweight, Stateless, and Deterministic Two-Round Threshold Schnorr Signatures

Code by Ian Goldberg, iang@uwaterloo.ca

This repository contains the library code, benchmark harness, and reproduction scripts for our paper:

Chelsea Komlo and Ian Goldberg. "Lightweight, Stateless, and Deterministic Two-Round Threshold Schnorr Signatures".

This code implements both Arctic (the deterministic two-round threshold Schnorr signature scheme) and Shine (the underlying verifiable pseudorandom secret sharing scheme).

We used Rust 1.73.0 to build and benchmark this code.

Running the benchmarks

There are two branches in this repository: the main branch is the single-threaded version, and the rayon branch is the multi-threaded version.

Single-threaded benchmarks (Figure 7a in the paper)

Build the code with:

  git checkout main
  cargo build --release

Then you can run individual benchmarks with:

  • ./target/release/arctic n t Cs nsigs

Where:

  • n is the total number of parties
  • t is the corruption threshold (if the adversary controls this many parties, they can recover the secret key and all security is lost)
  • Cs is the size of the signing coalition (the number of parties that participate to produce a signature).
  • nsigs is the number of signatures to generate.

It must be the case that nCs ≥ 2t-1, and t ≥ 2.

Sample command line:

./target/release/arctic 21 11 21 10

Sample output:

21 11 21 10 184756 43984.1 ± 49.2 45616.8 ± 47.2 134.8 ± 5.4

The output fields are:

  • 21 11 21 10: the four command-line arguments as above
  • 184756: the value δ = (n-1 choose t-1), which is the number of elements in the Shine private key.
  • 43984.1 ± 49.2: the time in microseconds for each of the Cs parties to compute Arctic's Sign1 (signing round 1) operation. The reported values are the mean and stddev over the Cs parties and the nsigs signatures.
  • 45616.8 ± 47.2: the time in microseconds for each of the Cs parties to compute Arctic's Sign2 (signing round 2) operation. The reported values are the mean and stddev over the Cs parties and the nsigs signatures.
  • 134.8 ± 5.4: the time in microseconds for a single party to compute Arctic's Combine (combining the parties' outputs into the final signature) operation. The reported values are the mean and stddev over the nsigs signatures.

To collect all the datapoints needed to reproduce the Arctic data in Figure 7a in our paper:

   cd repro
   ./repro-fig7a

This should take about 30–40 minutes, depending on your hardware. The values plotted in the figure are the sums of the means of Sign1, Sign2, and Combine, divided by 1000 to convert from microseconds to milliseconds. The stddevs plotted are the square roots of the sums of the squares of the stddevs of Sign1, Sign2, and Combine (and again converted to milliseconds), but they are mostly too small to see in the figure.

Multi-threaded benchmarks (Figure 7b in the paper)

Build the code with:

  git checkout rayon
  cargo build --release

You will also need to have numactl installed (even if you aren't running on a NUMA machine).

You will not get a significant performance boost from hyperthreading. If you have P physical cores on your CPU, this code assumes that in /proc/cpuinfo, the first P listed processors are all the "A sides" of your P physical cores. The code also assumes that these first P physical cores are all on NUMA node 0, if you have a NUMA machine. (These assumptions are quite likely to be true.)

Then you can run individual benchmarks with:

  • numactl -C cores -m0 ./target/release/arctic n t Cs nsigs

Where cores is a range of core numbers to use. If you want to use, for example, 18 physical cores on your first (or only) CPU, you would use numactl -C 0-17 -m0. The other arguments, and the output, are as in the single-threaded benchmarks above.

To collect all the datapoints needed to reproduce Figure 7b in our paper, decide how many cores you want to use for each of the datapoints. For example, if you have a four-core CPU, you might use 1 2 3 4, while if you have a 16-core CPU, you might use 1 2 3 4 6 8 10 12 14 16. Then, for example:

   cd repro
   ./repro-fig7b 1 2 3 4 6 8 10 12 14 16

Note that only Shine.Gen is parallelized, which is used in Arctic's Sign1 and Sign2, and is in fact the dominant cost of signing when δ is large. Key generation is not currently parallelized.