burdges
commented
3 years ago 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]) -> Vec
AffineCurve:
fn mul<S: Into<
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 https://github.com/rust-lang/rust/issues/31844
Step 5. Execution
We need a second crate that deserializes and executes any method calles serialized by the above.
gitcoinbot
Pratyush
jon-chuang
weikengchen
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:
Under the hood, a type like
Bls12_WasmGatemight implement addition usingBls12but then turns heavier calls into specific types for which it invokes some type satisfying someWasmBoundarytrait. 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.