miden-crypto/benches/README.md
benches/README.mdRaw
1# Benchmarks
2
3## Miden VM Hash Functions
4In the Miden VM, we make use of different hash functions. Some of these are "traditional" hash functions, like `BLAKE3`, which are optimized for out-of-STARK performance, while others are algebraic hash functions, like `Rescue Prime`, and are more optimized for a better performance inside the STARK. In what follows, we benchmark several such hash functions and compare against other constructions that are used by other proving systems. More precisely, we benchmark:
5
6* **BLAKE3** as specified [here](https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blake3.pdf) and implemented [here](https://github.com/BLAKE3-team/BLAKE3) (with a wrapper exposed via this crate).
7* **SHA3** as specified [here](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf) and implemented [here](https://github.com/novifinancial/winterfell/blob/46dce1adf0/crypto/src/hash/sha/mod.rs).
8* **Poseidon** as specified [here](https://eprint.iacr.org/2019/458.pdf) and implemented [here](https://github.com/mir-protocol/plonky2/blob/806b88d7d6e69a30dc0b4775f7ba275c45e8b63b/plonky2/src/hash/poseidon_goldilocks.rs) (but in pure Rust, without vectorized instructions).
9* **Rescue Prime (RP)** as specified [here](https://eprint.iacr.org/2020/1143) and implemented [here](https://github.com/novifinancial/winterfell/blob/46dce1adf0/crypto/src/hash/rescue/rp64_256/mod.rs).
10* **Rescue Prime Optimized (RPO)** as specified [here](https://eprint.iacr.org/2022/1577) and implemented in this crate.
11* **Rescue Prime Extended (RPX)** a variant of the [xHash](https://eprint.iacr.org/2023/1045) hash function as implemented in this crate.
12
13### Comparison and Instructions
14
15#### Comparison
16We benchmark the above hash functions using two scenarios. The first is a 2-to-1 $(a,b)\mapsto h(a,b)$ hashing where both $a$, $b$ and $h(a,b)$ are the digests corresponding to each of the hash functions.
17The second scenario is that of sequential hashing where we take a sequence of length $100$ field elements and hash these to produce a single digest. The digests are $4$ field elements in a prime field with modulus $2^{64} - 2^{32} + 1$ (i.e., 32 bytes) for Poseidon, Rescue Prime and RPO, and an array `[u8; 32]` for SHA3 and BLAKE3.
18
19##### Scenario 1: 2-to-1 hashing `h(a,b)`
20
21| Function | BLAKE3 | SHA3 | Poseidon | Rp64_256 | RPO_256 | RPX_256 |
22| ------------------- | ------ | ------- | --------- | --------- | ------- | ------- |
23| Apple M1 Pro | 76 ns | 245 ns | 1.5 µs | 9.1 µs | 5.2 µs | 2.7 µs |
24| Apple M2 Max | 71 ns | 233 ns | 1.3 µs | 7.9 µs | 4.6 µs | 2.4 µs |
25| Amazon Graviton 3 | 108 ns | | | | 5.3 µs | 3.1 µs |
26| AMD Ryzen 9 5950X | 64 ns | 273 ns | 1.2 µs | 9.1 µs | 5.5 µs | |
27| AMD EPYC 9R14 | 83 ns | | | | 4.3 µs | 2.4 µs |
28| Intel Core i5-8279U | 68 ns | 536 ns | 2.0 µs | 13.6 µs | 8.5 µs | 4.4 µs |
29| Intel Xeon 8375C | 67 ns | | | | 8.2 µs | |
30
31##### Scenario 2: Sequential hashing of 100 elements `h([a_0,...,a_99])`
32
33| Function | BLAKE3 | SHA3 | Poseidon | Rp64_256 | RPO_256 | RPX_256 |
34| ------------------- | -------| ------- | --------- | --------- | ------- | ------- |
35| Apple M1 Pro | 1.0 µs | 1.5 µs | 19.4 µs | 118 µs | 69 µs | 35 µs |
36| Apple M2 Max | 0.9 µs | 1.5 µs | 17.4 µs | 103 µs | 60 µs | 31 µs |
37| Amazon Graviton 3 | 1.4 µs | | | | 69 µs | 41 µs |
38| AMD Ryzen 9 5950X | 0.8 µs | 1.7 µs | 15.7 µs | 120 µs | 72 µs | |
39| AMD EPYC 9R14 | 0.9 µs | | | | 56 µs | 32 µs |
40| Intel Core i5-8279U | 0.9 µs | | | | 107 µs | 56 µs |
41| Intel Xeon 8375C | 0.8 µs | | | | 110 µs | |
42
43Notes:
44- On Graviton 3, RPO256 and RPX256 are run with SVE acceleration enabled.
45- On AMD EPYC 9R14, RPO256 and RPX256 are run with AVX2 acceleration enabled.
46
47#### Instructions
48Before you can run the benchmarks, you'll need to make sure you have Rust [installed](https://www.rust-lang.org/tools/install). After that, to run the benchmarks for RPO and BLAKE3, clone the current repository, and from the root directory of the repo run the following:
49
50 ```
51 cargo bench hash
52 ```
53
54To run the benchmarks for Rescue Prime, Poseidon and SHA3, clone the following [repository](https://github.com/Dominik1999/winterfell.git) as above, then checkout the `hash-functions-benches` branch, and from the root directory of the repo run the following:
55
56```
57cargo bench hash
58```
59
60## Miden VM DSA
61
62We make use of the following digital signature algorithms (DSA) in the Miden VM:
63
64* **RPO-Falcon512** as specified [here](https://falcon-sign.info/falcon.pdf) with the one difference being the use of the RPO hash function for the hash-to-point algorithm (Algorithm 3 in the previous reference) instead of SHAKE256.
65* **RPO-STARK** as specified [here](https://eprint.iacr.org/2024/1553), where the parameters are the ones for the unique-decoding regime (UDR) with the two differences:
66 * We rely on Conjecture 1 in the [ethSTARK](https://eprint.iacr.org/2021/582) paper.
67 * The number of FRI queries is $30$ and the grinding factor is $12$ bits. Thus using the previous point we can argue that the modified version achieves at least $102$ bits of average-case existential unforgeability security against $2^{113}$-query bound adversaries that can obtain up to $2^{64}$ signatures under the same public key.
68
69
70
71### Comparison and Instructions
72
73#### Comparison
74
75
76##### Key Generation
77
78| DSA | RPO-Falcon512 | RPO-STARK |
79| ------------------- | :-----------: | :-------: |
80| Apple M1 Pro | 590 ms | 6 µs |
81| Intel Core i5-8279U | 585 ms | 10 µs |
82
83##### Signature Generation
84
85| DSA | RPO-Falcon512 | RPO-STARK |
86| ------------------- | :-----------: | :-------: |
87| Apple M1 Pro | 1.5 ms | 78 ms |
88| Intel Core i5-8279U | 1.8 ms | 130 ms |
89
90##### Signature Verification
91
92| DSA | RPO-Falcon512 | RPO-STARK |
93| ------------------- | :-----------: | :-------: |
94| Apple M1 Pro | 0.7 ms | 4.5 ms |
95| Intel Core i5-8279U | 1.2 ms | 7.9 ms |
96
97#### Instructions
98Before you can run the benchmarks, you'll need to make sure you have Rust [installed](https://www.rust-lang.org/tools/install). After that, to run the benchmarks, clone the current repository, and from the root directory of the repo run the following:
99
100 ```
101 cargo bench --bench dsa
102 ```