Optimized assembly acceleration

[tarcieri]

Though we should definitely maintain a baseline profile which is pure Rust, it would be nice to be able to leverage optimized assembly implementations, and ideally formally verified ones which have been mechanically extracted from upstream sources.

One possible source of such assembly is the s2n-bignum project: https://github.com/awslabs/s2n-bignum

[spitters]

I wonder how it compares to Jasmin's https://github.com/haslab/libjbn

[tarcieri]

As a data point, the graviola crate has adopted assembly from s2n-bignum and seems to perform quite well: https://crates.io/crates/graviola

[dvdplm]

Graviola, assembly

Spent some time reviewing graviola today and hacked together some benchmarks. It's not immediately obvious to compare the two libraries, given crypto-bigint's focus on being an ergonomic and general purpose building block for a lot of different applications and compatibility with 32 bit CPUs.
Graviola on the other hand is implementing high level algorithms useful in a TLS setting. Low-level big integer arithmetic is decidedly low level and the code is not even exposed outside the crate.

Results

Montgomery arithmetic/graviola, convert to montgomery form
                        time:   [3.9583 µs 3.9615 µs 3.9644 µs]
                        change: [-0.2006% -0.0188% +0.1611%] (p = 0.85 > 0.05)
                        No change in performance detected.
Found 13 outliers among 100 measurements (13.00%)
  2 (2.00%) low severe
  5 (5.00%) low mild
  1 (1.00%) high mild
  5 (5.00%) high severe
Montgomery arithmetic/crypto-bigint, convert to montgomery form
                        time:   [85.582 µs 85.691 µs 85.806 µs]
                        change: [-0.1196% +0.1132% +0.3678%] (p = 0.41 > 0.05)
                        No change in performance detected.
Found 14 outliers among 100 measurements (14.00%)
  1 (1.00%) low severe
  6 (6.00%) low mild
  3 (3.00%) high mild
  4 (4.00%) high severe
Montgomery arithmetic/graviola, from montgomery
                        time:   [532.26 ns 532.84 ns 533.40 ns]
                        change: [-0.2177% -0.0238% +0.1529%] (p = 0.82 > 0.05)
                        No change in performance detected.
Found 12 outliers among 100 measurements (12.00%)
  6 (6.00%) low mild
  2 (2.00%) high mild
  4 (4.00%) high severe
Montgomery arithmetic/crypto-bigint, from montgomery
                        time:   [831.75 ns 832.72 ns 833.77 ns]
                        change: [-0.2612% +0.0554% +0.3777%] (p = 0.74 > 0.05)
                        No change in performance detected.
Found 16 outliers among 100 measurements (16.00%)
  9 (9.00%) high mild
  7 (7.00%) high severe
Benchmarking Montgomery arithmetic/graviola, exponentiation: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 9.6s, enable flat sampling, or reduce sample count to 50.
Montgomery arithmetic/graviola, exponentiation
                        time:   [1.9107 ms 1.9127 ms 1.9151 ms]
                        change: [+0.1467% +0.3646% +0.5915%] (p = 0.00 < 0.05)
                        Change within noise threshold.
Found 16 outliers among 100 measurements (16.00%)
  3 (3.00%) low mild
  2 (2.00%) high mild
  11 (11.00%) high severe
Benchmarking Montgomery arithmetic/graviola, exponentiation (fair): Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 9.6s, enable flat sampling, or reduce sample count to 50.
Montgomery arithmetic/graviola, exponentiation (fair)
                        time:   [1.9045 ms 1.9061 ms 1.9075 ms]
                        change: [-0.1639% -0.0246% +0.1237%] (p = 0.75 > 0.05)
                        No change in performance detected.
Found 13 outliers among 100 measurements (13.00%)
  1 (1.00%) low severe
  6 (6.00%) low mild
  3 (3.00%) high mild
  3 (3.00%) high severe
Montgomery arithmetic/crypto-bigint, exponentiation
                        time:   [3.3300 ms 3.3338 ms 3.3376 ms]
                        change: [-0.2623% -0.1045% +0.0439%] (p = 0.18 > 0.05)
                        No change in performance detected.

Although limited, the numbers speak pretty clear: the assembly routines used by graviola are faster.

For some cases, e.g. converting to Montgomery form, the comparison is unfair: constructing MontyParams in crypto-bigint does more work than graviola (e.g. it pre-calculates R^3 and a few other things that graviola doesn't).

Overall I think graviola is a quite "C-ish" code base, especially on the lower levels. As an application coder, I'd be quite anxious to use their low-level primitives as they stand today and am grateful for the type-system level reassurances of crypto-bigint (not a criticism of graviola: the code I benchmarked today is not part of a public API and not intended to be used by civilians).

The integration of s2n-bignum includes a fair bit of python code that writes rust to take care of clobbers and asm! options, and a number of extra macros and helper code.
Didn't love what I saw, and was somewhat surprised that there was that much scaffolding. Maybe it's all helpful/useful/necessary though? Certainly something to keep in mind before taking the plunge: using third party assembly routines is much more involved than adding another dependency to Cargo.toml.

In conclusion I think there are good performance gains to be had with assembly code, and perhaps even more appealing is the security boost from formally verified code. Assembly is easier to make constant time than Rust, there's simply no way around that. On the negative side, adopting assembly carries a substantial additional maintenance burden.

[tarcieri]

If there’s some way to reuse the s2n-bignum integrations from graviola, that’d be great, though I would agree Python isn’t ideal and I’d prefer the assembly be extracted using Rust-based transformations if possible.

Even if we don’t end up using code directly from graviola we could potentially compare to how it extracts assembly to see if our implementation is equivalent-or-better.