Nonce for merged mining chain merkle tree index

[DrHaribo]

After getting merged mining with a single auxiliary chain working, I'd like to implement support for multiple auxiliary chains.

I looked at how a chain's position in the chain merkle tree is calculated.

From namecoind source code:

Code:

    unsigned int rand = nNonce;
    rand = rand * 1103515245 + 12345;
    rand += nChainID;
    rand = rand * 1103515245 + 12345;

    if (nChainIndex != (rand % nSize))
        return error("Aux POW wrong index");

I don't get it. The nonce and chain ID are effectively added together. If I try a different nonce it will just make the same two chains collide in a different slot. It would have made more sense if nonce and chain ID were multiplied, then using different nonces would yield different results.

Am I supposed to increase the number of slots (nSize) until there are no collisions? Or are other auxiliary chains expected to use a different formula?

[1714782892]

1714782892

[1714782892]

1714782892

[1714782892]

1714782892

[Mike Hearn]

This is a workaround for something that is better done in another way. See the "alternative chains" wiki page for a discussion.

Essentially you want to ensure somebody doesn't attempt to solve multiple blocks at once with the same work. The way vince did this is a bit odd - a better way is to make require proof of work hashes to be unique. See:

https://en.bitcoin.it/wiki/Alternative_Chains#Protecting_against_double_proof

If you do that you don't need Vinces system.

[makomk]

I don't get it. The nonce and chain ID are effectively added together. If I try a different nonce it will just make the same two chains collide in a different slot. It would have made more sense if nonce and chain ID were multiplied, then using different nonces would yield different results.

This doesn't seem to be entirely true because of the way the result is taken modulo the number of available slots; if that's not a power of two it appears that changing the nonce can rarely cause colliding chains not to collide. It is kind of broken though. (This is also a shame because power-of-two numbers of slots are conceptually simpler.)

Am I supposed to increase the number of slots (nSize) until there are no collisions? Or are other auxiliary chains expected to use a different formula?

I'd suggest trying a few hundred or thousand nonces and if that doesn't work increase the number of slots by one and try again. Using odd values for nSize may help too. Fortunately you only need to do this once at startup.

Essentially you want to ensure somebody doesn't attempt to solve multiple blocks at once with the same work. The way vince did this is a bit odd - a better way is to make require proof of work hashes to be unique.

Unless I'm missing something, wouldn't that make double-spending attacks a lot cheaper because you could share the same work on both sides of the double-spend?

[makomk]

This doesn't seem to be entirely true because of the way the result is taken modulo the number of available slots; if that's not a power of two it appears that changing the nonce can rarely cause colliding chains not to collide. It is kind of broken though.

Except of course I missed the first time that merged mining doesn't support non-power-of-2 numbers of slots:

Code:

    if (nSize != (1 << vChainMerkleBranch.size()))
        return error("Aux POW merkle branch size does not match parent coinbase");

Wow, that's quite badly broken.

[DrHaribo]

I don't get it. The nonce and chain ID are effectively added together. If I try a different nonce it will just make the same two chains collide in a different slot. It would have made more sense if nonce and chain ID were multiplied, then using different nonces would yield different results.

This doesn't seem to be entirely true because of the way the result is taken modulo the number of available slots; if that's not a power of two it appears that changing the nonce can rarely cause colliding chains not to collide. It is kind of broken though. (This is also a shame because power-of-two numbers of slots are conceptually simpler.)

If A==B where A=X%Z and B=Y%Z then increasing X and Y by the same amount means you still have A==B. It doesn't matter whether Z is a power of 2. (% is modulo and == is equality)

Another thing is that the number of merkle leaves IS required to be a power of 2. Namecoin block validation checks that the number of merkle leaves is equal to (1 << vChainMerkleBranch.size()). If you are merged mining 3 aux chains, you have to use a dummy slot merkle leaf.

Essentially you want to ensure somebody doesn't attempt to solve multiple blocks at once with the same work. The way vince did this is a bit odd - a better way is to make require proof of work hashes to be unique.

Unless I'm missing something, wouldn't that make double-spending attacks a lot cheaper because you could share the same work on both sides of the double-spend?

It is also important to stop someone from creating X number of blocks on top of each other with a single hash. I guess that's the problem referred to at https://en.bitcoin.it/wiki/Alternative_Chains#Protecting_against_double_proof.

But I think the double-spending attack you are talking about is even scarier.

Can you stop someone from working on multiple forks with the same hashing power by just requiring aux pows to be unique? To me, namecoin's solution looks much more secure. It's just unfortunate that the formula for merkle indices is broken.

[Luke-Jr]

Or are other auxiliary chains expected to use a different formula?

This

[makomk]

If A==B where A=X%Z and B=Y%Z then increasing X and Y by the same amount means you still have A==B. It doesn't matter whether Z is a power of 2. (% is modulo and == is equality)

In this case it does seem to matter a bit, probably because the result is truncated to 32 bits prior to the modulo operation. You're right though - the merged mining code does require it to be a power of 2 anyway.

A good possible candidate for a better function is the "final" function from http://burtleburtle.net/bob/c/lookup3.c - though switching to this would need some way to communicate with the merged mining implementation in the pool server or wherever and telling them that this is in use for that particular chain.

Edit: For example:

Code:

#define lrot(x,n) (((x) << (n)) | ((x) >> (32-(n))))

uint32_t n = (0xdeadbeef ^ chain_id) - lrot(chain_id, 14);
nonce = (nonce ^ n) - lrot(n, 11);
chain_id = (chain_id ^ nonce) - lrot(nonce, 25);
n = (n ^ chain_id) - lrot(chain_id, 16);
nonce = (nonce ^ n) - lrot(n, 4);
chain_id = (chain_id ^ nonce) - lrot(nonce, 14);
n = (n ^ chain_id) - lrot(chain_id, 24);
chainIndex = n % nSize

[Mike Hearn]

Unless I'm missing something, wouldn't that make double-spending attacks a lot cheaper because you could share the same work on both sides of the double-spend?

You still can't outrun the main chain unless you have 51% of the power.

If you're worried about an attacker using the profit from mining on the main chain to pay for equipment or something, perhaps you could make both blocks be considered invalid. That is, if you see the following chain:

Code:

a  -> b1 -> b3
  \-> b2 -> b4

If b3 and b4 share a PoW, then both are considered invalid and the chain must be rebuilt from one of those points. Neither side wins. This shouldn't allow you to break the chain unless you can find a hash collision.