zec
/
pasta
mirror of https://github.com/zcash/pasta.git
1
0
Fork 0
Code Issues Projects Releases Wiki Activity
108 Commits 2 Branches 0 Tags 6.1 MiB
Commit Graph

108 Commits

Author SHA1 Message Date
Daira Hopwood f0f7068552 Add test vectors for map_to_simple_swu. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-04-27 14:24:13 +01:00
Daira Hopwood 6a4f42ce25 Resolve an ambiguity in the Internet Draft 
(https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-10.html#name-finding-z-for-the-shallue-va).

Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-04-21 13:14:15 +01:00
Daira Hopwood 71094393e8 Sage-on-Python 3 compatibility fixes. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-04-21 12:32:27 +01:00
Daira Hopwood d10932faf0 Add sinsemilla.sage. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-04-02 17:52:06 +01:00
ebfull bdf50d9ede
Merge pull request #2 from zcash/hashtocurve-blocksize 
hashtocurve.sage: the block size of BLAKE2b is 128 bytes, not 64 bytes.
 2021-04-01 16:21:05 -06:00
Daira Hopwood 571dab6596 Update the Pallas test vector so that it exercises both the gx1 square and non-square branches. 
This matches the comment in the Rust code:

// This test vector is chosen so that the first map_to_curve_simple_swu takes the gx1 square
// "branch" and the second takes the gx1 non-square "branch" (opposite to the Vesta test vector).

The existing test vector for Vesta, by coincidence (1 in 4 chance), did not need to be changed.

Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-03-27 13:53:00 +00:00
Daira Hopwood 3b511bf281
Merge pull request #1 from zcash/patch-base-tables 
[base_tables.sage] Remove -r personalisations from Sinsemilla Q
 2021-03-22 22:36:57 +00:00
Daira Hopwood 044baaab1f hashtocurve.sage: the block size of BLAKE2b is 128 bytes, not 64 bytes. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-03-22 22:34:29 +00:00
Daira Hopwood f744721899 Add right-to-left addition chains for 5^-1 (mod p-1, q-1). 
These trade more multiplications (but fewer than naive rtl) for greater potential parallelism,
since almost all of the multiplications can be done in parallel with squarings.

Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-03-19 20:55:49 +00:00
therealyingtong 3e599445be Remove -r personalisations from Sinsemilla Q 
These don't participate in SinsemillaHashToPoint.
 2021-03-15 12:54:38 +08:00
Daira Hopwood dfeb3f7fbd base_tables.sage: corrections; window tables are not needed for Sinsemilla bases. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-03-06 22:52:03 +00:00
Daira Hopwood b34ba21d5d Add base_tables.sage: compute the tables for fixed-base scalar multiplication. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-03-06 22:08:43 +00:00
Daira Hopwood de872b47f7 hashtocurve.sage: minor changes to get access to the Sage EllipticCurve point from hash_to_*_jacobian. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-03-06 22:04:22 +00:00
Daira Hopwood b4a8d29ca1 subgroupcheck.sage: ensure that progress dots are printed consistently by all threads. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-03-01 19:06:09 +00:00
Daira Hopwood c51449a535 Change to XMD:BLAKE2b, and use the same test vectors as the Rust implementation. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-02-21 21:11:19 +00:00
Daira Hopwood 779c3b117e Fix the case where the input to map_to_curve_simplified_swu is 0. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-02-21 21:10:23 +00:00
Daira Hopwood 798e1e9a89 Remove non-ASCII characters from subgroupcheck.sage. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-02-19 19:00:04 +00:00
Daira Hopwood 8f8d0ba399 Add subgroupcheck.sage. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-02-19 18:56:20 +00:00
Daira Hopwood fb448f3538 Add isogeny for Vesta. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-01-13 01:11:34 +00:00
Daira Hopwood 540fe946c1 Fix unified addition. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-01-02 21:01:33 +00:00
Daira Hopwood 8e22490f43 hashtocurve.sage: make DEBUG = True work. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-01-02 02:23:55 +00:00
Daira Hopwood 3523aee87f hashtocurve.sage: fix a bug due to inadvertently relying on values calculated by debug code. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-01-02 02:22:01 +00:00
Daira Hopwood fd7283a979 Make map_to_curve_simple_swu take a single input again (since we no longer need batch inversion). 
Also make it clearer that we don't depend on Sage's elliptic curve impl except for debugging.

Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-01-02 00:50:42 +00:00
Daira Hopwood c0f2b2d8b6 Correct a comment. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-01-02 00:20:36 +00:00
Daira Hopwood 4a3a34feea Improve comments and cost accounting. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-01-01 19:44:32 +00:00
Daira Hopwood 50d3e83467 Implement the optimization from [WB2019, section 4.2] that removes the remaining inversion. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-01-01 03:37:41 +00:00
Daira Hopwood 391e67f250 hashtocurve.sage: correct a comment. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-12-31 15:26:20 +00:00
Daira Hopwood 112983e667 hashtocurve: allow use of the sqrt optimization with the Z recommended by the Internet Draft. 
This also makes the sqrt and hash-to-curve implementations depend on each other less strongly.

Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-12-31 13:45:35 +00:00
Daira Hopwood ef3405dd20 Add an optimization from [WB2019, section 4.2] that saves a square root for each map_to_curve. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-12-31 03:35:50 +00:00
Daira Hopwood 71afc68f7d hashtocurve.sage: add Jacobian coordinate implementation that avoids two of the three inversions. 
Do not base production code on this yet!

Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-12-30 16:09:25 +00:00
Daira Hopwood 7df33f4ce4 hashtocurve.sage: more realistic use of Montgomery's trick. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-12-29 17:58:50 +00:00
Daira Hopwood 96fd2c794e [WIP] Add a prototype implementation of hash-to-curve. This intends to implement the Internet Draft but has not been checked. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-12-29 17:58:50 +00:00
Daira Hopwood 7afb4e0d75 Add variant of the table-based square root that uses 16-entry tables. 
This could in principle be made truly constant-time.

Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-12-29 12:50:16 +00:00
Daira Hopwood be58b5e128 Addition chains for 7^-1 (mod p-1, q-1). 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-12-12 22:44:56 +00:00
Daira Hopwood ad02b756cd Addition chains for 5^-1 (mod p-1, q-1). 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-12-12 16:46:32 +00:00
Daira Hopwood 56945c09e0 Import sys explicitly rather than relying on sage to do it. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-11-30 13:28:25 +00:00
Daira Hopwood bf740d64b8 Add some nice assertions and tests to make it clearer what is going on. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-11-30 13:17:18 +00:00
Daira Hopwood 7bf9015957 Assert that there are no collisions in invtab. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-11-30 12:00:50 +00:00
Daira Hopwood 79738d2cb7 Improve the perfect hash function. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-11-30 10:43:17 +00:00
Daira Hopwood bda5810e46 Python 2 compatibility. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-11-30 10:42:55 +00:00
Daira Hopwood a8b6b48b91 Include the cost of checking the result in the squaring cost. 
(The algorithm will return a nonsense result for non-squares if we don't do this check.)

Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-11-29 20:47:58 +00:00
Daira Hopwood 25dd9f0ed9 squareroottab.sage: remove unused instance variables. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-11-29 20:45:12 +00:00
Daira Hopwood 223b60825c Save one squaring. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-11-29 20:38:58 +00:00
Daira Hopwood d45dd14238 Make squareroot.sage more similar to squareroottab.sage to facilitate comparison. 
(This is actually a slight pessimisation, but we're not going to use the non-table-based variant.)

Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-11-29 20:35:36 +00:00
Daira Hopwood e7f9d2cef6 squareroot.sage: turn off VERBOSE and EXPENSIVE. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-11-29 20:04:14 +00:00
Daira Hopwood b26d051c59 Slightly optimize addition chain for Fq. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-11-29 20:03:25 +00:00
Daira Hopwood 5bfaa90bf7 squareroottab.sage: inlining and shift microoptimizations. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-11-29 19:29:32 +00:00
Daira Hopwood 49878117db squareroottab.sage: inline eval, and remove an unused part of gtab[3]. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-11-29 19:03:43 +00:00
Daira Hopwood debab754cb squareroottab.sage: remove redundant code. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-11-29 18:45:04 +00:00
Daira Hopwood 4f47706877 Add table-based variant of square root. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2020-11-29 18:43:07 +00:00