Sapling Implementation Refactor

[ebfull]

Goals:

1. Improve code quality and testing coverage to decrease the chance of critical bugs. This includes modifying code to match the specification in areas where the specification diverged. Also, clearly specifying code that is variable time.
2. Separate components so that hardware wallets, light wallets etc. can use lightweight, portable implementations of the pieces that they need.
3. Expose more engineers to the cryptographic underpinnings and algorithms, at the implementation level, to improve code maintenance.

Strategy:

Different components will be built and cleaned up independently and then brought together as git subtrees in this librustzcash repository as code matures.

Primitive crates (not Zcash specific, generally useful):

1. zkcrypto/jubjub implements the Jubjub elliptic curve, the scalar field Fr, and the base field Fq, as defined in the Zcash protocol specification.
2. zkcrypto/ff implements traits for finite fields. We will not be bringing in ff_derive or any other macros, to reduce dependency trees. jubjub will bring this in as a dependency.
3. zkcrypto/group implements traits and generic group tools such as multi-exponentiation and FFTs. (TODO: multi-threaded variants of these algorithms; enabled by crate feature, or built outside this crate by exposing primitives?)
4. zkcrypto/bellman implements circuit traits and primitive structures, as well as basic gadget implementations such as booleans, number abstractions, etc. Unlike now, bellman will be generic using ff and won't be pairing-specific.
5. zkcrypto/pairing implements basic traits for pairing-friendly elliptic curve constructions.
6. zkcrypto/bls12_381 implements BLS12-381, which brings in jubjub as a dependency (to use its Fq implementation).
7. zkcrypto/groth16 implements the Groth16 proving system as used in Zcash. This brings in pairing and bellman as dependencies.

Zcash-specific crates:

1. zcash_primitives contains implementations of crypto components in Zcash, such as keys and their derivations (ZIP32), addresses, notes, and any other structures or algorithms specific to Zcash, such as transactions.
2. zcash_proofs contains an implementation of the prover and verifier for Sapling proofs. This brings in bls12-381, groth16 as dependencies and contains the implementation of the Spend/Output circuits.
3. zcash_client_backend contains tools for maintaining a Zcash wallet (something which can send and receive payments, maintain keys, etc.)
4. librustzcash is a C FFI for consensus-rule verification of Sapling transactions, interacting with the prover from C++, etc.

Task list (as of 2019-08-14):

• Merge zip32 crate into zcash_primitives.
  • Sapling address encodings #88
• Split up sapling-crypto across bellman, zcash_primitives, and zcash_proofs.
  • Refactor to remove sapling-crypto #104
• Implement new jubjub crate.
• Pull jubjub into workspace.
  • Import the jubjub crate as a git subtree #62
• Refactor ff traits to match jubjub API.
  • Remove ff::PrimeFieldRepr #223
• impl ff::* for jubjub
  • Implement ff traits for bls12_381 and jubjub crates #227
• ⚠️ Refactor group traits to match jubjub API.
  • group crate refactoring #230, New group traits #241
• ⚠️ Move multicore logic from bellman into group.
• impl group::* for jubjub
  • Implement group and pairing traits for bls12_381 and jubjub crates #245
• ⚠️ Implement new bls12_381 crate.
• Pull bls12_381 into workspace.
• impl ff::* for bls12_381
  • Implement ff traits for bls12_381 and jubjub crates #227
• impl group::* for bls12_381
  • Implement group and pairing traits for bls12_381 and jubjub crates #245
• Refactor pairing traits to match bls12_381 API.
  • pairing: Refactor traits to reflect bls12_381 crate API #238
• impl pairing::* for bls12_381
  • Implement group and pairing traits for bls12_381 and jubjub crates #245
• Replace zcash_primitives::jubjub with the new crate.
  • Migrate to bls12_381 and jubjub crates #272
• Replace pairing::bls12_381 with the new crate.
  • Migrate to bls12_381 and jubjub crates #272
• Extract groth16 from bellman.
  • Moved to Extract Groth16 implementation into separate crate zkcrypto/bellman#51

[zebambam]

Any chance you can put those module diagrams up here? @ebfull