[bitcoin-dev] Schnorr signatures BIP

[bitcoin-dev] Schnorr signatures BIP

[Pieter Wuille]

Hello everyone,

Here is a proposed BIP for 64-byte elliptic curve Schnorr signatures,
over the same curve as is currently used in ECDSA:
https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki

It is simply a draft specification of the signature scheme itself. It
does not concern consensus rules, aggregation, or any other
integration into Bitcoin - those things are left for other proposals,
which can refer to this scheme if desirable. Standardizing the
signature scheme is a first step towards that, and as it may be useful
in other contexts to have a common Schnorr scheme available, it is its
own informational BIP.

If accepted, we'll work on more production-ready reference
implementations and tests.

This is joint work with several people listed in the document.

Cheers,

-- 
Pieter

Re: [bitcoin-dev] Schnorr signatures BIP

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 3332 bytes --]

Some quick comments:

Signing
>
> To sign:
>
>    - Let *k = int(hash(bytes(d) || m)) mod n*[8
>    <https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki#cite_note-8>
>    ].
>    - Let *R = kG*.
>    - If *jacobi(y(R)) ≠ 1*, let *k = n - k*.
>    - Let *e = int(hash(bytes(x(R)) || bytes(dG) || m)) mod n*.
>    - The signature is *bytes(x(R)) || bytes(k + ex mod n)*.
>
> Can we avoid mutable variables in these specification?  I know this is
commonly done in RFCs, but I think it is fairly confusing to have `k`
defined in two different ways within a single specification.
Let's let k' = k when jacobi(y(R)) = 1 and let k' = n - k when jacobi(y(R))
= -1.  Note that this ensures that jacobi(y(k'G)) = 1.

Also you've sort of left it undefined what to do when k = 0.  According to
the current specification, you will produce an invalid signature.  The
expected result is that you should win a 1000 BTC prize.

One solution is to let k = *1 + int(hash(bytes(d) || m)) mod (n-1)*.
Alternatively you could let k' = 1 when k = 0.  Or you could just make a
note that signature generation fails with this message and private key pair
when this happens.

Let *e = int(hash(bytes(x(R)) || bytes(dG) || m)) mod n*.
>

P = dG should probably be noted somewhere in the text.  I.e. this signature
is generated for the public key P = dG.

If the inputs to hash were reordered as *hash(bytes(dG) || bytes(x(R)) ||
m)* then there is an opportunity for SHA256 expander to be partially
prefilled for a fixed public key.  This could provide a little benefit,
especially when multiple signatures for a single public key need to be
generated and/or verified.  If all things are otherwise equal, perhaps this
alternate order is better.

 The signature is *bytes(x(R)) || bytes(k + ex mod n)*.


You haven't defined `x`.  I'm guessing you mean `d` instead.

> Optimizations
>
> *Jacobian coordinates*
>
>    - *oncurve(P)* can be implemented as *y2 = x3 + 7z6 mod p*.
>
> oncurve(P) requires that `P` be on the curve and not infinity.  You need
another condition here to ensure that `P` is not infinity.


On Fri, Jul 6, 2018 at 2:08 PM, Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello everyone,
>
> Here is a proposed BIP for 64-byte elliptic curve Schnorr signatures,
> over the same curve as is currently used in ECDSA:
> https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
>
> It is simply a draft specification of the signature scheme itself. It
> does not concern consensus rules, aggregation, or any other
> integration into Bitcoin - those things are left for other proposals,
> which can refer to this scheme if desirable. Standardizing the
> signature scheme is a first step towards that, and as it may be useful
> in other contexts to have a common Schnorr scheme available, it is its
> own informational BIP.
>
> If accepted, we'll work on more production-ready reference
> implementations and tests.
>
> This is joint work with several people listed in the document.
>
> Cheers,
>
> --
> Pieter
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 4986 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Gregory Maxwell]

On Fri, Jul 6, 2018 at 9:05 PM, Russell O'Connor via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> If the inputs to hash were reordered as hash(bytes(dG) || bytes(x(R)) || m)
> then there is an opportunity for SHA256 expander to be partially prefilled
> for a fixed public key.  This could provide a little benefit, especially
> when multiple signatures for a single public key need to be generated and/or
> verified.  If all things are otherwise equal, perhaps this alternate order
> is better.

There is a minor design preference to have message before nonce when
H() is a MD-style hash function.  Say the attacker knows some weakness
in H and can find pairs of messages m and m' so that the compression
function results in the same midstate.  He could then ask you to sign
m but get a signature that also works for m'.   If the signer
controlled R value comes first, then this doesn't work.    The pubkey
being where it is in the current design just follows from the idea
that it is just logically prepended on the message.  I don't think the
pubkey is sufficiently attacker controlled that the above argument
would apply,  so H(P || R.x || m) would be okay.

BUT, the sha256 compression function reads 64 bytes at a time. PRM
would not let you precompute a whole compression function run, but
instead would just let you hardwire part of the expander in a pubkey
dependant way-- an optimization I'm pretty confident virtually no one
would use.  (Hardwiring to a constant, yes. Hardwiring to a reused
dynamic value that comes in from the network, no)

If instead the hash function were defined as using 31 zeros then
P||R||m (or P || 31 zeros bytes || R || m, I'm not sure what would be
better), an entire midstate could be cached for different pubkeys. m
is often 32 bytes, sadly- - but the final compression run in that case
would only be the constant update with the length.... and
almost-all-zeros + constant length, is an easy optimization. (Bitcoin
core even has it for computing sha256(sha256())).

[I'm not really sure if I was clear, so I'll try TLDRing it:  I think
optimizing sha256 where part of the input is constant is realistic,
optimizing midstate reuse is realistic, optimizing where part is
reused is less realistic.  If we insert padding, and put P first, we
can make it possible to midstate cache P,  and the 'extra' compression
function run ends up with all constant input, so it could be made
faster.]

Re: [bitcoin-dev] Schnorr signatures BIP

[Gregory Maxwell]

On Fri, Jul 6, 2018 at 10:00 PM, Gregory Maxwell <greg@xiph.org> wrote:
> There is a minor design preference to have message before nonce when

::sigh:: to NOT have the message before the nonce.

Re: [bitcoin-dev] Schnorr signatures BIP

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 3707 bytes --]

On Fri, Jul 6, 2018 at 6:00 PM, Gregory Maxwell <greg@xiph.org> wrote:

> On Fri, Jul 6, 2018 at 9:05 PM, Russell O'Connor via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > If the inputs to hash were reordered as hash(bytes(dG) || bytes(x(R)) ||
> m)
> > then there is an opportunity for SHA256 expander to be partially
> prefilled
> > for a fixed public key.  This could provide a little benefit, especially
> > when multiple signatures for a single public key need to be generated
> and/or
> > verified.  If all things are otherwise equal, perhaps this alternate
> order
> > is better.
>
> There is a minor design preference to have message before nonce when
> H() is a MD-style hash function.  Say the attacker knows some weakness
> in H and can find pairs of messages m and m' so that the compression
> function results in the same midstate.  He could then ask you to sign
> m but get a signature that also works for m'.   If the signer
> controlled R value comes first, then this doesn't work.    The pubkey
> being where it is in the current design just follows from the idea
> that it is just logically prepended on the message.  I don't think the
> pubkey is sufficiently attacker controlled that the above argument
> would apply,  so H(P || R.x || m) would be okay.
>
> BUT, the sha256 compression function reads 64 bytes at a time. PRM
> would not let you precompute a whole compression function run, but
> instead would just let you hardwire part of the expander in a pubkey
> dependant way-- an optimization I'm pretty confident virtually no one
> would use.  (Hardwiring to a constant, yes. Hardwiring to a reused
> dynamic value that comes in from the network, no)
>

Right.  I readily admit my proposal has extremely marginal efficiency
benefits. However, I didn't realize there is also an extremely marginal
security benefit to placing the nonce in front of everything.  Although
these things are so marginal that it is perhaps a waste of time to even be
considering them, I think I'd judge the extremely marginal security benefit
to exceed the value of the extremely marginal efficiency gain.  It's
probably best to leave the nonce at the beginning after all.


> If instead the hash function were defined as using 31 zeros then
> P||R||m (or P || 31 zeros bytes || R || m, I'm not sure what would be
> better), an entire midstate could be cached for different pubkeys. m
> is often 32 bytes, sadly- - but the final compression run in that case
> would only be the constant update with the length.... and
> almost-all-zeros + constant length, is an easy optimization. (Bitcoin
> core even has it for computing sha256(sha256())).
>

I did consider this, however the 31 bytes of zeros, plus the SHA256 padding
means we would need to compress *three* blocks in general instead of the
current proposal of just two blocks.  This burden seems to exceed the
benefit of maybe sometimes getting a slightly fast
two-blocks-with-lots-of-zeros when public keys are reused. I wouldn't
recommend it.

There is an alternative of just dropping the SHA-256 length padding.  This
would still be secure in this context because the data is of fixed size.
However, I doubt it is worth breaking the API of every SHA-256 library in
existence to enable that.


> [I'm not really sure if I was clear, so I'll try TLDRing it:  I think
> optimizing sha256 where part of the input is constant is realistic,
> optimizing midstate reuse is realistic, optimizing where part is
> reused is less realistic.  If we insert padding, and put P first, we
> can make it possible to midstate cache P,  and the 'extra' compression
> function run ends up with all constant input, so it could be made
> faster.]
>

[-- Attachment #2: Type: text/html, Size: 4672 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Sjors Provoost]

[-- Attachment #1: Type: text/plain, Size: 2030 bytes --]


> Op 6 jul. 2018, om 20:08 heeft Pieter Wuille via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> het volgende geschreven:
> 
> Hello everyone,
> 
> Here is a proposed BIP for 64-byte elliptic curve Schnorr signatures,
> over the same curve as is currently used in ECDSA:
> https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki

The power of simplification at work, thanks Pieter!

Questions:

Regarding verification: why does bytes(P) use compressed key serialization rather than the implicit Y coordinate used for signing? I understand space savings don't matter since these values don't end up on the blockchain. Is it just easier to implement or is it faster?

Regarding rationale for choosing (e,s) vs. (R,s), you say that (e,s) "avoids the difficulty of encoding a point R in the signature". But since e = H(sG - eP || m) also involves converting a point to some byte encoding in order to hash it, how much difficulty is actually avoided? Is that, like for previous question, because you could get away with compressed keys rather than implicit Y coordinates?

Regarding batch verification: "randomly generated independently for each batch of verifications" - by whom? I assume randomly picked by the verifier?

Regarding random number used for signing. The suggested (?) deterministic algorithm to derive secret key ''k'' from the private key ''d''  seems similar to RFC6979. Maybe it's useful to briefly explain the difference, as well as your rationale for not making it mandatory (presumably the same as why RFC6979 isn't mandatory although most (?) wallets use it).

Nits:

* Motivation: "signatures ... These are standardized", but the "standardized" link points to the secp256k1 curve parameters, not to anything signature related afaik
* "message m: an array of 32 bytes", maybe add "typically the sha256 hash of the transaction components commited to by SIGHASH_TYPE”
* I left a few even smaller nits as a PR: https://github.com/sipa/bips/pull/10

Cheers,

Sjors

[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Pieter Wuille]

On Sat, Jul 14, 2018 at 8:42 AM, Sjors Provoost <sjors@sprovoost.nl> wrote:
> Questions:
>
> Regarding verification: why does bytes(P) use compressed key serialization rather than the implicit Y coordinate used for signing? I understand space savings don't matter since these values don't end up on the blockchain. Is it just easier to implement or is it faster?

Following the design decision to use key-prefixed Schnorr, the
signature must commit to the entire public key, including its Y
coordinate.

It would be possible to only permit public keys whose Y coordinates
are even, or quadratic residues (like the signature internally uses
for the R point), but that would mean changing what public keys are
acceptable. Not doing so has significant practical advantages, like
not breaking existing key generation mechanisms (like BIP32 and
derivatives).

So if we're going to serialize the public key into the hash, in full,
the easiest choice seems to be to use the encoding everyone already
uses for public keys.

> Regarding rationale for choosing (e,s) vs. (R,s), you say that (e,s) "avoids the difficulty of encoding a point R in the signature". But since e = H(sG - eP || m) also involves converting a point to some byte encoding in order to hash it, how much difficulty is actually avoided? Is that, like for previous question, because you could get away with compressed keys rather than implicit Y coordinates?

This is mostly a historical argument. When Schnorr is applied to an
integer multiplication group rather than an elliptic curve group,
serializing a group element is many times larger than serializing a
hash. For elliptic curve based Schnorr, there is hardly any benefit
for choosing the (e,s) form over (R,s).

> Regarding batch verification: "randomly generated independently for each batch of verifications" - by whom? I assume randomly picked by the verifier?

Randomly picked by the verifier, yes. The randomization factors are
there so that an attacker cannot choose signatures which cancel out
other invalid signatures within the same batch.

> Regarding random number used for signing. The suggested (?) deterministic algorithm to derive secret key ''k'' from the private key ''d''  seems similar to RFC6979. Maybe it's useful to briefly explain the difference, as well as your rationale for not making it mandatory (presumably the same as why RFC6979 isn't mandatory although most (?) wallets use it).

What would "mandatory" mean? To follow the BIP, signers must sign
using nonces generated deterministically following the provided
method. That's as far as mandatory can go.

However, it is not possible to enforce (by a verifier) than nonces
were generated in a specific way. To do so, the verifier would need to
know the nonce, which implies learning the private key. So the nonce
choosing algorithm cannot be enforced by the verifier. This implies
that it is possible to generate valid (and secure) nonces in a way
that does not follow the BIP.

> * Motivation: "signatures ... These are standardized", but the "standardized" link points to the secp256k1 curve parameters, not to anything signature related afaik

There are two documents on the site linked to. One describes the ECDSA
signing algorithm and serializations, the other specifies the curve
parameter. I could link to both.

> * "message m: an array of 32 bytes", maybe add "typically the sha256 hash of the transaction components commited to by SIGHASH_TYPE”

Ok.

> * I left a few even smaller nits as a PR: https://github.com/sipa/bips/pull/10

Thanks for your comments, will review.

Cheers,

-- 
Pieter

Re: [bitcoin-dev] Schnorr signatures BIP

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 1097 bytes --]

I propose changing the verification equation from "Let *R = sG - eP*" to

    Let *R = sG + eP*

This allows faster verification by avoiding negating a point (or a
coefficient).


If, instead of directly following the literal verification specification,
one is instead reconstructing R from r by finding a y coordinate that is a
quadratic residue, under the existing scheme one would verify


*sG - eP = R*

which is effectively verifying

  0 = *sG - eP* - R  or 0 = R - *sG + eP*

Either way one needs to negate at least one point (or one coefficient)
because of the opposite signs between sG and eP.


Under my proposed revised verification scheme, one would instead verify

  0 = sG + eP + (-R).

While it seems that this requires negating R, it does not.  Rather (-R) can
be directly constructed from r by finding a y coordinate that is *not* a
quadratic residue, which is precisely the same amount of work that
construction R from r was.

In either verification procedure, changing the verification equation to my
proposal removes one negation operation from the cost of doing verification.

[-- Attachment #2: Type: text/html, Size: 1527 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 2720 bytes --]

Over chat it has been pointed out to me that computing the non-quadratic
residue is not the same cost as computing a quadratic residue.  As pointed
out in footnote 7 of the the proposed BIP, c^((p+1)/4) is always a
quadratic residue and must be negated to find the non-quadratic residue.

In light of this, I revise my proposed change to make the verification
equation

R + sG + eP = 0.

(by 0 in the equation above I mean the identity element for the (+)
operation, which is the point at infinity.)

This equation is suitable for batch verification.  This equation is clearly
written as a linear combination that doesn't use negation.  In most
implementations, equality comparison tests are implemented by subtraction
and a comparison with zero. By writing the verification equation this way,
we clearly see that only the comparison with zero test is needed.

For single signature verification the check becomes, compute Q := sG + eP.
Verify that Q isn't the point at infinity and Q.x = r.  Verify that Q.y is
*not* a quadratic residue. (While I was incorrect earlier about the costs
of computing a non-residue, it is the case the *verifying* a value is a
quadratic residue is the same cost as verifying a value is a non-residue.)

Effectively in my first email I was suggesting that the 'e' value in a
signature be negated from the current BIP proposal.  In this revision I am
effectively suggesting that the 's' value in a signature should be the one
that is negated instead.

On Sat, Aug 4, 2018 at 8:22 AM, Russell O'Connor <roconnor@blockstream.io>
wrote:

> I propose changing the verification equation from "Let *R = sG - eP*" to
>
>     Let *R = sG + eP*
>
> This allows faster verification by avoiding negating a point (or a
> coefficient).
>
>
> If, instead of directly following the literal verification specification,
> one is instead reconstructing R from r by finding a y coordinate that is a
> quadratic residue, under the existing scheme one would verify
>
>
> *sG - eP = R*
>
> which is effectively verifying
>
>   0 = *sG - eP* - R  or 0 = R - *sG + eP*
>
> Either way one needs to negate at least one point (or one coefficient)
> because of the opposite signs between sG and eP.
>
>
> Under my proposed revised verification scheme, one would instead verify
>
>   0 = sG + eP + (-R).
>
> While it seems that this requires negating R, it does not.  Rather (-R)
> can be directly constructed from r by finding a y coordinate that is *not*
> a quadratic residue, which is precisely the same amount of work that
> construction R from r was.
>
> In either verification procedure, changing the verification equation to my
> proposal removes one negation operation from the cost of doing verification.
>
>
>

[-- Attachment #2: Type: text/html, Size: 3607 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Anthony Towns]

On Sun, Aug 05, 2018 at 10:33:52AM -0400, Russell O'Connor via bitcoin-dev wrote:
> In light of this, I revise my proposed change to make the verification
> equation
> 
> R + sG + eP = 0.

Isn't the verification equation "R + s(-G) + eP = 0" equally good, then,
since -G is a constant? (ie, at worst it's a matter of optimising the
verifier for -G as well as G)

If not, what's the actual performance impact of having to negate "s"
as part of batch verifying ~10000 signatures? It seems like it should
be trivially small to me? (scalar_negate benchmarks at 0.00359us, while
ecdsa_verify benchmarks at 66us, which I believe then reduces by a factor
of ~3 for batches of 10k schnorr sigs?)

FWIW, I'm a fan of the formulation "s = r + H(R,P,m)p" mostly because
it seems like the simplest possible way of describing the setup, and I'm
all for optimising for people being able to understand what's going on.

Cheers,
aj

Re: [bitcoin-dev] Schnorr signatures BIP

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 509 bytes --]

On Mon, Aug 6, 2018 at 4:39 AM, Anthony Towns <aj@erisian.com.au> wrote:

> On Sun, Aug 05, 2018 at 10:33:52AM -0400, Russell O'Connor via bitcoin-dev
> wrote:
> > In light of this, I revise my proposed change to make the verification
> > equation
> >
> > R + sG + eP = 0.
>
> Isn't the verification equation "R + s(-G) + eP = 0" equally good, then,
> since -G is a constant? (ie, at worst it's a matter of optimising the
> verifier for -G as well as G)
>

Yes you are right.

Thanks, I withdraw my proposal.

[-- Attachment #2: Type: text/html, Size: 1014 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Tim Ruffing]

Is it intentional that the encoding of public (and private) keys is
unspecified? I'd consider at least the encoding of the public key to be
part of the signature scheme, so ideally it should be specified already
in this BIP. On the other hand, there may be good arguments against it,
but I'm not aware of any.

This issue leads to a discrepancy between the specification and the
test vectors because the data fields of test vectors "are given as byte
arrays", including public and secret key. As a consequence, even the
Python reference implementation in the BIP draft doesn't work on test
vectors (in a strict sense).

Best,
Tim


On Fri, 2018-07-06 at 11:08 -0700, Pieter Wuille via bitcoin-dev wrote:
> Hello everyone,
> 
> Here is a proposed BIP for 64-byte elliptic curve Schnorr signatures,
> over the same curve as is currently used in ECDSA:
> https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
> 
> It is simply a draft specification of the signature scheme itself. It
> does not concern consensus rules, aggregation, or any other
> integration into Bitcoin - those things are left for other proposals,
> which can refer to this scheme if desirable. Standardizing the
> signature scheme is a first step towards that, and as it may be
> useful
> in other contexts to have a common Schnorr scheme available, it is
> its
> own informational BIP.
> 
> If accepted, we'll work on more production-ready reference
> implementations and tests.
> 
> This is joint work with several people listed in the document.
> 
> Cheers,
> 

Re: [bitcoin-dev] Schnorr signatures BIP

[Andrew Poelstra]

[-- Attachment #1: Type: text/plain, Size: 2451 bytes --]


I think it's just an oversight. We should specify that we use the standard
encoding from section 2.3 of http://www.secg.org/sec1-v2.pdf except that
we allow only compressed public keys.

Andrew


On Mon, Aug 06, 2018 at 11:12:48PM +0200, Tim Ruffing via bitcoin-dev wrote:
> Is it intentional that the encoding of public (and private) keys is
> unspecified? I'd consider at least the encoding of the public key to be
> part of the signature scheme, so ideally it should be specified already
> in this BIP. On the other hand, there may be good arguments against it,
> but I'm not aware of any.
> 
> This issue leads to a discrepancy between the specification and the
> test vectors because the data fields of test vectors "are given as byte
> arrays", including public and secret key. As a consequence, even the
> Python reference implementation in the BIP draft doesn't work on test
> vectors (in a strict sense).
> 
> Best,
> Tim
> 
> 
> On Fri, 2018-07-06 at 11:08 -0700, Pieter Wuille via bitcoin-dev wrote:
> > Hello everyone,
> > 
> > Here is a proposed BIP for 64-byte elliptic curve Schnorr signatures,
> > over the same curve as is currently used in ECDSA:
> > https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
> > 
> > It is simply a draft specification of the signature scheme itself. It
> > does not concern consensus rules, aggregation, or any other
> > integration into Bitcoin - those things are left for other proposals,
> > which can refer to this scheme if desirable. Standardizing the
> > signature scheme is a first step towards that, and as it may be
> > useful
> > in other contexts to have a common Schnorr scheme available, it is
> > its
> > own informational BIP.
> > 
> > If accepted, we'll work on more production-ready reference
> > implementations and tests.
> > 
> > This is joint work with several people listed in the document.
> > 
> > Cheers,
> > 
> 
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
> 

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

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
       --Joanna Newsom


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 3241 bytes --]

Note:

This spec cannot be used directly with a shamir scheme to produce
single-round threshold multisigs, because shares of point R would need to
be broadcast to share participants in order to produce valid single
signatures.

(R, s) schemes can still be used "online", if share participants publish
the R(share).... but, not sure if it matter much, this choice eliminates
offline multiparty signing in exchange for batch validation.








On Sun, Aug 12, 2018 at 12:47 PM Andrew Poelstra via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
> I think it's just an oversight. We should specify that we use the standard
> encoding from section 2.3 of http://www.secg.org/sec1-v2.pdf except that
> we allow only compressed public keys.
>
> Andrew
>
>
> On Mon, Aug 06, 2018 at 11:12:48PM +0200, Tim Ruffing via bitcoin-dev
> wrote:
> > Is it intentional that the encoding of public (and private) keys is
> > unspecified? I'd consider at least the encoding of the public key to be
> > part of the signature scheme, so ideally it should be specified already
> > in this BIP. On the other hand, there may be good arguments against it,
> > but I'm not aware of any.
> >
> > This issue leads to a discrepancy between the specification and the
> > test vectors because the data fields of test vectors "are given as byte
> > arrays", including public and secret key. As a consequence, even the
> > Python reference implementation in the BIP draft doesn't work on test
> > vectors (in a strict sense).
> >
> > Best,
> > Tim
> >
> >
> > On Fri, 2018-07-06 at 11:08 -0700, Pieter Wuille via bitcoin-dev wrote:
> > > Hello everyone,
> > >
> > > Here is a proposed BIP for 64-byte elliptic curve Schnorr signatures,
> > > over the same curve as is currently used in ECDSA:
> > > https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
> > >
> > > It is simply a draft specification of the signature scheme itself. It
> > > does not concern consensus rules, aggregation, or any other
> > > integration into Bitcoin - those things are left for other proposals,
> > > which can refer to this scheme if desirable. Standardizing the
> > > signature scheme is a first step towards that, and as it may be
> > > useful
> > > in other contexts to have a common Schnorr scheme available, it is
> > > its
> > > own informational BIP.
> > >
> > > If accepted, we'll work on more production-ready reference
> > > implementations and tests.
> > >
> > > This is joint work with several people listed in the document.
> > >
> > > Cheers,
> > >
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> >
>
> --
> Andrew Poelstra
> Mathematics Department, Blockstream
> Email: apoelstra at wpsoftware.net
> Web:   https://www.wpsoftware.net/andrew
>
> "A goose alone, I suppose, can know the loneliness of geese
>  who can never find their peace,
>  whether north or south or west or east"
>        --Joanna Newsom
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 4889 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Andrew Poelstra]

[-- Attachment #1: Type: text/plain, Size: 953 bytes --]

On Wed, Aug 29, 2018 at 08:09:36AM -0400, Erik Aronesty wrote:
> Note:
> 
> This spec cannot be used directly with a shamir scheme to produce
> single-round threshold multisigs, because shares of point R would need to
> be broadcast to share participants in order to produce valid single
> signatures.
> 
> (R, s) schemes can still be used "online", if share participants publish
> the R(share).... but, not sure if it matter much, this choice eliminates
> offline multiparty signing in exchange for batch validation.
>

Please stop with this FUD. No tradeoff was made. There are no non-interactive
Schnorr signatures.


Andrew
 

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

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
       --Joanna Newsom


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 1606 bytes --]

Why would you call it FUD?   All the weird hemming and hawing about it is
really strange to me.  The more I look into it and speak to professors
about i, the more it seems "so trivial nobody really talks about it".

1. Generate an M of N shared public key (done in advance of signing ....
this gets you the bitcoin address)
2. Generate signature fragments (this can be done offline, with no
communication between participants)

Detailed explanation with code snippets:

https://medium.com/@simulx/an-m-of-n-bitcoin-multisig-scheme-e7860ab34e7f



On Sun, Sep 2, 2018 at 8:05 PM Andrew Poelstra <apoelstra@wpsoftware.net>
wrote:

> On Wed, Aug 29, 2018 at 08:09:36AM -0400, Erik Aronesty wrote:
> > Note:
> >
> > This spec cannot be used directly with a shamir scheme to produce
> > single-round threshold multisigs, because shares of point R would need to
> > be broadcast to share participants in order to produce valid single
> > signatures.
> >
> > (R, s) schemes can still be used "online", if share participants publish
> > the R(share).... but, not sure if it matter much, this choice eliminates
> > offline multiparty signing in exchange for batch validation.
> >
>
> Please stop with this FUD. No tradeoff was made. There are no
> non-interactive
> Schnorr signatures.
>
>
> Andrew
>
>
> --
> Andrew Poelstra
> Mathematics Department, Blockstream
> Email: apoelstra at wpsoftware.net
> Web:   https://www.wpsoftware.net/andrew
>
> "A goose alone, I suppose, can know the loneliness of geese
>  who can never find their peace,
>  whether north or south or west or east"
>        --Joanna Newsom
>
>

[-- Attachment #2: Type: text/html, Size: 2462 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Andrew Poelstra]

[-- Attachment #1: Type: text/plain, Size: 2231 bytes --]

On Wed, Sep 05, 2018 at 08:26:14AM -0400, Erik Aronesty wrote:
> Why would you call it FUD?   All the weird hemming and hawing about it is
> really strange to me.  The more I look into it and speak to professors
> about i, the more it seems "so trivial nobody really talks about it".
> 
> 1. Generate an M of N shared public key (done in advance of signing ....
> this gets you the bitcoin address)
> 2. Generate signature fragments (this can be done offline, with no
> communication between participants)
> 
> Detailed explanation with code snippets:
> 
> https://medium.com/@simulx/an-m-of-n-bitcoin-multisig-scheme-e7860ab34e7f
>

The hemming and hawing is because you've been repeatedly told that your
scheme doesn't work, and to please implement it in some computer algebra
system so that you can see that (or so we can see where your mistake is),
and you instead continue to post incomplete/incoherent copies of the same
thing across multiple mediums - Reddit, this list, Bitcointalk, Medium,
etc ad nauseum.

It's distracting and offensive to people who have spent a lot of time and
energy thinking about this stuff, and more importantly it causes confusion
in the public eye. Phrasings like "weird hemming and hawing" suggest that
we don't know/don't care about some insight you have, which is not true.
This is why your posts are FUD.

For example, in your linked post I looked at every single instance of the
character 'k' and *not one of them* defined the value 'k' from which 'R'
is derived in the signing procedure.


Of course there is no possible value, individual signers cannot learn 'R'
at signing time without interaction, and your whole scheme is broken. Given
the number of times you've been told this, I find it hard to believe that
this was an honest mistake.



Andrew



-- 
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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 2559 bytes --]

Correct, there is an interaction step to deduce G*k, when signing, each
participant has to publishes G*ki. I didn't talk about it.   That doesn't
break it, but you're correct, it's not non-interactive.

On Wed, Sep 5, 2018 at 9:06 AM Andrew Poelstra <apoelstra@wpsoftware.net>
wrote:

> On Wed, Sep 05, 2018 at 08:26:14AM -0400, Erik Aronesty wrote:
> > Why would you call it FUD?   All the weird hemming and hawing about it is
> > really strange to me.  The more I look into it and speak to professors
> > about i, the more it seems "so trivial nobody really talks about it".
> >
> > 1. Generate an M of N shared public key (done in advance of signing ....
> > this gets you the bitcoin address)
> > 2. Generate signature fragments (this can be done offline, with no
> > communication between participants)
> >
> > Detailed explanation with code snippets:
> >
> >
> https://medium.com/@simulx/an-m-of-n-bitcoin-multisig-scheme-e7860ab34e7f
> >
>
> The hemming and hawing is because you've been repeatedly told that your
> scheme doesn't work, and to please implement it in some computer algebra
> system so that you can see that (or so we can see where your mistake is),
> and you instead continue to post incomplete/incoherent copies of the same
> thing across multiple mediums - Reddit, this list, Bitcointalk, Medium,
> etc ad nauseum.
>
> It's distracting and offensive to people who have spent a lot of time and
> energy thinking about this stuff, and more importantly it causes confusion
> in the public eye. Phrasings like "weird hemming and hawing" suggest that
> we don't know/don't care about some insight you have, which is not true.
> This is why your posts are FUD.
>
> For example, in your linked post I looked at every single instance of the
> character 'k' and *not one of them* defined the value 'k' from which 'R'
> is derived in the signing procedure.
>
>
> Of course there is no possible value, individual signers cannot learn 'R'
> at signing time without interaction, and your whole scheme is broken. Given
> the number of times you've been told this, I find it hard to believe that
> this was an honest mistake.
>
>
>
> Andrew
>
>
>
> --
> 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
>
>

[-- Attachment #2: Type: text/html, Size: 3437 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Gregory Maxwell]

On Wed, Sep 5, 2018 at 1:49 PM Erik Aronesty via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> Detailed explanation with code snippets:
>
> https://medium.com/@simulx/an-m-of-n-bitcoin-multisig-scheme-[snip]

This appears to be a repost of the broken scheme you posted about on
Bitcointalk, but then failed to respond to the response.

https://bitcointalk.org/index.php?topic=4973123.0

> The more I look into it and speak to professors about i, the more it seems "so trivial nobody really talks about it".

I think you might be falling into the trap of ignoring feedback you
don't like and and accepting that which sounds like "yea yea,
something like that".

Something "like that" does work: and is expressly and explicitly
anticipated by the BIP but to be both secure and functional requires
proper delineation (E.g. musig) _and_ interaction. What you're
proposing is continually vague.  My best efforts at making sense of
what you've written indicate that either it's non-interactive and
not-actually functional at all,  OR it's interactive and just a less
secure subset (no proper delinearization to prevent rogue key attacks)
of what we already propose.

When Poelstra suggests a CAS implementation he means something like
this Sage notebook: http://bitcoin.ninja/secp256k1.ecdsa.sage  This
provides for a method of communicating in both directions which is
completely precise.

Re: [bitcoin-dev] Schnorr signatures BIP

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 2731 bytes --]

 To answer points:

- I switched to the medium article so that I could correct, edit and
improve things to make them more clear.
- I responded to feedback by modifying the protocol to make it work - not
by ignoring it.
- I coded it up in python so I could be sure it worked, because I was
concerned that it was broken
- Yes, coding it up showed me that it's definitely interactive, and no
different than a "standard shnorr sig" in any meaningful way regarding the
security
- No special protocol support is needed over Schnorr signing itself.  The
e, s version can be made at least as secure as schnorr + DLP.  I haven't
researched the R,s version.
- An M-1 rogue-key attack would require the attacker would to either

  - attack the hash function to produce a predictable R based on a known
mesage
  - attack the DLP to influence x or k

Neither attack gives any particular advantage to someone who has M-1 keys.

I haven't tested whether the R,s version is susceptible though.


On Thu, Sep 6, 2018 at 9:15 AM Gregory Maxwell via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Wed, Sep 5, 2018 at 1:49 PM Erik Aronesty via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > Detailed explanation with code snippets:
> >
> > https://medium.com/@simulx/an-m-of-n-bitcoin-multisig-scheme-[snip]
>
> This appears to be a repost of the broken scheme you posted about on
> Bitcointalk, but then failed to respond to the response.
>
> https://bitcointalk.org/index.php?topic=4973123.0
>
> > The more I look into it and speak to professors about i, the more it
> seems "so trivial nobody really talks about it".
>
> I think you might be falling into the trap of ignoring feedback you
> don't like and and accepting that which sounds like "yea yea,
> something like that".
>
> Something "like that" does work: and is expressly and explicitly
> anticipated by the BIP but to be both secure and functional requires
> proper delineation (E.g. musig) _and_ interaction. What you're
> proposing is continually vague.  My best efforts at making sense of
> what you've written indicate that either it's non-interactive and
> not-actually functional at all,  OR it's interactive and just a less
> secure subset (no proper delinearization to prevent rogue key attacks)
> of what we already propose.
>
> When Poelstra suggests a CAS implementation he means something like
> this Sage notebook: http://bitcoin.ninja/secp256k1.ecdsa.sage  This
> provides for a method of communicating in both directions which is
> completely precise.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 4183 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Gregory Maxwell]

[-- Attachment #1: Type: text/plain, Size: 2342 bytes --]

On Tue, Sep 11, 2018 at 4:34 PM Erik Aronesty <erik@q32.com> wrote:

> To answer points:
>
> - I switched to the medium article so that I could correct, edit and
> improve things to make them more clear.
> - I responded to feedback by modifying the protocol to make it work - not
> by ignoring it.
>

To this moment there remains no response at your post.
https://bitcointalk.org/index.php?topic=4973123.0

I'm not sure how I am supposted to have figured out that you wrote a
somewhat different repost of it elsewhere...

- An M-1 rogue-key attack would require the attacker would to either
>
>   - attack the hash function to produce a predictable R based on a known
> mesage
>   - attack the DLP to influence x or k
>
> Neither attack gives any particular advantage to someone who has M-1 keys.
>

You keep asserting this. It isn't true. Asserting it more does not make it
any more true.  I already explained how to attack this style of signature
(e.g. in the BCT thread).

Set aside your 'interpolation' for a moment, and imagine that you construct
a 2 of 2 signature by just adding the keys.  Your tell me your key, P1  and
then I tell you that my key P2 which I derived by computing -P1  + xG.   We
now compute P = P1 + P2 = P1 + -P1 + xG = xG ... and now in spite adding P1
with an unknown discrete log, I know the discrete log of P with respect to
G and I did not need to violate the standard DL security assumption to
achieve that.

With the 'interpolation' in effect the same attack applies but its
execution is somewhat more complex: instead of adding the negation of P1  I
must add a number of multiplicities of P1 (like P1*2, P1*3, P1*4...)
selected so that their interpolation coefficients add up to -1. Finding a
suitable subset requires solving a randomized modular subset sum problem
and Wagner's algorithm provides a computationally tractable solution to it.

The potential of rogue keys applies to both the keys themselves and to the
nonces. There are several ways to prevent these attacks, the musig paper
describes a delinearization technique which doesn't require additional
interaction or communication.

I haven't tested whether the R,s version is susceptible though.
>

There is a perfect bijection between the two encodings which is easily
computable, so they're the same thing from an abstract security perspective.

[-- Attachment #2: Type: text/html, Size: 3393 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 2986 bytes --]

Greg,

I added, stripped out, and added analogous musig delinearization 3 times in
response to stuff posted here.  I'm adding it back now. Not sure why my
head is thick around that issue.

The security advantages of a redistributable threshold system are huge.
If a system isn't redistributable, then a single lost or compromised key
results in lost coins... meaning the system is essetntially unusable.

I'm actually worried that Bitcoin releases a multisig that encourages loss.




On Tue, Sep 11, 2018 at 1:00 PM Gregory Maxwell <greg@xiph.org> wrote:

> On Tue, Sep 11, 2018 at 4:34 PM Erik Aronesty <erik@q32.com> wrote:
>
>> To answer points:
>>
>> - I switched to the medium article so that I could correct, edit and
>> improve things to make them more clear.
>> - I responded to feedback by modifying the protocol to make it work - not
>> by ignoring it.
>>
>
> To this moment there remains no response at your post.
> https://bitcointalk.org/index.php?topic=4973123.0
>
> I'm not sure how I am supposted to have figured out that you wrote a
> somewhat different repost of it elsewhere...
>
> - An M-1 rogue-key attack would require the attacker would to either
>>
>>   - attack the hash function to produce a predictable R based on a known
>> mesage
>>   - attack the DLP to influence x or k
>>
>> Neither attack gives any particular advantage to someone who has M-1 keys.
>>
>
> You keep asserting this. It isn't true. Asserting it more does not make it
> any more true.  I already explained how to attack this style of signature
> (e.g. in the BCT thread).
>
> Set aside your 'interpolation' for a moment, and imagine that you
> construct a 2 of 2 signature by just adding the keys.  Your tell me your
> key, P1  and then I tell you that my key P2 which I derived by computing
> -P1  + xG.   We now compute P = P1 + P2 = P1 + -P1 + xG = xG ... and now in
> spite adding P1 with an unknown discrete log, I know the discrete log of P
> with respect to G and I did not need to violate the standard DL security
> assumption to achieve that.
>
> With the 'interpolation' in effect the same attack applies but its
> execution is somewhat more complex: instead of adding the negation of P1  I
> must add a number of multiplicities of P1 (like P1*2, P1*3, P1*4...)
> selected so that their interpolation coefficients add up to -1. Finding a
> suitable subset requires solving a randomized modular subset sum problem
> and Wagner's algorithm provides a computationally tractable solution to it.
>
> The potential of rogue keys applies to both the keys themselves and to the
> nonces. There are several ways to prevent these attacks, the musig paper
> describes a delinearization technique which doesn't require additional
> interaction or communication.
>
> I haven't tested whether the R,s version is susceptible though.
>>
>
> There is a perfect bijection between the two encodings which is easily
> computable, so they're the same thing from an abstract security perspective.
>
>

[-- Attachment #2: Type: text/html, Size: 4383 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Gregory Maxwell]

On Tue, Sep 11, 2018 at 5:20 PM Erik Aronesty <erik@q32.com> wrote:
> The security advantages of a redistributable threshold system are huge.   If a system isn't redistributable, then a single lost or compromised key results in lost coins... meaning the system is essetntially unusable.
>
> I'm actually worried that Bitcoin releases a multisig that encourages loss.

There is no "non- edistributiable multisig" proposed for Bitcoin
anywhere that I am aware of.

Re: [bitcoin-dev] Schnorr signatures BIP

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 894 bytes --]

- Musig, by being M of M, is inherently prone to loss.

- Having the senders of the G*x pubkey shares sign their messages with the
associated private key share should be sufficient to prevent them from
using wagner's algorithm to attack the combined key.   Likewise, the G*k
nonce fragments should also be signed with the pubkey shares.



On Tue, Sep 11, 2018 at 1:27 PM Gregory Maxwell <greg@xiph.org> wrote:

> On Tue, Sep 11, 2018 at 5:20 PM Erik Aronesty <erik@q32.com> wrote:
> > The security advantages of a redistributable threshold system are huge.
>  If a system isn't redistributable, then a single lost or compromised key
> results in lost coins... meaning the system is essetntially unusable.
> >
> > I'm actually worried that Bitcoin releases a multisig that encourages
> loss.
>
> There is no "non- edistributiable multisig" proposed for Bitcoin
> anywhere that I am aware of.
>

[-- Attachment #2: Type: text/html, Size: 1307 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Gregory Maxwell]

On Tue, Sep 11, 2018 at 5:38 PM Erik Aronesty <erik@q32.com> wrote:
>
> - Musig, by being M of M, is inherently prone to loss.

M of M is a particular threshold.   If you want M of M (there are
plenty of cases where M of M _must_ be used) then you get the
consequences of M of M, which presumably you want.

This has nothing to do with musig.  If you want a threshold other than
M of M then you use a threshold other than M of M.

No one is under the impression that M of M is somehow a replacement
for other thresholds.  We've spent more time talking about M of M in
some writeups in the past because it's exactly the case you need for
signature aggregation in Bitcoin and because it's a simpler case to
explain.

> - Having the senders of the G*x pubkey shares sign their messages with the associated private key share should be sufficient to prevent them from using wagner's algorithm to attack the combined key.

Yes, that is one possibility which is described in the musig paper,
but it requires users communicate an extra signature per key.  So, for
example, if used with aggregate signature it would completely
eliminate the communications efficiency gains from aggregation, making
aggregation worse than pointless.  It also has somewhat worse failure
properties than delinearization, because a signer that fails to
validate other's share signatures behaves behaves exactly the same as
a correct one, on honest inputs.  That approach has its uses but I
think that in any case where delinearization can be used it's a better
option.

Re: [bitcoin-dev] Schnorr signatures BIP

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 2212 bytes --]

>  That approach has its uses but I think that in any case where
delinearization can be used it's a better option.

I agree, communication efficiency is a concern for some applications, and I
can think of cases where delinearization is the better option as well.

For users that want an "M of N" scheme that

a) doesn't cost more to send funds
b) allows them to lose a device and keep their coins
c) allows them to establish and validate the scheme safely

...  a simple, "verified signer" threshold scheme is probably the best
solution.




On Tue, Sep 11, 2018 at 1:51 PM Gregory Maxwell <greg@xiph.org> wrote:

> On Tue, Sep 11, 2018 at 5:38 PM Erik Aronesty <erik@q32.com> wrote:
> >
> > - Musig, by being M of M, is inherently prone to loss.
>
> M of M is a particular threshold.   If you want M of M (there are
> plenty of cases where M of M _must_ be used) then you get the
> consequences of M of M, which presumably you want.
>
> This has nothing to do with musig.  If you want a threshold other than
> M of M then you use a threshold other than M of M.
>
> No one is under the impression that M of M is somehow a replacement
> for other thresholds.  We've spent more time talking about M of M in
> some writeups in the past because it's exactly the case you need for
> signature aggregation in Bitcoin and because it's a simpler case to
> explain.
>
> > - Having the senders of the G*x pubkey shares sign their messages with
> the associated private key share should be sufficient to prevent them from
> using wagner's algorithm to attack the combined key.
>
> Yes, that is one possibility which is described in the musig paper,
> but it requires users communicate an extra signature per key.  So, for
> example, if used with aggregate signature it would completely
> eliminate the communications efficiency gains from aggregation, making
> aggregation worse than pointless.  It also has somewhat worse failure
> properties than delinearization, because a signer that fails to
> validate other's share signatures behaves behaves exactly the same as
> a correct one, on honest inputs.  That approach has its uses but I
> think that in any case where delinearization can be used it's a better
> option.
>

[-- Attachment #2: Type: text/html, Size: 2879 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Andrew Poelstra]

[-- Attachment #1: Type: text/plain, Size: 793 bytes --]

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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 1409 bytes --]

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 <apoelstra@wpsoftware.net>
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
>
>

[-- Attachment #2: Type: text/html, Size: 2185 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Andrew Poelstra]

[-- Attachment #1: Type: text/plain, Size: 2909 bytes --]

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 <apoelstra@wpsoftware.net>
> 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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 1238 bytes --]

It would be helpful to add the intermediate 'e' values computed to the
first four test vectors.

On Fri, Jul 6, 2018 at 2:08 PM, Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello everyone,
>
> Here is a proposed BIP for 64-byte elliptic curve Schnorr signatures,
> over the same curve as is currently used in ECDSA:
> https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
>
> It is simply a draft specification of the signature scheme itself. It
> does not concern consensus rules, aggregation, or any other
> integration into Bitcoin - those things are left for other proposals,
> which can refer to this scheme if desirable. Standardizing the
> signature scheme is a first step towards that, and as it may be useful
> in other contexts to have a common Schnorr scheme available, it is its
> own informational BIP.
>
> If accepted, we'll work on more production-ready reference
> implementations and tests.
>
> This is joint work with several people listed in the document.
>
> Cheers,
>
> --
> Pieter
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 2033 bytes --]

Re: [bitcoin-dev] Schnorr signatures BIP

[Артём Литвинович]

[-- Attachment #1: Type: text/plain, Size: 919 bytes --]

Neat.

Some minor notes as an outsider who just spent an hour implementing and
playing with this:

-In several places you have things like "Let k = int(hash(bytes(d) || m))
mod n", but reference code says things like "e = sha256(R[0].to_bytes(32,
byteorder="big") + bytes_point(point_mul(G, seckey)) + msg)", no modulo.
Confusing.

-x is not defined in "The signature is *bytes(x(R)) || bytes(k + ex mod n)*",
apparently it's the private key.

-jacobi function is great at exposing bugs in divmod implementations, due
to the full 256 bit exponent. Add a line about it being something to watch
for?

-"bytes" notation is defined as "turn to bytes" for an integer, but the
same for a point is "take X with prefix and turn to bytes". Confusing,
might be a good idea to name it differently?

-Finally, it would have been nice to have a larger set of test vectors in a
JSON or CSV file, covering all the edge cases.


Artem

[-- Attachment #2: Type: text/html, Size: 1229 bytes --]