Implement Schnorr signatures #212

pull sipa wants to merge 1 commits into bitcoin-core:master from sipa:schnorr3 changing 14 files +946 −13
  1. sipa commented at 0:36 am on February 13, 2015: contributor
  2. sipa renamed this:
    Implement Schnorr signatures + batch verification
    [WIP] Implement Schnorr signatures + batch verification
    on Feb 13, 2015
  3. sipa force-pushed on Mar 2, 2015
  4. sipa commented at 10:29 am on March 2, 2015: contributor
    Rebased.
  5. sipa force-pushed on Mar 2, 2015
  6. sipa force-pushed on Apr 23, 2015
  7. sipa commented at 9:11 am on April 23, 2015: contributor
    Rebased.
  8. sipa commented at 9:11 am on April 23, 2015: contributor
    TODO: use context to store the batch multipliers
  9. dcousens commented at 1:57 am on April 27, 2015: contributor

    This is awesome, as Schnorr signatures are dead easy to understand. But, for what purpose have they been added?

    (just curious)

  10. sipa commented at 7:24 am on April 27, 2015: contributor
    They have not been added yet :)
  11. sipa force-pushed on May 1, 2015
  12. evoskuil cross-referenced this on May 12, 2015 from issue Tracking: Implications of Schnorr patent expiration. by evoskuil
  13. sipa force-pushed on Jun 22, 2015
  14. sipa force-pushed on Jun 22, 2015
  15. sipa renamed this:
    [WIP] Implement Schnorr signatures + batch verification
    Implement Schnorr signatures
    on Jun 22, 2015
  16. sipa commented at 4:06 pm on June 22, 2015: contributor

    Separated batch validation into a separate branch. This pull request should be usable. Question for reviewers:

    • Enable Schnorr code by default, or hide behind a compile flag (and perhaps move to a separate include/.h file)?
  17. sipa force-pushed on Jun 25, 2015
  18. sipa force-pushed on Jul 1, 2015
  19. sipa commented at 2:42 pm on July 1, 2015: contributor
    @gmaxwell Added multiparty signing API.
  20. apoelstra commented at 6:31 pm on July 1, 2015: contributor

    I’m a bit concerned about using secp256k1_nonce_function_default. If you sign the same message in both ECDSA and Schnorr with the same nonce, it is possible to recover the secret key from the two signatures. So I think by default Schnorr should use a slightly different noncegen function.

    Edit: Oh, I’m being stupid, in Schnorr the messagehash has R inside of it while with ECDSA it does not. So you’d have to do this very deliberately.

    Edit2: No, I was right the first time :). Regardless of message-hash, two signatures with the same key/nonce represent two equations in two unknowns.

  21. in src/schnorr_impl.h: in 71d3db66cf outdated
    62+    }
    63+    secp256k1_ge_set_gej(&Ra, &Rj);
    64+    secp256k1_fe_normalize(&Ra.y);
    65+    if (secp256k1_fe_is_odd(&Ra.y)) {
    66+        secp256k1_scalar_negate(&n, &n);
    67+    }
    


    apoelstra commented at 1:33 pm on July 2, 2015:
    Can you add a comment above this block explaining that forcing the parity of y allows batch verification (and is part of the definition of Schnorr signatures), at the cost of making inversion-free validation impossible?
  22. sipa commented at 2:26 pm on July 2, 2015: contributor

    @apoelstra You’re not being stupid, I think.

    k is the secret nonce, r is R’s x coordinate, m is the message, x is the private key, h = H(m || r). x and k are unknown to an attacker.

    ECDSA: s_ecdsa * k = m + r * x Schnorr: s_schnorr = k - h * x

    Or: ECDSA: k = (m + r * x) / s_ecdsa Schnorr: k = s_schnorr + h * x

    So: (m + r * x) / s_ecdsa = s_schnorr + h * x

    So: x = (s_schnorr - m/s_ecdsa) / (r/s_ecdsa - h)

  23. sipa force-pushed on Jul 2, 2015
  24. sipa commented at 3:28 pm on July 2, 2015: contributor

    Fixed the problem listed above by xoring the name of the signature algorithm into the message.

    Added a rationale for the choice of full R validation and implicit even y.

  25. sipa force-pushed on Jul 2, 2015
  26. sipa force-pushed on Jul 2, 2015
  27. sipa force-pushed on Jul 10, 2015
  28. sipa commented at 5:43 pm on July 10, 2015: contributor
    Rebased on top of #269 and passing the signature algorithm name into the PRNG, to avoid the issue @apoelstra found above.
  29. sipa force-pushed on Jul 24, 2015
  30. sipa commented at 3:34 pm on July 24, 2015: contributor
    Rebased on top of new #269 and #282, and made compilation of Schnorr code optional (with API defined in a separate header). @theuni Any comments on the module approach here?
  31. sipa force-pushed on Jul 24, 2015
  32. sipa force-pushed on Jul 24, 2015
  33. sipa force-pushed on Jul 26, 2015
  34. sipa force-pushed on Jul 26, 2015
  35. sipa force-pushed on Jul 26, 2015
  36. apoelstra commented at 7:45 pm on July 26, 2015: contributor
    Valgrind shows a bunch of errors on the test binary with this code. You need CFLAGS="-g -O0" ./configure to see them.
  37. sipa force-pushed on Jul 26, 2015
  38. apoelstra commented at 10:51 pm on July 26, 2015: contributor

    Almost there :) test_schnorr_end_to_end is never called (and as a consequence _sign and _recover aren’t tested).

    _Edit:_ Ah, test_ecdsa_end_to_end is called rather than the schnorr version.

  39. sipa force-pushed on Jul 26, 2015
  40. sipa commented at 10:55 pm on July 26, 2015: contributor
    Fixed.
  41. apoelstra commented at 11:57 pm on July 26, 2015: contributor
    ACK
  42. theuni commented at 9:04 pm on July 27, 2015: contributor

    @sipa Looks good to me. One nit though. IMO we should also add a define in the main header that lists which modules are available. Otherwise preprocessing would be necessary to determine if schnorr functionality could be #included.

    Even easier than that would be a 3rd (pushing it, i know) header with those defines, to avoid hacking up the main interface header. As a bonus, we could also stick the current config in there so that features like USE_ENDOMORPHISM, USE_NUM_GMP, etc. could be known at the application level.

  43. sipa commented at 9:34 pm on July 27, 2015: contributor
    @theuni Feel like writing a patch for that? I’m not sure I follow, but I think it would be nice to have a clean extension mechanism (the two ECDH implementations would also fit there).
  44. sipa commented at 11:46 pm on July 27, 2015: contributor
    Hmm, I don’t know about exposing implementation details in the headers. I jist thought: if you enable the Schnorr module, the schnorr header file is installed, otherwise it isn’t… no preprocessing needed.
  45. theuni commented at 1:26 am on July 28, 2015: contributor

    @sipa There’s no way to tell if it’s installed without preprocessing though, you’d just “#include secp256k1_schnorr.h” and hope for the best.

    I took a quick stab at it here: https://github.com/theuni/secp256k1/tree/212

    If you decide to go this route, since the config details become part of the api, we’d need to namespace/cleanup their values.

    Of course, you could also just take a subset of this and only expose the module details, leaving the rest as it is.

  46. sipa commented at 1:40 am on July 28, 2015: contributor

    Well, duh. But how is that different from doing an include #include <gmp.h> and hoping that that libgmp is installed?

    I would really like to avoid having the public API expose implementation details. I’d rather just see them as two separate APIs that happen to be implemented in the same library.

  47. theuni commented at 2:01 am on July 28, 2015: contributor

    @sipa Because when you ‘apt-get install libgmp’, you know you can “#include <gmp.h>”. But if I apt-get install libsecp256k1, I have no idea what it contains. Using the existence of a file is shaky at best, as it’d be very easy to hit the system file in /usr/include when building against another or a cross build.

    No problem if you don’t want to expose implementation details, but I still think the user needs some explicit way to know what optional apis are available.

  48. sipa commented at 1:43 pm on July 28, 2015: contributor
    @theuni What would an application do with the knowledge that an extra API is available? If it needs it, the build will fail (at link time or at compile time), if it doesn’t, it doesn’t care…
  49. theuni commented at 7:18 pm on July 28, 2015: contributor

    @sipa Just as libsecp256k1 falls back to internal implementations if gmp isn’t usable, an application could do the same if libsecp256k1_foo feature isn’t available.

    But it’s really not worth the argument, and certainly not worth holding up this PR.

  50. sipa commented at 7:21 pm on July 28, 2015: contributor

    @theuni Right, there may be optional behaviour. But that’s something you’d typically check at configure time, which can try to compile.

    I guess the fundamental question I have is: why can you trust that the contents of a file on your disk corresponds with the library installed, when you can’t trust the presence of the file corresponding to it.

  51. sipa commented at 7:22 pm on July 28, 2015: contributor
    @theuni Ok, one other question: when you don’t specify –enable-module-schnorr, the schnorr files don’t get included in “make dist” I think. Is that something you’d typically want?
  52. theuni commented at 7:58 pm on July 28, 2015: contributor

    @sipa all files needed to build all configs should be included in the dist tarball. From a quick check, that’s currently working as expected:

    0./autogen.sh
    1./configure
    2make distdir # same as 'make dist' and extract tarball
    3cd libsecp256k1-0.1
    4./configure --enable-module-schnorr
    5make
    
  53. apoelstra commented at 11:23 pm on July 29, 2015: contributor
    Before merge can you add bench_schnorr_verify to .gitignore?
  54. apoelstra commented at 3:56 pm on August 1, 2015: contributor
    Also I think you need to change the last line of travis.yml so that the value of $SCHNORR actually affects configure.
  55. sipa force-pushed on Aug 2, 2015
  56. sipa commented at 5:37 pm on August 2, 2015: contributor
    Rebased.
  57. sipa force-pushed on Aug 2, 2015
  58. Add support for custom EC-Schnorr-SHA256 signatures a5a66c70b6
  59. sipa force-pushed on Aug 3, 2015
  60. sipa commented at 6:09 pm on August 3, 2015: contributor
    @apoelstra Nits addressed.
  61. apoelstra commented at 7:38 pm on August 3, 2015: contributor
    Thanks! Tested ACK.
  62. sipa merged this on Aug 3, 2015
  63. sipa closed this on Aug 3, 2015

  64. sipa referenced this in commit 258720851e on Aug 3, 2015
  65. sipa cross-referenced this on Aug 28, 2015 from issue Support for optional parts by sipa
  66. jl777 commented at 4:29 am on June 14, 2016: none
    is there anyway to use schnorr combined pubkey in a standard p2sh script? I assume the schnorr sigs are different so OP_CHECKSIG wont work, but if we can assume externally coordinated reveal on secret script, I am hoping there is a way to achieve this as a combined pubkey can be created, but I cant see how to get a script verifiable value before the signature. Maybe there is a way to cooperatively construct a combined privkey that can be used to sign?
  67. voisine commented at 4:46 am on June 14, 2016: contributor
    I believe schnor is planned for the first segwit upgrade. It will require a new checksig opcode and a soft fork.
  68. jl777 commented at 4:50 am on June 14, 2016: none
    well a new schnorr_sig opcode would make this all too easy :) that is what I am adding now but would be nice to get this on the bitcoin side too
  69. sipa commented at 6:21 am on June 14, 2016: contributor
    @jl777 Unsure what you mean. Schnorr signatures are not compatible with ECDSA at all, and needs different signing and verification code. Further, Bitcoin scripts that do not use any digital signature are inherently insecure (if there is no secret information being verified, miners can steal all the coins once they see a spend). Thus, indeed, the only way is using a new opcode.
  70. jl777 commented at 6:29 am on June 14, 2016: none

    it would be combined with a normal signature: OP_HASH160 hash(sharedsecret) OP_EQUALVERIFY (normal_pubkey) OP_CHECKSIG

    granted the protection from just the normal_pubkey OP_CHECKSIG isnt as much as full verification, but if there was a way to offchain calculate a schnorr sig based sharedsecret equivalent, then I think it would work.

    problem is I dont see a way to know ahead of time any value that a group signature would create. The combined pubkey appears to be a standard pubkey, but without any normal privkey. Maybe there is a way for a set of nodes to create onetime use keypairs and somehow create a combined privkey that can be used with the combined pubkey.

  71. sipa commented at 6:40 am on June 14, 2016: contributor
    You seem to be describing a normal signature with a hashlocked secret. Where does Schnorr come in?
  72. jl777 commented at 6:50 am on June 14, 2016: none

    the schnorr would come in offchain, so a group can do larger scale MofN between themselves was hoping there was a way to generate some sort of sharedsecret equivalent among the participants so that if each member of the group validates the schnorr combined sig, they release their portion of the sharedsecret.

    using shamir’s shared secret that each of the participants have and release only if they are satisfied, comes really close to being the hashlocked secret to use. The problem is we cant have any single node to know the secret that is being shamir’ed.

    maybe some sort of oblivious transfer method could be used, but this is getting to where I am not comfortable as I dont know of any C libraries for that.

    So the constraints are that each member of the group can directly run the schnorr lib, they can coordinate and precalculate any sort of magic value, but ultimately a hashlocked bitcoin tx needs to be used

  73. unknown cross-referenced this on Oct 8, 2018 from issue Add schnorrsig module which implements BIP-340 compliant signatures by jonasnick

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin-core/secp256k1. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-12-22 21:15 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me