Strahn here! Our developers just verifiably achieved a 1.9 to 2x speedup on Halo2 batched MSM over industry standard pasta_curves crate!
Testing on standard M4:
| k |
pasta_curves |
fuji batch |
Speedup |
| 8 |
7.8 ms |
8.3 ms |
none (cache warmup overhead) |
| 11 |
34.6 ms |
17.0 ms |
2.0x |
| 12 |
66.9 ms |
33.4 ms |
2.0x |
| 13 |
110.5 ms |
59.3 ms |
1.9x |
| 14 |
223.2 ms |
117.8 ms |
1.9x |
Check it out: https://github.com/StrahnIo/GoldenDelicious and https://github.com/StrahnIo/FUJI
We used NEON/SIMD registers as a scratchpad to parallelise operations across four execution ports on Apple CPUs, sharing computations over the same G-base to speed everything up!
Sean Bowe on X: "@strahnio We'd love to look at that! Tachyon also uses the Pasta curves and most of the cost during proving remains MSMs. Orchard/Ironwood proofs using halo2 spend a lot of time in FFTs, but Ragu (for Tachyon) doesn't depend on those, just MSMs." / X )
He says that Tachyon ALSO uses a ton of MSM, even more than Orchard/Halo2, meaning this would accelerate Tachyon EVEN MORE!
We are waiting for Sean’s review. In the meantime, should we apply for a grant to expand this to mobile A-series chips in iPhones to make Zcash transactions, both Orchard and Tachyon, MASSIVELY faster?
X: https://x.com/strahnio/status/2078786280624914685
@artkor
5 Likes
We have decided to amend our original grant from (Grant Application: Tensor-Core Accelerated Proving for Orchard/Ironwood - #13 by strahncryptography) to instead use this to accelerate proving on mobile CPUs with the desktop processor results as a proof of concept.
1 Like
After a bug crisis on some scalars, we have made it public again; but it is currently taking a small performance hit. Regardless, it easily hits a 30%+ performance gain on k=11 and 50%+ on k=12! We are working on fixing the NEON register corruption bug ASAP
Great looking forward to it, Congrats on the speedup, especially since assembly level optimizations are quite hard, the grant is mainly for Apple devices right?
Also well I’m kinda worried about the assembly level optimization it’ll be quite hard to maintain especially if new chips come around, we’ll that just the though I had, new chips might require changes too.
Anyway great proposal
Actually, that’s the GREAT thing about Apple. They only release one chipset a year or so, and it’s almost always backwards compatible (ARM ISA spec)
So unlike Intel and other Android chips which are impossible to optimise, a single optimisation covers 10-30% of the entire ecosystem at once. Device uniformity means benchmarks also replicate almost bit by bit and millisecond by millisecond.
oh, that’s really convenient, it makes the whole thing easier to maintain. Good luck with the proposal