Bitcoin Forum
December 03, 2016, 09:48:22 AM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 »  All
  Print  
Author Topic: What EXACTLY means "longest" chain ?  (Read 2245 times)
Forp
Full Member
***
Offline Offline

Activity: 198


View Profile
July 09, 2011, 11:09:14 PM
 #1

Trying to work my way through the code  Smiley according to Richard Feynman's principle of learning "What I can't produce - I do not understand".   Wink

So, I reached another place I do not understand.  Shocked

Every node always considers the longest chain the correct one. Yes?

Ok. What happens if there are two longest chains.

Well, this is not a problem for the future of the entire system since, eventually, there will be a longest chain again. Odds are exponentially decreasing for a "two equally long longest chains" to survive in the long run.

That said: A single node (and, similarly, blockexplorer) has at any given moment in time a concept of what is the longest chain (even if there are two equally long chains). I checked the code. In the -printblock functionality there is no clear answer to this and I did not yet manage to digest the chain reorganization algorithms to understand this aspect.

So, assume there is this situation:

               B-C
              /
GENESIS-A
              \
               X-Y

What does the individual node or the block explorer consider the longest chain ? GENESIS-A-B-C or GENESIS-A-X-Y ?

This question might be considered academic, since in the long run one of the chains will stabilize and become the longest.

But there might be one interesting aspect here. I think, for quick chain stabilization, it is important that the nodes pick the same chain as the correct chain. Assume, 1/2 of the nodes pick GENESIS-A-B-C and the other 1/2 of the nodes pick GENESIS-A-X-Y. In this case the "battle" for the right correct chain might take much longer. Now assume that all nodes pick GENESIS-A-B-C. In this case the "battle" will be over quite quickly (not necessarily in favour of GENESIS-A-B-C though, but the chances of oscillating back and forth should be smaller).

Any ideas on this?




1480758502
Hero Member
*
Offline Offline

Posts: 1480758502

View Profile Personal Message (Offline)

Ignore
1480758502
Reply with quote  #2

1480758502
Report to moderator
1480758502
Hero Member
*
Offline Offline

Posts: 1480758502

View Profile Personal Message (Offline)

Ignore
1480758502
Reply with quote  #2

1480758502
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480758502
Hero Member
*
Offline Offline

Posts: 1480758502

View Profile Personal Message (Offline)

Ignore
1480758502
Reply with quote  #2

1480758502
Report to moderator
1480758502
Hero Member
*
Offline Offline

Posts: 1480758502

View Profile Personal Message (Offline)

Ignore
1480758502
Reply with quote  #2

1480758502
Report to moderator
Martin P. Hellwig
Jr. Member
*
Offline Offline

Activity: 33


View Profile
July 09, 2011, 11:15:20 PM
 #2

I sincerely hope that the amount of transactions in the block is a factor in defining the longest chain, but I don't know.
etotheipi
Legendary
*
expert
Offline Offline

Activity: 1428


Core Armory Developer


View Profile WWW
July 10, 2011, 01:23:46 AM
 #3

Nodes process which ever "longest chain" they hear about first.  If two nodes on opposite sides of the world solve the next block at exactly the same time, then half the world will get word of one block and start working on it, while the other half the world gets word of the other block first and starts working on that.  Once either of those chains is extended, the solution is broadcast and all nodes will switch to it, seeing that that chain is the longest.  Sure, both halves of the world could solve the next block at exactly the same time and both will be temporarily extended again.  But statistically speaking, eventually one chain will "lose", and it's entirely up to luck which one that is.

More often than not, you would get 90% of the world that sees one block, and 10% of that gets the other block first.  Unless the 10% side gets extremely lucky, the 90% will be the one to become the real chain.  The orphaned block becomes "invalid."  I believe nodes that who were working on that branch, will see what transactions need to be re-included in the new branch, but I'm not sure how that part works exactly.






Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
JoelKatz
Legendary
*
Offline Offline

Activity: 1386


Democracy is vulnerable to a 51% attack.


View Profile WWW
July 10, 2011, 01:36:50 AM
 #4

Ok. What happens if there are two longest chains.
Then the choice of chain is arbitrary. Eventually one chain will become longer and the problem will solve itsef.

Quote
Well, this is not a problem for the future of the entire system since, eventually, there will be a longest chain again. Odds are exponentially decreasing for a "two equally long longest chains" to survive in the long run.
Exactly.

Quote
What does the individual node or the block explorer consider the longest chain ? GENESIS-A-B-C or GENESIS-A-X-Y ?
In practice, whichever chain it saw first. In theory, it doesn't matter.

Quote
But there might be one interesting aspect here. I think, for quick chain stabilization, it is important that the nodes pick the same chain as the correct chain. Assume, 1/2 of the nodes pick GENESIS-A-B-C and the other 1/2 of the nodes pick GENESIS-A-X-Y. In this case the "battle" for the right correct chain might take much longer. Now assume that all nodes pick GENESIS-A-B-C. In this case the "battle" will be over quite quickly (not necessarily in favour of GENESIS-A-B-C though, but the chances of oscillating back and forth should be smaller).
The chain will already stabilize quickly because it will take, on average, several minutes to extend either chain. If you were designing a protocol that tried to add blocks more often, maybe it would be worth the cost of extra reorganizations.

I am an employee of Ripple.
1Joe1Katzci1rFcsr9HH7SLuHVnDy2aihZ BM-NBM3FRExVJSJJamV9ccgyWvQfratUHgN
WakiMiko
Jr. Member
*
Offline Offline

Activity: 59



View Profile
July 10, 2011, 01:38:55 AM
 #5

Assume, 1/2 of the nodes pick GENESIS-A-B-C and the other 1/2 of the nodes pick GENESIS-A-X-Y. In this case the "battle" for the right correct chain might take much longer.

Not really, the "battle" should be over pretty fast in any case, as the next block settles the issue.
There is of course the chance that the next two blocks are found at proximately the same time and the split continues, but the chances for this to happen are pretty slim.

1APeJ2DiUNdsNizn47MBeAwbjaugEgg4Zn
Forp
Full Member
***
Offline Offline

Activity: 198


View Profile
July 10, 2011, 12:53:16 PM
 #6

...

Thank you, Joel, for your help ! It clarified the issue.
Forp
Full Member
***
Offline Offline

Activity: 198


View Profile
July 10, 2011, 12:58:12 PM
 #7

Nodes process which ever "longest chain" they hear about first. 

Yup. Of course.

I did not phrase the question clearly enough. I was thinking of the following situation: A node is booted, bitcoind is started...reads the disc files and finds a block index where there are TWO longest chains. The program will prefer one of them. Which one will it prefer? I was not able to find that answer. I now realize, that it is in fact not really important. And I realize that I will have to spend a day or two understanding block reorganization... :-)

Actually, the terminology of longest chain is ill defined. There can be several chains of maximal length.

And again: If this thing (bitcoind) should eventually takle over management of my money - I want to make sure, as computer scientist, I understand every single bit of what it does.  Smiley
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
July 10, 2011, 02:20:31 PM
 #8

The longest chain is defined as the one with the most proof-of-work.

Technically, the "length" of each chain is the sum of (2^256 divided by the block's target) for a given block plus all its ancestors.
This number is the statistically expected number of hashes to have been performed in the chain, and is currently equal to about 4.1e19 (41 billion billion).

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Forp
Full Member
***
Offline Offline

Activity: 198


View Profile
July 10, 2011, 08:45:21 PM
 #9

The longest chain is defined as the one with the most proof-of-work.

Technically, the "length" of each chain is the sum of (2^256 divided by the block's target) for a given block plus all its ancestors.

Ah. This makes again much more sense! Of course. Guess  I will have to read some more satoshi c++...

Just curious: How is the longest chain picked if there are two chains with an equal amount of proof-of-work?
Maged
Legendary
*
Offline Offline

Activity: 1260


View Profile
July 10, 2011, 08:55:18 PM
 #10

Just curious: How is the longest chain picked if there are two chains with an equal amount of proof-of-work?
Exactly as we've already described: the client picks the one it received first.

TierNolan
Legendary
*
Offline Offline

Activity: 1036


View Profile
July 10, 2011, 10:13:25 PM
 #11

The longest chain is defined as the one with the most proof-of-work.

I am not sure that that's true.  

It is how it should be done, but may not be how it is actually done.

You could even define it as the sum of 1/<hash value> for all blocks in the chain.

The difficulty value only changes every 2160 blocks, so in most cases 2 chains will have the same difficulty for the blocks after the split.

If sum (1/<hash value>) was used, then it would be very unlikely that a tie would happen.

Alternatively, the rule could be that if 2 valid blocks are received, then the one with the lowest hash value wins.

               B-C
              /
GENESIS-A
              \
               X-Y

If B had a hash of 0000000123 and X had a hash of 0000000122, then everyone who had received the B hash first would switch to A as soon as they received the A block.  C would likely never be found at all.

This would short circuit the tie-break rule.

It wouldn't even require a network rule change.  Miners could just agree to do it that way.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
July 10, 2011, 11:05:34 PM
 #12

The longest chain is defined as the one with the most proof-of-work.

I am not sure that that's true. 

It is how it should be done, but may not be how it is actually done.

You could even define it as the sum of 1/<hash value> for all blocks in the chain.

The difficulty value only changes every 2160 blocks, so in most cases 2 chains will have the same difficulty for the blocks after the split.

If sum (1/<hash value>) was used, then it would be very unlikely that a tie would happen.

Alternatively, the rule could be that if 2 valid blocks are received, then the one with the lowest hash value wins.

               B-C
              /
GENESIS-A
              \
               X-Y

If B had a hash of 0000000123 and X had a hash of 0000000122, then everyone who had received the B hash first would switch to A as soon as they received the A block.  C would likely never be found at all.

This would short circuit the tie-break rule.

It wouldn't even require a network rule change.  Miners could just agree to do it that way.

Yes, but they won't have the same difficulty after the next block is received.

In your example, A-B-C and A-X-Y are equally valid and each node considers the one it saw first to be true.  The matter will be settled across the entire network when either D or Z is found next.

In practice, it almost never even gets this far.  Most of the time, either C or Y would have decided the question between B and X.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
TierNolan
Legendary
*
Offline Offline

Activity: 1036


View Profile
July 11, 2011, 11:10:31 AM
 #13

Yes, but they won't have the same difficulty after the next block is received.

The point is that if there was a defined tie break rule, then one or other could be discarded.

When B and X were found, all nodes would agree on which one was first, even if they received them in different order.


1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
JoelKatz
Legendary
*
Offline Offline

Activity: 1386


Democracy is vulnerable to a 51% attack.


View Profile WWW
July 11, 2011, 02:08:15 PM
 #14

The point is that if there was a defined tie break rule, then one or other could be discarded.

When B and X were found, all nodes would agree on which one was first, even if they received them in different order.
That would destabilize the network. Assume a block has been found and propagated to most of the network. Right now, to force a reorganization, I have to find two blocks before the rest of the network finds one. With this change, I only have to find one block and I have a 50/50 chance of upsetting the network.

With a well-defined tie break rule, the number of reorganizations would be much higher.

I am an employee of Ripple.
1Joe1Katzci1rFcsr9HH7SLuHVnDy2aihZ BM-NBM3FRExVJSJJamV9ccgyWvQfratUHgN
TierNolan
Legendary
*
Offline Offline

Activity: 1036


View Profile
July 11, 2011, 02:34:37 PM
 #15

With a well-defined tie break rule, the number of reorganizations would be much higher.

However, they would last for a shorter period of time.

Currently, if there is a fork, it will last for on average 10 minutes until one or other half of the network finds the next block.

Assuming most of the network switches immediately to the new best, then it is less wasted effort.  The benefit is that there is no need to wait for the next block to trigger the tie break.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
July 11, 2011, 02:55:56 PM
 #16

What exactly do you mean by wasted effort?

Also, you are doubling the amount of time an attacker has to find a superior block.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
JoelKatz
Legendary
*
Offline Offline

Activity: 1386


Democracy is vulnerable to a 51% attack.


View Profile WWW
July 11, 2011, 03:09:16 PM
 #17

Currently, if there is a fork, it will last for on average 10 minutes until one or other half of the network finds the next block.
Yes, but it will tend to be a small portion of the network that is forkeds.
Quote
Assuming most of the network switches immediately to the new best, then it is less wasted effort.  The benefit is that there is no need to wait for the next block to trigger the tie break.
I think this is an incoherent argument. Either you consider attempts to create a block that don't produce a block wasted effort or not. But even if the network is split 50/50, it makes no sense to say the nodes working on the losing chain wasted effort. They had the same chance to produce a block as the nodes on the winning chain.

I don't like the idea that 95% of the network can be on a particular chain and one node produces a new block and has a 50% chance of forcing the network to switch.

I am an employee of Ripple.
1Joe1Katzci1rFcsr9HH7SLuHVnDy2aihZ BM-NBM3FRExVJSJJamV9ccgyWvQfratUHgN
TierNolan
Legendary
*
Offline Offline

Activity: 1036


View Profile
July 11, 2011, 07:09:12 PM
 #18

Yes, but it will tend to be a small portion of the network that is forkeds.

With a tie break, even that small part is eliminated.

Quote
I think this is an incoherent argument. Either you consider attempts to create a block that don't produce a block wasted effort or not. But even if the network is split 50/50, it makes no sense to say the nodes working on the losing chain wasted effort. They had the same chance to produce a block as the nodes on the winning chain.

True, I guess my objection is that you have a 1 block fork for longer.  With a tie break, the fork is instantly eliminated.

In the extreme, with chain = sum of proof of work, people could submit blocks with any amount of difficulty.  The more difficulty, the more likely it is to end up in the final chain.

Quote
I don't like the idea that 95% of the network can be on a particular chain and one node produces a new block and has a 50% chance of forcing the network to switch.

That can also happen with the fork case.  The 5% fork might win, and the 95% will have to reorganise.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
July 11, 2011, 07:28:30 PM
 #19

I don't like the idea that 95% of the network can be on a particular chain and one node produces a new block and has a 50% chance of forcing the network to switch.

That can also happen with the fork case.  The 5% fork might win, and the 95% will have to reorganise.

But only if the minority block is transmitted within seconds of the majority block.  In your system, the reversal can happen several minutes later, and it can cause a reorg of not just 95% of the network, but 100% (minus the attacker's mining node).

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
TierNolan
Legendary
*
Offline Offline

Activity: 1036


View Profile
July 12, 2011, 10:53:01 AM
 #20

In your system, the reversal can happen several minutes later, and it can cause a reorg of not just 95% of the network, but 100% (minus the attacker's mining node).

So, the issue is

Chain: ----> A

B is found

Chain: ----> A -> B

Transactions in B get "confirmed/1"

B' is found (with lower hash) before C is found.

Chain: ----> A -> B'

Transactions in B are reversed.

Under the current system, the attacker would need to find B' and C' before C is found, in order to clear B.

The trade-off is that under the current system, all of the nodes won't necessarily agree on what is the top node.  During a fork, some of the nodes will think a trade is still valid, while the majority of the network is working to reverse them.  With the tie break rule B all nodes will agree that B has been canceled, once it has been broadcast.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
Pages: [1] 2 »  All
  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!