As I already said I am not in favor of asking the miners to use some conventions as for choosing one of several competitive blocks, yet I would like to note that apart from the suggested convention to choose the block at random there is a deterministic approach that is almost as good (meaning, it is not god at all):
We ask all nodes to propagate all competitive valid blocks. We ask the miner who receives k valid blocks B_1, B_2, …, B_k, to calculate the xor (or sum modulus 2^128) of lh_1, lh_2, …, lh_k and get a 128 bit random number R, where lh_j is the 128 lower bits of the hash of the block B_j (meaning, the bits that doesn’t affect the validity of the proof of effort). Then the miner should take the block whose index is R modulus k.
Despite being deterministic, this convention is having a similar effect as the convention asking miners to choose at random one of the blocks. If the attacker choose to keep her new mined block secret and release it only when the new honest block is published, since the lower 128 bits of the not-existing yet honest block are random, her winning probability is 1/2. Moreover, when the attacker is trying to discard a block that is already existing (i.e. replace the currently last block of the chain by on of hers), then although the lower 128 bits of the existing honest blocks are known to the attacker, the lower 128 bits of her own blocks are currently random, thus the winning probability is still 1/2.
Yet this convention is a bit worse than the randomly-choosing possibility: in this convention the attacker knows immediately whether her block win or lose the race, instead of knowing this only when the new block on top of either of the competitive blocks is published. This knowledge can be used to improve the attack in case the attacker is secretly keeping yet another block on top of the recently released block, and can make a cleverer decision as for immediately releasing the next block or not. This exactly is the difference between the "st_m" family of strategies and the "sst_m" family, presented in my paper - http://eprint.iacr.org/2013/868.pdf.
Lear
Topic: Discouraging "Selfish" mining (Read 4733 times)
tl;dr all your suggestions actually make the attack easier, as the attacker can adapt her/himself to the new rule.
Meanwhile, I would like to explain my view of all kinds of solutions that suggest asking users to propagate blocks in a certain way and asking miners to adopt blocks in a certain way.
First, as Gavin said, such a countermeasure is external to the core protocol and is not obligatory. Hence we better not base our security on the good will of users and miners, unless we point out a really strong incentive for them to follow the proposed change.
Second, even if all miners could somehow always distinguish between the honest block and its malicious competitor block, and all miner would always mine on top of the honest block in case of a competition, there is still a reasonable attack strategy for attacker having more than third of the total hash-power.
Third, I believe we cannot distinguish between honest and withholded blocks, hence the best we can do is to propagate all competitive blocks and let each miner randomly choose on which one to mine. Any other criteria will actually help the attacker and makes thing worst! I have seen three sophisticated proposals on this thread (of ByteCoin, HanSolo, and Peter) that ignores the fact that the attacker can easily adapt her/himself to the new rule.
ByteCoin suggests always preferring the block with more transactionseconds. This way the attacker can simply copy all transactions of the last block in the chain, add some more transactions oh her/his own, and create a block that is about to replace the currently last block in the chain. The honest nodes in the network will actually think that the honest block is the malicious block and vice versa!
HanSolo suggests always preferring the block whose timestamp is closer to the time it was received. This way the attacker can win the race simply by having a better network connectivity than a small honest miner (meaning, having many slave nodes all across the network that propagate the attacker's blocks immediately, without the verification which cause much of the delay).
Peter suggests always preferring the block that takes the least total sum of fees. This way the attacker can simply omit a single transaction out of the last block in the chain, and form a competitive block that is about to replace the currently last block in the chain.
Please remember: block discarding strategies doesn’t necessarily involve keeping mined blocks in secret. The underlying principle of the block discarding attack is to increase the attacker's portion of the total number of eventually confirmed blocks, so that it will be higher than the attacker's portion of the total hash-power. This is done by artificially forking the chain: instead of increasing the chain's length by mining on top of the last known block, the attacker sometimes mine on top of earlier block in order to discard one of the honest blocks and replace it by the attacker's block.
Currently the convention is to prefer the block that is firstly received, hence the attacker strategy involves keeping a block secret and releasing it as fast as possible only when a competitive honest block have been found. If this convention is changes, the strategy would change. A more comprehensive analysis of Block Discarding strategies is given in my paper.
In conclusion, the only possible strong countermeasure involves punishing forks, because artificially creating forks is the core principal of the attack, rather than any specific property of the mined blocks.
Happy New Year,
Lear.
Meanwhile, I would like to explain my view of all kinds of solutions that suggest asking users to propagate blocks in a certain way and asking miners to adopt blocks in a certain way.
First, as Gavin said, such a countermeasure is external to the core protocol and is not obligatory. Hence we better not base our security on the good will of users and miners, unless we point out a really strong incentive for them to follow the proposed change.
Second, even if all miners could somehow always distinguish between the honest block and its malicious competitor block, and all miner would always mine on top of the honest block in case of a competition, there is still a reasonable attack strategy for attacker having more than third of the total hash-power.
Third, I believe we cannot distinguish between honest and withholded blocks, hence the best we can do is to propagate all competitive blocks and let each miner randomly choose on which one to mine. Any other criteria will actually help the attacker and makes thing worst! I have seen three sophisticated proposals on this thread (of ByteCoin, HanSolo, and Peter) that ignores the fact that the attacker can easily adapt her/himself to the new rule.
ByteCoin suggests always preferring the block with more transactionseconds. This way the attacker can simply copy all transactions of the last block in the chain, add some more transactions oh her/his own, and create a block that is about to replace the currently last block in the chain. The honest nodes in the network will actually think that the honest block is the malicious block and vice versa!
HanSolo suggests always preferring the block whose timestamp is closer to the time it was received. This way the attacker can win the race simply by having a better network connectivity than a small honest miner (meaning, having many slave nodes all across the network that propagate the attacker's blocks immediately, without the verification which cause much of the delay).
Peter suggests always preferring the block that takes the least total sum of fees. This way the attacker can simply omit a single transaction out of the last block in the chain, and form a competitive block that is about to replace the currently last block in the chain.
Please remember: block discarding strategies doesn’t necessarily involve keeping mined blocks in secret. The underlying principle of the block discarding attack is to increase the attacker's portion of the total number of eventually confirmed blocks, so that it will be higher than the attacker's portion of the total hash-power. This is done by artificially forking the chain: instead of increasing the chain's length by mining on top of the last known block, the attacker sometimes mine on top of earlier block in order to discard one of the honest blocks and replace it by the attacker's block.
Currently the convention is to prefer the block that is firstly received, hence the attacker strategy involves keeping a block secret and releasing it as fast as possible only when a competitive honest block have been found. If this convention is changes, the strategy would change. A more comprehensive analysis of Block Discarding strategies is given in my paper.
In conclusion, the only possible strong countermeasure involves punishing forks, because artificially creating forks is the core principal of the attack, rather than any specific property of the mined blocks.
Happy New Year,
Lear.
tl;dr the best solution is simply not reward any of the competitive blocks. Meaning, miners will not be rewarded for blocks that have competitive orphan blocks.
Hi all,
I'm Lear, and I have discovered and analyzed the Block Discarding Attack, which is a generalization of the "Selfish Mining" strategy, independently (and actually before) Eyal and Sirer published their paper. You can find here my draft paper, in which I present a more comprehensive analysis of the attack and its possible countermeasures: http://eprint.iacr.org/2013/868.pdf. You might as well read the bitcointalk posts I wrote in response to Eyal and Sirer misleading paper: https://bitcointalksearch.org/topic/m.3494144, https://bitcointalksearch.org/topic/m.3504846.
In this post I would like to be focused on the possible countermeasures, yet I must note that the Block Discarding Attack (including the "selfish mining" strategy) is not applicable to pools, and only solo miners can perform it (Please read my paper or the first of my two posts for explanations). Thus, the current threat of the Bitcoin network is negligible. Nevertheless the currently theoretic attack might one day become feasible, in case a solo miner gains a relatively high fraction of the total hash-power. This is not completely unlikely scenario, as the arrival of new ASICs changes the distribution of hash-power. So I do believe that a countermeasure should be introduced.
Fortunately, there is a very simple change to the core protocol, that can be shown to make the attack unreasonable unless the attacker's fraction of the total hash-power is *very* close to 50%. Obviously, that is as far as we can get. The solution is to introduce a fork-punishment mechanism, as explained in the paper and in my first post. Basically, I suggest that when there are two competitive blocks, no matter which one of them is eventually confirmed, both the confirmed and the unconfirmed blocks will not reward their miners. A detailed possible implementation, incentive-oriented, is presented in my paper.
Lear.
Hi all,
I'm Lear, and I have discovered and analyzed the Block Discarding Attack, which is a generalization of the "Selfish Mining" strategy, independently (and actually before) Eyal and Sirer published their paper. You can find here my draft paper, in which I present a more comprehensive analysis of the attack and its possible countermeasures: http://eprint.iacr.org/2013/868.pdf. You might as well read the bitcointalk posts I wrote in response to Eyal and Sirer misleading paper: https://bitcointalksearch.org/topic/m.3494144, https://bitcointalksearch.org/topic/m.3504846.
In this post I would like to be focused on the possible countermeasures, yet I must note that the Block Discarding Attack (including the "selfish mining" strategy) is not applicable to pools, and only solo miners can perform it (Please read my paper or the first of my two posts for explanations). Thus, the current threat of the Bitcoin network is negligible. Nevertheless the currently theoretic attack might one day become feasible, in case a solo miner gains a relatively high fraction of the total hash-power. This is not completely unlikely scenario, as the arrival of new ASICs changes the distribution of hash-power. So I do believe that a countermeasure should be introduced.
Fortunately, there is a very simple change to the core protocol, that can be shown to make the attack unreasonable unless the attacker's fraction of the total hash-power is *very* close to 50%. Obviously, that is as far as we can get. The solution is to introduce a fork-punishment mechanism, as explained in the paper and in my first post. Basically, I suggest that when there are two competitive blocks, no matter which one of them is eventually confirmed, both the confirmed and the unconfirmed blocks will not reward their miners. A detailed possible implementation, incentive-oriented, is presented in my paper.
Lear.
I must remark that I am very concerned that we do not introduce further incentives for miners to spam the network with transactions carrying fees in order to increase their own profits at the expense of everyone else. One important metric for the health of the network is the number of zero-fee transactions in blocks.
I haven't had time to read your proposal in detail, but why not make the tie-breaking rule be to favor the block with the least fee-paying transactions? That's what aligns with miner's rational self-interest to have fee-paying transactions available for them to mine.
Of course, both versions can be somewhat gamed by miners accepting out-of-band fee payment.
I would be wary of allowing fees to change the merit of the block because it's low-risk for a miner to publish a transaction with a large fee immediately before publishing a pre-mined block which has its merit artificially inflated because of the influence of the included transaction's fee. Let's not forget that the purpose of a fee is to pay a fair amount for the time taken to verify the transaction and the space it takes in the block-chain. There are a variety of distorting effects that transactions with large fees have so I suggest that a transaction's fee for the purpose of calculating transactionfee seconds be capped at a value which is no larger than the transaction with the largest fee that the client saw did not make it into the previous block.
That's a good suggestion, but still open to abuse. The selfish miner mines a normal block, then a block with a high fee tx. It releases the high fee tx before releasing either of the blocks. Now it looks like the tx did not make it into block 1, and block 2 gets full credit for the large fee-seconds count it displays. Of course this requires a minimum of two pre-mined blocks to work, so your countermeasure assures that the attacker has gamma=0 in the case where both the private and public chains are 1 block long, (which is the only case where gamma mattered in the SM attack as described), but at the cost of giving him gamma=1 for any block races where the split is more than 1 block back. It is trivial to adapt the SM attack to exploit this by not revealing the private chain when the lead gets reduced to 1, but rather only once the public chain catches up (since gamma=1 means everyone will prefer our fork), which allows us to build longer secret chains.
I am also concerned about the potential to exploit something like this by not working from the head (i.e. we give the public chain a 1 block headstart). Unless the block creator explicitly maximised his transaction-fee-seconds score at the cost of all other considerations, I can build a block with a higher txfee-seconds count and know that my block will win the block race.
I am sensitive to hannesnaude's concerns not to encourage block-bloating but hopefully the existing schemes to calculate transaction priority will cope with that. Am I right in thinking that clients are likely to fail to relay and otherwise drop transactions with very low priority?
Even if you fill up a 1MB block with 192 byte transactions, each carrying a 0.0001BTC fee, you only spend 0.546BTC in fees. A selfish miner will fill a block with all the public transactions it deems small enough and then fill all the remaining space with small secret transactions that carry fees (which he expects to get back). As soon as the block has been mined, he releases the secret transactions. Then no honest miner can exceed his transaction-seconds score, the best they can do is to match it, and unless they are using transaction-seconds as the only measure to optimise, they will probably end up with a lower transaction-seconds score.
Curious to hear your opinion on HanSolo's proposal.
I really like your proposal, ByteCoin. I think it captures the intuitive notion of "incentivize publishing blocks immediately as the best policy".
... highest-number-of-transactionseconds seems like a very good criteria for resolving ties.
Thank you. The intention was also to provide an incentive for miners to make an effort to clear client's memory pools.... highest-number-of-transactionseconds seems like a very good criteria for resolving ties.
I wonder if transactionfee seconds is more interesting that transactionseconds?
I would be wary of allowing fees to change the merit of the block because it's low-risk for a miner to publish a transaction with a large fee immediately before publishing a pre-mined block which has its merit artificially inflated because of the influence of the included transaction's fee. Let's not forget that the purpose of a fee is to pay a fair amount for the time taken to verify the transaction and the space it takes in the block-chain. There are a variety of distorting effects that transactions with large fees have so I suggest that a transaction's fee for the purpose of calculating transactionfee seconds be capped at a value which is no larger than the transaction with the largest fee that the client saw did not make it into the previous block. In other words, if a client received a transaction paying 0.01BTC in fees and then received a plausible block which did not include that transaction, then when the client receives a 10BTC fee transaction followed swiftly by a block including that transaction then the transactionfeeseconds of the 10BTC fee transaction should be calculated as if that transaction had a 0.01BTC fee.
The general idea behind this is to start to remove perverse incentives that arise from transactions with large fees while still allowing fees to buy priority service.
I am sensitive to hannesnaude's concerns not to encourage block-bloating but hopefully the existing schemes to calculate transaction priority will cope with that. Am I right in thinking that clients are likely to fail to relay and otherwise drop transactions with very low priority?
I must remark that I am very concerned that we do not introduce further incentives for miners to spam the network with transactions carrying fees in order to increase their own profits at the expense of everyone else. One important metric for the health of the network is the number of zero-fee transactions in blocks.
ByteCoin
Well a system that aims for security can not rely on self-asserted time, and there is no distributed secure time. If you start from a false assumption people will systematically abuse your assumption.
I know this as a principle, and also hard-won wisdom from real systems.
But, it's easier than ever before for a system to get a 'true' time, drawing it from the rest of the world: network services, radio signals, sunrise/sunset times. Though small numbers of systems can be faulted or frauded out of sync, systems for which this is economically important (like large mining combines) can get it right.
So though ugly in theory and provability, the assumption that most miners can consult and be rewarded to use an out-of-band 'true' time may work in practice. Or, may work as one of many informal hacks that deter sluggishness-for-profit.
Under the modification proposed, the miner can adjust self-asserted time in both directions, but his incentive is to report time as accurately as possible.
This is my intuition too. Since it is unpredictable when the miner's own next block, or a competitor's next block, will be found, there's no clear value other than 'now' (or maybe 'now+average_lag') to improve your block's tiebreaking power.
The same heuristic may also work with other timelike measures. As with Bytecoin's proposal, a miner could record when (by local time) they see each transaction. (A miner might even issue their own 'tick' transactions at regular intervals.) When receiving two competing blocks, they could prefer the one whose transaction-mix suggests a mining-time closest to receiving-time.
I know that there has traditionally been reluctance to assume accurate clocks (since NTP is seen as a central point of failure), but this appears to me to be a very weak dependency.
Well a system that aims for security can not rely on self-asserted time, and there is no distributed secure time. If you start from a false assumption people will systematically abuse your assumption.
Understood, but we aren't really relying on the self-asserted time are we? If we said that we give preference to the one with the earlier timestamp, or the one with the later timestamp, then people would certainly lie about their internal time. But given that we give preference to the block that matches our own internal timestamp the closest, it seems to me that the incentive is to be as accurate as possible with your self asserted time. As things stand today we are implicitly relying on self-asserted time in the sense that nodes assume that the time when a block is received is a good proxy for the time when it was mined. But, as selfish mining shows, this proxy is open to systematic abuse by the miner who mined the block and may choose to delay its broadcast. The miner can only adjust self-asserted time in one direction, but he has an incentive to do so. Under the modification proposed, the miner can adjust self-asserted time in both directions, but his incentive is to report time as accurately as possible.
I know that there has traditionally been reluctance to assume accurate clocks (since NTP is seen as a central point of failure), but this appears to me to be a very weak dependency.
Well a system that aims for security can not rely on self-asserted time, and there is no distributed secure time. If you start from a false assumption people will systematically abuse your assumption.
This is why for optimistic parallel discrete event simulation Lamport clocks were invented (some kind of vector of local clocks based on observed messages, to partially order transactions, and detect out of order relayed messages, without relying on clock sync, the only assumption is the clocks monotonically increase, they dont even have to be remotely accurate to wall-clock) - you want to progress the simulation with optimistically and roll-back when you later discover causality violations. But rollback is not such a hot idea in bitcoin, then your n-confirmed coins disappear at uncontrollable wall-clock delays. You do not ideally want to rely on clock accuracy or secure clock convergence protocol in a network with symbil attacks. Bitcoin may already depend slightly too much on clock convergence.
Also in crypto protocols for freshness proofs (anti-replay) people use a relying party generated nonce rather than time.
Heh maybe you can find a new 8th use for mining - a loose (+/- 10mins) sybil resistant clock convergence (same mining argument against byzantine generals). Maybe thats already happening I never did read how bitcoins internal clock sanity rules work.
Adam
For block-height ties, prefer the block whose locally-observed arrival time is closest to its internal timestamp.
Really like this idea.
Creates big incentives to screw with the subsecond accuracy of the network times.
Not sure I follow, could you give us an example of an attack? Has the anti-convergence property where if a first block is announced with a bad time you can keep trying instead of moving forward and you'll be sure to replace it unless you end up with a race with a child of it.
You could. But this would just be a new (and less potent) variation of selfish mining, which is only applicable "if a block is announced with a bad time" (which would happen a lot less often since nodes will be incentivised to keep their clocks accurate. More importantly it would not be a profitable strategy (compared to following the protocol). I know that there has traditionally been reluctance to assume accurate clocks (since NTP is seen as a central point of failure), but this appears to me to be a very weak dependency. Even if you had the magical capability to change the clocks on all network nodes when you want (not when they choose to sync) to whatever time you want (typically the time that is in the header of your selfishly mined block) you only end up with a selfish mining attack which we are vulnerable to today anyway. So as far as I can see no worse attacks become possible and the one we knew about becomes immensely harder. But this could just be a failure of imagination on my part.
My countermeasure for "Selfish" mining relies on the fact that pre-mined transactions from a selfish miner don't contain as many transactions of non-zero age from the memory pool. So conceptually, when a miner receives a transaction it should start a timer which measures the age of that transaction. When a block arrives it stops all the timers, sums the total age of all transactions in that block and stores this value against the block. As this is a product of transactions and seconds I propose it should be called "transactionseconds" (similar to bitcoindays) . If another block arrives then the number of transactionseconds for the new block is measured as if it had arrived at the same time as the previous block. The block with the highest number of transactionseconds is used to build the next block.
If another block arrives and the existing block chain rules indicate that a block should be orphaned then the transactionseconds of the longer block chain should be calculated as if all the blocks had arrived at once and the orphaning should not be successful unless the longer chain also destroys a larger number of transactionseconds.
If another block arrives and the existing block chain rules indicate that a block should be orphaned then the transactionseconds of the longer block chain should be calculated as if all the blocks had arrived at once and the orphaning should not be successful unless the longer chain also destroys a larger number of transactionseconds.
Careful, this means that in the presence of a selfish miner attack, anyone can DOS the network by sending thousands of tiny (in both kB and BTC terms) zero-fee transactions. Huge blocks stuffed full of these garbage transactions will win the transaction-seconds comparison against smaller blocks containing only normal transactions and once there are enough of these txs in the network to push us up against the block size limit, it becomes ineffective against the selfish miner attack anyway.
This can be alleviated somewhat by using transaction-fee-seconds as gmaxwell proposes, but even then, an attacker could build a maximum-size block that contains a bunch of insanely-high-fee transactions that it created itself and is keeping secret. As soon as it successfully builds a block, it publishes all the high-fee transactions, but not the block. This allows it to win any tx-fee-seconds races with competing blocks.
I wonder if transactionfee seconds is more interesting that transactionseconds?
By the way:
I really like your proposal, ByteCoin. I think it captures the intuitive notion of "incentivize publishing blocks immediately as the best policy".
IF all proof-of-work-valid chains are relayed (and, as I said, my intuition is that they should be) then highest-number-of-transactionseconds seems like a very good criteria for resolving ties.
I really like your proposal, ByteCoin. I think it captures the intuitive notion of "incentivize publishing blocks immediately as the best policy".
IF all proof-of-work-valid chains are relayed (and, as I said, my intuition is that they should be) then highest-number-of-transactionseconds seems like a very good criteria for resolving ties.
For block-height ties, prefer the block whose locally-observed arrival time is closest to its internal timestamp.
Creates big incentives to screw with the subsecond accuracy of the network times.How so? Also, assuming most nodes use a reliable out-of-band time source, who benefits from inaccuracy?
The 'true' time is a cooperative focal point that's hard to displace, barring such a large conspiracy that you're screwed anyway.
Quote
Has the anti-convergence property where if a first block is announced with a bad time you can keep trying instead of moving forward and you'll be sure to replace it unless you end up with a race with a child of it.
The point of anti-selfish-mining tactics is "anti-convergence", on chains preferred by the attackers. So suppressing "first blocks with a bad time" is a feature, not a bug.
Join the cooperating consensus, use the true time and broadcast any blocks you've mined (or chosen to build on) as fast as you can, or suffer.
For block-height ties, prefer the block whose locally-observed arrival time is closest to its internal timestamp.
Creates big incentives to screw with the subsecond accuracy of the network times. Has the anti-convergence property where if a first block is announced with a bad time you can keep trying instead of moving forward and you'll be sure to replace it unless you end up with a race with a child of it.
For block-height ties, prefer the block whose locally-observed arrival time is closest to its internal timestamp.
I was very pleased to read a recent paper by Eyal and Sirer which put on a rigorous footing something I had investigated in 2010.
I posted some comments to the bitcoin-dev list (cc the authors).
http://sourceforge.net/mailarchive/message.php?msg_id=31612133
Quote from: adam3us link=bitcoin-dev
(Talking about the paper, not the BIP). With regard to racing the other winner which catches up when private pool length=1:
i) the model does not appear to take into account that when another pool goes on to mine a block, and the attacker publishes their selfishly-withheld block, the selfish pool will not be able to change the existing winners mind. This is not insignificant as the pools have 30%, 20%, 15%, 7% etc.
ii) The miners already have an incentive, as other big bitcoin processors, to maintain fast, secure and redundant links to other significant miners.
The attacker is giving up a large proportion of their winnings from the times that they win at all. Say the attacker IS the 30% pool, when he wins and waits for someone else to win, > 80% of the network is pool mined, so there is a good chance that the other winner individually represents a non-negligible proportion of the network or a sufficiently well connected portion of the network that the attacker will be unable to race them to publication with a useful proportion of the network.
iii) Also broadcast is not instantaneous, lets say network propagation takes 10 seconds; a big proportion of the time, the actual mining times will be more than 5 seconds apart so that by the time the selfish miner learns of the block, much of the network will already have accepted it block as first.
iv) Even within the 10 seconds ambiguity period, the more powerful miner will tend statistically to come first, and so reach a bigger portion of the network, as well as having a stronger incentive to maintain links as in ii).
These four factors erode the achievable \gamma parameter. I suspect it unlikely \gamma>0.5 would be achievable, putting the profitable threshold \alpha in 25% - 33%. (And assuming whatever techniques to reduce latency are used by the selfish pools can be used by other pools.)
Your main result that even with \gamma=0 (if you dont win any races) that you still win once the selfish pool reaches 33% is an important new indication, which needs further consideration. (And you could expect to win some percentage \gamma>0 even with the factors I mention, and full
implementation of the same latency reduction techniques in all moderate sized miners, selfish and normal).
It is also not clear what will happen if multiple selfish miners compete with each other. A selfish miner cooperating as a peer to increase percentage runs risk of mutual sabotage - he has to announce his private block to his co-conspirator, and the co-conspirator may publish, or collude
with another non-selfish miner.
Your supposition is there is a profit motive to collude. However there are other profit motives in bitcoin that are not exercised - for example there were for sometime 2 pools that had excess of 50% power, and yet this was not abused for double spending. Of course increasing profit by a new mining strategy is not theft as double spending which has a clear loser. Miners even exercised restraint and volutarily avoided growing over 50%.
As others have I think said by now analysis is welcome. It seems that Peter Todd may have observed the same or something similar wrt miner incentives some months ago, though it wasnt as widely read nor formally verified.
It might be useful to release the source for your simulator if that is open to you.
In my opinion a constructive direction for reducing centralization risks is to try to reduce the use of and motivation for pools. Even at <51% per pool there is (probabilistic) miner risk in double-spends. And there is risk that the large miners evolve to become a defacto policy enforcement point for policies not aligned with user interests, or with fungibility of bitcoin which itself presents another kind of risk (defacto reduced fungibility should this arise would also be bad for bitcoin).
Also without even having mining power, there is scope to network hacking (eg of routers in front of miners) to influence the mining profit, and even double spend. As I mentioned large miners have an incentive to maintain secure redudant links (probably some links using Tor for blocks) as a counter-measure.
Adam
On Tue, Nov 05, 2013 at 11:56:53AM -0500, Ittay wrote:
> Hello,
> Please see below our BIP for raising the selfish mining threshold.
> Looking forward to your comments.
i) the model does not appear to take into account that when another pool goes on to mine a block, and the attacker publishes their selfishly-withheld block, the selfish pool will not be able to change the existing winners mind. This is not insignificant as the pools have 30%, 20%, 15%, 7% etc.
ii) The miners already have an incentive, as other big bitcoin processors, to maintain fast, secure and redundant links to other significant miners.
The attacker is giving up a large proportion of their winnings from the times that they win at all. Say the attacker IS the 30% pool, when he wins and waits for someone else to win, > 80% of the network is pool mined, so there is a good chance that the other winner individually represents a non-negligible proportion of the network or a sufficiently well connected portion of the network that the attacker will be unable to race them to publication with a useful proportion of the network.
iii) Also broadcast is not instantaneous, lets say network propagation takes 10 seconds; a big proportion of the time, the actual mining times will be more than 5 seconds apart so that by the time the selfish miner learns of the block, much of the network will already have accepted it block as first.
iv) Even within the 10 seconds ambiguity period, the more powerful miner will tend statistically to come first, and so reach a bigger portion of the network, as well as having a stronger incentive to maintain links as in ii).
These four factors erode the achievable \gamma parameter. I suspect it unlikely \gamma>0.5 would be achievable, putting the profitable threshold \alpha in 25% - 33%. (And assuming whatever techniques to reduce latency are used by the selfish pools can be used by other pools.)
Your main result that even with \gamma=0 (if you dont win any races) that you still win once the selfish pool reaches 33% is an important new indication, which needs further consideration. (And you could expect to win some percentage \gamma>0 even with the factors I mention, and full
implementation of the same latency reduction techniques in all moderate sized miners, selfish and normal).
It is also not clear what will happen if multiple selfish miners compete with each other. A selfish miner cooperating as a peer to increase percentage runs risk of mutual sabotage - he has to announce his private block to his co-conspirator, and the co-conspirator may publish, or collude
with another non-selfish miner.
Your supposition is there is a profit motive to collude. However there are other profit motives in bitcoin that are not exercised - for example there were for sometime 2 pools that had excess of 50% power, and yet this was not abused for double spending. Of course increasing profit by a new mining strategy is not theft as double spending which has a clear loser. Miners even exercised restraint and volutarily avoided growing over 50%.
As others have I think said by now analysis is welcome. It seems that Peter Todd may have observed the same or something similar wrt miner incentives some months ago, though it wasnt as widely read nor formally verified.
It might be useful to release the source for your simulator if that is open to you.
In my opinion a constructive direction for reducing centralization risks is to try to reduce the use of and motivation for pools. Even at <51% per pool there is (probabilistic) miner risk in double-spends. And there is risk that the large miners evolve to become a defacto policy enforcement point for policies not aligned with user interests, or with fungibility of bitcoin which itself presents another kind of risk (defacto reduced fungibility should this arise would also be bad for bitcoin).
Also without even having mining power, there is scope to network hacking (eg of routers in front of miners) to influence the mining profit, and even double spend. As I mentioned large miners have an incentive to maintain secure redudant links (probably some links using Tor for blocks) as a counter-measure.
Adam
On Tue, Nov 05, 2013 at 11:56:53AM -0500, Ittay wrote:
> Hello,
> Please see below our BIP for raising the selfish mining threshold.
> Looking forward to your comments.
Adam
ps Presumably you sent the authors an email with a link to this bitcointalk topic thread?
[edited for politeness at request of topic starter]
http://en.wikipedia.org/wiki/Folk_theorem_(game_theory)
Q: What does the folk theorem tell us?
A: Whether or not selfish mining has positive payoffs in the short-run is irrelevant. Miners are holding on to valuable assets, their ASICs.
Their incentive problem is not just maximization of short-run mining profits, but maximization of the joint sum of mining profits and capital gains (or losses) on ASICs.
The ASICs are useless except for bitcoin mining. That's just great because it gives miners a stake in the system (maybe not as elegant as proof-of-stake, but a stake nonetheless)
Now let's say that these guys are right and that if one selfish miner appears then we will snowball into eternal selfishness. What does the folk theorem say about this?
It says "Hey that's wonderful news, we can rest assured that we will never ever ever see a selfish miner. Such a miner would be attaching a time bomb to his ASICs. And that's just silly."
When you see some people dynamiting their ASICs for profit let me know and I will reconsider my views on the matter.
http://en.wikipedia.org/wiki/Folk_theorem_(game_theory)
Q: What does the folk theorem tell us?
A: Whether or not selfish mining has positive payoffs in the short-run is irrelevant. Miners are holding on to valuable assets, their ASICs.
Their incentive problem is not just maximization of short-run mining profits, but maximization of the joint sum of mining profits and capital gains (or losses) on ASICs.
The ASICs are useless except for bitcoin mining. That's just great because it gives miners a stake in the system (maybe not as elegant as proof-of-stake, but a stake nonetheless)
Now let's say that these guys are right and that if one selfish miner appears then we will snowball into eternal selfishness. What does the folk theorem say about this?
It says "Hey that's wonderful news, we can rest assured that we will never ever ever see a selfish miner. Such a miner would be attaching a time bomb to his ASICs. And that's just silly."
When you see some people dynamiting their ASICs for profit let me know and I will reconsider my views on the matter.
I have several partly-formed thoughts.
First, on "is there REALLY a problem" -- I think Ed Felten makes a good argument that, at least in the current world of mining pools, the incentives work to prevent "selfish" mining: https://freedom-to-tinker.com/blog/felten/bitcoin-isnt-so-broken-after-all/
Related, I think it is important to remember that the current structure and behavior of the p2p networking code is NOT part of the fundamental consensus algorithm. It is easy to change, and, as I've said in the past, I would really like to see blocks and transactions being broadcast over some completely different networking protocol.
I think there is a really interesting theoretical question that I don't know the answer to; I'll try to state it clearly:
As the p2p network is currently implemented, nodes only have a partial view of competing best-chains, because nodes only relay the first node they see at a given height.
If there are two blocks at the same height announced at approximately the same time, they propagate exponentially fast across the network in two waves, and only the nodes at the edges of where the waves meet will see both blocks.
Given that network behavior, assuming no selfish mining, there is a strong incentive to announce your block as soon as possible, because in an exponentially fast race any delay is very likely to make you lose.
There are lots of ideas for fixing selfish mining that rely on changing that behavior, and having nodes relay orphan blocks. I think it is important to remember that no matter what rules we SAY the network will follow, we can't stop individual nodes from implementing whatever rules they wish to follow; any solution that begins "If all nodes do THIS..." is not a solution.
That applies to the behavior we have now about not relaying orphan blocks, too, of course. The interesting theoretical question I'm pondering: does the security of the Bitcoin system depend on the relaying behavior, or on how ties are resolved in block races?
My intuition is that we SHOULD be relaying all orphan blocks, and should let each node decide how to resolve races, but before we talk about how to resolve races I think we should consider the incentives that arise from the current relaying behavior.
First, on "is there REALLY a problem" -- I think Ed Felten makes a good argument that, at least in the current world of mining pools, the incentives work to prevent "selfish" mining: https://freedom-to-tinker.com/blog/felten/bitcoin-isnt-so-broken-after-all/
Related, I think it is important to remember that the current structure and behavior of the p2p networking code is NOT part of the fundamental consensus algorithm. It is easy to change, and, as I've said in the past, I would really like to see blocks and transactions being broadcast over some completely different networking protocol.
I think there is a really interesting theoretical question that I don't know the answer to; I'll try to state it clearly:
As the p2p network is currently implemented, nodes only have a partial view of competing best-chains, because nodes only relay the first node they see at a given height.
If there are two blocks at the same height announced at approximately the same time, they propagate exponentially fast across the network in two waves, and only the nodes at the edges of where the waves meet will see both blocks.
Given that network behavior, assuming no selfish mining, there is a strong incentive to announce your block as soon as possible, because in an exponentially fast race any delay is very likely to make you lose.
There are lots of ideas for fixing selfish mining that rely on changing that behavior, and having nodes relay orphan blocks. I think it is important to remember that no matter what rules we SAY the network will follow, we can't stop individual nodes from implementing whatever rules they wish to follow; any solution that begins "If all nodes do THIS..." is not a solution.
That applies to the behavior we have now about not relaying orphan blocks, too, of course. The interesting theoretical question I'm pondering: does the security of the Bitcoin system depend on the relaying behavior, or on how ties are resolved in block races?
My intuition is that we SHOULD be relaying all orphan blocks, and should let each node decide how to resolve races, but before we talk about how to resolve races I think we should consider the incentives that arise from the current relaying behavior.
I was very pleased to read a recent paper by Eyal and Sirer which put on a rigorous footing something I had investigated in 2010.
I mentioned at the time that there were a number of different strategies which a selfish miner could follow. I found the one that appeared to appeared to become worthwhile at 34% which is the one outlined in section 4.2 of the linked paper. The fact that it pays off at 34% is mentioned in section 4.4 and apparent from Fig.3
Although their paper is substantially correct, I believe the authors neglect the fact that (if I recall correctly) the optimum strategy changes when the percentage of hashpower is between 33% and 50%.
The linked forum topic shows how I was unable to convince Gavin that this mining strategy was viable. I hope that the recent paper and publicity will lead him to reconsider.
My concern at the time was to show how the mining incentives in place encourage the formation of cartels. This is still a problem and I can imagine the bitcoin network reaching a steady state with two mining pools the large one verifiably "honest" and the smaller one "selfish" whereby the presence of the selfish mining pool is tolerated (and even encouraged) by the larger "honest" pool because it suppresses competing smaller "honest" pools. The selfish pool can pay "protection money" to the honest pool either directly out of the coinbase or more covertly by including in the "selfish blocks" double spent transactions which fund new transactions paying a large fee (the success of this scheme depends on the absence of forfeiture of double-spent coins).
As time goes by and fees become large compared to the block reward, miners will of course feel the incentive to build on or orphan blocks based on their share of fees after any block reorganization. It is easy for a miner to appear honest and still participate in cartel activity as it is hard to prove in what order the miner received blocks.
My countermeasure for "Selfish" mining relies on the fact that pre-mined transactions from a selfish miner don't contain as many transactions of non-zero age from the memory pool. So conceptually, when a miner receives a transaction it should start a timer which measures the age of that transaction. When a block arrives it stops all the timers, sums the total age of all transactions in that block and stores this value against the block. As this is a product of transactions and seconds I propose it should be called "transactionseconds" (similar to bitcoindays) . If another block arrives then the number of transactionseconds for the new block is measured as if it had arrived at the same time as the previous block. The block with the highest number of transactionseconds is used to build the next block.
If another block arrives and the existing block chain rules indicate that a block should be orphaned then the transactionseconds of the longer block chain should be calculated as if all the blocks had arrived at once and the orphaning should not be successful unless the longer chain also destroys a larger number of transactionseconds.
We don't just compare the number of memorypool transactions included in the different blocks as that would give the selfish miner an incentive to stuff their selfish blocks with dummy transactions (which could pay themselves hefty fees to allow themselves to bloat the block).
There's no point for non-miners really to have an opinion about which block is better but if they see blocks destroying large numbers of transactionseconds being orphaned by blocks destroying small numbers of transactionseconds then they can be pretty sure that something fishy is going on!
ByteCoin
PS If I am allowed, I intend to moderate this thread to remove posts which are off topic or do not contribute positively to discussion of cartels, selfish mining, incentives or Eyal and Sirer's paper.
I mentioned at the time that there were a number of different strategies which a selfish miner could follow. I found the one that appeared to appeared to become worthwhile at 34% which is the one outlined in section 4.2 of the linked paper. The fact that it pays off at 34% is mentioned in section 4.4 and apparent from Fig.3
Although their paper is substantially correct, I believe the authors neglect the fact that (if I recall correctly) the optimum strategy changes when the percentage of hashpower is between 33% and 50%.
The linked forum topic shows how I was unable to convince Gavin that this mining strategy was viable. I hope that the recent paper and publicity will lead him to reconsider.
My concern at the time was to show how the mining incentives in place encourage the formation of cartels. This is still a problem and I can imagine the bitcoin network reaching a steady state with two mining pools the large one verifiably "honest" and the smaller one "selfish" whereby the presence of the selfish mining pool is tolerated (and even encouraged) by the larger "honest" pool because it suppresses competing smaller "honest" pools. The selfish pool can pay "protection money" to the honest pool either directly out of the coinbase or more covertly by including in the "selfish blocks" double spent transactions which fund new transactions paying a large fee (the success of this scheme depends on the absence of forfeiture of double-spent coins).
As time goes by and fees become large compared to the block reward, miners will of course feel the incentive to build on or orphan blocks based on their share of fees after any block reorganization. It is easy for a miner to appear honest and still participate in cartel activity as it is hard to prove in what order the miner received blocks.
My countermeasure for "Selfish" mining relies on the fact that pre-mined transactions from a selfish miner don't contain as many transactions of non-zero age from the memory pool. So conceptually, when a miner receives a transaction it should start a timer which measures the age of that transaction. When a block arrives it stops all the timers, sums the total age of all transactions in that block and stores this value against the block. As this is a product of transactions and seconds I propose it should be called "transactionseconds" (similar to bitcoindays) . If another block arrives then the number of transactionseconds for the new block is measured as if it had arrived at the same time as the previous block. The block with the highest number of transactionseconds is used to build the next block.
If another block arrives and the existing block chain rules indicate that a block should be orphaned then the transactionseconds of the longer block chain should be calculated as if all the blocks had arrived at once and the orphaning should not be successful unless the longer chain also destroys a larger number of transactionseconds.
We don't just compare the number of memorypool transactions included in the different blocks as that would give the selfish miner an incentive to stuff their selfish blocks with dummy transactions (which could pay themselves hefty fees to allow themselves to bloat the block).
There's no point for non-miners really to have an opinion about which block is better but if they see blocks destroying large numbers of transactionseconds being orphaned by blocks destroying small numbers of transactionseconds then they can be pretty sure that something fishy is going on!
ByteCoin
PS If I am allowed, I intend to moderate this thread to remove posts which are off topic or do not contribute positively to discussion of cartels, selfish mining, incentives or Eyal and Sirer's paper.
Jump to: