From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 087C7892 for ; Sun, 7 May 2017 06:45:04 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-it0-f45.google.com (mail-it0-f45.google.com [209.85.214.45]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id F37B0134 for ; Sun, 7 May 2017 06:45:01 +0000 (UTC) Received: by mail-it0-f45.google.com with SMTP id x188so25615289itb.0 for ; Sat, 06 May 2017 23:45:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=awsomnet-org.20150623.gappssmtp.com; s=20150623; h=mime-version:from:date:message-id:subject:to; bh=q2N3lfEcgBQCF/8K0L8W97l8X3Ms52zwbZoR4JdySU4=; b=xgp79wdfqGParqrZS43lOxyQqky8IH+ToVvq8q9JI0EN2WRU+zFReePeY7AwYGPggl NBAhxajcs11ADTiwlE1aYNhHG5oH+sZHb8sTJqCioBvbveoWRiIAtf3iDm/4X3KGa+ox qQcylmneL69hlhlNbop/IWZI7Vhzf4kdPg+VPF/k6WuaJDTS+g7xNaafssR+ETP0Rr1S oHmV1Qstvjc/HETm/8QKF/rHhRm/GaVp6jHjk/8fEkiniGZssBHafaAmz4NOh3a4lHzM oYQIGfjxnNuZ6Bx8p/BrtpV7qKEAo1jWWAooCdw7rKhLEEdMb+Y2nyFMdPC6cRdXRWzg TknQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=q2N3lfEcgBQCF/8K0L8W97l8X3Ms52zwbZoR4JdySU4=; b=jLo4EhHMIzw2xz/4IluO71z8wboSqcvOmZ05idr6EkU+ggOnSnuCMN4HbpTdvcGoPu r3B7OmqQb9afskW5ydytIHGpDwSZR6VLREvWRKK9Rdg085yfECdrnvIAMw1O3+Kcv7/Z 0e7ZCM+IXliCNj7eDjk//AkYc5iED6UfkpJrb/xh5xm721+Mk9US+Y4pLIGav9J1q5B1 92X0yJETe6hBn3uF2RMvnzLw2ytc2djRSCHUXQQudGdoiAFGnilIQ2Z3QIKaHRDGg0zO YYIxgorhGSXwrSzRIQerR0jZ3JIa7Puwnoxyv+7gJkKs7UztaRwz8CGEtf5xgaYtxgM1 84vA== X-Gm-Message-State: AN3rC/42Jw65Nrx+tdDfBfNRUY0qYCpyN4/5EhK3lCsrk2H8J3/KUFHd yug8cAvkVLSIDlJgg0ZJsoMJLnWXorgP X-Received: by 10.36.57.68 with SMTP id l65mr16567365ita.101.1494139500935; Sat, 06 May 2017 23:45:00 -0700 (PDT) MIME-Version: 1.0 Received: by 10.36.47.68 with HTTP; Sat, 6 May 2017 23:45:00 -0700 (PDT) X-Originating-IP: [73.234.153.245] From: adiabat Date: Sun, 7 May 2017 02:45:00 -0400 Message-ID: To: Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary=001a114a9e4a3308f2054ee9769c X-Spam-Status: No, score=-1.4 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: [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: Sun, 07 May 2017 06:45:04 -0000 --001a114a9e4a3308f2054ee9769c Content-Type: text/plain; charset=UTF-8 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 --001a114a9e4a3308f2054ee9769c Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
If / when Schnorr signatures are deployed in a future= witness version, it may be possible to have non-interactive partial aggreg= ation of the signatures on a per-block basis.=C2=A0 This could save quite a= bit of space.=C2=A0 It *seems* not to have any security problems but this = mailing list is very good at finding vulnerabilities so that type of feedba= ck is the main reason I'm writing :) (A quick explanation of why this i= s 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 =3D P1, x2G =3D P2, x3G =3D P3

Everyone ma= kes their sighash m1, m2, m3, and 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 liter= ature / explanations but helps with some attacks; I beleive that's the = current thinking.=C2=A0 Anyway it 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 *interactively* make aggregate signatures, which = requires co-signers to build an aggregate R value by coming up with their o= wn 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-intera= ctively though, it seems like you can aggregate half the signature.=C2=A0 T= he 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

To use this property in Bitcoin, = when making transactions, wallets can sign in the normal way, and the signa= ture, consisting of [R, s] goes into the witness stack.=C2=A0 When miners g= enerate a block, they remove the s-value from all compatible inputs, and co= mmit 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 byte= s each, so you can fit more of them 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 separate s-values)

Anothe= r advatage is that block verification is sped up.=C2=A0 For individual sign= atures, 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 &= lt;- 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 mu= ltiplication, pretty slow

with s-aggregate v= erification, 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 po= int addition per signature is needed, where you have some accumulator and a= dd in the left side:
A +=3D R - e*P
this can be paralle= lized pretty well as it's commutative.

The mai= n downside I can see (assuming this actually works) is that it's hard t= o cache signatures and quickly validate a block after it has come in.=C2=A0= It might not be as bad as it first seems, as validation given chached sign= atures looks possible without 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, subtract all the s-values for txs not included i= n the block.=C2=A0 If the block includes txs you weren't aware of, requ= est them in the same way compact blocks works, and get the full signature f= or those txs.=C2=A0 It could be several thousand operations, but those are = all bigInt modular additions / subtractions which I believe are pretty quic= k in comparison with point additions / multiplications.

There may be other complications due to the fact that the witness-txi= ds change when building a block.=C2=A0 TXIDs don't change though so sho= uld be possible to keep track of things OK.

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

Would be interested to h= ear if this idea looks promising.
Andrew Polestra mentioned somet= hing 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
--001a114a9e4a3308f2054ee9769c--