From Data Types to Programs

Programs and Addresses

Delving Into Simplicity

Programs and Addresses

Simplicity Programs
Commitment Merkle Root
Addresses
Witness Expressions
Witness Values
Type Inference
Conclusion

In the previous chapter we described two side effects used in Simplicity: the Failure effect, which determines a program's success or failure, and the Reader effect, which provides access to the transaction environment. Now we turn to the practical question: what exactly is a Simplicity program, and how does it become an address on the blockchain?

Simplicity Programs

A Simplicity program is defined as a Simplicity expression of type 𝟙 ⊢ 𝟙. This type signature means the program takes no meaningful input (just the unit value) and produces no meaningful output (just the unit value). The Reader effect captures the transaction environment input, while the Failure effect indicates success or failure. These effects handle I/O rather than Simplicity types themselves.

Commitment Merkle Root

Rather than storing complete programs on-chain, Bitcoin employs commitments — a practice extending from Pay-to-Script-Hash (P2SH). Simplicity uses a Commitment Merkle Root (CMR).

Each combinator receives a SHA-256 tag derived from the pattern: Simplicity␟Commitment␟[identifier], where ␟ represents ASCII code 31 (the unit separator).

Each tag is the SHA-256 hash of the corresponding pre-image string listed below:

Combinator	Tag pre-image (ASCII string)
`iden`	`Simplicity␟Commitment␟iden`
`unit`	`Simplicity␟Commitment␟unit`
`comp`	`Simplicity␟Commitment␟comp`
`pair`	`Simplicity␟Commitment␟pair`
`case`	`Simplicity␟Commitment␟case`
`take`	`Simplicity␟Commitment␟take`
`drop`	`Simplicity␟Commitment␟drop`
`injl`	`Simplicity␟Commitment␟injl`
`injr`	`Simplicity␟Commitment␟injr`

A Simplicity expression is then recursively hashed into a 256-bit CMR by computing a tagged SHA-256 midstate for each combinator together with the CMRs of its arguments (write #ᶜ(e) for the CMR of expression e, and ∥ for byte concatenation):

Combinator	CMR rule
`iden`	`#ᶜ(iden) = SHA-256-midstate(tag_iden ∥ tag_iden)`
`unit`	`#ᶜ(unit) = SHA-256-midstate(tag_unit ∥ tag_unit)`
`comp f g`	`#ᶜ(comp f g) = SHA-256-midstate(tag_comp ∥ tag_comp ∥ #ᶜ(f) ∥ #ᶜ(g))`
`pair f g`	`#ᶜ(pair f g) = SHA-256-midstate(tag_pair ∥ tag_pair ∥ #ᶜ(f) ∥ #ᶜ(g))`
`case f g`	`#ᶜ(case f g) = SHA-256-midstate(tag_case ∥ tag_case ∥ #ᶜ(f) ∥ #ᶜ(g))`
`take f`	`#ᶜ(take f) = SHA-256-midstate(tag_take ∥ tag_take ∥ 32·0x00 ∥ #ᶜ(f))`
`drop f`	`#ᶜ(drop f) = SHA-256-midstate(tag_drop ∥ tag_drop ∥ 32·0x00 ∥ #ᶜ(f))`
`injl f`	`#ᶜ(injl f) = SHA-256-midstate(tag_injl ∥ tag_injl ∥ 32·0x00 ∥ #ᶜ(f))`
`injr f`	`#ᶜ(injr f) = SHA-256-midstate(tag_injr ∥ tag_injr ∥ 32·0x00 ∥ #ᶜ(f))`

Binary combinators (comp, pair, case) concatenate the CMRs of both children; unary combinators (take, drop, injl, injr) concatenate their single child's CMR after 32 bytes of 0x00 padding; and the nullary leaves (iden, unit) hash their tag alone. Two conventions keep this cheap to compute: SHA-256 midstates are used so that each expression requires at most one call to the SHA-256 compression function (assuming the midstate up to the constant tags is precomputed), and the one-argument constructors prefix their argument with 32 bytes of 0x00 padding, which allows for a little extra precomputation for implementations that want it.

For the unit combinator — a nullary constructor with no argument sub-expressions — this rule specialises to #ᶜ(unit) = SHA-256-midstate(tag_unit ∥ tag_unit), where tag_unit = SHA-256(Simplicity␟Commitment␟unit) (the tag is fed in twice). The resulting CMR for the trivial unit program is:

0xc40a10263f7436b4160acbef1c36fba4be4d95df181a968afeab5eac247adff7

Critically, the CMR does not commit to the types of Simplicity expressions, relying instead on type inference during redemption.

Addresses

Addresses employ BIP-0341's Taproot mechanism with CMRs committed under TapLeaf version 0xbe. The process involves:

Computing a TapLeaf tagged hash combining the version byte, CMR length, and CMR itself
Tweaking an internal public key (using a NUMS point when no key-spend path is desired)
Converting to bech32m format
Adding appropriate checksums

When no key-spend path is desired, the internal public key is set to a NUMS ("Nothing-Up-My-Sleeve") point: a curve point deliberately chosen so that nobody knows its discrete logarithm — in other words, a point with no corresponding private key. Because no one can ever produce a signature for it, the key-spend path is provably unusable, and the output can be spent only through the committed Simplicity script path. In a real application, this NUMS point should be randomized as recommended by BIP-0341, so that outputs with no key-spend path are indistinguishable from ordinary Taproot outputs (a privacy benefit).

From Simplicity to Address

Let's walk through the whole derivation for the simplest program possible: unit : 𝟙 ⊢ 𝟙, a no-op that always succeeds.

1. Combinator tag. First compute the unit tag:

tag_unit = SHA-256(Simplicity␟Commitment␟unit)
         = 0xd723083cff3c75e29f296707ecf2750338f100591c86e0c71717f807ff3cf69d

2. CMR. Feed the tag in twice to obtain the program's CMR:

CMR = #ᶜ(unit) = SHA-256-midstate(tag_unit ∥ tag_unit)
    = 0xc40a10263f7436b4160acbef1c36fba4be4d95df181a968afeab5eac247adff7

3. TapLeaf hash. Prefix the CMR with Simplicity's TapLeaf version 0xbe and the CMR length 0x20 (32 bytes), then take the Elements TapLeaf tagged hash (a tagged hash is hash_str(x) = SHA-256(SHA-256(str) ∥ SHA-256(str) ∥ x)):

hash_TapLeaf/elements(0xbe ∥ 0x20 ∥ CMR)
  = 0x44cc38311ec7e5dfb7b573baf38449496ecd334eb5509cfed1b4fd30da8dd41c

With only this one leaf there are no TapBranches, so this hash is already the TapTree root.

4. TapTweak. Since we want no key-spend path, we use the BIP-0341 NUMS point as the internal key and tweak it with the TapTree root:

internal_pk = 0x50929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0
t = hash_TapTweak/elements(internal_pk ∥ 0x44cc38311ec7e5dfb7b573baf38449496ecd334eb5509cfed1b4fd30da8dd41c)
  = 0xb3bef172389b0937d7e5a8b15cfa41e776777f13f2f659cb06220a6ff0658285

5. Output key. Tweak the internal key on the curve, output_pk = lift_x(internal_pk) ⊕ t·G (the elliptic-curve arithmetic is summarized here), giving the x-only output key 0x2cb0c20acd7340b4d4b65f6a60e2888d0d64e3267261f3b3cf7290e5af3f9e09.

6. Bech32m address. Encode the x-only output key, prefix a p (the SegWit v1 witness-version character), add the Liquid-testnet human-readable prefix tex1, and append the Bech32m checksum. The final address is:

tex1p9jcvyzkdwdqtf49kta4xpc5g35xkfcexwfsl8v70w2gwttelncyshxjk56

That was a lot of work — but much of it is mandated by Taproot itself, not by Simplicity.

Witness Expressions

A new combinator type addresses the absence of input to Simplicity programs: the witness expression. The witness combinator permits signature data and other witness material to be integrated into programs.

      w : B
-----------------
witness w : A ⊢ B

The witness expression's semantics is straightforward: it ignores its input and simply returns the value w (which may be of any Simplicity type), i.e. ⟦witness w⟧(a) = w. This adds no new expressiveness — by the completeness theorem, Simplicity can already build any such constant function (recall the scribe macro from the previous chapters). The point of the witness combinator lies entirely in its CMR: the value w is excluded from the expression's CMR, so the address can be computed before w is known, and w is supplied at redemption time.

This design choice supports pruning — unexecuted conditional branches needn't be revealed on-chain, including their associated witness expressions. When a branch is pruned, the verifier only needs the CMR of the pruned subtree, not its actual content.

Witness Values

It may seem like a limitation that a witness expression can hold only a value, and not a more general Simplicity expression. But programs for UTXO-based blockchains are executed only once. There is no need to pass a whole sub-expression into a witness node: the user can simply run that sub-expression themselves, off-chain, and transcribe its output into the witness value to obtain the very same result.

(Later in this course we will meet the disconnect combinator, which behaves much like a witness expression that does take an entire Simplicity expression as its argument.)

An alternative design would feed all witness data in as an argument to the top-level Simplicity program. Witness expressions are preferred for two reasons. First, pruning: unexecuted branches of case expressions are never revealed on-chain, and any witness expressions inside those branches are pruned away along with them. Second, locality: witness expressions let us place each witness value exactly where it is used, instead of threading it down from the program's top-level input.

Type Inference

Since CMRs don't commit to types, the type system is reconstructed during redemption. Simplicity's type inference algorithm determines the minimal types for each subexpression based on the combinator structure. More precisely, inference computes the principal (most general) type of every subexpression; any type variables that remain free are then instantiated to the unit type 𝟙, which yields a unique, minimal type for the program.

Conclusion

In this chapter we established that Simplicity programs are expressions of type 𝟙 ⊢ 𝟙, explained how Commitment Merkle Roots are constructed from tagged SHA-256 hashes of each combinator, and showed how CMRs are turned into on-chain addresses via BIP-0341 Taproot. We introduced witness expressions as the mechanism for providing signature data and other inputs at spending time without committing to their values at address creation time.

Quiz

scr4033.3

1/5

Why are witness values excluded from the Commitment Merkle Root (CMR)?