From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id B8742D07 for ; 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 ; Wed, 2 Mar 2016 16:56:49 +0000 (UTC) Received: by mail-wm0-f41.google.com with SMTP id n186so95326420wmn.1 for ; 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: References: From: =?UTF-8?Q?Emin_G=C3=BCn_Sirer?= Date: Wed, 2 Mar 2016 11:56:28 -0500 Message-ID: To: Bitcoin Dev 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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

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

This is not the definition of eventual consisten= cy. From https://en.wikipedia.org/wiki/Eventual_consistency:
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.

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.

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's block rearrangements =3D no strong consistency.=C2= =A0
=C2=A0
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 int= erfaces with the client -- but that'd drag us into a fruitless email-li= st-style discussion from which no one would emerge any wiser. I'll avoi= d that, and will instead dryly note that the reference client'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'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.

Not to mention that your definition ignore= s the nonzero probability of a block rearrangement extending beyond your co= nstant 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 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

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.

Bitcoin pro= vides a probabilistic, accumulative probability. Not a perfect one.

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's exponentially dropping probability o= f reorganization isn't quite a "perfect" 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

= - egs

--047d7bacb4ee8486fd052d13c470--