path: root/55/5a03552a18e0c374cd9cb7cf4d580d7eb86ec7

Return-Path: <el33th4x0r@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id B8742D07
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed,  2 Mar 2016 16:56:50 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f41.google.com (mail-wm0-f41.google.com [74.125.82.41])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id A27C879
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed,  2 Mar 2016 16:56:49 +0000 (UTC)
Received: by mail-wm0-f41.google.com with SMTP id n186so95326420wmn.1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 02 Mar 2016 08:56:49 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to; 
	bh=m3zCYPVEqPdLmCNXxMq6Hpsre1LtiqY2BGpoYGVJ7/M=;
	b=c26AKM23h3IFwO+GbJ6Zu69F3AuXCDwDR+flrZADKi1vQ2vTrtaYzDIOIiAXIwauY2
	ZWzf7WN3YwPcmPraynWZKD2pPsXj8ntREVzndm7cNc3+zv6NG1YmMnBI2fCq2e5xOFoo
	Zt1v9/wklXqQGEsl/Az9KBlJ6A41UwQyd7NK5iWC8NHO4n7LofBmGO2/+RCl9VVeN13/
	+mTwLo5QKbX89mhpZcTJ7+YcI412nzRVAr4SEE9M0J9Qk53vCDs5xoHu9X/qP3B6tvkw
	W3BChRn11cZwPMvUK0cWqAULwfgc8cd7ci/LX+XF06vZHniOfM1gWv3tyVGz9STXwRJm
	WTZA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20130820;
	h=x-gm-message-state:mime-version:in-reply-to:references:from:date
	:message-id:subject:to;
	bh=m3zCYPVEqPdLmCNXxMq6Hpsre1LtiqY2BGpoYGVJ7/M=;
	b=nKd9yvQrhtOuZ8j2PKMZ9L/6Y6mEMdU6iGHsiT/xUVf8MnrYjuB4N37UDZl4xF0bqA
	mhB5ijHxM+sAObP+rKBBBz+WRaUxbIZFBCbgWrFMg6HMXODDRGTX5prP4hgk3guTJXfk
	g59jyWYwXKt+eRiUgE3xKJNhFyqNTNZBB4/8hR0lVOIATii/Isgghc1+cw1csuyMdfFN
	22fjYmIzLEVYjVe7n8cut+u0VJKnWv6tM9MC3xpKlp0ObXJ6ZRrMQOeLCS4iyCwF96Zi
	Q3NhyGkdKhzhib5ABYW5ds3ejSSseEweRc/R7ziGzYxGEj3smF+TwzTGAcD4lUBYx4qu
	oDig==
X-Gm-Message-State: AD7BkJInjfKmTCNe/zYLPaMovDZEKi8oDDJa7ye1ComFCp/sano8E/joANMhDAD+C7Fhf83kTULcsaTOo1ATCw==
X-Received: by 10.194.61.131 with SMTP id p3mr26632702wjr.159.1456937808198;
	Wed, 02 Mar 2016 08:56:48 -0800 (PST)
MIME-Version: 1.0
Received: by 10.194.236.66 with HTTP; Wed, 2 Mar 2016 08:56:28 -0800 (PST)
In-Reply-To: <CAAt2M197OWV1euFX5x+9A0K=0tTMamrTbXS=2KWX=ZKyPMyXAQ@mail.gmail.com>
References: <CAPkFh0tx6BJ2=pCamtawa=niPfci7-a6Vs-wFo3rXXx6oks0Jg@mail.gmail.com>
	<CAAt2M197OWV1euFX5x+9A0K=0tTMamrTbXS=2KWX=ZKyPMyXAQ@mail.gmail.com>
From: =?UTF-8?Q?Emin_G=C3=BCn_Sirer?= <el33th4x0r@gmail.com>
Date: Wed, 2 Mar 2016 11:56:28 -0500
Message-ID: <CAPkFh0vbKv3vJBz2=M92u3cx9bQdCFR3dkP=8=o7tPAq+w5Dyg@mail.gmail.com>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=047d7bacb4ee8486fd052d13c470
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,DKIM_VALID_AU,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: Wed, 02 Mar 2016 17:01:35 +0000
Subject: Re: [bitcoin-dev] Bitcoin Guarantees Strong, not Eventual,
	Consistency.
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: Wed, 02 Mar 2016 16:56:50 -0000

--047d7bacb4ee8486fd052d13c470
Content-Type: text/plain; charset=UTF-8

> The entire point of the definition of eventually consistency is that your
> computer system is running continously and DO NOT have a final state, and
> therefore you must be able to describe the behavior when your system either
> may give responses to queries across time that are either perfectly
> consistent *or not* perfectly consistent.
>
This is not the definition of eventual consistency. From
https://en.wikipedia.org/wiki/Eventual_consistency:
Eventual consistency is a consistency model used in distributed computing
to achieve high availability that informally guarantees that, if no new
updates are made to a given data item, eventually all accesses to that item
will return the last updated value.

The actual definition makes it quite clear that a system need not have a
final state to be evaluated for its consistency properties. Almost all
practical database systems execute continuously without a final state.

> And Bitcoin by default *does not* ignore the contents of the last X
> blocks. A Bitcoin node being queried about the current blockchain state
> WILL give inconsistent answers when there's block rearrangements = no
> strong consistency.


One could split hairs here by pedantically defining "Bitcoin by default" --
you could refer to just the reference client code and ignore the shim code
in the app that interfaces with the client -- but that'd drag us into a
fruitless email-list-style discussion from which no one would emerge any
wiser. I'll avoid that, and will instead dryly note that the reference
client's listreceivedbyaddress will return the number of confirmations by
default, and every application will then check the confirmations value to
confirm that it exceeds that application's own omega, while
getbalance,getreceivedbyaddress will take a number of confirmations as an
argument, shielding the app from reorgs of the suffix. That is precisely
the point made in the post.

> Not to mention that your definition ignores the nonzero probability of a
> block rearrangement extending beyond your constant omega.
>
The post covers this case. Technically, there is a difference between 0
probability and epsilon probability -- this is the reason why Nakamoto
Consensus was an exciting breakthrough result; the same reason why
Lamport's results regarding a 3f+1 bound on the Byzantine Generals Problem
do not apply to Nakamoto Consensus; and the same reason it took our paper
(Majority is Not Enough) to show that Nakamoto consensus has a similar 33%
bound as Lamport-style consensus when it comes to tolerating Byzantine
actors.

Practically, however, there is little difference between 0 and a value that
exponentially approximates 0, given that we operate on hardware subject to
random errors. The post makes the case that one can pick an omega such that
the probability of your processor mis-executing your code is larger than
the probability of observing a reorganization.

Bitcoin provides a probabilistic, accumulative probability. Not a perfect
> one.
>
Sometimes, non-technical people get confused about the difference between
very very very small probabilities that approximate 0 and 0. For instance,
some people get very worried about hash collisions, on which Bitcoin relies
for its correctness, whose probability also drops exponentially but is not
exactly 0. Your overall point seems to be an analogous concern that
Bitcoin's exponentially dropping probability of reorganization isn't quite
a "perfect" 0. If so, I agree and the original post made this quite clear.
Though I hope we can avoid that kind of discussion on this particular list.

- egs

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

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><div=
><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.=
8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-st=
yle:solid;padding-left:1ex"><p dir=3D"ltr">The entire point of the definiti=
on of eventually consistency is that your computer system is running contin=
ously and DO NOT have a final state, and therefore you must be able to desc=
ribe the behavior when your system either may give responses to queries acr=
oss time that are either perfectly consistent *or not* perfectly consistent=
.<br></p></blockquote><div>This is not the definition of eventual consisten=
cy. From <a href=3D"https://en.wikipedia.org/wiki/Eventual_consistency" tar=
get=3D"_blank">https://en.wikipedia.org/wiki/Eventual_consistency</a>:</div=
><div>Eventual consistency is a consistency model used in distributed compu=
ting to achieve high availability that informally guarantees that, if no ne=
w updates are made to a given data item, eventually all accesses to that it=
em will return the last updated value.<br></div><div><br></div><div>The act=
ual definition makes it quite clear that a system need not have a final sta=
te to be evaluated for its consistency properties. Almost all practical dat=
abase systems execute continuously without a final state.<br></div><blockqu=
ote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-wid=
th:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-l=
eft:1ex"><p dir=3D"ltr"></p><span style=3D"font-size:12.8px">And Bitcoin by=
 default *does not* ignore the contents of the last X blocks. A Bitcoin nod=
e being queried about the current blockchain state WILL give inconsistent a=
nswers when there&#39;s block rearrangements =3D no strong consistency.=C2=
=A0</span></blockquote><div>=C2=A0</div><div>One could split hairs here by =
pedantically defining &quot;Bitcoin by default&quot; -- you could refer to =
just the reference client code and ignore the shim code in the app that int=
erfaces with the client -- but that&#39;d drag us into a fruitless email-li=
st-style discussion from which no one would emerge any wiser. I&#39;ll avoi=
d that, and will instead dryly note that the reference client&#39;s listrec=
eivedbyaddress will return the number of confirmations by default, and ever=
y application will then check the confirmations value to confirm that it ex=
ceeds that application&#39;s own omega, while getbalance,getreceivedbyaddre=
ss will take a number of confirmations as an argument, shielding the app fr=
om reorgs of the suffix. That is precisely the point made in the post.</div=
><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border=
-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;=
padding-left:1ex"><p dir=3D"ltr">Not to mention that your definition ignore=
s the nonzero probability of a block rearrangement extending beyond your co=
nstant omega.</p></blockquote><div>The post covers this case. Technically, =
there is a difference between 0 probability and epsilon probability -- this=
 is the reason why Nakamoto Consensus was an exciting breakthrough result; =
the same reason why Lamport&#39;s results regarding a 3f+1 bound on the Byz=
antine Generals Problem do not apply to Nakamoto Consensus; and the same re=
ason it took our paper (Majority is Not Enough) to show that Nakamoto conse=
nsus has a similar 33% bound as Lamport-style consensus when it comes to to=
lerating Byzantine actors.=C2=A0</div><div><br></div><div>Practically, howe=
ver, there is little difference between 0 and a value that exponentially ap=
proximates 0, given that we operate on hardware subject to random errors. T=
he post makes the case that one can pick an omega such that the probability=
 of your processor mis-executing your code is larger than the probability o=
f observing a reorganization.</div><div><br></div><div><div class=3D"gmail_=
quote"><div><blockquote class=3D"gmail_quote" style=3D"color:rgb(34,34,34);=
margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,20=
4,204);border-left-style:solid;padding-left:1ex"><p dir=3D"ltr">Bitcoin pro=
vides a probabilistic, accumulative probability. Not a perfect one.</p></bl=
ockquote></div></div></div><div>Sometimes, non-technical people get confuse=
d about the difference between very very very small probabilities that appr=
oximate 0 and 0. For instance, some people get very worried about hash coll=
isions, on which Bitcoin relies for its correctness, whose probability also=
 drops exponentially but is not exactly 0. Your overall point seems to be a=
n analogous concern that Bitcoin&#39;s exponentially dropping probability o=
f reorganization isn&#39;t quite a &quot;perfect&quot; 0. If so, I agree an=
d the original post made this quite clear. Though I hope we can avoid that =
kind of discussion on this particular list.=C2=A0</div><div><br></div><div>=
- egs<br></div><div><br></div></div></div></div>

--047d7bacb4ee8486fd052d13c470--