Bitcoin Forum
November 20, 2017, 04:23:00 PM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Best chain / work definition/calculation?  (Read 1604 times)
smtp
Member
**
Offline Offline

Activity: 70


View Profile
January 15, 2013, 04:19:13 PM
 #1

Where can I get information how the "best chain value" and the "work" is computed/defined?

In the file $HOME/.bitcoin/debug.log, there are messages like:

SetBestChain: new best=0000000000000419f719  height=212580  work=666804971104474944731

Thx,
smtp
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1511194980
Hero Member
*
Offline Offline

Posts: 1511194980

View Profile Personal Message (Offline)

Ignore
1511194980
Reply with quote  #2

1511194980
Report to moderator
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
January 15, 2013, 05:20:45 PM
 #2

Each block has a target.  The target is the largest possible hash value that is considered valid for that block.  In work terms, it takes about (uint256_max-target) hashes to create that block.

Note that this is calculated based on the acceptable hash values that the block could have had, not the actual hash value.

Each block has a prevHash field in the header that tells what block it is building on.  Each block can only have one parent, but it can have many children.  Consider all of the blocks in a tree structure, leading up to the genesis block at the root of the tree.  That block is actually special, because it doesn't point to another block.  (Instead, it points to a newspaper headline.)

For each leaf node in the tree, calculate the sum of the work values (target inverse) for each block starting from the leaf and going to the genesis block.  The highest sum you get is the longest path through the tree, and that is the "best chain value", and the chain that corresponds to that is the best chain.

Note that there may be two paths (rarely more than two) with equal value.  In that case, the one you saw first is your best chain.  The ambiguity will be resolved shortly, as one chain or the other will grow faster.

In the log messages, new best is the start of the hash of the block that it considers to be the head of the best chain, height is the length of the path through the tree, and work is the sum of the work embedded in that path.

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

Activity: 70


View Profile
January 15, 2013, 06:14:14 PM
 #3

For each leaf node in the tree, calculate the sum of the work values (target inverse) for each block starting from the leaf and going to the genesis block.  The highest sum you get is the longest path through the tree, and that is the "best chain value", and the chain that corresponds to that is the best chain.
Thx for this explanation -- luckily I had analyzed block-headers before and knew what they serve (URL https://en.bitcoin.it/wiki/Block_hashing_algorithm).
Still one question to be sure what exactly you mean when defining "work":
What do you call the "inverse of a target (value)"? Surely not 1/target (because it is no integer). :-)

Thx, smtp
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
January 15, 2013, 06:45:31 PM
 #4

For each leaf node in the tree, calculate the sum of the work values (target inverse) for each block starting from the leaf and going to the genesis block.  The highest sum you get is the longest path through the tree, and that is the "best chain value", and the chain that corresponds to that is the best chain.
Thx for this explanation -- luckily I had analyzed block-headers before and knew what they serve (URL https://en.bitcoin.it/wiki/Block_hashing_algorithm).
Still one question to be sure what exactly you mean when defining "work":
What do you call the "inverse of a target (value)"? Surely not 1/target (because it is no integer). :-)

Thx, smtp

I screwed up my answer a bit.  It really isn't (uint256_max-target).

The output of sha256 is a 256 bit integer, in the range from zero to uint256_max, and it has many properties similar to random numbers.  Now we define a number smaller than uint256_max that is our target.  If a hash is less than or equal to target, that block is valid.  If it is greater than target, we keep trying.

The target is (roughly) 2256-(difficulty*232).  That second term is the work value.  Target, difficulty and work are all different aspects of the same thing, they are ways to look at the amount of luck a given hash has to have to be valid.  Target is the highest acceptable value, work is the number of impossible values between target and uint256_max, difficulty is the work scaled down such that the first blocks have a difficulty of 1.

Does that help?

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

Activity: 70


View Profile
January 15, 2013, 07:25:13 PM
 #5

The target is (roughly) 2256-(difficulty*232).  That second term is the work value.  Target, difficulty and work are all different aspects of the same thing, they are ways to look at the amount of luck a given hash has to have to be valid.  Target is the highest acceptable value, work is the number of impossible values between target and uint256_max, difficulty is the work scaled down such that the first blocks have a difficulty of 1.

Does that help?
Yes, I think so. And you were totally right: "work" is the additive inverse of target (in the group modulo 2256). Wink

thx, smtp
smtp
Member
**
Offline Offline

Activity: 70


View Profile
January 15, 2013, 10:43:36 PM
 #6

Hi

Let me correct your memory a bit, kjj. Smiley

I asked:
Where can I get information how the "best chain value" and the "work" is computed/defined?

In the file $HOME/.bitcoin/debug.log, there are messages like:

SetBestChain: new best=0000000000000419f719  height=212580  work=666804971104474944731

This new best value are simply the first (highest) 10 bytes of sha256 (2 times sha-256 hashed) of the block's raw header data printed in hexadecimal. Nothing else.

work is "something" summed up from the target of the blocks in decimal notation. Firstly I looked at successive differences in hexadecimal.
At the beginning it is 100010001 (in hexa) , later e.g. at height 212580 1FFC8061F54 (in hexa decimal), so it seems to be increasing, but rather strong.

Finally I looked it up in the source of bitcoin-0.7.2, file src/src/main.h

(CBigNum(1)<<256) / (bnTarget+1)  is the result which GetBlockWork()  returns for each block, and the above mentioned "work" is the sum of these values.
Hence "work" is defined as  2256 / (target+1) , rounded down to the next integer, and summed up until the current block of the block chain.

Thanks for pressing me to look the correct answer up in the source code.  Roll Eyes

smtp
smtp
Member
**
Offline Offline

Activity: 70


View Profile
January 16, 2013, 11:38:30 AM
 #7

Hi

This lead me just to the very special question:

Is the target-value stored in compressed form in the 5th field of the block header be always normalized?

Or put it differently: Must (block_header.bits & 0xff0000) always be notequal 0 for a valid block?

smtp

smtp
Member
**
Offline Offline

Activity: 70


View Profile
January 16, 2013, 11:49:01 AM
 #8

Is the target-value stored in compressed form in the 5th field of the block header be always normalized?
No it need not to be -- I just see this e.g. in the first blocks of the block chain.

smtp
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!