path: root/1a/181ca61cb9135542c3ac4db92227b11a621009

Return-Path: <sergio.d.lerner@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 9F34971E
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 10 May 2016 21:43:42 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-io0-f180.google.com (mail-io0-f180.google.com
	[209.85.223.180])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 6E65B193
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 10 May 2016 21:43:41 +0000 (UTC)
Received: by mail-io0-f180.google.com with SMTP id i75so27277621ioa.3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 10 May 2016 14:43:41 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to; 
	bh=uA477wleNo6ls5d9ZobO6/LwFfJB2AaoQHpRbQ+wrlk=;
	b=npHhoJzx7pF+CPvHzAejiVPqlytiDH+guR/JSdQdp2favKYJOmPFaHZ7eCBgSc9o2x
	+hoSIflCXA4zwlS8DldTj2KXCW0L9xT3ZSBm97Icg8z6hjke+DbRPDYPrMyv1MhtG4eT
	A6VS9ij1XI8LpIQaVw+t0JeETvrOA/WSFgdCp7ioBAgl/ZvCL7HlOpjrG0qhYUdncyFy
	GGxP1YORoFkwyoxqzBf24CZ0lDE97qc3EIxJj5bWSvS4ajo8WAh5plxKD0BXQ1Lz2eaX
	RaMvw+ekS64IPTobqaur0medqFatgn7IrcVrf5s73iJTtxUbHtXsjv6iwYsdWw7QrLQZ
	PNEA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20130820;
	h=x-gm-message-state:mime-version:in-reply-to:references:from:date
	:message-id:subject:to;
	bh=uA477wleNo6ls5d9ZobO6/LwFfJB2AaoQHpRbQ+wrlk=;
	b=aeCk51Z1x/0/wx71N0n/5fXihgs0CVwwWap6AB3AcMTfC0cLTwNkSFs+pFkTloj/K8
	Sg+O0XlhjRRqGqRE7UfXzV+E5BuGn7+uLDWTRNtX/M8wpoO8un66x1G8hZwX+mF+nLmF
	77PLqNUXRT36Y5hNKcl32hvudRgw91MTV/q79ls7f79UDm1qpQgiS20JMCdYRI/2RmYF
	uy9eyp0Gs9nA2ILttTvBAhgHgUl6mOm0UyQbjz4dCEfupHWL+gNmmSlZ/SdUEeoWVNl+
	FrDnrW6fW1SkRmq5PnRMBi7vvoLV/PE+yLUEDiM5n638xuNLli+Cx8mr7Xy89KbDFOqz
	Qv6g==
X-Gm-Message-State: AOPr4FWo0gX7nW48keXtVo9J+iaOmsC+nzVFoJtqtjfHOjaSNQnLIe4li2K0xmhgXbAHuRnrHuQTNpk1v6jcmA==
X-Received: by 10.36.22.141 with SMTP id a135mr2366291ita.80.1462916620847;
	Tue, 10 May 2016 14:43:40 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.107.142.69 with HTTP; Tue, 10 May 2016 14:43:01 -0700 (PDT)
In-Reply-To: <CAE-z3OWvLqONwaN+608jBn9=q1yUvU4ggGrMpA8rE6qmjDQHtg@mail.gmail.com>
References: <20160510185728.GA1149@fedora-21-dvm>
	<CAE-z3OWvLqONwaN+608jBn9=q1yUvU4ggGrMpA8rE6qmjDQHtg@mail.gmail.com>
From: Sergio Demian Lerner <sergio.d.lerner@gmail.com>
Date: Tue, 10 May 2016 18:43:01 -0300
Message-ID: <CAKzdR-ou2FYjjxmRBLARhvfhHO-46weiMc2Q2f+GZf1E_JUEAg@mail.gmail.com>
To: Tier Nolan <tier.nolan@gmail.com>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=001a11434a3485a019053283d1b8
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
Subject: Re: [bitcoin-dev] Making AsicBoost irrelevant
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: Tue, 10 May 2016 21:43:42 -0000

--001a11434a3485a019053283d1b8
Content-Type: text/plain; charset=UTF-8

Your idea of moving the Merkle root to the second chunk does not work.

The AsicBoost can change the version bits and it does not need to find a
collision.
(However *Spondoolies patent *only mentions Merkle collisions:
https://patentscope.wipo.int/search/docservicepdf_pct/id00000032873338/PAMPH/WO2016046820.pdf
)

Back in 2014 I designed a ASIC-compatible block header that prevents
AsicBoost in all its forms.

You can find it here:
https://bitslog.wordpress.com/2014/03/18/the-re-design-of-the-bitcoin-block-header/

Basically, the idea is to put in the first 64 bytes a 4 byte hash of the
second 64-byte chunk. That design also allows increased nonce space in the
first 64 bytes.

But it you want to do a simpler change, you can more easily use the first
32 bits of the Parent Block Hash (now currently zero) to store the first 4
bytes of the SHA256 of the last 16 bytes of the header. That way to "tie"
the two header chunks. It's a minimal change (but a hard-fork)

But some ASIC companies already have cores that are better (on power, cost,
rate, temperature, etc.) than competing companies ASICs. Why do you think a
10% improvement from AsicBoost is different from many of other improvements
they already have (secretly) added? Maybe we (?) should only allow ASICs
that have a 100% open source designs?

If we change the protocol then the message to the ecosystem is that ASIC
optimizations should be kept secret. It is fair to change the protocol
because we don't like that certain ASIC manufacturer has better chips, if
the chips are sold in the market and anyone can buy them? And what about
using approximate adders (30% improvement), or dual rail asynchronous
adders (also more than 10% improvement) ? How do we repair those?

Disclaimer: I have stake in AsicBoost, but I'm not sure about this.


On Tue, May 10, 2016 at 5:27 PM, Tier Nolan via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> The various chunks in the double SHA256 are
>
> Chunk 1: 64 bytes
> version
> previous_block_digest
> merkle_root[31:4]
>
> Chunk 2: 64 bytes
> merkle_root[3:0]
> nonce
> timestamp
> target
>
> Chunk 3: 64 bytes
> digest from first sha pass
>
> Their improvement requires that all data in Chunk 2 is identical except
> for the nonce.  With 4 bytes, the birthday paradox means collisions can be
> found reasonable easily.
>
> If hard forks are allowed, then moving more of the merkle root into the
> 2nd chunk would make things harder.  The timestamp and target could be
> moved into chunk 1.  This increases the merkle root to 12 bytes in the 2nd
> chunk.  Finding collisions would be made much more difficult.
>
> If ASIC limitations mean that the nonce must stay where it is, this would
> mean that the merkle root would be split into two pieces.
>
> On Tue, May 10, 2016 at 7:57 PM, Peter Todd via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> As part of the hard-fork proposed in the HK agreement(1) we'd like to
>> make the
>> patented AsicBoost optimisation useless, and hopefully make further
>> similar
>> optimizations useless as well.
>>
>> What's the best way to do this? Ideally this would be SPV compatible, but
>> if it
>> requires changes from SPV clients that's ok too. Also the fix this should
>> be
>> compatible with existing mining hardware.
>>
>>
>> 1)
>> https://medium.com/@bitcoinroundtable/bitcoin-roundtable-consensus-266d475a61ff
>>
>> 2)
>> http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-April/012596.html
>>
>> --
>> https://petertodd.org 'peter'[:-1]@petertodd.org
>>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

--001a11434a3485a019053283d1b8
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div><div><div><div><div>Your idea of moving the Merkle ro=
ot to the second chunk does not work.<br><br>The AsicBoost can change the v=
ersion bits and it does not need to find a collision.<br></div><div>(Howeve=
r <b>Spondoolies patent </b>only mentions Merkle collisions: <a href=3D"htt=
ps://patentscope.wipo.int/search/docservicepdf_pct/id00000032873338/PAMPH/W=
O2016046820.pdf">https://patentscope.wipo.int/search/docservicepdf_pct/id00=
000032873338/PAMPH/WO2016046820.pdf</a>)<br><br></div><div>Back in 2014 I d=
esigned a ASIC-compatible block header that prevents AsicBoost in all its f=
orms.<br><br></div>You can find it here: <a href=3D"https://bitslog.wordpre=
ss.com/2014/03/18/the-re-design-of-the-bitcoin-block-header/" target=3D"_bl=
ank">https://bitslog.wordpress.com/2014/03/18/the-re-design-of-the-bitcoin-=
block-header/</a><br></div><div><br></div>Basically, the idea is to put in =
the first 64 bytes a 4 byte hash of the second 64-byte chunk. That design a=
lso allows increased nonce space in the first 64 bytes. <br><br></div>But i=
t you want to do a simpler change, you can more easily use the first 32 bit=
s of the Parent Block Hash (now currently zero) to store the first 4 bytes =
of the SHA256 of the last 16 bytes of the header. That way to &quot;tie&quo=
t; the two header chunks. It&#39;s a minimal change (but a hard-fork)<br><b=
r></div>But some ASIC companies already have cores that are better (on powe=
r, cost, rate, temperature, etc.) than competing companies ASICs. Why do yo=
u think a 10% improvement from AsicBoost is different from many of other im=
provements they already have (secretly) added? Maybe we (?) should only all=
ow ASICs that have a 100% open source designs? <br><br></div><div>If we cha=
nge the protocol then the message to the ecosystem is that ASIC optimizatio=
ns should be kept secret. It is fair to change the protocol because we don&=
#39;t like that certain ASIC manufacturer has better chips, if the chips ar=
e sold in the market and anyone can buy them? And what about using approxim=
ate adders (30% improvement), or dual rail asynchronous adders (also more t=
han 10% improvement) ? How do we repair those?<br></div><div></div><div><di=
v><div><div><div><br></div><div>Disclaimer: I have stake in AsicBoost, but =
I&#39;m not sure about this.<br></div><div>=C2=A0<br></div></div></div></di=
v></div></div><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">On =
Tue, May 10, 2016 at 5:27 PM, Tier Nolan via bitcoin-dev <span dir=3D"ltr">=
&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_bla=
nk">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</span> wrote:<br><blockqu=
ote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc s=
olid;padding-left:1ex"><div dir=3D"ltr"><div><div><div>The various chunks i=
n the double SHA256 are<br><br></div><div></div>Chunk 1: 64 bytes<br></div>=
version<br></div><div>previous_block_digest<br></div>merkle_root[31:4]<br><=
div><div><br></div><div>Chunk 2: 64 bytes<br></div><div>merkle_root[3:0]<br=
></div><div>nonce<br></div><div>timestamp<br></div><div>target<br><br></div=
><div>Chunk 3: 64 bytes<br></div><div>digest from first sha pass<br><br></d=
iv><div></div><div>Their improvement requires that all data in Chunk 2 is i=
dentical except for the nonce.=C2=A0 With 4 bytes, the birthday paradox mea=
ns collisions can be found reasonable easily.<br><br>If hard forks are allo=
wed, then moving more of the merkle root into the 2nd chunk would make thin=
gs harder.=C2=A0 The timestamp and target could be moved into chunk 1.=C2=
=A0 This increases the merkle root to 12 bytes in the 2nd chunk.=C2=A0 Find=
ing collisions would be made much more difficult.<br><br></div><div>If ASIC=
 limitations mean that the nonce must stay where it is, this would mean tha=
t the merkle root would be split into two pieces.<br></div></div></div><div=
 class=3D"gmail_extra"><br><div class=3D"gmail_quote"><div><div class=3D"h5=
">On Tue, May 10, 2016 at 7:57 PM, Peter Todd via bitcoin-dev <span dir=3D"=
ltr">&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D=
"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</span> wrote:<br></d=
iv></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;borde=
r-left:1px #ccc solid;padding-left:1ex"><div><div class=3D"h5">As part of t=
he hard-fork proposed in the HK agreement(1) we&#39;d like to make the<br>
patented AsicBoost optimisation useless, and hopefully make further similar=
<br>
optimizations useless as well.<br>
<br>
What&#39;s the best way to do this? Ideally this would be SPV compatible, b=
ut if it<br>
requires changes from SPV clients that&#39;s ok too. Also the fix this shou=
ld be<br>
compatible with existing mining hardware.<br>
<br>
<br>
1) <a href=3D"https://medium.com/@bitcoinroundtable/bitcoin-roundtable-cons=
ensus-266d475a61ff" rel=3D"noreferrer" target=3D"_blank">https://medium.com=
/@bitcoinroundtable/bitcoin-roundtable-consensus-266d475a61ff</a><br>
<br>
2) <a href=3D"http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-A=
pril/012596.html" rel=3D"noreferrer" target=3D"_blank">http://lists.linuxfo=
undation.org/pipermail/bitcoin-dev/2016-April/012596.html</a><br>
<span><font color=3D"#888888"><br>
--<br>
<a href=3D"https://petertodd.org" rel=3D"noreferrer" target=3D"_blank">http=
s://petertodd.org</a> &#39;peter&#39;[:-1]@<a href=3D"http://petertodd.org"=
 rel=3D"noreferrer" target=3D"_blank">petertodd.org</a><br>
</font></span><br></div></div>_____________________________________________=
__<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
<br></blockquote></div><br></div>
<br>_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
<br></blockquote></div><br></div>

--001a11434a3485a019053283d1b8--