Bitcoin Forum
December 09, 2016, 03:46:42 PM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Nonce for merged mining chain merkle tree index  (Read 3225 times)
DrHaribo
Legendary
*
Offline Offline

Activity: 1960


Bitminter.com Operator


View Profile WWW
November 06, 2011, 07:13:00 PM
 #1

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?

▶▶▶ Bitminter.com - Your trusted mining pool since 2011.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481298402
Hero Member
*
Offline Offline

Posts: 1481298402

View Profile Personal Message (Offline)

Ignore
1481298402
Reply with quote  #2

1481298402
Report to moderator
1481298402
Hero Member
*
Offline Offline

Posts: 1481298402

View Profile Personal Message (Offline)

Ignore
1481298402
Reply with quote  #2

1481298402
Report to moderator
1481298402
Hero Member
*
Offline Offline

Posts: 1481298402

View Profile Personal Message (Offline)

Ignore
1481298402
Reply with quote  #2

1481298402
Report to moderator
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526


View Profile
November 07, 2011, 12:29:08 PM
 #2

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
Hero Member
*****
Offline Offline

Activity: 686


View Profile
November 07, 2011, 02:20:23 PM
 #3

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?

Quad XC6SLX150 Board: 860 MHash/s or so.
SIGS ABOUT BUTTERFLY LABS ARE PAID ADS
makomk
Hero Member
*****
Offline Offline

Activity: 686


View Profile
November 07, 2011, 07:44:38 PM
 #4

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.

Quad XC6SLX150 Board: 860 MHash/s or so.
SIGS ABOUT BUTTERFLY LABS ARE PAID ADS
DrHaribo
Legendary
*
Offline Offline

Activity: 1960


Bitminter.com Operator


View Profile WWW
November 07, 2011, 07:58:32 PM
 #5

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.

▶▶▶ Bitminter.com - Your trusted mining pool since 2011.
Luke-Jr
Legendary
*
expert
Offline Offline

Activity: 2100



View Profile
November 07, 2011, 07:59:13 PM
 #6

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

makomk
Hero Member
*****
Offline Offline

Activity: 686


View Profile
November 07, 2011, 08:12:36 PM
 #7

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

Quad XC6SLX150 Board: 860 MHash/s or so.
SIGS ABOUT BUTTERFLY LABS ARE PAID ADS
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526


View Profile
November 09, 2011, 01:37:03 PM
 #8

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.
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!