Appendix A
Last updated
Last updated
This section demonstrates that Satoshi Plus is secure if less than one-third of the validators are adver- sarial. It begins by examining the actions of potential enemies. What is the adversary’s “ideal” strategy, and what could they achieve? It asserts that the one-third bound is tight by presenting an idealized attack method: under some attack, the system is compromised if the adversary takes more than one-third of the validator seats. Anything less than one-third would be unsuccessful. Thereafter, it discusses the logic behind the proof, as well as the methodology of proof by contradiction. Finally, the formal proof is presented, which explains the claimed outcomes mathematically.
This section considers ways to increase the likelihood of a safety violation from an adversarial stand- point. It presents one method for carrying out a double-spending attack. In this attack, adversaries manage to keep a second blockchain hidden, releasing it when their attack begins. The double-spending attack is successful if the revealed blockchain is longer than the current longest public blockchain. To accomplish this, the adversaries must take advantage of the protocol and manipulate the honest blocks in such a way that they assist in the attack without violating the protocol. For example, they can keep the attacking and legal blockchains as balanced as possible, as demonstrated in Figure 6,
There are three validators in this attack, one of which is adversarial. The attack target is the block on slot 0 (designated with a star). Block 1 is originally hidden during the attack. The block with the star and block 1’ are visible to honest validators, and they are oriented to generate the new block, block 2, on top of block 1’. The attacker then generates a new block, block 4, on top of block 1, publishes it, then generates block 4’ and hides it at slot 4. As a result, when honest validators observe two blockchains of the same height at slot 5, they attempt to generate a new block, block 5, on top of block 4, and so on. With this strategy, the two blockchains may be kept balanced for as long as possible with only one adversary. A user’s transaction is not secure no matter how long they wait. Even though 16 slots have elapsed in this example, the targeted block is reverted if the adversary decides to perform an assault at slot 16.
This section dives into the attack strategy to get a sense of what a successful attack looks like. As dis- cussed above, each honest validator generates exactly one block in its slot. In this attack, two adversarial blocks are generated at an adversarial validator’s slot and contributed to two different blockchains, with the idea being to maintain a balance between the two. As a consequence, at each height, a matching pair of blocks is required. Assume block 1’ is the start of the attack and has the same parent as the block with the star in this scenario. The height of block 4 is equal to that of block 3, whereas block 4’ is equal to that of block 5. Block 7’ corresponds to block 6, while block 7 corresponds to block 8.
The key to a successful attack is for each adversary to generate two blocks in their respective slot and match them to two separate honest blocks. The “onematch- two” pattern illustrates why, for a successful attack, the ratio of adversarial to honest validators must be at least 1:2, implying that the safety guarantee is one-third of adversaries.
Is the adversary capable of more? Is it possible to construct three adversarial blocks in one slot and match them to three honest blocks? The answer is no. The reason for this is that the two adversarial blocks formed at the same slot must match two honest blocks, one of which is generated before the slot and the other after the slot. To match to three honest blocks, two adversarial blocks must match two honest blocks generated both before and after the slot, which is not possible. The next section will include a formal proof.
The major technique used here is proof by contradiction. Proving something by contradiction involves assuming that the statement under examination is not true, and then showing that the consequences of this are not possible. That is, the consequences contradict either what was just assumed, or something already known to be true.
This proof assumes the total number of validators is N, among which m validators are honest and the remaining validators are adversarial. Then,
According to the protocol, a discrete model is adopted, in which actions take place in slots. If a validator publishes one or more blocks in a slot, all validators receive the block(s) by the end of the slot. A val- idator is said to be honest if it always follows the protocol. Each validator is either honest or adversarial. A block is said to be honest if it is generated by an honest validator. Evidently, by the end of each slot, all honest validators are fully synchronized. Honest validators only generate new blocks on top of the longest published blockchain(s) at their own slots. A blockchain is said to be honest in slot r if it is the longest blockchain as seen by some honest validators in slot r. In discussions of the blockchain, it is always assumed that the blockchain is legal (i.e., accepted by honest validators) according to the protocol. An honest validator slot is defined as a slot in which the legal generator is an honest validator.
Blockchain b is the blockchain ending with block b. Let T(b) denote the slot in which block b is generated. The height of block b, denoted as h(b), is defined as the number of blocks (including the genesis block) in the same blockchain. Then,
Lemma .1. Honest blocks have identical heights.
Proof. This is a simple consequence of the fact that all honest generators have seen the same blocks and every honest validator adopts the longest blockchain at the end of every slot.
Lemma .2. Suppose two adversarial blocks, block a and block b, satisfy T (a) = T (b) and match two honest blocks c and d, then (T (a) − T (c))(T (a) − T (d)) < 0. That is to say, the two honest blocks cannot be generated both before or after the slot of the adversarial blocks.
Proof. Contrary to the claim, assume blocks c and d could be generated both before or after slot T (a). Without losing generality, assume they are generated after T (a). By definition, claiming that block a matches block d (block b matches to block c, respectively) implies h(a) = h(d)(h(b) = h(c), respec- tively). By the protocol, since honest block c is generated after block a on the same blockchain, we have h(c) > h(a) (and h(d) > h(b), respectively). Thus,
This gives rise to a contradiction, thus the proof.
Note that as a consequence, one adversary can match at most two honest blocks during one slot.
An adversarial sequence is defined as a sequence of consecutive adversarial validators as ranked by the protocol. We say an adversarial block matches an honest block if they are at the same height of different blockchains.
Lemma .3. The adversarial blocks generated by an adversarial sequence of n validators match at most 2n honest blocks.
Proof. This is a natural extension of Lemma 2
A block is said to be permanent after slot r if the block remains in all honest blockchains starting from slot r. Basically, if a user transaction is permanent, the user can safely believe their transaction will not be reversed no matter what the adversaries do in the future.
Theorem .4. If an honest block b remains in an honest blockchain in slot T(b)+ N, then block b is permanent.
Proof. We prove the desired result by contradiction. For simplicity let r = T (b). Let n be the number of adversaries in the N validators.
Contrary to the claim, assume s ≥ r + N is the smallest slot when there exists some other honest blockchain d1 which does not include block b. Then there exists another honest blockchain d2 in slot s − 1 containing block b. Then h(d2) ≤ h(d1). Let k be the number of adversarial sequences in the first N validator rank starting from slot r. Let n1, n2, . . . , nk be the number of validators in each adversarial sequence. This means [Pki = 1]ni = n and k ≤ n. Let function M(ni) represent the number of honest blocks matched by adversarial sequence ni. Then, we have M(ni) ≤ 2ni by Lemma 3. Let l = [(s − r)/N], then l is a positive integer since s − r ≥ N. Let k′ be the number of adversarial sequences starting from slot r + lN ending in slot s. Then n1, n2, . . . , nk′ are the number of validators in the adversarial sequences during slot [r + lN, s].
Note that since there are k′ adversarial sequences, there are at least P[k′i = 1]M(ni) honest validators during slot [r + lN, s] to separate the sequences. Thus the total number of honest blocks during [r, s] is at least lm + P[k′i = 1]M(ni). Note that each honest block has identical heights according to Lemma 1, thus the height increase of blockchain d1 and blockchain b2 are both at least
blocks are generated and included in the two blockchains during slot [r, s].
On the other hand, we calculate the maximum number of blocks that the adversaries can match in the two blockchains. Each adversarial sequence with ni validators contributes M(ni) blocks to match the honest blocks in the two chains. Thus, the total number of honest blocks being matched is
The mathematical proof in the previous section demonstrates that as long as a transaction is confirmed by more than N blocks, where N is the size of the elected validator set, it can never be reversed. It has also been proven that to perform an attack successfully, a minimum of 1/3 of the validators must be adversarial.
Note that the adversarial model used in the proof is extremely strict. The adversaries in the proof’s model are assumed to be operating in conditions of perfect coordination and are placed in perfect slots in the set to compromise honest validators in a 1:2 ratio. In this case, they also have the ability to induce honest validators to choose the required block to perform the attack when there are 2 blocks with the same block height.
In reality, the conditions mentioned above are very unlikely to occur, and, in some cases, are impossible. Strong punishments have been implemented for various malicious behaviors to disincentivize validators from conducting such behaviors. As a result of these countermeasures, for normal transactions on Core, (1/2)N block confirmations should prove sufficiently safe. For more critical transactions, we recom- mend (2/3)N+ block confirmations. For the most pessimistic case, N block confirmations will achieve 100% safety.
Most of the attacks outlined throughout this document have been mitigated. The proof above provides strong guarantees that with enough block confirmations, the network is always safe. To provide additional protection, slashing, jailing, and ejection mechanisms have been implemented to further disincentivize malicious behaviors. Verifiers can submit evidence to have validators slashed and jailed for different cases.
