Subject: Re: [bitcoin-dev] Schnorr signatures BIP

From: Andrew Poelstra <[email-masked]>
Date: Fri, 14 Sep 2018 14:38:02 +0000

Hi Erik,

Sorry, you're right - I thought we mentioned m-of-n as a footnote but that was
actually in the earlier pre-MuSig version of our multisig paper.

Threshold signatures -are- mentioned in the BIP which started this thread, though.
At https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki we say

    "Further, by combining Schnorr signatures with Pedersen Secret Sharing,
     it is possible to obtain an interactive threshold signature scheme that
     ensures that signatures can only be produced by arbitrary but predetermined
     sets of signers. For example, k-of-n threshold signatures can be realized
     this way. Furthermore, it is possible to replace the combination of
     participant keys in this scheme with MuSig, though the security of that
     combination still needs analysis. 

and this combination of MuSig and VSS is exactly what is implemented in my code.

Cheers
Andrew

On Thu, Sep 13, 2018 at 04:20:36PM -0400, Erik Aronesty wrote:
> The paper refers to either:
> 
>   a) building up threshold signatures via concatenation, or. implicitly -
> in Bitcoin -
>   b) by indicating that of M of N are valid, and requiring a validator to
> validate one of the permutations of M that signed - as opposed to a scheme,
> like a polynomial function, where the threshold is built in to the system.
> 
> Maybe there's another mechanism in there that I'm not aware of - because
> it's just too simple to mention?
> 
> - Erik
> 
> 
> 
> 
> 
> 
> On Thu, Sep 13, 2018 at 2:46 PM Andrew Poelstra <[email-masked]>
> wrote:
> 
> > On Tue, Sep 11, 2018 at 01:37:59PM -0400, Erik Aronesty via bitcoin-dev
> > wrote:
> > > - Musig, by being M of M, is inherently prone to loss.
> > >
> >
> > It has always been possible to create M-of-N threshold MuSig signatures
> > for any
> > M, N with 0 < M ≤ N. This is (a) obvious, (b) in our paper, (c)
> > implemented at
> >
> >
> > https://github.com/apoelstra/secp256k1/blob/2018-04-taproot/src/modules/musig/main_impl.h
> >
> > --
> > Andrew Poelstra
> > Research Director, Mathematics Department, Blockstream
> > Email: apoelstra at wpsoftware.net
> > Web:   https://www.wpsoftware.net/andrew
> >
> > "Make it stop, my love; we were wrong to try
> >  Never saw what we could unravel in traveling light
> >  Nor how the trip debrides like a stack of slides
> >  All we saw was that time is taller than space is wide"
> >        --Joanna Newsom
> >
> >

-- 
Andrew Poelstra
Research Director, Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"Make it stop, my love; we were wrong to try
 Never saw what we could unravel in traveling light
 Nor how the trip debrides like a stack of slides
 All we saw was that time is taller than space is wide"
       --Joanna Newsom