Quote from: HZKto on December 20, 2013, 09:28:47 PM

we should add ability to request block headers sorted by difficulty, starting with the most expensive one and continue in descending order. This would allow to detect flood with even less traffic, like few percents of Max_Blocks.

There would be no way to prove that they are part of the chain.

In the High hash highway, a second pointer is added. Headers would have a link to the previous block and also an "up" link.

This allows you follow backwards from the leaf of the chain much faster, but still hit all the high blocks. However, it is a hard fork.

The 2nd link points to the nearest block with more leading zero bits than the previous block.

In fact, I think optimal would be, point to the block after the nearest block with more leading zero bits than the previous block.

So, the blocks had the following leading zero bits

A) 30
B) 31 - up -> genesis (since 30 is the best so far)
C) 29 - up -> genesis (since 31 is the best so far)
D) 33 - up -> C
E) 31 - up -> genesis (since 33 is the best block)
F) 32 - up -> E
G) 30 - up -> E
H) 32 - up -> G

If you follow the up link backwards, you go to a block that is the successor of a block with at least 1 more leading zero than the previous block.

To find the highest block, these are the steps

- Set N to the index of the leaf block
- Set b to the number of leading zeros for block N-1

Loop
- The up pointer for block N points to block M
- Block M-1 has more leading zeros than block N-1 (by definition)
- It also has more leading zeros than any blocks from N-1 to M, inclusive
- This means you can't have skipped a better block than block M-1
- set N = M
- set b = the number of leading zeros for block M-1

Each time through the loop b is guaranteed to increase and also you are guaranteed not to skip the best block.

Therefore, this search will find the best block.

The PoW of the main chain can be estimated just by looking at the work of the best block.

You can also use the system to find all blocks which have difficulty within a number of bits of the best block.