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