Merkle tree of the block hashes

[TierNolan]

I have been thinking about block commitments. 

One interesting commitment is to commit the root of a Merkle tree that contains all the block hashes as leaves.

This would help with initial synchronization.  You could pick the lowest N block hashes and prove that they are part of the same chain.

Starting from the last block in the set, each Merkle root could be checked to make sure everything is consistent.

Code:

                A
               / \
              /   \
             /     \
            /       \
           /         \
          /           \
         /             \
        B               C
       / \             / \
      /   \           /   \
     /     \         /    |
    D       E       F     G
   / \     / \     / \    |
  H   I   J   K   L   M   N 
 

To prove that block L is in the block chain, the path to block M can be sent and the previous link used to get to block M.  This has the advantage that the committed value for the Merkle root including block L is contained in block M.

This would mean sending hashes for B, G and L.

The Merkle root for block L can be recalculated.

Code:

                A*
               / \
              /   \
             /     \
            /       \
           /         \
          /           \
         /             \
        B               C*
       / \             / 
      /   \           /   
     /     \         /    
    D       E       F*
   / \     / \     /
  H   I   J   K   L
 

F* = Hash(L | L)   // L is known
C* = Hash(F* | F*) // F* is computed
A* = Hash(B* | C*) // C* is computed

A* is the new Merkle root and can be compared to the committed value.

If block K was being sent, then the branch to L would be sent (B, G and M).  B becomes the new Merkle root, so that is actually easier. 

This gives the similar (log(Blocks) * N) performance as the high hash highway, but is easier to explain.  Checking all the Merkle roots is probably overkill though.

With 1 million blocks, the paths would be 20 levels.  If the 16 best hashes were sent, that is 20 * 16 * 32 = 10kB to give a pretty accurate proof of the POW on the main chain.

With headers first, the proof length is 80MB for 1 million blocks.

If this commitment was used, the hash of the block that it starts at could be hard coded, so nodes don't check the auxiliary header before that.

[gmaxwell]

Using the lowest value hashes, however, let you pick the correct longest chain among multiple contenders... Which IMO is unfortunate since that means only really useful in a hard-coding model.

A much more powerful scheme (which basically uses the same commitments you're talking about) is proposed in the pegged sidechains paper as appendix b: http://www.blockstream.com/sidechains.pdf  it gives _exactly_ the same work computation as just traversing the chain one step at a time, and takes (in the expectation) exactly that amount of work to forge.

[TierNolan]

Using the lowest value hashes, however, let you pick the correct longest chain among multiple contenders... Which IMO is unfortunate since that means only really useful in a hard-coding model.

I am not sure what you mean.  The suggestion was to include the N lowest hashes for the compact proof.

A miner could be lucky to get the lowest hash.  The odds of getting N low hashes should be much lower.

A much more powerful scheme (which basically uses the same commitments you're talking about) is proposed in the pegged sidechains paper as appendix b: http://www.blockstream.com/sidechains.pdf  it gives _exactly_ the same work computation as just traversing the chain one step at a time, and takes (in the expectation) exactly that amount of work to forge.

Interesting.  I think the restriction limiting the steps to a fixed value is similar to having the N best hashes.  An attacker might get lucky once, but getting lucky N times is much less likely.

[gmaxwell]

A miner could be lucky to get the lowest hash.  The odds of getting N low hashes should be much lower.

And honest miners can be unlucky.  The point I was making is that the work you compute that way is not the same as the work computed the normal way. There is always some random error in the number, and so you may select the wrong chain that way, e.g. even assuming no attacker. Thats all.

[TierNolan]

And honest miners can be unlucky.  The point I was making is that the work you compute that way is not the same as the work computed the normal way. There is always some random error in the number, and so you may select the wrong chain that way, e.g. even assuming no attacker. Thats all.

Ahh ok.  I was thinking about initial sync and protecting against a chain that forked with low difficulty.  In that case a few percent error in the estimate is not that big a deal.  A new node would be able to determine which are the honest nodes.

Their situation needs to cover short range proofs.

The attack they suggest is to create a block where the entire Merkle tree points to the latest block.  Depending on what the POW of the block turns out to be, you can step back multiple steps at once.

Given that the height is committed too, that could be detected, since the number of hops would be wrong.

I wonder if committing the total POW for the block would be worth committing as part of the aux-header.