Re: [bitcoin-dev] Schnorr signatures BIP

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,

Re: [bitcoin-dev] Schnorr signatures BIP

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

Re: [bitcoin-dev] Schnorr signatures BIP

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

Re: [bitcoin-dev] Schnorr signatures BIP

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

Re: [bitcoin-dev] Schnorr signatures BIP

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

Re: [bitcoin-dev] Schnorr signatures BIP

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

Re: [bitcoin-dev] Schnorr signatures BIP

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

Re: [bitcoin-dev] Schnorr signatures BIP

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

Re: [bitcoin-dev] Schnorr signatures BIP

On Tue, Sep 11, 2018 at 5:38 PM Erik Aronesty 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

Re: [bitcoin-dev] Schnorr signatures BIP

On Tue, Sep 11, 2018 at 5:20 PM Erik Aronesty 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 wor

Re: [bitcoin-dev] Schnorr signatures BIP

On Tue, Sep 11, 2018 at 4:34 PM Erik Aronesty 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 mome

Re: [bitcoin-dev] Schnorr signatures BIP

On Wed, Sep 5, 2018 at 1:49 PM Erik Aronesty via bitcoin-dev 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 th

Re: [bitcoin-dev] Schnorr signatures BIP

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 wrote: > On Wed, Sep 05, 2018 at 08:26:14AM -04

Re: [bitcoin-dev] Schnorr signatures BIP

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

Re: [bitcoin-dev] Schnorr signatures BIP

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

Re: [bitcoin-dev] Schnorr signatures BIP

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

Re: [bitcoin-dev] Schnorr signatures BIP

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 publis

Re: [bitcoin-dev] Schnorr signatures BIP

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

Re: [bitcoin-dev] Schnorr signatures BIP

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 awa

Re: [bitcoin-dev] Schnorr signatures BIP

On Mon, Aug 6, 2018 at 4:39 AM, Anthony Towns 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

Re: [bitcoin-dev] Schnorr signatures BIP

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 wors

Re: [bitcoin-dev] Schnorr signatures BIP

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 o

Re: [bitcoin-dev] Schnorr signatures BIP

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 fin

Re: [bitcoin-dev] Schnorr signatures BIP

On Sat, Jul 14, 2018 at 8:42 AM, Sjors Provoost 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

Re: [bitcoin-dev] Schnorr signatures BIP

> Op 6 jul. 2018, om 20:08 heeft Pieter Wuille via bitcoin-dev > 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-schno

Re: [bitcoin-dev] Schnorr signatures BIP

On Fri, Jul 6, 2018 at 6:00 PM, Gregory Maxwell wrote: > On Fri, Jul 6, 2018 at 9:05 PM, Russell O'Connor via bitcoin-dev > 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 >

Re: [bitcoin-dev] Schnorr signatures BIP

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

Re: [bitcoin-dev] Schnorr signatures BIP

On Fri, Jul 6, 2018 at 10:00 PM, Gregory Maxwell wrote: > There is a minor design preference to have message before nonce when ::sigh:: to NOT have the message before the nonce. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://

Re: [bitcoin-dev] Schnorr signatures BIP

On Fri, Jul 6, 2018 at 9:05 PM, Russell O'Connor via bitcoin-dev 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, especia

Re: [bitcoin-dev] Schnorr signatures BIP

Some quick comments: Signing > > To sign: > >- Let *k = int(hash(bytes(d) || m)) mod n*[8 > > >]. >- Let *R = kG*. >- If *jacobi(y(R)) ≠ 1*, let *k = n - k*. >- Let *e = int(hash(bytes(x(R)) |

[bitcoin-dev] Schnorr signatures BIP

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 conse