Bitcoin & Tragedy of the Commons

[cunicula]

This is an iterated game (compare it to iterated prisoners dilemma vs single round). In an iterated game of assurance contracts, people will understand it's really in their best interest to get a mutual buy in, and will not necessarily do the short term selfish thing of withholding from investing. Also, we could blur the line with "vague contracts" - some amount of BTC and a deadline are chosen in advance, but the exact numbers are not published beforeahand, but rather only some estimates. "I donate 10 BTC, provided X amount of BTC, between 1000 and 1500 is gathered up by block Y, between 2,000,000 and 2,150,000". This vagueness might reduce the possibility of knowing whether you are the marginal contributor, and might solve this problem completely. This is like in prisoner's dilemma, if the number of rounds is known in advance, the rational analysis suggests you should betray at round 1, while if the exact number of rounds is not known, this is not the case. Also, as Mike and others have commented, game theory is just a model of real people's behavior, and is often very very wrong, as numerous studies have shown.

No, it is not a repeated game. The participants are anonymous, so there is no way conditioning strategies on the actions of past players. Moreover, even if the game were not anonymous, improved outcomes in repeated games rely on punishments that can be inflicted on players who behave poorly. There is no strong punishment that can be meted out here, so even the repeated setting wouldn't help that much.

As far as your other responses go, I can't refute them with a logical argument. In some sense they are empirical questions rather than theoretical questions. Nevertheless, I remain extremely skeptical and see assurance contracts as a dead-end/red herring. It will be interesting to see the assurance contracts implemented because I am curious as to what will be the primary mechanisms of failure.

[Mike Hearn]

I don't understand the assumption that you have to keep network speeds at the current level (argument 2). It seems to me very likely that network speeds are too high currently and could fall a lot without reversal attacks becoming overly problematic.

By the way, some people believe that a single transaction reversal, ever, will kill Bitcoin. I don't agree with that perspective, but there's only one way to find out, and that's for network speeds to drop to the point where we see one.

[cunicula]

I don't understand the assumption that you have to keep network speeds at the current level (argument 2). It seems to me very likely that network speeds are too high currently and could fall a lot without reversal attacks becoming overly problematic.

By the way, some people believe that a single transaction reversal, ever, will kill Bitcoin. I don't agree with that perspective, but there's only one way to find out, and that's for network speeds to drop to the point where we see one.

What you need out of the network speed depends on what you are trying to secure the network against. I'm not concerned about double spends either. However, I think it will become relatively easy for a single miner to acquire 51% and exclude all other miners. This will be profitable because:

a) he will be able to acquire 100% of block generations as opposed to 51%
b) he will be able to acquire 100% of txn fees as opposed to 51%
c) he will be able to charge higher txn fees than would occur in under competition.

This is already pretty feasible for a wealthy individual or group of individuals. Later, it will become easy vis-a-vis the potential rewards. I think you will need something like the current block reward to prevent a monopoly from forming. It is worth nothing that because of (c), fee-based rewards are more conducive to monopoly than currency generation. I don't think bitcoin will fail when mining becomes a monopoly. In my view, the profits of an honest monopoly likely greatly exceed those due to double spending. This is a good thing because it means that there is no reason to fear a monopoly.

Despite all this, I believe proof-of stake is much better than proof-of-work because it results in a lower marginal cost of txn verification and therefore lower fees under both monopoly and competition.

[markm]

Not fully utilising the full merged-mining capacity seems like a tragedy too, maybe it is not technically exactly a tragedy of the commons per se, but all that open potential being dog-in-the-manger fenced away from the commoners instead of being expansive and accomodating as many chains as it can seems not unlike some steps in how commons got fenced off.

We're lucky we even still have rights of way along rivers and beaches in some juridictions let alone any actual commons.

Its my power, mine to waste, I profit by denying it to others... Familiar tune.

-MarkM-

[finway]

If there's not enough interests in bitcoin,
and the difficulty falls,
and it's easy to make a 51% attack,
then it raise two questions:

1.  Are you sure there will be any interests in attacking it ?
2.  Why do you even care ?

[DeathAndTaxes]

If there's not enough interests in bitcoin,
and the difficulty falls,
and it's easy to make a 51% attack,
then it raise two questions:

1.  Are you sure there will be any interests in attacking it ?
2.  Why do you even care ?

That isn't the issue.

Say instead:
There IS a lot of interest in Bitcoin but the reward system is borked so difficulty falls.
Entrenched interests see this as an easy opportunity to kill a competitor and make a 51% attack.

[cunicula]

I prefer to call an attack a takeover. Attack suggests a hostile intent towards the technology. I expect that when someone or some group takes over that they will do their best to foster broad use of bitcoin. In fact, if anything I expect the technology to benefit from a takeover. They will only want to 'attack' competing miners.

1.  Are you sure there will be any interests in attacking it ?
2.  Why do you even care ?

1) A takeover will be profitable. A monopolist will be able to increase his bitcoin earnings per unit of mining expenditure by several-fold. This is motivation enough.

2a) I'm concerned that an irrational fear of monopoly could lead to a destructive panic in the event of takeover. I would prefer a smooth transition because I like bitcoin and want it to succeed. People need to get prepared to accept the coming monopoly. Right now everyone is prepped to respond like Chicken-little.
 
2b) I would like to promote a mixed proof-of-stake and proof-of-work system. The system will lead to lower equilibrium txn fees and make cryptocurrency technology more competitive with other payment platforms. Lower fees with proof-of-stake occur under both monopoly and competition.

2bi) The case for proof-of-stake becomes stronger if you believe that a takeover is likely to occur.

2bia)If you fear takeover, then proof-of-stake makes takeover much more difficult (perhaps an order of magnitude).

2bib) If you are willing to accept takeover, then you will likely feel more comfortable with proof-of-stake. The monopolist will have even stronger incentives to behave benevolently if he is required to hold a near majority of the bitcoin money supply in order to retain his position.

[markm]

Hmm I guess SolidCoin's take-away from your proposals was proof of stake.

Somehow I don't think he quite got it right, though.

This 0.8 / 0.2 you propose doesn't sound particularly difficult to code, but if yet another altcoin is to be launched to implement the concept the coin or chain should have a name...

-MarkM- (I hesitate to suggest CUNcoin, though maybe it is kind of an easy one to arrive at...)

[Meni Rosenfeld]

... I assume you mean that the confirming pools will also reject any blocks that contain a conflicting transaction.

Yes, if by "a conflicting transaction" you mean a fraudulent double-spending attempt. That's not a bug, it's a feature.

The protocol doesn't say that if there are two conflicting transactions (whether a fraudulent double-spend attempt or something else) you have to reject both and reject any block that contains either. It says you go with the one you encountered first, unless a block is found that contains the other and then you go with that. In your scenario (especially if there is a dedicated denial-of-service attack), every block will be rejected by every miner because it contains some transaction the miner committed to reject.

Reduction in block reward is arguably the second biggest challenge Bitcoin is facing (the first is legal attacks).

In my opinion, the first challenge is legal attacks. The second challenge is wallet security. Reduction in block reward doesn't feature as a problem at all. We'll know after December anyway.

In December the block reward will be 25 BTC. The problem is when block reward is close to 0. We're no going to have any empirical evidence for a long time.

I'm not saying the problem isn't solvable; I'm saying it's silly to think of it as "not a problem" when it was never tested, and when the proposed ideas of how the ecosystem will work depart completely from how Bitcoin works now and from its design principles.

Agreed. While this scheme helps protect the network integrity, I'm not sure this addresses the "Tragedy of the Commons " fallacy. They claim a conspiracy will form and that people will choose the side of the conspiracy because it human nature to exploit any public works to the point of failure. They will argue that people will not use network assurance contracts enough to counter a monopolistic attack because it is "someone else's problem to worry about." Game theory helps us find problems to address, but the real world isn't the zero-sum game that some folks want to believe it is.  They are simply naive.

Yes, people will contribute more than what the immediate incentives can account for, due to altruism, fear of a snowball effect, superrationality, etc. But they will only do so by a small amount, not enough to sustain the expenditure that will be required. If you really want to be future-proof, you need to align the immediate incentives properly.

If anyone succeeded in monopolizing mining power, the price of bitcoin will plummet, thus eliminating the very incentive for obtaining that monopoly (unless your incentive is to destroy bitcoin).

A big unless. You'd want to attack the network either for profiting from double-spending, or for harming Bitcoin (political agenda, destroying competition, short-selling bitcoins). There's a tradeoff, some things you can do to protect against the former makes you more vulnerable to the latter.

I don't understand the assumption that you have to keep network speeds at the current level (argument 2). It seems to me very likely that network speeds are too high currently and could fall a lot without reversal attacks becoming overly problematic.

They are (arguably) too high now for the current value of Bitcoin. As the impact of Bitcoin rises, so will the incentives to attack it. Since the attack incentive is more or less proportional to the purchase power of a bitcoin, it is safe to assume that the BTC reward per block is the invariant security factor. 50 BTC is high, but 1 BTC - which may very well be the future equlibrium - is not.

I believe Bitcoin already has everything required to handle this situation by having players who benefit from high network speeds automatically create and broadcast network assurance contracts:

  https://bitcointalk.org/index.php?topic=67255.msg785122#msg785122

I think this correctly solves the problem by allowing co-operation amongst competing players to fund network security in such a way that one player doesn't end up carrying the rest.

This will certainly help. Decoupling compensation from individual transactions is a positive direction. But I think the fundamental problem remains. Someone would want to pledge his own funds only if he thinks there's a good chance he will tip the scale to passing the threshold. Which means the network will always walk on the edge in which there's a chance for everything to crumble.

Also, as Mike and others have commented, game theory is just a model of real people's behavior, and is often very very wrong, as numerous studies have shown.

Game theory isn't a model of what people do. It's a model of what people should do. Even if 99% of people do "better" than what game theory prescribes, there can still be 1% who are selfish and rational and exploit the system. Having a system that is secure in theory can go a long way to preventing unpleasant surprises in practice.

By the way, "failures of game theory predictions" are commonly not problems with the theory, but with the game that was chosen to model the specific real-world situation.


I am still of the opinion that all the ideas proposed could account for some level of hashing, but not enough for proof-of-work to completely secure the network. Which is why proof-of-stake will need to augment it to pick up the slack.

[markm]

I am still of the opinion that all the ideas proposed could account for some level of hashing, but not enough for proof-of-work to completely secure the network. Which is why proof-of-stake will need to augment it to pick up the slack.

Thanks! So then maybe we call it CMRcoin or MRCcoin? (Cunicula/Meni Rosenfeld or vice versa; I know normally it'd be just one initial for each of you but I have this bias for three-letter currency-symbols...)

-MarkM-

EDIT: Oh wait, duh, CRCoin or RCCoin (Cunicula-Rosenfeld Coin or Rosenfeld-Cunicula Coin).

[Meni Rosenfeld]

I am still of the opinion that all the ideas proposed could account for some level of hashing, but not enough for proof-of-work to completely secure the network. Which is why proof-of-stake will need to augment it to pick up the slack.

Thanks! So then maybe we call it CMRcoin or MRCcoin? (Cunicula/Meni Rosenfeld or vice versa; I know normally it'd be just one initial for each of you but I have this bias for three-letter currency-symbols...)

Thanks, but I'd much rather see this change implemented while keeping the Bitcoin name and the current blockchain.

PS. AFAIK, the first mention of using proof-of-stake in Bitcoin was by QuantumMechanic, in this appropriately named post.

[markm]

Thanks, but I'd much rather see this change implemented while keeping the Bitcoin name and the current blockchain.

Ha ha, good luck with that without proof of concept.

So, back to proof of concept... I do not want to detract from bitcoin with altchains, so we can maybe make sure it is clear from the outset that if it takes off too darn well Bitcoin itself is free to set some block number at which it adopts a similar system.

But to drive Bitcoin to do so, we really should demonstrate that failing to do so could indeed prove a competitive threat to Bitcoin's value rather than being a harmless companion-coin or hanger-on or, indeed, merely yet another of the many currencies used by various civilisations of the Galactic Milieu.

I am losing track, are you both in favour of making such a change to Bitcoin on purely theoretical grounds, or is at least one of you at least a little more empirically oriented than that?

-MarkM-

[Meni Rosenfeld]

Thanks, but I'd much rather see this change implemented while keeping the Bitcoin name and the current blockchain.

So, back to proof of concept... I do not want to detract from bitcoin with altchains, so we can maybe make sure it is clear from the outset that if it takes off too darn well Bitcoin itself is free to set some block number at which it adopts a similar system.

But to drive Bitcoin to do so, we really should demonstrate that failing to do so could indeed prove a competitive threat to Bitcoin's value rather than being a harmless companion-coin or hanger-on or, indeed, merely yet another of the many currencies used by various civilisations of the Galactic Milieu.

I can certainly imagine a scenario where Bitcoin fails due to this problem, and an alt proof-of-stake coin will be there to pick up the pieces. But I fear that people will attribute the failure to the concept of cryptocurrency itself, rather than to solvable problems that were foreseen in advance.

I don't expect an alt to rise to prominence before Bitcoin failing, so by the time people will be convinced to make the change, it will arguably be too late.

Which is why I hope people will give more weight to theoretical considerations. Empirical testing is great but it's not always feasible.

This needn't be an immediate all-or-nothing change. You could start by collecting people's signatures and ignoring them. Then you could try reasoning what would happen if we used these signatures in branch selection.

I am losing track, are you both in favour of making such a change to Bitcoin on purely theoretical grounds, or is at least one of you at least a little more empirically oriented than that?

I'm not going to be writing code to implement this anytime soon, if that's what you mean. But I'm putting a lot of personal resources into Bitcoin on the hope that its challenges will eventually be overcome, so it's not "purely theoretical" to me.

Anyway, this problem probably won't manifest for a long time. Discussion of the problem and solutions should be out there, but as long as uncertainty of the future prospects isn't holding back adoption, there's no rush to implement anything.

[markm]

Actually there has already been a rush to implement pretty much "anything", ha ha.

I want to push merged mining further, it seems to me I could mine at least a few more chains than I am currently mining, so given a choice between this or just a bunch of boring old identical clones this concept might be worth trying.

We have a bunch of pennystock-like chains already, lets see if a penny-CRCoin can beat out the other penny-chains.

If it can emerge a clear leader "in its class" then that should lend at least a couple of pennyweights to the theory, yes?

I don't expect you to write code, I don't expect Cunicula to write code. It was a very very pleasant surprise to me that Unthinkingbit does write code, in fact a whole lot more of DeVCoin's code than I wrote. (Heh "than I hacked a little" is more like it, I didn't really "write" anything, I just hacked away some at what was already written, enough to get it to at least look like it runs.)

So don't worry about coding. We can bribe codemonkeys with DeVCoins, or just make up the code, it doesn't sound real hard. And it sounds like an interesting idea.

-MarkM-

P.S. Hey maybe we should also accelerate the decay of the block-rewards in it so we can get to the juicy bits sooner?

[Meni Rosenfeld]

... I assume you mean that the confirming pools will also reject any blocks that contain a conflicting transaction.

Yes, if by "a conflicting transaction" you mean a fraudulent double-spending attempt. That's not a bug, it's a feature.

The protocol doesn't say that if there are two conflicting transactions (whether a fraudulent double-spend attempt or something else) you have to reject both and reject any block that contains either. It says you go with the one you encountered first, unless a block is found that contains the other and then you go with that. In your scenario (especially if there is a dedicated denial-of-service attack), every block will be rejected by every miner because it contains some transaction the miner committed to reject.

I've obviously not explained myself clearly enough, because that's not what I'm suggesting. The miner does not commit to reject any block that it would not reject anyway.

Suppose WalMart sells a widget to Joe for 2 BTC. Joe is at the checkout and sends 2 BTC to WalMart's receiving address.

WalMart doesn't expect Joe to wait for 6 confirmations before departing with his newly-purchased widget. So WalMart pays DeepBit 0.01 BTC to validate the transaction and promise that DeepBit will include that transaction in the next block mined IF DeepBit is the miner of the next block. Neither WalMart nor DeepBit objects if some other miner includes the transaction first, so there's no need to reject from some other miner for this reason.

In practice, WalMart might have a similar arrangement with DeepBit, Slush, Eligius and a couple of other pools, to obtain sufficient certainty that the transaction will make it into the block chain.

WalMart is not paying these miners to reject anything. WalMart is paying these miners for advance knowledge that WalMart's transaction will be included in the next block, IF that next block is mined by one of those miners. And that service is valuable enough that mining will be plenty profitable even with a block reward of zero.

I assumed the participating pools would reject conflicting blocks, because if not, the weakness is even clearer. Joe makes a double-spend, one to Walmart and one to himself. Walmart pays 51% of the pools to commit to the transaction to Walmart. Meanwhile Joes pays the other 49% (or 20%, or whatever) to commit to the send-back. Walmart thinks the transaction is safe and gives the product to Joe, when in fact there's a 49% chance that the next block found will have the payment to Joe, and Walmart will lose the money.

Actually there has already been a rush to implement pretty much "anything", ha ha.

I am a critic of the majority of existing alt coins. Alts have their place but they really need to be thought out and have a reason to exist, I'm not eager to rush an alt of my own.

We have a bunch of pennystock-like chains already, lets see if a penny-CRCoin can beat out the other penny-chains.

If it can emerge a clear leader "in its class" then that should lend at least a couple of pennyweights to the theory, yes?

I don't expect you to write code, I don't expect Cunicula to write code. It was a very very pleasant surprise to me that Unthinkingbit does write code, in fact a whole lot more of DeVCoin's code than I wrote. (Heh "than I hacked a little" is more like it, I didn't really "write" anything, I just hacked away some at what was already written, enough to get it to at least look like it runs.)

So don't worry about coding. We can bribe codemonkeys with DeVCoins, or just make up the code, it doesn't sound real hard. And it sounds like an interesting idea.

-MarkM-

There's still some work to be done with the design. The design I currently have should work against double-spending, but not necessarily against denial of service.

I can work on the design from a high-level perspective, but I don't think I'll be able to lead the development and promotion efforts in the near future. Someone would have to volunteer for that (and to create a new thread for further discussion).

P.S. Hey maybe we should also accelerate the decay of the block-rewards in it so we can get to the juicy bits sooner?

Possibly, but that's not strictly necessary, test attacks should work well for testing resilience.

[markm]

There's still some work to be done with the design. The design I currently have should work against double-spending, but not necessarily against denial of service.

I can work on the design from a high-level perspective, but I don't think I'll be able to lead the development and promotion efforts in the near future. Someone would have to volunteer for that (and to create a new thread for further discussion).

No problem, it is CRCoin not RCCoin I am thinking of first off anyway, since the 0.8 & 0.2 proposal seems concrete enough and simple enough, gosh knows how complicated whatever you want to "collect signatures" for will turn out to be. I was thinking of going really simple, the address the reward is to go to either contains enough stake or it doesn't, no licensed miner / licensed mining, just put the reward where the stake is if there is enough stake already there or invalidate the block.  Maybe make sure at least stake plus reward is still there 120 blocks later or don't mature the reward.

-MarkM-

[Meni Rosenfeld]

There's still some work to be done with the design. The design I currently have should work against double-spending, but not necessarily against denial of service.

I can work on the design from a high-level perspective, but I don't think I'll be able to lead the development and promotion efforts in the near future. Someone would have to volunteer for that (and to create a new thread for further discussion).

No problem, it is CRCoin not RCCoin I am thinking of first off anyway, since the 0.8 & 0.2 proposal seems concrete enough and simple enough, gosh knows how complicated whatever you want to "collect signatures" for will turn out to be. I was thinking of going really simple, the address the reward is to go to either contains enough stake or it doesn't, no licensed miner / licensed mining, just put the reward where the stake is if there is enough stake already there or invalidate the block.  Maybe make sure at least stake plus reward is still there 120 blocks later or don't mature the reward.

-MarkM-

Can you link to the 0.8 & 0.2 proposal? My current design is described here, I think it's not complicated at all.

[markm]

I thought the 80% / 20% proposal was in this thread or the other, certainly I read it in this span of being awake. But I cannot find it.

Thanks for the link, I will go check that out.

Things I saw while looking for the 80% / 20% thing though made me realise there probably are a bunch of complications that will pop up in actually trying to code though. Not in the code itself initially but in all kinds of sneaky problems that need to be thought out.

One thing I liked about the proposal though was it scaled so that pooling together basically ended up increasing the stake you'd need, so you might as well solo mine with a tiny stake or maybe even no stak in coin form (hashes count) instead of ganging up with others to pile up a stake between the lot of you. It seemed that might actually even potentially be able to be tuned to address the LiTeCoin people's concern that the little guy keeps losing the ability to make a few pennies at home over and above electricity costs.

-MarkM-

[ripper234]

FYI, I added these two entries to the wiki, you're all invited to edit:

https://en.bitcoin.it/wiki/Tragedy_of_the_Commons
https://en.bitcoin.it/wiki/Proof_of_Stake

[cunicula]

I would be tremendously excited to see a proof-of-concept, but please don't name anything after my handle. The coder will deserve most of the credit for doing the actual work.

Thanks for the wiki entry Ripper. I will edit the wiki, eventually including my conception of how proof-of-stake would work. I will also allot separate space for criticism of this conception. I'm not the best communicator so anyone can feel free to edit what I write for clarity.

I'm not going to describe my own idea or Meni's idea in detail here, but here is an overview of three important differences.

My system aggregates information about stake and work to generate a composite vote about block validity. Validity is determined by whoever can muster the most composite votes. My system distributes the majority of fees and generations to people who already have a lot of coins. An advantage of this is that it is associated with lower txn fees in equilibrium.

Meni's system polls stake and work separately. I believe validity requires concurrence of votes by miners and votes by stakeholders (but am not sure, Meni?).  Meni's system distributes most (maybe all) fees and generations to miners. Advantages of this are increased economic mobility and reduced inequality.