Simple way to determine block chain length

[remmy]

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?

[1714191316]

1714191316

[1714191316]

1714191316

[ByteCoin]

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]

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]

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.

[remmy]

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]

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]

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]

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]

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.