【论文翻译】HotStuff:BFT Consensus in the Lens of Blockchain – Model

这是《HotStuff:BFT Consensus in the Lens of Blockchain》论文翻译的第三篇,包含了论文的模型部分。


3. 模型

我们考虑一个由n=3f+1个副本组成的系统,由i \in [n]索引,其中[n] = {1,2,\dots,n}。一个集合拥有至少f = |F|的集合F \contains [n]是拜占庭正确的,反之则是错误的。我们通常将拜占庭副本定义为由竞争对手操控的副本,它们拥有这些副本所持有的所有内部状态(包括它们的加密密钥,见下文)。

We consider a system consisting of a fixed set of n = 3f + 1 replicas, indexed by i ∈ [n] where [n] = {1, . . . , n}. A set F ⊂ [n] of up to f = |F| replicas are Byzantine faulty, and the remaining ones are correct. We will often refer to the Byzantine replicas as being coordinated by an adversary, which learns all internal state held by these replicas (including their cryptographic keys, see below).

网络通信是点对点的,经过验证且可靠的:一个正常的副本可以从另一个正常副本接受消息当且仅当后者确实曾经发送过消息。当我们说“广播”时,也往往指的是发送相同的点对点消息给包括自身在内的所有副本。我们采用了Dwork等人的部分同步模型,模型存在一个已知的界限\Delta和一个未知的全局稳定时间GST。在GST时限过后,副本间的所有通信都顺利到达。我们的模型可以保持持续的安全性,并且保证可以在GST之后有限的时间内获得进展(前人已经证明GST之前取得任何进展是不可能的)。在实际操作中,如果系统在GST后保持足够长时间的稳定,我们的模型一定会取得进展。这里,对于稳定性的要求是用来简化讨论的。

Network communication is point-to-point, authenticated and reliable: one correct replica receives a message from another correct replica if and only if the latter sent that message to the former. When we refer to a “broadcast”, it involves the broadcaster, if correct, sending the same point-to-point messages to all replicas, including itself. We adopt the partial synchrony model of Dwork et al. [25], where there is a known bound ∆ and an unknown Global Stabilization Time (GST), such that after GST, all transmissions between two correct replicas arrive within time ∆. Our protocol will ensure safety always, and will guarantee progress within a bounded duration after GST. (Guaranteeing progress before GST is impossible [27].) In practice, our protocol will guarantee progress if the system remains stable (i.e., if messages arrive within ∆ time) for sufficiently long after GST, though assuming that it does so forever simplifies discussion.

加密原语 HotStuff使用阈值签名加密。在一个(k-n)阈值签名的场景下,所有节点都持有一个公钥,而这n个副本各自又单独持有一个唯一的私钥。第i个副本可以用他所持有的私钥去生成消息m的一个部分签名\rho_i \leftarrow tsign_i(m)。在|I|=k的条件下,部分签名{\rho_i}, i \in I可以用于生成一个m的数字签名\sigma \leftarrow tcombine(m, {\rho_i}, i\in I)。所有其余的节点都可以使用签名以及函数tverify验证签名的合法性。即tverify(m, \sigma)返回真当且仅当对于i \in I, |I| = k,有\rho_i \leftarrow tsign_i(m),且\sigma \leftarrow tcombine(m, {\rho_i}, i\in I)。考虑到我们需要允许先知者(oracles)访问oracles{tsign_i(\cdot)}{i \in [n]/F},一个竞争对手通过在小于k-f个先知者处查询tsign_i(m)得到可验证通过的签名概率可以忽略不计。在后续的论文中,我们将使用k=2f+1作为阈值,同样,我们通常会在协议描述中保留隐含的tverify调用。

Cryptographic primitives. HotStuff makes use of threshold signatures [48, 18, 14]. In a (k, n)-threshold signature scheme, there is a single public key held by all replicas, and each of the n replicas holds a distinct private key. The i-th replica can use its private key to contribute a partial signature \rho_i \leftarrow tsign_i(m) on message m. Partial signatures {\rho_i} i \in I , where |I|=k and each \rho_i \leftarrow tsign_i(m), can be used to produce a digital signature \sigma \leftarrow tcombine(m, {\rho_i}, i\in I) on m. Any other replica can verify the signature using the public key and the function tverify. We require that if \rho_i \leftarrow tsign_i(m) for each i \in I, |I| = k, and if \sigma \leftarrow tcombine(m, {\rho_i}, i\in I), then tverify(m, \sigma) returns true. However, given oracle access to oracles oracles{tsign<em>i(\cdot)}</em>{i \in [n]/F} , an adversary who queries tsign_i(m) on strictly fewer than k-f of these oracles has negligible probability of producing a signature σ for the message m (i.e., such that tverify(m, \sigma)returns true). Throughout this paper, we use a threshold of k = 2f + 1. Again, we will typically leave invocations of tverify implicit in our protocol descriptions.

我们还需要一个加密哈希函数h(该函数也被称为消息摘要函数),该函数将任意长度的数据映射至一个固定长度的输出。哈希函数应该是能够防止碰撞的,意思是对手能够找到两个输入mm_o,满足h(m)=h(m_o)是忽略不计的。综上,h(m)可以被看作输入消息唯一的标识符。

We also require a cryptographic hash function h (also called a message digest function), which maps an arbitrary length input to a fixed-length output. The hash function must be collision resistant [46], which informally requires that the probability of an adversary producing inputs m and m 0 such that h(m) = h(m_0) is negligible. As such, h(m) can serve as an identifier for a unique input m in the protocol.

复杂性度量 我们关心的复杂度度量是“认证复杂度”,具体来说,指的是GST之后(在GST之前,可能存在一些比较坏的情况,共识通信消息尚未完全到达),为了获得决策的共识,所有副本i \in [n]从其他副本那里获得的验证器(authenticator)的总和。这里,验证器或者是一个部分签名或者是一个完整签名。认证复杂度在衡量通信复杂度方面很有意义,原因有三点:第一,和比特复杂度相似,和消息复杂度不同,认证复杂度隐藏了一些由于传输方式导致的细节偏差。比如说,被分装到n个消息中的认证器和被装在1个消息中的认证器拥有相同的认证开销。第二,与比特复杂度相比,认证复杂度更能够捕获这类迭代达成共识的算法的开销。第三,在实践中,我们发现生成或验证数字签名,合并部分签名的密码学操作通常是使用他们的协议中计算最为密集的操作,因此验证复杂度同样也提供了对于计算量的洞察。

Complexity measure. The complexity measure we care about is authenticator complexity, which specifically is the sum, over all replicas i \in [n], of the number of authenticators received by replica i in the protocol to reach a consensus decision after GST. (Again, before GST, a consensus decision might not be reached at all in the worst case [27].) Here, an authenticator is either a partial signature or a signature. Authenticator complexity is a useful measure of communication complexity for several reasons. First, like bit complexity and unlike message complexity, it hides unnecessary details about the transmission topology. For example, n messages carrying one authenticator count the same as one message carrying n authenticators. Second, authenticator complexity is better suited than bit complexity for capturing costs in protocols like ours that reach consensus repeatedly, where each consensus decision (or each view proposed on the way to that consensus decision) is identified by a monotonically increasing counter. That is, because such a counter increases indefinitely, the bit complexity of a protocol that sends such a counter cannot be bounded. Third, since in practice, cryptographic operations to produce or verify digital signatures and to produce or combine partial signatures are typically the most computationally intensive operations in protocols that use them, the authenticator complexity provides insight into the computational burden of the protocol, as well.

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据