Seed - Dev. Discussion - Solving The Poison Chain Problem

carsonroscoe (61)in #crypto • 6 years ago

Overview

Despite the Seed project being a hybrid approach between blockchain and directed acyclic graph (DAG) technologies, tech transaction validation process is achieved solely through the DAG portion. This allows Seed to bypass the problems found in traditional blockchain proof-of-work, as explained in my literature review. However, this comes at the drawback of inheriting the flaws of the DAG.

Today we're going to discuss the security threat of poison chains, which is the primary threat behind DAGs, and possible solutions to avoid this threat.

Distributed Validation

First, we will briefly go over how transactions are validated in directed acyclic graphs in a distributed manner, without miners or any centralized powers.

How DAG's Validate

Directed acyclic graphs validate transactions by having transactions themselves offer the validation work required. For example, they may require that each transaction validates two other transactions. This works by having the validation process be shared, indirectly validating multiple transactions. If transaction A validates transaction B, and B validated C, then transaction A is indirectly contributing to transaction C's validation.

If a transaction is invalid, the protocol is to simply ignore it. A transaction only becomes valid by being given enough validation work. If all users follow the protocol correctly, invalid transactions would never become valid, and would just sit in the graph, stagnating. This process works as long as all actors are honest.

Where this process fails is not when a transaction lies, but when the validating transactions lie about their validation work. If a large enough amount of transactions lie with regards to their validation work, they can validate each other, and the rest of the network could be none the wiser. Any user who detects the lie would simply refuse to validate the transaction, keeping the honest users quiet, despite the lie continuing to validate.

Majority Rules

The goal of any distributed validation system is to create majority rules approach, where users must control the majority of the actors in order to lie. The above approach fails to meet this goal, as a minority of the network can successfully get away with lying if they are large enough. In this scenario, "large enough" does not refer to requiring a certain percent of the network, more-so it requires simply a handful of users lying. In actuality, one person could create these many users, and therefore it simply takes one person to abuse the system.

Poison Chains

Poison Chains are the malicious byproduct of this inherent problem with distributed validation. We will discuss what is a poison chain, and how could they be either prevented or refuted.

What Is A Poison Chain

A poison chain is the term for the phenomenon listed above. It occurs when a group of transactions strictly validates each other while being loosely connected to the DAG. This separate chain is not, at first, propagated to the entire network, and is instead kept a secret between only the malicious actors. These users continue to validate each other, creating malicious transactions, and then lying with regards to their validation work, claiming the lies were honest.

Once the chain is large enough that the malicious transactions are valid, the malicious actors can propagate their chain to the rest of the network. Nodes receiving this chain will be fed the malicious transaction, but then very quickly receive validation showcasing the transaction was valid. Enough validation comes in that users will not be expected to validate the malicious transaction anymore. At this point, the poison chain has successfully exploited the graph.

Preventing Poison Chains

The follow approaches are solutions other DAG's have taken in the past when attempting to solve this issue.

Coordinated Validation

Having some sort of "coordinator" which dictates which transactions need validating, and by who, is one simple solution to the dilemma. Due to the security threat being a problem with users lying with regards to their validation work, taking away their right to pick who they validate prevents transactions from exploiting this flaw.

The flaw of this approach is it requires a degree of centralization. Somehow, we need to enforce which transactions need to be validated. We cannot be fully aware of what transactions are available in a users local DAG, due to being unaware of which transactions had been propagated to any given user, and when. The order transactions were received in varies due to jitter on the network. Therefore, we cannot simply have users follow an algorithm on their local computer in order to pick the transactions to validate, as that would be unenforceable. The only way to provably do this would be to rely on the coordinator to make the decisions, which adds a single point of failure to the network.

Even if a solution existed which did not require a centralized node, this solution does not prevent exploitation fully. It simply prevents users who choosing to be in the position to exploit the system. The threat still remains, albeit becomes very unlikely to ever occur.

Limit User Creation

If account creation was limited, we could simply not allow malicious actors to have accounts, or somehow keep them only having one account. Users cannot validate themselves, therefore limiting accounts can potentially solve the issue.

There are a couple flaws to this approach. First and foremost, it may also require centralizing the system to enforce account creation. On top of that, it makes it inconvenient for users to initially create their keys to join the network. Considering the speed of DAG's comes from having many users and transactions, we want to encourage users to join early on, not discourage them.

Staking/Proof-of-Stake

A common proof-of-stake style approach is to have users stake currency upon creating a transaction. There are variations of this approach outlined across the internet, however the simplest approach is to have users stake their currency upon creating a transaction, and have that currency returned to them at some point in the future, as long as their transaction is deemed valid. If another user outs a liar, they receive the liars staked currency as a reward, as well as the stakes of every user who validated the liar.

This approach can work, however it comes with new constraints to consider. Users now need currency to use the network, which prevents the network from truly being free. It becomes harder to initially fund accounts, and also allows a user with enough stake to control the network by effectively buying the network. However, any user with adequate stake will be deterred from harming the network, as it would destroy the value of their stake.

Staking works and is a valid approach, however it does come with its own set of drawbacks. It requires a currency to be built into the system, and a staking system to be present. It requires users to have some currency in order to even make transactions to begin with, which adds a complicated barrier to entry for most. Despite these drawbacks, it is a valid solution.

Refuting Poison Chains

The alternative to preventing poison chains would be to have a mechanism present for refuting such chains.

Moderators

Moderators having special transactions is one approach. Simply put, a transaction chain requires a moderators' direct or indirect approval in order to become valid.

This does, however, indirectly centralize the network. Requiring special users creates a class system, instead of keeping every user equal in the system. Each user still creates transactions and contributes to the validation process, however many users effectively get extra power over others. If the act of becoming a moderator was available to the public, it must now be considered how we avoid malicious moderators gaining the power.

If only users trusted by the Seed creators can become moderators, the system stops being decentralized, now relying on trust.

Transactions Refusing Transactions

Following the concept of transactions validating other transactions, the same process could be attributed to refuting transactions.

This could work by allowing transactions to state which transactions they do not acknowledge. If a node is to accept this transaction to the network, they must reject the refuted transaction, and by proxy, any transactions which validated the refuted transaction.

This process would force clients to reevaluate specific points in history in order to determine which transaction is the honest one.

Transaction Refuting Expanded

Preventing poison chains would be ideal, however, to the best of my knowledge, none of the existing solutions fit for the Seed project's use-case. Seed should remain distributed, without any centralized nodes, without any class system, and without requiring users own currency before using the network. The only approach which appears to solve the poison chain problem would be having transactions refute transactions.

As stated above, transaction refuting would allow transactions to state which transactions they do not acknowledge. If a node is to accept this transaction to the network, they must reject the refuted transaction, and by proxy, any transactions which validated the refuted transaction.

If transaction A refutes transaction B, then moving forward, only transaction A or transaction B can be stored in history. Nodes are forced to determine which transaction is honest. If, after reevaluating, transaction B was malicious, transaction B and every transaction which directly or indirectly validated it, would be removed from the entanglement. If it is discovered that transaction B was honest and did properly affect the ledger as expected, transaction A is ignored.

How users on the network "vote" for which transaction is real is by simply accepting their real-one. The act of creating a transaction which validates the refuter can be viewed as a "vote" towards removing the refuted transaction. The act of creating a transaction which validates the refuted transaction can be viewed as a "vote" towards keeping the refuted transaction.

The network temporarily splits on each refute, however the split should be small. This becomes a "majority rules" phenomenon, where the chain that will keep growing is the one that the community decided was honest.