Script State from Lamport Signatures

The last six months or so have seen several proposals for improvements to Bitcoin Script: CAT, 64-bit arithmetic, as well as some older ideas (CTV) and far-future ideas (Chialisp and Simplicity). This activity has largely overshadowed some revolutionary changes in our understanding of the existing Bitcoin Script, changes which form the basis of BitVM but which may also form the basis of other, equally-exciting improvements.

This article tries to summarize and organize research into Script by other people. I make no claim to originality or authorship of anything described here.

Bitcoin Script

As many readers are aware, Bitcoin Script is a simple programming language embedded in the Bitcoin blockchain, which is used to control under what conditions coins may move. By far the most common use of Script is to simply check a signature with a single signature verification key. Though Bitcoin addresses have changed throughout the years, every form of address has supported this use of script in a first-class way: signing keys can be encoded directly into Bitcoin addresses, and wallets know how to expand these keys into full programs that check signatures on those keys.

Script can do many more things: it can check hash preimages, check relative and absolute timelocks, and it can do some simple reasoning to combine these checks in various ways. This is the premise behind Miniscript: we can generalize the notion of expanding a key into a Script to the notion of expanding an arbitrarily-large set of signing conditions into a Script.

Script can technically do even more than this: it can add and subtract 32-bit numbers, it can hash data and check the hash values for equality, and it can rearrange and manipulate a "stack" of values in various interesting ways. However, Script has many limitations: it lacks opcodes to do simple arithmetic such as multiplication, it is (nearly) incapable of reasoning about objects larger than 32 bits, and it has (nearly) no ability to introspect transaction data. The latter limitation is why covenant support appears to require a softfork, and the former limitations are why Script, until recently, was never used to compute any "interesting" functions.

For example, to multiply two 16-bit numbers in Script, using only the addition and subtraction opcodes that Script provides, you need to break them into bits (by requiring the bits be provided as witness data, then doubling and adding them to reconstruct the original number) and then implementing multiplication in terms of additions of these bits. The resulting code would involve several dozen opcodes for a single multiplication.

Prior to Taproot, Script had an artificial limit of 201 opcodes per program, and with individual multiplications taking more than a quarter of this budget, it was impossible to do much of anything. After Taproot, the 201-opcode limit was removed, but every opcode still takes up a witness byte, meaning that multi-kilobyte programs would be prohibitively expensive for ordinary wallets to put on the blockchain.

And without transaction introspection, it isn't even clear what large computations would be good for.

After all, if you can do arbitrary computations on arbitrary values, but those values aren't tied to transaction data on the blockchain, how can those computations add useful semantics to Bitcoin?

Lamport Signatures

Lamport signatures were invented in 1979 by Leslie Lamport -- though they are insecure without modern cryptographic hash functions, which did not exist until the 1990s -- and are one of the few cryptographic objects from that era which endure to this day. Their lasting popularity comes from their simplicity and the fact that their security against quantum computers depends only on sufficiently-random-looking hash functions, unlike more modern and efficient proposals for quantum-secure signature schemes.

However, Lamport signatures come with two large drawbacks: (1) they are horribly inefficient, taking multiple kilobytes of data for both keys and signatures, and (2) they are single-use. This means that if a user signs more than one message, it becomes possible for a 3rd party to forge more messages, making all signatures effectively worthless. This can be mitigated, for example by having your public key be a Merkle tree of millions of single-use keys, but this stretches the bounds of practicality..

These limitations have made Lamport signatures popular as a "backup signature scheme" for Bitcoin in case of a quantum computing breakthrough, but have prevented their use as primary signatures in any widely deployed system.

The way they work is simple: assume that the message to be signed is 256 bits wide. This can be assured by first running an arbitrary-length message through the SHA256 hash function. The user's public key consists of 256 pairs of hashes 512 in total. To sign a message, they reveal a preimage for one hash in each pair, choosing the preimage to reveal based on a bit of the message.

A signature verifier re-hashes the message and preimages to ensure they are all consistent.

In 2021, Jeremy Rubin posted a blog post claiming that Bitcoin Script can directly verify Lamport signatures on 33-bit values. His mechanism was very clever. Bitcoin Script does not have an opcode to read individual bits from a number, nor can it do the bitwise operations needed to construct a number from bits. But Script does have an opcode to add two numbers, and by adding different numbers where each has only a single bit set, it is possible to bitwise-construct or bitwise-deconstruct a number.

Using this insight, Rubin checks a Lamport signature, encoded as a series of hash preimages, as follows:

For each preimage, compute its hash and compare it against a pair of target values (comprising the public key) embedded in the Script.
If the hash matches the first member of the pair, this is a 0-bit; the script does nothing in this case.
If it matches the second member, this is a 1-bit. In this case, add a particular power of 2 to an accumulator.
(If it matches neither member, the signature is invalid and the script should abort.)

The final value of the accumulator will then equal the signed number, constructed by adding powers of two corresponding to each 1 bit in its binary expansion.

Already this is interesting: it means that for certain kinds of "oracle signature" applications, you can directly check signatures in Bitcoin Script, assuming you have an oracle that is willing to produce one-time Lamport signatures on specific events and that you know a Lamport public key in advance for each event. For example, a specific sports match outcome can be encoded as a single bit. The particular score can be encoded using a few bits. A particular timestamp can (probably) be encoded in 33 bits. And so on. And of course, by checking multiple Lamport signatures, you can effectively get signatures on as many bits as you want.

Without the ability to sign large messages, you can't get a signature on transaction data and therefore cant get covenants. (Or can we?)

BitVM and Equivocation

This blog post by Jeremy Rubin was largely considered to be a curiosity at the time and was lost among larger discussions around his OP_CTV proposal and covenants. In December of 2023, it was indirectly cited in the OP_CAT BIP by Ethan Heilman and Armin Sabouri, which gave it a fresh audience among people who were thinking differently about Bitcoin Script.

People were thinking differently because in October 2023, just two months prior, Robin Linus had announced on the mailing list his project BitVMan ambitious project to do arbitrary computations in Bitcoin Script by splitting programs across multiple transactions. The individual transactions each do a single simple operation, with outputs from one operation hooked to inputs of another via a hash-preimage-revealing construction that looks suspiciously similar to a Lamport signature.

The trick here is that if a user Lamport-signs multiple messages with the same key, the result will be two hashes in the same hash-pair whose preimages are both known. This is easy to check for in Script, which can be used to construct a "slashing transaction" that will take coins from a user if they do this. Such a slashing transaction would then become valid exactly in the case that a user publicly signed two messages with the same key. Slashing transactions are used within multi-transaction protocols to punish users who misbehave, typically by forfeiting a bond that they must post ahead of time.

So these Lamport signatures, rather than merely losing security when they are used more than once, can be configured to actively punish a user who signs multiple times. This has obvious applications for an oracle signature where a signer is supposed to attest to exactly one outcome of a real-life event; we want to disincentivize such a signer from claiming that e.g. both teams won a particular sports match. But this is an even more powerful idea than it seems.

In the cryptographic literature, when a party reveals two values for something that is supposed to be unique, this is called equivocation. We can think of a slashing transaction as an anti-equivocation measure, because it punishes any signer who produces signatures on the same key with the same message.

Then our Lamport signature with anti-equivocation construction has the effect of mapping public keys to specific and immutable values. In other words, we have a global key-value store accessible from Script, with the curious property that each entry in the global store can be set by a specific person (the person who knows the preimages for that key), but can only be set once for all time. This key-value store is also accessible from any Bitcoin transaction (or a transaction on any blockchain, really) regardless of its connection to other transactions.

This key-value store has on the order of 2^256 entries, most of which are not accessible since nobody knows the preimages to their keys, so while it is a "global key-value store" shared by every possible program using this Lamport signature construction, it cannot fill up and there is no risk that data from one program might accidentally clobber data from another, or that a value which should be set by one user might be set by another. Nor is the key-value store actually stored anywhere in its entirety.

BitVM and its variants use this fact to tie the output of one operation to the input of the next: a given program can be split into a long series of basic operations, for example opcodes in the RISC-V instruction set, and each of these basic operations can be implemented by a self-contained Script program which looks up the operation's inputs and outputs in the key-value store, checks that they are related correctly, and somehow punishes the user if not.

The complete BitVM system is much more complicated than this: for each program, it carves out an addressable memory space from the key-value store; each operation needs to look up its inputs and outputs from this memory space; each operation needs to track a program counter and other state beyond its inputs and outputs; and the whole thing is tied together with interactive protocols and trees of unconfirmed transactions to ensure than slashing penalties are correctly enforced and that even a single incorrect step in a multi-billion-step program can be zeroed-in-on and punished. But this article is not about BitVM and we will not explore this.

Interlude: Small Script and Big Script

We take a moment to remind the reader that Script can only do non-trivial computations on values that are 32 bits wide or smaller. Such values are "scriptnums" and Script has many opcodes to manipulate them by interpreting them as signed integers or boolean values, sometimes as both.

Using BitVM or a similar mechanism to split Script programs across multiple transactions, you can do arbitrary computations in Small Script, from ZKP verification to proof-of-work checking to number factoring.

Values that are larger than 32 bits can only be manipulated by a small set of narrow-purpose opcodes: they can be hashed, interpreted as public keys or signatures to check a transaction signature, their size in bytes can be computed, and they can be moved around the stack as opaque blobs. The only "real" general-purpose computation that can be done on them is a check for equality, which by itself provides very little value.

We describe the world of 32-bit values as "Small Script", which is computationally expressive but cannot access transaction data in any way. The world of larger values we call "Big Script", and can access transaction data through the CHECKSIG opcode. It is also possible to check hash preimages in Big Script, and this is essential to implementing Lamport signatures, but that's pretty much the only thing you can do in Big Script.

It is impossible to usefully bridge the two worlds: you can hash a Small value to get a Big value, but you cannot then learn anything about the Big value that you didn't already know. And you can use the SIZE opcode to learn the size of a Big value, but if this value represents a hash, public key or signature, then its size is fixed so you learn nothing new. (Although prior to Taproot, signatures had a variable size, and it is possible that you can extract transaction information from a suitably constrained CHECKSIG-passing transaction.)

All this to remind the reader that, while this new Script functionality is exciting, it provides a lot of computation expressivity without the ability to inspect transaction data, and therefore cannot be used for vaults or other covenant applications.

The CAT opcode provides a mechanism to bridge the two Scripts, which is why CAT is sufficient to provide covenants. This is also why there are so many ways in which Script "almost" supports covenants, or in which non-covenant-related proposals like CAT turn out to enable covenants: pretty much any opcode that takes Small values and outputs Big ones, or vice-versa, can be used to feed Big Script transaction data into a Small Script general program. Even a sufficiently bad break of the SHA1 opcode could probably be used as a bridge, because then you could do "computations" on Big values by interpreting them as SHA1 hashes and finding Small preimages for them.

Interlude: Wormholes

Actually, there is a way that you can get covenants in Small Script, assuming you have enough computational power. By going "outside" of Script, users can validate the Bitcoin blockchain itself, as well as the transaction that contains the Script (it needs to avoid directly encoding its own data to avoid being infinitely-sized, but this can be done by indirect means; see the next section for more details), and then impose additional constraints on the transaction by imposing those constraints on this internally-validated "view" of itself.

This idea could allow the creation of some limited covenant functionality, but it is important to remember that correct access to the key-value store, which is necessary in order to split large computations, is not directly enforced. Instead, some additional mechanism needs to be imposed to enforce slashing penalties on incorrect access. This greatly complicates the implementation of vault-like covenants whose functionality depends on certain spending patterns actually being impossible, not just disincentivized.

Tic-Tac-Toe

Thus far we have talked about the anti-equivocation feature of Lamport signatures, and how this can be used to effect a "global key-value store" in Bitcoin Script, which in turn can be used to pass data between Script programs and to split large computations into many independent parts. But there is another interesting and perhaps surprising aspect of Lamport signatures, which is that they allow committing to a unique value in a script without that value affecting the TXID of its transaction.

This has two consequences: one is that we can commit data in a transaction without affecting its TXID, meaning that we can potentially change parameters within a Script program without invalidating chains of unconfirmed transactions. The other is that we can commit data without affecting the signature hash, meaning that users can "pre-sign" a transaction without first knowing all of its data.

(By the way, these properties apply to any signature scheme, provided there is a check to punish the signing of multiple values. What is interesting about Lamport signatures is that we can use them in Bitcoin today.)

The ability to put data into a Script program without affecting the TXID of the contained transaction opens the door to constructions in which a program is able to refer to its own code (for example, by injecting the TXID itself into the program, which is a hash of all transaction data including the program). This is called Quining, and can be used to enable delegation and to create recursive covenants. This ability is the motivation behind the disconnect combinator in Simplicity. However, since we can only validate Lamport signatures in Small Script, which excludes objects as large as txids, it appears that there is currently nothing we can do in that direction. However, nothing is stopping us from emulating non-recursive covenants with similar tricks.

Let's describe an example due to supertestnet on Github.

Consider the game tic-tac-toe, played between two people who take turns marking a three-by-three grid. The rules are simple: no player may mark an already-marked square, and if either player marks three squares in a row (horizontally, vertically, or diagonally) then they win. Imagine that these players want to play this game on-chain, representing each turn by a transaction.

Of course, in parallel to these transactions, they would have a single happy path transaction where both parties would just sign coins over to the winner so that if they agreed on the events of the game, they wouldnt actually need to publish the individual turns! But its important to also construct the full game transcript so that in the case of disputes, the blockchain can mediate.

One approach they might take is to model the game as a series of pre-signed transactions, which each require a signature from both players. The first player has nine possible moves. So the second player would sign all nine, and the first player would sign whichever one they wanted to take. Then for each of the nine possible moves, the second player has eight moves; so the first player signs all eight, and the second player picks one to sign, and so on.

It turns out that this doesnt quite work because either player might refuse to sign a particular move, there is no way to assign blame in the case that the game stalls out, and therefore no incentive for the losing player to complete the game. To prevent this situation, each player must sign all of his counterpartys moves before the game starts. Then a player can only refuse to sign his own moves, and this can be easily disincentivized by adding timelocked forfeit conditions to the transactions.

As an alternative to having each player sign the other players moves, a trusted third party could be enlisted to pre-sign each move. But the result is the same: every possible series of transactions must be signed. For the tic-tac-toe game, there are 255168 paths for a total of 549945 pre-signed transactions. This is pushing the bounds of practicality, and its clear that such a strategy will not generalize to nontrivial games. For chess, for example, these values are bounded below by the Shannon number, which is 10^120.

The reason that we have such a large blow-up is that we are distinguishing between moves by distinct transactions which each must be set up before the game has started.

However, using Lamport signatures, we can do much better:

Each game of tic-tac-toe has (at most) nine moves,
Each of which is a transition between two board states, that are small enough to be Lamport-signed,
And each transition must obey rules which are simple enough to reasonably encode within Script.

We can therefore approach the game differently: each player generates a Lamport public key with which to sign the game state after each of their moves (so the first player generates 5 keys, the second player 4). They then generate a series of 9 transactions whose output taptrees have three branches:

A ordinary move branch, consisting of

An ordinary signature from both players;
A Lamport signature on the previous game state from the appropriate player,

A Lamport signature on the next game state from the other player,
And a check, implemented in Script, that the two-game states are correctly related (they differ by exactly one legal move by the correct player).

A win condition, consisting of

An ordinary signature from both players;
A Lamport signature on the previous ga)me state from the appropriate player,
A check, implemented in Script, that this player has won the game.

A timeout condition, consisting of

An ordinary signature from both players;
A relative timelock that has expired.

The final transaction, in place of an ordinary move branch, has a draw branch, since if all moves have completed without a win, there is no winner and presumably any coins at stake should go back to their original owners.

As before, each player pre-signs all transactions, of which there are 27, including win condition transactions (which send all the coins to the winning player), timeout condition transactions (which send all the coins to the player who didnt time out) and draw condition.

[insert picture of transaction tree, which is 9 transactions in a row, with each one branching to timeout and win, and the final one also ending in draw]

And by the way, while the rules of Chess are a fair bit more complicated, and the board state may require multiple 32-bit values to represent, and there may be more than 9 moves, it is still feasible to carry out exactly the same construction.

Transaction Trees

In the previous example, we took great advantage of the fact that the rules of tic-tac-toe can be embedded in Script itself, meaning that a user cannot usefully sign an invalid game state. (If they sign an invalid move, the transaction representing the move will be invalid, and the transactions representing all future moves will also be invalid because they depend on it. So all the attacker will have accomplished is leaking part of his Lamport signing key, allowing the other player to potentially forge moves on his behalf.

We also took advantage of the fact that our complete protocol was not very long: at most 9 moves. This means that if one player refuses to complete the game, or completes the game but will not acknowledge the result, it is reasonable to publish the entire game transcript on-chain as a recourse. For many games this is sufficient.

It is out of scope of this blog post, but there are many tricks we can play with this model: checking single-party computations as a game between a prover and verifier, outsourcing one or both roles, combining multiple steps into single transactions with large taptrees, replacing the linear transcript with a binary search for invalid steps, and so on. These tricks form the basis for BitVM, BitVM 2, BitVMX, and so forth.

Using such tricks, we can reduce the cost of existing protocols that depend on trees of unsigned transactions. A classic 2017 Bitcoin paper by Bentov and Miller argues that stateful protocols in the UTXO model always suffer an exponential blowup relative to analogous protocols in the account model, e.g. on Ethereum. Using Lamport signatures as a global key-value store, we can partially refute this paper. But we are out of space and will need to explore this in our next post!

Acknowledgments

I would like to thank Robin Linus and Ethan Heilman for reviewing an early draft of this post.

This is a guest post by Andrew Poelstra. Opinions expressed are entirely their own and do not necessarily reflect those of BTC Inc or Bitcoin Magazine.

Text source: Bitcoin Magazine: Bitcoin News, Articles, Charts,

Technical