Great work.

For the traits, let's rebase this on top of #309 after #318 is merged in. We should be able to make Icicle a new backend for Hyrax exclusively without touching other traits.

Currently some of the e2e tests are failing due to failed Hyrax Proof verification. Initially investigating this it seems the msm results of icicle and jolt_core::msm::VariableBase::msm differ. After comparing the results of the msm variants with icicle_msm, it appears the results of icicle_msm and msm_bigint match but differ from the results of msm_u64 and msm_binary.

On Sam Rags advice I compared the results icicle_msm() and msm() for random distribtutions of different scalars as following:

• scalars all 0
• scalars randomly {0, 1}
• scalars randomly {0, ... 2^9}
• scalars randomly {0, 2^63}
• scalars randomly {0, 2^253}

The results of these tests match my earlier attempts at debugging (the result of icicle matches msm_bigint and is different for the other msm_vairants). However across 10 runs the results of icicle_msm() and msm_bigint() were different 2 times. My suspicion is that is why the e2e tests are inconsistently failing.

Pinging the icicle team for more help: @jeremyfelder @LeonHibnik @DmytroTym for visibility

It's quite possible this is a bug in the custom Jolt MSMs. We use the same function in prove and verify so I don't think it would cause a verification error on the opening proofs.

I've isolated a failing test case (below) where msm_bigint() is different from icicle_msm(). This is for msm_length = 3 on bn254 G1. I compared the output of msm_bigint, icicle_msm to arkworks_msm as a baseline. Icicle_msm differs from both msm_bigint and arkworks_msm which match.

scalars:
[BigInt([9016117505638758543, 352751388875653018, 14946620785396285244, 211688466542070544]), BigInt([9016117505638758543, 352751388875653018, 14946620785396285244, 211688466542070544]), BigInt([9016117505638758543, 352751388875653018, 14946620785396285244, 211688466542070544])]

bases:
[(7688067217989994385175370005327028282099909322677106416431281707406319639423, 7687918639911294339882576580611551419932980906448618049918745820988988940544), (7688067217989994385175370005327028282099909322677106416431281707406319639423, 7687918639911294339882576580611551419932980906448618049918745820988988940544), (7688067217989994385175370005327028282099909322677106416431281707406319639423, 7687918639911294339882576580611551419932980906448618049918745820988988940544)]

Icicle_msm:
G1Projective { 8762571254902059470736832095824632961938556720240244842612617999683902078046, 10092157708131004888930512565411407719316059820784025059444099681630462320054, 11168217204278712267950517896802450080070912830806623791345428292444699192104}

msm_bigint/arkworks_msm:
G1Projective{ 8556297242478855084502684745245972997742728399108653613517190125786236661471, 8050224918617737447598769520885148623820108452568297893643817103436495388203, 11360129327871628975120284343765061813104420509947328992138115752583312160988 }

For reference we had some conversion logic between ark_ff::PrimeField and ff::PrimeField back when we were using Spartan2 externally: #188

Current perf on an H100 accelerates sha2-chain 40% E2E for {Zeromorph, HyperKZG}. Currently slows down hyrax due to the tiny MSMs and call overhead.

Remaining waste:

• max_num_bits check at the beginning of VariableBaseMSM::msm becomes a bottleneck for opening proofs
• The GPU scalar conversion could be faster and is done repeatedly to save plumbing, but could be amortized
• Zeromorph and HyperKZG opening proofs are unoptimized, particularly w.r.t univariate polynomial math. Theoretically could use icicle here, although feels like a heavy hammer

hey, I tried this PR and built successfully but I don't see it use any of my GPU

I've isolated a failing test case (below) where msm_bigint() is different from icicle_msm(). This is for msm_length = 3 on bn254 G1. I compared the output of msm_bigint, icicle_msm to arkworks_msm as a baseline. Icicle_msm differs from both msm_bigint and arkworks_msm which match.

scalars: [BigInt([9016117505638758543, 352751388875653018, 14946620785396285244, 211688466542070544]), BigInt([9016117505638758543, 352751388875653018, 14946620785396285244, 211688466542070544]), BigInt([9016117505638758543, 352751388875653018, 14946620785396285244, 211688466542070544])]

bases: [(7688067217989994385175370005327028282099909322677106416431281707406319639423, 7687918639911294339882576580611551419932980906448618049918745820988988940544), (7688067217989994385175370005327028282099909322677106416431281707406319639423, 7687918639911294339882576580611551419932980906448618049918745820988988940544), (7688067217989994385175370005327028282099909322677106416431281707406319639423, 7687918639911294339882576580611551419932980906448618049918745820988988940544)]

Icicle_msm: G1Projective { 8762571254902059470736832095824632961938556720240244842612617999683902078046, 10092157708131004888930512565411407719316059820784025059444099681630462320054, 11168217204278712267950517896802450080070912830806623791345428292444699192104}

msm_bigint/arkworks_msm: G1Projective{ 8556297242478855084502684745245972997742728399108653613517190125786236661471, 8050224918617737447598769520885148623820108452568297893643817103436495388203, 11360129327871628975120284343765061813104420509947328992138115752583312160988 }

Note: Arkworks and icicle will generate different projective points, but when compared in affine, arkworks and icicle will be the same. Also the icicle result should still contribute to a correct proof.

Also, when converting, do not use bigint conversion for scalars. transmute the scalars into the icicle type instead, it works better and is faster.

Edit: the checks fail because the check environment does not have cuda, this should be alleviated or worked around by using mock structs

Current perf on an H100 accelerates sha2-chain 40% E2E for {Zeromorph, HyperKZG}. Currently slows down hyrax due to the tiny MSMs and call overhead.

Remaining waste:

* `max_num_bits` check at the beginning of `VariableBaseMSM::msm` becomes a bottleneck for opening proofs

* The GPU scalar conversion could be faster and is done repeatedly to save plumbing, but could be amortized

* Zeromorph and HyperKZG opening proofs are unoptimized, particularly w.r.t univariate polynomial math. Theoretically could use icicle here, although feels like a heavy hammer

Can we do something about the hyrax slowdown? Perhaps batch the msms to reduce call overhead? What is the difference between the raw calculation of the msm for hyrax on the GPU vs CPU (excl data transmission)?