Tracking: proof of work validation

[teor2345]

In #572, we created CompactDifficulty and ExpandedDifficulty wrapper types for block proof of work difficulty.

But we also use difficulty to validate blocks, and choose the best tip.

Alpha Releases

Context-free block validation

• Compare difficulty_threshold to block.hash() (Block difficulty checks - context-free #809)

Choosing the best tip

Convert difficulty_threshold to Work

• implement CompactDifficulty to Work (feature: Implement CompactDifficulty to Work #838)
  • zcashd avoids dividing 2^256 by calculating:
    • ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1 or
    • (~bnTarget / (bnTarget+1)) + 1
    • See https://github.com/zcash/zcash/blob/b4ec903ac4e27943b667291c34271b2275653bb1/src/pow.cpp#L140
  • Use u128 for Work? (Zcash is 2^58 total, Bitcoin is 2^66 per second or 2^91 per year)
• derive Default, Ord, Eq for Work
• manually derive Add, AddAssign for Work
• cumulative work tests
• previous block / cumulative work state RFC
• check the total cumulative work against zcashd's calculation
  • we decided not to store the total cumulative work
• validate the proof of work limit, based on the consensus parameter for the current network

Implement Expanded to Compact

• implement ExpandedDifficulty to CompactDifficulty
• implement Arbitrary for CompactDifficulty by converting from random, non-zero Hash
  • use Arbitrary for CompactDifficulty in Arbitrary for Block
• implement Arbitrary for ExpandedDifficulty by converting from Arbitrary for CompactDifficulty
• implement Arbitrary for Work using a random u128
• implement Arbitrary for PartialCumulativeWork using a random u128

Testing

• round-trip tests from compact to expanded
  • on existing test cases
  • on historical blocks
  • on arbitrary CompactDifficulty and ExpandedDifficulty
    • also convert to Work, and do Add and Sub on PartialCumulativeWork

Difficulty adjustment - contextual

Spec Issues:

• Off-by-one error in testnet minimum difficulty block gap specification Off-by-one error in testnet minimum difficulty block gap specification #1276
  • Partial fix in zcash/zips@806076c
  • Final fix in Change the specification of minimum-difficulty blocks to reflect the zcashd implementation zcash/zips#417
• Implicit conversion of the minimum difficulty threshold to the compact representation Implicit conversion of the minimum difficulty threshold to the compact representation  #1277
  • Fix in Change the specification of minimum-difficulty blocks to reflect the zcashd implementation zcash/zips#417
• Testnet min-difficulty rules are incorrectly specified Testnet min-difficulty rules are incorrectly specified zcash/zips#416
  • Fix in Change the specification of minimum-difficulty blocks to reflect the zcashd implementation zcash/zips#417

Design:

• Proof of Work design RFC Proof of Work / Difficulty Design RFC #1036

Implementation:

Check that difficulty_threshold satisfies the difficulty adjustment consensus rules

• implement the "recent blocks" contextual validation abstraction (Add internal iterator API for accessing relevant chain blocks #1271)
• include the candidate block's height, hash, and network in a span that is active for the entire contextual validation function (Fix Block Height contextual verification #1303)
• add a debug mode for difficulty contextual verification
• implement the difficulty module
  • difficulty_threshold_is_valid
  • AdjustedDifficulty and new_from_block
  • expected_difficulty_threshold
    • threshold_bits
      • mean_target_difficulty
      • median_timespan_bounded
        • median_time
        • averaging_window_timespan and averaging_window_timespan_for_height on NetworkUpgrade
    • is_testnet_min_difficulty_block on NetworkUpgrade
      • this check uses >, and it's easy to get > confused with >=

Check that the time field is valid:

• block time median-time-past validation Block time contextual validation #1444

Tests:

• mainnet and testnet contextual test vectors Write tests for difficulty contextual validation #1414

Tests for spec errors:

• Test that testnet min-difficulty rules follow zcashd Testnet min-difficulty rules are incorrectly specified zcash/zips#416
• Test implicit conversion of the minimum difficulty threshold to the compact representation Implicit conversion of the minimum difficulty threshold to the compact representation  #1277

Cleanup

Semantic validation:

• Change the difficulty filter check into a method on block::Header - Move the difficulty filter into a block::Header method #1445
  • this check uses <=, and it's easy to get <= confused with <

Refactor:

• Rename the chain methods to any_block_iter, to avoid confusion - Rename state methods based on any chain or best chain #1446

---

Later Releases

Additional Tests

• add test vectors for difficulty adjustment from zcashd
• test consensus rules
  • successes
  • edge cases
  • failures
• check zcashd for test vectors
• create property tests with arbitrary difficulty and time values
  • constrain values within typical bounds, or choose distributions that favour typical values
  • ensure that about half of the arbitrary sets of 28 headers contain values that are all in range
  • ensure that some large values are included, particularly ones that trigger the testnet minimum difficulty rule

Tests for spec errors:

• Test off-by-one error in testnet minimum difficulty block gap specification Off-by-one error in testnet minimum difficulty block gap specification #1276

RFC Improvements

Guide-level:

• cut detail from the guide-level explanation - turn it into a summary
• explaining the feature largely in terms of examples
• provide sample error messages

Reference-level:

• The section should return to the examples given in the previous section, and explain more fully how the detailed proposal makes those examples work
• Corner cases are dissected by example (add examples)

Test Plan:

Explain how the feature will be tested, including:

• tests for consensus-critical functionality
• existing test vectors, if available
• Zcash blockchain block test vectors (specify the network upgrade, feature, or block height and network)
• property testing or fuzzing

The tests should cover:

• positive cases: make sure the feature accepts valid inputs
  • using block test vectors for each network upgrade provides some coverage of valid inputs
• negative cases: make sure the feature rejects invalid inputs
  • make sure there is a test case for each error condition in the code
  • if there are lots of potential errors, prioritise:
    • consensus-critical errors
    • security-critical errors, and
    • likely errors
• edge cases: make sure that boundary conditions are correctly handled

Denial of Service resistance

• Apply the difficulty filter to CheckpointVerifier blocks, so that a single bad peer can't poison arbitrary heights in the verifier's queue

Potential Refactor

• consider storing CompactDifficulty as { mantissa: NonZeroU32, exponent: NonZeroU8 }
  • remove code that deals with invalid values which are no longer representable
  • check each field's size at parse time, rather than just converting the whole u32 to a bag of bits
    • mantissa: 2^23
    • exponent: 34 = 255/8 + OFFSET

Difficulty cache

• consider caching the next difficulty for each block hash in the non-finalized state
• cache the next difficulty for the finalized tip
• this change avoids retrieving the previous 28 blocks for every new block, and avoids some calculations
• only worth doing if difficulty adjustment shows up in CPU or memory profiles

Dependencies

• replace primitive_types with a crate that has fewer dependencies (Replace primitive_types with bigint #829)

[hdevalence]

Removed the checkbox from #829 since I don't think it's essential to do immediately.

[mpguerra]

How much is there left to do on this for the Alpha release? We should move this out of the milestone once we have the Alpha release items done

[teor2345]

How much is there left to do on this for the Alpha release? We should move this out of the milestone once we have the Alpha release items done

The difficulty adjustment validation doesn't have any tests yet.

I have been prioritising fixing known bugs and errors over writing extra tests. If I get time, I'll write a few tests for this code. (There are other tests I'd like to do, but they will probably take more time than we have.)

This ticket already had a "lower-priority tasks" section. I've renamed it to "future releases", and moved most of the testing work into it.

[teor2345]

I've created specific tickets for the remaining first alpha release work in this ticket, and moved it out of the milestone.

[mpguerra]

Removing Epic label as there are no longer any issues tracked under this Epic and this better fits a github tracking issue instead.

[teor2345]

There are no required tasks left in this tracking issue.