Tracking: implement ALL THE SPEC

[hdevalence]

This issue tracks Zebra's progress implementing the entire Zcash protocol specification, indexed by spec section.

A checkbox means that that part of the specification describes something to implement. A checked box means that we have either implemented or otherwise resolved (e.g., by not implementing) that item. Leaf nodes are marked by – and correspond to implementable items. They should be followed by issue references that track the status of that issue, or a short explanation. A missing explanation or reference number means we have not yet taxonomized what work is do be done, if any, in connection to that section.

• 1. Introduction – nothing implementable
• 2. Notation – nothing implementable
• 3. Concepts
  • 3.1. Payment Addresses and Keys – Sprout keys and addresses #265, Sapling keys and addresses #266, Implement ZIP-32 Sapling and Orchard key derivation #267
  • 3.2. Notes – Sprout note encryption/decryption implementation. #181, Sapling/Orchard note encryption implementation. #269
    • 3.2.1 Note Plaintexts and Memo Fields – Sprout note encryption/decryption implementation. #181, Sapling/Orchard note encryption implementation. #269, Make Memo an enum type #250
  • 3.3. The Block Chain – Block, BlockHeader and Block messages #21
  • 3.4. Transactions and Treestates – Update Transaction type and message to support the Zcash changes from Bitcoin #13, Treestate type #290
  • 3.5. JoinSplit Transfers and Descriptions – Update Transaction definition. #105,
  • 3.6. Spend Transfers, Output Transfers, and their Descriptions – Update Transaction definition. #105
  • 3.7. Note Commitment Trees – Design Sprout note commitment trees. #36, Implement Sapling note commitment tree #286
  • 3.8. Nullifier Sets – Nullifier Set #289
  • 3.9. Block Subsidy and Founders' Reward - Check block subsidy (miner and founder's reward) rules as part of validation #297
  • 3.10. Coinbase Transactions – Add a CoinbaseData field, replacing Vec<u8>. #259, Validate that only the first transaction in a block is a coinbase transaction  #298, ZIP-213: Validate Shielded Coinbase Outputs like other shielded outputs #608 (Heartwood ZIP-213)
• 4. Abstract Protocol
  • 4.1. Abstract Cryptographic Schemes
    • 4.1.1. Hash Functions – pull as dependencies
    • 4.1.2. Pseudo Random Functions – pull as dependencies
    • 4.1.3. Authenticated One-Time Symmetric Encryption – pull as dependencies, alá librustzcash - ChaChaPoly
    • 4.1.4. Key Agreement – Pull in/wrap JubJub Diffie-Hellman for Sapling key agreement  #302, Pull in/wrap Curve25519 for Sprout key agreement #303
    • 4.1.5. Key Derivation – Implement Sprout key derivation  #300, Implement Sapling shared secret key derivation #301
    • 4.1.6. Signature
      • 4.1.6.1. Signature with Re-Randomizable Keys – RedJubJub signatures #125, Zcash-flavored Ed25519 #109
      • 4.1.6.2. Signature with Private Key to Public Key Monomorphism – RedJubJub signatures #125, Zcash-flavored Ed25519 #109
    • 4.1.7. Commitment – Implement Sprout Note Commitment Function #273, Implement Sapling Note Commitment Function #274, Implement Sapling Value Commitments #276
    • 4.1.8. Represented Group
    • 4.1.9. Hash Extractor – handled by JubJub lib
    • 4.1.10. Group Hash – handled by *25519, JubJub libs
    • 4.1.11. Represented Pairing
    • 4.1.12. Zero-Knowledge Proving System – proof types, Expose proof validation for BCTV14 type #304 , Implement verifiers that accept Groth16 types #305
  • 4.2. Key Components
    • 4.2.1. Sprout Key Components – Sprout keys and addresses #265, Implement ZIP-32 Sapling and Orchard key derivation #267, Implement Sprout key derivation  #300
    • 4.2.2. Sapling Key Components – Sapling keys and addresses #266, Implement ZIP-32 Sapling and Orchard key derivation #267, Implement Sapling shared secret key derivation #301
  • 4.3. JoinSplit Descriptions – Update Transaction definition. #105
  • 4.4. Spend Descriptions – Update Transaction definition. #105
  • 4.5. Output Descriptions – Update Transaction definition. #105
  • 4.6. Sending Notes - Implement EphemeralPrivateKey's for Orchard, Sapling, Sprout #2192 2192
    • 4.6.1. Sending Notes (Sprout) – Sprout note encryption/decryption implementation. #181
    • 4.6.2. Sending Notes (Sapling) – Sapling/Orchard note encryption implementation. #269
  • 4.7. Dummy Notes - probably doesn't exist in the wild yet
    • 4.7.1. Dummy Notes (Sprout) –
    • 4.7.2. Dummy Notes (Sapling) –
  • 4.8. Merkle Path Validity – Design Sprout note commitment trees. #36, Implement Sapling note commitment tree #286
  • 4.9. SIGHASH Transaction Hashing – Pull in/tidy up SIGHASH  #306
  • 4.10. Non-malleability (Sprout)
  • 4.11. Balance (Sprout)
  • 4.12. Balance and Binding Signature (Sapling) – Implement transaction binding signature verification key #318
  • 4.13. Spend Authorization Signature – Implement spend authorization signing. #319
  • 4.14. Note Commitments and Nullifiers – Sprout Nullifier #287, Sapling Nullifier #288, Nullifier Set #289
  • 4.15. Zk-SNARK Statements
    • 4.15.1. JoinSplit Statement (Sprout) – Validate JoinSplit proofs #322
    • 4.15.2. Spend Statement (Sapling) – Create a Spend Proof #320, Validate Spend Proofs #323
    • 4.15.3. Output Statement (Sapling) – Create Output Proof #321, Validate Output Proofs #324
  • 4.16. In-band secret distribution (Sprout) - Sprout Key Agreement and KDF #272
    • 4.16.1. Encryption (Sprout) – Sprout note encryption/decryption implementation. #181
    • 4.16.2. Decryption (Sprout) – Sprout note encryption/decryption implementation. #181
  • 4.17. In-band secret distribution (Sapling) - Sapling/Orchard Key Agreement and KDF #271
    • 4.17.1. Encryption (Sapling) – Sapling/Orchard note encryption implementation. #269
    • 4.17.2. Decryption using an Incoming Viewing Key (Sapling) – Sapling/Orchard note encryption implementation. #269
    • 4.17.3. Decryption using a Full Viewing Key (Sapling) – Sapling/Orchard note encryption implementation. #269
  • 4.18. Block Chain Scanning (Sprout) – Block Chain Scanning  #325
  • 4.19. Block Chain Scanning (Sapling) – Block Chain Scanning  #325
• 5. Concrete Protocol
  • 5.1. Caution
  • 5.2. Integers, Bit Sequences, and Endianness
  • 5.3. Constants
  • 5.4. Concrete Cryptographic Schemes
    • 5.4.1. Hash Functions
      • 5.4.1.1. SHA-256 and SHA256Compress Hash Functions – On release, upgrade to sha2=^0.8.2 #326
      • 5.4.1.2. BLAKE2 Hash Function –
      • 5.4.1.3. Merkle Tree Hash Function – Abstract MerkleCRH^Sprout Hash Function into its own function #329, Abstract MerkleCRH^Sapling Hash Function into its own function #330
      • 5.4.1.4. hSig Hash Function – Abstract out h_Sig hash function for sprout joinsplit verification #331
      • 5.4.1.5. CRHivk Hash Function – Abstract out the CRH^ivk hash function for Sapling incoming viewing key derivation #332
      • 5.4.1.6. DiversifyHash Hash Function – Abstract calling of jubjub::(grouphash) into DiversifierHash function #333
      • 5.4.1.7. Pedersen Hash Function – Pedersen Hash (at least for use in the Sapling merkle tree) #334
      • 5.4.1.8. Mixing Pedersen Hash Function - Notes, commitments, nullifiers, etc #596
      • 5.4.1.9. EquihashGenerator – Implement Equihash verification #335
    • 5.4.2. Pseudo Random Functions - finished in Notes, commitments, nullifiers, etc #596
    • 5.4.3. Authenticated One-Time Symmetric Encryption – Sprout note encryption/decryption implementation. #181, Sapling/Orchard note encryption implementation. #269
    • 5.4.4. Key Agreement and Derivation
      • 5.4.1.1. Sprout Key Agreement – Pull in/wrap Curve25519 for Sprout key agreement #303
      • 5.4.1.2. Sprout Key Derivation – Implement Sprout key derivation  #300
      • 5.4.1.3. Sapling Key Agreement – Pull in/wrap JubJub Diffie-Hellman for Sapling key agreement  #302
      • 5.4.1.4. Sapling Key Derivation – Implement Sapling shared secret key derivation #301
    • 5.4.5. JoinSplit Signature – Zcash-flavored Ed25519 #109
    • 5.4.6. RedDSA and RedJubjub – RedJubJub signatures #125
      • 5.4.6.1. Spend Authorization Signature
      • 5.4.6.2. Binding Signature
    • 5.4.7. Commitment Schemes
      • 5.4.7.1. Sprout Note Commitments – Implement Sprout Note Commitment Function #273
      • 5.4.7.2. Windowed Pedersen Commitments – Implement Sapling Note Commitment Function #274
      • 5.4.7.3. Homomorphic Pedersen Commitments – Implement Sapling Value Commitments #276
    • 5.4.8. Represented Groups and Pairings
      • 5.4.8.1. BN-254 – we don't implement BCTV14 and checkpoint on Sapling activation.
      • 5.4.8.2. BLS12-381 – comes with Pull in zcash_proofs #336
      • 5.4.8.3. Jubjub – comes with Use RedJubjub types in zebra-chain. #142, Sapling keys and addresses #327
      • 5.4.8.4. Hash Extractor for Jubjub – comes with Use RedJubjub types in zebra-chain. #142, Sapling keys and addresses #327
      • 5.4.8.5. Group Hash into Jubjub – comes with Use RedJubjub types in zebra-chain. #142, Sapling keys and addresses #327
    • 5.4.9. Zero-Knowledge Proving Systems
      • 5.4.9.1. BCTV14 – Expose proof validation for BCTV14 type #304
      • 5.4.9.2. Groth16 – Implement verifiers that accept Groth16 types #305
  • 5.5. Encodings of Note Plaintexts and Memo Fields – Sprout note encryption/decryption implementation. #181, Make Memo an enum type #250, ???
  • 5.6. Encodings of Addresses and Keys
    • 5.6.1. Transparent Addresses – Transparent keys and addresses #268
    • 5.6.2. Transparent Private Keys – Transparent keys and addresses #268
    • 5.6.3. Sprout Shielded Payment Addresses – Sprout keys and addresses #265
    • 5.6.4. Sapling Shielded Payment Addresses – Sapling keys and addresses #266
    • 5.6.5. Sprout Incoming Viewing Keys – Sprout keys and addresses #265
    • 5.6.6. Sapling Incoming Viewing Keys – Sapling keys and addresses #266
    • 5.6.7. Sapling Full Viewing Keys – Sapling keys and addresses #266
    • 5.6.8. Sprout Spending Keys – Sprout keys and addresses #265
    • 5.6.9. Sapling Spending Keys – Sapling keys and addresses #266
  • 5.7. BCTV14 zk-SNARK Parameters – we don't implement BCTV14 and checkpoint on Sapling activation.
  • 5.8. Groth16 zk-SNARK Parameters – part of Implement verifiers that accept Groth16 types #305
  • 5.9. Randomness Beacon – covered in JubJub, Use RedJubjub types in zebra-chain. #142
• 6. Network Upgrades – ZIP-200: Network Upgrade Mechanism #337
• 7. Consensus Changes from Bitcoin
  • 7.1. Encoding of Transactions – Update Transaction type and message to support the Zcash changes from Bitcoin #13, Update Transaction definition. #105, Implement transaction serialization. #124, Transaction proptests etc #118
  • 7.2. Encoding of JoinSplit Descriptions – Update Transaction definition. #105, Implement transaction serialization. #124, Transaction proptests etc #118
  • 7.3. Encoding of Spend Descriptions – Update Transaction definition. #105, Implement transaction serialization. #124, Transaction proptests etc #118
  • 7.4. Encoding of Output Descriptions – Update Transaction definition. #105, Implement transaction serialization. #124, Transaction proptests etc #118
  • 7.5. Block Header – Block, BlockHeader and Block messages #21, Some unit tests and proptests #212
  • 7.6. Proof of Work - Implement Equihash verification #335
    • 7.6.1. Equihash
    • 7.6.2. Difficulty filter
    • 7.6.3. Difficulty adjustment
    • 7.6.4. nBits conversion
    • 7.6.5. Definition of Work
  • 7.7. Calculation of Block Subsidy and Founder's Reward – Check block subsidy (miner and founder's reward) rules as part of validation #297, Validate that only the first transaction in a block is a coinbase transaction  #298, Calc Block Subsidy and Funding Streams #338
  • 7.8. Payment of Founders' Reward – Validate that only the first transaction in a block is a coinbase transaction  #298, Calc Block Subsidy and Funding Streams #338
  • 7.9. Changes to the Script System – Zcash-compatible Bitcoin script impl #180
  • 7.10. Bitcoin Improvement Proposals – see list below.
• 8. Differences from the Zerocash paper – does not contain implementable items
  • 8.1. Transaction Structure
  • 8.2. Memo Fields
  • 8.3. Unification of Mints and Pours
  • 8.4. Faerie Gold attack and fix
  • 8.5. Internal hash collision attack and fix
  • 8.6. Changes to PRF inputs and truncation
  • 8.7. In-band secret distribution
  • 8.8. Omission in Zerocash security proof
  • 8.9. Miscellaneous
• 9. Acknowledgements – does not contain implementable items
• 10. Change History – does not contain implementable items
• 11. References – does not contain implementable items

Appendices:

• A. Circuit Design
• B. Batching (Optional) - Implement Groth16 batch verification optimizations #406

Also remember that consensus ZIPs are part of the spec:

• Check BIPs: 11, 13, 14, 16, 30, 31, 34, 35, 37, 61, 65, 66, 111
• ZIP 32: Shielded Hierarchical Deterministic Wallets -Implement ZIP-32 Sapling and Orchard key derivation #267
• ZIP 143: Transaction Signature Verification before Overwinter -- not applicable due to checkpoint on Sapling activation
• ZIP 200: Network Upgrade Mechanism
• ZIP 201: Network Peer Management for Overwinter
• ZIP 202: Version 3 Transaction Format for Overwinter -- not applicable due to checkpoint
• ZIP 203: Transaction Expiry
• ZIP 205: Deployment of the Sapling Network Upgrade
• ZIP 206: Deployment of the Blossom Network Upgrade
• ZIP 208: Shorter Block Target Spacing
• ZIP 243: Network Upgrade Mechanism
• ZIP 302: Standardized Memo Field Format (in progress) -- not consensus but you'll probably want to implement it

and for Heartwood:

• ZIP 213: Shielded Coinbase - ZIP-213: Validate Shielded Coinbase Outputs like other shielded outputs #608
• ZIP 221: FlyClient - Consensus-Layer Changes
• ZIP 250: Deployment of the Heartwood Network Upgrade

[hdevalence]

Changes: checked off boxes corresponding to RedJubjub and ed25519-zebra as complete, checked off boxes related to BN254 and BCTV14 as planned unimplemented, marked "Differences from the Zerocash paper" as unimplementable.

[hdevalence]

Changes: added references to #181 and #250 to relevant parts of the spec.

[hdevalence]

Changes: checked off a few encoding boxes for transactions, their components, etc.

[daira]

Don't forget the appendices! You can probably pull in all of Appendix A as a dependency on zcash_proofs, but there's also batching in Appendix B. (Granted that is not needed for a minimal implementation, but you'll want to prepare for it.)

[daira]

Also remember that consensus ZIPs are part of the spec:

(moved to ticket description, so we don't forget them)

[teor2345]

Changes:

• ZIP-213: Validate Shielded Coinbase Outputs like other shielded outputs #608 for Heartwood ZIP-213
• moved Zips to ticket description
• added appendixes to ticket description

[mpguerra]

Closing and removing the Epic label for now as we have no issues being tracked under it and issue is superseded by other tracking issues and epics tracking the NU5 activation and client work.