github:https://github.com/xuewuli/Tiny.Scatter

Tiny.Scatter

Scatter javascript warpper for webview

inject to iOS WKWebView

extension WKWebViewConfiguration {
    static func makeScatterEOSSupport(account: String, publicKey: String, in messageHandler: WKScriptMessageHandler, with config: WKWebViewConfiguration) -> Void {
        var js = ""

        if let filepath = Bundle.main.path(forResource: "tiny_scatter", ofType: "js") {
            do {
                js += try String(contentsOfFile: filepath)
            } catch { }
        }

        js +=
        """
        // value as string "SIG_K1_..."
        function onSignEOSMessageSuccessful(id, value) {
            BrigeAPI.sendResponse(id, value)
        }

        // value as string with this format '{"signatures":["SIG_K1_..."]}'
        function onSignEOSSuccessful(id, value) {
            BrigeAPI.sendResponse(id, JSON.parse(value))
        }

        // error as string
        function onSignEOSError(id, error) {
            BrigeAPI.sendError(id, {"type": "signature_rejected", "message": error, "code": 402, "isError": true})
        }

        TinyIdentitys.initEOS("\(account)", "\(publicKey)");

        const scatter = new TinyScatter();
        scatter.loadPlugin(new TinyEOS());

        window.scatter = scatter;

        document.dispatchEvent(new CustomEvent('scatterLoaded'));

        """
        let onLoadScript = WKUserScript(source: "document.dispatchEvent(new CustomEvent('scatterLoaded'))", injectionTime: .atDocumentEnd, forMainFrameOnly: false)
        config.userContentController.addUserScript(onLoadScript)
        let userScript = WKUserScript(source: js, injectionTime: .atDocumentStart, forMainFrameOnly: false)
        config.userContentController.add(messageHandler, name: XMethod.signEOS.rawValue)
        config.userContentController.addUserScript(userScript)
    }
}

Additional Android injection init.js, your need thirdpart lib suchlike https://github.com/TrustWallet/Web3View (or roll you own) to accomplish the injection.

/**
/* use webView.evaluateJavascript to call when your finish the sign
/* @param id as number , you got it when XWebView.signEOS called
/* @param value as string, with this format '{"signatures":["SIG_K1_..."]}'
**/
function onSignEOSSuccessful(id, value) {
    BrigeAPI.sendResponse(id, JSON.parse(value))
}

// value as string "SIG_K1_..."
function onSignEOSMessageSuccessful(id, value) {
    BrigeAPI.sendResponse(id, value)
}

function onSignEOSError(id, error) {
    BrigeAPI.sendError(id, {"type": "signature_rejected", "message": error, "code": 402, "isError": true})
}

const messageHandlers = {
    signEOS: {
        postMessage: function (param) {
            //XWebView is your @JavascriptInterface
            XWebView.signEOS(param.id, param.object.data);
        }
    },
    signEOSMsg: {
        postMessage: function (param) {
            XWebView.signEOSMsg(param.id, param.object.data);
        }
    }
}

window.webkit = { messageHandlers };

TinyIdentitys.initEOS("%1$s", "%2$s");

const scatter = new TinyScatter();
scatter.loadPlugin(new TinyEOS());

window.scatter = scatter;

setTimeout(function() {document.dispatchEvent(new CustomEvent('scatterLoaded'));}, 1000);

挖矿实际就是在暴力猜谜，而要猜多少次，全凭全网共识的一个难度值。只有猜出一个数字能使得区块的哈希符合难度，才算答对谜题。
那么这个猜谜游戏由于越来越多人的加入，势必会更快猜出。所以为了维持一个恒定的游戏时间(两周)，每次游戏难度均会根据上次游戏的用时而重新计算。

游戏越来越难，如何抢在别人前面猜出呢？所以开启了抱团团战模式（矿池）加入游戏，使得解谜速度更快也更难。速度与难度总是此消彼长。 这也是为何在2014，2015年后难度值呈几何级数式增长。当然也因解谜的设备（矿机）更新换代越来越快。

比特币难度值Difficulty

难度值在区块中并不记录，仅仅是为了人类直观感受解题难度而演变出的一个浮点数。公式如下：

此处的 difficulty_1_target 为一个常数，非常大的一个数字。表示矿池挖矿最大难度。目标值越小，区块生成难度越大。

难度值如何存储在区块中的

在区块中存储的是Target，但是将Target经类似于浮点数的一种压缩表示法，字段为bits。例如，如果区块bits记录为0x1b0404cb，那么他表示的十六进制的Target值为：

0x0404cb * 2**(8*(0x1b - 3)) = 0x00000000000404CB000000000000000000000000000000000000000000000000

在计算时，后面3个字节0x0404cb作为底，前面1字节0x1b表示次方数。具体压缩过程如下：

• 将数字转换为256进制数
• 如果第一位数字大于127(0x7f),则前面添加0
• 压缩结果中的第一位存放该256进制数的位数
• 后面三个数存放该256进制数的前三位，如果不足三位，则后面补零

例如，将数字1000压缩，先转换为256进制数

1000 = 0x03 * 256 + 0xe8 * 1

那么是由两个数字构成：

03   e8

第一个数未超过0x7f,则不需填0，但长度两位低于三位，在后面补零，最终表示为：

0x0203e800

有比如数字 2^(256-32)-1,转换为256进制为：

ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff

第一位已经超过0x7f,前面添加零：

00 ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff

现在长度为28+1=29 (0x1d),则最终压缩结果为：0x1d00ffffff。此时就用精度缺失，后面的26个ff 被丢弃了，因为总共才4字节，前两字节已经被长度和添加的0所占用，只剩下2个字节来存储数字。如果我们将压缩结果0x1d00ffffff解压，会是原值吗? 实际结果为：

0x00ffff *256** (0x1d - 3)  = ff ff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

而此数为比特币的最大Target值，此时难度最小为1。将其结果前面添加4位0，其结果为：

0x00000000FFFFFF0000000000000000000000000000000000000000000000000000

此最小难度值1，在矿机上一般使用保留尾部的FF，则为：

0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

称上面数字为pool difficulty1 矿池难度1，矿池难度简称pdiff。而比特币客户端表示如此精度，也许是困难的，所以不保留尾部的FF,则结果为：

0x00000000FFFFFF0000000000000000000000000000000000000000000000000000

此值，在客户端上称之为bdiff。

如何查看当前难度值

当前难度值，可以在许多提供服务的网站上查看图表数据：

• https://bitcoinwisdom.com/bitcoin/difficulty
• https://data.bitcoinity.org/bitcoin/difficulty/5y?t=l
• https://btc.com/stats/diff

最大难度值是多少

按公式来看，当current_target=0时diffculty无穷大，标志着难以计算。而实际上current_target不会为0，最小current_traget=1时，难度值最大，接近2^(256-32)。

最小难度值是多少

当current_target=difficulty_1_target 为最大值时，难度值为最小值1

根据难度值如何计算网络算力network hash rate

网络算力，表示根据难度值，要计算多少次才能找到一个随机数使得区块哈希值低于目标值。
由当前目标值Target决定当前难度值 。如果当前难度为D，则根据公式：

因此，为找到一个难度为D区块，我们需计算哈希值的次数为：

目前难度计算速度要求是在10分钟内找到，即在600秒内完全计算，意味着网络算力最低必须是：

依上计算，当难度值D=1时，需要每秒计算7158278次哈希，即： 7.15 Mhahs/s。挖矿的每秒算力计算单位：

• 1 KHash/s = 1000 Hash/s
• 1 MHash/s = 1000 KHash/s
• 1 GHash/s = 1000 MHash/s
• 1 THash/s = 1000 GHash/s
• 1 PHash/s = 1000 THash/s

比特币区块目标值

目标值是一个全网统一的一个256字节的数字，非常大。 最大目标值为0x1d00ffff。
比特币区块被设计为平均每10分钟生成一个新区块。那如何才能维持区块生成速度呢？ 需要动态调整区块难度，而定期自动更新目标值，则可调整难度。所以比特币设计为每隔2016个区块时全网均会自动统计过去2016个区块生成耗时，重新计算出下一个2016个区块的目标值。

按10分钟一个区块生成速度，2016个区块生成时间为2016*10分钟=14天。

目标值计算细节

目标值计算公式如下，但在实际计算时有些特别处理，将目标值控制在一定范围内。

新目标值= 当前目标值 * 实际2016个区块出块时间 / 理论2016个区块出块时间(2周)。 

• 判断是否需要更新目标值( 2016的整数倍)，如果不是则继续使用最后一个区块的目标值
• 计算前2016个区块出块用时
• 如果用时低于半周，则按半周计算。防止难度增加4倍以上。
• 如果用时高于8周，则按8周计算。防止难度降低到4倍以下。
• 用时乘以当前难度
• 再除以2周
• 如果超过最大难度限制，则按最大难度处理

计算过程，Go代码如下。点击查看bticoin C++源码

var (
    bigOne = big.NewInt(1)
    // 最大难度：00000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffff，2^224，0x1d00ffff
    mainPowLimit = new(big.Int).Sub(new(big.Int).Lsh(bigOne, 224), bigOne)
    powTargetTimespan = time.Hour * 24 * 14 // 两周
)
func CalculateNextWorkTarget(prev2016block, lastBlock Block) *big.Int {
    // 如果新区块(+1)不是2016的整数倍，则不需要更新，仍然是最后一个区块的 bits
    if (lastBlock.Head.Height+1)%2016 != 0 {
        return CompactToBig(lastBlock.Head.Bits)
    }
    // 计算 2016个区块出块时间
    actualTimespan := lastBlock.Head.Timestamp.Sub(prev2016block.Head.Timestamp)
    if actualTimespan < powTargetTimespan/4 {
        actualTimespan = powTargetTimespan / 4
    } else if actualTimespan > powTargetTimespan*4 {
        // 如果超过8周，则按8周计算
        actualTimespan = powTargetTimespan * 4
    }
    lastTarget := CompactToBig(lastBlock.Head.Bits)
    // 计算公式： target = lastTarget * actualTime / expectTime
    newTarget := new(big.Int).Mul(lastTarget, big.NewInt(int64(actualTimespan.Seconds())))
    newTarget.Div(newTarget, big.NewInt(int64(powTargetTimespan.Seconds())))
    //超过最多难度，则重置
    if newTarget.Cmp(mainPowLimit) > 0 {
        newTarget.Set(mainPowLimit)
    }
    return newTarget
}

测试代码如下，计算的是对高度为497951+1出块时计算的新目标值。

func TestGetTarget(t *testing.T) {
    firstTime, _ := time.Parse("2006-01-02 15:04:05", "2017-11-25 03:53:16")
    lastTime, _ := time.Parse("2006-01-02 15:04:05", "2017-12-07 00:22:42")
    prevB := Block{Head: BlockHeader{Height: 497951, Bits: 0x1800d0f6, Timestamp: lastTime}}
    prev2016B := Block{Head: BlockHeader{Height: 495936, Bits: 0x1800d0f6, Timestamp: firstTime}}
    result := CalculateNextWorkTarget(prev2016B, prevB)
    bits := BigToCompact(result)
    if bits != 0x1800b0ed {
        t.Fatalf("expect 0x1800b0ed,unexpected %x", bits)
    }
}

转载自:https://yushuangqi.com/blog/2017/understand-bitcoin-difficulty.html

期待了这么长时间，REX 终于上线了！现在已经出现了很多怎么使用 REX 的教程，但是我们还没有看到有人解释在与 REX 交互的各种操作。所以 EOS Canada 希望深入地解析 REX 代码，给 EOS 社区做一下科普。
首先我们要定义八个术语，保证我们理解它们，它们对 REX 讨论都非常重要。

成熟期

当你购买 REX 代币时，在四天内将无法把它们换回 EOS。在此期间，这些代币被称为在成熟期。在同一天的不同时间购买的 REX 都从第二天0点开始计时，所以你最多可以有四个不同的到期日。

4天

如上所述，到期日的计算均从 UTC 时间的第二天00:00开始。因此，如果用户在今天16:00 UTC 购买 REX 代币，那么他们将只能在4天8小时后卖回 EOS（成熟后）。所以每当人们说“四天”时，它实际上是从购买后的 00:00 UTC 计算的四天。

30天

每次借用的 CPU 或网络带宽的有效期为30天。只有借来这些资源的用户才需要注意这个30天的期限。如果你是借出你的代币资源的用户，你只需要注意四天的成熟期。

储蓄桶

你可以选择把 REX 代币放到储蓄桶里，放到储蓄桶里的代不会自动进入成熟期的，直到你提出要取出里面的代币，它才会开始四天的成熟期，成熟后才能移动它们。这是为了让你能保证你的代币安全的一个选项。举一个具体的用例，如果你的活跃权限的密钥被盗，有你的密钥的人就能动用你已经成熟了的 REX 代币，换回 EOS 然后盗走。但是如果你的 REX 在储蓄桶里，你就有时间用拥有者权限更改你的活跃权限，然后取消储蓄桶里代币的成熟期。

REX 基金

要与 REX 交互，你先要在把 EOS 代币存入你的 REX 基金中 ，REX 基金中存的是 EOS 而不是 REX 代币。

投票前提

想用 REX 出租自己资源，有一个前提，他们必须至少投票给21个BP节点或者代理投票。

流动性紧缩

这种情况出现的几率很小，但是我们还是应该有所了解。如果在池中没有足够的EOS 代币来满足提款的数量，这种现象就叫“流动性紧缩”。这意味着所有提款订单会被排队，等有新的 EOS 代币进入 REX 池之后，或者有借用的资源到期。用户赎回 EOS 是没有风险的，他们可能最多需要等待30天，但再强调，这个现象是非常罕见的。

市场价

REX 由 Bancor 支持的，就是说价格不是由用户自己竞价决定的，而是由系统根据池中 EOS 和 REX 代币的比率去计算的。这就是为什么收益率或续约价格是不确定的，因为一切都是在购买时确定的，取决于买卖时间和当时的状况。

我们还想强调一下两件值得注意的事情。EOS:REX 比值的确定方式决定了你卖出REX收回EOS数量不是高于就是等于你投入的EOS数量。这意味着你永远不会因为持有 REX 而失去任何 EOS，你只会获益。

另一点是，在获取帐户快照时，空投可以选择是否考虑你的 REX 余额。就是说你在 REX 中的代币会不会被包含在内取决于该空投的开发者。
我们现在来看一下在与 REX 交互时可调用的所有操作，并作出相关解释。

转载自:https://mp.weixin.qq.com/s/zOmJA4R8JOHEedmHqhaoBw (by EOS Canada)

今天看到BOS更新了PBFT 3s进LIB的release 3.0版本，编译试试，遇到以下问题

CMake Error at plugins/kafka_plugin/CMakeLists.txt:2 (add_library):
Target "kafka_plugin" links to target "RdKafka::rdkafka" but the target was
not found. Perhaps a find_package() call is missing for an IMPORTED
target, or an ALIAS target is missing?

CMake Error at programs/nodeos/CMakeLists.txt:1 (add_executable):
Target "nodeos" links to target "RdKafka::rdkafka" but the target was not
found. Perhaps a find_package() call is missing for an IMPORTED target, or
an ALIAS target is missing?

解决方案

删除/usr/local/include/cppkafka , /usr/local/include/librdkafka两个目录
重新开始bos编译（会自动下载安装适配的kafka版本）

参考

https://github.com/boscore/bos/issues/37
https://github.com/boscore/bos/tree/master/plugins/kafka_plugin

基于PBFT提升EOS共识速度的算法

1 背景介绍

1.1 现象

当前主网的链高度和共识高度之间有325+个块的差距，相当于~3分钟左右的时间差。也就是说，当下提交的trx需要等到~3分钟后才能确认是否被记在链上。这样的表现对于很多DApp来说是不可承受的，尤其是那些需要即时确认的应用。

1.2 原因阐述

• 造成主网上这种现象的原因，是EOS基于DPOS的共识算法中，所有块同步和确认信息都只通过出块的时候才能发出。也就是说，在BP₁出块（所出块为BLK）、BP₁～BP₂₁轮流出块的情况下，BP₂～BP₂₁会陆续收到并验证BLK，但所有BP只能等到自己出块的时候才能发出对BLK的确认信息。这也是为什么我们看到nodes的log中，每个BP在schedule中第一次出块的时候，confirmed总是240。DPOS+Pipeline BFT理论上共识的最快速度（即head和LIB之间的最小差距）为325。

• 240 = (21-1)*12
  这其实是（在网络情况良好的情况下）上一轮所有块数之和。每个节点在block_header中维护着一个长度最长为240，初始值为14的vector confirm_count，对应所有收到但是未达成共识的块以及尚需的确认数。每当收到多一个BP对这些块的确认，对应块的数值-1，直到某一块所需的确认数减到0，此块及之前的所有块便进入共识（相关代码）。

• 325 = 12*(13+1+13) + 1
  整个网络需要15个人确认才能达成共识。每个人默认会对自己出的块进行确认，所以每个块需要14个人的implicit confirm和（explicit）confirm。第14个BP在出块时由于包括自己在内确认人数已经达到15人，所以它会同时发出implicit confirm和（explicit）confirm。那么理想情况下，一个块从它产生后，要到之后的第28个BP所产出的第一个块时才能得到全网共识，进入LIB。因此有以上计算。

• 我们认为，所有BP不需要等到出块的时候才对其他块进行确认，用PBFT（Practical Byzantine Fault Tolerance^[1]）来替代Pipeline BFT，让BP之间实时地对当前正在生产的区块进行确认，能够使整个系统最终达到接近实时的共识速度。

2 算法核心

• 保留DPOS的BP Schedule机制,和EOS一样对synchronized clock和BP Schedule进行强约束。

• 去掉EOS中的Pipeline BFT部分共识（即去掉原本EOS中出块时的implicit confirm和(explict) confirm部分），因为在极端情况下可能与PBFT的共识结果有冲突。

• 共识的通讯机制使用现有p2p网络进行通信,但增加通信成本,使用PBFT机制广播prepare和commit信息。

• 通过batch方式优化(替换掉PBFT中对每个块进行共识的要求), 能够达成批量共识，以此来逼近实时BFT的理想状态并减轻网络负载。

3 基础概念

3.1 DPOS中BP变更的具体实现

• 当前代码中，每60s（120个块）刷新一次投票排名（相关代码），如果前21名发生变化，会在下一次刷新排名的时候发出promoting proposed schedule（相关代码）

• 当包含promoting proposed schedule的块进入LIB后，BP会陆续更新自己block header中的pending_schedule

• 等到2/3 +1个BP节点都已经更新block header后，pending schedule达成共识。BP会陆续将active schedule更新为此时pending schedule的值，并按照新的BP组合开始出块，整个过程需要至少经过两轮完整的出块。

• 每一次新的BP组合，一定要能够达成共识才能真正生效。换句话说，如果网络中7个或更多节点无法正常通信，那么无论如何不能通过投票的方式产生新的BP。网络的LIB会一直停留在节点崩溃的那个共识点。

• DPOS这样的做法可以有效的避免一部分分叉问题，所以仍会沿用DPOS关于BP选举部分的共识机制，即所有的BP变动，需要等到propose schedule进入LIB后才真实生效。

3.2 PBFT的前提

• 如果网络中的拜占庭节点为f个，那么要求总节点数n满足n≥3f+1。拜占庭节点是指对外状态表现不一致的节点，包括主动作恶的节点和因为网络原因导致失效或部分失效的节点。

• 所有信息最终可达: 所有通信信息可能会被延迟/乱序/丢弃, 但通过重试的方式可以保证信息最终会被送达。

3.3 PBFT中的关键概念对应DPOS

pre-prepare，指primary节点收到请求，广播给网络里的所有replica。可以类比为DPOS中BP出块并广播至全网。

prepare，指replica收到请求后向全网广播将要对此请求进行执行。可类比为DPOS重所有节点收到块并验证成功后广播已收到的信息。

commit，指replica收到足够多的对同一请求的prepare消息，向全网广播执行此请求。可以类比为DPOS中节点收到足够多对同一个块的prepare消息, 提出proposed lib消息

committed-local, 指replica收到足够多对同一请求的commit消息, 完成了验证工作. 可以类比为DPOS中的LIB提升.

view change，指primary节点因为各种原因失去replica信任，整个系统更改primary的过程。由于EOS采用了DPOS的算法，所有BP是通过投票的方式提前确定的，在同一个BP schedule下整个系统的出块顺序是完全不变的，当网络情况良好并且BP schedule不变的时候可以认为不存在view change。
当引入PBFT后，为了避免分叉导致共识不前进的情况，加入view change机制，抛弃所有未达成共识的块进行replay，不断重试直到继续共识。

checkpoint, 指在某一个块高度记录共识证据, 以此来提供安全性证明. 当足够多的replica的checkpoint相同时, 这个checkpoint被认为是stable的. checkpoint的生成包括两大类,一类是固定k个块生成; 另一类是特殊的需要提供安全性证明的点,例如BP schedule发生变更的块.

4 未优化版本概述

术语:

• v: view version
• i: BP的名字
• BLK_n: 第n个块
• d_n: 对应第n个块的共识消息摘要digest
• σ_i: 名为i的BP的签名
• n: 区块的高度

所有BP针对每一个块按顺序进行共识, 采用PBFT机制. 以下分情况进行描述:

4.1 在正常的情况下（不涉及BP变更也没有分叉，且网络状况良好）

pre-prepare阶段，与现行逻辑没有区别，即BP广播其签名的块。

prepare阶段，BP_i收到当前BP签名的块BLK_n，经过验证后发出 (PREPARE,v,n,d_n,i)_σi 消息，等待共识。当BP_i收到了2/3的节点发出view v下对BLK_n的PREPARE消息，认为网络中对此块的prepare已达成共识。已发出的PREPARE消息，不可更改。

commit阶段，当BLK_n标记为 prepared 后，BP_i发出(COMMIT,v,n,d_n,i)_σi。需要注意的是，PBFT是通过保证严格顺序来实现安全性的，所以对所有节点对块的共识也是严格的按照顺序进行，也就是说，(PREPARE,v,n,d_n,i)_σi发出的前提条件是在同一个view下，BLK_n-1至少已经处于 committed 状态。

全网角度下LIB提升，当BP_i收到了2/3的节点发出v下对BLK_n的COMMIT消息，BP_i认为网络中对此块的commit已达成共识，即此块已达成共识，此块标记为 committed 状态，并将LIB提升到当前高度n，然后开始对下一个块进行prepare。若此区块高度为H_i，所有BP的LIB高度进行降序排列后得到长度为L的向量V_c, 从全网角度来看V_c[2/3L]及以下的LIB可以被认为 stable ，V_c[2/3L]即此时全网的LIB高度。

对于同一个块而言，只有收集足够的PREPARE消息，才会进入commit阶段。同理，只有收集足够的COMMIT消息，才会开始对下一个块开始prepare，否则就一直重发直到消息数满足要求或进行view change（见后文）。

4.2 当BP产生变化的时候

pre-prepare阶段，与4.1无区别。

prepare和commit阶段，由于不同BP间对于BP变动的信息达成共识的时间有先后，此时便会出现BP之间对于schedule的不一致状态。
以BP_i为例，BP_i收到了当前BP_c签名的块BLK_n，如果此时多数BP的active schedule已改为S'，而BP_i仍是S，那么BP_i便会持续等待S中的BP发送的PREPARE信息，从而无法进入commit阶段。
但此时网络中的多数节点仍会相互达成共识，致使全网的LIB提升。如果BP_i收到足够的同一个view下的commit信息, BP_i会进入commit-local状态,提升自己的LIB。

4.3 当产生分叉的时候

pre-prepare阶段，与4.1无区别。

prepare和commit阶段，当BP_i 在timeout=T内没有收集足够的PREPARE或COMMIT消息，即共识没有在这个时间段内提升，此时发出VIEW-CHANGE消息，发起view change 并不再接收除VIEW-CHANGE、NEW-VIEW和CHECKPOINT外的任何消息。

view change阶段，BP_i 发出 (VIEW-CHANGE,v+1,h_lib,n,i)_σi消息。当收集到 2/3 +1 个v'=v+1的VIEW-CHANGE消息后，由schedule中的下一个BP发出 (NEW-VIEW,v+1,n,VC,O)_σbp消息，其中VC是所有包括BP签名的VIEW-CHANGE消息，O是所有未达成共识的PRE-PREPARE消息（介于h_lib和n_max之间）。当其它BP收到并验证NEW-VIEW消息合法后，丢弃掉所有当前未达成共识的块，基于所有的PRE-PREPARE消息重新进行prepare和commit阶段。
若view change未能在timeout=T内达成共识（没有正确的NEW-VIEW消息发出），即发起新一轮v+2的view change，等待时间timeout=2T, 依次类推不断重试，直到网络状态收敛，共识开始提升。

备注: 原始的PBFT不存在分叉的问题, 因为PBFT只有在一个请求达成共识后才会开始处理下一个请求。

5 未优化版本存在的问题:

5.1 共识速度

当对一个块的共识速度小于500ms，即两轮消息的发送可以在500ms内收到足够的确认数，head和LIB的差距稳定后可以趋近于1个块，即实时共识。而当对一个块的平均共识速度大于等于500ms或网络状态极差导致重试次数过多，本算法表现可能慢于DPOS+Pipeline BFT。

5.2 网络开销

假设网络中的节点为N，消息传播使用gossip算法，块大小为B，那么DPOS需要传播的消息为N²，所需带宽为BN²。
假设PREPARE和COMMIT消息大小分别为p和c，PBFT+DPOS所需要传播的消息数为 (1+r_p+r_c)N²，其中1 是pre-prepare的传输,r_m，r_c为prepare和commit的重试次数，所需带宽为(B+pr_p+cr_c)N²。当p、c优化的足够小后，额外的带宽开销主要取决于重试次数。

6 优化后的版本概述

6.1 通过自适应粒度调整,实现批量共识

6.1.1 batch 策略

LIB的高度为h_LIB
fork中最高点的块的高度为 h_HEAD
涉及到BP schedule变动的块高度为 h_s
批量共识batch:

• batch_min = 1
• batch_max = min(default_batch_max, h_HEAD - h_LIB)

当batch_max中不包含BP Schedule变动时, batch = batch_max
当batch_max中包含BP Schedule变动且h_LIB < h_s 时, batch = h_s - 1
当batch_max中包含BP Schedule变动且h_LIB == h_s 时, batch = batch_max

6.1.2 批量共识原理

当未出现分叉情况时, 以上构筑可类比PBFT中view不变情况下的共识. 并且基于Merkle Tree的基本结构，当多数节点可以对BLKn的Hash达成共识，那么之前的所有块都应该是共识的. 此处保证了块的total order.

当出现分叉情况时, PREPARE 信息不能变动，否则可能对外表现为拜占庭错误。此时需要不断重发当前的PREPARE消息直到网络达成共识或触发timeout 后发起view change。

6.1.3 实现方法

• 每当收到新的块时, BP 通过batch的策略生成PREPARE信息, 进行缓存及广播

• 每个BP为block_header维护一个最低水位h，和最高水位H，分别对应自己还没有达成共识的最低点和最高点。

• 同时维护两个长度为（H-h）的向量 V_p & V_c，包括水位间每一个块所需要的PREPARE消息数和COMMIT消息数。

• 每收到一个高度为n的PREPARE消息（或COMMIT消息），通过消息的签名和digest进行验证并确认他与自己处于相同的fork后，依次将V_p（V_c）中（h ≤ n）的所有数值-1。

• 不断重发同一个fork上高度为H的PREPARE消息（或COMMIT消息），直到达成共识或超时后触发View Change（基于New View重新开始PBFT共识，此时v' = v+1）。

• 当某一个处于高度x（h ≤ x ≤ H）的块收集超过2/3 +1个PREPARE消息，依次执行从h～x的块内容并标记所有（h ≤ x）的块为 prepared，然后自动发出高度为x的COMMIT消息。

• 当某一个处于高度y（y ≤ H）的块收集超过2/3 +1个COMMIT消息，依次执行从h～y的块内容并标记所有（h ≤ y）的块为 committed。此时认为≤y的所有块已达成共识，将自己的LIB高度提升至y。

• 每隔若干块生成checkpoint以提高性能。当网络内超过2/3 +1的最新的checkpoint 都达到某一高度c，并且处于同一fork上，则认为此checkpoint稳定。

6.1.4 view change策略

• BP依据出块的schedule依次成为前一人的backup，确保每一次view change后的primary只可能有一人。

• 当网络开始进入view change后，NEW-VIEW应该重新对2/3 +1人看到的最低点h和最高点H之间的块进行重新共识。

• 发出NEW-VIEW的BP应该在消息内包括所有VIEW-CHANGE消息，并根据所有的VIEW-CHANGE消息计算出h和H，并将[h, H]区间内超过（2/3 +1）的人选择的fork一并发出。

• 当BP收到NEW-VIEW消息并进行验证后，基于NEW-VIEW的内容重新进行prepare。

• 若在timeout=T内无法完成view change，便开始发起v+2的新一轮view change，直到网络对fork的选择达成共识。

6.2 通过始终prepare最长链并结合view change，避免分叉风险

• 当BP收到多个fork的时候，应该对当前所能看到的最长链进行prepare, 采取longest-live-fork原则.

• BP在进行prepare的时候，应该错开BP切换的时间点，从而避免选择少数人支持的fork。

• BP一旦对某个fork进行prepare，就不能再对prepare消息进行更改，否则可能成为拜占庭错误， BP需要：
  1）不断重发之前的PREPARE消息，等待最终达成共识。即使这个fork不是最长链, 因为有更多人支持，也应该选择这个fork；
  2）或等待timeout=T后，发起view change，所有BP基于NEW-VIEW发出的fork开始新的BPFT共识；
  3）收到超过（2/3 +1）同一fork的COMMIT消息或checkpoint，抛弃当前状态同步至多数人达成共识的高度。

6.3 通过Checkpoint机制实现GC并提升同步性能

• BP不断网络内广播自己当前的checkpoint状态，并且接收来自其他人的checkpoint。

• 当同一分支上有超过（2/3 +1）人的checkpoint已经高于c，认为CHECKPOINT_c已经stable，删除高度低于c以前所有PREPARE、COMMIT消息等cache。

• 通过验证checkpoint的正确性，可以大幅提升节点的同步速度。

7 FAQ

DPOS相关问题（见1.2）

1. 简单说明DPOS是如何工作的
   暂略
2. 为什么DPOS的lib是12个12个的涨
   暂略
3. 为什么DPOS的HEAD和LIB差距这么大
   暂略
4. 当BP变动时, DPOS是如何工作的
   暂略
5. 目前节点间的数据是如何同步的
   暂略

PBFT相关问题

1. 简单说明PBFT
   暂略

DPOS-PBFT相关问题

1. 简单说明DPOS-PBFT是如何工作的
   见5

2. 为什么不能只广播一次prepare的信息
   当网络出现分叉（或BP变动）的时候，如果只有PREPARE信息，所有节点是无法对其它节点的view change进行响应的，会导致硬分叉。 举例说明: 因为分布式网络的特性, 信息会被延迟或打乱。假设现在有三个连续出块的BP A,B,C 如果B没有收到A的最后一个块, 那么他会继续从倒数第二个块开始出块。这样造成了两个fork选择F1 F2. 假定A的最后一个块里包含了BP变动的信息(该块在F1里), 那么选择了F1的节点需要一个新的BP S1来进行共识, 而F2的节点需要原有的BP S2 进行共识。 共识的群体发生了变化, 很有可能会两边最终都进入共识状态, 进而导致整体网络发生分叉。

3. prepare和commit重发机制是如何工作的
   当超过给定的timeout T后仍然没有对某一个处于 prepared 或者 committed 的块收集到足够多的确认，就对同一个消息进行多一次的重发，直到收集到足够多的确认或发生view change。

4. 当BP集合变动的时候,是否存在分叉风险
   见4.2

5. 是否需要等待共识完成才能继续出块
   出块可以持续进行，共识只影响LIB的高度

6. 如果第N个块未满足BFT共识个数,但第N+1个块收到了足够多的confirm,该如何处理
   对于优化后的算法，可以直接开始基于N+2个块开始收集共识消息

7. 持续出块是否会因为共识未迅速达成而分叉
   不会，至少表现为DPOS的状态，最终会共识在最长链上

8. BFT的commit信息是否需要写入块中
   所有消息（发出的和收到的）都只存在本地. 但需要保留一段时间, 用以为peer提供共识的证据

9. 额外增加的开销有多少
   见5.2

10. 共识的速度真的能提升吗,如果BFT共识平均时间>500ms,BFT的高度是低于DPOS的
    见5.1

8 参考

[1] http://pmg.csail.mit.edu/papers/osdi99.pdf

转载自：https://github.com/eosiosg/dpos-pbft/blob/master/documentation/%E5%9F%BA%E4%BA%8EPBFT%E6%8F%90%E5%8D%87EOS%E5%85%B1%E8%AF%86%E9%80%9F%E5%BA%A6%E7%9A%84%E7%AE%97%E6%B3%95.md