path: root/13/1f4c97bc21465737653c7e880a3c145ed459b9

Return-Path: <timo.t.hanke@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 9E692BE0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>;
	Thu,  6 Apr 2017 17:43:58 +0000 (UTC)
Received: by mail-vk0-f66.google.com with SMTP id d188so6214228vka.3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>
	(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 <bitcoin-dev@lists.linuxfoundation.org>;
	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: <CABaSBawbufi0p89OqRb57UoH51NxZxnZ7EcsJcQYAA8Tq3Qdfg@mail.gmail.com>
References: <CAAS2fgR84898xD0nyq7ykJnB7qkdoCJYnFg6z5WZEUu0+-=mMA@mail.gmail.com>
	<SINPR04MB19493BB6268FBC75F107C2BAC20D0@SINPR04MB1949.apcprd04.prod.outlook.com>
	<CABaSBawbufi0p89OqRb57UoH51NxZxnZ7EcsJcQYAA8Tq3Qdfg@mail.gmail.com>
From: Timo Hanke <timo.hanke@web.de>
Date: Thu, 6 Apr 2017 10:43:56 -0700
X-Gmail-Original-Message-ID: <CAH6h1Lt=PKYxw-cWWeQGaTyLh2KAqU-o7eY9_WQbpanHJBxB7A@mail.gmail.com>
Message-ID: <CAH6h1Lt=PKYxw-cWWeQGaTyLh2KAqU-o7eY9_WQbpanHJBxB7A@mail.gmail.com>
To: Bryan Bishop <kanzure@gmail.com>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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 <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: 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

<div dir=3D"ltr">Bryan,<div><br></div><div>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&#39;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 &quot;fee=
ling&quot; it, rather than having to do the intended 10,000 attempts. That&=
#39;s the kind of thing that would be called an &quot;attack&quot;.</div><d=
iv><br></div><div>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&#39;t qualify as an attack in the sense that you mean.</d=
iv><div><br></div><div>Best,</div><div>Timo</div><div><br></div><div><br></=
div><div>=C2=A0</div></div><div class=3D"gmail_extra"><br><div class=3D"gma=
il_quote">On Thu, Apr 6, 2017 at 5:11 AM, Bryan Bishop via bitcoin-dev <spa=
n dir=3D"ltr">&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" =
target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</span> wrot=
e:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-l=
eft:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_e=
xtra"><span class=3D""><div class=3D"gmail_quote">On Thu, Apr 6, 2017 at 7:=
02 AM, Luv Khemani via bitcoin-dev <span dir=3D"ltr">&lt;<a href=3D"mailto:=
bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.=
<wbr>linuxfoundation.org</a>&gt;</span> wrote:<br><blockquote class=3D"gmai=
l_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,20=
4,204);padding-left:1ex"><p><span style=3D"font-family:calibri,arial,helvet=
ica,sans-serif,&quot;apple color emoji&quot;,&quot;segoe ui emoji&quot;,not=
ocoloremoji,&quot;segoe ui symbol&quot;,&quot;android emoji&quot;,emojisymb=
ols;font-size:16px">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.</span><br>
</p>
<p></p></blockquote></div><br></span>See <a href=3D"https://www.reddit.com/=
r/Bitcoin/comments/63otrp/gregory_maxwell_major_asic_manufacturer_is/dfwcki=
3/" target=3D"_blank">https://www.reddit.com/r/<wbr>Bitcoin/comments/63otrp=
/<wbr>gregory_maxwell_major_asic_<wbr>manufacturer_is/dfwcki3/</a></div><di=
v class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">&quot;&quot;&q=
uot;</div><div class=3D"gmail_extra"><div class=3D"gmail_extra">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.</div><div class=3D"gmail=
_extra"><br></div><div class=3D"gmail_extra">In Bitcoin&#39;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&#39;s an attack. Norm=
ally it wouldn&#39;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=
&#39;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.</div><div class=
=3D"gmail_extra"><br></div><div class=3D"gmail_extra">The proposal I posted=
 does not prevent the technique, only the covert form: That is, it doesn&#3=
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><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">Taking=
 a step back-- even ignoring my geeking out about the technical definition =
of &#39;attack&#39; 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.</div></div><div=
 class=3D"gmail_extra">&quot;&quot;&quot;<br><div><br></div><div class=3D"m=
_-8059209376853387444gmail_signature">- Bryan<br><a href=3D"http://heybryan=
.org/" target=3D"_blank">http://heybryan.org/</a><br><a href=3D"tel:(512)%2=
0203-0507" value=3D"+15122030507" target=3D"_blank">1 512 203 0507</a></div=
>
</div></div>
<br>______________________________<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
<wbr>linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org=
/mailman/listinfo/bitcoin-<wbr>dev</a><br>
<br></blockquote></div><br></div>

--001a11352768a278b7054c830da7--