Script State from Lamport Signatures

The final six months or so have seen a number of proposals for enhancements to Bitcoin Script: CAT, 64-bit arithmetic, in addition to some older concepts (CTV) and far-future concepts (Chialisp and Simplicity). This exercise has largely overshadowed some revolutionary modifications in our understanding of the prevailing Bitcoin Script, modifications which kind the idea of BitVM however which can additionally kind the idea of different, equally-exciting enhancements.

This text tries to summarize and manage analysis into Script by different folks. I make no declare to originality or authorship of something described right here.

Bitcoin Script

As many readers are conscious, Bitcoin Script is a straightforward programming language embedded within the Bitcoin blockchain, which is used to regulate beneath what situations cash could transfer. By far the commonest use of Script is to easily examine a signature with a single signature verification key. Although Bitcoin addresses have modified all through the years, each type of handle has supported this use of script in a first-class method: signing keys could be encoded immediately into Bitcoin addresses, and wallets know find out how to increase these keys into full packages that examine signatures on these keys.

Script can do many extra issues: it could actually examine hash preimages, examine relative and absolute timelocks, and it could actually do some easy reasoning to mix these checks in numerous methods. That is the premise behind Miniscript: we are able to generalize the notion of increasing a key right into a Script to the notion of increasing an arbitrarily-large set of signing situations right into a Script.

Script can technically do much more than this: it could actually add and subtract 32-bit numbers, it could actually hash information and examine the hash values for equality, and it could actually rearrange and manipulate a “stack” of values in numerous attention-grabbing methods. Nevertheless, Script has many limitations: it lacks opcodes to do easy arithmetic equivalent to multiplication, it’s (practically) incapable of reasoning about objects bigger than 32 bits, and it has (practically) no capability to introspect transaction information. The latter limitation is why covenant assist seems to require a softfork, and the previous limitations are why Script, till lately, was by no means used to compute any “attention-grabbing” capabilities.

For instance, to multiply two 16-bit numbers in Script, utilizing solely the addition and subtraction opcodes that Script gives, it is advisable break them into bits (by requiring the bits be offered as witness information, then doubling and including them to reconstruct the unique quantity) after which implementing multiplication when it comes to additions of those bits. The ensuing code would contain a number of dozen opcodes for a single multiplication.

Previous to Taproot, Script had a man-made restrict of 201 opcodes per program, and with particular person multiplications taking greater than 1 / 4 of this funds, it was unimaginable to do a lot of something. After Taproot, the 201-opcode restrict was eliminated, however each opcode nonetheless takes up a witness byte, that means that multi-kilobyte packages could be prohibitively costly for abnormal wallets to placed on the blockchain.

And with out transaction introspection, it is not even clear what giant computations could be good for.

In spite of everything, if you are able to do arbitrary computations on arbitrary values, however these values aren’t tied to transaction information on the blockchain, how can these computations add helpful semantics to Bitcoin?

Lamport Signatures

Lamport signatures have been invented in 1979 by Leslie Lamport — although they’re insecure with out trendy cryptographic hash capabilities, which didn’t exist till the Nineteen Nineties — and are one of many few cryptographic objects from that period which endure to at the present time. Their lasting reputation comes from their simplicity and the truth that their safety in opposition to quantum computer systems relies upon solely on sufficiently-random-looking hash capabilities, in contrast to extra trendy and environment friendly proposals for quantum-secure signature schemes.

Nevertheless, Lamport signatures include two giant drawbacks: (1) they’re horribly inefficient, taking a number of kilobytes of information for each keys and signatures, and (2) they’re single-use. Which means if a person indicators a couple of message, it turns into attainable for a third social gathering to forge extra messages, making all signatures successfully nugatory. This may be mitigated, for instance by having your “public key” be a Merkle tree of tens of millions of single-use keys, however this stretches the bounds of practicality..

These limitations have made Lamport signatures fashionable as a “backup signature scheme” for Bitcoin in case of a quantum computing breakthrough, however have prevented their use as main signatures in any extensively deployed system.

The best way they work is easy: assume that the message to be signed is 256 bits broad. This may be assured by first operating an arbitrary-length message via the SHA256 hash operate. The person’s public key consists of 256 pairs of hashes – 512 in whole. To signal a message, they reveal a preimage for one hash in every pair, selecting the preimage to disclose primarily based on a little bit of the message.

A signature verifier re-hashes the message and preimages to make sure they’re all constant.

In 2021, Jeremy Rubin posted a weblog put up claiming that Bitcoin Script can immediately confirm Lamport signatures on 33-bit values. His mechanism was very intelligent. Bitcoin Script doesn’t have an opcode to learn particular person bits from a quantity, nor can it do the bitwise operations wanted to assemble a quantity from bits. However Script does have an opcode so as to add two numbers, and by including completely different numbers the place every has solely a single bit set, it’s attainable to bitwise-construct or bitwise-deconstruct a quantity.

Utilizing this perception, Rubin checks a Lamport signature, encoded as a collection of hash preimages, as follows:

1. For every preimage, compute its hash and evaluate it in opposition to a pair of goal values (comprising the general public key) embedded within the Script.
2. If the hash matches the primary member of the pair, it is a 0-bit; the script does nothing on this case.
3. If it matches the second member, it is a 1-bit. On this case, add a specific energy of two to an accumulator.
4. (If it matches neither member, the signature is invalid and the script ought to abort.)

The ultimate worth of the accumulator will then equal the signed quantity, constructed by including powers of two corresponding to every 1 bit in its binary growth.

Already that is attention-grabbing: it signifies that for sure sorts of “oracle signature” functions, you may immediately examine signatures in Bitcoin Script, assuming you could have an oracle that’s prepared to provide one-time Lamport signatures on particular occasions and that you already know a Lamport public key prematurely for every occasion. For instance, a particular sports activities match consequence could be encoded as a single bit. The actual rating could be encoded utilizing just a few bits. A selected timestamp can (in all probability) be encoded in 33 bits. And so forth. And naturally, by checking a number of Lamport signatures, you may successfully get signatures on as many bits as you need.

With out the flexibility to signal giant messages, you may’t get a signature on transaction information and due to this fact can’t get covenants. (Or can we?)

BitVM and Equivocation

This weblog put up by Jeremy Rubin was largely thought of to be a curiosity on the time and was misplaced amongst bigger discussions round his OP_CTV proposal and covenants. In December of 2023, it was not directly cited within the OP_CAT BIP by Ethan Heilman and Armin Sabouri, which gave it a contemporary viewers amongst individuals who have been pondering in another way about Bitcoin Script.

Individuals have been pondering in another way as a result of in October 2023, simply two months prior, Robin Linus had introduced on the mailing checklist his undertaking BitVM—an formidable undertaking to do arbitrary computations in Bitcoin Script by splitting packages throughout a number of transactions. The person transactions every do a single easy operation, with outputs from one operation hooked to inputs of one other by way of a hash-preimage-revealing development that appears suspiciously much like a Lamport signature.

The trick right here is that if a person Lamport-signs a number of messages with the identical key, the end result can be two hashes in the identical hash-pair whose preimages are each recognized. That is simple to examine for in Script, which can be utilized to assemble a “slashing transaction” that may take cash from a person in the event that they do that. Such a slashing transaction would then grow to be legitimate precisely within the case {that a} person publicly signed two messages with the identical key. Slashing transactions are used inside multi-transaction protocols to punish customers who misbehave, sometimes by forfeiting a bond that they need to put up forward of time.

So these Lamport signatures, slightly than merely shedding safety when they’re used greater than as soon as, could be configured to actively punish a person who indicators a number of occasions. This has apparent functions for an oracle signature the place a signer is meant to attest to precisely one consequence of a real-life occasion; we wish to disincentivize such a signer from claiming that e.g. each groups gained a specific sports activities match. However that is an much more highly effective concept than it appears.

Within the cryptographic literature, when a celebration reveals two values for one thing that’s presupposed to be distinctive, that is referred to as equivocation. We are able to consider a slashing transaction as an anti-equivocation measure, as a result of it punishes any signer who produces signatures on the identical key with the identical message.

Then our Lamport signature with anti-equivocation development has the impact of mapping public keys to particular and immutable values. In different phrases, now we have a worldwide key-value retailer accessible from Script, with the curious property that every entry within the world retailer could be set by a particular individual (the one that is aware of the preimages for that key), however can solely be set as soon as all the time. This key-value retailer can also be accessible from any Bitcoin transaction (or a transaction on any blockchain, actually) no matter its connection to different transactions.

This key-value retailer has on the order of two^256 entries, most of which aren’t accessible since no one is aware of the preimages to their keys, so whereas it’s a “world key-value retailer” shared by each attainable program utilizing this Lamport signature development, it can’t replenish and there’s no danger that information from one program may unintentionally clobber information from one other, or {that a} worth which needs to be set by one person is perhaps set by one other. Neither is the key-value retailer truly saved wherever in its entirety.

BitVM and its variants use this truth to tie the output of 1 operation to the enter of the subsequent: a given program could be break up into a protracted collection of fundamental operations, for instance opcodes within the RISC-V instruction set, and every of those fundamental operations could be applied by a self-contained Script program which seems up the operation’s inputs and outputs within the key-value retailer, checks that they’re associated appropriately, and one way or the other punishes the person if not.

The whole BitVM system is way more sophisticated than this: for every program, it carves out an addressable reminiscence house from the key-value retailer; every operation must lookup its inputs and outputs from this reminiscence house; every operation wants to trace a program counter and different state past its inputs and outputs; and the entire thing is tied along with interactive protocols and timber of unconfirmed transactions to make sure than slashing penalties are appropriately enforced and that even a single incorrect step in a multi-billion-step program could be zeroed-in-on and punished. However this text just isn’t about BitVM and we won’t discover this.

Interlude: Small Script and Large Script

We take a second to remind the reader that Script can solely do non-trivial computations on values which can be 32 bits broad or smaller. Such values are “scriptnums” and Script has many opcodes to control them by deciphering them as signed integers or boolean values, typically as each.

Utilizing BitVM or the same mechanism to separate Script packages throughout a number of transactions, you are able to do arbitrary computations in Small Script, from ZKP verification to proof-of-work checking to quantity factoring.

Values which can be bigger than 32 bits can solely be manipulated by a small set of narrow-purpose opcodes: they are often hashed, interpreted as public keys or signatures to examine a transaction signature, their dimension in bytes could be computed, and they are often moved across the stack as opaque blobs. The one “actual” general-purpose computation that may be performed on them is a examine for equality, which by itself gives little or no worth.

We describe the world of 32-bit values as “Small Script”, which is computationally expressive however can’t entry transaction information in any method. The world of bigger values we name “Large Script”, and might entry transaction information via the CHECKSIG opcode. Additionally it is attainable to examine hash preimages in Large Script, and that is important to implementing Lamport signatures, however that is just about the one factor you are able to do in Large Script.

It’s unimaginable to usefully bridge the 2 worlds: you may hash a Small worth to get a Large worth, however you can not then study something in regards to the Large worth that you simply did not already know. And you should utilize the SIZE opcode to study the dimensions of a Large worth, but when this worth represents a hash, public key or signature, then its dimension is mounted so that you study nothing new. (Though previous to Taproot, signatures had a variable dimension, and it’s attainable you could extract transaction info from a suitably constrained CHECKSIG-passing transaction.)

All this to remind the reader that, whereas this new Script performance is thrilling, it gives loads of computation expressivity with out the flexibility to examine transaction information, and due to this fact can’t be used for vaults or different covenant functions.

The CAT opcode gives a mechanism to bridge the 2 Scripts, which is why CAT is ample to supply covenants. That is additionally why there are such a lot of methods wherein Script “virtually” helps covenants, or wherein non-covenant-related proposals like CAT end up to allow covenants: just about any opcode that takes Small values and outputs Large ones, or vice-versa, can be utilized to feed Large Script transaction information right into a Small Script normal program. Even a sufficiently unhealthy break of the SHA1 opcode might in all probability be used as a bridge, as a result of then you would do “computations” on Large values by deciphering them as SHA1 hashes and discovering Small preimages for them.

Interlude: Wormholes

Truly, there’s a method you could get covenants in Small Script, assuming you could have sufficient computational energy. By going “exterior” of Script, customers can validate the Bitcoin blockchain itself, in addition to the transaction that accommodates the Script (it must keep away from immediately encoding its personal information to keep away from being infinitely-sized, however this may be performed by oblique means; see the subsequent part for extra particulars), after which impose further constraints on the transaction by imposing these constraints on this internally-validated “view” of itself.

This concept might enable the creation of some restricted covenant performance, however it is very important do not forget that appropriate entry to the key-value retailer, which is important to be able to break up giant computations, just isn’t immediately enforced. As a substitute, some further mechanism must be imposed to implement slashing penalties on incorrect entry. This enormously complicates the implementation of vault-like covenants whose performance relies on sure spending patterns truly being unimaginable, not simply disincentivized.

Tic-Tac-Toe

So far now we have talked in regards to the anti-equivocation function of Lamport signatures, and the way this can be utilized to impact a “world key-value retailer” in Bitcoin Script, which in flip can be utilized to move information between Script packages and to separate giant computations into many impartial components. However there’s one other attention-grabbing and maybe shocking side of Lamport signatures, which is that they permit committing to a singular worth in a script with out that worth affecting the TXID of its transaction.

This has two penalties: one is that we are able to commit information in a transaction with out affecting its TXID, that means that we are able to doubtlessly change parameters inside a Script program with out invalidating chains of unconfirmed transactions. The opposite is that we are able to commit information with out affecting the signature hash, that means that customers can “pre-sign” a transaction with out first realizing all of its information.

(By the way in which, these properties apply to any signature scheme, offered there’s a examine to punish the signing of a number of values. What’s attention-grabbing about Lamport signatures is that we are able to use them in Bitcoin as we speak.)

The flexibility to place information right into a Script program with out affecting the TXID of the contained transaction opens the door to constructions wherein a program is ready to check with its personal code (for instance, by injecting the TXID itself into this system, which is a hash of all transaction information together with this system). That is referred to as Quining, and can be utilized to allow delegation and to create recursive covenants. This capability is the motivation behind the disconnect combinator in Simplicity. Nevertheless, since we are able to solely validate Lamport signatures in Small Script, which excludes objects as giant as txids, it seems that there’s at the moment nothing we are able to do in that course. Nevertheless, nothing is stopping us from emulating non-recursive covenants with related methods.

Let’s describe an instance resulting from supertestnet on Github.

Contemplate the sport tic-tac-toe, performed between two individuals who take turns marking a three-by-three grid. The principles are easy: no participant could mark an already-marked sq., and if both participant marks three squares in a row (horizontally, vertically, or diagonally) then they win. Think about that these gamers wish to play this recreation on-chain, representing every flip by a transaction.

In fact, in parallel to those transactions, they might have a single “glad path” transaction the place each events would simply signal cash over to the winner in order that in the event that they agreed on the occasions of the sport, they wouldn’t truly must publish the person turns! However it’s necessary to additionally assemble the complete recreation transcript in order that within the case of disputes, the blockchain can mediate.

One method they could take is to mannequin the sport as a collection of pre-signed transactions, which every require a signature from each gamers. The primary participant has 9 attainable strikes. So the second participant would signal all 9, and the primary participant would signal whichever one they needed to take. Then for every of the 9 attainable strikes, the second participant has eight strikes; so the primary participant indicators all eight, and the second participant picks one to signal, and so forth.

It seems that this doesn’t fairly work – as a result of both participant may refuse to signal a specific transfer, there isn’t a strategy to assign blame within the case that the sport stalls out, and due to this fact no incentive for the shedding participant to finish the sport. To stop this case, every participant should signal all of his counterparty’s strikes earlier than the sport begins. Then a participant can solely refuse to signal his personal strikes, and this may be simply disincentivized by including timelocked forfeit situations to the transactions.

As a substitute for having every participant signal the opposite gamers’ strikes, a trusted third social gathering may very well be enlisted to pre-sign every transfer. However the end result is similar: each attainable collection of transactions have to be signed. For the tic-tac-toe recreation, there are 255168 paths for a complete of 549945 pre-signed transactions. That is pushing the bounds of practicality, and it’s clear that such a technique won’t generalize to nontrivial video games. For chess, for instance, these values are bounded under by the Shannon quantity, which is 10^120.

The explanation that now we have such a big blow-up is that we’re distinguishing between strikes by distinct transactions which every have to be arrange earlier than the sport has began.

Nevertheless, utilizing Lamport signatures, we are able to do a lot better:

• Every recreation of tic-tac-toe has (at most) 9 strikes,
• Every of which is a transition between two board states, which can be sufficiently small to be Lamport-signed,
• And every transition should obey guidelines that are easy sufficient to moderately encode inside Script.

We are able to due to this fact method the sport in another way: every participant generates a Lamport public key with which to signal the sport state after every of their strikes (so the primary participant generates 5 keys, the second participant 4). They then generate a collection of 9 transactions whose output taptrees have three branches:

1. A “abnormal transfer” department, consisting of

• An abnormal signature from each gamers;
• A Lamport signature on the earlier recreation state from the suitable participant,

• A Lamport signature on the subsequent recreation state from the opposite participant,
• And a examine, applied in Script, that the two-game states are appropriately associated (they differ by precisely one authorized transfer by the proper participant).

1. A “win situation”, consisting of

• An abnormal signature from each gamers;
• A Lamport signature on the earlier ga)me state from the suitable participant,
• A examine, applied in Script, that this participant has gained the sport.

1. A “timeout” situation, consisting of

• An abnormal signature from each gamers;
• A relative timelock that has expired.

The ultimate transaction, rather than an “abnormal transfer” department, has a “draw” department, since if all strikes have accomplished and not using a win, there isn’t a winner and presumably any cash at stake ought to return to their unique house owners.

As earlier than, every participant pre-signs all transactions, of which there are 27, together with “win situation” transactions (which ship all of the cash to the successful participant), “timeout situation” transactions (which ship all of the cash to the participant who didn’t outing) and “draw situation”.

And by the way in which, whereas the foundations of Chess are a good bit extra sophisticated, and the board state could require a number of 32-bit values to characterize, and there could also be greater than 9 strikes, it’s nonetheless possible to hold out precisely the identical development.

Transaction Bushes

Within the earlier instance, we took nice benefit of the truth that the foundations of tic-tac-toe could be embedded in Script itself, that means {that a} person can’t usefully signal an invalid recreation state. (In the event that they signal an invalid transfer, the transaction representing the transfer can be invalid, and the transactions representing all future strikes may even be invalid as a result of they rely on it. So all of the attacker could have achieved is leaking a part of his Lamport signing key, permitting the opposite participant to doubtlessly forge strikes on his behalf.

We additionally took benefit of the truth that our full protocol was not very lengthy: at most 9 strikes. Which means if one participant refuses to finish the sport, or completes the sport however won’t acknowledge the end result, it’s affordable to publish your entire recreation transcript on-chain as a recourse. For a lot of video games that is ample.

It’s out of scope of this weblog put up, however there are numerous methods we are able to play with this mannequin: checking single-party computations as a “recreation” between a prover and verifier, outsourcing one or each roles, combining a number of steps into single transactions with giant taptrees, changing the linear transcript with a binary seek for invalid steps, and so forth. These methods kind the idea for BitVM, BitVM 2, BitVMX, and so forth.

Utilizing such methods, we are able to scale back the price of current protocols that rely on timber of unsigned transactions. A basic 2017 Bitcoin paper by Bentov and Miller argues that stateful protocols within the UTXO mannequin all the time endure an exponential blowup relative to analogous protocols within the account mannequin, e.g. on Ethereum. Utilizing Lamport signatures as a worldwide key-value retailer, we are able to partially refute this paper. However we’re out of house and might want to discover this in our subsequent put up!

Acknowledgments

I want to thank Robin Linus and Ethan Heilman for reviewing an early draft of this put up.

It is a visitor put up by Andrew Poelstra. Opinions expressed are completely their very own and don’t essentially replicate these of BTC Inc or Bitcoin Journal.