Short-range attacks come in a variety of forms, but in summation, they are aimed at rewriting a small number of blocks rather than all the way back to Genesis. Some notable examples are bribery attacks, liveness denial, and race attacks. Below, we present a mathematical proof stating that as long as less than 1/3 of the nodes are malicious and enough blocks are confirmed, transactions on Satoshi Plus are definitely safe.
Mathematical Proof
In this section, we demonstrate that Satoshi Plus is secure if less than one-third of the validators are adversarial. We begin by examining the actions of potential enemies. What is the adversary’s “ideal” strategy, and what could they achieve? We assert 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, we discuss the logic behind our proof as well as the methodology of proof by contradiction. Finally, we present the formal proof, which explains the claimed outcomes mathematically.
The Balanced Attack
In this section, we consider the ways to increase the likelihood of a safety violation from an adversarial standpoint. We present one method for carrying out a double-spending attack. In this attack, the adversaries manage to keep a second blockchain hidden and release it when attacking. 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 feasible, as demonstrated in Figure 6,
3 validators are in this attack, one of which is adversarial. The attack target is the block on slot 0 (with a star sign). 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 another 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 are motivated 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 feasible with only one adversary. A user’s transaction is not secure no matter how long they wait. Even though 16 slots have elapsed in our example, the targeted block is reverted if the adversary decides to perform assault at slot 16.
Methodology
Let’s dive into the attack strategy in part 4.2.2 to get a sense of what a successful attack looks like. Each honest validator, as we know, 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 blockchains. The idea is to maintain a balance between the two blockchains. 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 our 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 adversarial to honest validator ratio 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 we use is proof by contradiction. To prove something by contradiction, we assume that what we want to prove is not true, and then show that the consequences of this are not possible. That is, the consequences contradict either what we have just assumed, or something we already know to be true.
Formal Proof
We assume the total number of validators is N, among which m validators are honest and the remaining validators are adversarial. Then,
m > (2/3)N. (16)
According to the protocol, we adopt a discrete model where 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 validator 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 (resp. adversarial) if it is generated by an honest (resp. adversarial) 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. When mentioning a blockchain, we always assume the blockchain is legal (i.e., accepted by honest validators) according to the protocol. Define an honest validator slot to be a slot where the legal generator is an honest validator.
By saying blockchain b, we mean 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 we have
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 the 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, by claiming block a matches to block d (block b matches to block c, respectively), we have h(a) = h(d) (h(b) = h(c), respectively). 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, we have,
h(a) = h(d) > h(b) = h(c) > h(a). (17)
Contradiction arises, 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 exist 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 sequences. We have [Σk i=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 ℓ = [ (s−r) / N ], then ℓ is a positive integer since s − r ≥ N. Let k′ be the number of adversarial sequences starting from slot r + ℓN ending in slot s. Then n1, n2, . . . , nk′ are the number of validators in the adversarial sequences during slot [r + ℓN, s].
Note that since there are k′ adversarial sequences, there are at least Σ[k′ i=1] M(ni) honest validators during slot [r+ℓN, s] to separate the sequences. Thus the total number of honest blocks during [r,s] is at least ℓm + Σ[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
Contradiction arises with equation 18.
Summary of Security and Finality
Based on the mathematical proof in the previous section, we conclude 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. We have also 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. YESCOIN has implemented strong punishments on various malicious behaviors to disincentivize validators to conduct such behaviors. As a result of these countermeasures, for normal transactions on YESCOIN, (1/2)N block confirmations should provide enough safety. For more critical transactions, we recommend (2/3)N+ block confirmations. For the most pessimistic case, N block confirmations will achieve 100% safety.
Slash-able cases
YESCOIN has managed to mitigate most attacks by various means outlined throughout this document. Our proof above provides strong guarantees that with enough block confirmations we are always safe. However, we also chose to implement slash + jail/ejection mechanisms to further disincentive malicious behaviors. Verifiers can submit evidence to have validators slashed and jailed for different cases. Two notable cases that are slash-able are double signing and unavailability.
Last updated