Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id D1D7A9F0 for ; Wed, 9 Dec 2015 01:09:22 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-lb0-f175.google.com (mail-lb0-f175.google.com [209.85.217.175]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 52B83106 for ; Wed, 9 Dec 2015 01:09:18 +0000 (UTC) Received: by lbblt2 with SMTP id lt2so21165010lbb.3 for ; Tue, 08 Dec 2015 17:09:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=2NwQhr0WpECBDv4+61CttmjUbca7k+awSzCWeOapQoE=; b=lSWhKOmkWSevkvH2TRP0oLrCWd15WFKR65tIZO0W27nVjn8MkAiU4wDwW7ADdGN3uG f1ZPc8yxhhqLInDhX0cqqBa6m77rVrm4MIz4W9oJCu3bK7WNx5wC850ri2/Uq9XjjjIk cm/4n5M8WI6i4HD1Vr9ewPdLBSc/uVIqNyFFxDp+I8/SY77QQih9Qe/qGKCBL3ClF2Il o0eGfdYlefUGG9HJIKbjKjzx2YiXeJ5AHXLJtAZ07O8wKl+0WxYkP4PQXpf9lUAn7dIJ nhtxM/8pqo5xLcycX+H7QMyY8C3RUJtNnDcrRbZ1jtqCzt6Ftp7MulWj9wv6cXtZEWWC VM6A== MIME-Version: 1.0 X-Received: by 10.112.63.100 with SMTP id f4mr1177185lbs.85.1449623356599; Tue, 08 Dec 2015 17:09:16 -0800 (PST) Received: by 10.25.22.95 with HTTP; Tue, 8 Dec 2015 17:09:16 -0800 (PST) In-Reply-To: References: <20151208110752.GA31180@amethyst.visucore.com> Date: Tue, 8 Dec 2015 20:09:16 -0500 Message-ID: From: Gavin Andresen To: Gregory Maxwell Content-Type: multipart/alternative; boundary=001a11c3fe803a789f05266cbd9b X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Bitcoin Dev Subject: Re: [bitcoin-dev] Capacity increases for the Bitcoin system. X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Development Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 09 Dec 2015 01:09:22 -0000 --001a11c3fe803a789f05266cbd9b Content-Type: text/plain; charset=UTF-8 On Tue, Dec 8, 2015 at 6:59 PM, Gregory Maxwell wrote: > > We also need to fix the O(n^2) sighash problem as an additional BIP for > ANY > > blocksize increase. > > The witness data is never an input to sighash, so no, I don't agree > that this holds for "any" increase. > Here's the attack: Create a 1-megabyte transaction, with all of it's inputs spending segwitness-spending SIGHASH_ALL inputs. Because the segwitness inputs are smaller in the block, you can fit more of them into 1 megabyte. Each will hash very close to one megabyte of data. That will be O(n^2) worse than the worst case of a 1-megabyte transaction with signatures in the scriptSigs. Did I misunderstand something or miss something about the 1-mb transaction data and 3-mb segwitness data proposal that would make this attack not possible? RE: fraud proof data being deterministic: yes, I see, the data can be computed instead of broadcast with the block. RE: emerging consensus of Core: I think it is a huge mistake not to "design for success" (see http://gavinandresen.ninja/designing-for-success ). I think it is a huge mistake to pile on technical debt in consensus-critical code. I think we should be working harder to make things simpler, not more complex, whenever possible. And I think there are pretty big self-inflicted current problems because worries about theoretical future problems have prevented us from coming to consensus on simple solutions. -- -- Gavin Andresen --001a11c3fe803a789f05266cbd9b Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

= On Tue, Dec 8, 2015 at 6:59 PM, Gregory Maxwell <greg@xiph.org> = wrote:
> We also need to fix the = O(n^2) sighash problem as an additional BIP for ANY
> blocksize increase.

The witness data is never an input to sighash, so= no, I don't agree
that this holds for "any" increase.
=
Here's the attack:

Create a 1-megabyte transaction, with all of it's = inputs spending segwitness-spending SIGHASH_ALL inputs.

Because the segwitness in= puts are smaller in the block, you can fit more of them into 1 megabyte. Ea= ch will hash very close to one megabyte of data.

That will be O(n^2) worse than t= he worst case of a 1-megabyte transaction with signatures in the scriptSigs= .

Did I misunderstand something or miss something about the 1-mb tra= nsaction data and 3-mb segwitness data proposal that would make this attack= not possible?

RE: fraud proof data being deterministic: =C2=A0yes, I see, the da= ta can be computed instead of broadcast with the block.

RE: emerging consensus of= Core:

I think it is a huge mistake not to "design for success" (see=C2= =A0http://gavi= nandresen.ninja/designing-for-success ).

I think it is a huge mistake to pile= on technical debt in consensus-critical code. I think we should be working= harder to make things simpler, not more complex, whenever possible.

And I th= ink there are pretty big self-inflicted current problems because worries ab= out theoretical future problems have prevented us from coming to consensus = on simple solutions.

--
=
--
Gavin Andresen
--001a11c3fe803a789f05266cbd9b--