I believe a system should by secure by-design and not by anything else. It is true that a system may have some weaknesses and yet practically be quite safe, but this is not preferable. Fortunately for most of the problems we do have simple solutions, and as long as a solution causes no further problem I think it should be implemented.
 
If it was the case that there is not possible secure modification of the PoW structure which is suitable to current ASICs, then maybe we better put with the weakness (there are other ways to counter block discarding attacks, such as my "fork punishment" proposal). As far as I'm concerned, Bitcoin ASICs' designs are not open source so neither me and you can know for sure whether a concrete modification is applicable or not. Yet I think that ASIC machine has a unique set of op-codes (such as SHA-256 compression function) and can be programed to run different codes. Do you know that Sony Playstation machines have been used to run cryptanalysis programs? Dedicated hardware can be very flexible!
 
I have no intention to argue about off-topic issues that have been thoroughly discussed in other threads, yet I will just note that there is an incentive for selfish mining: increased mining profits. Such an attack will most probably not cause the total destruction of the system (it will just cause some honest miners to earn less, and the dev team to implement proposals like mine's). Moreover, I don’t think we should make any assumptions about the attacker intentions and incentives: the attacker may theoretically want to harm the system (say if it is a terror organization, the Chinese government, or more likely the NSA).

I will say it again: a system should be secure by design and not by anything else!

One last thing: it is OK to criticize academy, just please remember that Bitcoin is built upon cryptographic elements that were all invented by the academy. We don’t know who Nakamoto is, but I am quite sure he is an academician. Nevertheless I absolutely agree with you that academicians should not say "Bitcoin is broken" whenever a new weakness have been found.

Lear
 

Hi gmaxwell,

I agree with you that the threat of the 51% attack is not much increased by this weakness, yet the vulnerability to selfish mining is: say there are bad miners whose total hash-power is only 30% of the total network's hash-power. Despite the selfish mining attack being profitable to an attacker having 30% of the total network's hash-power, it is not trivial to actually perform this attack. If one of the bad miners is a traitor (i.e. a good miner), this miner can discretely publish all the blocks that the pool wants to keep secret, and thus preventing the attack – unless the pool miners just don’t know the previous (secret) block. The bad miners will have no problem mining on top of unknown blocks, as long as they receive their (increased…) rewards. So this is not a pure theoretic attack. Yet I agree with you that this is not an immediate threat.

As for the ASICs:  the Bitcoin dedicated hardware can compute SHA-256 really fast. As long as we continue to use the SHA-256 compression function, there is no need to switch to a new hardware – just to modify the program of the ASIC machines. Consider for example my proposal of requiring that the outcome will be close to the (upper 128 bits of the) previous block's hash rather than being close to zero.  

Lear.

I have recently discovered a weakness of the way Proof of Work is currently implemented in Bitcoin. In this post I show how a miner can mine a valid block without knowing on top of which previous block he/she mines, and without even knowing the hash of the previous block. Then I explain the consequence of this weakness on the real world possibility of  51% attack and selfish mining / block discarding attacks. Simple protocol modifications are proposed and discussed at the end of the post.

Mining without knowing the hash of the previous block
We are all familiar with the proof of work (PoW) concept, and we all know that a certain hash of the block-header of any valid Bitcoin block must be lower than the corresponding target, yet the specific technical implementation of PoW is less discussed. All details can be found in the wiki or in this recent interesting paper.

For simplicity let's say that the block-header is the concatenation of the previous block's hash, root of the current block's merkle tree, and a 32bit short nonce, in this order. Note that the first two fields are of 256 bits each. In reality the block header contains also a timestamp and other data we shall ignore in order to make the weakness clearer. The SHA-256 hash function is applied twice over the block header (meaning, first SHA-256 is calculated over the header and then SHA-256 is calculated over the outcome of the previous calculation), and the result should be lower than the target.

Since the current difficulty is higher than 60 bits and the short nonce contains only 32 bits, once every 2^32 double-SHA-256 calculations the Merkle-tree must be changed in order to refresh the block-header (in fact, the coin-base transaction of the tree contains some extra-nonce as a special field). Moreover, pool miners are used to modify the coin-base transaction of the Merkle-tree not only for block-header refreshing, but also in order to mark the block so that the pool owner can reward them for their shares.

Let's say that the pool organizer sends all pool members (different) lists of merkle-tree roots. Each pool miner then try all 2^32 possible combinations for the short nonce, before taking another root and start all over again. The miner doesn’t need to know the actual merkel-tree, because the pool organizer has already marked it for him/her. Now here is the key point: SHA-256 is a Merkle-Damgard hash function that iteratively compresses 512 bits blocks of the input data. So the first step of calculating SHA-256 over the block-header is compressing the first 512 bits, which are the concatenation of the previous block's hash with the Merkle tree root. After this step those 512 bits are unneeded, hence the pool organizer may just send the pool miners a list of compressed concatenations of the previous block's hash with some Merkle tree root.

Since the compression function of SHA-256 is one-way and the Merkle-tree roots are effectively random numbers, the pool miners cannot discover the hash of the previous block. In other words, they are mining valid blocks without knowing on top of which previous blocks they mine.

Implications
Recently Eyal and Sirer published a paper describing the "selfish mining" attack. Unfortunately I was independently working on the same attack, but they have published their results first (and refused to share the credit with me…). Anyway, I have published my results too and since the Block Discarding Attack is more general and comprehensive I advise you to read my paper too.

I have claimed that the Block Discarding Attack / Selfish Mining is not applicable to pools, and have just changed my mind about that due to the possibility of mining without knowing the previous block's hash. Assuming pool miners must know the previous block's hash, it can be shown that in practice the selfish mining attack cannot work properly if the attacker is a pool:  the attack is based on two contradicting requirements. The first is the ability of pool miners to keep in secret blocks they have found but have not released yet (the pool miners will mine on top of this secret blocks while the honest network mines on older blocks). The second is the acceptance of new miners to the pool (who want to join the pool so they will not suffer from reduced profits due to the attack).

Because anyone can join the pool, including other pools organizers or sites like blockchain.info (note that miners are anonymous), and because pool miners are expected to mine on top of the secret block (whenever there is such a block), assuming that mining can only be done when the previous block hash is known, the hash of any withholded block is expected to be published by some of the pool unfaithful miners. When this hash is published, non-pool miners can also mine on top of it, making the attack impossible (Asaf Ziv, a friend of mine, have noted that in such a situation the pool organizer can choose not to reveal the full block whose hash have been published. However by doing so the pool loses a single block and the honest network loses only a single block too, so this is unprofitable unless the pool has more than half of the total computational power).

Anyway, a pool can use the technique presented here so that unfaithful pool miners will not be able to publish the secret block (or its hash). The only thing they can do is to publish the compressed concatenations of the secret block's hash with a Merkle tree root whose coin-base transaction rewards the pool organizer 25 Bitcoins. Obviously, this cannot harm the pool.

As for the 51% attack, a group of pool organizers whose total hash-power exceeds the hash-power of the rest of the network can use the describe technique to anonymously perform 51% attack, without being affiliated with the attack not even by pool miners! The pool organizer can use new address in the (initially secret) coin-base transactions, so that whenever a valid block is mined by one of the pool miners, only this miner is expected to know that the pool participates in the attack. Because I don’t know of any honest advantage of this technique, my observation about the 51% attack is probably insignificant: honest pools, or pools that pretend to be honest, will simply not use this technique, and thus no honest pool miner will be tricked to participate in any attack.

Protocol modification
The Bitcoin protocol can be slightly modify so that mining without knowing the previous block's hash (and may be the Merkle tree root too) will not be enabled. There are many possibly ways to do so, of which the most simple is probably reversing the order of the block-header's fields so that the nonce becomes first. Other possibilities include: concatenating the block-header to itself and computing a single SHA-256 over the doubled block-header; Xoring the previous block's hash to the outcome of the first SHA-256 iteration before doing the second SHA-256 iteration; requiring that the outcome of the second SHA-256 iteration will be a number bigger than 2^-128 times the previous block's hash and smaller than 2^-128 times the previous block's hash plus the current target; etc.

Along with the weakness of mining without knowing the previous block's hash, there is another weakness, which is the possibility of non-trivial mining optimizations, i.e. the existence of better mining algorithms than simply calculating the regular SHA-256 function. One such optimization is described here. When I have the time, I intend to look for optimization of mining multiple blocks on top of the same block, for example mining two blocks on top of the same block so that it will only take 1.5 times more calculations than mining a single block (this might have bad implications over the GHOST proposal).

I think the current protocol should be changed in the near future, so that it will have no weakness due to the specific use of SHA-256.


Lear.
 

Hi,

I have been thinking about enabling secure zero-confirmation (and even completely offline) transactions, using special contracts with a third party. My construction doesn’t claim to be 100% secure, but secure enough so that if I stop by some roadside stall without any internet connection I'll be able to buy and the vendor well be able to accept my transaction without being afraid too much of double spending.

Following are some varieties, and I am sure there are many more, but the core idea is that I can sign a special commitment saying that X of my Bitcoins are frozen until tomorrow and can be used only for at most X/L transactions that each one transmits at most L Bitcoins to an address that is approved by a certain certificate authority (CA). Until tomorrow I can't transfer any of this frozen money to an address which is not approved by the CA; I can't make more than X/L such transaction; and I can't have multiple transactions with the same (approved) address if the total sum is more than L Bitcoins.

The CA is going to charge vendors for providing them certificates, and makes sure no vendor receives more than a single approved address. After a transaction have been made, and the vendor have finally connected to the internet, the transaction can be included within a block only if the vendor sends along with the transaction the CA certificate of the address; there are at least L unspent frozen Bitcoins of the buyer; and the transaction is of no more than L Bitcoins combined with all previous transactions with the same address.

Basic security
The only way a buyer can trick the vendor is by spending all the frozen money before the vendor connects to the internet. Since a buyer can spend at most L Bitcoins on each vendor, he must run through more than X/L different vendors during a relatively short time. If we are interested only in zero-confirmation transaction and not offline transaction, that means the attacker has to visit X/L different places within approximately 10 minutes. That is quite difficult. A bunch of thieves sharing the same private key can nevertheless do so, but the more thieves are involved the bigger is their risk of getting caught.

Making the CA more involved
A possible way to strengthen the basic security is by making the CA more involved: for a higher certificate charge, the CA can partly or fully compensate the vendor for double spending cases. That's way the CA will have a strong incentive to approve only reliable vendors (and no vendors that might sell their approved address for the thieves).
 
Approving also the buyers
The CA may approve potential buyers that are willing to be registered (and thus compromise their privacy). Vendors may refuse to accept offline payments from unapproved buyers, so in case of a double spending they can contact the CA and ask for the buyer's details that will be delivered to the police. The anonymity compromising is limited, at least if you trust the CA for not sharing this information without a reason and trust yourself to protect well your private key (if someone steals your private key and commits double spending, your details will be shared).

So… what do you think about it?

Lear

Hi,

I think that one possible alternative to (securely) accelerate blocks creation is to combine the following proposals: http://www.tik.ee.ethz.ch/file/49318d3f56c1d525aabf7fda78b23fc0/P2P2013_041.pdf and http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03307.html. Basically, the information-propagation paper propose to introduce special kind of messages, that deliver only the block header (including the nonce) so that it will still be possible to validate the PoW (and therefore DoS attacking the system by spamming fake headers is not possible), in order to make blocks propagate faster. Peter Todd suggests allowing blocks to contain invalid transactions, e.g. double spending of money that was already spent in some earlier block. Adopting the first spending transaction and ignoring all letter attempts is enough to maintain security.

So if a miner founds a new block and separately propagates the block header and the block itself (or even only a list of the transactions' hashes), propagation of the block header will quickly inform all the network of the new founded block, and miners can start mining on top of that block even if they have not received yet the block itself. In the worst case, the second miner might include transactions that were already included in the previous block or other invalid transactions (of whom he/she we get no fees).

Yet a possible problem with that solution is regarding the Bloom filter technique, which doesn’t work well if invalid transactions are included in the blocks. So I would like to propose here a possible solution for that, by punishing double spenders: each transaction must include a minimal deposit that is unlocked only after a few blocks (for example, 10) and only in case no earlier double spending transaction have been found. However if there has been such an earlier transaction, the deposit money will be destroyed (may be part of it can be used to compensate the miner who mined the block that contains this invalid transaction). Obviously, if the same exact transaction has been included twice within different blocks in the chain, it will not be regarded as a double-spending transaction.

I personally much prefer the GHOST proposal, and think it will be more efficient.

Lear.

Hi,

I have post my suggestion for GHOST implementation, aiming to solve the centralization/unfairness of mining problem, and to reduce the vulnerability to convergence attacks (by making it much more difficult to effectively release old-mined blocks). Here is the link to the thread, and I will appreciate any of your comments:  https://bitcointalk.org/index.php?topic=396350.msg4278073#msg4278073.
 
Lear.

Hi,

Let's reexamine proposition 8.1 and claim 8.2 of the paper, that say there will always eventually be a convergence ("collapse") to the next chain block and this convergence takes in expectation a finite time.

The proof is based on the fact that for any finite interval of time, there is a positive constant probability of the event where no new block is created anywhere in the network during a period of time of this interval's length. The problem is that you implicitly assume all miners immediately release any block they have found, and we know this is untrue. So you cannot simply derive that on some point all the nodes in the network will have exactly the same information without assuming that all nodes are honest!

If the average time of creating a new block in the tree is longer than the network diameter, your proof is nevertheless valid. Else, theoretically there is a positive probability that the network will never come to a point of sharing exactly the same information, since withholded blocks might be released once every d seconds where d is the network's diameter.
 
Now let me describe a possible DoS attack that tries to prevent convergence. We take the approach of the paper to have a simplified network of only two honest nodes, while noting that a similar attack is applicable to a more complex network. Say we have two honest nodes whose connection having a delay of d that is relatively big compared with the mean time of block creation.

Say we have two more nodes controlled by the same attacker, each one is adjacent to one of the two honest nodes, so that the delay between the pair is negligible compared to d. The two attacker's nodes may be connected by a special secret channel whose delay is lower than d, or may have no direct connection at all. Having such a special connection can only reduce the attacker's required fraction of total hash-power, but this is not crucial for the attack success. (Nevertheless I think it is most probable that such a faster channel may exist, because in reality the attacker can skip validation of directly transmitted data between his nodes, or even send only data about the number of created blocks instead of the block themselves. On the other hand those two honest nodes are actually two "centers" of the network and the delay between them is caused by having a path of at least several nodes between them…).

Let the two honest nodes have about the same hash-power, and the two attacker's nodes have relatively small hash-power compared with the honest nodes. Due to the delay, one honest node is informed only of his blocks and the released blocks of his adjacent attacker, as well as the blocks of the other honest node and the released blocks of the other attacker's node that were not released at the last d seconds. Therefore it is possible that the other honest node is working on a branch that is actually heavier that the branch the first honest node is working on, because first honest node wrongly thinks that his branch is the heavier. The attacker is trying to always fool the honest node that mines on the less heavy branch, so that the honest nodes will never converge to the same branch.

In order to analyze the required hash-power of the attacker needed so that with a positive probability there will never occur a "collapse" (in contradiction to proposition 8.1), we shall slightly modify our model so it will be easier to mathematically analyze it: instead of saying a honest node will continue to mine on his initial branch until a point where the competitive branch has been heavier already d seconds before, we say that he continues to mine on his initial branch unless the other branch is heavier by k blocks or more (ignoring any delays). In a sense having a delay can be shown to be equivalent of having such k > 0. Moreover, on reality there is no such fixed delay d, so I am not sure that the model of having a fixed corresponding k is less realistic than having a fixed delay d.

The attack goes as follows: each of the attacker's nodes keeps mining in secret on top of the branch of its adjacent honest node, and whenever the competitive second branch is reaching a tie from the point of view of the two nodes working on the first branch, meaning it is actually leading by k blocks) the attacker's node release a single block that breaks the tie in favor of its adjacent honest node. So the question is what is the minimal required hash-power of the attacker so that there is a positive probability that he will never run out of blocks when he needs to release a new block? (In fact the attacker might temporarily run out of blocks, so the network will temporarily collapse to one of the branches, but the attacker may later succeed mining the required block to reverse the collapse. We ignore that for simplicity).

Mathematically, we have a random walking on the 2k-1 numbers: 0, +-1, +-2, … +-(k-1). Each step is forward with probability 1/2 and backward with probability 1/2, where "forward" of (k-1) is regarded as (k-1) and backward of -(k-1) is regarded as -(k-1), as long as the attacker hasn’t run out of secret blocks. This simple Markov process can be shown to define a uniform distribution over the set of legal positions, therefore each of the attacker's nodes have to release a single block every 2(2k-1) blocks in expectation. So the minimum required hash rate of the attacker is 1/(2k-1) of the total honest hash-power, or 1/2k of the total network's hash-power.

The bigger is the delay d with respect to the average time it takes to create a new block, the bigger is k, and the closer to zero is the required hash-power of a successful attacker. Therefore I am afraid that 1 second per block-chain block (which is less than 1 second per a block in the tree!!) is just too much. Yet I am sure GHOST is a revolutionary proposal that can much improve the very low current rate of 10 minutes per block.

The last thing I would like to note is that vulnerability to the same kind of convergence attack isn’t unique to GHOST, but to any system whose delay is relatively high compared with the average time per block. If Bitcoin blocks will be *much* increased (a lot more than the current 1MB maximum) and as a result the delay will increase too, it will be possible to attack Bitcoin similarly.

Yet a major difference is that in Bitcoin the attacker cannot keep secret blocks and release them later, as this will have no effect. Therefore the attacker should always mine on top of the shorter chain, and hopes that the difference between the lengths of the competitive chains will not grow too much. Theoretically it can be shown that no matter how much hash-power the attacker has, eventually this gap will reach any natural number. As this might take a very long time, I still consider such an attack valid.


Lear

Well, you could have said exactly the same things about Bitcoin back then when it was just a paper: how nodes in the Bitcoin network are forced to select the longest chain? No one force them. Preferring the longest chain is just a convention, yet if everybody else act according to this convention, you better follow them or else your mining becomes meaningless. The same is true for GHOST.

You asked how nodes will be informed of all tree blocks, and is done simply by propagating valid blocks like today. As there are more blocks to propagate indeed there is a higher chance for someone to miss a block. I think that the standard protocol solves that continuously comparing the list of recent block hashes with the node's neighbors, yet this can be further improved by including previous off-chain blocks' headers within each block (those blocks are off-chain with respect to the chain forms by the block that contains their headers). In my suggested implementation blocks are actually incentive to inform about competitive chains!
 
No one doubts that the original Bitcoin creation is genius, yet even Gavin Andresen is saying that it will not last forever without modifications. So we better be open-minded to look for the next genius creation  

Lear

Let me put it this way: currently, reducing the time intervals between blocks harms both security of the system and mining fairness (having the profits depends only on the hash-power and not on network connectivity). The GHOST proposal enables reducing the average interval without harming security while unfortunately harming mining fairness. My proposal enables to do so also without harming much mining fairness.

So I agree with you that making this interval about a second might be just too much despite GHOST (and my improvements), yet I don’t quite see why are you thinking 10 minutes is the right interval… we already have functioning alt-coins that works pretty well with 2.5 minutes and without GHOST!

As for the academia, I think it is quite diverse: sometimes (and I believe this paper is such an example) the border between the "real world" and academy is really unclear, while sometimes the theory is so different that the practice and might only be relevant long time into the future.   

Well, Bitcoin was designed 6 years ago by a mysterious individual and before there have been any such similar system. Since then there have been so many progressions, new ideas and new coins, and we now have so much knowledge that Satoshi hadn’t while designing the original protocol. So I don’t think that any arbitrary choice made by Satoshi is neither the only possibility nor the best one…

 What the authors are basically saying is that there is no need to make the average interval so long that there will almost be no natural occurring forks, meaning this interval doesn’t have to be much bigger than the network delay. So you may think that 1block per second is too optimistic, but you must agree with the authors that GHOST can get the interval significantly shorter…

Indeed I agree with you that this novel idea should be checked in reality before we make any change to Bitcoin (perhaps by building a new crypto-coin), yet I am very optimistic about that! The authors based their claims on empirical results of the Bitcoin network and their work seems very reasonably to me (not like many other academic paper that have some unrealistic claims).

Lear

It should be noted that theoretically there is a bug in my rewarding mechanism: if all miners unite to form as many blocks as they can on top of one single block, and after 4 months or so include all blocks' headers within a single block, then they might be rewarded more money than the total sum of taxes (i.e. making the Bitcoin Security Reserve in overdraft).

This obviously is really unlikely, yet if someone is nevertheless interested in a solution, we can simply limit the number of block headers included in a single block to be at most 10 for say…

Hi all,

Recently Yonatan Sompolinsky and Aviv Zohar have published an important paper in which they suggest a protocol change for Bitcoin, named GHOST:  Greedy Heaviest Observed Sub-Tree. Basically the paper shows that the mining rate (or equivalently, the expected interval between consecutive blocks in the chain, which is 10 minutes in Bitcoin) can be much accelerated without compromising the security of the system, by simply accepting the blocks that form the heaviest sub-tree instead of always accepting those who form the longest/heaviest chain. Here is a link to the paper: http://www.cs.huji.ac.il/~avivz/pubs/13/btc_scalability_full.pdf.

On this thread I would like to propose a different implementation for GHOST than the one described in the paper. My proposal arguably solves a major potential weakness of GHOST that is decently noted in the paper, as well as two other known weaknesses of Bitcoin which are magnified by GHOST: vulnerability to Block Discarding Attacks (like "selfish mining"), and the expected mining tragedy of the commons that might cause the honest hash-power to decrease in case the fees won't be able to compensate the decreased basic block rewards.
 
Basically, although the accelerated mining rate doesn’t (directly) increase the vulnerability to 50% hash-power attacks when using GHOST, it does theoretically increase the decentralization of the system: as there are more forks to the chain, the probability of a miner to get an eventually confirmed block within a certain period of time, is the probability of succeeding to form a valid block within that period, times the probability of a valid block to get eventually confirmed. The first probability is linear as a function of the miner's computational power, while the second isn’t constant as it depends upon the miner's network connectivity.

Thus, 1000 small miners are expected to collectively gain less confirmed blocks than one strong miner with the same total hash-power, simply because the strong miner would be faster informed of any new mined block and faster propagate her/his blocks, in order to improve her/his blocks confirmation probability. Moreover, since Block Discarding Attacks can be much amplified by network superiority (meaning, the connectivity advantage of the attacker over the average miner), the accelerated mining rate might increases the system vulnerability to those attacks.
 
I therefore propose to reward (almost) all orphan blocks just a bit less than the confirmed block's reward. In order to do so I suggest having a mandatory tax on transactions, founding the "Bitcoin security reserve" account. Both confirmed and orphaned blocks get rewarded by the security reserve, while miners of the confirmed blocks may collect fees in addition. Since block mining is accelerated, each block contains less transaction, so the income from fees is supposedly negligible compared to the reward.

The specific proposed implementation goes as follows:

Mining rate
6 seconds per (confirmed) block, at least. Difficulty is smoothly adjusted according to the formula
Dif_n+1 = dif_n * ( 1  +  (time_n – time_n-1) / two weeks  -   (6 seconds / two weeks) )
where dif_k  and time_k are correspondingly the difficulty and the timestamp of the k-th block.

Mandatory security tax
The tax on transaction transferring X Bitcoins is \alpha + x*\beta, meaning a constant minimal tax plus a very small percentage of the transaction. \alpha and \beta should be chosen such that the expected total taxes sum within 10 minutes is about 25 BTC, or some other security parameter.

Blocks rewarding
With respect to a certain chain, we say a block is of 0-degree if it is a member of the chain; of 1-degree if its parent is a member of the chain, of 2-degree if its parent's parent is a member of the chain, etc. I suggest rewarding the 0-3 degree blocks with 100%, 90%, 75% and 50% (correspondingly) of the average reward of a confirmed block. Blocks of degree 4 or more should not be rewarded at all.

Inspired by the fork-punishment mechanism of http://eprint.iacr.org/2013/868.pdf, block headers of 1-3 degree blocks will be included, using a special syntax, within confirmed blocks. Block headers should be changed to include their miners' addresses, and a (confirmed) block is extra rewarded with 1% of the average reward for any valid block header it includes. An orphaned block header might be included only within the 10 consecutive blocks following its 0-degree ancestor.  

The average (basic) reward for confirmed blocks is smoothly adjusted as follows: The 100% reward of the k-th block is given by
((Bitcoin security reserve at time_k) / ratio_k )* ((6 seconds) / 4 months)
Where ratio_k, which is the average ratio between the block-chain growth rate and the block-tree growth rate, is recursively calculated by  
ratio_n+1 = (1 – (6 seconds / two weeks)) * ratio_n + (6 seconds / two weeks) * q_n
Where q_n is the total percentages of the average confirmed block reward that is rewarded on time time_n (say 100% + 90% + 50%, in case the n-th blocks contains headers of a single 1-degree block and a single 3-degree block).


Protected GHOST
Extending the current chain is done according to regular GHOST, meaning that the next chosen block is the one having the heaviest known subtree out of all the blocks that are mined on top of the current last block of the chain.

As for replacing a chain-block by an off-chain block that forms heavier subtree, I suggest a slight modification named "Protected GHOST": in calculating the size of a subtree, we shall ignore all blocks that were received suspiciously later than one could have expected. Specifically, when considering a competitive chain that is allegedly heavier, we ignore all off-chain blocks whose headers are not included within blocks of the competitive chain unless their (on-chain) predecessor has been mined during the last hour, or some other security parameter.

And that's it. Quite simple, huh?

 
Advantages and disadvantages:

The tragedy of the commons problem is solved as the total honest network is rewarded about 25BTC per 10 minutes, as it is now. Assuming the market is competitive, the total honest investment in hash-power is just a bit less than 25 BTC per 10 minutes, so the 50% attacker should be *very* rich in order to succeeds.

Smaller miners, whose probability of their valid blocks get eventually confirmed is smaller, will be rewarded just a bit less than the strong miners per a hash-power unite, Thus the network is not about to become more centralized.

The Block Discarding Attack / "Selfish Mining" is conceptually based on artificially forking the chain in order to get higher portion of the block-chain than the attacker's portion of total hash-power (which is equivalent to the attacker's portion of the block-tree). As we reward (almost) all blocks of the tree and not only those of 0-degree, this kind of attacks becomes much harder and less profitable.

We maintain a strong incentive to mine on top of the "right" chain, despite rewarding blocks that are off-chain, as their reward is slightly reduced. Moreover, we provide a strong incentive for miners to report other off-chain blocks by extra rewarding them for doing so. This is helpful not only for rewarding the 1-3 degree blocks, but also for providing the necessary information needed to choose the "right" chain.  

The main disadvantage of my proposal is the mandatory tax, which in a sense contradicts the libertarian spirit of Bitcoin. Yet I believe there is no such a thing as ideal currency, and in particular, for security you have to pay. This payment might be explicit as in my proposal, or implicit as currently it is in Bitcoin (the inflation caused by the 25 BTC rewards per block form an implicit tax), but it must somehow exist - or else we shall all suffer lower security because somebody isn’t willing to pay his/her share.

Lear.
P.S. let me just link my paper few more times, in case someone have somehow missed it: http://eprint.iacr.org/2013/868.pdf.
 

Indeed. I am saying that there might be two other ways to merge-mine two different NameCoin blocks: by having the parent block be a NameCoin block instead of a Bitcoin block; or by having two different Merkel tree roots embedded within the same coinbase transaction.

Some crypto-currencies (the most notable being NameCoin) enable merged mining, which is a technique to form two or more blocks that are related in such a way so that the calculation of a certain hash (taken over some nonce) is applicable to the proof of effort of all of the corresponding blocks. The aim of merged mining is to strengthen relatively small SHA-256 currencies by enabling Bitcoin miners to invest their hash-power in the smaller currency too without extra price.

This is a very cool technique, yet I believe it is potentially dangerous if is wrongly implemented. I am afraid of the possibility of merged mining with respect to the same coin, meaning that two of the merged blocks are of the same crypto-coin. I found that this concern has already been noted here https://en.bitcoin.it/wiki/Merged_mining#Protecting_against_double_proof but only partially: obviously, having some merged blocks that form a NameCoin chain is extremely bad because the same effort can be used to mine several blocks altogether, yet merged blocks of the same crypto-coin might be dangerous even if they are not on the same chain!

Let me outline a possible double spending attack based on the (potential) possibility to simultaneously mine on top of two competitive forks of the chain. In case of a naturally occurring fork in the chain, unless there is some kind of connection problem in the network, the next block to be mined on top of either of the two competitive blocks is going to be accepted by all and thus confirm the block it was mined upon. So generally, when a fork occurs, miners who mine on top of either of the competitive blocks should not be concerned of their newly mined block eventually becoming orphan.

However when there is a connection problem in the network, part of the network might be unaware of one of the two competitive blocks and also unaware of a third block built on top of it. Thus it is possible that when a fork occurs, and some miner extends one of the two competitive blocks by a second block, someone else will extend the other block by a second block, and then a third miner extend it by yet another block, so that the block that have temporarily formed the longest chain would nevertheless become orphan.  So rational miners should always mine on top of the two competitive chains simultaneously, as this doesn’t require extra effort and on the other hand improved the probability of gaining a valid and confirmed block is the chain.

A double-spending attacker can get other miner used to simultaneously mine on competitive chains by simply artificially forking the chain and continuing (for a while) to mine over shorter branches. The attacker might even supply the network with a mining code that always simultaneously mine on top of competitive chains in case there is no chain which is longer by at least 10 blocks than the other chain(s).

The attack goes as follows: the attacker makes the first spend in some block, and start secretly mine a competitive chain on top of its predecessor. After the unlucky receiver has been satisfied, the attacker publish the competitive chain, which is probably shorter than the original chain, as the attacker have less than half of the total hash-power. As a result, other miners start simultaneously mine on top of the competitive chains, thus preserving the gap. The attacker on the other hand, is going to mine solely on top of the shorter chain, until this chain is so longer that other miners stop mining on top of the original chain! At this point the attack succeeds.


Hopefully I've convinced you that merge mining should not enable to simultaneously mine on top of two or more blocks of the same currency, in any circumstances. Now the question is whether the mechanisms of NameCoin and other merge-mining currencies enable to do that. So I tried to understand how the NameCoin mechanism works, and it is something like that:

There are two kinds of NameCoin blocks – regular blocks and merged-mined blocks. The regular blocks are built much the same way as Bitcoin blocks, and their PoW is same as Bitcoin's (the hash of the block header concatenated with a nonce should be lower than the target). As for the merged-mined blocks, the hash of the block is included in a merkel tree that may contain some other hashes of other blocks. The root of the tree is placed in a field of the coinbase transaction of some other block (e.g. Bitcoin block) which is called the "parent block", and the hash of the parent block's header is the hash that should be lower than the target. Moreover, the place of the hash of the NameCoin merged-mined block within the merkel tree is uniquely derived from the parent block, so that if the hash of the merged-mined block happens to be placed somewhere else within the tree – the proof of effort will not be valid.

Assuming that within the merkel tree there is indeed only one possible place in which the merged-mined block's hash can be placed, there are yet two other points which could possibly enable merge-mining two different blocks of the same crypto-coin:

1.   May the parent block not be a Bitcoin block but rather a NameCoin (regular) block? Is there a different structure for NameCoin regular blocks than Bitcoin blocks (e.g. the field of the Bitcoin coinbase transaction in which the merkel tree root is placed must be set to zero in NameCoin blocks)? May a Bitcoin block be interpreted as a NameCoin block?

2.   May the Bitcoin coinbase transaction be interpreted in two different ways so that there would be two different possible valid merkel tree roots?

I hope this issue has been thoroughly checked by someone already, and you can confidently assure me that having merged blocks of the same crypto-coin is impossible in any circumstances.
 
Lear.

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

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.  

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://bitcointalk.org/index.php?topic=325824.msg3494144#msg3494144, https://bitcointalk.org/index.php?topic=325824.msg3504846#msg3504846.

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 Cunicula,

I have recently submitted a manuscript to some workshop. Indeed it is not finished and can be improved (hopefully I would be able to do so if it will be accepted), however the essential improvement should be the exclusions of some less important calculations and additions of more intuitive explanations (Currently the paper has no proper introduction). Hence I don’t think it will be a good idea to include yet another aspect to the paper (i.e. the economic game theoretic point of view). Yet I would definitely like to see a paper of yours fully dedicated to this important point of view.

Some other field in which I think we might collaborate is purely proof of stake designs. I have some immature ideas, and if I hopefully have the time I plan to think about them on the upcoming days and would like to hear your opinions. In case we will come to a sparkly design, we can write a paper and even try to form a development team in order to make it a real coin.

Anyway, if we write something together I think credit should be given to you even if you prefer to use a pseudonym. And by the way, I am not much of a computer scientist myself: I am a student for mathematics, and have never written a CS paper yet. 

Lear

Hi Cunicula,

First, I'm sorry for not responding for long periods of time. I have just read your analysis, which I like very much. Although I basically agree with you, I would like to make some notes:

1.   When theoretically analyzing a system, I do think it is wise to make as few assumptions about the external-to-the-system-world as possible. Yet while doing so you must be careful when you derive conclusions about the real world (e.g. aggressively spamming the web with "Bitcoin is broken" nonsense is a great example of a wrong attitude).

2.   As I said, I am not considering the (many) Block-Discarding-Attack strategies as applicable to pools, while the Cornell guys does. So game-theoretic equilibriums are interesting in my opinion only as a mean to analyze the expected reaction of the pools and the small miners to a theoretical block-discarding attack operated by a  big strong *solo miner*.

3.   It is hard to estimate your beta variable (the long-term post attack worth of a Bitcoin in terms of the current value). The attack might not decrease the value much, as long as there is no massive double spending or massive denial of service. If the attacker's motives are increased rewards, than she is likely to choose not to do those thinks.

4.   It is possible that the attacker have external motives, i.e. she can benefits from harming the system, say if she has interest in competitive money. In fact the most likely scenario of lunching such attack I can think of is where a government tries to fight the black market by DoS-ing Bitcoin. If so, all assumption about supposedly-rationality of the attacker becomes invalid.

5.   Another assumption that I prefer not to introduce to the theoretical analysis is the illiquidity of ASICs. You noted yourself that a PoW crypto-currency with the same structure of Bitcoin might be more vulnerably if it use the more liquid CPUs, and I would like to note that a SHA-256 ASIC can be turned to mining of other crypto-currencies:

If some SHA-256 alt-coin is attacked than miners (including the attacker) can leave for Bitcoin if the attack destroys the alt-coin. In case Bitcoin itself is attacked and destroyed, then a new (hopefully more secure) crypto-currency can be expected to replace it. Furthermore, this crypto-currency is expected to be based on SHA-256 since currently the SHA-256 ASICs are widely spread. 

Yet I note in my paper, regarding the theoretically possible gradual leaving of honest miners, that in practice the resulted equilibrium is about to be less biased toward the attacker since the cost of mining is divided between the liquid electricity and the less liquid machinery. (BTW I was looking exactly for the term "illiquidity" to explain that. My English is not so great, e.g. "shellfish mining", and so is my knowledge of economy).

Lear.

So here is the simplified explanation, based in part on my draft:

--------------------------------------------------------------------

The block discarding attack

We shall first describe the attack in subsection 3.1 w.r.t the Bitcoin protocol; in subsection 3.2 we adjust and improve the attack to the PoA protocol; and then in section 3.3 we suggest to introduce a fork-punishment protocols change as a countermeasure.

[3.1]
The attack is based on the assumption that the attacker can achieve "Network Superiority" by maintaining many direct network connections, much above the average of a single user. As explained in the previous section, when two blocks are released around the same time, the one that will be propagated faster has much higher chance to be eventually confirmed. The ability to make one's block be propagated much faster is part of what we regard as network superiority, while the other part is the ability to become instantly aware of any new released block in the network.   

Propagation of blocks is relatively slow – the average time it takes for a node to be informed of a new block is 12.6 seconds – since propagation delay composes both of the data transmissions time and the blocks verification time (a node verifies each block before it propagates it to its neighbors). Therefore, an attacker that maintains many slave nodes all across the network which are programmed to propagate her blocks without verification and to send her new received blocks without verification, is most definitely expected to acquire network superiority. That is, as long as the network is homogeneous, as the distributed Bitcoin network is supposed to be. Propagation of the attacker's block can be accelerated even farther by composing empty or relatively short blocks, whose verification (by the non-slave nodes) is faster.

Assuming an attacker with 0 < p < 1/2 fraction of the total hash power achieves total network superiority, meaning she is instantly informed of any new released block and her generated blocks always win the race when they are release on the same time as a competitor block. Then the attacker will lose nothing by holding each new generated block until a competitor is found and then release it immediately, and while holding the block treating it like it was already got into the chain, i.e. mining the next block on top of the temporary-secret block.

When normally the attacker generates x blocks and the rest of the network generates y blocks, each one of the blocks is mined on top of the previous generated one, so the chain eventually grows by x+y more blocks. However in time of attack, if the attacker generates x blocks and the rest y blocks, then all of the attacker's blocks will eventually get into the chain while only y-x of the other blocks will get into the chain, so the chain eventually grows by only y more blocks:

Each block of the attacker is released when another block is found and hence it is used to "replace" the competitive block within the chain. So if the attacker mine x blocks, x blocks of the rest of the network will be discarded, and replaced by the attacker's blocks. The total block-chain growing rate will be as if the attacker don’t mine at all, that is (1-p) times the normal rate.

Difficulty adjustment then lowers the difficulty so there will be approximately the same number of generated blocks within the same period, however the total share of the attacker's blocks out of the block-chain is now raised from p to p/(1-p). Lows of economy dictates that the cost of hash-power invested into mining should be around the expected reward. The expected reward of the non-attacker miners is now only (1-2p)/(1-p) times than before, so the total hash-power of the honest miners is about to decline as more miners leave the game.
 
By essence that means the attacker's share of the total hash-power is about to exceed p, so that the attack becomes more efficient and hence there are more miners to leave the game… the process can halt on some equilibrium or continue until all honest miners leave.

To analyze the exact outcome let b be the hash-power of the attacker, g the initial hash-power of the honest network, and h > 0 the new hash-power of the honest network when a possible equilibrium is reached. For simplicity let the hash-power unit we used be such that b + g = 1, or equivalently b = p.

Lows of economy dictate that in any stable situation, the cost of hash-power invested by an honest miner should be approximately the same as the expected reward. Hence the expected number of (eventually confirmed) mined blocks per a hash-power unit of an honest miner in the equilibrium state is the same as what the expected number of mined blocks per a hash-power unit was before the attack.

Since the total hash-power of confirmed blocks in the equilibrium state is h, we get
(g/(b+g))/g = ((h – b) / h) / h.
By convention b+g =1, so we get h^2 = h –b, or h = 1/2(1+sqrt(1-4b)).
That means the fraction of the attacker out of the new total hash-power is
b/(h+b) = 2p / (2p + 1 + sqrt(1-4p))

for p = 1/4 that means 1/4 of the initial hah-power has left, attacker has 1/3 fraction of the new hash-power and gets twice as much block rewarding as before, and the difficulty is half than before. For 0 < p < 1/4, the attacker gain more rewards than before but less than twice, and for p > 1/4 the equilibrium is obviously impossible, meaning the process will not halt until all honest miners leaves the network.

In practice total network superiority can never be achieved, so the analysis should include a probability w < 1 of the attacker winning a block race. Interestingly, the attack is reasonable even were w is explicitly lower than 1, but the most accurate analysis is complex.
When w != 1, there is a hierarchy of Block-Discarding-Attack strategies, of whom the "s(h)elfish mining" is just the first one. My complete analysis that explains everything will be published soon.

Meanwhile, I want to stress some points:

1.   As I said, the attack is currently infeasible with any of its versions.
2.   Since the attack is based on secrecy, it is not applicable to pools. Moreover, the dynamic process of the theoretic attack does not involves transfer of miners from one pool to another, but a gradually quitting of honest miners due to unprofitability.
3.   The difficulty adjustment is the key point of the attack.
4.   On any not purely theoretic scenario, equilibrium will be achieved, and the security impact of that is the increased vulnerability of the system to a second attacker, since the total block-chain hash-power is reduced. The first attacker is unable to harm the system whatsoever.
5.   On the purely theoretical scenario where the attacker deports all other miners, she can harm the system by lunching a DoS attack. Double-spending attack, however, is more problematic since the moment the Block-Discarding attacker stops mining linearly, all the ex-miners will happily start mining again, and are expected to gain awesome rewards due to the lower difficulty.   

Lear