Bitcoin Forum
December 03, 2016, 07:49:17 PM *
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]
  Print  
Author Topic: Simple way to determine block chain length  (Read 1042 times)
remmy
Jr. Member
*
Offline Offline

Activity: 35


View Profile WWW
August 23, 2011, 11:28:32 PM
 #1

My understanding of the procedure for determining the official block chain is as follows:

- Calculate the difficulty for each block.
- Walk the chain starting at the genesis block, and sum the difficulties of the blocks as you go.
- When you reach the end, the chains, the one with the highest difficulty is the official chain.

My problem comes from the difficulty calculation.  Difficulty is the current target divided by a constant.

Would it not be simpler and equally effective to just count the leading zeroes of the block hash and use that as a difficulty measure?
1480794557
Hero Member
*
Offline Offline

Posts: 1480794557

View Profile Personal Message (Offline)

Ignore
1480794557
Reply with quote  #2

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

Posts: 1480794557

View Profile Personal Message (Offline)

Ignore
1480794557
Reply with quote  #2

1480794557
Report to moderator
1480794557
Hero Member
*
Offline Offline

Posts: 1480794557

View Profile Personal Message (Offline)

Ignore
1480794557
Reply with quote  #2

1480794557
Report to moderator
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
August 23, 2011, 11:48:33 PM
 #2

Would it not be simpler and equally effective to just count the leading zeroes of the block hash and use that as a difficulty measure?
I presume you mean counting the leading zeroes in the binary representation.

The obvious objection to your suggestion would be that it does not provide as fine granularity as the existing scheme. I think it would be difficult to determine or argue the inequivalence of its effectiveness.

I believe that it's the target that's used to determine chain difficulty rather than the actual hash in order to discourage some rather impractical attacks exploiting particularly "lucky" blocks. I believe theymos has addressed the issue if you care to search through his history(!).

From main.h
Code:
    CBigNum GetBlockWork() const
    {
        CBigNum bnTarget;
        bnTarget.SetCompact(nBits);
        if (bnTarget <= 0)
            return 0;
        return (CBigNum(1)<<256) / (bnTarget+1);
    }

ByteCoin
remmy
Jr. Member
*
Offline Offline

Activity: 35


View Profile WWW
August 24, 2011, 10:32:37 PM
 #3

I understand now that difficulty is inversely proportional to the current target.  What I would like to know is if there exists a method to calculate difficulty without using floating point math, and what that method is.
etotheipi
Legendary
*
expert
Offline Offline

Activity: 1428


Core Armory Developer


View Profile WWW
August 24, 2011, 11:07:11 PM
 #4

Quote
What I would like to know is if there exists a method to calculate difficulty without using floating point math, and what that method is.

But difficulty is a floating point number, so I don't know how you can get there without doing floating point math.  The most straightforward way I know is simply what is in the client source code: 

Code:
def difficultyBits_to_float(b):
   i = binary_to_int(b)
   nShift = (i >> 24) & 0xff
   dDiff = float(0x0000ffff) / float(i & 0x00ffffff)
   while nShift < 29:
      dDiff *= 256.0
      nShift += 1
   while nShift > 29:
      dDiff /= 256.0
      nShift -= 1
   return dDiff

Even I don't totally understand the calculation, but I think this is as simple as it gets, using some bit-math (shiftings, bit-and).  Be aware that the difficulty is typically a 32-bit number that looks like 1DAABBCC.  The first 8 bits (1D) are the "nShift" above, and the last 24 bits (AABBCC) contribute to the dDiff number.  It looks like to me that the "nShift" is the raw number of zero-bytes needed on the front of the hash (multiples of eight 0-bits), and the other 24 bits give you an adjustment factor.   Something like that...

The way I calculate the longest chain is to start with a pool of unorganized blocks, accessed by hash.  I go through all the blocks one-by-one, and follow them down to the genesis block (or the first block that I've already calculated) by following the "previous-hash" field, accumulating all the difficulty values as I go.  When I get to the "end", I walk back up the chain in the exact same order, and accumulate the difficulty-sums assigning them to each block as I go.  After that, I just find the block with the highest sum.   

The reason I can't just start at the genesis block and walk up is that "next-hash" is not initially defined.  And if the block chain forks anywhere, you would actually have two "next-hash" values, and you won't know which branch to follow without knowing the longest chain... but that's what we're trying to find!

But of course, you're going to need that difficulty calculation above to make it work.

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!)
remmy
Jr. Member
*
Offline Offline

Activity: 35


View Profile WWW
August 25, 2011, 12:45:46 AM
 #5

The 32-bit number you call difficulty (1DAABBCC) is actually a compressed representation of the current target, which is inversely proportional to difficulty.

Calculating difficulty should not be mysterious.  All you do to obtain it is divide a constant (a large integer) by the current target (another large integer).  The constant is:

0x00000000FFFF0000000000000000000000000000000000000000000000000000 = 0x1d00ffff in bits notation

Assume the current target is:

0x00000000000404CB000000000000000000000000000000000000000000000000 = 0x1b0404cb in bits notation

The resulting difficulty is:

16307.420938523983

If you line up the numbers and drop the zeroes in common, this example reduces to:

0xFFFF0000 / 0x000404CB, or 4294901760 / 263371, which you can punch into your calculator to confirm.

I'm a little concerned that over time, the cumulative difficulty will overshadow the current difficulty by several orders of magnitude.

At that point, attempting to calculate the difficulty of a set of block chains will not work, and every fork will be considered equivalent.

I'm wondering if it would cause problems if we stuck to integer division on the difficulty calculation, and that way we could avoid the problems tidily (using bignums).
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
August 25, 2011, 01:04:46 AM
 #6

I'm wondering if it would cause problems if we stuck to integer division on the difficulty calculation, and that way we could avoid the problems tidily (using bignums).

As the code I quoted in my first post shows, the client uses fixed-point bignum arithmetic to compare chains already.

ByteCoin
remmy
Jr. Member
*
Offline Offline

Activity: 35


View Profile WWW
August 25, 2011, 01:25:49 AM
 #7

ByteCoin, sorry for not noticing that in your quote.  Does that mean the difficulty calculation shown in the protocol specification in the wiki diverges from the method used in the client?

https://en.bitcoin.it/wiki/Difficulty


Code:
0x00000000FFFF0000000000000000000000000000000000000000000000000000 /
0x00000000000404CB000000000000000000000000000000000000000000000000
= 16307.420938523983
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
August 25, 2011, 02:24:17 AM
 #8

ByteCoin, sorry for not noticing that in your quote.  Does that mean the difficulty calculation shown in the protocol specification in the wiki diverges from the method used in the client?
In your original post, you're asking about the calculation which determines the valid block chain.
I believe that this calculation results in a value called bnChainWork calculated in the following fashion in main.cpp
Code:
bnChainWork = (pindexNew->pprev ? pindexNew->pprev->bnChainWork : 0) + pindexNew->GetBlockWork();

It's probably worth examining and taking the time to understand the source code I've pointed you to. You can then tell us yourself whether the wiki is correct and inform us of the relationship between the difficulties and the chainwork.

It's not obvious to me that satoshi's way of calculating chainwork cannot be manipulated to produce some undesirable behaviour.
This would be an interesting area for some research.

Also, it seems a little wasteful to do repeated bignum "reciprocal" calculation when the argument only changes every couple of thousand blocks.

ByteCoin
remmy
Jr. Member
*
Offline Offline

Activity: 35


View Profile WWW
August 25, 2011, 09:38:14 PM
 #9

Here is my analysis of GetBlockWork:

Current Codebase:
Code:
CBigNum GetBlockWork() const
    {
        CBigNum bnTarget;

        // expand the bits value to the current target
        bnTarget.SetCompact(nBits);

        // if the target is negative, return an undefined difficulty value (0)
        if (bnTarget <= 0)
            return 0;

        // return (2 ^ 256) / (current target + 1)
        return (CBigNum(1)<<256) / (bnTarget+1);
    }

Original Commit:
Code:
CBigNum GetBlockWork() const
    {
        return (CBigNum(1)<<256) / (CBigNum().SetCompact(nBits)+1);
    }

The documented wiki maximum target is 0xffff * 2 ^ 208, therefore the numerator should be CBigNum(0xFFFF) << 208; but this shouldn't cause any problems as the number used is larger than the documented target.

The routine returns 0 when the target is 0, the calling function should check for this return value and halt bitcoin transactions (the system can no longer determine who controls 51% of the resources of the network if the target is 0).

This makes adding 1 to the target unnecessary.

OpenSSL states that their bignums (from which the bitcoin bignums are derived) are integer only, so the fractional component displayed on the wiki is ignored in the client.
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!