Weak Independence

As stated earlier, FastSet allows claims to be processed and settled in any order, unless they originate from the same account, in which case, the claim order is preserved.

Although the ordering is relaxed, FastSet provides the same correctness guarantees as systems that enforce a total order. However, it does not employ a strong consistency consensus algorithm like blockchains do to achieve correctness. Instead, FastSet adopts an eventual consistency consensus, sometimes called "weak consensus". And this is possible because of the weak independence requirement on claims it enforces.

This section explains weak independence and how it enables the next generation of decentralized and concurrent infrastructure for digital assets.

Total ordering

There has been a long-held belief that decentralized payment systems are required to enforce a total order on transactions in order to prevent the double-spending attack.

A double-spending attack is one in which an account sends two concurrent transactions attempting to spend the same coin with two different recipients.

This is why all blockchains are built the way they are. Validated transactions are chained together to preserve the historical order and to solve the double-spending issue.

However, it turns out that payments can be generated and settled in different orders by different nodes in the network and still prevent the attack from taking place. See recent work on The consensus number of a cryptocurrency and FastPay introducing this idea. The insight here is that the order in which an account receives payments is irrelevant. Moreover, even the order in which different accounts send payments is irrelevant, provided each account stays valid for every transaction, i.e., no double-spending and sufficient balance. As long as the nodes/validators are in agreement on the set of locally valid transactions that took place in the system, consensus on a total order is unnecessary.

FastSet extends this idea beyond payments to voting, auctioning, and basically to any type of verifiable statement, which we call claim. Moreover, it generalizes the property of commutativity on payments mentioned above to arbitrary state-effectful computations and introduces this generalization as the notion of weak independence.

Payment transactions as claims

Although FastSet is more than payments, in this section we will focus mostly on payment transactions. Payments are a special instance of a claim because a transaction is simply a claim on the change of account balance.

Like in blockchains, every FastSet account has a state (for example, a token balance) and is required to sign any claims it issues. These signatures allow validators to confirm both the authenticity and integrity of the claim.

A claim referring to a payment transaction would be a signature by $sender

which specifies $sender is transferring $value tokens to $recipient.

Node state

Nodes in FastSet maintain their own state, which is a consistent copy of the system’s state.

FastSet node state vs. Blockchain node state

For a sequence of claims waiting to be settled, the states of the FastSet nodes may diverge temporarily and get out of sync (at most) until the entire sequence is processed. This is in contrast to the blockchain approach, which requires the same transaction order on all nodes. This is also why in blockchains strong consistency is enforced and why in FastSet we can do away with eventual consistency consensus. But more on this later in the section.

Through their states, nodes in FastSet keep the balances of all the tokens in the system, but also the state of all clients and the global state of the protocol, such as the set of all the claims that were settled.

For simplicity, let’s just focus on particular claims which are token transfers, that is, the state of the system at a certain time is just the token balances corresponding to the various accounts:

s =

Nodes process the claims issued by the clients. However, two points are worth mentioning. The first is that only valid claims are processed and the second that the system’s (or individual node’s) state may change after a claim is processed. Let’s take a look at each point and see what it means.

1. A claim may or may not be valid in a given state.

Valid payment transaction

A payment transaction is valid if the sender’s balance is enough and the value it sends is positive.

We use a color palette to distinguish valid claims (green) from invalid ones (red).

In the state above, claim is invalid as balance(Charlie) < 60, while claim is valid because balance(Alice) ≥ 80.

2. Processing a claim can (and usually does) change the state.

Processing valid claim in state s (left) gives state s’ (right):

In this new state s', balances of both Alice and Bob are updated—Alice’s decreases by 80, while Bob’s increases by the same amount.

Processing a claim may lead to a state change. However, a state change may also lead to validity status change for other claims.

3. An invalid claim becomes valid.

Initially, Charlie’s balance would not allow him to send 60 tokens to Dave (balance(Charlie) < 60). However, Bob’s valid transaction increased Charlie’s balance, so now Charlie can perform his payment to Dave.

4. A valid claim becomes invalid.

In the initial state, Alice has enough balance to perform either of the transactions (balance(Alice) ≥ 45 and balance(Alice) ≥ 80), hence both claims are valid. After performing the payment to Bob, Alice does not have enough tokens to perform the transaction to Charlie too, and the claim for this payment becomes invalid.

Double-spending attack prevention

In FastSet transactions can be executed in any order, with a minor caveat. They need to originate from different accounts. Thus, the double-spending attack is prevented by enforcing transactions from the same account to be processed sequentially in the original order they have been issued. In order to enforce this, signatures are required to carry a nonce which increases with every signature the user creates.

If Alice tries to cheat and use the same nonce for both claims above, some validators could process the payment to Bob first (as in the diagram above) and validate it, others could process the payment to Charlie first and validate it. Half of validators processed a transfer, the other half the other and thus could never reach a quorum. In this case Alice’s account gets stuck. This is an adequate behavior, albeit different from blockchains, because Alice attempted to cheat. An honest user would never try to send two messages using the same nonce.

Any order and weak independence

We said that, in FastSet, the claims from different accounts may be processed in a different order and that we can achieve strong eventual consistency if the claims are weakly independent. But what does it mean for two claims to be weakly independent?

Intuitively, the weak independence of payments by different clients says that the overall state of the system will be the same independently of the order in which they are processed, provided that the initial state of the system allows for each payment to be independently made.

We would like to stress that although we give the intuition for weak independence of claims as payment transactions, weak independence is a general concept covering all the other verifiable statements one can settle in FastSet.

The diagram in Figure 2 depicting weak independence of claims c₁ and c₂ says the following: Suppose that both c₁ and c₂ are valid in initial state s. If we process any of these claims in s, the other claim will continue to be valid in the subsequent state, meaning c₂ will be valid in s₁ and c₁ will be valid in s₂. Moreover, processing the remaining claims from the states they are valid into (c₂ from s₁ and c₁ from s₂) leads to the same final state s’. Or, simply put, processing both claims in any order leads to the same final state.

Example 1 (Weak independence): Let’s see what this means by having a look at a concrete example. Claims and are weakly independent in state s below:

s =

Let’s prove that.

First, both claims are valid in state s, as balance(Alice) ≥ 80 and balance(Dave) ≥ 20:

Now, processing the claims in either order leads to the same final state:

While this is a proof by example, a general proof would follow a similar reasoning.

Weak independence general proof Take two claims originating from different accounts a₁ and a₂⟨transfer(b₁, v₁)⟩a₁ and ⟨transfer(b₂, v₂)⟩a₂and let’s prove they are weakly independent.

If both are valid claims, then v₁ > 0 and balance(a₁) >= v₁ and, respectively, v₂ > 0 and balance(a₂) >= v₂. We have to prove that the balances of a₁, a₂, b₁, and b₂ are, respectively, the same no matter in which order the two transfer claims are processed.

We distinguish several cases, depending on whether b₁ and b₂are equal or not, or if any of them or both are equal to any of a₁or a₂.

b₁ and b₂ are distinct and also distinct from a₁ and a₂.

Then in both cases the balances are clearly the same: a₁- v₁, a₂- v₂, b₁+ v₁, b₂+ v₂. This case is a generalization of the example we have presented above.

b₁ = b₂ = b and are different from a₁ and a₂.

Then the balances are also the same: a₁- v₁, a₂- v₂, and b + v₁+ v₂.

b₁ = a₂ and b₂ are distinct.

Then the balances are also the same: a₁- v₁, a₂- v₂+ v₁, and b₂+ v₂.

b₁ = a₂ and b₂ = a₁.

Then the balances are the same, too: a₁- v₁+ v₂, a₂- v₂+ v₁.

b₁ = b₂ = a₂.

Then the balances are: a₁- v₁, a₂+ v₁.

The remaining cases are similar. Consequently, the two claims satisfy the weak independence requirement that guarantees its determinism no matter how the transfer claim blocks by different accounts are permuted. Because the (atomic) addition and subtraction operations on integers are commutative, an even stronger property holds: the individual claims in different blocks can also be further interleaved. This gives validators the freedom to maximize the parallelism and thus the throughput of token transfers.

Example 2 (Vacuous weak independence): Recall the example from before with the invalid claim becoming valid:

Weak independence holds vacuously in this case. Recall that weak independence requires both claims to be valid in the current state, and then if they are processed independently from the same state, the claim not processed in one state will continue to be valid in the subsequent state. Then, the final state will be the same in both cases. In this example, the payment claim from Charlie to Dave is not valid in the initial state, so it satisfies the weak independence of any claim vacuously.

Vacuous truth

In mathematical logic, a vacuously true statement is a conditional statement in which the antecedent cannot be satisfied.

Strong eventual consistency

FastSet ensures the correctness of the protocol, including its node/validator transaction processing determinism, whenever the weak independence property holds. More specifically, in FastSet, we achieve strong eventual consistency whenever weak independence holds.

Basically, strong eventual consistency is a generalization of weak independence to claim sequences of arbitrary length, not just 2, where one sequence is an interleaving of the other. This means that both sequences contain the same claims, but in different order.

For example, two interleaving equivalent claim sequences are γ and γ' below:

γ =

γ' =

They contain the same payment transactions, but the order they should be processed in differs, with the exception of the payment transfers of Alice, which are in the same order in which they were initiated in both sequences.

Assuming the current state of the system to be state s specified above, processing the two sequences of transactions γ and γ' leads to the following two series of node state change:

As you can see in Figures 3a and 3b, the intermediate states are different, as the transactions are processed in different sequences. However, the initial and final states are the same. And this is what strong eventual consistency is about, whenever the claims they process are weakly independent, nodes eventually converge to the same global state.

For FastSet, this means that if two different nodes/validators process the same claim sequences for the same clients, then they end up in the same state regardless of how the claim sequences were interleaved. That is, from the collective perspective of the clients, validators behave deterministically and do not diverge. Or put differently, they are in “consensus”.

In the diagram above, the sequences of colored stripes represent two different sequences of the same set of transactions to be processed by two nodes (depicted as cubes) in FastSet, initially in the same state.

While the intermediate states of the individual nodes are out of sync as the sequence of transactions is processed, eventually, the states become again in sync, or achieve consensus, once they all process their last transaction in the sequence. In their final states, the nodes will have processed the same set of transactions, albeit in different order.

A more detailed and formal explanation of weak independence you can find in our whitepaper on FastSet.

PreviousCore Concepts NextFastSet Protocol

Last updated 6 days ago

Was this helpful?