Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 9806E90 for ; 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 ; Fri, 6 Nov 2015 20:48:28 +0000 (UTC) Received: by oies6 with SMTP id s6so30054266oie.1 for ; 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: <28CC699B-4DA8-4472-A795-9505418C688A@mattcorallo.com> <56302E34.7070906@mattcorallo.com> From: Ittay Date: Fri, 6 Nov 2015 15:48:08 -0500 X-Google-Sender-Auth: J-sgzIeh9k24L-budv-K7wZbk9c Message-ID: To: Matt Corallo 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 via bitcoin-dev 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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 > > 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


On Tue, Oct 27, 2015 at 10:08 PM, Matt Corallo <lf-lists@mattco= rallo.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:
>
>=C2=A0 =C2=A0 =C2=A0That conversation missed a second issue. Namely tha= t there is no way
>=C2=A0 =C2=A0 =C2=A0to punish people if there is a double spend in a mi= cro block that
>=C2=A0 =C2=A0 =C2=A0happens in key block which reorg'd away the fir= st transaction. eg
>=C2=A0 =C2=A0 =C2=A0one miner mines a transaction in a micro block, ano= ther miner
>=C2=A0 =C2=A0 =C2=A0(either by not having seen the first yet, or being = malicious -
>=C2=A0 =C2=A0 =C2=A0potentially the same miner) mines a key block which= reorgs away the
>=C2=A0 =C2=A0 =C2=A0first micro block and then, in their first micro bl= ock, mines a
>=C2=A0 =C2=A0 =C2=A0double spend. This can happen at any time, so you e= nd up having to
>=C2=A0 =C2=A0 =C2=A0fall back to regular full blocks for confirmation t= imes :(.
>
>
> 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-bloc= k
> she missed. The wait time is chosen according to the network propagati= on
> 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 tha= t
> you have one confirmation you should wait for the propagation time of<= br> > 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<= br> > doesn't catch such an event, as it is indistinguishable from benig= n
> 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.=C2=A0<= /div>
They will succeed eve= ry time they mine a block after the to-be-double-spent=C2=A0
transaction is placed by the= current leader. So a microblock + delay is stronger=C2=A0
than a zero-confirmation trans= action, but not as strong as a first-block=C2=A0
confirmation.=C2=A0

<= span style=3D"font-size:12.8px">A game theory analysis is indeed difficult = here, mainly since the assumptions=C2=A0
are not entirely clear. We are working towards t= his, starting with formalizing=C2=A0
the attacker's incentive structure.=C2=A0=

--001a113d674493a9f60523e55db4--