兄弟连区块链入门教程以太坊源码分析fast sync算法一

　　兄弟连区块链入门教程以太坊源码分析fast sync算法一，2018年下半年，区块链行业正逐渐褪去发展之初的浮躁、回归理性，表面上看相关人才需求与身价似乎正在回落。但事实上，正是初期泡沫的渐退，让人们更多的关注点放在了区块链真正的技术之上。

this PR aggregates a lot of small modifications to core, trie, eth and other packages to collectively implement the eth/63 fast synchronization algorithm. In short, geth --fast.

这个提交请求包含了对core，trie,eth和其他一些package的微小的修改，来共同实现eth/63的快速同步算法。 简单来说， geth --fast.

## Algorithm算法

The goal of the the fast sync algorithm is to exchange processing power for bandwidth usage. Instead of processing the entire block-chain one link at a time, and replay all transactions that ever happened in history, fast syncing downloads the transaction receipts along the blocks, and pulls an entire recent state database. This allows a fast synced node to still retain its status an an archive node containing all historical data for user queries (and thus not influence the network's health in general), but at the same time to reassemble a recent network state at a fraction of the time it would take full block processing.

快速同步算法的目标是用带宽换计算。快速同步不是通过一个链接处理整个区块链，而是重放历史上发生的所有事务，快速同步会沿着这些块下载事务处理单据，然后拉取整个最近的状态数据库。这允许快速同步的节点仍然保持其包含用于用户查询的所有历史数据的存档节点的状态（并且因此不会一般地影响网络的健康状况），对于最新的区块状态更改，会使用全量的区块处理方式。

An outline of the fast sync algorithm would be:

- Similarly to classical sync, download the block headers and bodies that make up the blockchain

- Similarly to classical sync, verify the header chain's consistency (POW, total difficulty, etc)

- Instead of processing the blocks, download the transaction receipts as defined by the header

- Store the downloaded blockchain, along with the receipt chain, enabling all historical queries

- When the chain reaches a recent enough state (head - 1024 blocks), pause for state sync:

    - Retrieve the entire Merkel Patricia state trie defined by the root hash of the pivot point

    - For every account found in the trie, retrieve it's contract code and internal storage state trie

- Upon successful trie download, mark the pivot point (head - 1024 blocks) as the current head

- Import all remaining blocks (1024) by fully processing them as in the classical sync

快速同步算法的概要：

-与原有的同步类似，下载组成区块链的区块头和区块body

-类似于原有的同步，验证区块头的一致性（POW，总难度等）

-下载由区块头定义的交易收据,而不是处理区块。

-存储下载的区块链和收据链，启用所有历史查询

-当链条达到最近的状态（头部 - 1024个块）时，暂停状态同步：

-获取由 pivot point定义的区块的完整的Merkel Patricia Trie状态

-对于Merkel Patricia Trie里面的每个账户，获取他的合约代码和中间存储的Trie

-当Merkel Patricia Trie下载成功后，将pivot point定义的区块作为当前的区块头

-通过像原有的同步一样对其进行完全处理，导入所有剩余的块（1024）

##分析 Analysis

By downloading and verifying the entire header chain, we can guarantee with all the security of the classical sync, that the hashes (receipts, state tries, etc) contained within the headers are valid. Based on those hashes, we can confidently download transaction receipts and the entire state trie afterwards. Additionally, by placing the pivoting point (where fast sync switches to block processing) a bit below the current head (1024 blocks), we can ensure that even larger chain reorganizations can be handled without the need of a new sync (as we have all the state going that many blocks back).

通过下载和验证整个头部链，我们可以保证传统同步的所有安全性，头部中包含的哈希（收据，状态尝试等）是有效的。基于这些哈希，我们可以自信地下载交易收据和整个状态树。另外，通过将pivoting point（快速同步切换到区块处理）放置在当前区块头（1024块）的下方一点，我们可以确保甚至可以处理更大的区块链重组，而不需要新的同步（因为我们有所有的状态 TODO）。

##注意事项 Caveats

The historical block-processing based synchronization mechanism has two (approximately similarly costing) bottlenecks: transaction processing and PoW verification. The baseline fast sync algorithm successfully circumvents the transaction processing, skipping the need to iterate over every single state the system ever was in. However, verifying the proof of work associated with each header is still a notably CPU intensive operation.

基于历史块处理的同步机制具有两个（近似相似成本）瓶颈：交易处理和PoW验证。 基线快速同步算法成功地绕开了事务处理，跳过了对系统曾经处于的每一个状态进行迭代的需要。但是，验证与每个头相关联的工作证明仍然是CPU密集型操作。

However, we can notice an interesting phenomenon during header verification. With a negligible probability of error, we can still guarantee the validity of the chain, only by verifying every K-th header, instead of each and every one. By selecting a single header at random out of every K headers to verify, we guarantee the validity of an N-length chain with the probability of (1/K)^(N/K) (i.e. we have 1/K chance to spot a forgery in K blocks, a verification that's repeated N/K times).

但是，我们可以在区块头验证期间注意到一个有趣的现象由于错误概率可以忽略不计，我们仍然可以保证链的有效性，只需要验证每个第K个头，而不是每个头。 通过从每个K头中随机选择一个头来验证，我们保证N长度链的可能会被伪造的概率为（1 / K）^（N / K）（在K块中我们有1 / K的机会发现一个伪造，而验证经行了N/K次。）。

Let's define the negligible probability Pn as the probability of obtaining a 256 bit SHA3 collision (i.e. the hash Ethereum is built upon): 1/2^128. To honor the Ethereum security requirements, we need to choose the minimum chain length N (below which we veriy every header) and maximum K verification batch size such as (1/K)^(N/K) <= Pn holds. Calculating this for various {N, K} pairs is pretty straighforward, a simple and lenient solution being http://play.golang.org/p/B-8sX_6Dq0.

我们将可忽略概率Pn定义为获得256位SHA3冲突（以太坊的Hash算法）的概率：1/2 ^ 128。 为了遵守以太坊的安全要求，我们需要选择最小链长N（在我们每个块都验证之前），最大K验证批量大小如（1 / K）^（N / K）<= Pn。 对各种{N，K}对进行计算是非常直接的，一个简单和宽松的解决方案是http://play.golang.org/p/B-8sX_6Dq0。

|N   |K      |N   |K       |N   |K       |N   |K |

| ------|-------|-------|-----------|-------|-----------|-------|---|

|1024   |43     |1792   |91      |2560   |143        |3328   |198|

|1152   |51     |1920   |99      |2688   |152        |3456   |207|

|1280   |58     |2048   |108        |2816   |161        |3584   |217|

|1408   |66     |2176   |116        |2944   |170        |3712   |226|

|1536   |74     |2304   |128        |3072   |179        |3840   |236|

|1664   |82     |2432   |134        |3200   |189        |3968   |246|

The above table should be interpreted in such a way, that if we verify every K-th header, after N headers the probability of a forgery is smaller than the probability of an attacker producing a SHA3 collision. It also means, that if a forgery is indeed detected, the last N headers should be discarded as not safe enough. Any {N, K} pair may be chosen from the above table, and to keep the numbers reasonably looking, we chose N=2048, K=100. This will be fine tuned later after being able to observe network bandwidth/latency effects and possibly behavior on more CPU limited devices.

未完待续欢迎继续关注兄弟连区块链教程分享!http://t.cn/EZtFYV0