[API CHANGE] Introduce pubkey and signature types #282

1. 
   sipa commented at 6:47 pm on July 20, 2015: contributor

   This introduces a new data type secp256k1_pubkey_t, which is an abstract parsed public key, convertible to/from serialized variable-size public keys.

   This avoids all API problems resulting from needing to pass pubkey sizes and pointers to pubkey sizes anywhere public keys are needed.

   Advantages:

   • No need for secp256k1_ec_pubkey_verify, secp256k1_ec_pubkey_compress, secp256k1_ec_pubkey_decompress
   • Reusing the same public key in multiple operations is faster due to avoiding decompression costs on every use.
   • Less parameters to pass around.
   • No need for separate secp256k1_ecdsa_verify return code to deal with invalid public keys.

   Disadvantages:

   • Need for API calls secp256k1_ec_pubkey_serialize and secp256k1_ec_pubkey_parse.
   • Slightly slower for verification (0.4%) due to extra serialization and weak validation overhead between parsing and verifying.
   • Potentially unsafe when passing an uninitialized secp256k1_pubkey_t for verification, though this is mitigated as much as possible by wiping the output secp256k1_pubkey_t any time an invalid one would be returned, and not accepting a wiped one as input.
2. sipa renamed this:
   Introduce secp256k1_pubkey_t type
   [API CHANGE] Introduce secp256k1_pubkey_t type
   on Jul 20, 2015
3. sipa force-pushed on Jul 20, 2015
4. 
   sipa commented at 7:23 pm on July 20, 2015: contributor

   An alternative to this is having a secp256k1_pubkey_t type that maintains the compressedness, and is just a serialized pubkey, but in a constant-size buffer.

   This has as advantages that it does not add any significant performance overhead, and does not risk extra problems when uninitialized secp256k1_pubkey_t’s are passed in (though that would still be a risky bug for other reasons), but it also would not avoid the compress/decompress/verify API calls, not offer any performance advantages for repeated pubkey use, and be a bit unintuitive for having parsing of an invalid pubkey potentially succeed.

5. 
   sipa commented at 4:42 pm on July 23, 2015: contributor

   @afk11 Any comments here? This significantly changes the way public keys are handled, and removes the need for the secp256k1_ec_pubkey_compress function which you added.
6. sipa force-pushed on Jul 24, 2015
7. 
   sipa commented at 12:59 pm on July 24, 2015: contributor

   Added extra documentation.
8. sipa cross-referenced this on Jul 24, 2015 from issue Implement Schnorr signatures by sipa
9. in src/secp256k1.c: in 24ae07c273 outdated

   70+    secp256k1_fe_normalize_var(&ge->y);
   71+    secp256k1_fe_get_b32(pubkey->data, &ge->x);
   72+    secp256k1_fe_get_b32(pubkey->data + 32, &ge->y);
   73+}
   74+
   75+int secp256k1_ec_pubkey_parse(const secp256k1_context_t* ctx, secp256k1_pubkey_t* pubkey, const unsigned char *input, int inputlen) {
   

   ---

   ---

   

   apoelstra commented at 7:09 pm on July 24, 2015:

   The indentation in this function is different from all the others.
10. 
    apoelstra commented at 7:17 pm on July 24, 2015: contributor

    It looks like bench_recover fails:

    0[apoelstra@titanic secp256k1]$ ./bench_recover 
    1src/bench_recover.c:26: test condition failed: secp256k1_ecdsa_recover_compact(data->ctx, data->msg, data->sig, &pubkey, 1)
    2Aborted
    

11. sipa force-pushed on Jul 24, 2015
12. sipa force-pushed on Jul 24, 2015
13. 
    DavidEGrayson commented at 9:07 pm on July 24, 2015: none

    I was expecting @gmaxwell to point out that _t is reserved by POSIX (see #198).
14. sipa force-pushed on Jul 24, 2015
15. sipa cross-referenced this on Jul 24, 2015 from issue Introduce callback functions for dealing with errors by sipa
16. sipa force-pushed on Jul 25, 2015
17. 
    sipa commented at 3:29 pm on July 25, 2015: contributor

    @DavidEGrayson I thought I already answered, but can’t see the post now @gmaxwell would be right to point that out, but then we should consistently change it throughout the codebase once, not introduce multiple coding standards.
18. 
    sipa commented at 3:30 pm on July 25, 2015: contributor

    I’ve changed the implementation of secp256k1_pubkey_load/save now, using secp256k1_ge_storage where possible… and the result is around 0.15% faster now than before the pubkey_t introduction.
19. sipa renamed this:
    [API CHANGE] Introduce secp256k1_pubkey_t type
    [API CHANGE] Introduce pubkey and signature types
    on Jul 25, 2015
20. 
    sipa commented at 11:55 pm on July 25, 2015: contributor

    I extended the scope of this patch, and introduced a secp256k1_ecdsa_signature_t for ECDSA signatures.
21. sipa force-pushed on Jul 26, 2015
22. in include/secp256k1.h: in 3e9aff1bf0 outdated

    201- *          -2: invalid signature
    202+ *           0: incorrect or unparseable signature
    203  * In:       ctx:       a secp256k1 context object, initialized for verification.
    204  *           msg32:     the 32-byte message hash being verified (cannot be NULL)
    205  *           sig:       the signature being verified (cannot be NULL)
    206  *           siglen:    the length of the signature
    

    ---

    ---

    

    apoelstra commented at 1:34 pm on July 26, 2015:

    Update comment for removal of siglen

    ---

    

    sipa commented at 1:36 pm on July 26, 2015:

    done
23. sipa force-pushed on Jul 26, 2015
24. in include/secp256k1.h: in 3e9aff1bf0 outdated

    331  *          seckey:     pointer to a 32-byte private key (cannot be NULL)
    332- *  Out:    pubkey:     pointer to a 33-byte (if compressed) or 65-byte (if uncompressed)
    333+ *  Out:    pubkey:     pointer to the created public key (cannot be NULL)
    334  *                      area to store the public key (cannot be NULL)
    335  *          pubkeylen:  pointer to int that will be updated to contains the pubkey's
    336  *                      length (cannot be NULL)
    

    ---

    ---

    

    apoelstra commented at 1:38 pm on July 26, 2015:

    Remove second line under pubkey, entry for pubkeylen, entry for compressed in this comment
25. sipa force-pushed on Jul 26, 2015
26. Introduce secp256k1_pubkey_t type 23cfa914d2
27. Add a secp256k1_ecdsa_signature_t type 74a2acdb8a
28. in src/secp256k1.c: in 3e9aff1bf0 outdated

    53@@ -54,11 +54,152 @@ void secp256k1_context_destroy(secp256k1_context_t* ctx) {
    54     free(ctx);
    55 }
    56 
    57-int secp256k1_ecdsa_verify(const secp256k1_context_t* ctx, const unsigned char *msg32, const unsigned char *sig, int siglen, const unsigned char *pubkey, int pubkeylen) {
    58+static void secp256k1_pubkey_load(secp256k1_ge_t* ge, const secp256k1_pubkey_t* pubkey) {
    59+    if (sizeof(secp256k1_ge_storage_t) == 64) {
    

    ---

    ---

    

    apoelstra commented at 1:48 pm on July 26, 2015:

    Under what circumstances is this not 64? You are depending on its exact format in the case that it is, so I’m confused about what you think could change.

    ---

    

    sipa commented at 1:52 pm on July 26, 2015:

    Who knows what a compiler can do with integer sizes and alignments. Maybe we want to add debug fields at some point, when VERIFY is enabled.

    It’s also not relying on its exact representation, only that it can be memcpy’d to and from a 64-byte array, which is faster than going through the b32 representation.

    ---

    

    sipa commented at 1:52 pm on July 26, 2015:

    In any case, this probably requires some comments in the code.

    ---

    

    apoelstra commented at 1:58 pm on July 26, 2015:

    Yeah, I realized that you weren’t depending on the representation down below when I saw you were doing the same thing with scalar_t. I think you should add a comment saying that (assuming the data fits) the API only allows the content of pubkey->data to be a memcpy of a preexisting secp256k1_ge_storage_t, so this is fine.
29. sipa force-pushed on Jul 26, 2015
30. 
    sipa commented at 2:03 pm on July 26, 2015: contributor

    Added several comments about the representation of pubkey and signature types.
31. 
    apoelstra commented at 2:21 pm on July 26, 2015: contributor

    I find it a little confusing to have two signature types, especially ones that are so similarly named. It’s hard to remember which one is the public one and which is the internal.

    The internal one, secp256k1_ecdsa_sig_t, consists of an (r, s) pair, and is used only by the five functions defined in ecdsa.h. If you grep for these five functions you will see that every one of them occurs in only two places: in their passthroughs in the public API, and in the unit tests.

    I propose:

    • Dropping secp256k1_ecdsa_sig_t and having the ecdsa.h functions take a public secp256k1_ecdsa_signature_t.
    • Moving signature_load and signature_save into ecdsa_impl.h, and having them output separate r, s scalars rather than a single struct (since the ecdsa.h functions use the individual scalars and never pass around the complete type anyway).

    This would avoid having separate types and remove some double conversions (like calling secp256k1_ecdsa_sig_parse immediately followed by secp256k1_ecdsa_signature_save in secp256k1_ecdsa_signature_parse_der). Also note that recid is already carried around separately from secp256k1_ecdsa_sig_t, so this type is not doing a great job of encapsulation anyway.

    I don’t feel super strongly about this, it’s up to you.

32. 
    sipa commented at 2:28 pm on July 26, 2015: contributor

    I think that would be a layering violation. the toplevel module defines a data type for external use, and depends on the internal code for operations on it. The lowlevel module would end up depending on the toplevel module if it needed to be passed in the toplevel data type, resulting in a weak circular dependency.

    Furthermore, both datatypes have a different use case: one is obscurity and consistency (at least wrt its size), the other is efficiency.

    Moving the load and save to ecdsa feels wrong, as it makes the ecdsa module depend on external API peculiarities.

    One option is to drop the internal type, and just operate on scalar_t’s inside ecdsa. The other is perhaps to rename the internal types to something more obvious (secp256k1_ecdsa_signature_internal_t ?), and maybe move the recid inside it.

33. 
    apoelstra commented at 2:31 pm on July 26, 2015: contributor

    That’s a good point.

    Between the two options you listed I’d prefer to just operate on scalar_t’s, since there are only two of them and they have standard names.

34. 
    afk11 commented at 2:38 pm on July 26, 2015: contributor

    @sipa concept ACK on this, the performance boost should affect me also since presently I have to serialize my PublicKey types whenever calling secp256k1_* functions. I’ll get to testing this today.
35. Remove the internal secp256k1_ecdsa_sig_t type 18c329c506
36. 
    sipa commented at 2:53 pm on July 26, 2015: contributor

    @apoelstra Added a commit which removes the internal secp256k1_ecdsa_sig_t.
37. 
    apoelstra commented at 2:57 pm on July 26, 2015: contributor

    Thanks, I’m much happier with this.
38. 
    apoelstra commented at 3:25 pm on July 26, 2015: contributor

    ACK
39. sipa merged this on Jul 26, 2015
40. sipa closed this on Jul 26, 2015

    ---

41. sipa referenced this in commit c33307495b on Jul 26, 2015

Contributors
sipa apoelstra DavidEGrayson afk11