ebfull/halo

Implement variable-bound range proofs

str4d opened this issue · 1 comments

str4d commented

The Bitcoin example recursive circuit needs to enforce:

  • hash <= target (to ensure the block header satisfies the required work)
  • remainder <= target (as part of constraining the integer division 2^256 / (target + 1) = work)

target is expanded from the header's nBits field, and thus is almost never a power of two, requiring a variable-bound range proof.

daira commented

I recommend implementing the power-of-two range proof as a separate gadget, and then implementing this in terms of that one.