Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 9E692BE0 for ; Thu, 6 Apr 2017 17:43:59 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-vk0-f66.google.com (mail-vk0-f66.google.com [209.85.213.66]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9013217C for ; Thu, 6 Apr 2017 17:43:58 +0000 (UTC) Received: by mail-vk0-f66.google.com with SMTP id d188so6214228vka.3 for ; Thu, 06 Apr 2017 10:43:58 -0700 (PDT) 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=FnQu3SMNDd3asf3n2R1Xy1ifD5pY6KUb0gz+1A7P09A=; b=TUnjG/qqrB90YNVbFtBWkirthsTb8mJmUYRksKd2SvhJBv1Q+7zGlmkp/FZ2V9ONeW 6vTGBS2LyXoz9imnKB33D9VMxcAsW4akqxe8slpxJ8AnZVbCYXDilgL7nokarayMJNOK 4jxVbOjw9QxhD/L8Ad0zPJeC/DquC277GElGYV44ryn7S1vm3r+fXHpTfDhMKsGJTqaw DUAXv69wh2gEtILSWv/5y38MuytfRP7XTaVUyNbMDAMfjh5UioOJp/8zW6VDrD6AhP2Z CiP3zlDXPgo7WWrmXrjU5zEqgLholEw7nX6T2NBIrwRziSS/HKo7l4xLm7ns77FPuFAb nZ/A== X-Gm-Message-State: AFeK/H37zAbNaMW1cFrrQBIKh+VfIOVlK3wKKnJVk5FERseNfMHONQGaEVx82xjGdoPSZA== X-Received: by 10.31.75.68 with SMTP id y65mr15888175vka.46.1491500637624; Thu, 06 Apr 2017 10:43:57 -0700 (PDT) Received: from mail-vk0-f43.google.com (mail-vk0-f43.google.com. [209.85.213.43]) by smtp.gmail.com with ESMTPSA id d128sm547780vke.12.2017.04.06.10.43.57 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 06 Apr 2017 10:43:57 -0700 (PDT) Received: by mail-vk0-f43.google.com with SMTP id z204so49432300vkd.1 for ; Thu, 06 Apr 2017 10:43:57 -0700 (PDT) X-Received: by 10.159.36.39 with SMTP id 36mr1632329uaq.84.1491500636717; Thu, 06 Apr 2017 10:43:56 -0700 (PDT) MIME-Version: 1.0 Received: by 10.103.122.149 with HTTP; Thu, 6 Apr 2017 10:43:56 -0700 (PDT) In-Reply-To: References: From: Timo Hanke Date: Thu, 6 Apr 2017 10:43:56 -0700 X-Gmail-Original-Message-ID: Message-ID: To: Bryan Bishop , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary=001a11352768a278b7054c830da7 X-Spam-Status: No, score=-1.4 required=5.0 tests=BAYES_00,FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function 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: Thu, 06 Apr 2017 17:43:59 -0000 --001a11352768a278b7054c830da7 Content-Type: text/plain; charset=UTF-8 Bryan, Interesting argument, but I think it is not an accurate comparison. People usually mean that, for example, say 2^80 of the original operations are needed rather than the intended 2^128 to find a collision. This could be the case in a broken algorithms such as a toy SHA variant with too small states and too few rounds. These kind of attacks usually refer to that something is learned from prior evaluations that be should't be possible to be learned. For example, if someone could somehow construct a pre-image in 256 evaluations, getting one additional bit right at a time. Similar to a cheap combination lock where you can figure out the correct 4 digits in a worst case of 4*10 attempts by "feeling" it, rather than having to do the intended 10,000 attempts. That's the kind of thing that would be called an "attack". Here, however, we are talking about making the individual operations cheaper by a constant of ~20%, not changing the number of operations. That doesn't qualify as an attack in the sense that you mean. Best, Timo On Thu, Apr 6, 2017 at 5:11 AM, Bryan Bishop via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > On Thu, Apr 6, 2017 at 7:02 AM, Luv Khemani via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > >> Could you elaborate on why you consider ASICBOOST to be an attack? Attack >> here implies ill-intent by the practitioner towards the network as a >> primary motivating factor. >> >> > See https://www.reddit.com/r/Bitcoin/comments/63otrp/ > gregory_maxwell_major_asic_manufacturer_is/dfwcki3/ > > """ > I think that it is an attack is a completely unambiguous technical > description of what it is. If a signature is supposed to resist forgery > against 2^128 operations, but you find a way to do it with 2^80 instead, > this is an attack. It is, perhaps, not a very concerning attack and you may > or may not change your signature scheme to avoid it or may just instead say > the scheme has 2^80 security. But there is no doubt that it would be called > an attack, especially if it was not described in the original proposal. > > In Bitcoin's Proof of Work, you are attempting to prove a certain amount > of work has been done. This shortcut significantly reduces the amount of > work. It's an attack. Normally it wouldn't be a serious attack-- it would > just get appended to the defacto definition of what the Bitcoin Proof of > work is-- similar to the signature system just getting restarted as having > 2^80 security-- but in it's covert form it cannot just be adopted because > it blocks many further improvements (not just segwit, but the vast majority > of other proposals), and additional the licensing restrictions inhibit > adoption. > > The proposal I posted does not prevent the technique, only the covert > form: That is, it doesn't even attempt to solve the patented tech > eventually will centralize the system problem. It is narrowly targeted at > the interference with upgrades. > > Taking a step back-- even ignoring my geeking out about the technical > definition of 'attack' in crypographic contexts, we have a set of issues > here that left addressed will seriously harm the system going forward for > the the significant monetary benefit of an exploiting party. I think that > also satisfies a lay definition of the term: Something someone does, that > none one expected, that makes them money at everyone elses expense. > """ > > - Bryan > http://heybryan.org/ > 1 512 203 0507 <(512)%20203-0507> > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > --001a11352768a278b7054c830da7 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Bryan,

Interesting argument, but I thin= k it is not an accurate comparison. People usually mean that, for example, = say 2^80 of the original operations are needed rather than the intended 2^1= 28 to find a collision. This could be the case in a broken algorithms such = as a toy SHA variant with too small states and too few rounds. These kind o= f attacks usually refer to that something is learned from prior evaluations= that be should't be possible to be learned. For example, if someone co= uld somehow construct a pre-image in 256 evaluations, getting one additiona= l bit right at a time. Similar to a cheap combination lock where you can fi= gure out the correct 4 digits in a worst case of 4*10 attempts by "fee= ling" it, rather than having to do the intended 10,000 attempts. That&= #39;s the kind of thing that would be called an "attack".

Here, however, we are talking about making the individual= operations cheaper by a constant of ~20%, not changing the number of opera= tions. That doesn't qualify as an attack in the sense that you mean.

Best,
Timo


=C2=A0

On Thu, Apr 6, 2017 at 5:11 AM, Bryan Bishop via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrot= e:
On Thu, Apr 6, 2017 at 7:= 02 AM, Luv Khemani via bitcoin-dev <bitcoin-dev@lists.= linuxfoundation.org> wrote:

Could you elaborate on why you consider ASICBOOST to be= an attack? Attack here implies ill-intent by the practitioner=C2=A0towards the networ= k as a primary motivating factor.


See https://www.reddit.com/r/Bitcoin/comments/63otrp= /gregory_maxwell_major_asic_manufacturer_is/dfwcki3/

""&q= uot;
I think tha= t it is an attack is a completely unambiguous technical description of what= it is. If a signature is supposed to resist forgery against 2^128 operatio= ns, but you find a way to do it with 2^80 instead, this is an attack. It is= , perhaps, not a very concerning attack and you may or may not change your = signature scheme to avoid it or may just instead say the scheme has 2^80 se= curity. But there is no doubt that it would be called an attack, especially= if it was not described in the original proposal.

In Bitcoin's Proof of Work= , you are attempting to prove a certain amount of work has been done. This = shortcut significantly reduces the amount of work. It's an attack. Norm= ally it wouldn't be a serious attack-- it would just get appended to th= e defacto definition of what the Bitcoin Proof of work is-- similar to the = signature system just getting restarted as having 2^80 security-- but in it= 's covert form it cannot just be adopted because it blocks many further= improvements (not just segwit, but the vast majority of other proposals), = and additional the licensing restrictions inhibit adoption.

The proposal I posted= does not prevent the technique, only the covert form: That is, it doesn= 9;t even attempt to solve the patented tech eventually will centralize the = system problem. It is narrowly targeted at the interference with upgrades.<= /div>

Taking= a step back-- even ignoring my geeking out about the technical definition = of 'attack' in crypographic contexts, we have a set of issues here = that left addressed will seriously harm the system going forward for the th= e significant monetary benefit of an exploiting party. I think that also sa= tisfies a lay definition of the term: Something someone does, that none one= expected, that makes them money at everyone elses expense.
"""

- Bryan
http://heybryan.org/
1 512 203 0507

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


--001a11352768a278b7054c830da7--