Introduction
Blockchains are strongly consistent distributed systems in which account holders cooperate by making transactions. Transactions are intents of actions, which need to be given a state to execute in order to materialize. Transactions are signed by their owners and broadcast to a decentralized network of nodes, sometimes called miners or validators. The nodes play dice in order to identify a proposer for the next block (or sequence) of transactions. Nodes replicate the global state and follow a consensus protocol by which the proposed block is processed by all the nodes, thus materializing all the transactions in the block and each node updating its state accordingly. In the end, the transactions submitted to the blockchain are totally ordered, and thus so are the states in between.
Strongly consistent distributed systems [12, 10, 14, 17] "behave like one computer", which is the desirable property for blockchains, but are notorious for higher latency and lower performance and scalability — they require coordination and communication between nodes to maintain consistency. At the other extreme stands the actor model [11, 1], aiming at highly parallel computing and massive concurrency. Actors are the basic building blocks of concurrent computation and communicate only through messages. In response to a message it receives, an actor can modify its own private state, create more actors together with code governing their behavior, and send messages to other actors.
There is no doubt that blockchains play an important role in modern finance. Also, blockchains have demonstrated, in our view irreversibly, that decentralization is not only possible in the world of digital assets, but also very much desirable. Not only decentralization addresses the single point of failure, corruption, and censorship vulnerabilities, but equally importantly, through blockchains, it has lead to the Web3 philosophy and movement: users own their digital assets, from money to diplomas and medical records to pictures and messages, and they and only they can transfer them and decide who has access to what. However, a major overhaul is needed in order to scale blockchains and achieve the level of high performance and low cost required by recent applications. For example, few blockchains can consistently perform more than 1,000 transactions per second (TPS) and it takes seconds, sometimes minutes, to settle a transaction. Metaphorically, because of the total order on transactions that they enforce by their nature, blockchains require the entire universe to squeeze through a narrow pipe. Completely unrelated transactions are required to stay in line and wait to be sequenced in some order that the blockchain must globally choose when forming its next block. This is clearly not scalable, even if all transactions are initiated by humans. The situation is in fact much worse, because AI and AI agents doing transactions on humans' behalf are already here to stay and they require a payment system able to perform millions of TPS, most of which micro-transactions whose cost is expected to be negligible, in the order of fractions of a cent. Blockchains cannot do this. A massively parallel decentralized infrastructure for payments in particular and computing in general is required.
A series of papers before 2008 culminating with Bitcoin [16], have incrementally built a belief that a total order on transactions ought to be required in any distributed/decentralized payment system in order to avoid the infamous double spending attack: an account sending two concurrent transactions attempting to spend the same coin with two different recipients. A total ordering enforced on transaction settlement indeed solves the double spending problem, but is it really necessary? Recent works starting around 2019 [8, 9, 3] propose a radically different way to approach the problem, a truly concurrent approach where payments can be generated and settled in different orders by different nodes without breaking the semantics of payments. The key insight of these works is that the order in which an account receives payments is irrelevant, and so is the order in which different accounts send payments — provided each account stays valid: no double spending and sufficient balance. That is, as far 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. We believe that this apparently simple and innocent observation marks a crucial breakthrough moment in decentralized finance. A moment where the tyranny of sequentiality is abolished and the door is open to innovations that will lead to the next generation of decentralized, yet truly concurrent, safe, and scalable infrastructure for digital assets.
Inspired by this recent work on weaker variants of consensus in the context of cryptocurrencies [8, 9, 3], as well as by the unbounded concurrent computing promise of the actor model [11, 1], in this paper we propose FastSet, a general-purpose distributed computing protocol that generalizes the payment system protocol FastPay [3]. FastSet performs nearly embarrassingly parallel settlement of arbitrary verifiable claims, including verifiable computations in arbitrary programming languages. Specifically, FastSet allows a set of clients to settle verifiable claims consistently, using a set of validators. Clients broadcast their claims to all validators. Validators validate the received claims and replicate the system state based on the order in which they receive the claims. Importantly, similarly to FastPay but in sharp contrast to blockchains, the FastSet validators do not need to communicate with each other, nor directly achieve consensus on any values or orders or blocks or computations.
What makes the problem difficult is that claims can have side effects on the validators' states. However, if claims issued by different clients are weakly independent, a notion that generalizes the property of commutativity on payments [8, 9, 3] discussed above to arbitrary state-effectful computations, then the validators' states will remain (strongly eventually) consistent in spite of the different orders in which they receive and process the claims.
Like in blockchains, FastSet accounts have a state (e.g., a balance) and are required to sign any claims they issue. We present the protocol in Section 2, requiring only abstract notions of state, claim, and claim validity and effect. How claims are generated, e.g., randomly by users or programmatically by contracts, is irrelevant for the core protocol and its correctness discussed in Section 3.4. However, to make it practical, implementations of FastSet have to offer specific types of claims and specific ways to generate them. In Section 4 we propose an actor-inspired language for generating claims, which we call the FastSet Language and abbreviate SETL1, and pronounce "settle". Some accounts are controlled by users, others by SETL programs (or scripts, or contracts). The difference is that the user-controlled accounts are free to issue any claims, including ones that create new accounts and interact with them, while the contract-based accounts can only issue claims as prescribed by their SETL program/script/contract.
Like in the actor model, accounts are regarded as actors that communicate only with the actors they know about, and can create new accounts/actors and then communicate with them. Since validators maintain replicas of the global system state, all the actors/accounts are also replicated on all validators. This should not be regarded as a deviation from the underlying thesis of the actor model, where each actor is meant to be a separate process interacting concurrently with the other actors, but rather as a high-availability high-resilience decentralized implementation of an actor system. Moreover, the actor model is particularly suitable for a language like SETL for two additional reasons: (1) each validator can itself be a high-performance concurrent system, which receives and processes potentially millions of claims per second, so SETL must be a high-performance concurrent programming language; and (2) since each validator receives the claims in different orders, yet all of them (strongly eventually consistently) are expected to replicate the same state, SETL concurrent programs must be easy to reason about, in particular to prove their determinism.
The rest of the paper is organized as follows. Section 2 defines the FastSet Protocol. Section 3 proves the correctness of the protocol. Section 4 proposes, through examples that are commonly encountered in Web3, an informal design of SETL, a contract scripting language for FastSet. Section 5 concludes the paper. This paper also has two appendix sections. Appendix A elaborates on the basic concepts that help the reader to better understand the examples in Section 4. Appendix B discusses some possible extensions of the examples.
We recommend the reader to first read Section 2, to understand how the FastSet protocol works. Then readers can take one of the following two paths. The theoretically inclined reader can dive into the mathematical formalization and the proofs of correctness of FastSet in Section 3. The reader interested in applications that can take advantage of FastSet's massively parallel architecture can skim Section 3 and skip directly to Section 4. If some examples are difficult to understand, the reader can check out the explanations in Appendix A.
1Not to be confused with the SET Language (https://en.wikipedia.org/wiki/SETL), invented in the late 1960s, based on the mathematical theory of sets.
