Popular Science | Long-distance attack problem of PoS protocol

In this article, we briefly discuss the largest cloud in the PoS protocol that is recognized as the largest long-range attack; the content also covers two current or expected solutions: weak subjectivity (weak subjectivity) ) and forward-secure keys . Finally, we propose a new fork selection rule that makes long-range attacks more expensive; this fork option can be combined with several existing solutions as an additional measure to prevent long-range attacks. This article is one of a series of articles on blockchain agreements and related topics. We continue to work on high-quality blockchain technology content creation. For a more comprehensive overview of current state of the art, please see our About Layer 2 approach, randomness. Related articles such as shards and papers (Editor's Note: Chinese translation at the end of the article). Also please follow our Twitter or join the Near Protocol channel to avoid missing content updates.

Long-range attack

In PoW, using the longest chain selection rule can yield a very satisfying attribute: unless a malicious attacker controls more than 50% of the computing power of the entire network, it can't reverse the block that has been confirmed for a while.

But there is no such feature in PoS. Especially when the block producers build the blocks and get back the pledge tokens, the keys used to create the blocks are no longer valuable to them; at this point the attacker can try to be much lower than the creation area. The token amount pledge at the time of the block to purchase these keys. Unlike PoW, because PoS does not have a mechanism to force delay between blocks, after buying a key, the attacker can create a pseudo chain longer than the main chain in a few minutes and is accepted by the fork selection rule.

There are two ways to avoid the above problem:

Weak subjectivity

The entire network node is required to periodically check the latest blocks and reject those blocks that "reorganize the overly long records." As long as the block is checked frequently enough that the time period during which the pledge token is released must contain more than one check, the node will never choose the longest chain created by the attacker because the adversary is from the certifier where the margin is taken out. The purchased private key must only be created from "too long" (so the node will reject those blocks).

The shortcoming of the weak subjective approach is that although the nodes already in the network are not deceived by the attacker, for the nodes joining the network for the first time, they do not have enough information to determine which chain was created first. Therefore, the new node will tend to choose the longer chain created by the attacker. In order to avoid this situation, the new nodes need to know the knowledge about the main chain in the chain in a certain way, which essentially requires them to choose to trust a certain subject in the network. Forward-secure keys

Another method is to ask the block creator to destroy the key they used to build the block in a very short time or immediately after the block is released; you can create a new key pair each time you build the block, or pass The forward security key structure (which allows the private key to be changed if the public key is consistent) is completed. This approach relies on the fact that the node is honest and strictly adheres to the agreement. Because once the block creator knows some point in the future, someone might want to buy their key, the key value is not zero, and the block creator has no incentive to destroy the key. Not to mention that at a certain point in time, it is not realistic to have a large percentage of block creators willing to modify their files and remove the private key; this depends on the agreement of most participants to cooperate honestly , and depends on most Participants are rational agreements, and the security guarantees between the two are not different. PoW is based on the premise that most participants are rational and will not collude, and their fork selection rules and anti-witch attacks also rely on this assumption.

Our proposed fork selection rule

Refer to the figure below: Block B has enough front position on the main chain, so most (or all) in-place verifiers have already taken out the deposit when B is generated.

The attacker has access to these block producers and obtains a private key of ~2/3; since the key is of no value to the block producer at this time, the attacker can pledge far below the actual building block. The amount to buy these keys.

Because there is no so-called scarce resource in the PoS system, an attacker can create a pseudo-chain that is longer than the main chain in a very short time.

We need a fork selection rule so that users (including those who access the network for the first time) don't see the chain created by the attacker as the main chain – no matter how long the attacker builds the pseudo chain, and how many A malicious verifier endorses his signature.

The bifurcation selection rule step proposed in this paper is: starting from the creation block, select each sub-block as the next legal block for each block by the following rules:

  1. After the current block is adopted by the main chain, the state is snapshotted.
  2. List all current accounts holding tokens and make a comparison table (public key → holding amount).
  3. For each candidate sub-block, according to the comparison table, find the public key of at least one transaction signed in the sub-block and its respective sub-tree (the block following the sub-block), and verify it.
  4. (Verification) Calculate the total amount of tokens transferred by the public key of at least one transaction in each candidate sub-block and its respective sub-tree; select the sub-block with the largest total amount of transferred tokens as the legal next block .

From the example in the figure, the current block is B, the candidate sub-blocks are C1 and C2; the sub-tree of C1 is the block on all compliant backbones, and the sub-tree of C2 is created by the attacker.

Starting from the B-block state snapshot, calculate the total amount of tokens transferred by the public key that signed at least one transaction (including token transfer and pledge token transactions) as the score of the main chain (C1); the chain created by the attacker The (C2) score is calculated in the same way, but because of the replay protection, all transactions in C2 and its subtrees are created by the attacker.

Starting from the B-block state snapshot, it is assumed that on the main chain (C1), the total amount of tokens transferred by the public key signed once and above is calculated as p; and on the chain (C2) created by the attacker, only the attacker exists. The transaction created by the purchased key, the total amount of tokens transferred by these public keys is q, then q&p is always established.

If the chain created by the attacker wants to get a higher score, then the total transaction amount in C2 and its subtree must be greater than p from the B-block state snapshot, so the attacker also needs to get the total amount in the account is greater than (p – q) The keys (and these keys cannot be signed in the main chain C1 and its subtrees) (otherwise these credits are counted in p). But the attacker has a headache at this time, because these key holders have not made any transactions in the main chain, so their account has funds in the snapshot state, so the attacker can not use the amount below the snapshot state. Get these keys.

Therefore, even if the attacker obtains the B block at a low price, and 80% of the "accounts that have initiated at least one transaction in the main chain", the attacker still has to pay at least 0.2p.

Please note that this fork rule is only valid if the main chain is resistant to bifurcation and needs to accumulate a large number of valid transactions, so this selection rule only applies to forked options that face long-range attacks. The fork selection rule can be combined with the classic solution, first forming a subset of the blockchain with the block determined by the BFT finality gadget, and executing the above-mentioned fork selection rule on the sub-chain. Then, based on the final block selected by the above rules, use other more suitable fork selection rules (eg, LMD GHOST).

Conclusion

The above-mentioned fork selection rules provide additional measures to prevent long-range attacks; although such rules have some interesting features, there are still many studies to be done before putting them into practical use. For example, it is unclear whether the rule will provide economic certainty; everything requires more long-term analysis.

At present, we are actively studying ways to defend against long-range attacks, and we are about to release more information, so stay tuned.

(Finish)

Original link:

Https://nearprotocol.com/blog/long-range-attacks-and-a-new-fork-choice-rule/

Author: ALEXANDER SKIDANOV

Translation & Proofreading: IAN LIU & Ajian

This article is authored by the author to translate and republish EthFans.