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)
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Per-block non-interactive Schnorr signature
 aggregation
Precedence: list


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