Native-WASM gateway

[burdges]

There is clearly an interest in using arkworks from WASM, so eventually there should be an interest in using arkworks from WASM with the computationally intensive parts required by verifiers running in native.

I suspect algebra exposes roughly the interface one wants here already. You'd maybe keep additions and most scalar arithmetic inside WASM, well assuming you pay some context switches, but then use native for scalar and multi-scalar multiplications on all groups (Edwards,G_1,G_2,G_T), batch normalization, subgroup checks, cofactor mults, G2 point preparation, Miller loops, and final exponentiation.

An interface like this could be provided by gateway curve types that themselves are polymorphic over the original curve implementation, so maybe a user imports the curve like:

type Bls12_377 = Bls12_WasmGate<bls12_377::Bls12_377,MyWasmBoundary>;

Under the hood, a type like Bls12_WasmGate might implement addition using Bls12 but then turns heavier calls into specific types for which it invokes some type satisfying some WasmBoundary trait. Or perhaps WASM boundaries are cheap enough for just doing addition native, which simplifies things.

There are verifiers like TIPP/MIPP for which this list leaves a logarithmic number of context switches, but that's likely acceptable. It's likely prover tooling like FFTs benefits from some special treatment, but this gets more complex and maybe kinda niche.

I think arkworks need not be distracted by this since it might depend somewhat upon the specific WASM deployment. It's maybe a good introductory project for an interested undergrad intern, or good GSoC student, or even for on-boarding someone. If anyone gets interested then we could provide support in the form of both grants and assistance with concrete wasm boundaries for benchmarks, etc.

---

Update: It appears at least some wasm boundaries do not require a context switch, so I suspect a first target could be the "simpler" thing that performs almost everything, ala addition, etc., using native code.

Update: As a rule, browsers implement their wasm boundary in C/C++ inside their JavaScript engine, so a question is the extent to which one should be C friendly here.

Update: Appears the wasm boundary in substrate serializes data. I hear SpiderMonkey has a more efficient wasm boundary that avoids serialization, but this sounds unimportant since elliptic curve operations consume considerable CPU. Algebra free serialization maybe suffices here.

[burdges]

Step 1. Pattern for opaque non-canonical de/serializer

At present, arkworks only serializes affine points never projective:
https://github.com/arkworks-rs/algebra/blob/master/ec/src/models/short_weierstrass_jacobian.rs#L754

We thus require non-canonical de/serialization with scary methods names:

pub trait NonCanonicalSerialize {
    fn noncanonical_serialized_size(&self) -> usize;
    fn noncanonical_serialize_uncompressed_unchecked<W: Write>(&self, writer: W) -> Result<(), SerializationError>
}

pub trait NonCanonicalDeserialize {
    fn noncanonical_deserialize_uncompressed_unchecked<R: Read>(reader: R) -> Result<Self, SerializationError>;
}

I’d love it if these were opaque somehow, but not sure exactly how yet, but scary names may suffice.

Step 2. Native-WASM Boundary

Initially, we’ll ignore any technical details about the native-WASM boundary, like passing slices the way Servo does, etc., well not sure anyone else gets that fancy. I suspect non-self methods never touch boundary, so maybe one simply this works:

pub use ark_std::io::{Read, Write};

/// Fork the boundary session freely with `Clone`, but within one boundary session you alternatively must `Write` and then `Read`. 
pub trait NativeBoundary : Clone {
    type Writer: Write;
    fn query(&mut self) -> &mut Writer;
    type Reader: Read;
    fn answer(&mut self) -> &mut Reader;
}

or however one handles the interior mutability. We’ll might want type-ish level builders here too, but not y, but et sure.

Individual wrapper types capture this boundary interface, although not sure if they work value level or use type level builders.

pub struct Bls12_Gateway<C,NB: NativeBoundary>(C,NB);

type Bls12_377 = Bls12_Gateway <bls12_377::Bls12_377,MyWasmBoundary>;

Step 3. Wire format

We'll employ some binary format, which sounds straightforward. I've not considered the details though.

Step 4. Wrapper types

We implement wrapper types upon many traits in ark-ec: We wrap PairingEngine itself obviously, but leave PairingEngine::{Fr,Fq,Fqe} propagate unwrapped. All other PairingEngine types propagate wrappers, ideally even Fqk, maybe delaying that one makes sense. All PairingEngine methods invoke boundary.

There are many methods that pass through directly for other types, but these slow methods deserve invoking the boundary:

ProjectiveCurve:
fn batch_normalization(v: &mut [Self])
fn batch_normalization_into_affine(v: &[Self]) -> VecSelf::Affine
fn mul<S: AsRef<[u64]>>(mut self, other: S) -> Self

AffineCurve:
fn mul<S: Into<<Self::ScalarField as PrimeField>::BigInt>>(&self, other: S) -> Self::Projective
fn mul_by_cofactor_to_projective(&self) -> Self::Projective
fn mul_by_cofactor(&self) -> Self
fn mul_by_cofactor_inv(&self) -> Self
(actually cofactor methods relevance depends upon the curve side, but maybe just do them)

Group:
fn mul<'a>(&self, other: &'a Self::ScalarField) -> Self

Also impls of Mul and MulAssign for these. It might makes more sense to directly impl traits on wrappers applied to model types that wrap parameters, but again not sure. See. https://github.com/arkworks-rs/algebra/blob/master/ec/src/models/short_weierstrass_jacobian.rs

We’ll share VariableBaseMSM and FixedBaseMSM with all other curves, but AffineCurve and/or maybe ProjectiveCurve could document itself as being a wrapper somehow, either that or use min_specialization rust-lang/rust#31844

Step 5. Execution

We need a second crate that deserializes and executes any method calles serialized by the above.

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

This issue now has a funding of 4000.0 DAI (4000.0 USD @ $1.0/DAI) attached to it.

• If you would like to work on this issue you can 'start work' on the Gitcoin Issue Details page.
• Want to chip in? Add your own contribution here.
• Questions? Checkout Gitcoin Help or the Gitcoin's Discord
• $1,471,364.17 more funded OSS Work available on the Gitcoin Issue Explorer

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

Work has been started.

These users each claimed they can complete the work by 265 years, 8 months from now.
Please review their action plans below:

1) ashutoshvarma has been approved to start work.

As per @burdges comment

1. Implement opaque non-canonical de/serializer for projective points
2. Try to implement WASM Boundary trait and Wrapper types
3. Implement crate for the execution of serialized method calls.
   2) bacdayhx has applied to start work (Funders only: approve worker | reject worker).

Okokkoko tôi làm đươc bạn tin ở tôi

Learn more on the Gitcoin Issue Details page.

[gitcoinbot]

@ashutoshvarma Hello from Gitcoin Core - are you still working on this issue? Please submit a WIP PR or comment back within the next 3 days or you will be removed from this ticket and it will be returned to an ‘Open’ status. Please let us know if you have questions!

• reminder (3 days)
• escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

[burdges]

We'll discuss this publicly while in progress but maybe on a fork, not here, not sure, so urban will give this a 100 day snooze.

[Pratyush]

I'd be happy to look over code/design and give feedback!

[jon-chuang]

So just to get a sense of what is going on, computationally expensive parts include pairings, scalar muls? If ignoring those, what's really left? Why not make the entire verification binary native and invoke it from a WASM call context?

I guess the idea is we want reusable native calls so as not to have separate native library files for each type of poly commit/instance size/proof system

[burdges]

Yes. It's flexibility and pain reduction. :)

A native groth16 verifier would only be slightly faster than four separate native calls for the multi-scalar multiplication, point preperation, Miller loop, and final exponentiation, even if each call demands allocation and serialization. You'd always batch verify groth16 of course, perhaps batch across many circuits, or even other SNARK types, and MIPP/TIPP enables many more options.

In polkadot, one deploys and upgrades block verification functions using WASM built from Rust (core+alloc), so arbitrary arkworks code should already work, with whatever speed penalty our WASM imposes. Any native calls we expose require indefinite support though, which makes adding native verifiers expensive. We'd become up a batch verifier graveyard!

A well designed JS/WASM boundary like in Servo avoids not only allocation and serialization, but even context switches. It's plausible you could expose only native field arithmetic in Servo and only observe a small penalty, due to no inlining and poor call optimizations. Ain't so clear anyone but Servo achieved this however, so making native field arithmetic problematic.

We're therefore left with exposing "only the slow parts" for whatever curves become popular. In particular, individual shards aka parachains could upgrade their batch verification logic without consulting us, although nuances around paritytech/polkadot#1656 (comment) remain.

We need some modularity over the WASM boundary, both for other projects and for our own sanity when improving the WASM boundary in future, which seemingly rules out adding #[cfg(..)]s in ark-ec and curves. We're therefore left with two options for implementing WASM boundary calls from arkworks:

• I suppose cargo patching in ark-ec and curves forks supports non-polymorphic code code that fixes its curve, but I think cargo patch always makes maintenance messy.
• Instead the type wrappers proposed here increase the total delta when porting over verifiers, but they ensure rustc complains more informatively when miss-used, and cargo patch remains an option for the desperate. :)

[burdges]

At this point @ashutoshvarma has written much of the wrapper types in https://github.com/ashutoshvarma/algebra/tree/wasm/ec/src/models/wrapped but we still need both an initial stub WASM boundary interface with a mechanism to call from higher level constructions, like the multi-scalar multiplication https://github.com/ashutoshvarma/algebra/tree/wasm/ec/src/msm

We could explore #[feature(min_specialization)] on nightly since it seemingly gives nice trait based interfaces, meaning stuff like bases: &[G] .. let bases: &[<G as Wrapped>::WrapTarget] = unsafe { &mut *bases }; or maybe you need unsafe { mem::transmute::<&[G],&[<G as Wrapped>::WrapTarget]> } there, not sure.

We've no associated type defaults so one cannot simply add a type GoNative: NativeBoundary = (); hook into ProjectiveCurve. I'd love this because then we'd simply test type_id::<G>() == type_id::<()>() to determine if we invoke the WASM boundary.

We do however have associated const defaults on stable so maybe add some const GO_NATIVE: Option<&'static dyn NativeBoundary> = None; hook into ProjectiveCurve perhaps. In this, VariableBaseMSM::multi_scalar_mul::<G: AffineCurve> begins roughly

impl VariableBaseMSM {
    pub fn multi_scalar_mul<G: AffineCurve>(
        bases: &[G],
        scalars: &[<G::ScalarField as PrimeField>::BigInt],
    ) -> G::Projective {
        if Some(boundary) = <<G as AffineCurve>::Projective as ProjectiveCurve>::GO_NATIVE {
            return boundary.call(PassVariableBaseMSM { bases, scalars });
        }
        ...

I've not quite thought through well enough what happens here though, maybe initially we just non-canonically serialize right here like I originally proposed above.

We'd do similarly if we ever need more higher level constructs to invoke across the boundary.

Thoughts?

[burdges]

@Pratyush We'd love to discuss @ashutoshvarma progess so far, which you'll find in his wasm-patch branch: https://github.com/ashutoshvarma/algebra/tree/wasm-patch We'll chat and telegram and maybe work out a time for a quick call.

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

Work for 4000.0 DAI (4000.0 USD @ $1.0/DAI) has been submitted by:

---

• Learn more on the Gitcoin Issue Details page
• Want to chip in? Add your own contribution here.
• Questions? Checkout Gitcoin Help or the Gitcoin's Discord
• $1,922,884.59 more funded OSS Work available on the Gitcoin Issue Explorer

[burdges]

We're paying Ashutosh Varma's gitcoin bounty now since the bounty covered only a first draft. Ashutosh will work for us as an intern for finishing this up. :)

[weikengchen]

Thanks a lot. Much appreciated!

[burdges]

Issues to discuss:

• Avoid passing precomputed tables.
• Arkworks exposes considerable details of windowed multiplication, so I'm curious where this comes up.

[Pratyush]

I think this is done?