Add an experimental schnorr signature adaptor module

[ZhePang]

Overview

This PR adds support for Schnorr Adaptor signatures. It is based on the work of Schnorr Signature by @jonasnick and @apoelstra, and the discussion #191.

Schnorr Adaptor Signatures

This implementation is mainly based on the idea of adaptor signatures in BIP-340 specification. It refers to the design and implementation of ECDSA adaptor signatures and MuSig2 adaptor signature.

Instead of having a verification algorithm for the adaptor signature, this module uses extract_t which extracts the adaptor point from the adaptor signature. (graph for complete atomic swap process)

Python

A Python specification of Schnorr Adaptor signatures has also been implemented, which generates all test vectors for the module.

[ssantos21]

Concept ACK.

It might be interesting to include a examples/adaptor.c file.

[instagibbs]

It might be interesting to include a examples/adaptor.c file.

this would be great :)

[ZhePang]

@ssantos21 @instagibbs Thanks for the advice! I'll for sure add the example code for Schnorr Adaptor.

[ZhePang]

This pull request is still under review and most likely will have some modifications. Feel free to give me more suggestions and advice!

[siv2r]

The current const time test is failing because:

• invalid compressed adaptor point value used (the pt doesn't lie on the secp curve)
• pre_sig doesn’t declassify R, and T before using them is gej_add_ge_var

I have fixed these issues in this commit: https://github.com/siv2r/secp256k1-zkp/commit/ad1cc6e78be02f5c99cdf3dcc66c64576b2735f8. Feel free to cherry-pick it using git or simply copy the changes :)

The commit also adds const-time tests for the adapt, and extract_adaptor APIs.

[instagibbs]

Pushed an example file, in the pattern of proposed LN PTLC usage: https://github.com/instagibbs/secp256k1-zkp/tree/schnorr-adaptor-signature-example

feel free to cherry-pick as well

[jonasnick]

We've just merged https://github.com/BlockstreamResearch/secp256k1-zkp/pull/270 which means that this PR can be rebased to fix CI. Note that rebasing may require some additional changes that are documented in https://github.com/BlockstreamResearch/secp256k1-zkp/discussions/271. Let me know if you have any questions.

[Tibo-lg]

I was playing around with this, and it's great! Though one issue I encountered is that the schnorr_adaptor_extract_adaptor will sometimes lead to a call to the illegal_callback for invalid adaptor signatures when the extracted public key is invalid (which leads to a panic at the rust layer). This makes is not a very good method for verifying adaptor signatures.

[ZhePang]

I was playing around with this, and it's great! Though one issue I encountered is that the schnorr_adaptor_extract_adaptor will sometimes lead to a call to the illegal_callback for invalid adaptor signatures when the extracted public key is invalid (which leads to a panic at the rust layer). This makes is not a very good method for verifying adaptor signatures.

Hi @Tibo-lg , we expect users to call schnorr_adaptor_extract (was extract_t) before schnorr_adaptor_extract_sec (was schnorr_adaptor_extract_adaptor) so in this way the adaptor signature passed to 'extract_sec' is valid and would not raise illegal_callback. We'll put that in the documentation, thanks for mentioning it up!

[jonasnick]

Hi @Tibo-lg , we expect users to call schnorr_adaptor_extract (was extract_t) before schnorr_adaptor_extract_sec (was schnorr_adaptor_extract_adaptor) so in this way the adaptor signature passed to 'extract_sec' is valid and would not raise illegal_callback. We'll put that in the documentation, thanks for mentioning it up!

Actually we don't. Sorry, I was wrong when we talked about this. Typically, the party that created the adaptor signature would call extract_sec and therefore they know that they created the first byte correctly. But since this cannot be guaranteed in a proper type safe language like rust, I'd prefer if we'd remove the ARG_CHECK and just returned 0 instead.

[jonasnick]

Here's my suggestion for a module level documentation (to be put at the top of include/secp256k1_schnorr_adaptor.h):

/** This module provides an experimental implementation of a Schnorr adaptor
 *  signature protocol variant.
 *
 *  The test vectors have been generated and cross-verified using a Python
 *  implementation of this adaptor signature variant available at [0].
 *
 *  The protocol involves two parties, Alice and Bob. The general sequence of
 *  their interaction is as follows:
 *  1. Alice calls the `schnorr_adaptor_presign` function for an adaptor point T
 *  and sends the pre-signature to Bob.
 *  2. Bob extracts the adaptor point T from the pre-signature using
 *  `schnorr_adaptor_extract`.
 *  3. Bob provides the pre-signature and the discrete logarithm of T to
 *  `schnorr_adaptor_adapt` which outputs a valid BIP 340 Schnorr signature.
 *  4. Alice extracts the discrete logarithm of T from the pre-signature and the
 *  BIP 340 signature using `schnorr_adaptor_extract_sec`.
 *
 *  In contrast to common descriptions of adaptor signature protocols, this
 *  module does not provide a verification algorithm for pre-signatures.
 *  Instead, `schnorr_adaptor_extract` returns the adaptor point encoded by a
 *  pre-signature, reducing communication cost. If a verification function for
 *  pre-signatures is needed, it can be easily simulated with
 *  `schnorr_adaptor_extract`.
 *
 *  Assuming that BIP 340 Schnorr signatures satisfy strong unforgeability under
 *  chosen message attack, the Schnorr adaptor signature scheme fulfills the
 *  following properties as formalized by [1].
 *
 *  - Witness extractability:
 *    If Alice
 *      1. creates a pre-signature with `schnorr_adaptor_presign` for message m
 *         and adaptor point T and
 *      2. receives a Schnorr signature for message m that she hasn't created
 *         herself,
 *    then Alice is able to obtain the discrete logarithm of T with
 *    `schnorr_adaptor_extract_sec`.
 *
 *  - Pre-signature adaptability:
 *    If Bob
 *      1. receives a pre-signature and extracts an adaptor point T using
 *         `schnorr_adaptor_extract`, and
 *      2. obtains the discrete logarithm of the adaptor point T
 *    Then then Bob is able to adapt the received pre-signature to a valid BIP
 *    340 Schnorr signature using `schnorr_adaptor_adapt`.
 *
 *  - Existential Unforgeability:
 *    Bob is not able to create a BIP 340 signature from a pre-signature for
 *    adaptor T without knowing the discrete logarithm of T.
 *
 *  - Pre-signature existiential unforgeability:
 *    Only Alice can create a pre-signature for her public key.
 *
 *  [0] https://github.com/ZhePang/Python_Specification_for_Schnorr_Adaptor
 *  [1] https://eprint.iacr.org/2020/476.pdf
 */

[ZhePang]

There were a few warnings during compilation, but all tests passed successfully.

warnings

src/ctime_tests.c: In function ‘run_tests’:
src/ctime_tests.c:212:74: warning: passing argument 5 of ‘secp256k1_schnorr_adaptor_presign’ from incompatible pointer type [-Wincompatible-pointer-types]
  212 |         ret = secp256k1_schnorr_adaptor_presign(ctx, sig, msg, &keypair, t, NULL);
      |                                                                          ^
      |                                                                          |
      |                                                                          unsigned char *
In file included from src/ctime_tests.c:35:
src/../include/secp256k1_schnorr_adaptor.h:72:29: note: expected ‘const secp256k1_pubkey *’ {aka ‘const struct <anonymous> *’} but argument is of type ‘unsigned char *’
   72 |     const secp256k1_pubkey *adaptor,
      |     ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
In file included from src/secp256k1.c:896,
                 from src/bench_ecmult.c:8:
src/modules/schnorr_adaptor/main_impl.h: In function ‘secp256k1_schnorr_adaptor_extract’:
src/modules/schnorr_adaptor/main_impl.h:197:12: warning: unused variable ‘size’ [-Wunused-variable]
  197 |     size_t size = 33;
      |            ^~~~
In file included from src/secp256k1.c:896,
                 from src/tests.c:20:
src/modules/schnorr_adaptor/main_impl.h: In function ‘secp256k1_schnorr_adaptor_extract’:
src/modules/schnorr_adaptor/main_impl.h:197:12: warning: unused variable ‘size’ [-Wunused-variable]
  197 |     size_t size = 33;
      |            ^~~~
In file included from src/secp256k1.c:896,
                 from src/bench_internal.c:8:
src/modules/schnorr_adaptor/main_impl.h: In function ‘secp256k1_schnorr_adaptor_extract’:
src/modules/schnorr_adaptor/main_impl.h:197:12: warning: unused variable ‘size’ [-Wunused-variable]
  197 |     size_t size = 33;
      |            ^~~~
In file included from src/secp256k1.c:896,
                 from src/tests_exhaustive.c:23:
src/modules/schnorr_adaptor/main_impl.h: In function ‘secp256k1_schnorr_adaptor_extract’:
src/modules/schnorr_adaptor/main_impl.h:197:12: warning: unused variable ‘size’ [-Wunused-variable]
  197 |     size_t size = 33;
      |            ^~~~
In file included from src/secp256k1.c:896,
                 from src/tests.c:20:
src/modules/schnorr_adaptor/main_impl.h: In function ‘secp256k1_schnorr_adaptor_extract’:
src/modules/schnorr_adaptor/main_impl.h:197:12: warning: unused variable ‘size’ [-Wunused-variable]
  197 |     size_t size = 33;
      |            ^~~~
In file included from src/secp256k1.c:896:
src/modules/schnorr_adaptor/main_impl.h: In function ‘secp256k1_schnorr_adaptor_extract’:
src/modules/schnorr_adaptor/main_impl.h:197:12: warning: unused variable ‘size’ [-Wunused-variable]
  197 |     size_t size = 33;
      |            ^~~~
In file included from src/tests.c:7474:
src/modules/schnorr_adaptor/tests_impl.h: In function ‘test_schnorr_adaptor_api’:
src/modules/schnorr_adaptor/tests_impl.h:141:5: warning: ignoring return value of ‘secp256k1_ec_pubkey_parse’, declared with attribute warn_unused_result [-Wunused-result]
  141 |     secp256k1_ec_pubkey_parse(CTX, &t, adaptor33, 33);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from src/tests.c:7474:
src/modules/schnorr_adaptor/tests_impl.h: In function ‘test_schnorr_adaptor_vectors_check_presigning’:
src/modules/schnorr_adaptor/tests_impl.h:180:5: warning: ignoring return value of ‘secp256k1_ec_pubkey_parse’, declared with attribute warn_unused_result [-Wunused-result]
  180 |     secp256k1_ec_pubkey_parse(CTX, &adaptor, adaptor33, 33);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from src/tests.c:7474:
src/modules/schnorr_adaptor/tests_impl.h: In function ‘test_schnorr_adaptor_api’:
src/modules/schnorr_adaptor/tests_impl.h:141:5: warning: ignoring return value of ‘secp256k1_ec_pubkey_parse’, declared with attribute warn_unused_result [-Wunused-result]
  141 |     secp256k1_ec_pubkey_parse(CTX, &t, adaptor33, 33);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from src/tests.c:7474:
src/modules/schnorr_adaptor/tests_impl.h: In function ‘test_schnorr_adaptor_vectors_check_presigning’:
src/modules/schnorr_adaptor/tests_impl.h:180:5: warning: ignoring return value of ‘secp256k1_ec_pubkey_parse’, declared with attribute warn_unused_result [-Wunused-result]
  180 |     secp256k1_ec_pubkey_parse(CTX, &adaptor, adaptor33, 33);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

I probably forgot to delete some unused variables. And ec_pubkey_parse returns a 0/1 value, I'll put it into a CHECK

About the time_test warning, I forgot to change the code there and it might takes the original input format.