We wanted to make bitcoin-dev aware of our recently published draft on how to create and spend covenants on Bitcoin using Tapscript. https://colliderscript.co/colliderscript.pdf
Our approach does not require soft forks and should work on Bitcoin as it is currently deployed. While creating these covenants is as easy as creating a transaction with P2WSH output, spending these covenants requires substantial computation and involves creating very large bitcoin transactions. Spending such a covenant requires ~2^86 hash calls to SHA-1 and RIPEMD-160. In comparison, mining a Bitcoin block at current difficulty requires ~2^78.3 hash calls to SHA256x2. Thus, spending such a covenant would require the same number of hash queries the entire Bitcoin network does in roughly ~33 hours. Such covenants could be created today, but spending them likely requires the creation of dedicated ASICs. While the computational costs limit the immediate applicability of our covenants, we are optimistic that future work can significantly improve these numbers. This approach is not a replacement for a covenant opcode because: 1. High computational cost: Our approach is likely to be many orders of magnitude more computationally expensive than a covenant opcode. 2. 4Mb transactions: Transaction size, computation cost trade-off exists that reduces the computational costs of these covenants by increasing the transaction size. Due to most of the cost being computational it is likely they always be just under 4MB in size even with efficiency gain. 4MB is the limit for valid transactions. Our approach is framed around covenants, but our approach enables arbitrary computation on Bitcoin transaction data. This arbitrary computation is bounded only by the circuit size we can pack into what is left of a 4Mb Bitcoin transaction after it contains all our necessary machinery. This means, for example, we can do Tapscript lamport signatures that sign the sighash of the spending transaction. One of the authors of our paper, Andrew Poelstra, proposes in the paper a very interesting use case for lamport signatures (Section 7.2) which I think is worth making the list aware of. Leveraging the fact that it is very cheap for users to write and deploy our covenants, it is only expensive to spend them, the following scheme is proposed. A user could create a covenant in a tapleaf whose spending condition requires a Lamport signature over spending transaction. While the resulting script will be very large, they can hide it in a Taproot leaf where it will never be serialized on-chain unless it is used. In the case of a “surprise quantum computer” which forces Bitcoin to suddenly disable all elliptic curve cryptography including taproot key spends, such users will still be able to spend their coins (though at enormous cost). If a large quantity of users do this, it may be possible for the Bitcoin chain to survive such an event, even if no better solution is found or deployed. Our Technique ==== We will now look at how our technique works by introducing the core problem we solve and then showing how by solving this problem we can enforce covenants. Let’s say you want to write a Bitcoin script that checks if 12345678abcdef00 and [12345678, abcdef00] are equivalent. That is, if you treated 12345678 and abcdef00as a single element would it be equal to 12345678abcdef00? If we had OP_CAT this would be easy: 12345678abcdef00 == CAT(12345678, abcdef00) We call checking if one element is the concatenation of a list of smaller elements, an equivalence check. We can ask is 12345678abcdef00 equivalent to [12345678, abcdef00]? In Bitcoin script, checking equivalence between a single big element and a list of small elements is quite challenging, below we will show how to do it. Before getting there we need to make a short digression first. It has been part of the lore for some time that Bitcoin script can perform arbitrary computation on inputs, so long as the inputs are encoded as a list of 32-bit stack elements. This uses opcodes like OP_ADD, OP_SUB, which only accept 32-bit inputs. We call functions written using 32-bit elements Small Script. People have built all sorts of things in Small Script, for instance you can compute Blake3 in Tapscript in a bitcoin output using only 45,000 opcodes (a.k.a. 45,000 bytes)! See https://bitvmx.org/knowledge/optimizing-algorithms-for-bitcoin-script Let’s say you have a Small Script implementation of SHA-1 where it treats [12345678, ABCDEF00] as an Small Script encoding of 12345678abcdef00. Does the following equivalence check work? OP_SHA1(12345678abcdef00) == smallscript_SHA1([12345678, ABCDEF00]) No, because OP_SHA1 will produce one big 160-bit (20 byte) stack element OP_SHA1(12345678abcdef00) → a12d9ee23d07317c2d2d6887fe955819bc2d24c5 whereas the Small Script implementation of SHA1 will produce 5 32-bit (4 Byte) stack elements smallscript_SHA1([12345678, abcdef00]) → [a12d9ee2, 3d07317c, 2d2d6887, fe955819, bc2d24c5] Checking if these are the same requires the equivalence check, the very thing we were trying to build. Ok, hear me out, what if you magically discovered a value X which was 32-bits in size and just so happened to collide with 12345678abcdef00. That is, SHA1(12345678abcdef00) == SHA1(X) is true AND 12345678abcdef00 != X AND Size(X) = 32-bits You could do an equivalence check for 12345678abcdef00 by doing the following: In Big Script Check OP_SHA1(12345678abcdef00) == OP_SHA1(X) In Small Script Check smallscript_SHA1([12345678, abcdef00]) == smallscript_SHA1(X) If both of these return true, then we decide 12345678abcdef00 is equivalent to [12345678, abcdef00]. Put more generally: Check OP_SHA1(A) == OP_SHA1(X) and Check smallscript_SHA1(B) == smallscript_SHA1(X) Now if A is equivalent to B, and X collides with A, then X will collide with B in Small Script because B is just the Small Script encoding of A. However if A is not equivalent to B then this implies a triple collision which is much more expensive to find: SHA1(A) = SHA1(X) = SHA1(B) where A != B, A!=X, B!=X Given the choice between two possibles for an A and B that pass the check: 1. A equivalent to B 2. A not actually equivalent to B requires a triple collision that is computationally infeasible We argue that 1 is much more likely. Ok, but as some of the cryptographers are now typing, if X is only 32-bits it is extremely unlikely to find an X that collides for any particular value. To exploit the birthday bound to find collisions with a 160-bit hash function you need the input to be >80-bit in size. Overcoming this problem is the last trick of the paper. We introduce the function dGen(w, t) which can take any length of input and that input can be read by Small Script and Big Script. dGen(w, t): y = SHA1(w) for b in t: If b == 0: y = SHA1(y) If b == 1: y = RIPEMD160(y) return y w is a 33-bit stack element, t is a series of 32-bit stack elements which we treat as a list of bits. For instance is w=312a123e, t=01101 dGen would return the value created by running SHA1(RIPEMD160(SHA1(SHA1(RIPEMD160(SHA1(312a123e)))))) dGen can be run using OP_SHA1 and OP_RIPEMD160 and can also be run in Small Script using Small Script implementations of SHA1 and RIPEMD160. Since both sides can use the same stack elements to compute the output it lets us build our equivalence check. We just need to find a (w, t) such that: OP_SHA1(A) == BigScript-dGen(w, t) // Big script dGen using OP_SHA1 and OP_RIPEMD160 SHA1(B) == SmallScript-dGen(w, t) // Small script dGen Finding (w,t) is the main computational expense of spending our covenant as our covenant depends on this equivalence check. That said finding collisions in 160-bit hash functions requires significantly less computation than the Bitcoin network regularly performs. See our paper for our collision algorithm and discussions of known weaknesses in SHA1. How do you turn this equivalence check into a covenant? Past work -- https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-i.html -- has shown that by structuring a Schnorr signature correctly, that Schnorr signature will be the hash of the spending transaction (see our paper for how we adapt this to our setting). At very high level our covenant works as follows: 1. Get sighash of spending transaction onto stack 2. Use equivalence check to show that small script encoded sighash is the same as the sighash we have on the stack 3. Open the sighash in small script by showing bytes pushed on stack by the spending transaction hash to sighash are bytes of the spending transaction. Now we have the bytes of the spending transaction on the stack. 4. Use Small Script to enforce covenant on the bytes of the spending transaction. See paper for full details. Thanks, Ethan -- You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BW2jyFoJAq9XrE9whQ7EZG4HRST01TucWHJtBhQiRTSNQ%40mail.gmail.com.
