Replace primitive_types with bigint

[hdevalence]

Motivation

We want to use zcash_primitives for non-malleable transaction IDs in PR #2129. But our primitive_types dependency is incompatible with zcash_primitives.

Also, primitive_types has a fairly decent dependency footprint:

primitive-types v0.7.2
├── fixed-hash v0.6.1
│   ├── byteorder v1.3.4
│   ├── rand v0.7.3 (*)
│   ├── rustc-hex v2.1.0
│   └── static_assertions v1.1.0
├── impl-codec v0.4.2
│   └── parity-scale-codec v1.3.4
│       ├── arrayvec v0.5.1
│       ├── bitvec v0.17.4
│       │   ├── either v1.5.3
│       │   └── radium v0.3.0
│       ├── byte-slice-cast v0.3.5
│       └── serde v1.0.114 (*)
└── uint v0.8.4
    ├── byteorder v1.3.4
    ├── crunchy v0.2.2
    ├── rustc-hex v2.1.0
    └── static_assertions v1.1.0

This isn't a high priority compared to getting everything working, but it's one way we can prune the size of our dep tree.

Solution

We want to replace primitive_types with the bigint crate, because librustzcash also uses that dependency .

Required Code Changes

• use bigint::U256 in zebra_chain::work

To calculate the block difficulty threshold from recent blocks, we need to perform the following operations on u256 values:

• division
• invert bits
  • this can be implemented as subtraction from the all-ones u256
• addition
• multiplication
• comparison

Alternatives

Here are the alternative libraries I looked at:

• bigint: https://docs.rs/bigint/4.4.3/bigint/uint/struct.U256.html
  • obsolete version of primitive-types
• bignum: https://luozijun.github.io/bignum/bignum/struct.u256.html
  • some functions are not implemented, but I think it has all the ones we need
  • doesn't have direct conversion to bytes (only u32s)
• num-bigint: https://docs.rs/num-bigint/0.3.0/num_bigint/
  • arbitrary size integers, possibly slower
  • doesn't have invert bits

[teor2345]

To calculate the block difficulty threshold from recent blocks, we need to perform the following operations on u256 values:

• division
• invert bits
• addition
• multiplication
• comparison

See #802 for details.

Here are the alternative libraries I looked at:

• bigint: https://docs.rs/bigint/4.4.3/bigint/uint/struct.U256.html
  • obsolete version of primitive-types
• bignum: https://luozijun.github.io/bignum/bignum/struct.u256.html
  • some functions are not implemented, but I think it has all the ones we need
  • doesn't have direct conversion to bytes (only u32s)
• num-bigint: https://docs.rs/num-bigint/0.3.0/num_bigint/
  • arbitrary size integers, possibly slower
  • doesn't have invert bits

Let me know which one you'd prefer, or if you know of another library that does u256 division.

[teor2345]

See #838 of one example where we use division.

We also need to use division for calculating the average difficulty (median of recent blocks, scaled by the time range of those blocks).

[str4d]

We currently depend on bigint in zcash_history, so it would be nice to coalesce on a common U256 dependency that we can use there as well, so that it doesn't come into the zebra dependency tree when the FlyClient consensus rules are added.

[teor2345]

bigint has about half the dependencies of primitive-types, because it doesn't depend on impl-codec. (It also doesn't depend on fixed-hash, but those dependencies are duplicates anyway.)

So Zebra could switch to bigint if you want, or Zebra and zcashd could both switch to num-bigint.

[hdevalence]

Changed milestone since I think that if we have some working code, fixing it is lower-priority than getting the rest of our functionality done.

[teor2345]

I tried switching from primitive_types to bigint before starting some new difficulty work.

But bigint doesn't support u128 conversions (it has its own U128 type), which would have meant some bit twiddling.

That's not a huge amount of work, but it's out of scope right now, so I left it for later.

[daira]

doesn't have invert bits

That can be implemented as subtraction from the all-ones u256.

[teor2345]

Obsoleted by #2350