发表于 | 分类于

术语： ACS：异步公共子集协议（Asynchronous Common Subset）

ABA：异步二进制协议（Asynchronous Binary Agreement protocol）

RBC：可靠广播协议(Reliable Broadcast Protocol）

MVBA: 多值验证拜占庭协议(multi-value validated Byzantine agreement)

摘要。HoneyBadgerBFT是Miller等人[35]提出的第一个实用的异步原子广播协议，它展示了令人印象深刻的性能。 HoneyBadgerBFT (HB-BFT)的核心是利用Ben-Or等人的异步公共子集协议(ACS)实现批处理共识，由n个可靠广播协议(RBC)组成，每个节点提出自己的输入，然后n个异步二进制协议(ABA)对每个建议值(n为节点总数)做出决策。

本文提出了两种新的原子广播协议(Dumbo1, Dumbo2)，它们都具有渐近的和实际的更好的效率。特别是，Dumbo1的ACS只运行很小的$\kappa$个ABA实例(独立于n个实例)，而Dumbo2的ACS进一步将其降低为常数!我们的技术的核心是两个主要的观察结果:(1)减少ABA实例的数量显著提高效率;(2)更谨慎地使用多值验证拜占庭协议(multi-value validated Byzantine agreement, MVBA)，该协议被认为是[35]中ACS的次优方案，实际上可以导致更有效的ACS。

我们实现了Dumbo1和Dumbo2，并在100 Amazon EC2 t2上部署了它们和HB-BFT。介质实例均匀分布在全球10个不同的地区，并在相同的环境中进行广泛的实验。实验结果表明，我们的协议在延迟和吞吐量上都比HoneyBadgerBFT提高了好几倍，特别是当系统规模变大时。

阅读全文 »

发表于 | 分类于

简介

RLP(Recursive Length Prefix，递归的长度前缀)是一种编码规则，可用于编码任意嵌套的二进制数组数据。RLP编码的结果也是二进制序列。RLP主要用来序列化/反序列化数据。

RLP是以太坊中Trie树对对象进行序列化的主要编码方式。RLP的唯一目标就是解决结构体的编码问题；

定义

RLP编码的定义只处理以下两类数据：

  1. 字符串（string）是指字节数组。例如，空串”“，再如单词”cat”，以及句子”Lorem ipsum dolor sit amet, consectetur adipisicing elit”等。
  2. 列表（list）是一个可嵌套结构，里面可包含字符串和列表。例如，空列表[]，再如一个包含两个字符串的列表[“cat”,”dog”]，在比如嵌套列表的复杂列表[“cat”, [“puppy”, “cow”], “horse”, [[]], “pig”, [””], “sheep”]。

编码规则

0x00 ~ 0x7F: 0000 0000 ~ 0111 1111 - 127 Asicc本值

0x80 ~ 0xB7: 1000 0000 ~ 1011 0111 - 55 长度在内，如0x81，表示0x81后面一个字节是值

0xB8 ~ 0xBF: 1011 1000 ~ 1011 1111 - 8 表示长度的字节长度在内， 如0xB9,表示0xB9后面一个字节的值是字符串长度值

0xC0 ~ 0xF7: 1100 0000 ~ 1111 0111 - 55 列表， 同2

0xF8 ~ 0xFF: 1111 1000 ~ 1111 1111 - 8 列表，同3

阅读全文 »

发表于 | 分类于

摘要。 本报告介绍了LibraBFT，这是一个针对Libra Blockchain设计的强大而高效的状态机复制系统。 LibraBFT基于HotStuff，这是最近的一项协议，利用拜占庭容错（BFT）数十年的科学进步，实现了互联网设置所需的强大的可扩展性和安全性。 LibraBFT进一步完善了HotStuff协议，引入了明确的活跃度机制，并提供了具体的延迟分析。 为了推动与Libra Blockchain的集成，本文档提供了从全功能模拟器中提取的规范。 这些规范包括状态复制接口和用于参与者之间的数据传输和状态同步的通信框架。 最后，本报告提供了一个正式的安全证明，它引出了检测BFT节点不良行为的标准，同时还有一个简单的奖励和惩罚机制。

1 介绍

互联网和移动宽带的出现使全球数十亿人接触，提供知识，免费通信和各种低成本，更便捷的服务。 这种连接还使更多人能够访问金融生态系统。 然而，尽管取得了这些进展，但对于那些最需要金融服务的人来说，获得金融服务仍然有限。

区块链和加密货币表明，计算机科学，密码学和经济学的最新进展有可能在金融基础设施方面创造创新，但现有系统尚未达到主流应用。 作为实现这一目标的下一步，我们设计了Libra Blockchain [1]，[2]，目的是建立一个简单的全球货币和金融基础设施，为数十亿人提供支持。

这个新区块链的核心是一个名为LibraBFT的共识协议 - 本报告的重点 - 通过该协议对区块链交易进行排序和最终确定。 LibraBFT在参与共识协议的一组验证器中分散信任。 LibraBFT保证就诚实验证者之间的交易历史达成共识，即使参与者的门槛是拜占庭（即有缺陷或腐败[3]），它仍然是安全的。 通过采用经典的拜占庭容错方法，LibraBFT建立在分布式计算中坚实且经过严格验证的基础之上。 此外，科学界已经在LibraBFT的基础上取得了稳步进展，在扩展共识技术方面，并使其在互联网环境中保持稳健。

最初，参与的验证者将被允许进入共识网络，该协会由地理上分布的和不同的创始成员组成，这些成员是根据客观成员标准选择的组织，具有引导Libra生态系统的既得利益[2]。 随着时间的推移，会员资格将变为开放，仅基于组织持有Libra[4]。

LibraBFT的共识基于一种名为HotStuff的前沿技术[5]，[6]，它在BFT共识和区块链的世界之间架起了桥梁。 这种选择反映了丰富的专业知识和各种替代方案的探索，并为LibraBFT提供了以下关键属性，这些属性对于分散信任至关重要：

阅读全文 »

发表于

Basic PaLa

定义：

  • 时间：1sec≥5Δ 1min≥6sec

  • 区块：（e,TXs, h_1）

    e：时代数，严格增加，可跳跃；

    Txs：未完成的交易；

    h_1：前一区块hash

  • 区块链的有效性

    • 对每个1<=i<=∣c∣ ， c[i].h_1 = H(c[: i - 1])

    • 对任何1<=i<j<=∣c∣，它必须是c [i] .e <c [j] .e

    • c [i] .e = c [i-1] .e + 1，则c [i]被认为是正常块; 否则它被称为超时块

  • 公证： 2n/3节点签名验证

  • 提案人：假设节点i∈[n]是时代e的一个合格的提议者，当且仅当i=(H(e)modn)+1，H表示一个计算函数

协议

  • 内部时钟同步：每个节点维护本地时代e,初始为1. 按如下方式推进：

    • 节点已进入本地时代e超过1min, 则签名广播（e+1）,表示想要进入到e+1(但实际不推进到e+1)

    • 看到e-1块的公证，或是收到2n/3个不同节点的时钟签名消息（e）,将本地时代推进到e

  • 提案：当节点处于本地时期e,根据以下情况提议块B

    • 看到（e-1）的公证链

    • 否则，在进入e后1sec，选择最新的公证链c,提出块B:=(e,Txs,H(c))

  • 投票：节点处于e时代，对收到的第一个有效提案（e,Txs,h_1）(可能早已e)，如果满足如下条件，则投票

    • 节点对每个时代的区块只能投一票

    • 节点已收到链c的公证，且H(c)=h_1

    • 链c是节点进入本地时期e后看到的最新公证链

存在的问题

双流水线PaLa的委员会重组

定义：

  • 委员会重组：

  • 时钟同步：

阅读全文 »

发表于 | 分类于

1 绪言

我们描述了PaLa，一种概念上简单的，部分同步的区块链协议，可以容忍少于1/3的作恶。 在PaLa，提议者提出了一个块，扩展了迄今为止看到的最新鲜的公证链。 如果满足某些条件，共识节点（即委员会成员）就该提案进行投票。 当一个区块获得至少2n/3票时，它就会变成公证。 有效区块链中有两种类型的块，正常块和超时块，并且每种类型都有一组不同的有效性约束。 在任何时间点，公证链中的每个块直到最后一个正常块（不包括）都被认为是最终确定的。

PaLa的设计精简。 消息提议和投票只有两种类型。 在良好的条件下，每个区块只需要进行一轮投票即可确认 - 但是为了最终确定，必须等待下一个正常区块获得公证。

总的来说，关于提议者选举存在两种学说：democracy-favoring(偏向民主)的方法（例如，Dfinity [11]，Algorand [8]）为每个确认的区块切换提议者; 和tability-favoring(偏向稳定)方法（例如，PBFT [7]和Thunderella [14]）。 我们的范例允许使用任一策略。

我们还描述了一种简单的方法，用于在不等待任何同步事件的情况下更改委员会，同时保持协议的简化执行。

1.1 Pipelined-BFT范式的背景

经典型BFT协议使用两轮或多轮投票来确认每个块，例如在PBFT中，它们分别被称为“prepare”轮和“commit”轮。最近，加密货币社区出现了一个优雅的流水线理念，即，如果每个块需要两轮投票，为什么不在第二轮投票中捎带？这个想法在Buterin和Griffith [15]的优雅Casper-FFG作品中被隐含地描述，其形式为终极小工具“用于工作证明区块链。论坛和在线博客帖子[2,3]表明DPoS （即，EOS采用的共识协议，按市值排名前5的加密货币[1]）可能正在考虑采用类似的方法，尽管在撰写本文时尚未发布对DPoS协议和证据的正式描述。 Casper-FFG [15]和DPoS [2,3]的这种想法的实例都只实现了同步性能，即，即使网络能够更快地传送数据包，这些协议也只能以较慢的间隔确认块。 DPoS仅以固定间隔提出块[2,3]，而在Casper [15]中，块提议是进程是潜在的PoW区块链，因此块提议仅偶尔以随机间隔发生。

Abraham等人最近的优雅作品HotStuff。 [4]扩展了这种“流水线”方法，以提供可证明安全的BFT协议，容忍部分同步网络中的2/3损坏。在高层次上，PaLa依赖于与HotStuff非常相似的直觉（但我们给出了一些 - 在实现中可能有价值的更简单的想法表示）。在HotStuff中，活跃依赖于拥有一个旋转的提议者（即“支持民主的方法”），而在PaLa中，我们还展示了如何使用适合性能要求的场景的稳定性偏好的提议者轮换策略来实例化PaLa（参见章节 9关于具体的，现实世界的应用场景的更多讨论）。此外，我们提出了一种双流水线变体，它是对性能要求严格的场景所必需的流水线-BFT范例的进一步概括。此外，如上所述，我们提出了一种简单的方法来启用委员会切换（我们考虑的应用程序也需要这种方法）。

1.2 协议概述

我们在此提供PaLa共识协议的描述，重点是“随机”提议者选举政策和固定委员会。设$\Delta$是同步期间网络延迟的约束。由于我们处于部分同步模型中，协议只需要在同步期间取得进展，但一致性/安全性应始终保持在任意网络分区之下。为了简化表示法，我们将使用别名秒为$ c\Delta $，别名分钟表示为$ c^2\Delta $（即c秒）表示某些适当的常量c（在实际协议中c = 6）

每个节点保持一个从0开始的本地时期计数器e和当前的一个块链（b1, b2,…,bn）;每个块具有形式（e,TXs,h_1），使得时期数e严格增加，并且h_1是当前块之前的链的散列。我们说如果$ \pi $包含来自链中每个块的 >= 2/3的有效签名，则$ \pi $是链的公证。链的纪元号被定义为最后一个块的纪元号。该协议如下：

阅读全文 »

发表于 | 分类于

GPG

Gpg生成公私钥，密钥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
$ gpg --gen-key
gpg (GnuPG) 1.4.22; Copyright (C) 2015 Free Software Foundation, Inc.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Please select what kind of key you want:
   (1) RSA and RSA (default)
   (2) DSA and Elgamal
   (3) DSA (sign only)
   (4) RSA (sign only)
Your selection?
RSA keys may be between 1024 and 4096 bits long.
What keysize do you want? (2048)
Requested keysize is 2048 bits
Please specify how long the key should be valid.
         0 = key does not expire
      <n>  = key expires in n days
      <n>w = key expires in n weeks
      <n>m = key expires in n months
      <n>y = key expires in n years
Key is valid for? (0)
Key does not expire at all
Is this correct? (y/N) Y

You need a user ID to identify your key; the software constructs the user ID
from the Real Name, Comment and Email Address in this form:
    "Heinrich Heine (Der Dichter) <heinrichh@duesseldorf.de>"

Real name: lichengcai(suimi)<isuimi@aliyun.com>
Invalid character in name
Real name: lichengcai
Email address: isuimi@aliyun.com
Comment: suimi
You selected this USER-ID:
    "lichengcai (suimi) <isuimi@aliyun.com>"

Change (N)ame, (C)omment, (E)mail or (O)kay/(Q)uit? 0
Change (N)ame, (C)omment, (E)mail or (O)kay/(Q)uit? o
You need a Passphrase to protect your secret key.

We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.
....+++++
...+++++
We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.
.....+++++
.......+++++
gpg: /c/Users/suimi/.gnupg/trustdb.gpg: trustdb created
gpg: key 1AFEE421 marked as ultimately trusted
public and secret key created and signed.

gpg: checking the trustdb
gpg: 3 marginal(s) needed, 1 complete(s) needed, PGP trust model
gpg: depth: 0  valid:   1  signed:   0  trust: 0-, 0q, 0n, 0m, 0f, 1u
pub   2048R/1AFEE421 2019-04-16
      Key fingerprint = 3CE9 7E3C E01E E78E AFD8  0A32 0CF0 9882 1AFE E421
uid                  lichengcai (suimi) <isuimi@aliyun.com>
sub   2048R/F82E2AB5 2019-04-16
阅读全文 »

发表于 | 分类于

逻辑命题

  • =>：蕴含，implication，当且只有 F 等于 FALSE 或者 G 等于 TRUE（或者 F 和 G 都为 TRUE 或者 FALSE），F => G 等于 TRUE

    这里我们可能对 => 的定义感到困惑，为什么只有 F 为 TRUE 并且 G 为 FALSE 的时候 F => G 才为 FALSE，我们可以通过 (n > 5) => (n > 3) 来说明，对于整数 n 来说，如果 n 为 6，n > 5 就是 TRUE，自然 n > 3 也是 TRUE，也就是 (n > 5) 蕴含着 (n > 3)，我们可以将 n 设置为 1，4 这些值在自行推导。

  • :>：d:>e 等价于x \in d |->e,e为集合。相当于集合映射

  • |->: 类似与map映射关系。

    [x \in S |-> e]构造任意值域的函数. 譬如[ i \in 1..3 |-> i - 7]，这个就会得到<<-6, -5, -4>>，然后我们可以使用<<-6, -5, -4>>[1] 得到 -6 了

  • @@：合并，联合。 f@@g等价于[x \in (DOMAIN f) U (DOMIN g) |-> IF x \in DOMIN f THEN f[x] ELSE g[fx]]
阅读全文 »