path: root/62/92f7cc6844baff657aa2dc3f053061fa90cc5f

Return-Path: <stanga@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 9806E90
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri,  6 Nov 2015 20:48:30 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-oi0-f51.google.com (mail-oi0-f51.google.com
	[209.85.218.51])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9DCED138
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri,  6 Nov 2015 20:48:28 +0000 (UTC)
Received: by oies6 with SMTP id s6so30054266oie.1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri, 06 Nov 2015 12:48:28 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=mime-version:sender:in-reply-to:references:from:date:message-id
	:subject:to:cc:content-type;
	bh=s7Vud2Ht4oLMBOdOfsHzmP7YvXtsz9eX02SlKCo7lg4=;
	b=oFWFcyPyGuv35SCXZ1KeSCbqLeFNc8HCpJTkvFTSGMF3mfECxqmF5Jlk2Ujy7ezLJi
	kIlujhMsWBwREjxuYcupo8xzq3lgdIlgUc1v1IRnENJKIDPZWbgqi13rMrO3XYQtA+Xn
	xVwRIWRnXb5U1+kG4Y94mnhSSoLeEJoC2HdUjAEL3Ih/asT3cL9bEZUMYJKuKZVo7dHl
	voSKfDI1N2NFaGZYIlFY80rHIhgo9Z5EQ1mIDwalYQJlAOYkvSqABnfnuiD5uXX1MTQw
	s57k03TckfOJmfh7Au+w42d/UtlntVm3D83oZJ5btt1M7jz/ACSRojUyFEZCqHxiiGeZ
	QuwA==
X-Received: by 10.202.68.8 with SMTP id r8mr9312164oia.116.1446842907992; Fri,
	06 Nov 2015 12:48:27 -0800 (PST)
MIME-Version: 1.0
Sender: stanga@gmail.com
Received: by 10.182.104.164 with HTTP; Fri, 6 Nov 2015 12:48:08 -0800 (PST)
In-Reply-To: <56302E34.7070906@mattcorallo.com>
References: <CAPkFh0viwmkUvjo4Qj50TNnkA5kG3z-3dLGExjkmDacE4E49Ow@mail.gmail.com>
	<CABaSBaxWAsEG71FTy4SrVu94BXokeozmJ80tjsNU8ERpTfFaFA@mail.gmail.com>
	<CABT1wW=xqShMGU0+eDiNyNkr-77fQ_HnyKL87C6iGL-xq8BYVw@mail.gmail.com>
	<28CC699B-4DA8-4472-A795-9505418C688A@mattcorallo.com>
	<CABT1wWm0QXjGAXgrBMT7w+25kcsEJnP8JZ5RSpuk3aefX45+wQ@mail.gmail.com>
	<56302E34.7070906@mattcorallo.com>
From: Ittay <ittay.eyal@cornell.edu>
Date: Fri, 6 Nov 2015 15:48:08 -0500
X-Google-Sender-Auth: J-sgzIeh9k24L-budv-K7wZbk9c
Message-ID: <CABT1wWndkSNK5FDbaiYoFZhhBu9FxXhy9qkb_pA7KW6Xqq1nfg@mail.gmail.com>
To: Matt Corallo <lf-lists@mattcorallo.com>
Content-Type: multipart/alternative; boundary=001a113d674493a9f60523e55db4
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,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
X-Mailman-Approved-At: Fri, 06 Nov 2015 21:00:19 +0000
Cc: Ittay <ittay.eyal@cornell.edu>,
	Ittay via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Bitcoin-NG whitepaper.
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development 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: Fri, 06 Nov 2015 20:48:30 -0000

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

On Tue, Oct 27, 2015 at 10:08 PM, Matt Corallo <lf-lists@mattcorallo.com>
wrote:

> Oops, just realized I never responded to this...
>
> On 10/15/15 15:09, Ittay wrote:
> > Thanks, Matt. Response inline.
> >
> > On Wed, Oct 14, 2015 at 2:57 PM, Matt Corallo <lf-lists@mattcorallo.com
> > <mailto:lf-lists@mattcorallo.com>> wrote:
> >
> >     That conversation missed a second issue. Namely that there is no way
> >     to punish people if there is a double spend in a micro block that
> >     happens in key block which reorg'd away the first transaction. eg
> >     one miner mines a transaction in a micro block, another miner
> >     (either by not having seen the first yet, or being malicious -
> >     potentially the same miner) mines a key block which reorgs away the
> >     first micro block and then, in their first micro block, mines a
> >     double spend. This can happen at any time, so you end up having to
> >     fall back to regular full blocks for confirmation times :(.
> >
> >
> > If NG is to be used efficiently, microblocks are going to be very
> > frequent, and so such forks should occur at almost every key-block
> > publication. Short reorgs as you described are the norm. A user should
> > wait before accepting a transaction to make sure there was no key-block
> > she missed. The wait time is chosen according to the network propagation
> > delay (+as much slack as the user feels necessary). This is similar to
> > the situation in Bitcoin when you receive a block. To be confident that
> > you have one confirmation you should wait for the propagation time of
> > the network to make sure there is no branch you missed.
>
> I think you're overstating how short the wait times can be. They need to
> be much longer than the network propagation delay.
>
> > As for the malicious case: the attacker has to win the key-block, have
> > the to-be-inverted transaction in the previous epoch, and withhold his
> > key-block for a while. That being said, indeed our fraud proof scheme
> > doesn't catch such an event, as it is indistinguishable from benign
> > behavior.
>
> The attacker does not need to withold their keyblock at all. All the
> attacker does is, for every transaction they ever send, after it is
> included in a microblock, set their hashpower to start mining a keyblock
> immediately prior to this microblock. When they find a keyblock, they
> immediately announce it and start creating microblocks, the first of
> which double-spends the previous transaction. If they dont win the key
> block, oh well, their payment went through normally and they couldn't
> double-spend.
>
> In chatting with Glenn about this, we roughly agreed that the
> confirmation time for microblocks possibly doesn't need to be a full
> key-block, but it needs to be a reasonable period after which such an
> attacker would lose more in fees than the value of their double-spend
> (ie because the key-block afterwards gets 20% more in fees than the
> key-block before hand). In any case, the game theory here starts to get
> rather complicated and it doesn't make me want to suggest accepting
> microblocks as confirmations is safe.
>

Yes, an attacker can continuously try to do this, losing all (and only)
fees.
They will succeed every time they mine a block after the to-be-double-spent
transaction is placed by the current leader. So a microblock + delay is
stronger
than a zero-confirmation transaction, but not as strong as a first-block
confirmation.

A game theory analysis is indeed difficult here, mainly since the
assumptions
are not entirely clear. We are working towards this, starting with
formalizing
the attacker's incentive structure.

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

<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Tue, Oct 27, 2015 at 10:08 PM, Matt Corallo <span dir=3D"ltr">&lt;<a=
 href=3D"mailto:lf-lists@mattcorallo.com" target=3D"_blank">lf-lists@mattco=
rallo.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(20=
4,204,204);border-left-style:solid;padding-left:1ex">Oops, just realized I =
never responded to this...<br>
<span class=3D""><br>
On 10/15/15 15:09, Ittay wrote:<br>
&gt; Thanks, Matt. Response inline.<br>
&gt;<br>
&gt; On Wed, Oct 14, 2015 at 2:57 PM, Matt Corallo &lt;<a href=3D"mailto:lf=
-lists@mattcorallo.com">lf-lists@mattcorallo.com</a><br>
</span><span class=3D"">&gt; &lt;mailto:<a href=3D"mailto:lf-lists@mattcora=
llo.com">lf-lists@mattcorallo.com</a>&gt;&gt; wrote:<br>
&gt;<br>
&gt;=C2=A0 =C2=A0 =C2=A0That conversation missed a second issue. Namely tha=
t there is no way<br>
&gt;=C2=A0 =C2=A0 =C2=A0to punish people if there is a double spend in a mi=
cro block that<br>
&gt;=C2=A0 =C2=A0 =C2=A0happens in key block which reorg&#39;d away the fir=
st transaction. eg<br>
&gt;=C2=A0 =C2=A0 =C2=A0one miner mines a transaction in a micro block, ano=
ther miner<br>
&gt;=C2=A0 =C2=A0 =C2=A0(either by not having seen the first yet, or being =
malicious -<br>
&gt;=C2=A0 =C2=A0 =C2=A0potentially the same miner) mines a key block which=
 reorgs away the<br>
&gt;=C2=A0 =C2=A0 =C2=A0first micro block and then, in their first micro bl=
ock, mines a<br>
&gt;=C2=A0 =C2=A0 =C2=A0double spend. This can happen at any time, so you e=
nd up having to<br>
&gt;=C2=A0 =C2=A0 =C2=A0fall back to regular full blocks for confirmation t=
imes :(.<br>
&gt;<br>
&gt;<br>
&gt; If NG is to be used efficiently, microblocks are going to be very<br>
&gt; frequent, and so such forks should occur at almost every key-block<br>
&gt; publication. Short reorgs as you described are the norm. A user should=
<br>
&gt; wait before accepting a transaction to make sure there was no key-bloc=
k<br>
&gt; she missed. The wait time is chosen according to the network propagati=
on<br>
&gt; delay (+as much slack as the user feels necessary). This is similar to=
<br>
&gt; the situation in Bitcoin when you receive a block. To be confident tha=
t<br>
&gt; you have one confirmation you should wait for the propagation time of<=
br>
&gt; the network to make sure there is no branch you missed.<br>
<br>
</span>I think you&#39;re overstating how short the wait times can be. They=
 need to<br>
be much longer than the network propagation delay.<br>
<span class=3D""><br>
&gt; As for the malicious case: the attacker has to win the key-block, have=
<br>
&gt; the to-be-inverted transaction in the previous epoch, and withhold his=
<br>
&gt; key-block for a while. That being said, indeed our fraud proof scheme<=
br>
&gt; doesn&#39;t catch such an event, as it is indistinguishable from benig=
n<br>
&gt; behavior.<br>
<br>
</span>The attacker does not need to withold their keyblock at all. All the=
<br>
attacker does is, for every transaction they ever send, after it is<br>
included in a microblock, set their hashpower to start mining a keyblock<br=
>
immediately prior to this microblock. When they find a keyblock, they<br>
immediately announce it and start creating microblocks, the first of<br>
which double-spends the previous transaction. If they dont win the key<br>
block, oh well, their payment went through normally and they couldn&#39;t<b=
r>
double-spend.<br>
<br>
In chatting with Glenn about this, we roughly agreed that the<br>
confirmation time for microblocks possibly doesn&#39;t need to be a full<br=
>
key-block, but it needs to be a reasonable period after which such an<br>
attacker would lose more in fees than the value of their double-spend<br>
(ie because the key-block afterwards gets 20% more in fees than the<br>
key-block before hand). In any case, the game theory here starts to get<br>
rather complicated and it doesn&#39;t make me want to suggest accepting<br>
microblocks as confirmations is safe.<br></blockquote><div><br></div><div s=
tyle=3D""><div style=3D""><span style=3D"font-size:12.8px">Yes, an attacker=
 can continuously try to do this, losing all (and only) fees.=C2=A0</span><=
/div><div style=3D""><span style=3D"font-size:12.8px">They will succeed eve=
ry time they mine a block after the to-be-double-spent=C2=A0</span></div><d=
iv style=3D""><span style=3D"font-size:12.8px">transaction is placed by the=
 current leader. So a microblock + delay is stronger=C2=A0</span></div><div=
 style=3D""><span style=3D"font-size:12.8px">than a zero-confirmation trans=
action, but not as strong as a first-block=C2=A0</span></div><div style=3D"=
"><span style=3D"font-size:12.8px">confirmation.=C2=A0</span></div><div sty=
le=3D""><span style=3D"font-size:12.8px"><br></span></div><div style=3D""><=
span style=3D"font-size:12.8px">A game theory analysis is indeed difficult =
here, mainly since the assumptions=C2=A0</span></div><div style=3D""><span =
style=3D"font-size:12.8px">are not entirely clear. We are working towards t=
his, starting with formalizing=C2=A0</span></div><div style=3D""><span styl=
e=3D"font-size:12.8px">the attacker&#39;s incentive structure.=C2=A0</span>=
</div><div style=3D"font-size:12.8px"><br></div></div></div></div></div>

--001a113d674493a9f60523e55db4--