Bitcoin Forum
October 21, 2017, 09:07:16 AM
 News: Latest stable version of Bitcoin Core: 0.15.0.1  [Torrent]. (New!)
 Home Help Search Donate Login Register
 Pages: [1]
 Author Topic: Simple way to determine block chain length  (Read 1168 times)
remmy
Jr. Member

Offline

Activity: 35

 August 23, 2011, 11:28:32 PM

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?
1508576836
Hero Member

Offline

Posts: 1508576836

Ignore
 1508576836

1508576836
 Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
ByteCoin
Sr. Member

Offline

Activity: 416

 August 23, 2011, 11:48:33 PM

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

Activity: 35

 August 24, 2011, 10:32:37 PM

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

Offline

Activity: 1428

Core Armory Developer

 August 24, 2011, 11:07:11 PM

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

Activity: 35

 August 25, 2011, 12:45:46 AM

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

Offline

Activity: 416

 August 25, 2011, 01:04:46 AM

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

Activity: 35

 August 25, 2011, 01:25:49 AM

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

Offline

Activity: 416

 August 25, 2011, 02:24:17 AM

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?
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

Activity: 35

 August 25, 2011, 09:38:14 PM

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]