Is merged mining going to have excessive overhead as Bitcoin grows?

[DeathAndTaxes]

Merge mining is an awesome concept which can "reuse" the existing Bitcoin infrastructure to secure multiple blockchain type systems (not all of which need to be "currencies").  As currently implemented I believe it will not be a viable option for new chains as Bitcoin tx volume grows.  Correction: overhead grows only by the log of the tx volume so this is less of an issue although the overhead could be dropped further.

To link the aux chain to the bitcoin PoW the block hash of the aux chain needs to be encoded in the bitcoin block.  As the bitcoin block structure has no field for holding arbitrary values it is encoded in the coinbase transaction.  To link the coinbase tx to the merkle root hash in the blockheader requires recording the merkle branch.  The size of the merkle branch in bytes is (32 * num_txns / 2). (32 * log2(num_txns).  

One way to improve the efficiency of merged mining would be to add an fixed length "aux" 32 byte field to the blockheader.  This would make the bitcoin block header marginally larger but wouldn't make the full block any larger.  The bitcoin protocol can be extended by introducing a new version of the block header. It would be optimal to bundle a number of changes together in the next version of the blockheader.

Some ideas on how the blockheader can be extended in a manner which doesn't break compatibility with existing ASIC infrastructure:
https://bitcointalk.org/index.php?topic=626377.0

[1715049647]

1715049647

[1715049647]

1715049647

[1715049647]

1715049647

[maaku]

Size of the merkle hash tree proof is logarithmic not linear.

[DeathAndTaxes]

Size of the merkle hash tree proof is logarithmic not linear.

Thanks.   That does make the overhead much more manageable
4200 tx = CEIL(LOG2(4200)) = 14 * 32 = 448 bytes

I still think an "aux" field does merit some consideration if/when block header is updated.  Bitcoin also benefits through the use of merged mining. Anything that lowers the barrier for adoption over other methods helps to secure the Bitcoin chain by not diverting resources towards incompatible security systems.

[acoindr]

...  Bitcoin also benefits through the use of merged mining. Anything that lowers the barrier for adoption over other methods helps to secure the Bitcoin chain by not diverting resources towards incompatible security systems.

I agree merged mining can be beneficial, possibly even critical, to complementary block chains. As you point out it's a win-win by sharing resources to different tasks.

Peter Todd gave an interesting perspective on a LTB episode which is merged mining can encourage mining centralization. This is due to conflicting incentive vs resource requirements to merged mine. Independent miners need to maintain updated block chains for every coin mined which can offset monetary gains, whereas pools can manage the overhead while still offering the gains. The more chains providing incentive to merged mine, the greater the incentive to join a pool, especially one offering the most chains, undermining things like P2Pool.

I'm thinking (and hoping) we'll see many more pools spring up to counter the recurring theme of a single pool or a few comprising worrying percentages of global hashrate. However, I think it's also healthy to have a large number of independent miners. A healthy mix of pools, enterprise miners, hobbyists and independents I think is probably best. Just something to consider.