Delving Simplicity Part Ⅰ: Three Fundamental Ways of Combining Computations

Unlike conventional programming, where code can be executed multiple times on various inputs, Bitcoin transactions necessitate compact programs that are executed once per input, shared by all. The primary focus is on validating witness data cost-effectively rather than proving it, which inherently requires a different approach to language design. This includes the necessity for programs to be compact due to the high cost of block space, the elimination of unexecuted branches to prevent their appearance on the blockchain, and the absence of dynamic memory allocation during execution. Static analysis substitutes for runtime "gas" computation, ensuring that execution model details do not impact consensus.

The core philosophy behind Simplicity involves exploring how basic operations can be combined to create new functionality within this constrained environment. Starting with a set of primitive operations capable of performing computations, data processing, and signature verification, the challenge lies in devising methods to integrate these operations into more complex forms. Three fundamental composition techniques have been identified: sequential, parallel, and conditional composition. Sequential composition combines operations wherein the output of one serves as the input for another, creating a linear execution path. Parallel composition allows two operations to process the same input independently, with their results combined at the end. Conditional composition offers a choice between two operations based on a tagged union input, executing only one path based on the tag's value.

These composition methods have parallels in Bitcoin Script, demonstrating how programming constructs can be adapted to blockchain requirements. Sequential composition mirrors the concatenation of routines in Bitcoin Script, allowing outputs from one routine to feed into another. Parallel composition is achieved through stack manipulation, enabling simultaneous operation execution. Conditional composition utilizes OP_IF to branch execution based on stack values, guiding the script down different paths based on input criteria.

Looking ahead, Simplicity aims to encapsulate these composition forms alongside additional combinators to support a wider range of operations. The goal is to establish a comprehensive language framework capable of expressing any finite computation within the constraints of blockchain technology. However, it notably excludes recursive composition to avoid unbounded recursion, aligning with Bitcoin Script's limitations and emphasizing predictable transaction costs through alternative mechanisms such as recursive covenants. This exclusion underscores Simplicity's design philosophy, focusing on efficiency, predictability, and the specific needs of blockchain-based applications.