search

BlockstreamResearch / secp256k1-zkp

A fork of libsecp256k1 with support for advanced and experimental features such as Confidential Assets and MuSig2
MIT License
365 stars 207 forks source link

shallue_van_de_woestijne support for t = 0 #284

Closed roconnor-blockstream closed 8 months ago

roconnor-blockstream commented 8 months ago

The current implementation returns an off-curve point for the input t=0. This is due to performing a "0/0" computation.

Here we change the code to explicitly return the on-curve point (d, sqrt(8)), which is the point that the paper Indifferentiable Hashing to Barreto–Naehrig Curves suggests returning in this case.

Note: At the moment it is cryptographically impossible for the input t to be 0.

roconnor-blockstream commented 8 months ago

This fixes issue #279 using method (A) by having changing the behavior of shallue_van_de_woestijne at the input t=0.

The downside of this fix is that it alters the behavior of this function. This should be reasonably safe to do even though it amounts to a hard-fork in Elements consensus code, because it is cryptographically impossible for the t=0 case to arise in practice. This can be seen because this is a static function, it can only be called in this file, and we can see that t is only ever set to the result of a sha256 digest (or perhaps t = 4).

For an alternative solution see #283.

This change is the minimally invasive change that I could think of to fix this function. However, I think this function could, and perhaps should, be rewritten to be streamlined. I have a version written in Haskell that could be translated to C. Please advise me if you want me to create such a PR and see how it looks in comparison to this (and #277).

apoelstra commented 8 months ago

My thoughts on these PRs:

  1. I don't think it's a "hardfork" to have forking behavior on a cryptographically unreachable path.
  2. But since this will stop being cryptographically unreachable post-Simplicity we want to fix this issue now.
  3. And I think "returning an on-curve point" is the most elegant solution, vs having an error path to deal with or vs having an off-curve point to deal with.
jonasnick commented 8 months ago

Merged alternative fix #286.