Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id E026BB6C for ; Mon, 17 Apr 2017 22:35:00 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-yw0-f181.google.com (mail-yw0-f181.google.com [209.85.161.181]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id CC207180 for ; Mon, 17 Apr 2017 22:34:56 +0000 (UTC) Received: by mail-yw0-f181.google.com with SMTP id j9so62000947ywj.3 for ; Mon, 17 Apr 2017 15:34:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=U74r9NzVns6oCxB/9emicI/U6edFoFWvyJz8Bf1I9CE=; b=Iwi1F4bKrmJPxaz30+/HN0FWz4g/AGFXmWufnCuEusVxQBpU2EOF2o7mOrxDncy+Gd wwIbjfSz5c62S6W7BMlgCam+6Zhq1L364bS9fKYWlZDfNLDS7IufKx12SS2UQgHylZnn tm+buJhzkSxzvAxwFk5X45cR4vI1NRCR9kQtWY0b51ngbs+Sr/WQ3cClt24JI1X8iBei bnj62Vuxl2il2yt2qNYPtGicgny4RKB5E5qwSJ+tYJOMNvwJqTYGv5PDIGSwuDDXrOK6 EOVo08G8Bi+/5sBgdPRTTu/zhU93g9C0ThbZUyhi0Fma0N1FBCBJUZ2KgLFAgqgyI04b KRVw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=U74r9NzVns6oCxB/9emicI/U6edFoFWvyJz8Bf1I9CE=; b=hvXvwUG+OFTrsdbOGd+vvDzKeSuMwWrBFYhWffCv1UpM50PC3eZpVs8+uqb8+AwT1b dSKS8GZ7RrI++lIiEaj+zR6yM1/fwldVVHfjTQq9lsgR3iZ8BU4iFKCbjZbsnVq74Yo+ mNFH0Eh67AtloZUqu+D1dc32R0Sekjz5kTDHbon6bBBusGa9gDWo6FVfwNF8S4G30e1F Ptv/vE91Rh7NgjDlhzhQtrC/SJrotiMixBmiMSnDs3kAJkZcryHtDLvvyqOTeBvcujLk r9YUXv7EQmpMXctz5zgHlsQl7loQo4BluzQUZWvVkPd25YUSGJqyICZuTLtYyBQAj7Zp LrEg== X-Gm-Message-State: AN3rC/6TzFgnSmnlaR65LThsWvJcfRBT8ouk/Z6l8JknyyC7Xz9MxND3 lOs2wTWgWfoFkH8GMDEqUQ3s9FgRcw== X-Received: by 10.13.221.208 with SMTP id g199mr16873604ywe.21.1492468496012; Mon, 17 Apr 2017 15:34:56 -0700 (PDT) MIME-Version: 1.0 Received: by 10.37.35.88 with HTTP; Mon, 17 Apr 2017 15:34:55 -0700 (PDT) Received: by 10.37.35.88 with HTTP; Mon, 17 Apr 2017 15:34:55 -0700 (PDT) In-Reply-To: References: <0690791a46d7a7699fc3427e92a76e9b.squirrel@mail.fairluck.net> <461f7ce7a17c5765daadc461cdd3373c@cock.lu> From: Natanael Date: Tue, 18 Apr 2017 00:34:55 +0200 Message-ID: To: Erik Aronesty , erik@q32.com Content-Type: multipart/alternative; boundary=94eb2c06e3fa8b3515054d6466ed X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE 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] Malice Reactive Proof of Work Additions (MR POWA): Protecting Bitcoin from malicious miners 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: Mon, 17 Apr 2017 22:35:01 -0000 --94eb2c06e3fa8b3515054d6466ed Content-Type: text/plain; charset=UTF-8 Den 17 apr. 2017 16:14 skrev "Erik Aronesty via bitcoin-dev" < bitcoin-dev@lists.linuxfoundation.org>: It's too bad we can't make the POW somehow dynamic so that any specialized hardware is impossible, and only GPU / FPGA is possible. Maybe a variant of Keccak where the size of the sponge is increased along with additional zero bits required. Seems like this would either have to resist specialized hardware or imply sha3 is compromised such that the size of the sponge does not incerase the number of possible output bits as expected. Technically SHA3 (keccak) already has the SHAKE mode, an extensible output function (XOF). It's basically a hash with arbitary output length (with fixed state size, 256 bits is the common choice). A little bit like hooking a hash straight into a stream cipher. The other modes should *probably* not allow the same behavior, though. I can't guarantee that however. You may be interested in looking at parameterizable ciphers and if any of them might be applicable to PoW. IMHO the best option if we change PoW is an algorithm that's moderately processing heavy (we still need reasonably fast verification) and which resists partial state reuse (not fast or fully "linear" in processing like SHA256) just for the sake of invalidating asicboost style attacks, and it should also have an existing reference implementation for hardware that's provably close in performance to the theoretical ideal implementation of the algorithm (in other words, one where we know there's no hidden optimizations). Anything relying on memory or other such expensive components is likely to fall flat eventually as fast memory is made more compact, cheaper and moves closer to the cores. That should be approximately what it takes to level out the playing field in ASIC manufacturing, because then we would know there's no fancy tricks to deploy that would give one player unfair advantage. The competition would mostly be about packing similar gate designs closely and energy efficiency. (Now that I think about it, the proof MAY have to consider energy use too, as a larger and slower but more efficient chip still is competitive in mining...) We should also put a larger nonce in the header if possible, to reduce the incentive to mess with the entropy elsewhere in blocks. --94eb2c06e3fa8b3515054d6466ed Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

=
De= n 17 apr. 2017 16:14 skrev "Erik Aronesty via bitcoin-dev" <bi= tcoin-dev@lists.linuxfoundation.org>:
<= blockquote class=3D"m_8645300429802790440quote" style=3D"margin:0 0 0 .8ex;= border-left:1px #ccc solid;padding-left:1ex">

It's too= bad we can't make the POW somehow dynamic so that any specialized hard= ware is impossible, and only GPU / FPGA is possible.


= Maybe a variant of=C2=A0Keccak where the size of the sponge is increased along with additional = zero bits required.=C2=A0 Seems like this would either have to resist speci= alized hardware or imply sha3 is compromised such that the size of the spon= ge does not incerase the number of possible output bits as expected.=C2=A0<= /span>

Technically SHA3 (keccak) already has the SHAKE mode, an exte= nsible output function (XOF). It's basically a hash with arbitary outpu= t length (with fixed state size, 256 bits is the common choice). A little b= it like hooking a hash straight into a stream cipher.=C2=A0

The other modes should *probably* not= allow the same behavior, though. I can't guarantee that however.=C2=A0=

You may be interested i= n looking at parameterizable ciphers and if any of them might be applicable= to PoW.=C2=A0

IMHO the = best option if we change PoW is an algorithm that's moderately processi= ng heavy (we still need reasonably fast verification) and which resists par= tial state reuse (not fast or fully "linear" in processing like S= HA256) just for the sake of invalidating asicboost style attacks, and it sh= ould also have an existing reference implementation for hardware that's= provably close in performance to the theoretical ideal implementation of t= he algorithm (in other words, one where we know there's no hidden optim= izations).=C2=A0

Anythin= g relying on memory or other such expensive components is likely to fall fl= at eventually as fast memory is made more compact, cheaper and moves closer= to the cores.=C2=A0

Tha= t should be approximately what it takes to level out the playing field in A= SIC manufacturing, because then we would know there's no fancy tricks t= o deploy that would give one player unfair advantage. The competition would= mostly be about packing similar gate designs closely and energy efficiency= . (Now that I think about it, the proof MAY have to consider energy use too= , as a larger and slower but more efficient chip still is competitive in mi= ning...)=C2=A0

We should= also put a larger nonce in the header if possible, to reduce the incentive= to mess with the entropy elsewhere in blocks.=C2=A0
--94eb2c06e3fa8b3515054d6466ed--