Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 3CFFFC002D for ; Mon, 17 Oct 2022 19:02:17 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 0231C825CA for ; Mon, 17 Oct 2022 19:02:17 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 0231C825CA Authentication-Results: smtp1.osuosl.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20210112 header.b=E4DigfJ6 X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.097 X-Spam-Level: X-Spam-Status: No, score=-2.097 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URI_DOTEDU=0.001] autolearn=ham autolearn_force=no Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id VJ6JMf_JFvIx for ; Mon, 17 Oct 2022 19:02:15 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 03B3181B72 Received: from mail-yw1-x1130.google.com (mail-yw1-x1130.google.com [IPv6:2607:f8b0:4864:20::1130]) by smtp1.osuosl.org (Postfix) with ESMTPS id 03B3181B72 for ; Mon, 17 Oct 2022 19:02:14 +0000 (UTC) Received: by mail-yw1-x1130.google.com with SMTP id 00721157ae682-333a4a5d495so116525217b3.10 for ; Mon, 17 Oct 2022 12:02:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=gYLMjbRngFOM6ibv6eUVfyS4C/A2g6MngZCoU5gLWM8=; b=E4DigfJ6aNyij5M1ieTrLy1xeujN1XoTXIlJzZzz35gFoFWzx0SY9sll1ID4UgztKO pijjebc3s8/oXwmnQ3lMvFuyYbQ03mVwer4VrrnpBDDIb2rnl7PsG+HE2vQTi22X3mqt f/0PU71WOubkuMjHBsPcvQnUcnECUlssg71nsiofbzYWAihda9wi2AqqzL9iBHoO0sXx CHfg4rpw2Ny500qFXQvzlXHGzL9GZ6RKVfQf9MiKufSHJkb2j+yf4gLCK2p1qVbKfDg+ mWcVhefZdTILEf/M9tFyKERqORY337nZJgXarzhq8iEs5kS4ZZ0jAaizw15SuuIzusgV 2Slw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=gYLMjbRngFOM6ibv6eUVfyS4C/A2g6MngZCoU5gLWM8=; b=vqHdSnn+vl4ktAx6ictcyjqRvYDKWrn4qIh7TgWU0Lro1Z13AUcq1Q+DmE2btbsyIO +hNqE7rZHQsF/BH9MHzQBDIS4w6JrB82FgNbQCvEKU7PqULD5wzbiTHCODwiMXExhr4H 7nZaffIrs56xxSGB+3+t3orkB+Znm8urHzDtgdgDFBOoR+tfjqXumlxHrtzKPnNF9IIU QKlzcMQIAIHOUO1rsSPyjhro67xTwC9iC+mCRPdf62OnVIQB35u3lsdoSzeVF6WnOMcf IwcZwBooFFKlnTjesYFlNB4ipXuRTW8VU2b5NQMFNwl0IUiwspxKb+/RaTIIXhYgWtqn 4E0g== X-Gm-Message-State: ACrzQf02GlSH/5IEoLSYz+DmO4JUJQtRzkgcSFSWH7km7EYo9PfB2qfL fBbl5i5N90rTDxbWzv9KfHY01hV5jgQ8DBMoyn80OdPgFFw= X-Google-Smtp-Source: AMsMyM6lIvK53bv5YVV7yYi8GDIdTGxVIC7M5O/kMxd1EkNykkjAmf0zpECPsb5WzbyKN4FPRyt10IEu5AI3CrpZOwY= X-Received: by 2002:a81:6c92:0:b0:35b:fcb4:b68c with SMTP id h140-20020a816c92000000b0035bfcb4b68cmr10647042ywc.490.1666033333763; Mon, 17 Oct 2022 12:02:13 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Jeremy Rubin Date: Mon, 17 Oct 2022 15:02:01 -0400 Message-ID: To: "Russell O'Connor" Content-Type: multipart/alternative; boundary="0000000000000b03f805eb3f9dc3" Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Does Bitcoin require or have an honest majority or a rational one? (re rbf) X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 17 Oct 2022 19:02:17 -0000 --0000000000000b03f805eb3f9dc3 Content-Type: text/plain; charset="UTF-8" Good points, Russell. I think maybe for that particular property, one can partition the types of rules one can put into the "honest rules" without compromising the system. For example, your "keys deleted" property is one that is surely bad, but it can be broken down into a many different buckets, such as: 1) Many Keys deleted one time at the start, all parties seem to have an exogenous interest in not having the keys, as well as an endogenous one (e.g., trusted setup ceremonies for ZCash, all parties seem to love privacy, but also if anyone thinks you have your key maybe they rubber hose you) 2) Keys should be deleted, but only "in play" for some amount of time (Bitcoin NG maybe, statechains after the coin does a withdrawal, PoS with checkpoints) 3) "Keys" should be deleted, but can only cause mild or local harms / resolvable (Lightning, both eltoo and traditional, old transactions are "Keys") 4) Keys must be deleted for all time (proof of work if done as leader election In particular, I think the honest behavior assumptions are OK as long as they are reasonably time bounded and observable. For example, in transaction selection, assuming "honest behavior" may be acceptable because if the property is not true, it doesn't fundamentally brick the system or cause mass outage, but it does cause an annoyance and is observable. Further, agents may have a rationalization for following the honest policy even above their pointwise interest in profit maximizing, if they think it makes their overall participation more valuable. This is because it is an infinite game and not finite, the most effective strategies aren't always doing to be next-step profit maximizing (for those new to these concepts, http://www.econ.uiuc.edu/~hrtdmrt2/Teaching/GT_2015_19/L12.pdf is a decent primer). The example of deleting keys is interesting, because you don't need to make your defection observable. But for transaction selection, it absolutely is. Ultimately, I think the reason why (some) systems do the cop-out of "honest majority rules" --> "secure outcome" is because of a belief that there is an "existential unknown proof" that there is an infinite game that can be described where this should be the dominant strategy for all players, whether defined or not. However, one must be incredibly careful with such assumptions of an unknown existential game to which that is the dominant strategy to not abuse them to ex-falso-quod-libet themselves into a corner (Bertrand Russel is the Pope) if such a game does not actually exist. It's obviously much better to actually prove the incentive compatibility against an explicit game with explicitly stated assumptions for this reason (can include exogenous details like "wanting number-go-up", "have a 5 year hardware investment", or "belief that 0conf working required for adoption"). I (somewhat) suspect that things like the 0Conf safety assumptions are in this category where one must be careful, because I think there might not be a game where they are secure, so it leads to being able to prove false. But I also understand why others might think such a game would exist, so therein the debate. Best, Jeremy -- @JeremyRubin On Mon, Oct 17, 2022 at 11:51 AM Russell O'Connor wrote: > From my limited academic interactions, people generally take the "honest" > to mean following the rules (regardless of how bad it is for you to follow > those rules). This has in turn led to some blockchain designs based on > their own absurd set of rules, and simply waiving away their issues by > stipulating their own honest majority or supermajority requirement. For > example, a proof of stake blockchain might require as a rule that users > securely delete their signing keys after a period of time, and prove their > blockchain secure under these rules. They then argue that so long as the > "honest" majority follows this rule, then there is no risk of > reorganization. If enough users don't delete their signing keys, well > their honest majority assumption is violated, so anything goes. > > The thing is that it is most certainly in each user's interest to *not* > delete their signing keys. Each user has strictly more power and options > available by keeping their keys and not deleting them. This rule violation > is undetectable, at least until it is too late and a coalition decides to > try to collaborate for a reorg to their advantage. > > It is not reasonable to build a distributed pseudonymous system built on > arbitrary rules and then simply define your system to be secure by fiat. > Users need an incentive to follow the rules of the system or it just won't > work. In particular, the rules ought to form a Nash Equilibrium, and this > is violated by, for example, a requirement that users delete their signing > keys. If Bitcoin relied on users acting against their own interest to > function, I doubt Bitcoin would be in operation today. Certainly I would > have no interest in it. > > While it doesn't really matter, I do believe Satoshi was also aware that > the rules cannot just be arbitrary, with no incentive to follow them. > After all, he did note that it was designed to be in the miner's self > interest to build upon the longest (most work) chain, even if that point > ended up being rather involved. That is to say, I don't think that an > "honest" (i.e rule following) majority is meant to be taken as an > assumption, rather it is something that ought to be a consequence of the > design. > > Anyhow, the above is simply a comment on "honest majority", and I'm not > trying to make a specific claim about RBF here, though I do have my > opinions and I do see how it is related. > > On Sun, Oct 16, 2022 at 1:36 PM Jeremy Rubin via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > >> The Bitcoin white paper says: >> >> The proof-of-work also solves the problem of determining representation >> in majority decision >> making. If the majority were based on one-IP-address-one-vote, it could >> be subverted by anyone >> able to allocate many IPs. Proof-of-work is essentially one-CPU-one-vote. >> The majority >> decision is represented by the longest chain, which has the greatest >> proof-of-work effort invested >> in it. If a majority of CPU power is controlled by honest nodes, the >> honest chain will grow the >> fastest and outpace any competing chains. To modify a past block, an >> attacker would have to >> redo the proof-of-work of the block and all blocks after it and then >> catch up with and surpass the >> work of the honest nodes. We will show later that the probability of a >> slower attacker catching up >> diminishes exponentially as subsequent blocks are added. >> >> >> This, Satoshi (who doesn't really matter anyways I guess?) claimed that >> for Bitcoin to function properly you need a majority honest nodes. >> >> There are multiple behaviors one can describe as honest, and economically >> rational or optimizing is not necessarily rational. >> >> For example, if I run a shop that takes rain checks, but I sell an item >> to a higher bidder who didn't have a hold on the item, that is not honest, >> but it may be selfish profit maximizing. >> >> Satoshi said an honest majority is required for the chain to be extended. >> Honest is not really defined though. Honesty, in my definition, is that you >> follow a pre specified rule, rational or not. >> >> It seems a lot of the RBF controversy is that Protocol developers have >> aspired to make the honest behavior also be the rational behavior. This is >> maybe a good idea because, in theory, if the honest behavior is rational >> then we can make a weaker assumption of selfishness maximizing a parameter. >> >> However, Satoshi did not particularly bound what aspects of honesty are >> important for the network, because there isn't a spec defining exactly what >> is honest or not. And also as soon as people are honest, you can rely on >> that assumption for good effect. >> >> And sometimes, defining an honest behavior can be creating a higher >> utility system because most people are "law abiding citizens" who might not >> be short term rational. For example, one might expect that miners would be >> interested in making sure lightning closes are "accurate" because >> increasing the utility of lightning is good for Bitcoin, even if it is >> irrational. >> >> It seems that the NoRBF crowd want to rely on an honest majority >> assumption where the honest behavior is not doing replacement if not >> requested. This is really not much different than trying to close lightning >> channels "the right way". >> >> However, where it may be different, is that even in the presence of >> honest majority, the safety of 0conf isn't assured given the potential of >> race conditions in the mempool. Therefore it's not clear to me that 0conf >> working well is something you can drive from the Honest Majority Assumption >> (where honest includes first seen). >> >> >> Overall, it might be nice to more tightly document what bitcoins >> assumptions are in practice and what those assumptions do in terms of >> properties of Bitcoin, as well as pathways to weakening the assumptions >> without compromising the behaviors users expect the network to have. An >> "extended white paper" if you will. >> >> >> It's somewhat clear to me that we shouldn't weaken assumptions that only >> seem local to one subsystem of Bitcoin if they end up destabilizing another >> system. In particular, things that decrease "transaction utility" for end >> users decrease the demand for transactions which hurts the fee market's >> longer term viability, even if we feel good about making an honest policy >> assumption into a self interested policy assumption. >> >> A last reflection is that Bitcoin is specified with an honest majority >> assumption, but also has a rational dishonest minority assumption over both >> endogenous (rewards) and exogenous (electricity) costs. Satoshi did not >> suggest, at least as I read it, that Bitcoin works with an rational >> majority assumption. (If anyone thinks these three are similar properties >> you can make some trivial counterexamples) >> >> >> Cheers, >> >> Jeremy >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> > --0000000000000b03f805eb3f9dc3 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Good points, Russell.

I think maybe for that particular property, one can = partition the types of rules one can put into the "honest rules" = without compromising the system.

=
For example, your "keys deleted= " property is one that is surely bad, but it can be broken down into a= many different buckets, such as:
<= br>
1) Many Keys deleted one time at = the start, all parties seem to have an exogenous interest in not having the= keys, as well as an endogenous one (e.g., trusted setup ceremonies for ZCa= sh, all parties seem to love privacy, but also if anyone thinks you have yo= ur key maybe they rubber hose you)
2= ) Keys should be deleted, but only "in play" for some amount of t= ime (Bitcoin NG maybe, statechains after the coin does a withdrawal, PoS wi= th checkpoints)
3) "Keys" s= hould be deleted, but can only cause mild or local harms / resolvable (Ligh= tning, both eltoo and traditional, old transactions are "Keys")
4) Keys must be deleted for all time (= proof of work if done as leader election=C2=A0

In particular, I think= the honest behavior assumptions are OK as long as they are reasonably time= bounded and observable. For example, in transaction selection, assuming &q= uot;honest behavior" may be acceptable because if the property is not = true, it doesn't fundamentally brick the system or cause mass outage, b= ut it does cause an annoyance and is observable. Further, agents may have a= rationalization for following the honest policy even above their pointwise= interest in profit maximizing, if they think it makes their overall partic= ipation more valuable. This is because it is an infinite game and not finit= e, the most effective strategies aren't always doing to be next-step pr= ofit maximizing (for those new to these concepts,=C2=A0http://www.econ.uiuc= .edu/~hrtdmrt2/Teaching/GT_2015_19/L12.pdf is a decent primer). The exa= mple of deleting keys is interesting, because you don't need to make yo= ur defection observable. But for transaction selection, it absolutely is.= =C2=A0


Ultimately, I think= the reason why (some) systems do the cop-out of "honest majority rule= s" --> "secure outcome" is because of a belief that there= is an "existential unknown proof" that there is an infinite game= that can be described where this should be the dominant strategy for all p= layers, whether defined or not. However, one must be incredibly careful wit= h such assumptions of an unknown existential game to which that is the domi= nant strategy to not abuse them to ex-falso-quod-libet themselves into a co= rner (Bertrand Russel is the Pope) if such a game does not actually exist. = It's obviously much better to actually prove the incentive compatibilit= y against an explicit game with explicitly stated assumptions for this reas= on (can include exogenous details like "wanting number-go-up", &q= uot;have a=C2=A05=C2=A0year hardware investment", or "belief that= 0conf working required for adoption").

I (somewhat) suspect tha= t things like the 0Conf safety assumptions are in this category where one m= ust be careful, because I think there might not be a game where they are se= cure, so it leads to being able to prove false. But I also understand why o= thers might think such a game would exist, so therein the debate.

B= est,

Jeremy

On Mon, Oct 17, 2022 at 11:51 AM Russell O'Connor <roconnor@blockstream.com> wrote= :
From my limited academic = interactions, people generally take the "honest" to mean followin= g the rules (regardless of how bad it is for you to follow those rules).=C2= =A0 This has in turn led to some blockchain designs based on their own absu= rd set of rules, and simply waiving away their issues by stipulating their = own honest majority or supermajority requirement.=C2=A0 For example, a proo= f of stake blockchain might require as a rule that users securely delete th= eir signing keys after a period of time, and prove their blockchain secure = under these rules.=C2=A0 They then argue that so long as the "honest&q= uot; majority follows this rule, then there is no risk of reorganization.= =C2=A0 If enough users don't delete their signing keys, well their hone= st majority assumption is violated, so anything goes.

<= div>The thing is that it is most certainly in each user's interest to *= not* delete their signing keys.=C2=A0=C2=A0 Each user has strictly more pow= er and options available by keeping their keys and not deleting them.=C2=A0= This rule violation is undetectable, at least until it is too late and a c= oalition decides to try to collaborate for a reorg to their advantage.

It is not reasonable to build a distributed pseudonymo= us system built on arbitrary rules and then simply define your system to be= secure by fiat.=C2=A0 Users need an incentive to follow the rules of the s= ystem or it just won't work.=C2=A0 In particular, the rules ought to fo= rm a Nash Equilibrium, and this is violated by, for example, a requirement = that users delete their signing keys.=C2=A0 If Bitcoin relied on users acti= ng against their own interest to function, I doubt Bitcoin would be in oper= ation today.=C2=A0 Certainly I would have no interest in it.

=
While it doesn't really matter, I do believe Satoshi was als= o aware that the rules cannot just be arbitrary, with no incentive to follo= w them.=C2=A0 After all, he did note that it was designed to be in the mine= r's self interest to build upon the longest (most work) chain, even if = that point ended up being rather involved.=C2=A0 That is to say, I don'= t think that an "honest" (i.e rule following) majority is meant t= o be taken as an assumption, rather it is something that ought to be a cons= equence of the design.

Anyhow, the above is si= mply a comment on "honest majority", and I'm not trying to ma= ke a specific claim about RBF here, though I do have my opinions and I do s= ee how it is related.

On Sun, Oct 16, 2022 at 1:36 PM Jeremy Rubin= via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
The Bitcoin wh= ite paper says:=C2=A0

The proof-of-work al= so solves the problem of determining representation in majority decision
making. If the majority were based on one-IP-address-one-= vote, it could be subverted by anyone
able to allocate many IPs. Proof-of-work is essenti= ally one-CPU-one-vote. The majority
decision is represented by the longest chain, which= has the greatest proof-of-work effort invested
in it. If a majority of CPU power is controlled by = honest nodes, the honest chain will grow the
fastest and outpace any competing chains. To modify= a past block, an attacker would have to
redo the proof-of-work of the block and all blocks = after it and then catch up with and surpass the
work of the honest nodes. We will show later that t= he probability of a slower attacker catching up
diminishes exponentially as subsequent blocks are a= dded.


This, Satoshi (who doesn't really matter anyways I guess?) cl= aimed that for Bitcoin to function properly you need a majority honest node= s.=C2=A0

There are multi= ple behaviors one can describe as honest, and economically rational or opti= mizing is not necessarily rational.

For example, if I run a shop that takes rain checks, but I sell= an item to a higher bidder who didn't have a hold on the item, that is= not honest, but it may be selfish profit maximizing.

Satoshi said an honest majority is required f= or the chain to be extended. Honest is not really defined though. Honesty, = in my definition, is that you follow a pre specified rule, rational or not.=

It seems a lot of the R= BF controversy is that Protocol developers have aspired to make the honest = behavior also be the rational behavior. This is maybe a good idea because, = in theory, if the honest behavior is rational then we can make a weaker ass= umption of selfishness maximizing a parameter.

<= /div>
However, Satoshi did not particularly bound what asp= ects of honesty are important for the network, because there isn't a sp= ec defining exactly what is honest or not. And also as soon as people are h= onest, you can rely on that assumption for good effect.

And sometimes, defining an honest behavior = can be creating a higher utility system because most people are "law a= biding citizens" who might not be short term rational. For example, on= e might expect that miners would be interested in making sure lightning clo= ses are "accurate" because increasing the utility of lightning is= good for Bitcoin, even if it is irrational.

It seems that the NoRBF crowd want to rely on an hones= t majority assumption where the honest behavior is not doing replacement if= not requested. This is really not much different than trying to close ligh= tning channels "the right way".

=
However, where it may be different, is that even in the p= resence of honest majority, the safety of 0conf isn't assured given the= potential of race conditions in the mempool. Therefore it's not clear = to me that 0conf working well is something you can drive from the Honest Ma= jority Assumption (where honest includes first seen).


Overall, it might= be nice to more tightly document what bitcoins assumptions are in practice= and what those assumptions do in terms of properties of Bitcoin, as well a= s pathways to weakening the assumptions without compromising the behaviors = users expect the network to have.=C2=A0 An "extended white paper"= if you will.


=
=C2=A0It's somewhat clear to me that we shouldn't= weaken assumptions that only seem local to one subsystem of Bitcoin if the= y end up destabilizing another system. In particular, things that decrease = "transaction utility" for end users decrease the demand for trans= actions which hurts the fee market's longer term viability, even if we = feel good about making an honest policy assumption into a self interested p= olicy assumption.

A last= reflection is that Bitcoin is specified with an honest majority assumption= , but also has a rational dishonest minority assumption over both endogenou= s (rewards) and exogenous (electricity) costs. Satoshi did not suggest, at = least as I read it, that Bitcoin works with an rational majority assumption= . (If anyone thinks these three are similar properties you can make some tr= ivial counterexamples)

<= br>
Cheers,

Jeremy=C2=A0
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--0000000000000b03f805eb3f9dc3--