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 E626771F for ; 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 ; 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 To: Russell O'Connor Message-ID: <20170510075542.GZ10783@boulet.lan> References: MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="ICgY9hOMOIj3tkv0" Content-Disposition: inline In-Reply-To: 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 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 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--