Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 9F34971E for ; 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 ; Tue, 10 May 2016 21:43:41 +0000 (UTC) Received: by mail-io0-f180.google.com with SMTP id i75so27277621ioa.3 for ; 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: References: <20160510185728.GA1149@fedora-21-dvm> From: Sergio Demian Lerner Date: Tue, 10 May 2016 18:43:01 -0300 Message-ID: To: Tier Nolan , Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
Your idea of moving the Merkle ro= ot to the second chunk does not work.

The AsicBoost can change the v= ersion bits and it does not need to find a collision.
(Howeve= r Spondoolies patent only mentions Merkle collisions: https://patentscope.wipo.int/search/docservicepdf_pct/id00= 000032873338/PAMPH/WO2016046820.pdf)

Back in 2014 I d= esigned a ASIC-compatible block header that prevents AsicBoost in all its f= orms.

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 a= lso allows increased nonce space in the first 64 bytes.

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 "tie&quo= t; the two header chunks. It's a minimal change (but a hard-fork)
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?

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?

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

On = Tue, May 10, 2016 at 5:27 PM, Tier Nolan via bitcoin-dev = <bitcoin-dev@lists.linuxfoundation.org> wrote:
The various chunks i= n the double SHA256 are

Chunk 1: 64 bytes
= version
previous_block_digest
merkle_root[31:4]
<= div>

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 i= dentical except for the nonce.=C2=A0 With 4 bytes, the birthday paradox mea= ns collisions can be found reasonable easily.

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.

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.

On Tue, May 10, 2016 at 7:57 PM, Peter Todd via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
As part of t= he 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, b= ut if it
requires changes from SPV clients that's ok too. Also the fix this shou= ld be
compatible with existing mining hardware.


1) https://medium.com= /@bitcoinroundtable/bitcoin-roundtable-consensus-266d475a61ff

2) http://lists.linuxfo= undation.org/pipermail/bitcoin-dev/2016-April/012596.html

--
http= s://petertodd.org 'peter'[:-1]@petertodd.org

_____________________________________________= __
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev



_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.= linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev


--001a11434a3485a019053283d1b8--