Open oleganza opened 5 years ago
Seems like for "51%" threshold with a predicate tree and k-of-k keys, the merkle proof grows linearly with the number of parties:
https://www.wolframalpha.com/input/?i=plot+log_2%5BBinomial%5B2k,k%2B1%5D%5D+for+k+from+1+to+10
About MuSig
For multi-signature accounts and multi-party contracts we need to implement a n-of-n MuSig protocol (overview, paper).
The verification construction is very similar to the aggregated transaction signature except the key aggregation happens offline — the verifier is exposed only to the single pubkey.
The proving construction is a 3-round MuSig procedure (see the MuSig paper).
We'll also need to extend the ZkVM witness types and Prover API to handle the multi-party signing: we'd need to produce verifiable "signing instructions" that every co-signer can check before computing their part of the signature. It's not clear yet how that should be structured - this remains to be designed.
Checklist
aggregate(n-of-n) + constant
for predicate tree usage when n-of-n is inside the leftL
branch of a disjunction and theconstant
is an adjustment factorhash(L,R)
. #234signtx
mitigating the Russel's attack. #176signtx
: #146.signtx
: #146.FAQ
What's the role of Merlin transcripts?
MuSig can be specified more cleanly with transcripts rather than with nested hash constructions: e.g. instead of making a delinearization factor as
H(my key, H(all keys))
you'd just commit all pubkeys into a transcript, then squeeze all factors one by one from it. Also, no need to specify message hashing and padding - just have the user prepare the signature transcript however they please and then do the schnorr proof with it w/o worrying about the message.How do we do 2-of-3 and other thresholds?
Via predicate tree: happy path would be the most-expected 2-of-2 (Alice+Bob), while other combinations (Alice+Carol, Bob+Carol) tucked into deeper branches. This does not scale well to large number of participants, but works fine for typically small sizes.
Why not a threshold scheme?
Threshold signatures (m-of-n, m ≤ n) use a very similar cryptographic construction outlined in MuSig paper, yet have two important practical differences:
We'd eventually need threshold scheme too, especially for large thresholds or for cases where accountability is not necessary and we only need redundancy.
References