MIME-Version: 1.0
Sender: stanga@gmail.com
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
Message-ID: <CABT1wWndkSNK5FDbaiYoFZhhBu9FxXhy9qkb_pA7KW6Xqq1nfg@mail.gmail.com>
To: Matt Corallo <lf-lists@mattcorallo.com>
Content-Type: multipart/alternative; boundary=001a113d674493a9f60523e55db4
Cc: Ittay <ittay.eyal@cornell.edu>,
	Ittay via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Bitcoin-NG whitepaper.
Precedence: list

--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--