ark-ed-on-bls12-381-bandersnatch

• #772 (ark-ff) Implementation of mul method for BigInteger.
• #794 (ark-ff) Fix wasm compilation.
• #837 (ark-serialize) Fix array deserialization panic.
• #845 (Algebra) Implementation of mul method for DenseMultilinearExtension<F> * F.

Breaking changes

• #577 (ark-ff, ark-ec) Add AdditiveGroup, a trait for additive groups (equipped with scalar field).
• #593 (ark-ec) Change AffineRepr::xy() to return owned values.
• #633 (ark-ec) Generic pairing implementation for the curves from the BW6 family.
• #659 (ark-ec) Move auxiliary parity function from ark_ec::hashing::curve_maps::swu to ark_ec::hashing::curve_maps.
• #746 (ark-ec) Refactor fixed-based batch multiplication:
  • Move functionality to ScalarMul::batch_mul and ScalarMul::batch_mul_with_preprocessing.
  • Create new struct BatchMulPreprocessing for to hold preprocessed powers of base.
    • Provide high-level constructor new that calculates window size and scalar size.
    • Provide low-level constructor with_window_and_scalar_size that allows setting these parameters.
    • Make windowed_mul a private method of BatchMulPreprocessing.
    • Rename get_mul_window_size to compute_window_size and make it private.
• #748 (ark-ff) Add FromStr for BigInteger.
• #756 (ark-ec) Require Neg, Sub, SubAssign ops on AffineRepr.
• #767 (ark-curve25519) Change (negate) generator of curve25519 for inter-operability with curve25519-dalek.
• #811 (ark-serialize) Remove Send trait bound from Valid.

Features

• #758 Implement Elligator2 hash-to-curve parameters for Bandersnatch.
• #659 (ark-ec) Add Elligator2 hash-to-curve map.
• #689 (ark-serialize) Add CanonicalSerialize and CanonicalDeserialize impls for VecDeque and LinkedList.
• #691 (ark-poly) Implement Polynomial for SparseMultilinearExtension and DenseMultilinearExtension.
• #693 (ark-serialize) Add serialize_to_vec! convenience macro.
• #713 (ark-ff) Add support for bitwise operations AND, OR, and XOR between BigInteger.
• #763 (ark-poly) Add concat to concatenate evaluation tables of DenseMultilinearPolynomials.
• #811 (ark-serialize) Implement Valid & CanonicalDeserialize for Rc.

Improvements

• #736 (ark-ff) Deprecate divn(), and use core::ops::{Shr, ShrAssign} instead.
• #739 (ark-ff) Deprecate muln(), and use core::ops::{Shl, ShlAssign} instead.
• #771 (ark-ec) Omit expensive scalar multiplication in is_in_correct_subgroup_assuming_on_curve() for short Weierstrass curves of cofactor one.
• #817 (ark-ec) Relax the visibility for G2 ell coeffs and related algorithms.

Bugfixes

• #747 (ark-ff-macros) Fix fetching attributes in MontConfig macro.
• #803 (ark-ec, ark-test-template) Fix incorrect decomposition in GLV.
• #806 (ark-ff) Fix the impl for Displaying zero element in Fp.
• #822 (ark-ec, ark-test-template) Fix the incorrect Affine - Projective implementation

use workspace dependencies

temp remove cyclic dev-dependencies

Breaking changes

• #300 (ark-ec) Change the implementation of Hash trait of GroupProjective to use the affine coordinates.
• #302 (ark-ff) Rename find_wnaf to find_naf.
• #310 (ark-ec, ark-ff) Remove unnecessary internal PhantomData.
• #333 (ark-poly) Expose more properties of EvaluationDomains.
• #338 (ark-ec) Add missing UniformRand trait bound to GroupAffine.
• #338 (workspace) Change to Rust 2021 edition.
• #345 (ark-ec, ark-serialize) Change the serialization format for Twisted Edwards Curves. We now encode the Y coordinate and take the sign bit of the X coordinate, the default flag is also now the Positive X value. The old methods for backwards compatibility are located here
• #348 (ark-ec) Rename msm:{Fixed,Variable}BaseMSM:multi_scalar_mul to msm:{Fixed,Variable}:msm to avoid redundancy.
• #359 (ark-test-templates) Simplify the field and curve test macros.
• #365 (ark-ec)
  • Move COFACTOR, COFACTOR_INV, and is_in_correct_subgroup_assuming_on_curve() from {SW,TE}CurveConfig to CurveConfig.
  • Add mul_bits() to AffineCurve and provide a default implementation of mul() using this.
  • Remove duplicate function scale_by_cofactor() from short_weierstrass::GroupAffine and twisted_edwards_extended::GroupAffine
• #370 (all) Set the minimum rust-version = 1.56 in the manifests of all crates.
• #379 (ark-ff) Refactor Field implementation and PrimeField trait:
  • Switch from hardcoded FpXYZ to Fp<N> based on const generics.
  • Move Montgomery arithmetic to an optional backend.
  • Rename field_new macros to MontFp, QuadExt and CubicExt macros.
  • Introduce const fns for generating many constants.
  • Add default associated constants to reduce boilerplate.
  • Rename Fp*Parameters to Fp*Config.
  • Add From<u32>, From<u16>, and From<u8> impls for BigInt<N>.
  • Remove FftConfig; move its contents to FftField.
• #383 (ark-ff) Rename BigInteger::add_nocarry to add_with_carry and sub_noborrow to sub_with_borrow.
• #386 (ark-ff) Remove PrimeField::GENERATOR, since it already exists on FftField.
• #393 (ark-ec, ark-ff) Rename FpXParams to FpXConfig and FpXParamsWrapper to FpXConfigWrapper.
• #396 (ark-ec) Remove mul_bits feature, and remove default implementations of mul and mul_by_cofactor_to_projective.
• #408 (ark-ff) Change the output of Display formatting for BigInt and Fp from hex to decimal.
• #412 (ark-poly) Rename UV/MVPolynomial to DenseUV/MVPolynomial.
• #417 (ark-ff) Remove ToBytes and FromBytes.
• #418 (ark-ff) Add sums_of_products to Field and Fp
• #422 (ark-ff) Remove SquareRootField, and move functionality to Field
• #425 (ark-ec) Refactor VariableBase struct to VariableBaseMSM trait and implement it for GroupProjective.
• #438 (ark-ec) Rename modules, structs, and traits related to ec.
  • short_weierstrass_jacobian → short_weierstrass
  • twisted_edwards_extend → twisted_edwards
  • GroupAffine → Affine
  • GroupProjective → Projective
  • ModelParameters → CurveConfig
  • SWModelParameters → SWCurveConfig
  • TEModelParameters → TECurveConfig
  • MontgomeryModelParameters → MontCurveConfig
• #440 (ark-ff) Add a method to construct a field element from an element of the underlying base prime field.
• #443, #449 (ark-ec) Improve ergonomics of scalar multiplication.
  • Rename ProjectiveCurve::mul(AsRef[u64]) to ProjectiveCurve::mul_bigint(AsRef[u64]).
  • Bound ProjectiveCurve by
    • Mul<ScalarField>,
    • for<'a> Mul<&'a ScalarField>
    • MulAssign<ScalarField>,
    • for<'a> MulAssign<&'a ScalarField>
  • Bound AffineCurve by
    • Mul<ScalarField, Output = ProjectiveCurve>
    • for<'a> Mul<&'a ScalarField, Output = ProjectiveCurve>
• #445 (ark-ec) Change the ATE_LOOP_COUNT in MNT4/6 curves to use 2-NAF.
• #446 (ark-ff) Add CyclotomicMultSubgroup trait and implement it for extension fields
• #447 (ark-ec, ark-algebra-test-templates) Rename and refactor group infrastructure, and test infrastructure for fields, groups, and pairings:
  • Create new Group trait and move some functionality from ProjectiveCurve to it.
  • Refactor add_assign_mixed → add_assign that's polymorphic over its RHS.
  • Rename ProjectiveCurve to CurveGroup: Group.
    • Rename some associated types:
      • AffineCurve → Affine
    • Rename some methods:
      • batch_normalization_into_affine → normalize_batch
      • prime_subgroup_generator → generator
  • Rename AffineCurve to AffineRepr.
    • Rename associated types:
      • Projective → Group
    • Add methods:
      • Add method fn x(&self) -> Self::BaseField that returns the x coordinate of the point.
      • Add method fn y(&self) -> Self::BaseField that returns the y coordinate of the point.
    • Rename methods:
      • zero() → identity()
      • is_zero() → is_identity()
      • into_projective() → into_group()
      • prime_subgroup_generator() → generator()
  • Add new ScalarMul trait that encapsulates scalar multiplication routines for arbitrary Groups.
    • ScalarMul trait has a MulBase associated type to encapsulate bases for variable base and fixed-base scalar multiplication algorithms.
    • ScalarMul requires Add<Self::MulBase, Output = Self>, AddAssign<Self::MulBase>, and From<Self::MulBase>.
  • Rename PairingEngine to Pairing:
    • Rename associated types:
      • Fr → ScalarField
      • G1Projective → G1
      • G2Projective → G2
      • Fqk → TargetField: CyclotomicMultSubgroup
    • Remove associated type Fqe.
    • Rename methods:
      • miller_loop → multi_miller_loop
      • pairing → multi_pairing
    • Change method signatures:
      • product_of_pairings → multi_pairing
        • take two references to element iterators instead of an iterator of tuples.
      • miller_loop and multi_miller_loop now
        • take two iterators over impl Into<G1Prepared> and impl Into<G2Prepared> as input, and
        • output MillerLoopOutput, which is a newtype wrapper around TargetField.
      • final_exponentiation now
        • takes as input a MillerLoopOutput,
        • outputs PairingOutput, which is a newtype around TargetField, and which implements Group and ScalarMul, allowing it to be used with the existing MSM infrastructure.
      • Pairings, which are the composition of Miller loops and final exponentiation, are changed accordingly.
  • ark-algebra-test-templates macro syntax is now simplified; see the test files in test-curves for examples.
• #463 (ark-serialize, ark-ff, ark-ec) Refactor serialization infrastructure to enable more flexibility and less repetition of code:
  • New enum Compress that indicates whether point compression should be enabled or not.
  • New enum Validate that indicates whether type-specific validation checks should be carried out or not.
  • New trait Valid that provides methods for checking whether a deserialized value of a given type passes appropriate validation checks. The trait has the following methods
    • check which checks a single value, and
    • batch_check which checks a batch of values.
  • CanonicalSerialize:
    • New signature for serialize that takes in an argument compress: Compress
    • Old serialize → serialize_compressed
    • serialize_uncompressed → serialize_uncompressed
    • Every method has a default implementation that calls serialize with the appropriate compress value.
  • CanonicalDeserialize:
    • All types implementing
    • New signature for deserialize that takes in arguments compress: Compress and validate: Validate.
    • deserialize → deserialize_compressed
    • deserialize_uncompressed → deserialize_uncompressed
    • deserialize_unchecked → deserialize_uncompressed_unchecked
    • New method deserialize_compressed_unchecked that performs decompression but skips validation checks.
    • Every method has a default implementation that calls deserialize with the appropriate compress and validate values.
  • The SWFlags enum has been moved to ark_ec::models::short_weierstrass, and has had its variants renamed to be somewhat more descriptive.
  • The EdwardsFlags enum has been moved to ark_ec::models::twisted_edwards, has been renamed to TEFlags, and has had its variants renamed to be somewhat more descriptive.
  • New serialization format for Short Weierstrass curves:
    • Points with a "positive" y-coordinate are serialized with the sign bit set to zero (as opposed to the sign bit set to one in the old behavior).
    • Points with a "negative" y-coordinate are serialized with the sign bit set to one (as opposed to the sign bit set to zero in the old behavior).
    • The point at infinity is serialized with the infinity flag set to one.
  • New serialization format for Twisted Edwards curves:
    • Points with a "positive" x-coordinate are serialized with the sign bit set to zero.
    • Points with a "negative" x-coordinate are serialized with the sign bit set to one.
• #487 (ark-poly) Refactor EvaluationDomain trait for cosets:
  • Remove method generator_inv.
  • Remove method divide_by_vanishing_poly_on_coset_in_place.
  • Remove coset fft methods: coset_fft, coset_fft_in_place, coset_ifft, coset_ifft_in_place.
• #492 (ark-ff) Refactor ark-ff APIs:
  • Splits the contents of ff/src/fields/mod.rs into smaller files for easier management.
  • Moves BitIterator out of ark_ff::fields and into ark_ff directly.
  • Adds impl<'a, 'b> Add/Sub/Mul/Div<&'a F> for &'b F
• #517 (ark-ec) Move the definition of the isogeny map of WB hash-to-curve to a separate struct
• #519 (ark-ec) Refactor variable-base MSM to be checked by default, returning a Result if the lengths of the bases and scalars do not match.
• #545 (ark-ec, ark-ff) Rename all *Parameters or *Params to *Config, including:
  • SWUParams → SWUConfig
  • WBParams → WBConfig
  • Bls12Parameters → Bls12Config
  • G1Parameters → G1Config
  • G2Parameters → G2Config
  • BnParameters → BnConfig
  • BW6Parameters → BW6Config
  • MNT4Parameters → MNT4Config
  • MNT6Parameters → MNT6Config
  • GLVParameters → GLVConfig
• #557 (ark-ff) Change frobenius_map to return the result, instead of mutating the input. Add frobenius_map_in_place for the old behavior.

Features

• #301 (ark-ec) Add GLVParameters trait definition.
• #312 (ark-ec) Add is_in_correct_subgroup_assuming_on_curve for all Parameters.
• #321 (ark-ff) Change bigint conversions to impl From instead of Into.
• #343 (ark-ec) Add WB and SWU hash-to-curve maps.
• #348 (ark-ec) Add msm:{Fixed,Variable}Base:msm_checked_len.
• #364 (ark-ec) Add ChunkedPippenger to variable-base MSM.
• #371 (ark-serialize) Add serialization impls for arrays
• #386 (ark-ff-macros, ark-ff) Add a macro to derive MontConfig.
• #396 (ark-ec) Add a default mul function to {TE,SW}CurveConfig trait definition.
• #397 (ark-ec) Add HashMapPippenger to variable-base MSM.
• #418 (ark-ff) Add sums_of_products to Field and Fp
• #420 (ark-ec) Add a clear_cofactor method to AffineCurve.
• #430 (ark-ec) Add functionality for mapping a field element to a curve element for hash-to-curve.
• #440 (ark-ff) Add a method to construct a field element from an element of the underlying base prime field.
• #446 (ark-ff) Add CyclotomicMultSubgroup trait and impl for extension fields
• #467 (ark-ec)
  • Move implementation of serialize_with_mode(), deserialize_with_mode(), and serialized_size() into {SW,TE}CurveConfig to allow customization.
• #487 (ark-poly) Refactor EvaluationDomain trait for cosets:
  • Add constructor new_coset.
  • Add convenience method get_coset.
  • Add methods coset_offset, coset_offset_inv and coset_offset_pow_size.
• #539 (ark-ec) Implement wNAF-based MSM, resulting in 5-10% speedups.
• #528 (ark-ec) Allow to overwrite the default implementation of the msm function provided by the VariableBaseMSM trait by a specialized version in SWCurveConfig.

Improvements

• #302 (ark-ff) Add the relaxed NAF computation.
• #306 (ark-ff, ark-ff-asm) Make the assembly backend available on stable.
• #339 (ark-ff) Remove duplicated code from test_field module and replace its usage with ark-test-curves crate.
• #352 (ark-ff) Update QuadExtField::sqrt for better performance.
• #357 (ark-poly) Speedup division by vanishing polynomials for dense polynomials.
• #445 (ark-ec) Use 2-NAF for ate pairing in MNT4/6 curves.
• #509 (ark-ff, ark-ff-macros) Support prime fields with (64 * k)-bit modulus.
• #567 (ark-ec) Allow to overwrite the default implementation of the msm function for TwistedEdwards form provided by the VariableBaseMSM trait by a specialized version in TECurveConfig.

Bugfixes

• #350 (ark-serialize) Fix issues with hygiene whenever a non-standard Result type is in scope.
• #358 (ark-ff) Fix the bug for QuadExtField::sqrt when c1 = 0 && c0.legendre.is_qnr()
• #366 (ark-ff) Fix norm() for cubic extension field towers.
• #394 (ark-ff, ark-serialize) Remove EmptyFlags construction checks.
• #442 (ark-ff) Fix deserialization for modulo with 64 shaving bits.
• #460 (ark-ec) Fix a corner case for ate pairing in BLS12 and BW6 models.
• #521 (ark-poly) Change DensePolynomial::evaluate_over_domain to not truncate terms higher than the size of the domain.
• #526 (ark-ff) Fix squaring for Fp128.