<issue_start><issue_comment>Title: [WIP] Start in on hypothesis test for gap filling
username_0: ### What was wrong?

Fix #1929 

### How was it fixed?

Use hypothesis data draws. I think Piper is interested in the state machine approach, which may be superior.

### To-Do

[//]: # (Stay ahead of things, add list items here!)
- [ ] Clean up commit history

[//]: # (For important changes that should go into the release notes please add a newsfragment file as explained here: https://github.com/ethereum/py-evm/blob/master/newsfragments/README.md)

[//]: # (See: https://py-evm.readthedocs.io/en/latest/contributing.html#pull-requests)
- [ ] Add entry to the [release notes](https://github.com/ethereum/py-evm/blob/master/newsfragments/README.md)

#### Cute Animal Picture

![put a cute animal picture link inside the parentheses]()
<issue_comment>username_0: @username_2 hypothesis came up with another fun case:

```
B0
A1 (checkpoint)
A[0:10]
```

So what happens if you fill a gap, then cross a checkpoint, then fill the tail? It looks like it doesn't persist_header_chain() doesn't canonicalize the header at 0 to A.
<issue_comment>username_0: E               eth_utils.exceptions.ValidationError: <BlockHeader #1 bb9c3103> is not the parent of <BlockHeader #2 492097ce>

cls        = <class 'eth.db.header.HeaderDB'>
db         = <eth.db.atomic.AtomicDBWriteBatch object at 0x7faa4dc170b8>
expected_child = BlockHeader(parent_hash=b'\xd6\x99\xa7\xb9e\xe4\x17\xadn\x08m*\x97\xdc9@H\xb61\x9a\xa0\xf06!I\xe1\xf8\xaf\x14\x85\x12\xd6', uncles_hash=b'\x1d\xccM\xe8\xde\xc7]z\xab\x85\xb5g\xb6\xcc\xd4\x1a\xd3\x12E\x1b\x94\x8at\x13\xf0\xa1B\xfd@\xd4\x93G', coinbase=b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00', state_root=b'V\xe8\x1f\x17\x1b\xccU\xa6\xff\x83E\xe6\x92\xc0\xf8n[H\xe0\x1b\x99l\xad\xc0\x01b/\xb5\xe3c\xb4!', transaction_root=b'V\xe8\x1f\x17\x1b\xccU\xa6\xff\x83E\xe6\x92\xc0\xf8n[H\xe0\x1b\x99l\xad\xc0\x01b/\xb5\xe3c\xb4!', receipt_root=b'V\xe8\x1f\x17\x1b\xccU\xa6\xff\x83E\xe6\x92\xc0\xf8n[H\xe0\x1b\x99l\xad\xc0\x01b/\xb5\xe3c\xb4!', bloom=0, difficulty=17179869184, block_number=2, gas_limit=5000, gas_used=0, timestamp=1590013473, extra_data=b'f\xa0P\xba\x9a>\xf5v9\xf8!Ai\x1d?tz\xab\x02\xfb]\\\xa0H"\x03\xa9\xe6\x8as\xd7\x17', mix_hash=b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00', nonce=b'\x00\x00\x00\x00\x00\x00\x00B')
gap_change = <GapChange.GapFill: 3>
genesis_parent_hash = (b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
 b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00')
header     = BlockHeader(parent_hash=b'e\x96\xb4\nt\x1c\x8e\xb4-2\xaa\xced\xe0\x16]\xf7\x8f\x03Y\xaar\xf8\x0b\xdd\xef\xbe\x15\xe3\xeff\xef', uncles_hash=b'\x1d\xccM\xe8\xde\xc7]z\xab\x85\xb5g\xb6\xcc\xd4\x1a\xd3\x12E\x1b\x94\x8at\x13\xf0\xa1B\xfd@\xd4\x93G', coinbase=b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00', state_root=b'V\xe8\x1f\x17\x1b\xccU\xa6\xff\x83E\xe6\x92\xc0\xf8n[H\xe0\x1b\x99l\xad\xc0\x01b/\xb5\xe3c\xb4!', transaction_root=b'V\xe8\x1f\x17\x1b\xccU\xa6\xff\x83E\xe6\x92\xc0\xf8n[H\xe0\x1b\x99l\xad\xc0\x01b/\xb5\xe3c\xb4!', receipt_root=b'V\xe8\x1f\x17\x1b\xccU\xa6\xff\x83E\xe6\x92\xc0\xf8n[H\xe0\x1b\x99l\xad\xc0\x01b/\xb5\xe3c\xb4!', bloom=0, difficulty=17179869184, block_number=1, gas_limit=5000, gas_used=0, timestamp=1590013472, extra_data=b"4B\xc1\xb0@\xf3\xdaoA\x83\xf4Pt8M\x10\x8cw'\xeeK\xa8\x19\xdd\xb5\x02S\x1d<]\xbd\x9b", mix_hash=b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00', nonce=b'\x00\x00\x00\x00\x00\x00\x00B')
next_child_number = 2

eth/db/header.py:329: ValidationError
```
<issue_comment>username_0: Yup, and it's painful enough to make me wonder if this is the wrong approach.

So:
```
B0 - becomes canonical & head
A1 - persist as checkpoint, re-adds gap at 0
B[1:3] - B2 becomes canonical head, B[0:3] become canonical. -- but gap at 0 not marked as filled
A0 - crash, because it tries to fill the gap at 0, but the canonical child is B1
```

Some options are:

1. Disallow persisting B[1:3] (when the parent is at a gap. It should essentially always be at a checkpoint, so it's like saying you can't persist on top of a checkpoint)
2. Mark gap at 0 as filled when B[1:3] is persisted, overrides the checkpoint
3. Loosen gap filling requirements, allow non-canonical gap-fill as long as there's some child with a parent

I think 1 makes the most sense: disallow (implicitly) overriding a checkpoint
<issue_comment>username_0: Tried this approach. Not terrible, but not awesome.
<issue_comment>username_0: Maaybe the last one:

```
A0
B[0:2] - B becomes canonical
A1 - checkpoint -- A1 becomes canonical, but A0 doesn't
```
<issue_comment>username_0: Basically, just checked if parent of new checkpoint is available, and force it to canonical. I think this is insufficient: what if multiple parents are non-canonical. Just fixing that particular case ^.

Probably need to do something like find all ancestors and canonicalize them.
<issue_comment>username_0: The persist checkpoint was hacked to avoid looking at any parents. Tried another approach of just halting the lookup when ancestor headers are missing.
<issue_comment>username_0: Next hypothesis failure:

```
B[0:4]
A3 -- checkpoint
A[4:6]
A0 -- checkpoint
B[4:6]
A[1:2]
```

Getting a `eth_utils.exceptions.ValidationError: <BlockHeader #3 19b2746b> is not the parent of <BlockHeader #4 ea5d969c>`

So it looks like B3 stays canonical somehow, and so we're not allowed to fill the gap with A2? I'll have to pick it up from here tomorrow.
<issue_comment>username_1: Kind of cool to see hypothesis digging this stuff up!
<issue_comment>username_0: I'll split this into (at least) two before asking for reviews. But if anyone's interested in getting a first feel for the changes now, it's a reasonable time to look (now it's more than just my random explorations). I think the basics of a solution are all present.

A lot more changed than I thought. This addressed more than just the gap tracking, like:
- making sure checkpoints are never de-canonicalized
- when a new canonical head is chosen, make sure to decanonicalize the old niece blocks, even if they have a higher block number than the new head
- more...
<issue_comment>username_0: I haven't really thought about it, no. My first instinct is that most of the difficulty is introduced around accidental non-canonical blocks. So all of that should be handled by the headers before we even get to block tracking. One awkward thing is that after a block is persisted, but the header is decanonicalized, then we have to re-add the block gap too. (Maybe?) So not totally trivial.
<issue_comment>username_0: If no one wants me to split the PR, I'm happy to merge it as is. I did at least group two commits that were fairly distinct. I'll merge as-is tomorrow morning if no one objects.
<issue_comment>username_2: :shipit: