diff options
Diffstat (limited to 'vendor/ff')
| -rw-r--r-- | vendor/ff/.cargo-checksum.json | 1 | ||||
| -rw-r--r-- | vendor/ff/CHANGELOG.md | 109 | ||||
| -rw-r--r-- | vendor/ff/Cargo.toml | 64 | ||||
| -rw-r--r-- | vendor/ff/LICENSE-APACHE | 202 | ||||
| -rw-r--r-- | vendor/ff/LICENSE-MIT | 21 | ||||
| -rw-r--r-- | vendor/ff/README.md | 75 | ||||
| -rw-r--r-- | vendor/ff/rust-toolchain | 1 | ||||
| -rw-r--r-- | vendor/ff/src/batch.rs | 131 | ||||
| -rw-r--r-- | vendor/ff/src/lib.rs | 298 | ||||
| -rw-r--r-- | vendor/ff/tests/derive.rs | 88 |
10 files changed, 990 insertions, 0 deletions
diff --git a/vendor/ff/.cargo-checksum.json b/vendor/ff/.cargo-checksum.json new file mode 100644 index 000000000..fca4d79f2 --- /dev/null +++ b/vendor/ff/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"CHANGELOG.md":"5bde7167688830bc4e6650c03697aa37592538994113b1a2d60b1e7c1776fae5","Cargo.toml":"b3d94339e9e315e8c1c3f13b3347f942994cd8a8254967b34ed62e7b36b24616","LICENSE-APACHE":"3708458dee7f359ac6c9c5558023ed481be87e5372c43ebd7f2ca7ad23c12026","LICENSE-MIT":"8d0c1d1d4b2bebf5b9211f0e883d5a482b7808f3ed31320da14ddee95811f4ef","README.md":"0929aab646864a8c2ecb5a20f55d060116cabceca6ce048fb91e4183fa373fcf","rust-toolchain":"19f1c71cabd3cb062544023af771fbb2883524775fdaed6ca5855bae359b7b9c","src/batch.rs":"4eff75fb32714a1c23992ed0dd9f59e9b04e211115262a28304ede41a73db8d9","src/lib.rs":"ba28b7c480927e28351e6d343807e4099fdccf0731e6b1fd4f948d20ca9dd5e1","tests/derive.rs":"caea00c0b5e8d3f9d68e859dd492287b44207d304440525d828ab31d65b461b4"},"package":"d013fc25338cc558c5c2cfbad646908fb23591e2404481826742b651c9af7160"}
\ No newline at end of file diff --git a/vendor/ff/CHANGELOG.md b/vendor/ff/CHANGELOG.md new file mode 100644 index 000000000..418d660bb --- /dev/null +++ b/vendor/ff/CHANGELOG.md @@ -0,0 +1,109 @@ +# 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.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<Self>`. +- `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<V>` 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<Self>` 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<R: RngCore + ?Sized>(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 000000000..49a974693 --- /dev/null +++ b/vendor/ff/Cargo.toml @@ -0,0 +1,64 @@ +# 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.12.1" +authors = ["Sean Bowe <ewillbefull@gmail.com>", "Jack Grigg <thestr4d@gmail.com>"] +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.12.1" +optional = true + +[dependencies.rand_core] +version = "0.6" +default-features = false + +[dependencies.subtle] +version = "2.2.1" +features = ["i128"] +default-features = false +[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 000000000..1e5006dc1 --- /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 000000000..ed3a13fdd --- /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 000000000..6004f6e88 --- /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.12" +``` + +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.12", 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 000000000..3ebf789f5 --- /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 000000000..c479f9d49 --- /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<Item = &'a mut F: Field + ConstantTimeEq>` 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<F: Field> { + /// 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<F> for I +where + F: Field + ConstantTimeEq, + I: IntoIterator<Item = &'a mut F>, +{ + 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.ct_eq(&F::zero())); + } + acc = acc.invert().unwrap(); + let allinv = acc; + + for (tmp, p) in tmp.into_iter().rev() { + let skip = p.ct_eq(&F::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<F>(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.ct_eq(&F::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.ct_eq(&F::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<F, T, TE, TS>( + 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.ct_eq(&F::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.ct_eq(&F::zero()); + acc = F::conditional_select(&(acc * *p), &acc, skip); + *p = F::conditional_select(&tmp, &p, skip); + } + + allinv + } +} diff --git a/vendor/ff/src/lib.rs b/vendor/ff/src/lib.rs new file mode 100644 index 000000000..4ccd0de87 --- /dev/null +++ b/vendor/ff/src/lib.rs @@ -0,0 +1,298 @@ +//! 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::*; + +#[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::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<V> = BitArray<V, Lsb0>; + +/// This trait represents an element of a field. +pub trait Field: + Sized + + Eq + + Copy + + Clone + + Default + + Send + + Sync + + fmt::Debug + + 'static + + ConditionallySelectable + + ConstantTimeEq + + Add<Output = Self> + + Sub<Output = Self> + + Mul<Output = Self> + + Neg<Output = Self> + + for<'a> Add<&'a Self, Output = Self> + + for<'a> Mul<&'a Self, Output = Self> + + for<'a> Sub<&'a Self, Output = Self> + + MulAssign + + AddAssign + + SubAssign + + for<'a> MulAssign<&'a Self> + + for<'a> AddAssign<&'a Self> + + for<'a> SubAssign<&'a Self> +{ + /// Returns an element chosen uniformly at random using a user-provided RNG. + fn random(rng: impl RngCore) -> Self; + + /// Returns the zero element of the field, the additive identity. + fn zero() -> Self; + + /// Returns the one element of the field, the multiplicative identity. + fn one() -> 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<Self>; + + /// Returns the square root of the field element, if it is + /// quadratic residue. + fn sqrt(&self) -> CtOption<Self>; + + /// Exponentiates `self` by `exp`, where `exp` is a little-endian order + /// integer exponent. + /// + /// **This operation is variable time with respect to the exponent.** If the + /// exponent is fixed, this operation is effectively constant time. + fn pow_vartime<S: AsRef<[u64]>>(&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 prime field. +pub trait PrimeField: Field + From<u64> { + /// 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<Self> { + 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) + } + + /// 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<Self>; + + /// 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> { + 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() + } + + /// 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; + + /// Returns 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 method MUST ensure that this is the generator used to + /// derive `Self::root_of_unity`. + /// + /// [SageMath]: https://www.sagemath.org/ + fn 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; + + /// Returns the `2^s` root of unity. + /// + /// It can be calculated by exponentiating `Self::multiplicative_generator` by `t`, + /// where `t = (modulus - 1) >> Self::S`. + fn root_of_unity() -> 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<Self::ReprBits>; + + /// Returns the bits of the field characteristic (the modulus) in little-endian order. + fn char_le_bits() -> FieldBits<Self::ReprBits>; +} + +/// 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 000000000..bfa2cd2df --- /dev/null +++ b/vendor/ff/tests/derive.rs @@ -0,0 +1,88 @@ +//! 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 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); + } + } +} |