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.
Topic: Merged mining with respect to the same crypto-currency? (Read 1054 times)
Namecoin had this vulnerability initially but implemented a defense, where it required its commitment to be at a particular place in the tree. Are you saying the defense is inadequate?
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.
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.
Jump to: