Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 2D11C4A6 for ; Wed, 10 May 2017 01:59:29 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ua0-f171.google.com (mail-ua0-f171.google.com [209.85.217.171]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id B5C5E141 for ; Wed, 10 May 2017 01:59:27 +0000 (UTC) Received: by mail-ua0-f171.google.com with SMTP id e28so20349244uah.0 for ; Tue, 09 May 2017 18:59:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blockstream-io.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=yLuINV2jTlwm1jRa7r6Y80pkvrLXRwBlO/xF6CSJZic=; b=GGfIp4X1iBZy1Tv0MHpKK3HXBIpfTpPrMI451dhxBmTzH61zRawWJTsrBxOog/t8IK mg/vDFJlGZB3b/+lSjdVBm4jyjg5oKpxNse5y1j7xcamWUOg9fs0WoQ5FuVibOLOMRP9 rXmcSKBbep6hB8MC/cxIlhIMpJy81tJKJTfKf/NdWhgo/fgItHIVl980ZJqD0OmJMI0s p5WyG1DlhFo6Sgb7YwRmd9jpM/V+t3scOmSYEh0eIZHZQOP79esdkSanv0LSERxYeLmI C8q4ak80/lP7wUlpqki1u6L83rpIZUJo6F47zVEWEbq0maPxgm6fNdV6Nq1Egskxi71g WQIg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=yLuINV2jTlwm1jRa7r6Y80pkvrLXRwBlO/xF6CSJZic=; b=Lm7843E+MZbCypjKybWiGDi9roUmr796AeUKc24QLcGTwlp9Mf2ccoGCwirw7kYmn5 qKOcosyHk1orThj9TFTPrSHX3JVF8aGPnJrmU79f71NWVX4OVUTUpjvIRmgA53ZpI68p eSjOR/ef04EZP0U0cJx6299gDL6bed8Y5A+G1gU1L0eLqcy2jqBulwO4LrhKJL2v2JZj VH/iBLQMs1dpm3DvEiQJIMYNd8fBHgzTR5bO49MfFrIckVCgZJ/uiIHK/Q53w07SyPmr yPUHxDRz8z4jXi+pwsOwcyEppZ4N9DaXL/NfQvJQAUWUIuvoG2puoOBDXHmVyTGxMTjG Pewg== X-Gm-Message-State: AODbwcAOOwX1PvGZRETht79jxkDwygY0228TJOrqKBEJUsVPjkQn/K8Q lu0QDpFiI7MSZVj6f+b/8FdpVgGow4SeyCxQ1Q== X-Received: by 10.31.102.131 with SMTP id a125mr1464183vkc.6.1494381566702; Tue, 09 May 2017 18:59:26 -0700 (PDT) MIME-Version: 1.0 Received: by 10.176.81.48 with HTTP; Tue, 9 May 2017 18:59:06 -0700 (PDT) In-Reply-To: References: From: "Russell O'Connor" Date: Tue, 9 May 2017 21:59:06 -0400 Message-ID: To: adiabat Content-Type: multipart/alternative; boundary=001a114df358714ff1054f21d22b X-Spam-Status: No, score=-1.9 required=5.0 tests=AC_DIV_BONANZA,BAYES_00, DKIM_SIGNED,DKIM_VALID,HTML_MESSAGE,RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Per-block non-interactive Schnorr signature aggregation X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 10 May 2017 01:59:29 -0000 --001a114df358714ff1054f21d22b Content-Type: text/plain; charset=UTF-8 I'm a bit amateur at this sort of thing, but let me try to argue that this proposal is in fact horribly broken ;) Suppose Alice has some UTXO with some money Bob wants to steal. Grant me that the public key P0 protecting Alice's UTXO is public (say because the public key has been reused elsewhere). Bob going to spend Alice's UTXO by generating random values s0, k0 and R0 := k0*G and thus creating a random signature for it, [R0, s0]. Now clearly this signature isn't going to be valid by itself because it is just random. Bob's goal will be to make a transaction with other inputs such that, while the individual signatures are not valid, the aggregated signature will be valid. To do this Bob generates a set of random public keys P1 ... P_n of the form P_i := P0 + r_i*G, and a bunch of random k1 ... k_n with R1 := k1*G ... R_n := k_n*G, such that h(m1, R1, P1) + ... + h(m_n, R_n, P_n) = -h(m0, R0 P0) (modulo the order of the elliptic curve) I understand that this can be done efficiently with Wagner's Generalized Birthday attack. The RHS aggregated signature equation on the private side is k0 + k1 + ... k_n - h(m0, R0, P0)x0 - h(m1, R1, P1)(x0 + r1) - ... - h(m_n, R_n, P_n)(x0 + r_n) with x0 unknown to Bob. Rearranging the terms we get k0 + k1 + ... k_n - [h(m0, R0, P0) + h(m1, R1, P1) + ... + h(m_n, R_n, P_n)]*x0 - [h(m1, R1, P1)*r1 + ... + h(m_n, R_n, P_n)*r_n] However [h(m0, R0, P0) + h(m1, R1, P1) + ... + h(m_n, R_n, P_n)] is 0 so cancelling that we are left with k0 + k1 + ... k_n - [h(m1, R1, P1)*r1 + ... + h(m_n, R_n, P_n)*r_n] which no longer depends on the unknown value x0, so that is good. Bob knows what this value is. Bob creates a set UTXOs by spending to the set of public keys P1 .. P_n. Bob don't know what the private keys are for these public keys, but that is going to be okay. Bob creates a final transaction that takes as input the UTXO of Alice's funds he wants to steal, with public key P0, and also his newly created UTXOs with public keys P1 ... P_n. For the signature on Alice's input he uses [R0,s0]. For the rest of the signature he picks s1 ... s_n such that s0 + s1 + ... + sn = k0 + k1 + ... k_n - [h(m1, R1, P1)*r1 + ... + h(m_n, R_n, P_n)*r_n] (which is equal to k0 + k1 + ... k_n - h(m0, R0, P0)x0 - h(m1, R1, P1)(x0 + r1) - ... - h(m_n, R_n, P_n)(x0 + r_n)). and uses signatures [R1, s1] ... [R_n, s_n] on his other inputs. Thus, while none of the individual signatures are valid, the aggregated signature does validate. One wrinkles in this argument is that Bob needs to pick m1 ... m_n before he knows what the transaction will be. I think this can be mitigated by using some combination of SIGHASH_ANYONECANPAY, but I'm not sure if that works. Even if my argument doesn't actually work, I think it is close enough to be pretty scary. Thanks goes to Pieter Wuille for helping explain things to me; however any errors above are my own. On Sun, May 7, 2017 at 2:45 AM, adiabat via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > If / when Schnorr signatures are deployed in a future witness version, it > may be possible to have non-interactive partial aggregation of the > signatures on a per-block basis. This could save quite a bit of space. It > *seems* not to have any security problems but this mailing list is very > good at finding vulnerabilities so that type of feedback is the main reason > I'm writing :) (A quick explanation of why this is horribly broken could > save me lots of time!) > (also sorry if this has been discussed; didn't see anything) > > Quick recap / context of Schnorr sigs: > > There are a bunch of private keys x1, x2, x3... > multiply by generator G to get x1G = P1, x2G = P2, x3G = P3 > > Everyone makes their sighash m1, m2, m3, and their random nonces k1, k2, > k3. > > To sign, people calculate s values: > > s1 = k1 - h(m1, R1, P1)x1 > s2 = k2 - h(m2, R2, P2)x2 > > (adding the P2 into the e hash value is not in most literature / > explanations but helps with some attacks; I beleive that's the current > thinking. Anyway it doesn't matter for this idea) > > Signature 1 is [R1, s1]. Verifiers check, given P1, m1, R1, s1: > > s1G =? R1 - h(m1, R1, P1)P1 > > You can *interactively* make aggregate signatures, which requires > co-signers to build an aggregate R value by coming up with their own k > values, sharing their R with the co-signers, adding up the R's to get a > summed R, and using that to sign. > > Non-interactively though, it seems like you can aggregate half the > signature. The R values are unique to the [m, P] pair, but the s's can be > summed up: > > s1 + s2 = k1 + k2 - h(m1, R1, P1)x1 - h(m2, R2, P2)x2 > > (s1 + s2)G = R1 + R2 - h(m1, R1, P1)P1 - h(m2, R2, P2)P2 > > To use this property in Bitcoin, when making transactions, wallets can > sign in the normal way, and the signature, consisting of [R, s] goes into > the witness stack. When miners generate a block, they remove the s-value > from all compatible inputs, and commit to the aggregate s-value in the > coinbase transaction (either in a new OP_RETURN or alongside the existing > witness commitment structure). > > The obvious advatage is that signatures go down to 32 bytes each, so you > can fit more of them in a block, and they take up less disk and network > space. (In IBD; if a node maintains a mempool they'll need to receive all > the separate s-values) > > Another advatage is that block verification is sped up. For individual > signatures, the computation involves: > > e = h(m1, R1, P1) <- hash function, super fast > e*P <- point multiplication, slowest > R - e*P <- point addidion, pretty fast > s*G <- base point multiplication, pretty slow > > with s-aggregate verification, the first three steps are still carried out > on each signature, but the s*G operation only needs to be done once. > Instead another point addition per signature is needed, where you have some > accumulator and add in the left side: > A += R - e*P > this can be parallelized pretty well as it's commutative. > > The main downside I can see (assuming this actually works) is that it's > hard to cache signatures and quickly validate a block after it has come > in. It might not be as bad as it first seems, as validation given chached > signatures looks possible without any elliptic curve operations. Keep an > aggregate s-value (which is a scalar) for all the txs in your mempool. > When a block comes in, subtract all the s-values for txs not included in > the block. If the block includes txs you weren't aware of, request them in > the same way compact blocks works, and get the full signature for those > txs. It could be several thousand operations, but those are all bigInt > modular additions / subtractions which I believe are pretty quick in > comparison with point additions / multiplications. > > There may be other complications due to the fact that the witness-txids > change when building a block. TXIDs don't change though so should be > possible to keep track of things OK. > > Also you can't "fail fast" for the signature verification; you have to add > everything up before you can tell if it's correct. Probably not a big deal > as PoW check comes first, and invalid blocks are pretty uncommon and quite > costly. > > Would be interested to hear if this idea looks promising. > Andrew Polestra mentioned something like this in the context of CT / > mimblewimble transactions a while ago, but it seems it may be applicable to > regular bitcoin Schnorr txs. > > -Tadge > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > --001a114df358714ff1054f21d22b Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
I'm a bit amateur a= t this sort of thing, but let me try to argue that this proposal is in fact= horribly broken ;)

Suppose Alice has some UTXO with some mone= y Bob wants to steal.=C2=A0 Grant me that the public key P0 protecting Alic= e's UTXO is public (say because the public key has been reused elsewher= e).

Bob going to spend Alice's UTXO by generating random v= alues s0, k0 and R0 :=3D k0*G and thus creating a random signature for it, = [R0, s0].=C2=A0 Now clearly this signature isn't going to be valid by i= tself because it is just random.
Bob's goal will be to make a = transaction with other inputs such that, while the individual signatures ar= e not valid, the aggregated signature will be valid.

To do thi= s Bob generates a set of random public keys P1 ... P_n of the form P_i :=3D= P0 + r_i*G, and a bunch of random k1 ... k_n with R1 :=3D k1*G ... R_n := =3D k_n*G, such that

=C2=A0=C2=A0=C2=A0 h(m1, R1, P1) + ... + = h(m_n, R_n, P_n) =3D -h(m0, R0 P0) (modulo the order of the elliptic curve)=

I understand that this can be done efficiently wit= h Wagner's Generalized Birthday attack.

The RHS= aggregated signature equation on the private side is

=C2=A0=C2=A0= =C2=A0 k0 + k1 + ... k_n - h(m0, R0, P0)x0 - h(m1, R1, P1)(x0 + r1) - ... -= h(m_n, R_n, P_n)(x0 + r_n)

with x0 unknown to Bob.= =C2=A0 Rearranging the terms we get
=

=C2=A0=C2=A0=C2=A0 = k0 + k1 + ... k_n - [h(m0, R0, P0) + h(m1, R1, P1) + ... + h(m_n, R_n, P_n)= ]*x0 - [h(m1, R1, P1)*r1 + ... + h(m_n, R_n, P_n)*r_n]

However [h(m0, R0, P0) + h(m1, R1, P1) + ... + h(m_n, R= _n, P_n)] is 0 so cancelling that we are left with

=C2=A0=C2=A0=C2= =A0 k0 + k1 + ... k_n - [h(m1, R1, P1)*r1 + ... + h(m_n, R_n, P_n)*r_n]
=
which no longer depends on the unknown= value x0, so that is good.=C2=A0 Bob knows what this value is.

Bob creates a set UTXOs by spending to the set= of public keys P1 .. P_n.=C2=A0 Bob don't know what the private keys a= re for these public keys, but that is going to be okay.

Bob creates a final transaction that takes as input th= e UTXO of Alice's funds he wants to steal, with public key P0, and also= his newly created UTXOs with public keys P1 ... P_n.
For the signature on Alice's input he uses [R0,s0].=C2= =A0 For the rest of the signature he picks s1 ... s_n such that

=C2=A0=C2=A0=C2=A0 s0 + s1 + ... + sn =3D k0 += k1 + ... k_n - [h(m1, R1, P1)*r1 + ... + h(m_n, R_n, P_n)*r_n] (which is e= qual to k0 + k1 + ... k_n - h(m0, R0, P0)x0 - h(m1, R1, P1)(x0 + r1) - ... = - h(m_n, R_n, P_n)(x0 + r_n)).

and = uses signatures [R1, s1] ... [R_n, s_n] on his other inputs.

<= div class=3D"gmail_extra">Thus, while none of the individual signatures are= valid, the aggregated signature does validate.

One wrinkles in this argument is that Bob needs to pick m1 ...= m_n before he knows what the transaction will be.=C2=A0 I think this can b= e mitigated by using some combination of SIGHASH_ANYONECANPAY, but I'm = not sure if that works.=C2=A0 Even if my argument doesn't actually work= , I think it is close enough to be pretty scary.

Thanks goes to Pieter Wuille= for helping explain things to me; however any errors above are my own.
=

= On Sun, May 7, 2017 at 2:45 AM, adiabat via bitcoin-dev &= lt;bitcoin-dev@lists.linuxfoundation.org> wrote:
If / when Sc= hnorr signatures are deployed in a future witness version, it may be possib= le to have non-interactive partial aggregation of the signatures on a per-b= lock basis.=C2=A0 This could save quite a bit of space.=C2=A0 It *seems* no= t to have any security problems but this mailing list is very good at findi= ng vulnerabilities so that type of feedback is the main reason I'm writ= ing :) (A quick explanation of why this is horribly broken could save me lo= ts of time!)
(also sorry if this has been discussed; didn'= ;t see anything)

Quick recap / context of Schnorr = sigs:

There are a bunch of private keys x1, x2, x3= ...
multiply by generator G to get x1G =3D P1, x2G =3D P2, x3G = =3D P3

Everyone makes their sighash m1, m2, m3, an= d their random nonces k1, k2, k3.

To sign, people = calculate s values:

s1 =3D k1 - h(m1, R1, P1)x1
s2 =3D k2 - h(m2, R2, P2)x2

(adding the P2= into the e hash value is not in most literature / explanations but helps w= ith some attacks; I beleive that's the current thinking.=C2=A0 Anyway i= t doesn't matter for this idea)

Signature 1 is= [R1, s1].=C2=A0 Verifiers check, given P1, m1, R1, s1:

s1G =3D? R1 - h(m1, R1, P1)P1

You can *inter= actively* make aggregate signatures, which requires co-signers to build an = aggregate R value by coming up with their own k values, sharing their R wit= h the co-signers, adding up the R's to get a summed R, and using that t= o sign.

Non-interactively though, it seems like yo= u can aggregate half the signature.=C2=A0 The R values are unique to the [m= , P] pair, but the s's can be summed up:

s1 + = s2 =3D k1 + k2 - h(m1, R1, P1)x1 - h(m2, R2, P2)x2

(s1 + s2)G =3D R1 + R2 - h(m1, R1, P1)P1 - h(m2, R2, P2)P2

<= /div>
To use this property in Bitcoin, when making transactions, wallet= s can sign in the normal way, and the signature, consisting of [R, s] goes = into the witness stack.=C2=A0 When miners generate a block, they remove the= s-value from all compatible inputs, and commit to the aggregate s-value in= the coinbase transaction (either in a new OP_RETURN or alongside the exist= ing witness commitment structure).

The obvious adv= atage is that signatures go down to 32 bytes each, so you can fit more of t= hem in a block, and they take up less disk and network space. =C2=A0(In IBD= ; if a node maintains a mempool they'll need to receive all the separat= e s-values)

Another advatage is that block verific= ation is sped up.=C2=A0 For individual signatures, the computation involves= :

e =3D h(m1, R1, P1) =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 <- hash function, super fast
e*P =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 <-= point multiplication, slowest
R - e*P =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 <- point addidion, pretty = fast
s*G =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 <- base point multiplication, pretty slow

with s-aggregate verification, the first three= steps are still carried out on each signature, but the s*G operation only = needs to be done once.=C2=A0 Instead another point addition per signature i= s needed, where you have some accumulator and add in the left side:
A +=3D R - e*P
this can be parallelized pretty well as it'= s commutative.

The main downside I can see (assumi= ng this actually works) is that it's hard to cache signatures and quick= ly validate a block after it has come in.=C2=A0 It might not be as bad as i= t first seems, as validation given chached signatures looks possible withou= t any elliptic curve operations.=C2=A0 Keep an aggregate s-value (which is = a scalar) for all the txs in your mempool.=C2=A0 When a block comes in, sub= tract all the s-values for txs not included in the block.=C2=A0 If the bloc= k includes txs you weren't aware of, request them in the same way compa= ct blocks works, and get the full signature for those txs.=C2=A0 It could b= e several thousand operations, but those are all bigInt modular additions /= subtractions which I believe are pretty quick in comparison with point add= itions / multiplications.

There may be other compl= ications due to the fact that the witness-txids change when building a bloc= k.=C2=A0 TXIDs don't change though so should be possible to keep track = of things OK.

Also you can't "fail fast&q= uot; for the signature verification; you have to add everything up before y= ou can tell if it's correct.=C2=A0 Probably not a big deal as PoW check= comes first, and invalid blocks are pretty uncommon and quite costly.

Would be interested to hear if this idea looks promisi= ng.
Andrew Polestra mentioned something like this in the context = of CT / mimblewimble transactions a while ago, but it seems it may be appli= cable to regular bitcoin Schnorr txs.

-Tadge
=

_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.= linuxfoundation.org
https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev


=
--001a114df358714ff1054f21d22b--