halo icon indicating copy to clipboard operation
halo copied to clipboard

Implement variable-bound range proofs

Open str4d opened this issue 4 years ago • 1 comments

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.

str4d avatar Sep 18 '19 13:09 str4d

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

daira avatar Sep 22 '19 09:09 daira