saymrwulf/pasta_curves-source
1
0
Fork 0
mirror of https://github.com/saymrwulf/pasta_curves-source.git synced 2026-09-03 19:53:40 +00:00
Code Issues Projects Releases Packages Wiki Activity Actions
807 commits 1 branch 0 tags 1.7 MiB
Commit graph

504 commits

Author SHA1 Message Date
Jack Grigg
96116e20e5 Annotate docs with required feature flags 2021-12-07 14:31:27 +00:00
Jack Grigg
a91e262235 Document that the generator in SqrtRatio::sqrt_ratio might change 2021-09-30 13:57:59 +01:00
Jack Grigg
32cc10db46 Move FieldExt::get_lower_32 to SqrtRatio trait 
It is only used internally by the table-based square root impl, and we
should probably refactor this further, but for now it can live in the
sqrt extension trait.
 2021-09-30 13:57:59 +01:00
Jack Grigg
3a6f71d2f0 Remove FieldExt::{from_bytes, read, to_bytes, write} 
- `ff::PrimeField::{from_repr, to_repr}` are direct replacements for
  `FieldExt::{from_bytes, to_bytes}`.
- `FieldExt::{read, write}` were added for reading and writing `halo2`
  proofs, but `halo2::transcript` now handles this internally.
 2021-09-23 14:45:02 +01:00
Jack Grigg
ad0360bc1c Remove FieldExt::from_u64 2021-09-23 14:45:02 +01:00
Jack Grigg
11c5ddbc02 Remove FieldExt::{RESCUE_ALPHA, RESCUE_INVALPHA} 2021-09-23 14:45:02 +01:00
Jack Grigg
e31787d462 Remove unnecessary bounds on CurveExt 
They are already bounds on `group::Group`, which `CurveExt` inherits
via `group::prime::PrimeCurve`.
 2021-09-23 14:45:02 +01:00
Jack Grigg
1b2f581ac1 Move square-root operations from FieldExt into a separate trait 2021-09-23 14:45:02 +01:00
Jack Grigg
0c58a40a98 Remove pasta_curves::arithmetic::Field 2021-09-23 14:44:10 +01:00
Jack Grigg
aeda766c34 Remove FieldExt::ROOT_OF_UNITY 
We can use the `ff::PrimeField::root_of_unity` method everywhere we
currently use this associated constant. If there is a more general
need for accessing this as an associated constant, we should consider
that for `ff::PrimeField`.
 2021-09-23 14:44:10 +01:00
str4d
2b350118b0
Fix naming of Tonelli-Shanks 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
 2021-09-21 10:44:07 +12:00
Jack Grigg
9999964d17 Add no-std support 
We re-introduce the Tonelli-Shank square root algoritm that was removed
in zcash/halo2#120, to use in no-std mode (the table-based impl requires
allocations, and also uses 29kiB of memory which is a problem for
constrained environments that typically need no-std).
 2021-09-20 18:56:23 +01:00
Jack Grigg
8fabb44ad4 fields: Use ff::PrimeField instead of FieldExt where possible 2021-09-20 17:41:46 +01:00
Jack Grigg
6a47700b1d fields: Ensure that trait impl dependencies match trait bounds 
The `FieldExt` trait was originally the only trait implemented in this
crate. When we added `ff` support, we reworked `FieldExt` to be an
extension trait on top of `ff::PrimeField`, but left the existing impls
in `FieldExt`. This resulted in some circular dependencies that prevent
us from making `FieldExt` conditional (e.g. for no-std support).

This commit removes the cycles like so:

- `ff::PrimeField::{from_repr, to_repr}` were implemented as calls to
  `FieldExt::{from_bytes, to_bytes}`. The field encoding/decoding logic
  is moved into the `ff::PrimeField` trait impl, and `FieldExt` now
  calls into `ff::PrimeField`.

- `ff::Field::sqrt` was implemented in terms of `FieldExt::sqrt_alt`.
  Given that the latter is a trivial wrapper around the `SqrtTables`
  implementation, we duplicate the call to eliminate the cycle.

- `ff::Field::random` used `FieldExt::from_bytes_wide`, which wraps
  either `Fp::from_u512` or `Fq::from_u512`. We now use these internal
  methods directly.
 2021-09-20 17:41:46 +01:00
porcuquine
65a138cd77 Re-export group crate. 2021-09-02 13:19:32 -07:00
Jack Grigg
fd7a6edbb1 ff 0.11, group 0.11 2021-09-02 18:10:05 +01:00
Jack Grigg
43251286c0 Enable Pasta curve elements to be used with group::Wnaf 2021-08-06 01:23:27 +01:00
Jack Grigg
a6b018fb0e impl CofactorCurve for Pallas and Vesta 
They already implement CofactorGroup (trivially, with the prime-order
subgroup being Self); this just enables Pallas and Vesta to be used in
cofactor-aware protocols that also want to leverage the affine point
representation.
 2021-06-04 00:54:39 +01:00
Jack Grigg
38db112596 Fix clippy lints 2021-06-01 23:34:22 +01:00
Jack Grigg
bc20c5826b Migrate to ff 0.10.0 2021-06-01 23:31:00 +01:00
Jack Grigg
ccbfaf6a20 Remove large temprary stack allocations from SqrtTables::new 2021-04-28 14:21:45 +12:00
Jack Grigg
b016b972f8 Replace (x, y) tuple with Coordinates struct 
The previous `CurveAffine::get_xy` method returned the coordinates as
`CtOption<(C::Base, C::Base)>`. However, `ConditionallySelectable` is
not implemented for any tuple or array types, making it impossible to
use any of the useful `CtOption` methods like `and_then`. We replace it
with `CurveAffine::coordinates -> CtOption<Coordinates<Self>>` and
`impl ConditionallySelectable for Coordinates` to enable operating over
coordinates in constant time.
 2021-04-18 09:21:18 +12:00
Daira Hopwood
a1194672c5 Update hash_to_field to correct a discrepancy with the Hashing to Elliptic Curves Internet Draft 
pointed out in the NCC audit.

Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-03-27 14:39:39 +00:00
Jack Grigg
901ef2381e clippy: Allow binary operators in Mul impls for curves 
We use binary operators specifically to implement constant-time scalar
multiplication.
 2021-03-03 22:00:22 +00:00
Jack Grigg
a3921fd38c clippy: Allow too-many-arguments on F*::montgomery_reduce 
We need to reduce from eight limbs to four, so we need eight arguments.
 2021-03-03 22:00:22 +00:00
Jack Grigg
c13fc16ead clippy: Allow single-character names where necessary 2021-03-03 22:00:22 +00:00
Jack Grigg
b06937103d clippy: Use *Assign to implement arithmetic::Group trait 2021-03-03 22:00:22 +00:00
Jack Grigg
d40ed36d50 Move Pasta implementations into root 2021-03-03 21:59:08 +00:00
Jack Grigg
b36356667f Rename crate to pasta_curves and remove halo2 code 2021-03-03 21:59:08 +00:00
str4d
5e05845936
Remove unnecessary identity check from Group::random impl 
Co-authored-by: ebfull <ewillbefull@gmail.com>
 2021-03-03 11:11:13 +13:00
Jack Grigg
62e50ae6bd Fix Group::random implementation for Pallas and Vesta 
Also removes the broken CurveAffine::from_bytes_wide and unused
CurveAffine::to_bytes_wide methods.
 2021-03-02 21:29:59 +00:00
Jack Grigg
0a4db20d82 impl group::cofactor::CofactorGroup for Pallas and Vesta 
Prime-order groups can be treated as a group with a cofactor of 1,
allowing them to be used in cofactor-aware protocols like RedDSA.
 2021-03-01 20:27:34 +00:00
Sean Bowe
cb59a40ff8
Move PLONK integration tests into the tests subdirectory. 2021-02-26 08:22:19 -07:00
Sean Bowe
ef86a936ff
Remove print statements from tests. 2021-02-26 08:22:13 -07:00
Sean Bowe
d92b1c4fb9
Relocate computation of the degree of the constraint system to the ConstraintSystem struct. 2021-02-26 08:22:05 -07:00
Jack Grigg
e41fd7ca12 Move SHA-256 gadget and chip into examples 2021-02-25 20:01:44 +00:00
Jack Grigg
c64346467b Add Table16 circuit layout example 2021-02-25 20:01:44 +00:00
Jack Grigg
3fa36d7a60 Add test for circuit_dot_graph using SHA-256 2021-02-25 20:01:44 +00:00
therealyingtong
5f4a08898e SHA-256 benchmarks 2021-02-25 20:01:44 +00:00
therealyingtong
a5ac5b3ed3 Add Compression test 2021-02-25 20:01:44 +00:00
therealyingtong
46b5ddcc68 Compression subregion_digest assignments 2021-02-25 20:01:44 +00:00
therealyingtong
b47b2e436b Compression subregion_main assignments 2021-02-25 20:01:44 +00:00
therealyingtong
05c6ebd42d Compression subregion_initial assignments 2021-02-25 20:01:44 +00:00
therealyingtong
4d7c717107 Add utils for Compression assignments 2021-02-25 20:01:44 +00:00
therealyingtong
3778266eeb Add Compression gates 2021-02-25 20:01:44 +00:00
therealyingtong
5951ae6516 Add Compression 2021-02-25 20:01:44 +00:00
therealyingtong
f6af03c953 Add MessageSchedule test 2021-02-25 20:01:44 +00:00
therealyingtong
6f703d5cc3 MessageSchedule subregion3 assignments 2021-02-25 20:01:44 +00:00
therealyingtong
931d55a5bb MessageSchedule subregion2 assignments 2021-02-25 20:01:44 +00:00
therealyingtong
65f7707a28 MessageSchedule subregion1 assignments 2021-02-25 20:01:44 +00:00
therealyingtong
88379fa62f Add MessageSchedule gates and assign fixed column cells 2021-02-25 20:01:44 +00:00
therealyingtong
fc4f3576a0 Add utils for common MessageSchedule assignments 2021-02-25 20:01:44 +00:00
therealyingtong
feedffa2b2 Add MessageSchedule 2021-02-25 20:01:44 +00:00
therealyingtong
570f90e4ee SHA-256 chip that uses a 2^16 lookup table 
Co-authored-by: Jack Grigg <jack@electriccoin.co>
 2021-02-25 20:01:44 +00:00
Jack Grigg
b4feff8272 Remove ECC gadgets and instructions 
Migrated to the orchard crate:
https://github.com/zcash/orchard/pull/22
 2021-02-25 18:17:50 +00:00
Jack Grigg
bd17c726ac Add a Selector type 
This currently just wraps a `Column<Fixed>`, but enables us to start
writing circuits that can later have their selector usage optimised.
 2021-02-25 15:28:29 +00:00
str4d
9467a03ae2
Merge pull request #209 from zcash/ecc-gadget-fixedpoints 
Store `Loaded` chip state in chip
 2021-02-26 04:24:28 +13:00
therealyingtong
4f17322c2d Allow Chip::load to return state that the Layouter will hold 
This enables chips that e.g. want to load multiple lookup tables into
the same columns to store state about where each table was layed out.

Co-authored-by: Jack Grigg <jack@electriccoin.co>
 2021-02-24 23:28:18 +08:00
therealyingtong
6cbf32c2cd Add FixedPoints type and trait to ECC gadget 2021-02-24 23:24:53 +08:00
therealyingtong
4ae21a905d Update tests 2021-02-24 00:21:12 +08:00
therealyingtong
5a341b0f8f Modify Assignment::copy() to take Column<Any> instead of usize 2021-02-24 00:18:22 +08:00
therealyingtong
d82a0c85b1 Modify Assignment::copy() to take Permutation instead of usize 2021-02-24 00:17:29 +08:00
therealyingtong
340fb2b6df Move Permutation struct from crate::circuit -> plonk::circuit 2021-02-24 00:17:29 +08:00
ebfull
20bd44f854
Merge pull request #191 from zcash/sha-256-gadget-namespacing 
Alter the SHA-256 gadget to require namespacing
 2021-02-23 08:49:03 -07:00
ebfull
98896560fd
Merge pull request #203 from zcash/newtype-region-idx 
Add circuit::RegionIndex and circuit::RegionStart newtypes
 2021-02-23 08:20:19 -07:00
Sean Bowe
12230a49e0
Move CURVE_ID to CurveExt. 2021-02-22 16:30:05 -07:00
Sean Bowe
75bb8121fb
Switch to domain prefix based on what is suggested in #182 by @daira. 2021-02-22 16:13:11 -07:00
Sean Bowe
1078f854e3
Remove BLAKE2B_PERSONALIZATION constant. 2021-02-22 15:53:22 -07:00
Sean Bowe
5503517ac1
Produce URS using hashtocurve logic. 2021-02-22 15:50:01 -07:00
Sean Bowe
df8dcce042
Add CurveExt and AffineExt associated types to project Group trait implementations. 
Co-authored-by: Jack Grigg <jack@electriccoin.co>
 2021-02-22 15:47:57 -07:00
Jack Grigg
b4ed5295fe Migrate to group traits 
The `Curve` trait is now `CurveExt: group::prime::PrimeCurve`, and
`CurveAffine` is now `CurveAffine: group::prime::PrimeCurveAffine`.

There is no `CurveAffine` trait in `group`, and it's a widely-used
trait in this crate, so we don't rename it to `CurveAffineExt`.
 2021-02-22 20:20:23 +00:00
Jack Grigg
55fb581f17 Define hash-to-curve over Curve, not CurveAffine 
This removes an unnecessary layer of indirection from the type system,
and ensures that these APIs depend on the halo2-specific trait with the
extensions we require.
 2021-02-22 20:12:10 +00:00
Jack Grigg
082d66d6e7 pasta: Reorganize the curve macro 
This will make the migration to group easier to review.
 2021-02-22 20:05:12 +00:00
Jack Grigg
7037d55320 Rename Curve and CurveAffine properties to match group traits 2021-02-22 20:05:08 +00:00
Jack Grigg
81a7936d99 pasta: Split halo2-specific curve-specific logic into a separate macro 2021-02-22 18:53:27 +00:00
Sean Bowe
e93de2c285
Avoid heap allocations within hash_to_curve. 2021-02-22 10:15:30 -07:00
Daira Hopwood
16e5f96f3f Fix a clippy lint. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-02-22 16:02:38 +00:00
Daira Hopwood
e408a351d5 Remove a redundant bool::from. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-02-21 21:43:11 +00:00
Daira Hopwood
7dc21f4727 Repair test vectors and add tests for map_to_curve_simple_swu. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-02-21 21:01:19 +00:00
Daira Hopwood
24def7ce02 Fix case where the input to map_to_curve_simple_swu is 0, and remove unneeded B_OVER_ZA constants. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-02-21 21:00:50 +00:00
Daira Hopwood
642aad68a3
Revert comment changes that are no longer relevant, now that we don't expose the isogenous curves in the API 2021-02-20 21:54:50 +00:00
Daira Hopwood
a14eccc13d Remove unused hash support for Pasta Fp and Fq. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-02-20 21:51:32 +00:00
therealyingtong
84f732acb4 Add circuit::RegionIndex and circuit::RegionStart newtypes 2021-02-20 21:26:42 +08:00
Daira Hopwood
8b8dbbe2bb Refine type of buf in hash_to_field as suggested by @ebfull. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-02-19 15:52:11 +00:00
Daira Hopwood
6d8c899e16 Rename map_to_curve to map_to_curve_simple_swu. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-02-19 15:52:11 +00:00
Daira Hopwood
785ad5375c Switch from XOF:SHAKE128 to XMD:BLAKE2b. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-02-19 15:52:11 +00:00
Daira Hopwood
25ea5d07f7 Fix error in doc comment. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-02-19 15:52:11 +00:00
Daira Hopwood
9aa3327a0a Fix clippy lints. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-02-19 15:52:11 +00:00
Sean Bowe
c17cd408f1 Fix point doubling on isogenous curve and add test for isogeny of identity. 2021-02-19 15:52:11 +00:00
Sean Bowe
d14d2314a1 Remove isogenous curve from public API. 2021-02-19 15:52:11 +00:00
Sean Bowe
b488355e13 Add example to hash_to_curve doc comment. 2021-02-19 15:52:11 +00:00
Sean Bowe
dc069dff31 Rename hasher to hash_to_curve. 2021-02-19 15:52:11 +00:00
Sean Bowe
f6f008f905 Remove MINUS_B_OVER_A constant. 2021-02-19 15:52:11 +00:00
Sean Bowe
c48229ce0f Remove dependency on byteorder crate 2021-02-19 15:52:11 +00:00
Sean Bowe
783e602e85 Remove SimplifiedSWUWithDegree3Isogeny structure because state is no longer necessary. 2021-02-19 15:52:11 +00:00
Sean Bowe
83e2656c3e Introduce Curve::hasher abstraction. 2021-02-19 15:52:11 +00:00
Sean Bowe
68a7a19d3b Move hashtocurve module into pasta module. 2021-02-19 15:52:11 +00:00
Sean Bowe
b134a73ef5 Hardcode isogeny constants and constants for hash to curve. 2021-02-19 15:52:11 +00:00
Sean Bowe
5b33ff9cab Consolidate the hashtocurve module traits into a single structure. 2021-02-19 15:52:11 +00:00
Sean Bowe
e4e8aef5b6 Simplify HashToCurve trait. 2021-02-19 15:52:11 +00:00