On Mon, Dec 11, 2017 at 9:56 PM, Jim Posen via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
Omitting nBits entirely seems reasonable, I wrote up a possible implementation here. The downside is that it is more complex because it leaks into the validation code. The extra 4 byte savings is certainly nice though.

A compromise would be to have 1 byte indicating the difference since the last header.

Since the exponent doesn't use the full range you could steal bits from there to indicate mode.

- no change
- mantissa offset (for small changes)
- full difficulty

This would support any nBits rule and you say 3 of the 4 bytes.
 
Can you elaborate on how parallel header fetching might work? getheaders requests could probably already be pipelined, where the node requests the next 2,000 headers before processing the current batch (though would make sense to check that they are all above min difficulty first).

I suggest adding a message where you can ask for the lowest N hashes between 2 heights on the main chain.

The reply is an array of {height, header} pairs for the N headers with the lowest hash in the specified range.

All peers should agree on which headers are in the array.  If there is disagreement, then you can at least narrow down on which segment there is disagreement.

It works kind of like a cut and choose.  You pick one segment of the ones he gave you recursively.

You can ask a peer for proof for a segment between 2 headers of the form.

- first header + coinbase with merkle branch
- all headers in the segment

This proves the segment has the correct height and that all the headers link up.

There is a method called "high hash highway" that allows compact proofs of total POW.