Schnorr signatures BIP
31 messages, 6 Jul to 20 Sep 2018. Started by Pieter Wuille.
Erik Aronesty (8), Russell O'Connor (6), Gregory Maxwell (6), Andrew Poelstra (5), Pieter Wuille (2), Артём Литвинович, Sjors Provoost, Anthony Towns, +1 more
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,
Some quick comments:
Signing
Quoted text (12 lines)
> > 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*.
Quoted text (1 line)
>
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.
Quoted text (7 lines)
> 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:
Quoted text (28 lines)
> 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 >
On Fri, Jul 6, 2018 at 9:05 PM, Russell O'Connor via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (6 lines)
> 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.]
On Fri, Jul 6, 2018 at 10:00 PM, Gregory Maxwell <greg@xiph•org> wrote:
Quoted text (1 line)
> There is a minor design preference to have message before nonce when
::sigh:: to NOT have the message before the nonce.
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
On Fri, Jul 6, 2018 at 6:00 PM, Gregory Maxwell <greg@xiph•org> wrote:
Quoted text (31 lines)
> 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.
Quoted text (8 lines)
> 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.
Quoted text (8 lines)
> [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.] >
Quoted text (7 lines)
> 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
On Sat, Jul 14, 2018 at 8:42 AM, Sjors Provoost <sjors@sprovoost•nl> wrote:
Quoted text (3 lines)
> 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.
Quoted text (1 line)
> 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).
Quoted text (1 line)
> 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.
Quoted text (1 line)
> 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.
Quoted text (1 line)
> * 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.
Quoted text (1 line)
> * "message m: an array of 32 bytes", maybe add "typically the sha256 hash of the transaction components commited to by SIGHASH_TYPE”
Ok.
Quoted text (1 line)
> * I left a few even smaller nits as a PR: https://github.com/sipa/bips/pull/10
Thanks for your comments, will review.
Cheers,
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.
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:
Quoted text (37 lines)
> 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. > > >
On Sun, Aug 05, 2018 at 10:33:52AM -0400, Russell O'Connor via bitcoin-dev wrote:
Quoted text (4 lines)
> 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
On Mon, Aug 6, 2018 at 4:39 AM, Anthony Towns <aj@erisian•com•au> wrote:
Quoted text (11 lines)
> 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.
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:
Quoted text (23 lines)
> 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, >
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:
Quoted text (47 lines)
> 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 > >
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:
Quoted text (74 lines)
> > 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 >
On Wed, Aug 29, 2018 at 08:09:36AM -0400, Erik Aronesty wrote:
Quoted text (11 lines)
> 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
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:
Quoted text (33 lines)
> 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 > >
On Wed, Sep 05, 2018 at 08:26:14AM -0400, Erik Aronesty wrote:
Quoted text (13 lines)
> 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
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:
Quoted text (58 lines)
> 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 > >
On Wed, Sep 5, 2018 at 1:49 PM Erik Aronesty via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (3 lines)
> 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
Quoted text (1 line)
> 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.
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:
Quoted text (36 lines)
> 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 >
On Tue, Sep 11, 2018 at 4:34 PM Erik Aronesty <erik@q32•com> wrote:
Quoted text (7 lines)
> 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
Quoted text (7 lines)
> > - 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.
Quoted text (1 line)
>
There is a perfect bijection between the two encodings which is easily computable, so they're the same thing from an abstract security perspective.
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:
Quoted text (56 lines)
> 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. > >
On Tue, Sep 11, 2018 at 5:20 PM Erik Aronesty <erik@q32•com> wrote:
Quoted text (3 lines)
> 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.
- 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:
Quoted text (11 lines)
> 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. >
On Tue, Sep 11, 2018 at 5:38 PM Erik Aronesty <erik@q32•com> wrote:
Quoted text (2 lines)
> > - 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.
Quoted text (1 line)
> - 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.
Quoted text (1 line)
> 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:
Quoted text (32 lines)
> 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. >
On Tue, Sep 11, 2018 at 01:37:59PM -0400, Erik Aronesty via bitcoin-dev wrote:
Quoted text (2 lines)
> - 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
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:
Quoted text (26 lines)
> 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 > >
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:
Quoted text (47 lines)
> 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 > > > >
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:
Quoted text (28 lines)
> 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 >