Allow sign-to-contract commitments in schnorrsigs [̶a̶l̶t̶e̶r̶n̶a̶t̶i̶v̶e̶]̶ #589

pull jonasnick wants to merge 7 commits into bitcoin-core:master from jonasnick:schnorrsig-s2c-only-new changing 16 files +2225 −7
  1. jonasnick commented at 7:52 pm on February 14, 2019: contributor

    This is an alternative to #588 as requested by @real-or-random which I also slightly prefer (EDIT: this seems to be generally preferred now). The main difference is that the sign-to-contract commitment step happens in the signature function and not the nonce function. Also the nonce_is_negated argument in schnorrsig_sign is replaced by an s2c_opening object. A new argument to schnorrsig_sign is added called s2c_data. There’s no need to add a context argument to nonce functions. I also added parsing and serialization for s2c_openings. Manual initialization of s2c_opening is not necessary anymore.

    Example:

    0/* Signer */
1secp256k1_s2c_opening opening;
2unsigned char s2c_data[32];
3secp256k1_schnorrsig_sign(sign, &sig, &opening, msg, sk1, &s2c_data, NULL, NULL);
4
5/* Verifier */
6secp256k1_schnorrsig_verify_s2c_commit(ctx, &sig, s2c_data, &opening);
  2. gmaxwell commented at 0:17 am on February 15, 2019: contributor
    That workflow doesn’t make it look as easy to implement s2c anti-sidechannel blinding, if I understand it.
  3. jonasnick commented at 9:49 am on February 15, 2019: contributor
    Hm, I’ve done a quick and dirty rebase of the anti-nonce-sidechannel and it seems straight forward. It’s even a bit simpler on the client side.
  4. jonasnick cross-referenced this on Feb 15, 2019 from issue Add anti nonce-sidechannel protocol to schnorrsigs [̶a̶l̶t̶e̶r̶n̶a̶t̶i̶v̶e̶]̶ by jonasnick
  5. jonasnick commented at 1:36 pm on February 15, 2019: contributor
    I opened PR #590 to show the anti nonce-sidechannel protocol can be built on this PR in a similar way.
  6. real-or-random commented at 2:56 pm on February 15, 2019: contributor
    Concept ACK
  7. real-or-random commented at 3:01 pm on February 15, 2019: contributor
    I guess this is a more general discussion because it’s also in ECDSA: What’s the exact benefit of the user being able to provide a nonce function (and possibly shoot herself in the foot?) I’m not sure if there are meaningful cases,so I’m somewhat curious if anybody currently uses this in practice with ECDSA.
  8. gmaxwell commented at 8:45 am on February 19, 2019: contributor

    @real-or-random IIRC it’s actually used by joinmarket to do ECDH with the R value for a stealth payment donation feature. (like one of the outputs pays to P+H(kP)G for some pubkey P). The payments can be found by the recipient simply scanning every signature in the chain, performing ECDH with it, and checking the outputs…

    Less cosmically RFC6979 is kind of absurd and actually makes signing measurably slower compared to just a simple hash– for applications that care about signing speed (like matt’s betterhash) substituting it is probably a good idea. Not sure who if anyone is doing that right now, but some things probably should be. (Though those same applications should probably also do batch nonce generation and other stuff that wouldn’t really be simple with the current nonce function interface)

    Re: footgunnery, I haven’t yet seen anyone footgun themselves that way. Creating a working nonce function takes a fair amount of work, so I think it’s likely that if anyone bothers they at least have a fighting chance to get it right. I think the best mental model is that we’re trying to defend against users that are equal parts lazy and ignorant. Give them a nonce argument and they will set the nonce to private key xor messagehash (actual example which demonstrates lazy+ignorant), but give them a nonce function argument and they’ll leave it null unless they actually have a real reason to do otherwise. :)

  9. real-or-random commented at 2:54 pm on February 19, 2019: contributor

    Okay, convinced.

    I think the best mental model is that we’re trying to defend against users that are equal parts lazy and ignorant.

    That’s indeed a good way to think about it.

    Maybe it’s still a good idea to make it more prominent in the docs that people should use the default unless they really know what they are doing.

  10. gmaxwell commented at 9:53 am on February 20, 2019: contributor
    Sounds fine to me. I also think we could explicitly say that the nonce function isn’t an interface that we particularly care about keeping stable.
  11. in src/secp256k1.c:642 in 4debe30089 outdated 
    637+    unsigned char tweak[32];
638+
639+    VERIFY_CHECK(ctx != NULL);
640+    ARG_CHECK(commitment != NULL);
641+    ARG_CHECK(pubkey != NULL);
642+    ARG_CHECK(data != NULL);
    apoelstra commented at 2:45 pm on February 21, 2019:
    We generally don’t have ARG_CHECKs in static functions.
    apoelstra commented at 2:45 pm on February 21, 2019:
    Same below in ec_commit_seckey
    jonasnick commented at 2:50 pm on February 23, 2019:
    thought this could be non-static soon, but removed it nonetheless for now
  12. in src/secp256k1.c:702 in 4debe30089 outdated 
    697+    }
698+
699+    /* Return commitment == commitment_tmp */
700+    secp256k1_gej_set_infinity(&pj);
701+    secp256k1_pubkey_load(ctx, &p, &commitment_tmp);
702+    secp256k1_gej_add_ge(&pj, &pj, &p);
    apoelstra commented at 2:46 pm on February 21, 2019:
    We can use the _var variant of this function (same with below).
    jonasnick commented at 2:49 pm on February 23, 2019:
    fixed
  13. in include/secp256k1.h:92 in ed20dbd2c8 outdated 
    87+ *  This structure is not opaque, but it is strongly discouraged to read or write to
88+ *  it directly.
89+ *
90+ *  The exact representation of data inside is implementation defined and not
91+ *  guaranteed to be portable between different platforms or versions. It is however
92+ *  guaranteed to be 73 bytes in size, and can be safely copied/moved.
    apoelstra commented at 2:56 pm on February 21, 2019:
    This guarantee is basically impossible to make for a data structure with multiple heterogeneous fields.
    apoelstra commented at 2:56 pm on February 21, 2019:
    “safely copied/moved” is OK, but the exact size is implementation dependent.
    gmaxwell commented at 10:07 pm on February 21, 2019:
    (if it wasn’t clear, due to alignment padding, which could basically be anything)
    jonasnick commented at 2:56 pm on February 23, 2019:
    yeah, not sure what’s got into me
    jonasnick commented at 2:56 pm on February 23, 2019:
    fixed
  14. in src/secp256k1.c:709 in ed20dbd2c8 outdated 
    705@@ -706,6 +706,38 @@ static int secp256k1_ec_commit_verify(const secp256k1_context* ctx, const secp25
706     return secp256k1_gej_is_infinity(&pj);
707 }
708 
709+static uint64_t s2c_opening_magic = 0x5d0520b8b7f2b168;
    apoelstra commented at 3:07 pm on February 21, 2019:
    Using uint64_t here rather than char[8] introduces an endianness dependency. Is this on purpose?
    jonasnick commented at 3:43 pm on February 21, 2019:
    It’s not purposefully endian dependent, but purposefully uint64. Just looks nicer and the object is documented to be “implementation defined” anyway. But agree char should be better.
    jonasnick commented at 2:49 pm on February 23, 2019:
    fixed
  15. in include/secp256k1_schnorrsig.h:71 in 16a7592fd1 outdated 
    68+ *                a sign-to-contract commitment (i.e. the `s2c_data` argument
69+ *                is not NULL).
70  *  In:    msg32: the 32-byte message hash being signed (cannot be NULL)
71  *        seckey: pointer to a 32-byte secret key (cannot be NULL)
72+ *    s2c_data32: pointer to a 32-byte data to create an optional
73+ *                sign-to-contract commitment to if non-NULL (non-NULL).
    apoelstra commented at 3:11 pm on February 21, 2019:
    (non-NULL) should be removed.
    jonasnick commented at 2:49 pm on February 23, 2019:
    fixed
  16. in include/secp256k1_schnorrsig.h:78 in 16a7592fd1 outdated 
    69+ *                is not NULL).
70  *  In:    msg32: the 32-byte message hash being signed (cannot be NULL)
71  *        seckey: pointer to a 32-byte secret key (cannot be NULL)
72+ *    s2c_data32: pointer to a 32-byte data to create an optional
73+ *                sign-to-contract commitment to if non-NULL (non-NULL).
74  *       noncefp: pointer to a nonce generation function. If NULL, secp256k1_nonce_function_bipschnorr is used
    apoelstra commented at 3:18 pm on February 21, 2019:
    Can you add a comment to noncefp saying that it has to be NULL (or the default) if s2c_data is not NULL?
    jonasnick commented at 2:48 pm on February 23, 2019:
    fixed
  17. apoelstra commented at 3:33 pm on February 21, 2019: contributor
    valgrind ./tests 1 shows a bunch of branches on uninitialized memory.
  18. in src/modules/schnorrsig/main_impl.h:93 in 16a7592fd1 outdated 
    88+    }
89+
90+    secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pkj, &x);
91+    secp256k1_ge_set_gej(&pk, &pkj);
92+
93+    if(s2c_data32 != NULL) {
    real-or-random commented at 5:19 pm on February 21, 2019:
    nit: spacing
    jonasnick commented at 2:48 pm on February 23, 2019:
    fixed
  19. jonasnick cross-referenced this on Feb 22, 2019 from issue Java/JNI: Add native bindings for Schnorr signatures by guggero
  20. jonasnick cross-referenced this on Jun 17, 2019 from issue Add schnorrsig module which implements BIP-340 compliant signatures by jonasnick
  21. in src/secp256k1.c:697 in 68a8ca4583 outdated 
    692+    secp256k1_ge_neg(&p, &p);
693+    secp256k1_gej_add_ge_var(&pj, &pj, &p, NULL);
694+    return secp256k1_gej_is_infinity(&pj);
695+}
696+
697+static char s2c_opening_magic[8] = { 0x5d, 0x05, 0x20, 0xb8, 0xb7, 0xf2, 0xb1, 0x68 };
    elichai commented at 10:04 pm on July 1, 2019:
    Here it’s char but in the struct it’s unsigned char.
    jonasnick commented at 8:55 pm on July 4, 2019:
    Switched to uint64_t because there’s less room for mistakes and it’s easier to read.
  22. in src/modules/schnorrsig/main_impl.h:126 in 68a8ca4583 outdated 
    118+
119+    secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &rj, &k);
120+    secp256k1_ge_set_gej(&r, &rj);
121+    if (s2c_opening != NULL) {
122+        secp256k1_s2c_opening_init(s2c_opening);
123+        if (s2c_data32 != NULL) {
    elichai commented at 10:19 pm on July 1, 2019:
    Maybe add a check if s2c_opening == NULL || s2c_data32 == NULL? Because if that’s true I think it means the user made a mistake
    jonasnick commented at 12:50 pm on July 3, 2019:
    You mean CHECK((s2c_opening != NULL) == (s2c_data32 != NULL)) (both should be NULL or both should be non-NULL)? Yes, I’ll add an ARG_CHECK
    jonasnick commented at 8:56 pm on July 4, 2019:
    fixed
  23. in include/secp256k1.h:100 in 68a8ca4583 outdated 
     95+    /* magic is set during initialization */
 96+    unsigned char magic[8];
 97+    /* Public nonce before applying the sign-to-contract commitment */
 98+    secp256k1_pubkey original_pubnonce;
 99+    /* Integer indicating if signing algorithm negated the nonce */
100+    unsigned char nonce_is_negated;
    elichai commented at 10:43 pm on July 1, 2019:
    Is this a computational optimization to avoid computing the jacobi symbol on secp256k1_schnorrsig_verify_s2c_commit?
    jonasnick commented at 12:45 pm on July 3, 2019:
    Yes, we could could compute the ec_commitment of original_pubnonce and data then negate if this is not a valid nonce. But this prevents batch verification. I will mention this in the doc.
    jonasnick commented at 8:56 pm on July 4, 2019:
    added comment to explain this
  24. in src/modules/schnorrsig/main_impl.h:32 in 68a8ca4583 outdated 
    27+    ARG_CHECK(in64 != NULL);
28+    memcpy(sig->data, in64, 64);
29+    return 1;
30+}
31+
32+int secp256k1_schnorrsig_verify_s2c_commit(const secp256k1_context* ctx, const secp256k1_schnorrsig *sig, const unsigned char *data32, const secp256k1_s2c_opening *opening) {
    elichai commented at 10:51 pm on July 1, 2019:
    Should this function be constant time? could data32 actually be a secret worth guarding?
    real-or-random commented at 11:06 pm on July 2, 2019:
    I think you’re right but it seems that it is constant time in data32.
  25. elichai commented at 10:53 pm on July 1, 2019: contributor
    (I also prefer this design over #588)
  26. real-or-random cross-referenced this on Jul 2, 2019 from issue Allow sign-to-contract commitments in schnorrsigs by jonasnick
  27. jonasnick renamed this:
    Allow sign-to-contract commitments in schnorrsigs [alternative]
    Allow sign-to-contract commitments in schnorrsigs ~~[alternative]~~
    on Jul 3, 2019
  28. jonasnick renamed this:
    Allow sign-to-contract commitments in schnorrsigs ~~[alternative]~~
    Allow sign-to-contract commitments in schnorrsigs [̶a̶l̶t̶e̶r̶n̶a̶t̶i̶v̶e̶]̶
    on Jul 3, 2019
  29. in include/secp256k1.h:104 in 779458a2be outdated 
     96@@ -97,7 +97,10 @@ typedef struct {
 97     uint64_t magic;
 98     /* Public nonce before applying the sign-to-contract commitment */
 99     secp256k1_pubkey original_pubnonce;
100-    /* Integer indicating if signing algorithm negated the nonce */
101+    /* Byte indicating if signing algorithm negated the nonce. Alternatively when
102+     * verifying we could compute the EC commitment of original_pubnonce and the
103+     * data and negate if this would not be a valid nonce. But this would prevent
104+     * batch verification of sign-to-contract commitments. */
105     unsigned char nonce_is_negated;
    real-or-random commented at 9:50 pm on July 4, 2019:
    nit, feel free to ignore: Boolean values are typically represented by int and not unsigned char.
    jonasnick commented at 10:09 pm on July 4, 2019:
    Yes but ints are the worst. Since nonce_is_negated is only ever 0 or 1 I changed this to int.
  30. jonasnick force-pushed on Jul 4, 2019
  31. add chacha20 function 2f40e1ec2e
  32. Add schnorrsig module which implements BIP-schnorr [0] compatible signing, verification and batch verification. 
    [0] https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
    82645729cc
  33. Add ec_commitments which are essentially the pay-to-contract-style tweaks of public keys. 
    The functionality is not exposed.
    0b4bef4527
  34. Add and expose sign-to-contract opening with parse and serialize functions 854c1c495f
  35. Allow creating and verifying Schnorr sign-to-contract commitments 9037bcf5e8
  36. jonasnick force-pushed on Jul 4, 2019
  37. jonasnick commented at 10:10 pm on July 4, 2019: contributor
    rebased on schnorrsigs PR and squashed
  38. in include/secp256k1.h:484 in 9037bcf5e8 outdated 
    479+ *
480+ */
481+SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_s2c_opening_parse(
482+    const secp256k1_context* ctx,
483+    secp256k1_s2c_opening* opening,
484+    const unsigned char *input34
    elichai commented at 1:48 am on July 28, 2019:
    Is it worth it to optimize this down to 33 bytes by just using a single bit to mark if the nonce has been negated?(we can use the same byte that we use to signal the parity)
    jonasnick commented at 4:52 pm on July 30, 2019:
    good idea
  39. in src/modules/schnorrsig/main_impl.h:131 in 9037bcf5e8 outdated 
    126+        if (s2c_data32 != NULL) {
127+            /* Create sign-to-contract commitment */
128+            secp256k1_pubkey_save(&s2c_opening->original_pubnonce, &r);
129+            secp256k1_ec_commit_seckey(ctx, buf, &s2c_opening->original_pubnonce, s2c_data32, 32);
130+            secp256k1_scalar_set_b32(&k, buf, NULL);
131+            secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &rj, &k);
    elichai commented at 2:19 am on July 28, 2019:
    Maybe instead of recomputing the secret key and multiplying by the generator you can compute H(R, data)*G and add that to the R you already have? (although since all of this is constant time it might result in no performance change? I’m not sure about it)
    jonasnick commented at 4:36 pm on July 30, 2019:
    It’s R + H(R, data)*G vs. k*G. The latter is less code and faster (no addition). This is independent of being constant time.
    elichai commented at 1:51 pm on July 31, 2019:
    I guess the performance will be a matter of will this wrap around the order or not. (if it will cause a wrap than k*G is gonna be faster, if it doesn’t then calculating the H(R,data)*G and adding to R should be faster i think)
    jonasnick commented at 1:59 pm on July 31, 2019:
    No. Adding two curve points is completely separate from “wrapping around the order”.
  40. in src/secp256k1.c:784 in 9037bcf5e8 outdated 
    779+    }
780+
781+    /* Return commitment == commitment_tmp */
782+    secp256k1_gej_set_infinity(&pj);
783+    secp256k1_pubkey_load(ctx, &p, &commitment_tmp);
784+    secp256k1_gej_add_ge_var(&pj, &pj, &p, NULL);
    elichai commented at 3:14 am on July 28, 2019:
    You can use secp256k1_gej_set_ge() instead of setting to infinity and adding
    jonasnick commented at 8:47 am on July 31, 2019:
    fixed
  41. f Add ec_commitments 031ca34a4f
  42. jonasnick commented at 8:47 am on July 31, 2019: contributor
    Added commit to make the opening serialization 33 bytes instead of 34.
  43. f serialize s2c_opening as 33 bytes instead of 34 b631248693
  44. jonasnick cross-referenced this on Nov 13, 2019 from issue ecdsa sign-to-contract module, with anti nonce covert chan util functions by benma
  45. landanhu cross-referenced this on Dec 29, 2019 from issue Problem: rust-secp256k1 fork diverged from upstream by landanhu
  46. jonasnick cross-referenced this on Nov 9, 2021 from issue Implement sign-to-contract scheme for BIP-340 signatures by dr-orlovsky
  47. dr-orlovsky cross-referenced this on Nov 17, 2021 from issue Schnorr sign-to-contract commitments by dr-orlovsky
  48. dr-orlovsky cross-referenced this on Jan 16, 2022 from issue Sign-to-contract support in DBCs and signle-use-seals by dr-orlovsky
  49. jonasnick commented at 2:05 pm on March 24, 2022: contributor
    This PR is quite outdated. Sign-to-contract should use the schnorrsig_sign_custom API. PR #1018 is a WIP continuation of this work. Closing.
  50. jonasnick closed this on Mar 24, 2022
  51. dr-orlovsky cross-referenced this on May 24, 2022 from issue Implement sign-to-contract commitments by dr-orlovsky
  52. benma referenced this in commit 6daba2638e on Sep 11, 2022
  53. benma referenced this in commit b26da2a4c5 on Sep 11, 2022
  54. benma referenced this in commit 3d1c3013cc on Sep 11, 2022
  55. benma referenced this in commit d69625bece on Sep 11, 2022
  56. benma cross-referenced this on Sep 11, 2022 from issue Schnorr sign-to-contract and anti-exfil by benma
  57. benma referenced this in commit a903875151 on Sep 12, 2022
  58. benma referenced this in commit c1904b1246 on Sep 12, 2022
  59. benma referenced this in commit 2c50310e91 on Sep 13, 2022
  60. benma referenced this in commit 972f413720 on Sep 13, 2022
  61. benma referenced this in commit 81a745c998 on May 1, 2023
  62. benma referenced this in commit 5d768de16a on May 1, 2023
  63. benma referenced this in commit 999c82f7d7 on Jul 29, 2023
  64. benma referenced this in commit a8c192ddcf on Jul 29, 2023


jonasnick gmaxwell real-or-random apoelstra elichai

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-23 09:15 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me