Changeset View
Standalone View
src/secp256k1/src/modules/schnorr/schnorr_impl.h
Show First 20 Lines • Show All 239 Lines • ▼ Show 20 Lines | while (1) { | ||||
secp256k1_scalar_clear(k); | secp256k1_scalar_clear(k); | ||||
} | } | ||||
memset(seckey, 0, 32); | memset(seckey, 0, 32); | ||||
memset(nonce32, 0, 32); | memset(nonce32, 0, 32); | ||||
return ret; | return ret; | ||||
} | } | ||||
/** | |||||
* Schnorr signatures are linear and therefore lend themselves to aggregation. | |||||
* However, it is possible for one party to chose it key judiciously such as | |||||
Fabien: it => its | |||||
* it cancels the key of another party. Consider the two parties: | |||||
* Alice: A = a * G | |||||
* Bob: B = b * G | |||||
* | |||||
* Bob could pretend that his public key is Q = B - A, and lead Alice to | |||||
* to believe that she did share a key with Bob, when in fact Bob has the | |||||
* sole control of the key. | |||||
* In order to solve this problem, we derive a new key for both Alice and Bob | |||||
* in such a way that it is not possible for either Alice or Bob to chose | |||||
* his or her key depending on the key of the other. | |||||
* | |||||
* The procedure goes as follow: | |||||
* C = H(A || B || ...) | |||||
* A' = H(C || A) * A | |||||
* B' = H(C || B) * B | |||||
* The combined key is P = A' + B' + ... | |||||
* | |||||
* Anyone can verify that the key are combined properly as it doesn't require | |||||
* any private info to do so. Each participant is also able to derive a new | |||||
* private key from the existing one as follow: | |||||
* Alice: a' = a * H(C || A) | |||||
* Bob: b' = b * H(C || B) | |||||
* | |||||
* Because only Alice knows her private key, only she can compute the partial | |||||
* private key required to interract with Bob, and vice versa. | |||||
*/ | |||||
static int secp256k1_schnorr_multisig_compute_c( | |||||
const secp256k1_context *ctx, | |||||
unsigned char *C, | |||||
const secp256k1_pubkey *pubkeys, | |||||
const size_t nkeys | |||||
) { | |||||
size_t i, size; | |||||
secp256k1_sha256 sha; | |||||
secp256k1_ge q; | |||||
unsigned char buf[33]; | |||||
secp256k1_sha256_initialize(&sha); | |||||
/* Hash all the keys */ | |||||
for (i = 0; i < nkeys; i++) { | |||||
/** | |||||
* We do so by hashing the serialization fo all the keys one by one. | |||||
markblundebergUnsubmitted Not Done Inline Actionscompressed serialization, just to be clear markblundeberg: compressed serialization, just to be clear | |||||
FabienUnsubmitted Not Done Inline Actionsfo => for Fabien: fo => for | |||||
* However, this is not ideal because it makes the construction | |||||
* dependent ont he ordering of the keys. It may be preferable to | |||||
FabienUnsubmitted Not Done Inline Actionshe => the Fabien: he => the | |||||
* change this to use the multiset construction in the future. | |||||
markblundebergUnsubmitted Not Done Inline ActionsYes, I was wondering about this ordering issue too. Should be simple enough to just sort the pubkeys lexically since we don't require any fancy insert/remove behaviour. markblundeberg: Yes, I was wondering about this ordering issue too. Should be simple enough to just sort the… | |||||
*/ | |||||
secp256k1_pubkey_load(ctx, &q, &pubkeys[i]); | |||||
secp256k1_eckey_pubkey_serialize(&q, buf, &size, 1); | |||||
VERIFY_CHECK(size == 33); | |||||
secp256k1_sha256_write(&sha, buf, 33); | |||||
} | |||||
/* Compute C */ | |||||
secp256k1_sha256_finalize(&sha, C); | |||||
return 1; | |||||
} | |||||
static int secp256k1_schnorr_multisig_compute_tweak( | |||||
secp256k1_scalar *tweak, | |||||
const unsigned char *C, | |||||
secp256k1_ge *pubkey | |||||
) { | |||||
int overflow = 0; | |||||
size_t size; | |||||
unsigned char buf[33]; | |||||
secp256k1_sha256 sha; | |||||
secp256k1_sha256_initialize(&sha); | |||||
secp256k1_sha256_write(&sha, C, 32); | |||||
secp256k1_eckey_pubkey_serialize(pubkey, buf, &size, 1); | |||||
VERIFY_CHECK(size == 33); | |||||
secp256k1_sha256_write(&sha, buf, 33); | |||||
secp256k1_sha256_finalize(&sha, buf); | |||||
secp256k1_scalar_set_b32(tweak, buf, &overflow); | |||||
return !overflow & !secp256k1_scalar_is_zero(tweak); | |||||
markblundebergUnsubmitted Not Done Inline ActionsSeems more ideal if this never fails. That was always one of the totally unnecessary warts that bothered me about BIP32 (failure to generate key). An alternative never-fail: if tweak == 0: tweak = order-1 elif tweak == order: tweak = order-2 else: tweak = tweak % order or, with slightly more bias, tweak = tweak % order if tweak == 0: tweak = order-1 Failure is ok for interactive MuSig key generation because you can restart session, but if it's interactive then you don't actually need MuSig to begin with. You could just use random pre-committed keys with simple A+B+C+D aggregation. If you have a critical non-interactive key generation and restarting is not possible, then this could cause a deadlock with 2^-128 chance. In fact even doing just tweak = tweak % order (allowing for tweak=0 which unfortunately cancels someone's key, with 2^-255 chance) may be preferable to having a deadlock. markblundeberg: Seems more ideal if this never fails. That was always one of the totally unnecessary warts that… | |||||
markblundebergUnsubmitted Not Done Inline ActionsHmm, on second thought, the entire MuSig can fail if the final key ends up being point at infinity. So maybe it does fundamentally need a counter-increment-retry mechanism for computing C. markblundeberg: Hmm, on second thought, the entire MuSig can fail if the final key ends up being point at… | |||||
} | |||||
static int secp256k1_schnorr_multisig_compute_pubkey( | |||||
secp256k1_ge *partial_pubkey, | |||||
const unsigned char *C, | |||||
secp256k1_ge *pubkey | |||||
) { | |||||
secp256k1_scalar tweak; | |||||
secp256k1_gej Qj; | |||||
if (!secp256k1_schnorr_multisig_compute_tweak(&tweak, C, pubkey)) { | |||||
return 0; | |||||
} | |||||
secp256k1_ecmult_const(&Qj, pubkey, &tweak); | |||||
secp256k1_ge_set_gej(partial_pubkey, &Qj); | |||||
return 1; | |||||
} | |||||
static int secp256k1_schnorr_multisig_compute_privkey( | |||||
secp256k1_scalar *partial_privkey, | |||||
const unsigned char *C, | |||||
const secp256k1_scalar *privkey, | |||||
secp256k1_ge *pubkey | |||||
) { | |||||
secp256k1_scalar tweak; | |||||
if (!secp256k1_schnorr_multisig_compute_tweak(&tweak, C, pubkey)) { | |||||
return 0; | |||||
} | |||||
secp256k1_scalar_mul(partial_privkey, privkey, &tweak); | |||||
return 1; | |||||
} | |||||
static int secp256k1_schnorr_multisig_combine_keys( | |||||
const secp256k1_context *ctx, | |||||
secp256k1_ge *combined_pubkey, | |||||
const unsigned char *C, | |||||
const secp256k1_pubkey *pubkeys, | |||||
const size_t nkeys | |||||
) { | |||||
size_t i; | |||||
secp256k1_ge q; | |||||
secp256k1_gej Pj; | |||||
/* Aggregate the keys */ | |||||
secp256k1_gej_set_infinity(&Pj); | |||||
for (i = 0; i < nkeys; i++) { | |||||
secp256k1_pubkey_load(ctx, &q, &pubkeys[i]); | |||||
if (!secp256k1_schnorr_multisig_compute_pubkey(&q, C, &q)) { | |||||
return 0; | |||||
} | |||||
/** | |||||
* There are more effiscient ways to do this, but this | |||||
FabienUnsubmitted Not Done Inline Actionseffiscient => efficient Fabien: effiscient => efficient | |||||
* is the simplest, and will do for now. | |||||
* TODO: Use more effiscient algorithm such as pippenger. | |||||
FabienUnsubmitted Not Done Inline Actionsdito Fabien: dito | |||||
*/ | |||||
secp256k1_gej_add_ge(&Pj, &Pj, &q); | |||||
} | |||||
secp256k1_ge_set_gej(combined_pubkey, &Pj); | |||||
return 1; | |||||
} | |||||
#endif | #endif |
it => its