From 2aadc03ef15cb5ca5cc2af8a7c08e070742f0ac4 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 4 May 2024 14:47:55 +0200 Subject: Adding upstream version 0.70.1+ds1. Signed-off-by: Daniel Baumann --- vendor/ff/.cargo-checksum.json | 1 + vendor/ff/CHANGELOG.md | 143 ++++++++++++ vendor/ff/Cargo.toml | 67 ++++++ vendor/ff/LICENSE-APACHE | 202 +++++++++++++++++ vendor/ff/LICENSE-MIT | 21 ++ vendor/ff/README.md | 75 +++++++ vendor/ff/rust-toolchain | 1 + vendor/ff/src/batch.rs | 131 +++++++++++ vendor/ff/src/helpers.rs | 128 +++++++++++ vendor/ff/src/lib.rs | 498 +++++++++++++++++++++++++++++++++++++++++ vendor/ff/tests/derive.rs | 137 ++++++++++++ 11 files changed, 1404 insertions(+) create mode 100644 vendor/ff/.cargo-checksum.json create mode 100644 vendor/ff/CHANGELOG.md create mode 100644 vendor/ff/Cargo.toml create mode 100644 vendor/ff/LICENSE-APACHE create mode 100644 vendor/ff/LICENSE-MIT create mode 100644 vendor/ff/README.md create mode 100644 vendor/ff/rust-toolchain create mode 100644 vendor/ff/src/batch.rs create mode 100644 vendor/ff/src/helpers.rs create mode 100644 vendor/ff/src/lib.rs create mode 100644 vendor/ff/tests/derive.rs (limited to 'vendor/ff') diff --git a/vendor/ff/.cargo-checksum.json b/vendor/ff/.cargo-checksum.json new file mode 100644 index 0000000..0a06ed0 --- /dev/null +++ b/vendor/ff/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{},"package":"ded41244b729663b1e574f1b4fb731469f69f79c17667b5d776b16cda0479449"} \ No newline at end of file diff --git a/vendor/ff/CHANGELOG.md b/vendor/ff/CHANGELOG.md new file mode 100644 index 0000000..9188fcf --- /dev/null +++ b/vendor/ff/CHANGELOG.md @@ -0,0 +1,143 @@ +# Changelog +All notable changes to this library will be documented in this file. + +The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/), +and this library adheres to Rust's notion of +[Semantic Versioning](https://semver.org/spec/v2.0.0.html). + +## [Unreleased] + +## [0.13.0] - 2022-12-06 +### Added +- `ff::Field::{ZERO, ONE}` +- `ff::Field::pow` +- `ff::Field::{sqrt_ratio, sqrt_alt}` +- `core::iter::{Sum, Product}` bounds on `ff::Field` +- `ff::PrimeField::from_u128` +- `ff::PrimeField::{MODULUS, TWO_INV}` +- Constants related to multiplicative generators: + - `ff::PrimeField::MULTIPLICATIVE_GENERATOR` + - `ff::PrimeField::{ROOT_OF_UNITY, ROOT_OF_UNITY_INV}` + - `ff::PrimeField::DELTA` +- `ff::WithSmallOrderMulGroup` +- `ff::FromUniformBytes` +- `ff::helpers`: + - `sqrt_tonelli_shanks` + - `sqrt_ratio_generic` + +### Changed +- `ff::Field::sqrt` is now a provided method that uses the `Field::sqrt_ratio` + method. Implementors of the `Field` trait can choose to implement + `Field::sqrt_ratio` and use the provided `ff::Field::sqrt` method, especially + if it is more efficient in practice, or they can keep their own implementation + of `Field::sqrt` and implement `Field::sqrt_ratio` in terms of that + implementation using the `ff::helpers::sqrt_ratio_generic` helper function. +- `ff::PrimeField` is now documented as representing a non-binary field (i.e. + its prime is not 2). This was always the intention, but is now a concrete + requirement in order for `PrimeField::TWO_INV` to exist. + +### Removed +- `ff::Field::{zero, one}` (use `ff::Field::{ZERO, ONE}` instead). +- `ff::PrimeField::{multiplicative_generator, root_of_unity}` (use + `ff::PrimeField::{MULTIPLICATIVE_GENERATOR, ROOT_OF_UNITY}` instead). + +## [0.12.1] - 2022-10-28 +### Fixed +- `ff_derive` previously generated a `Field::random` implementation that would + overflow for fields that needed a full 64-bit spare limb. + +## [0.12.0] - 2022-05-04 +### Changed + +- MSRV is now 1.56.0. +- Bumped `bitvec` to 1.0. + +## [0.11.1] - 2022-05-04 +### Fixed +- `ff_derive` procedural macro can now be invoked within regular macros. +- Previously, `ff_derive`'s procedural macro would generate implementations of + `PrimeFieldBits` even when the `bits` crate feature was disabled. `ff_derive` + can now be used without a dependency on `bitvec` by disabling feature + features. The new crate feature `derive_bits` can be used to force the + generation of `PrimeFieldBits` implementations. This new crate feature will be + removed once our MSRV is at least 1.60 and we have access to [weak dependency + features](https://blog.rust-lang.org/2022/04/07/Rust-1.60.0.html#new-syntax-for-cargo-features). + +## [0.11.0] - 2021-09-02 +### Added +- `subtle::ConstantTimeEq` bound on `ff::Field` +- `Copy + Send + Sync + 'static` bounds on `ff::PrimeField::Repr` +- `ff::derive` module behind the `derive` feature flag, containing dependencies for the + `PrimeField` derive macro: + - Re-exports of required crates. + - `adc, mac, sbb` constant-time const helper functions. +- `ff::Field::is_zero_vartime` +- `ff::PrimeField::from_repr_vartime` + +### Changed +- `ff::Field::is_zero` now returns `subtle::Choice`. +- `ff::PrimeField::{is_odd, is_even}` now return `subtle::Choice`. +- `ff::PrimeField::from_repr` now return `subtle::CtOption`. +- `ff::PrimeField::from_str` has been renamed to `PrimeField::from_str_vartime`. + +### Removed +- `ff::{adc, mac_with_carry, sbb}` (replaced by `ff::derive::{adc, mac, sbb}`). + +## [0.10.1] - 2021-08-11 +### Added +- `ff::BatchInvert` extension trait, implemented for iterators over mutable field elements + which allows those field elements to be inverted in a batch. This trait is behind the + new `alloc` feature flag. +- `ff::BatchInverter` struct, which provides methods for non-allocating batch inversion of + field elements contained within slices. + +## [0.10.0] - 2021-06-01 +### Added +- `ff::PrimeFieldBits: PrimeField` trait, behind a `bits` feature flag. + +### Changed +- MSRV is now 1.51.0. +- Bumped `bitvec` to 0.22 to enable fixing a performance regression in `ff 0.9`. + The `bitvec::view::BitView` re-export has been replaced by + `bitvec::view::BitViewSized`. +- The `bitvec` dependency and its re-exports have been gated behind the `bits` + feature flag. + +### Removed +- `ff::PrimeField::{ReprBits, char_le_bits, to_le_bits}` (replaced by + `ff::PrimeFieldBits` trait). + +### Fixed +- `#[derive(PrimeField)]` now works on small moduli (that fit in a single `u64` + limb). + +## [0.9.0] - 2021-01-05 +### Added +- Re-export of `bitvec::view::BitView`. +- `ff::FieldBits` type alias for the return type of + `ff::PrimeField::{char_le_bits, to_le_bits}`. + +### Changed +- Bumped `bitvec` to 0.20, `rand_core` to 0.6. + +### Removed +- `From` and `From<&Self>` bounds on `ff::PrimeField::Repr`. + +## [0.8.0] - 2020-09-08 +### Added +- `ff::PrimeField::{ReprBits, char_le_bits, to_le_bits}`, and a public + dependency on `bitvec 0.18`. +- `ff::Field::cube` method with provided implementation. +- `Send + Sync` bounds on `ff::PrimeField::ReprBits` + +### Changed +- MSRV is now 1.44.0. +- `ff::Field::random(rng: &mut R) -> Self` has been changed + to `Field::random(rng: impl RngCore) -> Self`, to aligh with + `group::Group::random`. + +### Removed +- `fmt::Display` bound on `ff::Field`. +- `ff::PrimeField::char` (replaced by `ff::PrimeField::char_le_bits`). +- `ff::{BitIterator, Endianness, PrimeField::ReprEndianness` (replaced by + `ff::PrimeField::to_le_bits`). diff --git a/vendor/ff/Cargo.toml b/vendor/ff/Cargo.toml new file mode 100644 index 0000000..6575849 --- /dev/null +++ b/vendor/ff/Cargo.toml @@ -0,0 +1,67 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies. +# +# If you are reading this file be aware that the original Cargo.toml +# will likely look very different (and much more reasonable). +# See Cargo.toml.orig for the original contents. + +[package] +edition = "2021" +name = "ff" +version = "0.13.0" +authors = ["Sean Bowe ", "Jack Grigg "] +description = "Library for building and interfacing with finite fields" +homepage = "https://github.com/zkcrypto/ff" +documentation = "https://docs.rs/ff/" +readme = "README.md" +license = "MIT/Apache-2.0" +repository = "https://github.com/zkcrypto/ff" +resolver = "2" +[package.metadata.docs.rs] +all-features = true +rustdoc-args = ["--cfg", "docsrs"] + +[[test]] +name = "derive" +required-features = ["derive"] +[dependencies.bitvec] +version = "1" +optional = true +default-features = false + +[dependencies.byteorder] +version = "1" +optional = true +default-features = false + +[dependencies.ff_derive] +version = "0.13" +optional = true + +[dependencies.rand_core] +version = "0.6" +default-features = false + +[dependencies.subtle] +version = "2.2.1" +features = ["i128"] +default-features = false +[dev-dependencies.blake2b_simd] +version = "1" + +[dev-dependencies.rand] +version = "0.8" + +[features] +alloc = [] +bits = ["bitvec"] +default = ["bits", "std"] +derive = ["byteorder", "ff_derive"] +derive_bits = ["bits", "ff_derive/bits"] +std = ["alloc"] +[badges.maintenance] +status = "actively-developed" diff --git a/vendor/ff/LICENSE-APACHE b/vendor/ff/LICENSE-APACHE new file mode 100644 index 0000000..1e5006d --- /dev/null +++ b/vendor/ff/LICENSE-APACHE @@ -0,0 +1,202 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + +TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + +1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + +2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + +3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + +4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + +5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + +6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + +7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + +8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + +9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + +END OF TERMS AND CONDITIONS + +APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + +Copyright [yyyy] [name of copyright owner] + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. + diff --git a/vendor/ff/LICENSE-MIT b/vendor/ff/LICENSE-MIT new file mode 100644 index 0000000..ed3a13f --- /dev/null +++ b/vendor/ff/LICENSE-MIT @@ -0,0 +1,21 @@ +The MIT License (MIT) + +Copyright (c) 2017 Sean Bowe + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. diff --git a/vendor/ff/README.md b/vendor/ff/README.md new file mode 100644 index 0000000..907c069 --- /dev/null +++ b/vendor/ff/README.md @@ -0,0 +1,75 @@ +# ff + +`ff` is a finite field library written in pure Rust, with no `unsafe{}` code. + +## Disclaimers + +* This library does not provide constant-time guarantees. The traits enable downstream + users to expose constant-time logic, but `#[derive(PrimeField)]` in particular does not + generate constant-time code (even for trait methods that return constant-time-compatible + values). + +## Usage + +Add the `ff` crate to your `Cargo.toml`: + +```toml +[dependencies] +ff = "0.13" +``` + +The `ff` crate contains the `Field` and `PrimeField` traits. +See the **[documentation](https://docs.rs/ff/)** for more. + +### #![derive(PrimeField)] + +If you need an implementation of a prime field, this library also provides a procedural +macro that will expand into an efficient implementation of a prime field when supplied +with the modulus. `PrimeFieldGenerator` must be an element of Fp of p-1 order, that is +also quadratic nonresidue. + +First, enable the `derive` crate feature: + +```toml +[dependencies] +ff = { version = "0.13", features = ["derive"] } +``` + +And then use the macro like so: + +```rust +#[macro_use] +extern crate ff; + +#[derive(PrimeField)] +#[PrimeFieldModulus = "52435875175126190479447740508185965837690552500527637822603658699938581184513"] +#[PrimeFieldGenerator = "7"] +#[PrimeFieldReprEndianness = "little"] +struct Fp([u64; 4]); +``` + +And that's it! `Fp` now implements `Field` and `PrimeField`. + +## Minimum Supported Rust Version + +Requires Rust **1.56** or higher. + +Minimum supported Rust version can be changed in the future, but it will be done with a +minor version bump. + +## License + +Licensed under either of + + * Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or + http://www.apache.org/licenses/LICENSE-2.0) + * MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT) + +at your option. + +### Contribution + +Unless you explicitly state otherwise, any contribution intentionally +submitted for inclusion in the work by you, as defined in the Apache-2.0 +license, shall be dual licensed as above, without any additional terms or +conditions. diff --git a/vendor/ff/rust-toolchain b/vendor/ff/rust-toolchain new file mode 100644 index 0000000..3ebf789 --- /dev/null +++ b/vendor/ff/rust-toolchain @@ -0,0 +1 @@ +1.56.0 diff --git a/vendor/ff/src/batch.rs b/vendor/ff/src/batch.rs new file mode 100644 index 0000000..96ddc5a --- /dev/null +++ b/vendor/ff/src/batch.rs @@ -0,0 +1,131 @@ +//! Batched field inversion APIs, using [Montgomery's trick]. +//! +//! [Montgomery's trick]: https://zcash.github.io/halo2/background/fields.html#montgomerys-trick + +use subtle::ConstantTimeEq; + +use crate::Field; + +/// Extension trait for iterators over mutable field elements which allows those field +/// elements to be inverted in a batch. +/// +/// `I: IntoIterator` implements this trait when +/// the `alloc` feature flag is enabled. +/// +/// For non-allocating contexts, see the [`BatchInverter`] struct. +#[cfg(feature = "alloc")] +#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))] +pub trait BatchInvert { + /// Consumes this iterator and inverts each field element (when nonzero). Zero-valued + /// elements are left as zero. + /// + /// Returns the inverse of the product of all nonzero field elements. + fn batch_invert(self) -> F; +} + +#[cfg(feature = "alloc")] +#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))] +impl<'a, F, I> BatchInvert for I +where + F: Field + ConstantTimeEq, + I: IntoIterator, +{ + fn batch_invert(self) -> F { + let mut acc = F::ONE; + let iter = self.into_iter(); + let mut tmp = alloc::vec::Vec::with_capacity(iter.size_hint().0); + for p in iter { + let q = *p; + tmp.push((acc, p)); + acc = F::conditional_select(&(acc * q), &acc, q.is_zero()); + } + acc = acc.invert().unwrap(); + let allinv = acc; + + for (tmp, p) in tmp.into_iter().rev() { + let skip = p.is_zero(); + + let tmp = tmp * acc; + acc = F::conditional_select(&(acc * *p), &acc, skip); + *p = F::conditional_select(&tmp, p, skip); + } + + allinv + } +} + +/// A non-allocating batch inverter. +pub struct BatchInverter {} + +impl BatchInverter { + /// Inverts each field element in `elements` (when nonzero). Zero-valued elements are + /// left as zero. + /// + /// - `scratch_space` is a slice of field elements that can be freely overwritten. + /// + /// Returns the inverse of the product of all nonzero field elements. + /// + /// # Panics + /// + /// This function will panic if `elements.len() != scratch_space.len()`. + pub fn invert_with_external_scratch(elements: &mut [F], scratch_space: &mut [F]) -> F + where + F: Field + ConstantTimeEq, + { + assert_eq!(elements.len(), scratch_space.len()); + + let mut acc = F::ONE; + for (p, scratch) in elements.iter().zip(scratch_space.iter_mut()) { + *scratch = acc; + acc = F::conditional_select(&(acc * *p), &acc, p.is_zero()); + } + acc = acc.invert().unwrap(); + let allinv = acc; + + for (p, scratch) in elements.iter_mut().zip(scratch_space.iter()).rev() { + let tmp = *scratch * acc; + let skip = p.is_zero(); + acc = F::conditional_select(&(acc * *p), &acc, skip); + *p = F::conditional_select(&tmp, &p, skip); + } + + allinv + } + + /// Inverts each field element in `items` (when nonzero). Zero-valued elements are + /// left as zero. + /// + /// - `element` is a function that extracts the element to be inverted from `items`. + /// - `scratch_space` is a function that extracts the scratch space from `items`. + /// + /// Returns the inverse of the product of all nonzero field elements. + pub fn invert_with_internal_scratch( + items: &mut [T], + element: TE, + scratch_space: TS, + ) -> F + where + F: Field + ConstantTimeEq, + TE: Fn(&mut T) -> &mut F, + TS: Fn(&mut T) -> &mut F, + { + let mut acc = F::ONE; + for item in items.iter_mut() { + *(scratch_space)(item) = acc; + let p = (element)(item); + acc = F::conditional_select(&(acc * *p), &acc, p.is_zero()); + } + acc = acc.invert().unwrap(); + let allinv = acc; + + for item in items.iter_mut().rev() { + let tmp = *(scratch_space)(item) * acc; + let p = (element)(item); + let skip = p.is_zero(); + acc = F::conditional_select(&(acc * *p), &acc, skip); + *p = F::conditional_select(&tmp, &p, skip); + } + + allinv + } +} diff --git a/vendor/ff/src/helpers.rs b/vendor/ff/src/helpers.rs new file mode 100644 index 0000000..d1d6371 --- /dev/null +++ b/vendor/ff/src/helpers.rs @@ -0,0 +1,128 @@ +//! Helper methods for implementing the `ff` traits. + +use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption}; + +use crate::PrimeField; + +/// Constant-time implementation of Tonelli–Shanks' square-root algorithm for +/// `p mod 16 = 1`. +/// +/// `tm1d2` should be set to `(t - 1) // 2`, where `t = (modulus - 1) >> F::S`. +/// +/// ## Implementing [`Field::sqrt`] +/// +/// This function can be used to implement [`Field::sqrt`] for fields that both implement +/// [`PrimeField`] and satisfy `p mod 16 = 1`. +/// +/// [`Field::sqrt`]: crate::Field::sqrt +pub fn sqrt_tonelli_shanks>(f: &F, tm1d2: S) -> CtOption { + // This is a constant-time version of https://eprint.iacr.org/2012/685.pdf (page 12, + // algorithm 5). Steps 2-5 of the algorithm are omitted because they are only needed + // to detect non-square input; it is more efficient to do that by checking at the end + // whether the square of the result is the input. + + // w = self^((t - 1) // 2) + let w = f.pow_vartime(tm1d2); + + let mut v = F::S; + let mut x = w * f; + let mut b = x * w; + + // Initialize z as the 2^S root of unity. + let mut z = F::ROOT_OF_UNITY; + + for max_v in (1..=F::S).rev() { + let mut k = 1; + let mut b2k = b.square(); + let mut j_less_than_v: Choice = 1.into(); + + // This loop has three phases based on the value of k for algorithm 5: + // - for j <= k, we square b2k in order to calculate b^{2^k}. + // - for k < j <= v, we square z in order to calculate ω. + // - for j > v, we do nothing. + for j in 2..max_v { + let b2k_is_one = b2k.ct_eq(&F::ONE); + let squared = F::conditional_select(&b2k, &z, b2k_is_one).square(); + b2k = F::conditional_select(&squared, &b2k, b2k_is_one); + let new_z = F::conditional_select(&z, &squared, b2k_is_one); + j_less_than_v &= !j.ct_eq(&v); + k = u32::conditional_select(&j, &k, b2k_is_one); + z = F::conditional_select(&z, &new_z, j_less_than_v); + } + + let result = x * z; + x = F::conditional_select(&result, &x, b.ct_eq(&F::ONE)); + z = z.square(); + b *= z; + v = k; + } + + CtOption::new( + x, + (x * x).ct_eq(f), // Only return Some if it's the square root. + ) +} + +/// Computes: +/// +/// - $(\textsf{true}, \sqrt{\textsf{num}/\textsf{div}})$, if $\textsf{num}$ and +/// $\textsf{div}$ are nonzero and $\textsf{num}/\textsf{div}$ is a square in the +/// field; +/// - $(\textsf{true}, 0)$, if $\textsf{num}$ is zero; +/// - $(\textsf{false}, 0)$, if $\textsf{num}$ is nonzero and $\textsf{div}$ is zero; +/// - $(\textsf{false}, \sqrt{G_S \cdot \textsf{num}/\textsf{div}})$, if +/// $\textsf{num}$ and $\textsf{div}$ are nonzero and $\textsf{num}/\textsf{div}$ is +/// a nonsquare in the field; +/// +/// where $G_S$ is a non-square. +/// +/// For this method, $G_S$ is currently [`PrimeField::ROOT_OF_UNITY`], a generator of the +/// order $2^S$ subgroup. Users of this crate should not rely on this generator being +/// fixed; it may be changed in future crate versions to simplify the implementation of +/// the SSWU hash-to-curve algorithm. +/// +/// The choice of root from sqrt is unspecified. +/// +/// ## Implementing [`Field::sqrt_ratio`] +/// +/// This function can be used to implement [`Field::sqrt_ratio`] for fields that also +/// implement [`PrimeField`]. If doing so, the default implementation of [`Field::sqrt`] +/// *MUST* be overridden, or else both functions will recurse in a cycle until a stack +/// overflow occurs. +/// +/// [`Field::sqrt_ratio`]: crate::Field::sqrt_ratio +/// [`Field::sqrt`]: crate::Field::sqrt +pub fn sqrt_ratio_generic(num: &F, div: &F) -> (Choice, F) { + // General implementation: + // + // a = num * inv0(div) + // = { 0 if div is zero + // { num/div otherwise + // + // b = G_S * a + // = { 0 if div is zero + // { G_S*num/div otherwise + // + // Since G_S is non-square, a and b are either both zero (and both square), or + // only one of them is square. We can therefore choose the square root to return + // based on whether a is square, but for the boolean output we need to handle the + // num != 0 && div == 0 case specifically. + + let a = div.invert().unwrap_or(F::ZERO) * num; + let b = a * F::ROOT_OF_UNITY; + let sqrt_a = a.sqrt(); + let sqrt_b = b.sqrt(); + + let num_is_zero = num.is_zero(); + let div_is_zero = div.is_zero(); + let is_square = sqrt_a.is_some(); + let is_nonsquare = sqrt_b.is_some(); + assert!(bool::from( + num_is_zero | div_is_zero | (is_square ^ is_nonsquare) + )); + + ( + is_square & (num_is_zero | !div_is_zero), + CtOption::conditional_select(&sqrt_b, &sqrt_a, is_square).unwrap(), + ) +} diff --git a/vendor/ff/src/lib.rs b/vendor/ff/src/lib.rs new file mode 100644 index 0000000..96bd3e9 --- /dev/null +++ b/vendor/ff/src/lib.rs @@ -0,0 +1,498 @@ +//! This crate provides traits for working with finite fields. + +// Catch documentation errors caused by code changes. +#![no_std] +#![cfg_attr(docsrs, feature(doc_cfg))] +#![deny(rustdoc::broken_intra_doc_links)] +#![forbid(unsafe_code)] + +#[cfg(feature = "alloc")] +extern crate alloc; + +mod batch; +pub use batch::*; + +pub mod helpers; + +#[cfg(feature = "derive")] +#[cfg_attr(docsrs, doc(cfg(feature = "derive")))] +pub use ff_derive::PrimeField; + +#[cfg(feature = "bits")] +#[cfg_attr(docsrs, doc(cfg(feature = "bits")))] +pub use bitvec::view::BitViewSized; + +#[cfg(feature = "bits")] +use bitvec::{array::BitArray, order::Lsb0}; + +use core::fmt; +use core::iter::{Product, Sum}; +use core::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign}; + +use rand_core::RngCore; +use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption}; + +/// Bit representation of a field element. +#[cfg(feature = "bits")] +#[cfg_attr(docsrs, doc(cfg(feature = "bits")))] +pub type FieldBits = BitArray; + +/// This trait represents an element of a field. +pub trait Field: + Sized + + Eq + + Copy + + Clone + + Default + + Send + + Sync + + fmt::Debug + + 'static + + ConditionallySelectable + + ConstantTimeEq + + Neg + + Add + + Sub + + Mul + + Sum + + Product + + for<'a> Add<&'a Self, Output = Self> + + for<'a> Sub<&'a Self, Output = Self> + + for<'a> Mul<&'a Self, Output = Self> + + for<'a> Sum<&'a Self> + + for<'a> Product<&'a Self> + + AddAssign + + SubAssign + + MulAssign + + for<'a> AddAssign<&'a Self> + + for<'a> SubAssign<&'a Self> + + for<'a> MulAssign<&'a Self> +{ + /// The zero element of the field, the additive identity. + const ZERO: Self; + + /// The one element of the field, the multiplicative identity. + const ONE: Self; + + /// Returns an element chosen uniformly at random using a user-provided RNG. + fn random(rng: impl RngCore) -> Self; + + /// Returns true iff this element is zero. + fn is_zero(&self) -> Choice { + self.ct_eq(&Self::ZERO) + } + + /// Returns true iff this element is zero. + /// + /// # Security + /// + /// This method provides **no** constant-time guarantees. Implementors of the + /// `Field` trait **may** optimise this method using non-constant-time logic. + fn is_zero_vartime(&self) -> bool { + self.is_zero().into() + } + + /// Squares this element. + #[must_use] + fn square(&self) -> Self; + + /// Cubes this element. + #[must_use] + fn cube(&self) -> Self { + self.square() * self + } + + /// Doubles this element. + #[must_use] + fn double(&self) -> Self; + + /// Computes the multiplicative inverse of this element, + /// failing if the element is zero. + fn invert(&self) -> CtOption; + + /// Computes: + /// + /// - $(\textsf{true}, \sqrt{\textsf{num}/\textsf{div}})$, if $\textsf{num}$ and + /// $\textsf{div}$ are nonzero and $\textsf{num}/\textsf{div}$ is a square in the + /// field; + /// - $(\textsf{true}, 0)$, if $\textsf{num}$ is zero; + /// - $(\textsf{false}, 0)$, if $\textsf{num}$ is nonzero and $\textsf{div}$ is zero; + /// - $(\textsf{false}, \sqrt{G_S \cdot \textsf{num}/\textsf{div}})$, if + /// $\textsf{num}$ and $\textsf{div}$ are nonzero and $\textsf{num}/\textsf{div}$ is + /// a nonsquare in the field; + /// + /// where $G_S$ is a non-square. + /// + /// # Warnings + /// + /// - The choice of root from `sqrt` is unspecified. + /// - The value of $G_S$ is unspecified, and cannot be assumed to have any specific + /// value in a generic context. + fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self); + + /// Equivalent to `Self::sqrt_ratio(self, one())`. + /// + /// The provided method is implemented in terms of [`Self::sqrt_ratio`]. + fn sqrt_alt(&self) -> (Choice, Self) { + Self::sqrt_ratio(self, &Self::ONE) + } + + /// Returns the square root of the field element, if it is + /// quadratic residue. + /// + /// The provided method is implemented in terms of [`Self::sqrt_ratio`]. + fn sqrt(&self) -> CtOption { + let (is_square, res) = Self::sqrt_ratio(self, &Self::ONE); + CtOption::new(res, is_square) + } + + /// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer + /// exponent. + /// + /// # Guarantees + /// + /// This operation is constant time with respect to `self`, for all exponents with the + /// same number of digits (`exp.as_ref().len()`). It is variable time with respect to + /// the number of digits in the exponent. + fn pow>(&self, exp: S) -> Self { + let mut res = Self::ONE; + for e in exp.as_ref().iter().rev() { + for i in (0..64).rev() { + res = res.square(); + let mut tmp = res; + tmp *= self; + res.conditional_assign(&tmp, (((*e >> i) & 1) as u8).into()); + } + } + res + } + + /// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer + /// exponent. + /// + /// # Guarantees + /// + /// **This operation is variable time with respect to `self`, for all exponent.** If + /// the exponent is fixed, this operation is effectively constant time. However, for + /// stronger constant-time guarantees, [`Field::pow`] should be used. + fn pow_vartime>(&self, exp: S) -> Self { + let mut res = Self::ONE; + for e in exp.as_ref().iter().rev() { + for i in (0..64).rev() { + res = res.square(); + + if ((*e >> i) & 1) == 1 { + res.mul_assign(self); + } + } + } + + res + } +} + +/// This represents an element of a non-binary prime field. +pub trait PrimeField: Field + From { + /// The prime field can be converted back and forth into this binary + /// representation. + type Repr: Copy + Default + Send + Sync + 'static + AsRef<[u8]> + AsMut<[u8]>; + + /// Interpret a string of numbers as a (congruent) prime field element. + /// Does not accept unnecessary leading zeroes or a blank string. + /// + /// # Security + /// + /// This method provides **no** constant-time guarantees. + fn from_str_vartime(s: &str) -> Option { + if s.is_empty() { + return None; + } + + if s == "0" { + return Some(Self::ZERO); + } + + let mut res = Self::ZERO; + + let ten = Self::from(10); + + let mut first_digit = true; + + for c in s.chars() { + match c.to_digit(10) { + Some(c) => { + if first_digit { + if c == 0 { + return None; + } + + first_digit = false; + } + + res.mul_assign(&ten); + res.add_assign(&Self::from(u64::from(c))); + } + None => { + return None; + } + } + } + + Some(res) + } + + /// Obtains a field element congruent to the integer `v`. + /// + /// For fields where `Self::CAPACITY >= 128`, this is injective and will produce a + /// unique field element. + /// + /// For fields where `Self::CAPACITY < 128`, this is surjective; some field elements + /// will be produced by multiple values of `v`. + /// + /// If you want to deterministically sample a field element representing a value, use + /// [`FromUniformBytes`] instead. + fn from_u128(v: u128) -> Self { + let lower = v as u64; + let upper = (v >> 64) as u64; + let mut tmp = Self::from(upper); + for _ in 0..64 { + tmp = tmp.double(); + } + tmp + Self::from(lower) + } + + /// Attempts to convert a byte representation of a field element into an element of + /// this prime field, failing if the input is not canonical (is not smaller than the + /// field's modulus). + /// + /// The byte representation is interpreted with the same endianness as elements + /// returned by [`PrimeField::to_repr`]. + fn from_repr(repr: Self::Repr) -> CtOption; + + /// Attempts to convert a byte representation of a field element into an element of + /// this prime field, failing if the input is not canonical (is not smaller than the + /// field's modulus). + /// + /// The byte representation is interpreted with the same endianness as elements + /// returned by [`PrimeField::to_repr`]. + /// + /// # Security + /// + /// This method provides **no** constant-time guarantees. Implementors of the + /// `PrimeField` trait **may** optimise this method using non-constant-time logic. + fn from_repr_vartime(repr: Self::Repr) -> Option { + Self::from_repr(repr).into() + } + + /// Converts an element of the prime field into the standard byte representation for + /// this field. + /// + /// The endianness of the byte representation is implementation-specific. Generic + /// encodings of field elements should be treated as opaque. + fn to_repr(&self) -> Self::Repr; + + /// Returns true iff this element is odd. + fn is_odd(&self) -> Choice; + + /// Returns true iff this element is even. + #[inline(always)] + fn is_even(&self) -> Choice { + !self.is_odd() + } + + /// Modulus of the field written as a string for debugging purposes. + /// + /// The encoding of the modulus is implementation-specific. Generic users of the + /// `PrimeField` trait should treat this string as opaque. + const MODULUS: &'static str; + + /// How many bits are needed to represent an element of this field. + const NUM_BITS: u32; + + /// How many bits of information can be reliably stored in the field element. + /// + /// This is usually `Self::NUM_BITS - 1`. + const CAPACITY: u32; + + /// Inverse of $2$ in the field. + const TWO_INV: Self; + + /// A fixed multiplicative generator of `modulus - 1` order. This element must also be + /// a quadratic nonresidue. + /// + /// It can be calculated using [SageMath] as `GF(modulus).primitive_element()`. + /// + /// Implementations of this trait MUST ensure that this is the generator used to + /// derive `Self::ROOT_OF_UNITY`. + /// + /// [SageMath]: https://www.sagemath.org/ + const MULTIPLICATIVE_GENERATOR: Self; + + /// An integer `s` satisfying the equation `2^s * t = modulus - 1` with `t` odd. + /// + /// This is the number of leading zero bits in the little-endian bit representation of + /// `modulus - 1`. + const S: u32; + + /// The `2^s` root of unity. + /// + /// It can be calculated by exponentiating `Self::MULTIPLICATIVE_GENERATOR` by `t`, + /// where `t = (modulus - 1) >> Self::S`. + const ROOT_OF_UNITY: Self; + + /// Inverse of [`Self::ROOT_OF_UNITY`]. + const ROOT_OF_UNITY_INV: Self; + + /// Generator of the `t-order` multiplicative subgroup. + /// + /// It can be calculated by exponentiating [`Self::MULTIPLICATIVE_GENERATOR`] by `2^s`, + /// where `s` is [`Self::S`]. + const DELTA: Self; +} + +/// The subset of prime-order fields such that `(modulus - 1)` is divisible by `N`. +/// +/// If `N` is prime, there will be `N - 1` valid choices of [`Self::ZETA`]. Similarly to +/// [`PrimeField::MULTIPLICATIVE_GENERATOR`], the specific choice does not matter, as long +/// as the choice is consistent across all uses of the field. +pub trait WithSmallOrderMulGroup: PrimeField { + /// A field element of small multiplicative order $N$. + /// + /// The presense of this element allows you to perform (certain types of) + /// endomorphisms on some elliptic curves. + /// + /// It can be calculated using [SageMath] as + /// `GF(modulus).primitive_element() ^ ((modulus - 1) // N)`. + /// Choosing the element of order $N$ that is smallest, when considered + /// as an integer, may help to ensure consistency. + /// + /// [SageMath]: https://www.sagemath.org/ + const ZETA: Self; +} + +/// Trait for constructing a [`PrimeField`] element from a fixed-length uniform byte +/// array. +/// +/// "Uniform" means that the byte array's contents must be indistinguishable from the +/// [discrete uniform distribution]. Suitable byte arrays can be obtained: +/// - from a cryptographically-secure randomness source (which makes this constructor +/// equivalent to [`Field::random`]). +/// - from a cryptographic hash function output, which enables a "random" field element to +/// be selected deterministically. This is the primary use case for `FromUniformBytes`. +/// +/// The length `N` of the byte array is chosen by the trait implementer such that the loss +/// of uniformity in the mapping from byte arrays to field elements is cryptographically +/// negligible. +/// +/// [discrete uniform distribution]: https://en.wikipedia.org/wiki/Discrete_uniform_distribution +/// +/// # Examples +/// +/// ``` +/// # #[cfg(feature = "derive")] { +/// # // Fake this so we don't actually need a dev-dependency on bls12_381. +/// # mod bls12_381 { +/// # use ff::{Field, PrimeField}; +/// # +/// # #[derive(PrimeField)] +/// # #[PrimeFieldModulus = "52435875175126190479447740508185965837690552500527637822603658699938581184513"] +/// # #[PrimeFieldGenerator = "7"] +/// # #[PrimeFieldReprEndianness = "little"] +/// # pub struct Scalar([u64; 4]); +/// # +/// # impl ff::FromUniformBytes<64> for Scalar { +/// # fn from_uniform_bytes(_bytes: &[u8; 64]) -> Self { +/// # // Fake impl for doctest +/// # Scalar::ONE +/// # } +/// # } +/// # } +/// # +/// use blake2b_simd::blake2b; +/// use bls12_381::Scalar; +/// use ff::FromUniformBytes; +/// +/// // `bls12_381::Scalar` implements `FromUniformBytes<64>`, and BLAKE2b (by default) +/// // produces a 64-byte hash. +/// let hash = blake2b(b"Some message"); +/// let val = Scalar::from_uniform_bytes(hash.as_array()); +/// # } +/// ``` +/// +/// # Implementing `FromUniformBytes` +/// +/// [`Self::from_uniform_bytes`] should always be implemented by interpreting the provided +/// byte array as the little endian unsigned encoding of an integer, and then reducing that +/// integer modulo the field modulus. +/// +/// For security, `N` must be chosen so that `N * 8 >= Self::NUM_BITS + 128`. A larger +/// value of `N` may be chosen for convenience; for example, for a field with a 255-bit +/// modulus, `N = 64` is convenient as it matches the output length of several common +/// cryptographic hash functions (such as SHA-512 and BLAKE2b). +/// +/// ## Trait design +/// +/// This trait exists because `PrimeField::from_uniform_bytes([u8; N])` cannot currently +/// exist (trait methods cannot use associated constants in the const positions of their +/// type signature, and we do not want `PrimeField` to require a generic const parameter). +/// However, this has the side-effect that `FromUniformBytes` can be implemented multiple +/// times for different values of `N`. Most implementations of [`PrimeField`] should only +/// need to implement `FromUniformBytes` trait for one value of `N` (chosen following the +/// above considerations); if you find yourself needing to implement it multiple times, +/// please [let us know about your use case](https://github.com/zkcrypto/ff/issues/new) so +/// we can take it into consideration for future evolutions of the `ff` traits. +pub trait FromUniformBytes: PrimeField { + /// Returns a field element that is congruent to the provided little endian unsigned + /// byte representation of an integer. + fn from_uniform_bytes(bytes: &[u8; N]) -> Self; +} + +/// This represents the bits of an element of a prime field. +#[cfg(feature = "bits")] +#[cfg_attr(docsrs, doc(cfg(feature = "bits")))] +pub trait PrimeFieldBits: PrimeField { + /// The backing store for a bit representation of a prime field element. + type ReprBits: BitViewSized + Send + Sync; + + /// Converts an element of the prime field into a little-endian sequence of bits. + fn to_le_bits(&self) -> FieldBits; + + /// Returns the bits of the field characteristic (the modulus) in little-endian order. + fn char_le_bits() -> FieldBits; +} + +/// Functions and re-exported crates used by the [`PrimeField`] derive macro. +#[cfg(feature = "derive")] +#[cfg_attr(docsrs, doc(cfg(feature = "derive")))] +pub mod derive { + pub use crate::arith_impl::*; + + pub use {byteorder, rand_core, subtle}; + + #[cfg(feature = "bits")] + pub use bitvec; +} + +#[cfg(feature = "derive")] +mod arith_impl { + /// Computes `a - (b + borrow)`, returning the result and the new borrow. + #[inline(always)] + pub const fn sbb(a: u64, b: u64, borrow: u64) -> (u64, u64) { + let ret = (a as u128).wrapping_sub((b as u128) + ((borrow >> 63) as u128)); + (ret as u64, (ret >> 64) as u64) + } + + /// Computes `a + b + carry`, returning the result and the new carry over. + #[inline(always)] + pub const fn adc(a: u64, b: u64, carry: u64) -> (u64, u64) { + let ret = (a as u128) + (b as u128) + (carry as u128); + (ret as u64, (ret >> 64) as u64) + } + + /// Computes `a + (b * c) + carry`, returning the result and the new carry over. + #[inline(always)] + pub const fn mac(a: u64, b: u64, c: u64, carry: u64) -> (u64, u64) { + let ret = (a as u128) + ((b as u128) * (c as u128)) + (carry as u128); + (ret as u64, (ret >> 64) as u64) + } +} diff --git a/vendor/ff/tests/derive.rs b/vendor/ff/tests/derive.rs new file mode 100644 index 0000000..fa6ee20 --- /dev/null +++ b/vendor/ff/tests/derive.rs @@ -0,0 +1,137 @@ +//! This module exercises the `ff_derive` procedural macros, to ensure that changes to the +//! `ff` crate are reflected in `ff_derive`. It also uses the resulting field to test some +//! of the APIs provided by `ff`, such as batch inversion. + +#[macro_use] +extern crate ff; + +/// The BLS12-381 scalar field. +#[derive(PrimeField)] +#[PrimeFieldModulus = "52435875175126190479447740508185965837690552500527637822603658699938581184513"] +#[PrimeFieldGenerator = "7"] +#[PrimeFieldReprEndianness = "little"] +struct Bls381K12Scalar([u64; 4]); + +mod fermat { + /// The largest known Fermat prime, used to test the case `t = 1`. + #[derive(PrimeField)] + #[PrimeFieldModulus = "65537"] + #[PrimeFieldGenerator = "3"] + #[PrimeFieldReprEndianness = "little"] + struct Fermat65537Field([u64; 1]); +} + +mod full_limbs { + #[derive(PrimeField)] + #[PrimeFieldModulus = "39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319"] + #[PrimeFieldGenerator = "19"] + #[PrimeFieldReprEndianness = "little"] + struct F384p([u64; 7]); + + #[test] + fn random_masking_does_not_overflow() { + use ff::Field; + use rand::rngs::OsRng; + + let _ = F384p::random(OsRng); + } +} + +#[test] +fn constants() { + use ff::{Field, PrimeField}; + + assert_eq!( + Bls381K12Scalar::MODULUS, + "0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001", + ); + + assert_eq!( + Bls381K12Scalar::from(2) * Bls381K12Scalar::TWO_INV, + Bls381K12Scalar::ONE, + ); + + assert_eq!( + Bls381K12Scalar::ROOT_OF_UNITY * Bls381K12Scalar::ROOT_OF_UNITY_INV, + Bls381K12Scalar::ONE, + ); + + // ROOT_OF_UNITY^{2^s} mod m == 1 + assert_eq!( + Bls381K12Scalar::ROOT_OF_UNITY.pow(&[1u64 << Bls381K12Scalar::S, 0, 0, 0]), + Bls381K12Scalar::ONE, + ); + + // DELTA^{t} mod m == 1 + assert_eq!( + Bls381K12Scalar::DELTA.pow(&[ + 0xfffe5bfeffffffff, + 0x09a1d80553bda402, + 0x299d7d483339d808, + 0x73eda753, + ]), + Bls381K12Scalar::ONE, + ); +} + +#[test] +fn from_u128() { + use ff::{Field, PrimeField}; + + assert_eq!(Bls381K12Scalar::from_u128(1), Bls381K12Scalar::ONE); + assert_eq!(Bls381K12Scalar::from_u128(2), Bls381K12Scalar::from(2)); + assert_eq!( + Bls381K12Scalar::from_u128(u128::MAX), + Bls381K12Scalar::from_str_vartime("340282366920938463463374607431768211455").unwrap(), + ); +} + +#[test] +fn batch_inversion() { + use ff::{BatchInverter, Field}; + + let one = Bls381K12Scalar::ONE; + + // [1, 2, 3, 4] + let values: Vec<_> = (0..4) + .scan(one, |acc, _| { + let ret = *acc; + *acc += &one; + Some(ret) + }) + .collect(); + + // Test BatchInverter::invert_with_external_scratch + { + let mut elements = values.clone(); + let mut scratch_space = vec![Bls381K12Scalar::ZERO; elements.len()]; + BatchInverter::invert_with_external_scratch(&mut elements, &mut scratch_space); + for (a, a_inv) in values.iter().zip(elements.into_iter()) { + assert_eq!(*a * a_inv, one); + } + } + + // Test BatchInverter::invert_with_internal_scratch + { + let mut items: Vec<_> = values.iter().cloned().map(|p| (p, one)).collect(); + BatchInverter::invert_with_internal_scratch( + &mut items, + |item| &mut item.0, + |item| &mut item.1, + ); + for (a, (a_inv, _)) in values.iter().zip(items.into_iter()) { + assert_eq!(*a * a_inv, one); + } + } + + // Test BatchInvert trait + #[cfg(feature = "alloc")] + { + use ff::BatchInvert; + let mut elements = values.clone(); + elements.iter_mut().batch_invert(); + for (a, a_inv) in values.iter().zip(elements.into_iter()) { + assert_eq!(*a * a_inv, one); + } + } +} -- cgit v1.2.3