Loading...

Loading...

Scroll

Categories

Tags

Monthly Archives

Keyword

Back

SPECTRE:APPENDIX A

2018.07.25

Category

Tags

Source: https://eprint.iacr.org/2016/1159.pdf
TranStudy: https://github.com/DAGfans/TranStudy/new/master/Papers/SPECTRE

APPENDIX A

INTUITION AND EXAMPLES

In this section we provide some basic explanations and intuitions regarding the operation of SPECTRE. We focus primarily on explaining the ideas underlying Alg. 1 that is at the core of the protocol. We later go on to present examples for simple attacks that shed some light on how resilience is achieved.

在本节中,我们将提供关于SPECTRE操作的一些基本解释和思路。 我们主要关注解释作为协议核心的算法1的基本思想。 我们稍后继续介绍简单攻击的例子,以阐明如何实现韧性。

Intuition 1 (Vote in favour of visible blocks). If a block x is known by honest participants, their blocks will include it in their past. Given that blocks vote in favour of blocks in their past (over other unknown blocks), and given that honest nodes publish their blocks quickly, hidden attacker blocks lose votes.

思路1(投票赞成可见块)。 如果诚实的参与者知道区块x,他们的区块将包括在他们的过去。 鉴于区块投票赞成过去的区块(超过其他未知区块),并且鉴于诚实的节点快速发布区块,隐藏的攻击者区块会失去投票。

Intuition 2 (Majority amplification). Given blocks x, y that contain potential conflicts, blocks that are generated by honest participants after their publication reference both of them in the DAG. According to Alg. 1, these new blocks adopt the vote of the sub-DAG in their past with regards to x and y . Thus, if block x precedes block y , additional votes that support this decision are added, and the attacker will find it more difficult to reverse the vote.

思路2(多数放大)。 假定区块x,y包含潜在冲突的交易,在它们发布后由诚实的参与者在DAG中引用它们。 根据算法1,这些新块采纳了它们过去集的子DAG中关于x和y的投票。 因此,如果区块x位于区块y之前,则会增加支持该决策的附加投票,攻击者将发现更难以扭转投票结果。

Intuition 3 (Referencing recent blocks is beneficial). Blocks from the past vote according to their future. Thus if an attacker creates a block that does not reference recent blocks, it is at a disadvantage compared to other blocks that do (it loses votes from recent blocks it did not reference and did not “convince”).

思路3(引用最近的块是有益的)。 过去集的区块根据它们的未来集投票。 因此,如果攻击者创建了一个没有引用最近块的块,与其他块相比,它就处于劣势(它失去了它没有引用并且没有“说服”的最近块的投票)。

Intuition 4 (Votes from the past counter pre-mining attacks). Consider an attacker that creates a block y , withholds it, and constructs many blocks on top of it over an extended period of time. After a long while, a conflicting transaction is released to the network, and eventually ends up in some block x. Block y has many blocks (built by the attacker) that reference it. Thus, if only votes from the future are counted, block y would prevail even if x is allowed to accumulate some votes. In SPECTRE, blocks that were created by honest nodes while y was withheld, look to their future for their votes. These will usually vote in favour of x and will usually outnumber the attacker blocks that were created when y was withheld (an example of pre-mining appears in Fig. 3).

思路4(过去集的投票可以反击预挖矿攻击)。 假定一个攻击者创建了一个块y,并扣留它,并在很长一段时间内在它上面构建很多块。 很长一段时间后,一个冲突的交易被释放到网络,并最终被写入到某个块x中。 块y有很多块(由攻击者构建)引用它。 因此,如果只计算未来的票数,即使允许x累积一些票数,区块y也会占上风。 在SPECTRE中,在y被隐瞒时由诚实节点创建的块,会向他们的未来集寻求它们的投票。 这些通常会投票支持x,并且通常会超过y被隐瞒时创建的攻击者区块(预挖掘的一个例子出现在图3中)。

2018-07-17 12 00 53

Fig. 2: SPECTRE coincides with the longest-chain rule when it is applied to “simple” chains of blocks. In the depicted DAG, the chain ending at block 8 is longer and would be selected in the longest chain protocol. In SPECTRE each one of the blocks 5,6,7,8 precedes each of the blocks in 9,10,11. Consider for instance blocks 6 and 10 and the pairwise vote that involves them. Blocks 6-8 vote strongly 6 ≺ 10, as they see block 6 in their past but not block 10. Block 5 is a weak voter, as it sees neither 6 nor 10 in its past, hence it votes as the majority of its future (thus voting 6 ≺ 10 as well). For similar reasons, blocks 9-11 all vote 10 ≺ 6. Block 4, at the fork of the two chains, is a weak voters as well, as it sees neither 6 nor 10 in its past; it therefore votes according to the majority of future blocks. As block 4 sees four votes in favour of 6 ≺ 10, and three votes in favour of 10 ≺ 6, it will vote in favour of 6 ≺ 10. Blocks 1-3 similarly vote according to their future, and see an increasing number of votes for 6 ≺ 10, adding their own vote to the result. Thus, the end result is that 6 precedes 10.

图2:当SPECTRE应用于“简单”区块链时,SPECTRE与最长链规则相吻合。(译注: 简单这里指, 分支很少) 在所描绘的DAG中,以区块8为结尾的链更长, 因此会被选取为最长链。 在SPECTRE中,区块5,6,7,8中的每一个都在9,10,11中的每个块之前。 考虑例如区块6和10以及涉及它们的成对投票。。 区块6-8会明确地投票给6 ≺ 8,因为他们看到过去集的块6,而不是块10。 块5无法明确地投票,因为它过去集没有看到过6,也没有看到过10,所以它会根据其未来集中多数票来投票(因此也投票给6 ≺ 10) )。 由于类似的原因,9-11块都投了10 ≺ 6. 区块4在两个链的分叉处,也无法明确投票, y因为它无法在其过去集中看到6和10;它因此会根据其将来集中的区块多数票来投票。 因为区块4看到四票投给了6 ≺ 10, 还有三票投给了10 ≺ 6, 它会投票给6 ≺ 10. 类似地, 区块1-3根据它们的将来集投票,可以看到投给6 ≺ 10的票数越来越多,会将它们自己的票投给这个结果。 因此,最终的结果是6比10靠前。

A. Equivalence to longest-chain

A. 等效于最长链规则

We now demonstrate how SPECTRE coincides with Bitcoin’s longest-chain rule, in the case of a “simple” fork between two chains. Consider the DAG illustrated in Fig. 2. In Bitcoin, the longer chain would be selected. Similarly, in the pairwise ordering of SPECTRE, each of the blocks in the longest chain 5,6,7,8 would precede each of the blocks in the shorter one 9,10,11. To see why this is true refer to the caption of the figure.

现在我们来演示一下SPECTRE为什么和比特币是一致,那么两个链之间的“简单”分叉就是一例。 考虑图2所示的DAG。 在比特币中,选择较长的链。 类似地,在SPECTER的成对排序中,最长链5,6,7,8中的每个块将位于较短块9,10,11中的每个块之前。 要明白为什么这是真的,请参考数据的标题。

We now turn to examine two different attack scenarios, which we name double-spending, and censorship. Recall the requirement from our miner protocol: each miner is required to (i) reference recent blocks, and to (ii) publish his blocks immediately. Each attack is basically a violation of one of these requirements. In the double-spending attack, the attacker delays the publication of a set of blocks (that includes a conflicting transaction), and in the censorship attack he publishes blocks but “ignores” a certain block and transactions inside it, hoping to convince nodes that it did not secure enough votes, and thus cannot be accepted.

我们现在转而考察两种不同的攻击情景,我们称之为双花和审查。 回想一下我们矿工协议的要求:每个矿工必须(i)引用最近的块,并(ii)立即发布他的块。 每种攻击基本上都违反了这些要求之一。 在双花攻击中,攻击者推迟发布一组块(包括冲突交易),并且在审查攻击中,他发布了块,但是“忽略”某个块和其中交易,希望说服节点该块没有获得足够的选票,因此该块不能被接受。

B. Example of a double-spending attack

B. 双花攻击的例子

Fig. 3 depicts an (unsuccessful) double-spending attack. The attack is composed of three main phases: 图3描述了一次(不成功)的双花攻击。 攻击由三个主要阶段组成:

Phase I: Pre-mining. In phase I, the attacker begins building blocks and withholding them from the network. The first block that is constructed (named block y ) contains a transaction that will later conflict with the transaction sent to the honest nodes. Blocks built by the attacker ideally form a chain, and due to the voting rules in SPECTRE, will all vote y ≺ x (blocks y ,13,14). Blocks built by the honest node are unaware of y (and also of x that is yet to be created), and will eventually vote according to the majority of future votes. During this phase, attacker blocks reference honest blocks that are built (in hopes of later convincing them to vote y ≺ x). After some time, the attacker transmits the transaction to the network, and proceeds to phase II.

阶段I:预挖 在阶段I中,攻击者开始构建区块并组织它们进入网络, 。 构造的第一个块(名为块y)包含一个交易,稍后将与发送给诚实节点的交易冲突。 由攻击者构建的区块在理想的区块下会形成一个链,并且由于SPECTRE中的投票规则,它们都会投票 y ≺ x(块y,13,14)。 由诚实节点构建的块不知道y(还有尚未创建的x),并且最终将根据大多数未来投票进行投票。 在这个阶段,攻击者会阻止被创建诚实块(希望以后说服他们投票y ≺ x)。 一段时间后,攻击者将交易传输到网络,然后进入第二阶段。

2018-07-17 1 53 48

Fig. 3: An example of the voting procedure on a DAG in which a double-spending attack is (unsuccessfully) attempted. Block x and blocks 6-8 vote strongly x ≺ y as they only see x in their past, and not y . Similarly, block y and blocks 13-19 vote strongly y ≺ x. In the DAG which is the past of block 11, each of the blocks 1-5 sees more x ≺ y voters in its future than y ≺ x voters, hence each of them votes x ≺ y . Block 11 votes (as the virtual block of its past votes), according to the majority in its past, thus it too votes x ≺ y . A similar argument goes for the the vote of 11 and 12. Finally, aggregating the vote of all blocks in the DAG, x got more votes hence x ≺ y .

图3:DAG中投票程序的一个例子,其中尝试了双花攻击(未成功)。 块x和块6-8明确投票支持x ≺ y,因为他们只在它们的过去集合看到x,而不是y。 同样,区块y和区块13-19明确投票支持y ≺ X。 在块11的过去集形成的DAG中,块1-5中的每个块在各自的将来集中可以看到支持x ≺ y 的比 y ≺ x 更多,因此它们都投票支持x ≺ y。 区块11(可以看作是它过去集的虚拟块)根据它过去集的大多数来投票, 因此也会投票支持x ≺ y . 类似的思路也可以用于求得区块11和12的投票。 最后,汇总DAG中所有块的投票,x得到更多的选票,因此x < y。

Notice that at the exact time that phase I ends, the attacker has more blocks above block 4 than honest nodes have, so it starts at an advantage: it will more easily sway the vote of block 4 towards y ≺ x (this advantage later disappears as honest nodes typically build blocks faster than the attacker).

请注意,在阶段I结束的确切时间,攻击者比真实节点具有更多的块在块4上方,因此它从一个优点开始:它将更容易地将块4的投票移向y? x(这种优势随后消失,因为诚实的节点通常比攻击者更快地构建块)。

Phase II: Waiting for acceptance. The attacker now continues to build blocks in secret. If he publishes his blocks, then his conflicting transaction will be visible to all, and the double-spend will be detected. Instead, he waits for block x to receive sufficient weight (in the form of blocks built on top of it) so that the recipient of the transaction in x accepts it, and provides the attacker with some service or product. During this phase, attacker blocks that are created (blocks 15-17) vote y ≺ x, as the attacker is careful to have them reference only his secret chain, and never indirectly reference block x. Honest blocks created during this phase will typically vote x ≺ y since y is hidden from them. Some small number of blocks (created before x propagated to the whole network – block 5 in this example) do not reference x, and so will vote according to the result of future votes.

第二阶段:等待接受。 攻击者现在继续秘密构建区块。 如果他发布了他的区块,那么所有人都可以看到他的冲突交易,并且会检测到双花。 相反,他等待块x接收足够的权重(以在其上构建的区块的形式),以便x中的交易的接收者接受它,并向攻击者提供某种服务或产品。 在此阶段,被创建的攻击块(区块15-17)投票给 y ≺ x,因为攻击者小心地让它们仅引用他的秘密链,并且从不间接引用块x。 在此阶段创建的诚实块通常会投票x ≺ y 因为y是隐藏的。 少量的块(在x传播到整个网络之前创建 - 在本例中为块5)没有引用x,因此将根据未来投票的结果进行投票。

Phase III: Race to overtake. Once x was accepted by the victim, the attacker wishes to publish his secret blocks in hopes of causing his conflicting transaction in y to precede x. In this case, the transaction in x will be considered rejected, and the payment will be canceled (leaving the attacker with an item he did not pay for). He publishes his secret chain (which from this point on is referenced by honest nodes), and continues to build upon it. Blocks that he builds, again do not reference x, and so they vote y ≺ x, supporting his goal. New honest nodes are for the first time exposed to the conflicting transaction y , and thus vote according to the result in the sub-DAG in their past.

第三阶段:竞争以赶超。 一旦x被受害者接受,攻击者就希望发布他的秘密块,希望使他的冲突交易y在x之前。 在这种情况下,x中的交易将被视为已驳回,并且付款将被取消(向攻击者留下他未支付的交易)。 他发布了他的秘密链(从这个时间点开始,由诚实的节点引用),并继续在它上面构建。 他建立的块,再强调下不引用x的,所以他们会投票y ≺ x,支持他的目标。 新的诚实节点首次暴露于冲突交易y,因此根据过去集的子DAG中的结果进行投票。

Why the attack fails. First, notice that the attacker in the above example creates fewer blocks in each phase than the honest nodes. This will usually be the case if attackers have less computational power than all honest nodes. “Poisson bursts” in block creation by the attacker are possible, and this will allow him to overtake the network, but these are less likely if the attack lasts for a long period of time. The defender can control the length of phase II by waiting a long while before accepting the transaction, which decreases the probability of such bursts. If phase II is long enough, x will have more votes in this period than y . Weak blocks in the past of x will then vote in favour of x, according to this majority. Such blocks that look at their future begin a cascade: each block further in the past adds a vote that agrees with the majority of future blocks and thus strengthens the decision. The greater the majority obtained in Phase II, the less likely it is that the attacker will be able to catch up from behind in Phase III. The attack therefore depends heavily on successfully swaying the votes of blocks that were created just before x (e.g., block 4).

为什么攻击会失败。 首先,请注意上面示例中的攻击者在每个阶段中创建的块比诚实节点少。 如果攻击者的计算能力低于所有诚实节点,则通常会出现这种情况。 攻击者创建块时可能会出现“泊松爆发(Poisson bursts)”,这将使他能够超越网络,但如果攻击持续很长一段时间,则不太可能。(译注: 柏松爆发这里指有可能攻击者短期内出块速度比全网其他节点快, 但这种是小概率时间, 且很难持续) 通过在接受交易之前等待很长时间,防御者可以控制第二阶段的长度,这降低了这种突发的可能性。 如果第二阶段足够长,x将在此期间获得比y更多的选票。 根据多数人的说法,x过去的弱块将投票支持x。 这些看待未来的区块开始了一个级联:过去的每个区块都会增加一个与大多数未来区块一致的投票,从而加强决策。第二阶段获得的大多数人越多,攻击者在第三阶段就能越过后卫的可能性越小。 因此,攻击在很大程度上取决于成功地摇摆在x之前创建的块的投票(例如,块4)。

It is important to note that an attacker that creates more blocks in expectation than the honest network will succeed in carrying out this attack. The blocks voting y ≺ x would outnumber those who vote to the contrary. Hence the 50% threshold in Theorem 3.

值得注意的是,攻击者如果预期能比诚实网络创建更多的区块, 则可以成功实施这种攻击。 投票支持y ≺ x的区块会超过那些投反对票的。 因此,定理3中的阈值为50%。

C. Example of a censorship attack

C. 审查攻击的例子

Fig. 4 depicts an (unsuccessful) censorship attack. The attack is composed of a single main phase during which an attacker creates his own blocks, publishes them instantly, but also ignores (and does not reference) recent blocks created by the honest network. The figure depicts (in stage I on the left side) the current state of the blockchain (where all blocks are published at this point). An honest participant that then observes the network and wishes to tell if a transaction in block x is secure, can see a large number of blocks that do not reference x. These blocks are not guaranteed to vote in favour of x. An attacker may later insert a conflicting transaction y and add blocks atop it (this projected attack is depicted on the right-hand side of the figure). These may potentially sway previously created attacker blocks to vote against x.

图4描绘了一次(不成功的)审查攻击。 攻击由一个主要阶段组成,攻击者在此期间创建自己的块,并立即发布,但也忽略(并且不参考)诚实网络新建的块。 该图描绘了(在左侧的第一阶段)区块链的当前状态(此时所有区块都被公布)。 然后,一个诚实的参与者观察网络并希望判断块x中的交易是否安全,可以看到大量不引用x的块。 这些区块不保证投票支持x。 攻击者可能稍后插入冲突交易y并在其上添加块(此预测攻击描绘在图的右侧)。 这些可能会影响先前创建的攻击者块以投票反对x。

The main risk from the censorship attack is that merchants, upon seeing the attacker’s blocks, will consider transactions in block x not sufficiently secure. This could potentially delay the acceptance of transactions forever. Our analysis of SPECTRE shows that even in this case the merchants accept transactions quickly (and securely).

审查攻击的主要风险是,商家在看到攻击者的区块后,会认为区块x中的交易不够安全。 这可能会永久延迟对交易的接受。 我们对SPECTRE的分析表明,即使在这种情况下,商家也能快速(和安全地)接受交易。

2018-07-17 1 57 49

Fig. 4: An example of the voting procedure on DAG in which an unsuccessful censorship attack is depicted. The left side depicts the current state of the block DAG. The right-hand side depicts its likely future development. Blocks 12-16 do not add strong votes to x. Can they be convinced to vote for block y when it appears? Will they further sway other blocks in their past? The vote of each block in this projected future are depicted: Blocks 2-9 vote strongly for x as they see it in their past (but not y ). Blocks 17-18 similarly vote strongly for y . Block 16 is indeed convinced to vote for y as more blocks in its future vote for y than for x. Blocks 1, 12-15 vote for x. They each see more votes in favour of x than votes in favour of y in their future. Blocks 10-11 see more x ≺ y voters in their past when they make a recursive call.

图4:DAG的投票程序示例,其中描述了一次不成功的审查攻击。 左侧描绘了区块DAG的当前状态。 右侧描绘了其未来可能的发展。 区块12-16无法明确投票给x。 当它出现时,它们能否被说服投票支持y? 它们会进一步影响它们过去集的其他区块吗? 在这个预计的未来中,每个区块的投票都可以被描绘出来:区块2-9会明确投票支持x因为它们在它们的过去集中看到了x(而不是y)。 区块17-18同样明确投票给y。 事实上,块16确认投票给y因为它在它的将来集中看到更多的区块支持而非x。 块1,12-15投票给x。 它们每个人 在它们未来集中都看到支持x的投票多于支持y。 块10-11在它们的过去集中递归调用时看到更多的区块支持x ≺ y。

Related Posts

Top