Re: [bitcoin-dev] Does Bitcoin require or have an honest majority or a rational one? (re rbf)

From: Jeremy Rubin <jeremy.l.rubin@gmail•com>
To: email@yancy•lol
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Does Bitcoin require or have an honest majority or a rational one? (re rbf)
Date: Mon, 17 Oct 2022 23:34:08 -0400	[thread overview]
Message-ID: <CAD5xwhjFeUPGFfpNTt=4iuZMYAzBOc5vMuai0vxJCN9NO9e0dw@mail.gmail.com> (raw)
In-Reply-To: <2f4344b4c7952c3799f8766ae6b590bf@yancy.lol>

[-- Attachment #1.1: Type: text/plain, Size: 16978 bytes --]

I think a diagram might help a little...

[image: image.png]

(diagram contains below text, which should be sufficient to reimagine it
for the unsighted)

Given you observe events in the following order:

   1.

   Tx A
   2.

   Tx B
   3.

   Red Block
   4.

   Tx C
   5.

   Tx D
   6.

   Tx E
   7.

   Tx F

Which block would you most want to attempt to mine at times 1..=7?

Block W

Subsidy: 1

Fee: 10

Txs: A, B

Height N

Prev V

Block X

Subsidy: 1

Fee: 2

Txs: C, D

Height N+1

Prev W

Block Y

Subsidy: 1

Fee: 12

Txs: A, B, C, D

Height N

Prev V

Subsidy: 1

Fee: 1

Txs: E, F

Height N+1

Prev Y

Block Z

Subsidy: 1

Fee: 6

Txs: A, D

Height N

Prev V

Subsidy: 1

Fee: 6

Txs: B, C

Height N+1

Prev Z

I'd argue that Y, Z, W (re-mining it with different coinbase) all beat X.
And that most likely, something like Z is most incentive compatible for
miners, but supremely bad UX for users "pay more to wait more?? What kind
of society is this". Anti-fee sniping exists to decrease likelihood of this
circumstance, but is not sufficient in general to solve it.

> The idea that people won't do something because it's "bad for Bitcoin"
> doesn't fit an adversarial model.  Even in the above examples (which I
> think wouldn't expect to happen often), I would argue the network still
> conforms to a Nash Equilibrium without requiring trust.  Although It's
> mostly speculation without some empirical data.

quote the whitepaper:

> The steps to run the network are as follows:
> 1)  New transactions are broadcast to all nodes.
> 2)  Each node collects new transactions into a block.
> 3)  Each node works on finding a difficult proof-of-work for its block.
> 4)  When a node finds a proof-of-work, it broadcasts the block to all
> nodes.
> 5)  Nodes accept the block only if all transactions in it are valid and
> not already spent.
> 6)  Nodes express their acceptance of the block by working on creating the
> next block in the
> chain, using the hash of the accepted block as the previous hash.
> Nodes always consider the longest chain to be the correct one and will
> keep working on extending it. If two nodes broadcast different versions of
> the next block simultaneously, some nodes may receive one or the other
> first. In that case, they work on the first one they received, but save the
> other branch in case it becomes longer. The tie will be broken when the
> next proof- of-work is found and one branch becomes longer; the nodes that
> were working on the other branch will then switch to the longer one.

The idea that bitcoin should work in an adversarial, stepwise selfishly
interested model is nice. But I think that it is critical to keep in mind
that is an *aspiration*, and very likely not the reality of the network
today, which depends on people caring about other things exogenous to
simplified game descriptions (like price increasing or rather not
decreasing, long term hardware investments, etc).

If you note the later whitepaper language:

By convention, the first transaction in a block is a special transaction
> that starts a new coin owned by the creator of the block. This adds an
> incentive for nodes to support the network, and provides a way to initially
> distribute coins into circulation, since there is no central authority to
> issue them. The steady addition of a constant of amount of new coins is
> analogous to gold miners expending resources to add gold to circulation. In
> our case, it is CPU time and electricity that is expended.

> The incentive may help encourage nodes to stay honest. If a greedy
> attacker is able to assemble more CPU power than all the honest nodes, he
> would have to choose between using it to defraud people by stealing back
> his payments, or using it to generate new coins. He ought to find it more
> profitable to play by the rules, such rules that favour him with more new
> coins than everyone else combined, than to undermine the system and the
> validity of his own wealth.

It is clear that the incentive is there to help encourage honest miners to
join at all, and to encourage nodes of hidden phenotype "Greedy" to prefer
honest behavior, improving network convergence, but not to make the network
functional if all players are phenotype Greedy. Satoshi still expected, in
his analysis, an honest majority.

Side Bar:

What Satoshi said doesn't really matter in one sense. The protocol is what
it is, not what somebody described it as more than a decade ago.

However, what *is* important about what Satoshi wrote is that it is sort of
the "social contract" of what Bitcoin is that we can all sort of minimally
agree to. This makes it clear, when we try to describe Bitcoin with
differing assumptions than in the whitepaper, what the changes are and why
we think the system might support those claims. But if we can't prove the
new description sound, such as showing tip mining to be rational in a fully
adversarial model, it doesn't mean Bitcoin doesn't work as promised, since
all that was promised originally is functioning under an honest majority.
Caveat Emptor!

--
@JeremyRubin <https://twitter.com/JeremyRubin>

On Mon, Oct 17, 2022 at 6:31 PM <email@yancy•lol> wrote:

> Hi Jeremy,
>
> Thanks for the reply. I do find the semantics of mempool and block org
> interesting (although there's a lot on the topic I don't know).
>
>
> E.g., suppose:
>
> Block N: Fees = 10, reward = 1
>
> Mempool: Fees = 2
>
> Mining block N+1 with the mempool leads to reward 2+1 = 3, reorging
> leads to reward of up to 10 + 1 + c, (c < 2, where c is the extra
> transactions that fit).
>
> If I'm reading this correctly, Block N was already mined, but the miner
> who mined block N+1 repacks the transactions from block N because they have
> more to gain.  Wouldn't such a situation be resolved in the same way as two
> miners who find a block at a similar time? E.g the network will choose
> depending on when block N+2 is created.
>
>
> Assume instead your reward is 8, leaving 3+c on the table.
>
> Mining block N+1 with the mempool leads to reward 2+8 = 10, reorging leads
> to 10 + 8 + c?  Wouldn't that leave 8+c?
>
>
> If you assume all other miners are tip miners, and there are two
> conflicting tips, they should pick the one with the more profit for
> them, which is the new one you made as a non-tip miner since you
> "shared" some fee.
>
> I'm curious how the "fee sharing" would be organized.  To see if I
> understand, You're asking what would happen if one of the two miners
> incentives (bribes in this case) the next miner (block N+1) to choose one
> of the competing tip miners?
>
>
> You aren't particularly more likely to remine block N or N+1, before
> someone builds on it, as opposed to deeper reorgs (which require
> larger incentive).
>
> Agree.
>
>
> However, as many have pointed out, perhaps not following the simple
> "honest tip mining" strategy is bad for bitcoin, so maybe we should
> expect it not to happen often?
>
> The idea that people won't do something because it's "bad for Bitcoin"
> doesn't fit an adversarial model.  Even in the above examples (which I
> think wouldn't expect to happen often), I would argue the network still
> conforms to a Nash Equilibrium without requiring trust.  Although It's
> mostly speculation without some empirical data.
>
> Cheers,
> -Yancy
>
> On 2022-10-17 21:10, Jeremy Rubin wrote:
>
> Building on the most work chain is perhaps not rational in many normal
> circumstances that can come up today under the stated reference
> strategy:
>
> 1) Take highest paying transactions that fit
> 2) Mine on tips
>
> E.g., suppose:
>
> Block N: Fees = 10, reward = 1
>
> Mempool: Fees = 2
>
> Mining block N+1 with the mempool leads to reward 2+1 = 3, reorging
> leads to reward of up to 10 + 1 + c, (c < 2, where c is the extra
> transactions that fit). Assume instead your reward is 8, leaving 3+c
> on the table.
>
> If you assume all other miners are tip miners, and there are two
> conflicting tips, they should pick the one with the more profit for
> them, which is the new one you made as a non-tip miner since you
> "shared" some fee.
>
> You aren't particularly more likely to remine block N or N+1, before
> someone builds on it, as opposed to deeper reorgs (which require
> larger incentive).
>
> However, as many have pointed out, perhaps not following the simple
> "honest tip mining" strategy is bad for bitcoin, so maybe we should
> expect it not to happen often? Or other strategies to emerge around
> selecting transactions so that the next M blocks have a similar fee
> profile, as opposed to picking greedily for the next block.
>
> --
> @JeremyRubin [1 <https://twitter.com/JeremyRubin>]
>
> On Sun, Oct 16, 2022 at 3:03 PM <email@yancy•lol> wrote:
>
> 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.
>
>
> It's interesting that Nash Equilibrium isn't mentioned here.  Since
> each miner has the option to either contribute to the longest chain
> or not, even if the miners know what strategy the other miners will
> use, they still wouldn't change their decision to contribute to the
> majority.
>
> 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.
>
>
> It would be honest if the store policy said ahead of time they are
> allowed to sell rain checks for more in such an occurrence.
> Although this is a good example of the difference between honest and
> rational.  I think this means it's not a Nash Equilibrium if we
> needed to rely on the store owner to be honest.
>
> 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.
>
>
> My take is that "rational" is probably a better word than honest.
> In terms of a Nash Equilibrium, each participant is simply trying to
> maximize their outcome and honesty doesn't matter (only that
> participants are rational).
>
> 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.
>
>
> I'm curious, can RBF can be described by a Nash Equilibrium?  If
> yes, then it also shouldn't matter if participants are honest?
>
> 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.
>
>
> White paper 1.1 :D
>
> 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)
>
>
> My take is the opposite unless I'm missing something.  Participants
> are always incentivized to choose the rational solution (Not to
> waste electricity on a minority chain).
>
> Cheers,
> -Yancy
>
> On 2022-10-16 19:35, Jeremy Rubin via bitcoin-dev 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
>
>
>
> Links:
> ------
> [1] https://twitter.com/JeremyRubin
>
>

[-- Attachment #1.2: Type: text/html, Size: 38911 bytes --]

[-- Attachment #2: image.png --]
[-- Type: image/png, Size: 653415 bytes --]