Timing side channel in Groth16 proof generation
Description
According to the benchmarks (cargo bench -p penumbra-bench --features=parallel -- 'spend proving'), SpendProofs are approximately 6ms faster (341ms versus 334ms) when proofs are generated for them with nonzero versus zero amount.
Unmodified SpendProof benchmark:
Running benches/spend.rs (target/release/deps/spend-44899f51b8c07546)
Gnuplot not found, using plotters backend
Benchmarking spend proving: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 34.9s, or reduce sample count to 10.
spend proving time: [340.02 ms 341.16 ms 342.66 ms]
Found 5 outliers among 100 measurements (5.00%)
3 (3.00%) high mild
2 (2.00%) high severe
Number of constraints: 34630When modifying the SpendProof benchmark to use zero amount,
diff --git a/crates/bench/benches/spend.rs b/crates/bench/benches/spend.rs
index 474f1101e..551537689 100644
--- a/crates/bench/benches/spend.rs
+++ b/crates/bench/benches/spend.rs
@@ -23,7 +23,7 @@ fn prove(r: Fq, s: Fq, public: SpendProofPublic, private: SpendProofPrivate) {
}
fn spend_proving_time(c: &mut Criterion) {
- let value_to_send = Value::from_str("1upenumbra").expect("valid value");
+ let value_to_send = Value::from_str("0upenumbra").expect("valid value");
let seed_phrase = SeedPhrase::generate(OsRng);
let sk_sender = SpendKey::from_seed_phrase_bip44(seed_phrase, &Bip44Path::new(0)); Running benches/spend.rs (target/release/deps/spend-44899f51b8c07546)
Gnuplot not found, using plotters backend
Benchmarking spend proving: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 33.9s, or reduce sample count to 10.
spend proving time: [334.04 ms 334.80 ms 335.67 ms]
change: [-2.3289% -1.8650% -1.4490%] (p = 0.00 < 0.05)
Performance has improved.
Found 5 outliers among 100 measurements (5.00%)
3 (3.00%) high mild
2 (2.00%) high severe
Number of constraints: 34630Impact
While the variance may be particularly high for SpendProofs on account of the underconstraints for dummy spends, Arkworks' implementation of Groth16 proof generation may be nonconstant time in general. This may leak witness values if there are situations where a software agent will predictably initiate proving in response to network traffic (such as liquidity providers updating prices or wallet software automatically redeeming swap claims).
Recommendations
Evaluate whether it is possible for upstream Arkworks to guarantee that proof-generation time does not depend on witness values.
Remediation
This issue has been acknowledged by Penumbra Labs, and is considered outside of the threat model.