diff options
| author | Andrew Poelstra <apoelstra@wpsoftware.net> | 2017-05-10 07:55:42 +0000 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2017-05-10 07:55:44 +0000 |
| commit | 564a292e65d21ae202e89d871b68fb619f11aebb (patch) | |
| tree | 00f8a379cbda23ad36aa163ed5482cb2192157c2 | |
| parent | 7846dbee97bbc2d5d6155368ab450d1f9f66e967 (diff) | |
| download | pi-bitcoindev-564a292e65d21ae202e89d871b68fb619f11aebb.tar.gz pi-bitcoindev-564a292e65d21ae202e89d871b68fb619f11aebb.zip | |
Re: [bitcoin-dev] Per-block non-interactive Schnorr signature aggregation
| -rw-r--r-- | cd/8ee81ec4c4609f42e431cc893448e6dd455898 | 137 |
1 files changed, 137 insertions, 0 deletions
diff --git a/cd/8ee81ec4c4609f42e431cc893448e6dd455898 b/cd/8ee81ec4c4609f42e431cc893448e6dd455898 new file mode 100644 index 000000000..8673d37b9 --- /dev/null +++ b/cd/8ee81ec4c4609f42e431cc893448e6dd455898 @@ -0,0 +1,137 @@ +Return-Path: <apoelstra@wpsoftware.net> +Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org + [172.17.192.35]) + by mail.linuxfoundation.org (Postfix) with ESMTPS id E626771F + for <bitcoin-dev@lists.linuxfoundation.org>; + Wed, 10 May 2017 07:55:44 +0000 (UTC) +X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 +Received: from mail.wpsoftware.net (wpsoftware.net [96.53.77.134]) + by smtp1.linuxfoundation.org (Postfix) with ESMTP id 47DE214E + for <bitcoin-dev@lists.linuxfoundation.org>; + Wed, 10 May 2017 07:55:44 +0000 (UTC) +Received: from boulet.lan (boulot.lan [192.168.0.193]) + by mail.wpsoftware.net (Postfix) with ESMTPSA id 227C9400FB; + Wed, 10 May 2017 07:55:42 +0000 (UTC) +Date: Wed, 10 May 2017 07:55:42 +0000 +From: Andrew Poelstra <apoelstra@wpsoftware.net> +To: Russell O'Connor <roconnor@blockstream.io> +Message-ID: <20170510075542.GZ10783@boulet.lan> +References: <CAKEeUhh3Rj3Dh8ab5FFR6dGKc2Ojm5Z0uyWtAtrPrh=7dvj-GA@mail.gmail.com> + <CAMZUoK=iXXYkN64+T-haK=vXrd=L7eqbo3P-MOhrj6p35uaW0A@mail.gmail.com> +MIME-Version: 1.0 +Content-Type: multipart/signed; micalg=pgp-sha256; + protocol="application/pgp-signature"; boundary="ICgY9hOMOIj3tkv0" +Content-Disposition: inline +In-Reply-To: <CAMZUoK=iXXYkN64+T-haK=vXrd=L7eqbo3P-MOhrj6p35uaW0A@mail.gmail.com> +User-Agent: Mutt/1.7.1 (2016-10-04) +X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD + 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 <bitcoin-dev@lists.linuxfoundation.org> +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 <bitcoin-dev.lists.linuxfoundation.org> +List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> +List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> +List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> +List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> +List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe> +X-List-Received-Date: Wed, 10 May 2017 07:55:45 -0000 + + +--ICgY9hOMOIj3tkv0 +Content-Type: text/plain; charset=us-ascii +Content-Disposition: inline +Content-Transfer-Encoding: quoted-printable + +On Tue, May 09, 2017 at 09:59:06PM -0400, Russell O'Connor via bitcoin-dev = +wrote: +> I'm a bit amateur at this sort of thing, but let me try to argue that this +> proposal is in fact horribly broken ;) +>=20 +> 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). +>=20 +> Bob going to spend Alice's UTXO by generating random values s0, k0 and R0 +> :=3D k0*G and thus creating a random signature for it, [R0, s0]. Now cle= +arly +> this signature isn't going to be valid by itself because it is just rando= +m. +> Bob's goal will be to make a transaction with other inputs such that, whi= +le +> the individual signatures are not valid, the aggregated signature will be +> valid. +> + +If you seed the randomization with every R value (which would come for free +if you used, say, the witness root) then Wagner's attack no longer applies. + +The idea is that no aggregation occurs until a miner produces a block. You +have a bunch of independent Schnorr sigs (s_i, R_i). Then the _miner_ multi= +ples +each s_i by H(witness root || index) or whatever, sums up the s_i's, and co= +mmits +the sum somewhere where it doesn't affect the root. + +Verifiers then multiply each R_i by the same multiplying factors and are ab= +le +to do a batch verification of them. + + +Verifiers who have seen a signature before and cached it as valid can save +themselves a bit of time by subtracting H(witness root || index)*s_i from +the summed s-value and then skipping R_i in the above step. These are scalar +operations and are extremely cheap. + +They can recognize the signature given only the transaction it signs and R_= +i, +which uniquely determine a valid signature. + + +I believe this is what Tadge was referring to when he mentioned a talk of m= +ine. +It's roughly what I've had in mind whenever I talk about non-interactive Sc= +hnorr +aggregation. + + + +Cheers +Andrew + + +--=20 +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 + + +--ICgY9hOMOIj3tkv0 +Content-Type: application/pgp-signature; name="signature.asc" + +-----BEGIN PGP SIGNATURE----- + +iQEcBAEBCAAGBQJZEsd8AAoJEMWI1jzkG5fBmGcIAJFpS5Vs0Ch3JQAe3odBrixc +fS4TwGeORAjiXWmwvOeq+4ff4xpcOXCAR/BYwVojfLmCfTf4LvdCXX2mwq6uwvEl +7NGINe7kIWHulZVnn1zBb+5w3MGpjdQ7qGf9vuJG39jWIuo9tMvzHfI72RfZeHTe +kYwhHx1Twf44Iw6Fay1l1ug3rhO+T+w0ZsMfw5WvKh52joyGsiVVHOZkutOB9Rah +sOwFfj932MCYvPFf7Br6uoAVmTdtM5p/3mrp0c8k4tA4mMlCuSP1F3huFIbotSAh +XD/hT+zT3m3V/uPLV9bgF1/zUH4tW5WK8LoZD04vxui7G1BdOk2LLz1Ty5DOYbc= +=DLxO +-----END PGP SIGNATURE----- + +--ICgY9hOMOIj3tkv0-- + |