Skip to content

Instantly share code, notes, and snippets.

@amiller
Created April 25, 2013 05:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save amiller/cf9af3fbc23a629d3084 to your computer and use it in GitHub Desktop.
Save amiller/cf9af3fbc23a629d3084 to your computer and use it in GitHub Desktop.
Here's a thought about PoW consensus and Bitcoin's incentive model:
"Cooperation" in Bitcoin means following the first rule of mining:
"always mine on the valid chain with the most proof-of-work." This
protocol achieves stabilizing (eventual) consensus in the Cooperative
Majority setting. Although the protocol does not define how to choose
between two equal-work chains, all the standard clients for now prefer
the one they learn about first.
However, "honest majority" is not at all an interesting/realistic
model - Bitcoin's construction appeals to rational participants of
some kind, a model for which we have yet to provide. Mining is an
expensive protocol, but a secure platform for transactions (financial
and otherwise) is useful, and so users are willing to pay for service.
Bitcoin's current incentive scheme is this: users attach fees to the
transactions they submit, and when a miner wins a block, he is
rewarded with the total fees from all the transactions included in the
block.
What we'd like is for the Cooperative behavior to be an equilibrium of
some kind. Defecting means mining on a chain other than the longest
valid one (for example, a double-spend attack involves mining on a
fork more than 6 blocks in the past). The rough argument seems to be
that if everyone else follows the standard behavior, then even if a
defector builds a 1-block fork, no one will switch to it anyway. But
this doesn't hold in all cases. Consider the scenario where some user
broadcasts a transaction with an anomalously large fee, U₁. Let's say
that the chance of winning the next block is α, your proportion of the
total power (in hashes/second), and that the typical reward for a
block is U₀. Then the expected utility of cooperation (strategy C₀) is
(something like):
E[C₀] = αU₀
In order to earn the enormous reward U₁ (strategy C₁) you'd have to
win TWO blocks before the rest of the network wins one:
E[C₁] = α²U₁ (not quite right)
So, in the case that U₁/U₀ ≥ α⁻¹, a rational miner with hashpower α
will defect, even if all others cooperate. The larger your share of
the hash power, the lower the breakpoint for a prize be to be worth
contending over.
Example: Suppose the (fictional) RationalMiningPool accounts for about
33% of the hashpower. A software glitch at MyPHPWebWallet.com results
in a submitted transaction with a fee exceeding 75 btc (the typical
block reward is only 25 btc). RationalMiningPool does not find the
first winning block to include this fee; however, it decides to keep
fighting for the big prize, since the chance of finding the next two
consecutive solutions is decent and the high value makes it
worthwhile.
(1) This has predictive power: if an enormous transaction fee occurs
in the wild, I'd expect to see several contending blocks containing
that transaction (well, at least to the extent anyone engages in
"rational" mining at this time)
But defecting isn't an equilibrium either. Since mining is expensive
and overall utility might diminish if there is contention rather than
consensus, it can be preferable not to play at all. I assume that U₀
is already the competitive price below which a rational miner exits.
Is there a cooperative equilibrium? Here's my solution:
(2) A miner with hashpower α (such that U₁/U₀ ≥ α⁻¹) could safely
take a cut of the reward αU₁ for himself, and offer the remaining
(1-α)U₁ as a fee for everyone else to fight over next. The reason is
that for any miner with hashpower-portion β < 1-α, the value for
cooperating in the next round E[C₀'] = β(1-α)U₁ exceeds the value of
contending further E[C₁'] = β²U₁.
This line of reasoning (modulo some careless arithmetic) suggests that
cooperation is be an equilibrium, at least when the value of a single
block is not so high so as to reward contention rather than progress.
(3) There is an obscure rule in the Bitcoin protocol that prevents my
solution from occurring, and by the above argument I think this is a
design flaw. The "coinbase maturity" rule says that you can't spend
mining rewards immediately, instead you have to wait for 100 blocks to
elapse. With bounded budgets, a miner that wins the big prize would be
unable to offer up the suggested (1-α)U₁ share and therefore this
contention would be unavoidable.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment