1  /***********************************************************************
  2   * Distributed under the MIT software license, see the accompanying    *
  3   * file COPYING or https://www.opensource.org/licenses/mit-license.php.*
  4   ***********************************************************************/
  5  
  6  #ifndef SECP256K1_MODULE_MUSIG_KEYAGG_IMPL_H
  7  #define SECP256K1_MODULE_MUSIG_KEYAGG_IMPL_H
  8  
  9  #include <string.h>
 10  
 11  #include "keyagg.h"
 12  #include "../../eckey.h"
 13  #include "../../ecmult.h"
 14  #include "../../field.h"
 15  #include "../../group.h"
 16  #include "../../hash.h"
 17  #include "../../util.h"
 18  
 19  static const unsigned char secp256k1_musig_keyagg_cache_magic[4] = { 0xf4, 0xad, 0xbb, 0xdf };
 20  
 21  /* A keyagg cache consists of
 22   * - 4 byte magic set during initialization to allow detecting an uninitialized
 23   *   object.
 24   * - 64 byte aggregate (and potentially tweaked) public key
 25   * - 64 byte "second" public key (set to the point at infinity if not present)
 26   * - 32 byte hash of all public keys
 27   * - 1 byte the parity of the internal key (if tweaked, otherwise 0)
 28   * - 32 byte tweak
 29   */
 30  /* Requires that cache_i->pk is not infinity. */
 31  static void secp256k1_keyagg_cache_save(secp256k1_musig_keyagg_cache *cache, const secp256k1_keyagg_cache_internal *cache_i) {
 32      unsigned char *ptr = cache->data;
 33      memcpy(ptr, secp256k1_musig_keyagg_cache_magic, 4);
 34      ptr += 4;
 35      secp256k1_ge_to_bytes(ptr, &cache_i->pk);
 36      ptr += 64;
 37      secp256k1_ge_to_bytes_ext(ptr, &cache_i->second_pk);
 38      ptr += 64;
 39      memcpy(ptr, cache_i->pks_hash, 32);
 40      ptr += 32;
 41      *ptr = cache_i->parity_acc;
 42      ptr += 1;
 43      secp256k1_scalar_get_b32(ptr, &cache_i->tweak);
 44  }
 45  
 46  static int secp256k1_keyagg_cache_load(const secp256k1_context* ctx, secp256k1_keyagg_cache_internal *cache_i, const secp256k1_musig_keyagg_cache *cache) {
 47      const unsigned char *ptr = cache->data;
 48      ARG_CHECK(secp256k1_memcmp_var(ptr, secp256k1_musig_keyagg_cache_magic, 4) == 0);
 49      ptr += 4;
 50      secp256k1_ge_from_bytes(&cache_i->pk, ptr);
 51      ptr += 64;
 52      secp256k1_ge_from_bytes_ext(&cache_i->second_pk, ptr);
 53      ptr += 64;
 54      memcpy(cache_i->pks_hash, ptr, 32);
 55      ptr += 32;
 56      cache_i->parity_acc = *ptr & 1;
 57      ptr += 1;
 58      secp256k1_scalar_set_b32(&cache_i->tweak, ptr, NULL);
 59      return 1;
 60  }
 61  
 62  /* Initializes SHA256 with fixed midstate. This midstate was computed by applying
 63   * SHA256 to SHA256("KeyAgg list")||SHA256("KeyAgg list"). */
 64  static void secp256k1_musig_keyagglist_sha256(secp256k1_sha256 *sha) {
 65      static const uint32_t midstate[8] = {
 66          0xb399d5e0ul, 0xc8fff302ul, 0x6badac71ul, 0x07c5b7f1ul,
 67          0x9701e2eful, 0x2a72ecf8ul, 0x201a4c7bul, 0xab148a38ul
 68      };
 69      secp256k1_sha256_initialize_midstate(sha, 64, midstate);
 70  }
 71  
 72  /* Computes pks_hash = tagged_hash(pk[0], ..., pk[np-1]) */
 73  static int secp256k1_musig_compute_pks_hash(const secp256k1_context *ctx, unsigned char *pks_hash, const secp256k1_pubkey * const* pks, size_t np) {
 74      secp256k1_sha256 sha;
 75      size_t i;
 76  
 77      secp256k1_musig_keyagglist_sha256(&sha);
 78      for (i = 0; i < np; i++) {
 79          unsigned char ser[33];
 80          size_t ser_len = sizeof(ser);
 81          if (!secp256k1_ec_pubkey_serialize(ctx, ser, &ser_len, pks[i], SECP256K1_EC_COMPRESSED)) {
 82              return 0;
 83          }
 84          VERIFY_CHECK(ser_len == sizeof(ser));
 85          secp256k1_sha256_write(secp256k1_get_hash_context(ctx), &sha, ser, sizeof(ser));
 86      }
 87      secp256k1_sha256_finalize(secp256k1_get_hash_context(ctx), &sha, pks_hash);
 88      return 1;
 89  }
 90  
 91  /* Initializes SHA256 with fixed midstate. This midstate was computed by applying
 92   * SHA256 to SHA256("KeyAgg coefficient")||SHA256("KeyAgg coefficient"). */
 93  static void secp256k1_musig_keyaggcoef_sha256(secp256k1_sha256 *sha) {
 94      static const uint32_t midstate[8] = {
 95          0x6ef02c5aul, 0x06a480deul, 0x1f298665ul, 0x1d1134f2ul,
 96          0x56a0b063ul, 0x52da4147ul, 0xf280d9d4ul, 0x4484be15ul
 97      };
 98      secp256k1_sha256_initialize_midstate(sha, 64, midstate);
 99  }
100  
101  /* Compute KeyAgg coefficient which is constant 1 for the second pubkey and
102   * otherwise tagged_hash(pks_hash, pk) where pks_hash is the hash of public keys.
103   * second_pk is the point at infinity in case there is no second_pk. Assumes
104   * that pk is not the point at infinity and that the Y-coordinates of pk and
105   * second_pk are normalized. */
106  static void secp256k1_musig_keyaggcoef_internal(const secp256k1_hash_ctx *hash_ctx, secp256k1_scalar *r, const unsigned char *pks_hash, secp256k1_ge *pk, const secp256k1_ge *second_pk) {
107      VERIFY_CHECK(!secp256k1_ge_is_infinity(pk));
108  
109      if (!secp256k1_ge_is_infinity(second_pk)
110            && secp256k1_ge_eq_var(pk, second_pk)) {
111          secp256k1_scalar_set_int(r, 1);
112      } else {
113          secp256k1_sha256 sha;
114          unsigned char buf[33];
115          secp256k1_musig_keyaggcoef_sha256(&sha);
116          secp256k1_sha256_write(hash_ctx, &sha, pks_hash, 32);
117          /* Serialization does not fail since the pk is not the point at infinity
118           * (according to this function's precondition). */
119          secp256k1_eckey_pubkey_serialize33(pk, buf);
120          secp256k1_sha256_write(hash_ctx, &sha, buf, sizeof(buf));
121          secp256k1_sha256_finalize(hash_ctx, &sha, buf);
122          secp256k1_scalar_set_b32(r, buf, NULL);
123      }
124  }
125  
126  /* Assumes that pk is not the point at infinity and that the Y-coordinates of pk
127   * and cache_i->second_pk are normalized. */
128  static void secp256k1_musig_keyaggcoef(const secp256k1_hash_ctx *hash_ctx, secp256k1_scalar *r, const secp256k1_keyagg_cache_internal *cache_i, secp256k1_ge *pk) {
129      secp256k1_musig_keyaggcoef_internal(hash_ctx, r, cache_i->pks_hash, pk, &cache_i->second_pk);
130  }
131  
132  typedef struct {
133      const secp256k1_context *ctx;
134      /* pks_hash is the hash of the public keys */
135      unsigned char pks_hash[32];
136      const secp256k1_pubkey * const* pks;
137      secp256k1_ge second_pk;
138  } secp256k1_musig_pubkey_agg_ecmult_data;
139  
140  /* Callback for batch EC multiplication to compute keyaggcoef_0*P0 + keyaggcoef_1*P1 + ...  */
141  static int secp256k1_musig_pubkey_agg_callback(secp256k1_scalar *sc, secp256k1_ge *pt, size_t idx, void *data) {
142      secp256k1_musig_pubkey_agg_ecmult_data *ctx = (secp256k1_musig_pubkey_agg_ecmult_data *) data;
143      int ret;
144      ret = secp256k1_pubkey_load(ctx->ctx, pt, ctx->pks[idx]);
145  #ifdef VERIFY
146      /* pubkey_load can't fail because the same pks have already been loaded in
147       * `musig_compute_pks_hash` (and we test this). */
148      VERIFY_CHECK(ret);
149  #else
150      (void) ret;
151  #endif
152      secp256k1_musig_keyaggcoef_internal(secp256k1_get_hash_context(ctx->ctx), sc, ctx->pks_hash, pt, &ctx->second_pk);
153      return 1;
154  }
155  
156  int secp256k1_musig_pubkey_agg(const secp256k1_context* ctx, secp256k1_xonly_pubkey *agg_pk, secp256k1_musig_keyagg_cache *keyagg_cache, const secp256k1_pubkey * const* pubkeys, size_t n_pubkeys) {
157      secp256k1_musig_pubkey_agg_ecmult_data ecmult_data;
158      secp256k1_gej pkj;
159      secp256k1_ge pkp;
160      size_t i;
161  
162      VERIFY_CHECK(ctx != NULL);
163      if (agg_pk != NULL) {
164          memset(agg_pk, 0, sizeof(*agg_pk));
165      }
166      ARG_CHECK(pubkeys != NULL);
167      ARG_CHECK(n_pubkeys > 0);
168      for (i = 0; i < n_pubkeys; i++) {
169          ARG_CHECK(pubkeys[i] != NULL);
170      }
171  
172      ecmult_data.ctx = ctx;
173      ecmult_data.pks = pubkeys;
174  
175      secp256k1_ge_set_infinity(&ecmult_data.second_pk);
176      for (i = 1; i < n_pubkeys; i++) {
177          if (secp256k1_memcmp_var(pubkeys[0], pubkeys[i], sizeof(*pubkeys[0])) != 0) {
178              secp256k1_ge pk;
179              if (!secp256k1_pubkey_load(ctx, &pk, pubkeys[i])) {
180                  return 0;
181              }
182              ecmult_data.second_pk = pk;
183              break;
184          }
185      }
186  
187      if (!secp256k1_musig_compute_pks_hash(ctx, ecmult_data.pks_hash, pubkeys, n_pubkeys)) {
188          return 0;
189      }
190      /* TODO: actually use optimized ecmult_multi algorithms by providing a
191       * scratch space */
192      if (!secp256k1_ecmult_multi_var(&ctx->error_callback, NULL, &pkj, NULL, secp256k1_musig_pubkey_agg_callback, (void *) &ecmult_data, n_pubkeys)) {
193          /* In order to reach this line with the current implementation of
194           * ecmult_multi_var one would need to provide a callback that can
195           * fail. */
196          return 0;
197      }
198      secp256k1_ge_set_gej(&pkp, &pkj);
199      secp256k1_fe_normalize_var(&pkp.y);
200      /* The resulting public key is infinity with negligible probability */
201      VERIFY_CHECK(!secp256k1_ge_is_infinity(&pkp));
202      if (keyagg_cache != NULL) {
203          secp256k1_keyagg_cache_internal cache_i = { 0 };
204          cache_i.pk = pkp;
205          cache_i.second_pk = ecmult_data.second_pk;
206          memcpy(cache_i.pks_hash, ecmult_data.pks_hash, sizeof(cache_i.pks_hash));
207          secp256k1_keyagg_cache_save(keyagg_cache, &cache_i);
208      }
209  
210      if (agg_pk != NULL) {
211          secp256k1_extrakeys_ge_even_y(&pkp);
212          secp256k1_xonly_pubkey_save(agg_pk, &pkp);
213      }
214      return 1;
215  }
216  
217  int secp256k1_musig_pubkey_get(const secp256k1_context* ctx, secp256k1_pubkey *agg_pk, const secp256k1_musig_keyagg_cache *keyagg_cache) {
218      secp256k1_keyagg_cache_internal cache_i;
219      VERIFY_CHECK(ctx != NULL);
220      ARG_CHECK(agg_pk != NULL);
221      memset(agg_pk, 0, sizeof(*agg_pk));
222      ARG_CHECK(keyagg_cache != NULL);
223  
224      if (!secp256k1_keyagg_cache_load(ctx, &cache_i, keyagg_cache)) {
225          return 0;
226      }
227      secp256k1_pubkey_save(agg_pk, &cache_i.pk);
228      return 1;
229  }
230  
231  static int secp256k1_musig_pubkey_tweak_add_internal(const secp256k1_context* ctx, secp256k1_pubkey *output_pubkey, secp256k1_musig_keyagg_cache *keyagg_cache, const unsigned char *tweak32, int xonly) {
232      secp256k1_keyagg_cache_internal cache_i;
233      int overflow = 0;
234      secp256k1_scalar tweak;
235  
236      VERIFY_CHECK(ctx != NULL);
237      if (output_pubkey != NULL) {
238          memset(output_pubkey, 0, sizeof(*output_pubkey));
239      }
240      ARG_CHECK(keyagg_cache != NULL);
241      ARG_CHECK(tweak32 != NULL);
242  
243      if (!secp256k1_keyagg_cache_load(ctx, &cache_i, keyagg_cache)) {
244          return 0;
245      }
246      secp256k1_scalar_set_b32(&tweak, tweak32, &overflow);
247      if (overflow) {
248          return 0;
249      }
250      if (xonly && secp256k1_extrakeys_ge_even_y(&cache_i.pk)) {
251          cache_i.parity_acc ^= 1;
252          secp256k1_scalar_negate(&cache_i.tweak, &cache_i.tweak);
253      }
254      secp256k1_scalar_add(&cache_i.tweak, &cache_i.tweak, &tweak);
255      if (!secp256k1_eckey_pubkey_tweak_add(&cache_i.pk, &tweak)) {
256          return 0;
257      }
258      /* eckey_pubkey_tweak_add fails if cache_i.pk is infinity */
259      VERIFY_CHECK(!secp256k1_ge_is_infinity(&cache_i.pk));
260      secp256k1_keyagg_cache_save(keyagg_cache, &cache_i);
261      if (output_pubkey != NULL) {
262          secp256k1_pubkey_save(output_pubkey, &cache_i.pk);
263      }
264      return 1;
265  }
266  
267  int secp256k1_musig_pubkey_ec_tweak_add(const secp256k1_context* ctx, secp256k1_pubkey *output_pubkey, secp256k1_musig_keyagg_cache *keyagg_cache, const unsigned char *tweak32) {
268      return secp256k1_musig_pubkey_tweak_add_internal(ctx, output_pubkey, keyagg_cache, tweak32, 0);
269  }
270  
271  int secp256k1_musig_pubkey_xonly_tweak_add(const secp256k1_context* ctx, secp256k1_pubkey *output_pubkey, secp256k1_musig_keyagg_cache *keyagg_cache, const unsigned char *tweak32) {
272      return secp256k1_musig_pubkey_tweak_add_internal(ctx, output_pubkey, keyagg_cache, tweak32, 1);
273  }
274  
275  #endif