New ADR-21 approach

[frolosofsky]

This change relates to ADR-12, fork-choice rule.

This document describes a new headers-and-votes exchange approach. Peer downloads headers+votes in an epoch. If it looks legitimate, peer downloads the bunch of blocks in this epoch, validates them, and continue with next epoch until it reaches the end-of-chain.

Signed-off-by: Stanislav Frolov stanislav@thirdhash.com

[thothd]

I also suggest adding short info on why the previous approach wasn't eventually used and this one is better (you can also link to the specific commit)

[kostyantyn]

As we discussed and the majority agreed on the fast/full sync order of commands. I want to express my proposal (which is different) just for the sake of the record. Then we can always reference this thread why we didn't pick it up. Also, I think it can go to UIP to the section of other ideas considered as that's what we wanted to have.

The summary of the agreed fast sync solution (correct me if smth is missing)

1. we discover snapshot hashes and their heights
2. we pick the peer with the highest snapshot
3. we download headers first from that peer (to see that the point of the snapshot it claims exists), if not, restart from step=2
4. we download commits to verify that the snapshot is indeed finalized otherwise, repeat from step=2 but avoiding downloading existing headers/commits if there are any.
5. we download the snapshot.

my proposal is the following (some steps common for full/fast sync):

1. we download headers + commits of the first dynasty from the first peer
2. verify the dynasty by commits, and in case all is good a. in fast sync do nothing b. in full sync download blocks
3. progress until the end of the tip repeating step 1-2
4. after fully synced with the first peer, if there are other peers, check that we can progress further with the justification checkpoint (repeating step 1-3)
5. after syncing all headers + commits: a. in full sync we exit IBD (as we also have all blocks) b. in fast sync we discover snapshots from peers
6. if there are snapshots, we take the one that points to the highest finalized epoch and download it
7. in case we can't download the snapshot or no valid snapshot was discovered, we switch to full sync and download blocks for our best chain (it's already constructed and validated)

The reasoning of the proposal:

1. if we do header + commits, I believe we save on bandwidth. We don't request two messages instead of one.
2. In case the peer tries to fool us, we quicker detect that (based on commits) and don't download all headers. But in the worst-case scenario (peer claims there are no commits), then we will download exactly the same data as in headers-only sync
3. there is no overhead of downloading headers+commits because we would still need them after the headers and we won't download extra commits because there are as many as validators (so regardless of how many forks, number of commits will be the approximately the same).
4. node doesn't need to keep all headers in memory (from the Genesis to the tip) because as we progress gradually, we can delete those between two checkpoints up to the MIN_BLOCKS_TO_KEEP)
5. align the flow between fast/full sync will allow us (if needed) to switch between them. E.g. we started with the fast sync, we had to switch to full sync then we see that there is a possibility to switch back as new snapshot appeared (don't forget that full sync can take a couple of days).
6. allows to reduce the code as fast/full sync significantly will be very similar, only in the fast sync, we replace blocks with a snapshot.

[frolosofsky]

@kostyantyn,

As we already had conversation about this, I totally agree with your points. But let's don't mix and discuss multiple topics in single PR, otherwise we never merge it. I'd love to see your proposal in different PR to this ADR once this one gets merged (or, if you're eager to start, setup your branch on top of this one and then rebase).

One thing I want to point out you can address in our PR:

node doesn't need to keep all headers in memory (from the Genesis to the tip) because as we progress gradually, we can delete those between two checkpoints up to the MIN_BLOCKS_TO_KEEP)

I believe we shouldn't delete headers as well as commits from memory, because it's quite often scenario that other peers would ask you to sync from some point in past. Before do this, we have to measure all cons and pros. I can imagine this is useful when node is almost out of memory only.

[thothd]

@kostyantyn,

As we already had conversation about this, I totally agree with your points. But let's don't mix and discuss multiple topics in single PR, otherwise we never merge it. I'd love to see your proposal in different PR to this ADR once this one gets merged (or, if you're eager to start, setup your branch on top of this one and then rebase).

One thing I want to point out you can address in our PR:

node doesn't need to keep all headers in memory (from the Genesis to the tip) because as we progress gradually, we can delete those between two checkpoints up to the MIN_BLOCKS_TO_KEEP)

I believe we shouldn't delete headers as well as commits from memory, because it's quite often scenario that other peers would ask you to sync from some point in past. Before do this, we have to measure all cons and pros. I can imagine this is useful when node is almost out of memory only.

I totally agree with @frolosofsky, the Bitcoin protocol heavily relies on being able to iterate over ALL the headers fast - in our case headers + commits. I don't think it's related to being out of memory or not, the importance of the first header is as the last one. There are other ways to decrease the overall memory consumption (mempool, dbcache, as specified here https://gist.github.com/laanwj/efe29c7661ce9b6620a7).

@kostyantyn I'm not sure on how the items you wrote are related to the this proposal. We should discuss about it separately and think on all the different tradeoffs but what sometimes looks like an optimization can have security or other implications. Anyway It already took us good amount of work until we got to something good for this ADR and I wouldn't mix the fork choice rule with the fast sync specifics.

[kostyantyn]

@frolosofsky @thothd will move this discussion to a separate PR to this ADR.

Since this ADR defines messages that will be used for fast/full sync, I think it's good if such parts are covered in this and not separate ADR and we already have sections in the document where we describe the impact on fast sync / SPV, so it's good to extend.