zec
/
orchard
mirror of https://github.com/zcash/orchard.git
1
0
Fork 0
Code Issues Projects Releases Wiki Activity
1,220 Commits 5 Branches 11 Tags 24 MiB
Commit Graph

130 Commits

Author SHA1 Message Date
therealyingtong 78b0ec4e7b [book] Sinsemilla: reintroduce fixed_y_q column. 
Loading fixed_y_q into an advice column introduces an additional
row. Instead, we load it into a fixed column.

Co-authored-by: Jack Grigg <jack@electriccoin.co>
 2021-07-24 23:15:17 +08:00
ying tong 6c55e1a7e3
[book] Fix updates to Sinsemilla writeup. 2021-07-23 20:34:16 +08:00
therealyingtong 7866623a1b [book] Undo selector optimisation in variable-base scalar mul 
Previously, we were using a non-binary selector q_mul = {1, 2, 3}
to switch between three cases. Now, we replace this with three
binary selectors.
 2021-07-22 22:39:17 +08:00
therealyingtong c5cda9481d [book] Undo selector optimisations in Sinsemilla 
- Instead of defining a synthetic q_S3 based on a combination of
  of q_S1, q_S2, we simply create another selector q_S3.
- Instead of using fixed_y_q as a nonbinary selector, replace it
  with q_S4 and copy the fixed value into a row above.

Co-authored-by: Daira Hopwood <daira@jacaranda.org>
 2021-07-22 22:19:01 +08:00
ying tong c23897ea8d
Apply suggestions from code review 
Co-authored-by: str4d <jack@electriccoin.co>
 2021-07-19 19:01:06 +08:00
Daira Hopwood 43ffa37740 [book] Nullifiers: the scalar is (...) mod p, not ... (mod p). 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-07-12 20:24:18 +01:00
Daira Hopwood c76358769c book/src/design/nullifiers.md: cosmetics (make the table fit). 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-07-12 20:20:00 +01:00
therealyingtong 2dd23f47b8 [book] Update constraints for short signed fixed-base mul. 
Previously, we witnessed the magnitude of a short signed scalar
directly as three-bit windows. Now, we decompose and range-constrain
it using a running sum.
 2021-07-12 11:58:32 +08:00
therealyingtong d9f134ac4b [book] Details and formatting changes. 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
 2021-07-09 10:09:10 +08:00
ying tong 2febafbdfe
Apply suggestions from code review 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
Co-authored-by: str4d <jack@electriccoin.co>
 2021-07-08 16:40:44 +08:00
therealyingtong afc8d9a142 [book] Eliminate alpha_0 lookup decomposition when checking canonicity of base field element used in fixed-base mul. 2021-07-08 11:12:13 +08:00
therealyingtong 091592e110 [book] Document canonicity check for fixed-base scalar mul when base field element is used as the scalar. 2021-07-07 17:10:18 +08:00
therealyingtong 32f9622c23 [book] Document lookup range check and its use in overflow check. 2021-07-03 19:30:27 +08:00
ying tong 6479598b27
Apply suggestions from code review 
Co-authored-by: str4d <jack@electriccoin.co>
 2021-07-03 18:37:35 +08:00
therealyingtong 2b4d9fda49 [book] Correct q_mul = 3 case. 
Co-authored-by: Jack Grigg <jack@electriccoin.co>
 2021-07-02 22:44:01 +08:00
therealyingtong 1a531cf619 [book] Correct hi and lo ranges in constraint table 
Co-authored-by: Jack Grigg <jack@electriccoin.co>
 2021-07-02 21:41:31 +08:00
therealyingtong 802334892d [book] Constrain first and last rows in incomplete addition secton of variable-base scalar mul. 
Co-authored-by: Jack Grigg <jack@electriccoin.co>
 2021-07-02 17:28:33 +08:00
therealyingtong 902dbbb700 [book] Fix window table sum expression in fixed-base scalar mul. 
Co-authored-by: Jack Grigg <jack@electriccoin.co>
 2021-07-02 16:43:29 +08:00
therealyingtong 68acc33cae [book] Document overflow check for variable-base scalar mul. 2021-07-02 00:18:27 +08:00
str4d d5f3256785
Merge branch 'main' into book-ecc-gadget 2021-07-01 13:47:30 +01:00
str4d 6c34956c18
book: Remove superfluous checkmarks 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
 2021-07-01 13:46:48 +01:00
Daira Hopwood 3543bab39d
Merge pull request #82 from zcash/book-sinsemilla-gadget 
[book] Add Sinsemilla gadget description
 2021-06-20 01:07:58 +01:00
Daira Hopwood 9adeead975 [book] Make the order of advice columns for Sinsemilla the same as in the code. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-06-19 15:35:34 +01:00
Daira Hopwood 9dc909e842 [book] Formatting. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-06-19 13:37:07 +01:00
Daira Hopwood 2a8fe30fa8 [book] Clarify that x_Q, z_0, z'_0, etc. are copied in using equality constraints. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-06-19 13:32:11 +01:00
Daira Hopwood 48573705dc [book] Adjust the definition of m_{i+1} so that the last z_n does not need to be constrained to 0. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-06-19 08:53:41 +01:00
Daira Hopwood 22036e9f41 [book] More formatting. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-06-18 22:49:46 +01:00
Daira Hopwood aac10b816f [book] Formatting. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-06-18 22:45:50 +01:00
Daira Hopwood dc021a2ef1 [book] Merge two similar paragraphs. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-06-18 22:20:09 +01:00
Daira Hopwood 82316b607b [book] Update the Sinsemilla constraints to handle the gap between field elements correctly. 
This also changes i to be zero-based, which is more consistent with the spec.

Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-06-18 22:12:48 +01:00
Daira Hopwood 4cd0082294
Apply suggestions from code review 
Co-authored-by: str4d <jack@electriccoin.co>
 2021-06-18 21:27:55 +01:00
therealyingtong beaf4490f1 sinsemilla.md: Correct y_{A,i} and y_{P,i} formulas in gate specification 2021-06-14 21:30:51 +08:00
therealyingtong ab454f4fb2 [book] commitment-tree.md: Update Uncommitted^Orchard from 0 -> 2. 2021-06-11 18:45:25 +08:00
therealyingtong 1ea8397a7c variable-base-scalar-mul.md: Disable book tests. 2021-06-09 18:44:57 +08:00
ying tong f46a2a4c40
Apply suggestions from code review 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
 2021-06-09 18:31:06 +08:00
therealyingtong 02a732b921 fixed-base-scalar-mul.md: Include G^{Orchard} fixed base 2021-06-09 18:27:34 +08:00
therealyingtong ab96225f0f ecc::addition.md: Update complete addition constraints. 
Add constraint analysis and proofs of completeness and soundness.
 2021-06-09 18:23:02 +08:00
therealyingtong 6edfa579be sinsemilla.md: Update comments about lookup degree. 2021-06-09 15:14:44 +08:00
ying tong a40030750c
Add references to protocol spec. 2021-06-09 14:59:16 +08:00
ying tong 191a3c6304
Apply suggestions from code review 
Co-authored-by: str4d <jack@electriccoin.co>
 2021-06-09 14:48:12 +08:00
therealyingtong 79b0307b87 Formatting fixes 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
 2021-05-27 13:59:15 +08:00
therealyingtong e2ac3715f1 Explain (k+2) offset in fixed-base window formulae 2021-05-27 13:33:06 +08:00
therealyingtong 12feacf417 Fix complete addition constraints 2021-05-25 14:07:36 +08:00
therealyingtong 2699703b02 Update fixed-base window formulae 2021-05-25 00:20:18 +08:00
therealyingtong 58e3da88c2 Document point doubling constraints 2021-05-23 10:26:55 +08:00
ying tong cdea8b1f67
Apply suggestions from code review 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
 2021-05-22 22:55:14 +08:00
str4d 9585c67ed2
book: Refine types on Commitments page 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
 2021-05-21 21:23:08 +01:00
therealyingtong 1a08d6e078 [book] Add Sinsemilla gadget description 2021-05-21 21:13:45 +08:00
ying tong 0903ae23e7
Use correct symbol in incomplete addition section 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
 2021-05-21 17:43:08 +08:00
Jack Grigg d0c16910d6 book: Document why ivk != 0 2021-05-11 19:14:52 +12:00
therealyingtong 1e0c644a81 Detail optimised variable-base scalar mul 2021-05-06 20:02:19 +08:00
ying tong e881b19b6a
Apply suggestions from code review 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
 2021-04-23 22:03:04 +08:00
therealyingtong b4c3805e22 Address further review comments. 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
Co-authored-by: str4d <jack@electriccoin.co>
 2021-04-22 17:39:27 +08:00
ying tong 33b4192c0d
Apply suggestions from code review 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
Co-authored-by: str4d <jack@electriccoin.co>
 2021-04-22 17:10:33 +08:00
str4d 632fa8dcf2
Merge pull request #68 from daira/daira-nullifiers 
[Book] Update nullifier explanation to include Extract_P
 2021-04-22 05:50:01 +01:00
Daira Hopwood 18bc70afa2 [Book] Explain the decision to exclude zero points and scalars for KA.Orchard. fixes #62 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-04-21 18:38:25 +01:00
Daira Hopwood f5bab61f81 Update nullifier explanation to include Extract_P. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-04-21 18:25:31 +01:00
therealyingtong 96d60b3f13 Move addition sections into ecc.rs 2021-04-17 12:53:10 +08:00
ying tong cd809c57dc
Apply suggestions from code review 
Co-authored-by: str4d <jack@electriccoin.co>
 2021-04-09 16:53:35 +08:00
ying tong 137066e056
Apply suggestions from code review 
Co-authored-by: str4d <jack@electriccoin.co>
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
 2021-04-09 16:51:14 +08:00
therealyingtong c074990bb9 [book] Document ECC gadget in circuit 2021-03-29 14:01:05 +08:00
Daira Hopwood 0191fa0a47 Orchard book: minimal description of unified addresses. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-03-27 17:08:39 +00:00
Jack Grigg f563c1636f book: Update commitment tree section with the design decision 2021-02-12 01:47:04 +00:00
str4d d541261507
Apply suggestions from review 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
 2021-02-12 08:09:45 +13:00
Jack Grigg adb377de7d book: Document design rationale for Orchard keys and addresses 2021-02-08 18:31:36 +00:00
str4d a2f85c7932
Apply editorial suggestions from code review 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
 2021-01-22 14:52:05 +13:00
Jack Grigg 18e039218b book: Note that we use 0 for uncommitted leaves in the commitment tree 2021-01-22 00:32:24 +00:00
Daira Hopwood d6fd00b5b3 Cosmetics and Markdown formatting. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-01-21 00:07:38 +00:00
Daira Hopwood 265ff91cc6 F might be Poseidon. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-01-21 00:07:21 +00:00
Daira Hopwood db071913b6 Explain in more detail the argument for Balance. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-01-21 00:06:50 +00:00
Daira Hopwood 3ca9704d30 Swap ak and nk in the input to ShortCommit^{ivk}. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2021-01-21 00:05:47 +00:00
Jack Grigg f3a36457d7 book: Add rationale for nullifier design 2021-01-20 14:12:38 +00:00
Jack Grigg 0abc0ef11a book: Revert to the previous nullifier design 
We examined the nullifier designs more closely, and determined that the
previously-selected design was actually fine, but for a somewhat-subtle
reason: even though an adversary with knowledge of a victim's full viewing
key could choose psi to cancel out Hash_nk(rho), the nullifier still
directly depends on rho via the note commitment.
 2021-01-20 14:06:03 +00:00
Jack Grigg 9410d14d0a book: Switch to a new nullifier design 
The previously-selected design was broken because an adversary with
knowledge of a victim's full viewing key could perform a Faerie Gold
attack: given knowledge of nk, they can choose psi to cancel out
Hash_nk(rho) and cause a collision.
 2021-01-09 00:22:52 +00:00
Jack Grigg 750bdfb700 book: Update definitions on nullifier page 2021-01-08 23:29:46 +00:00
Jack Grigg 0fcacf9af0 book: Start adding Orchard design notes 
Some of this content may move into the concepts section, or possibly into
a dedicated specification area, but for now the design section includes
our choices alongside the reasoning.
 2021-01-08 17:10:12 +00:00
Jack Grigg db24a2ac4d book: Add KaTeX support 2021-01-08 17:01:35 +00:00
Jack Grigg 10bae831eb Rename to Orchard 2021-01-08 16:51:10 +00:00
Jack Grigg 8e6d2a7023 Add initial book skeleton 2020-10-27 21:23:20 +00:00
Jack Grigg b975600b35 Initialise empty mdBook 2020-10-20 23:02:49 +01:00