- Feature Name: sync_v2
- Status: Draft
- Start Date: 2020-10-16
- RFC PR: (leave this empty)
- Hathor Issue: (leave this empty)
- Author: Jan Segre jan@hathor.network, Marcelo Salhab Brogliato msbrogli@hathor.network
Version 2 of the protocol to synchronize the fullnode with the p2p network.
Sync-v1 propagates arbitrary orphan blocks that do not add to the network in any way and waste resources. More critically it will have to repropagate all those orphan blocks for the network to converge.
Sync-v2 uses many lessons from sync-v1. It is faster to sync, requires less indexing and uses less CPU.
The goal of the sync-v2 is to get the fullnode synchronized (synced) with the p2p network. As the network is decentralized and all nodes are equal, it happens that the fullnode must individually sync with each peer it is connected to. Even though we expect to have all peers agreeing in which is the bestchain, there might be one or more peers with different bestchains.
A checkpoint is a block that must be part of the bestchain, i.e. it cannot be orphan. It means that the bestchain must contain all checkpoints. The first natural and obvious checkpoint is the genesis with height zero. Sync-v2 supports static checkpoints, i.e., the list of checkpoints is hard-coded in the source code and cannot modified. There are several benefits to have support for checkpoints, including to prevent a large reorg attacks when the hashrate is not that big.
Notice that we wouldn't need to have a list of checkpoints because the last checkpoint itself uniquely defines the chain until the genesis block. But there are performance gains in the sync algorithm knowing intermediate checkpoints beforehand.
A transaction is said to be valid when it passes all verifications. If a transaction fails any verification, it is called invalid. Whether a transaction is valid or invalid is immutable, i.e., there's no way to change from valid to invalid or the other way around. Besides that, a transaction is either executed or voided. We say that a transaction is executed (or confirmed) when it takes effect (e.g. the funds are transferred). On the other hand, a transaction is voided when it is ignored (e.g. the funds are not transferred). A transaction may change from executed to voided and vice-versa over time (e.g. in case of a reorg). Notice that all executed transactions are necessarily valid. Invalid transactions should never be propagated to the network.
We say that a transaction belongs to the first block of the bestchain that verifies it. Transactions without a first block are said to be part of the mempool. Notice that, in case of a reorg, a block may turn into an orphan block and its transactions will be put back to the mempool.
From now on, let's enumerate the blocks of the bestchain by their heights (e.g., b0 is the genesis, b1 is the block with height one, b15 is the block with height 15, and so on and so forth). We can also use the following notation: [b0, b1, ..., b15, ...] to indicate a sequence of blocks connected by their parents.
Sync-v2 uses the fact that the weight of the blocks is way bigger than the transactions'. The synchronization happens in four phases: (i) sync the blocks until last checkpoint, (ii) sync the blocks from the last checkpoint to the latest best block, (iii) sync the mempool, and finally (iv) real-time propagation.
The first phase syncs all blocks (and their transactions) from genesis until last checkpoint. In this phase, we can safely download blocks from a given checkpoint and start going backwards (i.e., decreasing the height). For example, if we know that b100 is a checkpoint, we can safely download b99, and then b98, and then b97, and so on.
We say it is safe to download this sequence because nobody is able to create a fake sequence of blocks as we always check that b99 is the parent of b100, and then that b98 is the parent of b99, and so on. In this case, we say that we are downloading blocks from right (the newest) to left (the oldest).
Besides that, if we have a list of checkpoints (e.g. {b0, b100, b200, b300}), we can simultaneously download blocks from each of the checkpoints. It accelerates the sync because we can download a stream of blocks from each peer we are connected to. Let's say we have three connections. In this case, we can download [b100, b99, b98, ..., b0] from the first peer, while we also download [b200, b199, ... b101] from the second peer, while we also download [b300, b299, ..., b201] from the third peer. This speeds up the whole sync. This example is shown in the figure below:
After a block is downloaded and verified, the fullnode starts to download its transactions. The transactions of a block are downloaded starting from the two transactions verified by the block and going backwards, i.e., from the right (the newest ones) to the left (the oldest ones). In the image below, the transactions of b271 will be downloaded as follows: the orange ones ({ tx1, tx2 }), followed by the red ones ({ tx3, tx4, tx5 }), followed by the blue ones ({ tx6 and tx7 }), followed by the green one ({ tx8 }). The order is unknown inside each color group. From each transaction, we download both its parents (verification neighbors) and its inputs (fund neighbors).
The second phase syncs from the last checkpoint to the latest bestblock (and their transactions). The difference between Phase 2 and Phase 1 is that we do not know any checkpoints after the last one. So, we must download blocks from left (oldest) to right (newest), i.e., from the last checkpoint towards the bestblock.
In this phase, there's no way to be sure whether a peer is sending fake blocks to us. Of course, we verify all blocks and their proof-of-works to make it harder. Even so, an attacker may generate a fake blockchain and send it to strategically slow down the sync of a peer.
As we cannot trust the peers, the fullnode downloads the blocks from all peers it is connected to. Let's say we are connected to three peers, the last checkpoint is b300, and the best block is b650. It means that we will download [b301, b302, b303, ..., b650] from all three peers. We will probably receive duplicate blocks and waste some bandwidth.
This phase consists of two sub-steps that run in sequence: (i) discover the common block in the bestchain, and (ii) download blocks.
The discovery of the common block is necessary because we might already have some blocks. Let's say the fullnode was synced until block b402 and it was restarted. In this sub-step, we will find out that b402 is the common block. The discovery is done through an n-ary search algorithm detailed in the reference level implementation.
After we find out the common block (b402), we download blocks from it towards the best block. In our example, we will download blocks b403, then b404, then b405, and so on. After a block is downloaded and verified, the fullnode starts to download its transactions. This example is shown in the figure below:
Notice that Phase 1 and Phase 2 can run simultaneously. After both phases are finished, all blocks of the bestchain and their transactions will have been downloaded and verified. It is a benefit for miners, because after phase 2 is finished, the fullnode can start generating block templates for the mining API (even if phase 1 hasn't finished yet). This considerably reduces the required time to start mining (even though their blocks will not verify any transaction before the mempool is synced).
The mempool consists of transactions that have not been verified by any block in the bestchain yet. This phase can only start after phase 1 and phase 2 are finished.
It is critical to have the mempool synced because (i) wallets can quickly show new transactions and update the balance, (ii) miners need the mempool to confirm transactions, and (iii) new transactions should have the most recent transactions in the mempool as parents.
As the transactions form a Direct Acyclic Graph (DAG), the transactions in the mempool form a sub-DAG that connects to the sub-DAG of transactions confirmed by the bestchain (see figure below).
There are several optimizations and custom rules that can be applied in this phase. For example, we can safely discard a transaction that is in conflict with another transaction in the mempool (but we can't discard both, otherwise the transaction will be lost). If it happens that the discarded transaction is confirmed, it will be downloaded as soon as the new block is synced.
The mempool synchronizes from its unverified transactions (tips) toward the sub-DAG confirmed by the bestchain. We say it syncs from right (the most recent ones) to the left (the oldest ones). But the full-node cannot add a transaction that is not connected to its DAG. To solve it, the sync protocol walks through the DAG, downloading the dependencies (i.e. parents and inputs) of the transactions until they are connected to the DAG.
More specifically, the sync protocol gets a list of tips from the peer, picks a random tip the full-node does not have and download it. Let tx1 be this tip. Then, the sync runs the following recursive algorithm: If the full-node has all tx1's dependencies, then tx1 is simply added to the DAG and the sync goes to the next tip. Otherwise, it picks a random parent or input that it does not have, download it, and repeats the verification.
Notice that the sync protocol traversal is very similar to a DFS algorithm, i.e., it explores as far as possible along each tip before backtracking. As the full-node does not know how far each tip is from the sub-DAG confirmed by the bestchain, the sync protocol uses a sliding window with maximum length while it downloads the transactions. So, when the farthest transactions will eventually be discarded and might have been downloaded again later. The sliding window limits the memory usage and thus protects the full-node.
Another advantage of traversing the DAG from right to left is that it prevents attack from malicious peers. Let's say an attacker would like to generate a very long chain of transactions that never connects to the DAG. In this case, the right-to-left traversal forces the attacker to pre-generate and store the whole sub-DAG because a valid DAG can only be generated from left to right. In other words, the attacker cannot generate this sub-DAG in real-time. The sliding window prevents the full-node of a DoS attack on memory.
Besides that, the sync protocol has only unexpensive operations, making a DoS attack on CPU very unlikely.
XXX Is it safe to run Phase 3 in parallel with Phases 1 and 2? I feel it isn't because we don't know when it should stop.
After the blocks and transactions are fully synced, the fullnode enters in the real-time propagation mode. It means that the fullnode will receive any new block/transaction propagated to the network, and it will propagate them to all its peers.
This flood strategy is important to guarantee that all peers will receive the new blocks/transactions as soon as possible. New blocks received in this phase cannot have a parent block between the genesis and the last checkpoint.
In order to increase support to other clients, the sync protocol will only relay blocks and transactions to peers who enabled it. It means that the full-node must enable relay from the peers it would like to. For example, it might be used by exchanges to run custom clients around the world that fastly relay blocks to their central to reduce the chance of finding an orphan block.
The default criteria for the full-node is to enable relay after it has successfully finished the sync of mempool for the first time and never disables it.
As we may happen to download blocks and transactions that does not reach the genesis, we cannot guarantee we will have all parents and inputs to fully validate the blocks and transactions. So, we split the validation in the following states:
not-validated: initial state, no validation has been made yet.
basic-validated: all graph fields (except the parents and inputs) are valid, including the PoW, the weight field, the timestamp, etc. Funds fields have not been verified yet.
full-validated: the block/transaction has been fully validated and reaches the genesis.
invalid: this block/transaction is invalid and might be discarded (could be kept for quick hash detection or for banning the original peer that propagated it).Notice that
full-validatedrequires the block/transaction to reach the genesis to get to this validation state. It is a critical part of this state because it guarantees that all blocks and transactions behind it arefull-validatedas well.The transitions between the states are shown in the figure below:
A block/transaction can go from
not-validatedtoinvalidfor different reasons (e.g. invalid PoW, invalid timestamp, no outputs, no inputs). These blocks/transactions might be immediately discarded.The common reasons that moves a block/transaction from
basic-validatedtoinvalidare (i) the funds are unbalanced and fails, and (ii) any of their parents or inputs are invalid. The invalid block/transactions can be discarded any time. XXX Should we do it during the node initialization?Notice that the validation state is not related to the status (executed/voided) of the transaction. For clarity, orphan blocks and voided transactions are
full-validatedtransactions.All transactions of the mempool must be
full-validated. If they can't be fully validated, they can be safely discarded.We will rarely have a
not-validatedblock/transaction because they are basically verified as soon as they are received. No transaction/block saved in the storage might benot-validated.
As of v0.58.0 the phases 2 through 4 have been implemented without using the stateful validation, instead the protocol instance holds the transactions/blocks temporarily until the portion that is being downloaded reaches verified vertices, they are fed to HathorManager.on_new_tx in topological order.
The fullnode receives new blocks and transactions from two different sources: (i) the Sync Protocol, and (ii) its APIs.
When the source is the Phase 1 of the Sync Protocol, we may optimize and only verify the PoW. This optimization assumes that nobody can generate another transaction with the same hash as the original transaction (because it would imply finding a sha256 conflict). The fullnode currently does not use this optimization and verifies every block/transaction received.
When a transaction is received by the API, it must be fully validated. If it is not possible, the fullnode must reject it.
Each peer connected to the fullnode has its own progress indicator. As we know the height of the best block of a given peer, we know how many blocks we still need to download to finish the sync. We say that a block is fully downloaded when the block and all its transactions have been sucessfully downloaded. We can say that sync_percentage = #(remaining blocks) / #(total blocks) = 1 - downloaded_blocks / height_best_block.
We say that we are synced to a peer when all blocks between the genesis and the best block have been fully downloaded. The mempool does not affect the sync status. We can also say that we are virtually synced when we have downloaded all blocks but we are still downloading transactions.
TODO Global sync progress? We may get the score the best block, so we can calculate how many blocks we need to download until we reach it (regardless of the peers).
TODO Measure progress of the mempool?
TODO Measure progress of the block? We may include the number of transactions inside a block as a metadata.
The bestchain is the chain with the highest score among all chains. Notice that a new bestchain does not affect Phase 1 because it must have all checkpoints inside it. So, during Phase 2, our fullnode will verify that the peer has a different best block.
In this case, during the first sub-step, it will find out the most recent block we have in common with the peer. Then, in the second sub-step, the fullnode will download the blocks of the new bestchain.
After the last block is fully downloaded, the consensus algorithm will confirm that this chain has a higher score and will set it as the new bestchain.
As soon as the new bestchain is set, all other peers connected to us will do the same during their Phase 2 with us. This way, the new bestchain will be propagated through the whole network.
The double spending problem is solved by the following rules:
-
There cannot be two or more transactions spending the same output confirmed by blocks in the bestchain. If it would have happened, the blocks and conflicting transactions would be voided, and the blocks would not be part of the bestchain.
-
There cannot be any transaction in the mempool spending the same output as a transaction confirmed by the bestchain. In this case, the transaction in the bestchain is executed while the transaction in the mempool is voided (and may be discarded).
-
If there are two or more transactions in conflict in the mempool, different rules may be applied. The most common rule is to execute the one with highest accumulated weight and void all the others. But the mempool algorithm may even decide to discard some of these transactions. When one of these transaction is confirmed by a block, it will be synced by Phase 2 and the others will be foverer voided.
In order to update the peers in the mainnet, a new release of the fullnode will support a bridge mode. The bridge will accept connections from both sync-v1 and sync-v2, guaranteeing that blocks and transactions are propagated between peers using sync-v1 and sync-v2.
As we want to disable sync-v1 as soon as possible, the bridge will not be enabled by default, and most new fullnodes will accept only connections using sync-v2.
Hathor Labs will run a couple bridges and will monitor the other fullnodes. After the majority of the fullnodes have updated to sync-v2, Hathor Labs will turn off their bridges, and the migration will be completed. The next release of the fullnode can remove sync-v1 completely.
The Sync Protocol is a text and line-based protocol, i.e., the content is in a human-readable format and it has one command/reply per line. It is generally stateless, which means the peers can send messages in any order (except for a few).
These are the message used by the Sync-v2 Protocol:
-
GET_NEXT_BLOCKS: It requests to start a streaming of blocks between two checkpoints. -
BLOCKS: It carries one block inside the message. -
BLOCKS_END: It indicates that the current streaming of blocks has finished. -
GET_BEST_BLOCK: It requests the hash and height of the best block. -
BEST_BLOCK: It is a response to aGET_BEST_BLOCKmessage. -
GET_TRANSACTIONS_BFS: It starts a streaming of transaction from a list of given hashes, a "first block" hash which has to match the first block of the given transactions, and a "last block" which marks when to stop because the requester already has that block (and everything before it). -
TRANSACTION: It carries one transaction inside the message. -
TRANSACTIONS_END: It indicates that the current streaming of transactions has finished. -
GET_PEER_BLOCK_HASHES: It requests the hashes of the blocks in the bestchain associated with a list of heights. -
PEER_BLOCK_HASHES: It is a response to aGET_PEER_BLOCK_HASHESmessage. -
STOP_BLOCK_STREAMING: It requests the other peer to stop the streaming. -
GET_TIPS: It requests the peer to send its unconfirmed transaction tips so we can start to build the mempool from those. -
TIPS: It carries one transaction inside the message in response toGET_TIPS. -
TIPS_END: It indicates that the streaming of tips has finished. -
RELAY: It carries a boolean flag to indicate that the remote peer should relay (or stop relaying) vertices (blocks or transactions) in real-time. -
DATA: It is used to relay (propagate) vertices in real-time. -
ERROR: It indicates an error has occured. Usually the connection is closed right after the error.
The sync happens between two consecutive checkpoints, i.e., let [cp0, cp1, cp2, ..., cpN] be the list of checkpoints, the sync will run between the intervals [cp0, cp1], [cp1, cp2], [cp2, cp3], ..., [cp{N-1}, cpN]. In each case, the fullnode requests a peer to send a streaming of blocks starting at the end of the interval towards the beginning (e.g., if cp2 = b200 and cp3 = b300, we will receive the block b300, followed by b299, followed by b298, and so on until we receive b200).
The fullnode's best block, always fully validated and reaching back to the genesis, allows the fullnode to determine if syncing up to the last checkpoint is complete. This is done by comparing the height of the best block with that of the last checkpoint. Specifically, if bestblock.height >= last_checkpoint.height, then Phase 1 is considered complete.
Similarly, the fullnode can identify which checkpoints are yet to be downloaded. Download management is centralized through a SyncCheckpoint instance, shared across all peer connections. This approach optimizes and distributes the downloading task among peers.
XXX: as of hathor-core v0.58.0, which published the first generally available sync-v2 implementation, this phase is skipped and the syncing from checkpoints is not available. It will be available in a future version possibly enabled through a "capability" or a different sync version marker (i.e. sync-v2.1).
- Send
GET_PEER_BEST_BLOCKto ascertain the peer's best block. - If it matches our best block, we are "block synced," and Phase 3 begins. Concurrently, we enter a sleep state and later restart Phase 2.
- If the peer's best block is already known to us, indicating the peer is lagging, we enter a sleep state and later restart Phase 2, as there is nothing to gain from this peer.
- If the peer has a best block unknown to us, we are out of sync. Send
RELAY falseto stop them from sending real-time transactions, in case this was previously enabled. - Conduct a n-ary search to find the best common block, from which we'll start requesting blocks.
- After finding the best common block, request a stream of blocks starting from that block and ending at the peer's best block, using
GET_NEXT_BLOCKS.Expect manyBLOCKSand finally aBLOCKS_END, or sendSTOP_BLOCK_STREAMINGin case of errors in processing these blocks. - Request the necessary transactions for validating those blocks, starting from the transactions we don't have and ending at the highest block in this chain that we have processed. We also send the block expected to be the first block of the starting transactions, using
GET_TRANSACTIONS_BFS. Expect manyTRANSACTIONmessages and finally aTRANSACTIONS_END, or sendSTOP_TRANSACTIONS_STREAMINGin case of errors in processing these transactions. - This phase does not guarantee reaching the remote peer's best block, but it ensures advancement. Restart Phase 2 until "block synced" status is achieved.
For each peer, start when we’re in sync and our best chain ends in a full-validated block. Continually poll unconfirmed transactions from each peer. The command has a limit on the number of transactions returned, but this is acceptable because once they’re confirmed by a block, sync-transactions will eventually retrieve them.
Note: In theory, syncing the mempool is not necessary for the convergence of syncing peers. However, it should speed up the process, particularly in ensuring that unconfirmed transactions reach the nodes of miners.
This phase can, in theory, be enabled and disabled at any moment. When a peer sends RELAY true, it signals the remote peer that it wants to receive relayed transactions/blocks. Conversely, RELAY false indicates the desire to stop receiving them. The only downside of receiving relayed vertices too early is the potential waste of resources in attempting to verify them. In practice, this phase is enabled as soon as Phase 3 is reached, as it is a good indicator that the relayed vertices will be successfully processed. There isn't really any advantage in enabling it sooner.
[yan] It's still not clear to me how all parts connect. After we move from phase 1 to phase 2, I guess we will download all txs from the right-most block until genesis.
Although phase-1 and phase-2 are separate, phase 2 can start in parallel, I’d say we go with whatever is more convenient to implement. About the order of download, this needs a lot of clarification IMO. (I personally find left-to-right/right-to-left very hard to visualize) We can ask for the txs from either order, but we receive them in BFS order. Starting from the highest height will minimize these “get-block-txs” commands, I wouldn’t call it “right-to-left” order because we would only have to go left if we reach the tx stream limit. But if we start phase-2 in parallel, we would, in practice, visit the blocks from right-to-left (or ascending height order) in jumps (or not).
Then phase 3 is the most unclear to me. What's the mempool? In Bitcoin, it's the pool of unconfirmed transactions. Doesn't seem to be the same here.
Yes, it’s unclear for me too, or rather, it’s clear that we haven’t defined a solution. But “mempool” is just a nickname.
Also, I'm trying to figure out how conflict resolution happens. Let's say a new node joins the network with a different best chain that has more hashrate than the one I currently consider the best chain. How would I determine this new chain should be the winner? At one point when syncing with it, our blockchains will diverge. Should I mark it as out-of-sync and continue syncing so we get to the end of it and check if this new chain has a higher hashrate than mine?
From my understanding, after phase-1 catches up to the last checkpoint, it could very well download multiple forks. And then phase-2 would download all transactions for all chains Eventually validation will reach full-validated on all blocks/txs and the consensus will have properly marked the metadata (voids/conflicts) and we’d be in the same place we would on sync-v1.
[pedro] some questions
When does phase 1 ends? Does it run in parallel with phase 2? As far as I understood phase 2 will start when we sync all blocks until the latest checkpoint. As we still have more blocks to sync, I believe they will run both at the same time. Moreover phase 2 runs from right to left (at least that’s what I think), then if we have more blocks arriving every moment on the right of the best chain, are we “starting over” phase 2 every time or do we run the tx sync for the new blocks after downloading all txs before the first checkpoint? I think we could try to run phase 2 only after downloading all blocks in phase1 (even after the checkpoint), then the same when switching for phase3. Then we leave the remaining txs/blocks for the last phase or for the real time update.
Technically phase-2 can start as early as we have the first block that reaches “basic-validated”. There is no harm (just efficiency loss) in having the phases separate. I’d say we try to implement them together and if there’s any complication we leave them separate.
If we continue to run phase 1 even after phase 2 has started, I think phase 3 would have to deal only with txs that are still not confirmed by any blocks, right? And are we going to receive new blocks while on phase 3 as well?
We should not start phase-3 while there are blocks/txs that are neither “full-validated” or “invalid” (that is, which we have had enough information to run a full validation on them). This also marks the end of phase-1/phase-2.
What’s the new definition of “I am synced with peer X”?
I don’t know. I wonder if we still need that concept (“can-start-mining” aside).
When I am in sync with another peer, how would the sync algorithm work? Just the same real time update as we have in v1?
Yes, that’s the idea: periodically run a “tips check”, but constantly repropagate data to them.
Why should we not do this?
- Why is this design the best in the space of possible designs?
- What other designs have been considered and what is the rationale for not choosing them?
- What is the impact of not doing this?
Discuss prior art, both the good and the bad, in relation to this proposal. A few examples of what this can include are:
For protocol, network, algorithms and other changes that directly affect the code: Does this feature exist in other blockchains and what experience have their community had? For community proposals: Is this done by some other community and what were their experiences with it? For other teams: What lessons can we learn from what other communities have done here? Papers: Are there any published papers or great posts that discuss this? If you have some relevant papers to refer to, this can serve as a more detailed theoretical background.
This section is intended to encourage you as an author to think about the lessons from other blockchains, provide readers of your RFC with a fuller picture. If there is no prior art, that is fine - your ideas are interesting to us whether they are brand new or if it is an adaptation from other blockchains.
Note that while precedent set by other blockchains is some motivation, it does not on its own motivate an RFC. Please also take into consideration that Hathor sometimes intentionally diverges from common blockchain features.
Bitcoind (bitcoin-core) seems to use a similar strategy. TODO: research and detail more about it, so we can potentially avoid any pitfall we might have missed.
What parts of the design do you expect to resolve through the RFC process before this gets merged? What parts of the design do you expect to resolve through the implementation of this feature before stabilization? What related issues do you consider out of scope for this RFC that could be addressed in the future independently of the solution that comes out of this RFC?
Is it worth caching invalid blocks (or at least their hashes) in order to fast reject/ban peers sending them? Should we add a “originally_sent_by: PeerId” metadata, and additionally a message signed by that peer-id so we can use it to repropagate the block before validating it, so we aren’t banned in case the block is valid. Or is this overkill? Should we try to optimize the “get-blocks-range” (TODO: use the correct command name) for efficient bandwidth usage (i.e., by using a compact encoding, grouping blocks and using a stream iterator). Should we accept blocks pushed by other peers while on phase-2?
Think about what the natural extension and evolution of your proposal would be and how it would affect the network and project as a whole in a holistic way. Try to use this section as a tool to more fully consider all possible interactions with the project and network in your proposal. Also consider how this all fits into the roadmap for the project and of the relevant sub-team.
This is also a good place to "dump ideas", if they are out of scope for the RFC you are writing but otherwise related.
If you have tried and cannot think of any future possibilities, you may simply state that you cannot think of anything.
Note that having something written down in the future-possibilities section is not a reason to accept the current or a future RFC; such notes should be in the section on motivation or rationale in this or subsequent RFCs. The section merely provides additional information.
TODO: some unresolved questions might be resolved as “maybe in the future”, move them here