Nonce in Merged Mining

Question

When mining Bitcoin, the nonce is included in the header, which is then hashed and checked to see if it is below the target threshold.
Everybody can verify that the header does indeed hash below the threshold. However, in merged mining, according to the wiki, the hash of the auxiliary chain's header is included in the parent's coinbase txin script without the opportunity to change the nonce in the auxiliary chain. The parent's nonce is incremented as usual but the aux hash remains the same.

How can we then verify the auxiliary chain?

is it because the parent nonce makes its way into the auxiliary chain through the parent header's hash? even so it seems that this would not help for verification because the aux chain's hash no longer need meet any threshold criteria.

Answer 1

To verify the auxiliary chain, you need to prove that a certain amount of work has been done upon the latest block in that auxiliary chain. As with any form of mining, this involves computing a hash to be below a threshold.

However, it doesn't matter that the pre-image of the hash has a lot of other irrelevant data in it too, so long as it contains the relevant auxiliary-block header in there somewhere. I.e. from a proof-of-work perspective it makes no difference if you calculate this:

while(h > aux-threshold) {
    h = hash(aux-header + nonce)
    nonce++
}
result = nonce    

versus this:

container = hash(hash(aux-header) + other-data)
while(h > aux-threshold) {
    h = hash(container + nonce)
    nonce++
}
result = nonce

Both will take the same amount of work and both will prove that the work has been done on aux-header. This is so because container can be proven to contain the aux-header, and since aux-header and other-data are stored in the aux-chain block and the hash can be re-computed at any time.

So, for merged mining, container is actually the hashed header of the parent-chain block and aux-header just needs to be included in the parent block somewhere. It really could be included anywhere so long as the parent block passes the verification process. For example, you could include the aux-chain-header-hash as an address in a multisig transaction, or as a piece of data that gets placed on the stack but never popped off in one of the transactions. Yet, the easiest place to put it is in the txin script of the coinbase transaction. This always contains arbitrary data anyway, and its location at the top of the chain means that other-data can contain the smallest number of merkle branches.

Answer 2

You verify the auxiliary chain precisely the same way, except you must also check that the auxiliary chain's header is properly included in the parent's coinbase. From the point of view of the auxiliary chain, you can think of the entire primary chain header as part of a giant nonce.