Bitcoin Stack Exchange is a question and answer site for Bitcoin users, developers, and enthusiasts. It only takes a minute to sign up.
Sign up to join this community
Beginner questions...
I understand that everybody has their own copy of the blockchain.
If one person makes a change, for example a transaction, I assume that it has to propagate to all other nodes. How long does this take?
How does a node know that the update process is complete throughout the blockchain?
What algorithm is used to synchronize and what is its order (O())?
The Blockchain is never changed only extended.
As I understand it, nodes do not explicitly check or care whether other nodes have identical copies. They just verify what they receive against what they already have in their copy of the Blockchain.
Synchronisation isn't exactly the right word to describe what happens but it effectively occurs as a consequence of nodes applying the same "consensus" rules. Nodes follow the longest chain, the one with most proof of work.
The blockchain is an append-only data structure. The only changes that happen are appending to an existing chain or rolling back blocks to switch onto a better chain that forks off earlier.
Nodes always attempt to be on the valid chain with the most proof of work.
To accomplish this they synchronize block headers with their peers. Synchronization of headers uses locator messages: You send your peer a list of block IDs that you know going back to the initial block, and your peer finds the highest point in the list that they know and sends you headers after that point-- which you probably don't know. To make this efficient, the space between headers in the locator list doubles every entry after the first few. This causing the header synchronization process to be O(log n).
Once the node has a connected set of new headers that are a candidate for the most-work chain it starts fetching blocks along that chain of headers-- from peers that claim to have those block according to their header announcements-- and validating them. If it encounters an invalid block, disconnects the origin, marks it and all headers in the chain after that block as invalid, and figures out where the new most work tip would be disregarding all the headers for invalid blocks and begins fetching and validating blocks towards that new best tip.
