Page MenuHomePhabricator

[schnorr] Add features to combine public keys in order to do musig.
Needs RevisionPublic

Authored by deadalnix on Feb 9 2019, 21:17.

Details

Reviewers
Fabien
Group Reviewers
Restricted Project
Summary

This add facilities to combine public keys to do schnorr musig. It also includes a facility to compute the partial private key corresponding to the share.

Depends on D2457

Test Plan

Added test cases

Diff Detail

Repository
rABC Bitcoin ABC
Branch
pubkeycombine
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 4942
Build 7947: Bitcoin ABC Teamcity Staging
Build 7946: arc lint + arc unit

Event Timeline

deadalnix created this revision.Feb 9 2019, 21:17
Herald added a reviewer: Restricted Project. · View Herald TranscriptFeb 9 2019, 21:17
Herald added a subscriber: schancel. · View Herald Transcript

Quick comment for now, I'd like to take a closer look later.

src/secp256k1/src/modules/schnorr/main_impl.h
79

Looks like unsigned long int may be better for nkeys. Bizarrely, size_t is allowed to be as small as 16 bits, in C99 standard.

https://stackoverflow.com/questions/22514803/maximum-size-of-size-t

(maybe matters if anyone ever throws this into a weird hardware wallet embedded system)

markblundeberg added inline comments.Feb 10 2019, 00:38
src/secp256k1/src/modules/schnorr/schnorr_impl.h
292

compressed serialization, just to be clear

295

Yes, 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.

326

Seems 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 added inline comments.Feb 10 2019, 00:42
src/secp256k1/src/modules/schnorr/schnorr_impl.h
326

Hmm, 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.

Fabien requested changes to this revision.Feb 12 2019, 17:11
Fabien added a subscriber: Fabien.
Fabien added inline comments.
src/secp256k1/include/secp256k1_schnorr.h
56

priavate => private

src/secp256k1/src/modules/schnorr/main_impl.h
79

This is likely not the responsibility of the lib, but shouldn't the number of keys be (much) more limited ?
1<<31 keys is already a 128GiB buffer to store the public keys, and the computation needed will give the CPU a good warmup.

src/secp256k1/src/modules/schnorr/schnorr_impl.h
250

it => its

292

fo => for

294

he => the

381

effiscient => efficient

383

dito

This revision now requires changes to proceed.Feb 12 2019, 17:11
deadalnix added inline comments.Feb 14 2019, 12:01
src/secp256k1/src/modules/schnorr/main_impl.h
79

If people want to do it, then good for them.