* [bitcoindev] ColliderScript: Covenants in Bitcoin via 160-bit hash collisions
@ 2024-11-07 17:44 Ethan Heilman
2024-11-12 17:38 ` [bitcoindev] " Antoine Riard
0 siblings, 1 reply; 5+ messages in thread
From: Ethan Heilman @ 2024-11-07 17:44 UTC (permalink / raw)
To: Bitcoin Development Mailing List
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 bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BW2jyFoJAq9XrE9whQ7EZG4HRST01TucWHJtBhQiRTSNQ%40mail.gmail.com.
^ permalink raw reply [flat|nested] 5+ messages in thread* [bitcoindev] Re: ColliderScript: Covenants in Bitcoin via 160-bit hash collisions 2024-11-07 17:44 [bitcoindev] ColliderScript: Covenants in Bitcoin via 160-bit hash collisions Ethan Heilman @ 2024-11-12 17:38 ` Antoine Riard 2024-11-13 22:06 ` Ethan Heilman 0 siblings, 1 reply; 5+ messages in thread From: Antoine Riard @ 2024-11-12 17:38 UTC (permalink / raw) To: Bitcoin Development Mailing List [-- Attachment #1.1: Type: text/plain, Size: 14416 bytes --] Hi Ethan, Thanks you for this astute paper. The crux of the paper relies on the equivalence check, which in my understanding can be described as the following (correct me if the set of algorithms differs). On one side, we have our old good correct signatures on the stack. A signature is a commitment to the signature hash fields. This signature can be verified to be valid and it can be given to one of the 160-bits hash functions, i.e OP_SHA1 or OP_RIPEMD160. E.g: <<signature> <OP_DUP> <pubkey> <OP_CHECKSIG> <OP_SHA1>> Doing the Schnorr trick, a data-carrying transaction can be altered until its signature is equivalent to the SchnorrHash, by selecting accordingly that pubkey P and nonce R are equal to the generator. Those elements that the signature is well- composed are further checked by the small script "signature defragmentation" 32-bits integers opcodes. On the other side, we have the 32-bits integers opcodes that can be used to re-implement "bitcoin script natively-ish" cryptographic operations, e.g blake3. Giving the full script would be too lengthy, though hash functions are just (very) smart sequences of XORed seed, key, data that one can simulate easy in bitcoin script. E.g to flip one bit of data. E.g: <<1-bit input_a> <0x1> <OP_EQUAL> <OP_IF> <0x0> <OP_ELSE> <0x1> <OP_ENDIF>> So let's say we have some basic cryptographic operation like OP_SHA1 in small script (for p2tr tapscript spend the script size limit is the block size). If I'm understanding correctly, the goal of the equivalence check is to find a `y` such that `y <- h_big_script(s1)` and `y <- h_small_script(s2)` are logically equal. Once such `y` is found, the data-carrying transaction is grinded until s1 and s2 are equal. The hash `y` outcome for both `h_big_script` and `h_small_script` will be never compared themselves during the script execution, as we *cannot*. The former is a plain data push and the remainder an array of 32-bits script elements. Once the equivalence check has been done, the restrictions on the signature construction from the Schnorr trick can be checked, and then what covenant checks can be done in the remainder of the 4MB weight unit can be play out. E.g checking the spending transaction nAmount twice 32 bits are less than a given value. <<32-bits> <first digit amount> <OP_LESSTHAN> <32-bits> <second digit amount> <OP_LESSTHAN>> Withstanding the code proof that a OP_SHA1 or OP_RIPEMD160 fips-180-1 implem in small script effectively fit in the block size, I think the colliderscript equivalent check construction as presented can be sound, though I have few questions on the security model. 1) Let's say you have a 2 step smart contract as presented in Figure 4. The locking script is committed in a tapscript somewhere in the tree, and as such the collision `y` to found cannot be observed ahead of the spending. Once the script is revealed and before the transaction confirms every 10 block _in average_, an adversary with enormous computational resources, could come to find another collision (what I think you call a triple collision). While the s1 value, i.e the main data fields of the data-carrying transaction shouldn't be know ahead, for some use-cases they might very standards. E.g if you take a vault protocol, only the spent outpoint and pubkey might differs among vault instance belonging to different users (e.g everyone use same emergency or revaulting timelocks by default). So could a 160-bit hash collision attacker leverage some staticness of fields in bip341 sighash to lower the hardness under 2^109 ? As analyzed in appendix G. 2) The Schnorr trick assumes a signature where the pubkey and nonce are equivalent to the generator point. I think there could be some forgery of the covenanted transaction data, if an adversary can construct a transaction with still the same s1 and s2 to satisfy Big Script and Small Script. However, the transaction data would be a security downgrade from the smart contract protocol. E.g a nLocktime committing to a sooner chain tip than now, or even worst a malleated output pubkey. I think it's easy to fix if the schnorr pubkey, nonce are committed in the covenant locking script, and explicitly verified as such in the small script. This is pointed out in the section 2.4 about transaction grinding, but it's not discussed further afaict e.g in the section 7 on the security discussion. Best, Antoine ots hash: b47373e430c25a96e642ddad3cc330ee364f06c06f81a63238926a9ebbcb6795 Le jeudi 7 novembre 2024 à 17:48:03 UTC, Ethan Heilman a écrit : > 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 bitcoindev+unsubscribe@googlegroups•com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/fc031fe3-444c-446d-a5c1-f2d7a430b478n%40googlegroups.com. [-- Attachment #1.2: Type: text/html, Size: 16810 bytes --] ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [bitcoindev] Re: ColliderScript: Covenants in Bitcoin via 160-bit hash collisions 2024-11-12 17:38 ` [bitcoindev] " Antoine Riard @ 2024-11-13 22:06 ` Ethan Heilman 2024-11-25 3:42 ` Antoine Riard 0 siblings, 1 reply; 5+ messages in thread From: Ethan Heilman @ 2024-11-13 22:06 UTC (permalink / raw) To: Antoine Riard; +Cc: Bitcoin Development Mailing List > If I'm understanding correctly, the goal of the equivalence check is to find a `y` such that `y <- h_big_script(s1)` and `y <- h_small_script(s2)` are logically equal. Once such `y` is found, the data-carrying transaction is grinded until s1 and s2 are equal. You have the basic idea correct but I think you might be missing one piece of this (or perhaps you just simplified some details). For an honest party spending a covenant the s1 and s2 they generate are always equal. This means that y1 <- h_big_script(s1) and y2 <- h_small_script(s2) will generate the same y (y1 = y2). As you point out we can't compare y1 to y2 because they are encoded differently. > The hash `y` outcome for both `h_big_script` and `h_small_script` will be never compared themselves during the script execution, as we *cannot*. The former is a plain data push and the remainder an array of 32-bits script elements. To show equivalence between s1 and s2, we find a value d <-- dGen(w,t) which is equal to y. y1 <- h_big_script(s1) d1 <-- dGen_big_script(w, t) y1 == d1? y2 <- h_small_script(s2) d2 <-- dGen_small_script(w, t) y2 == d2? Since the inputs to dGen are 32-bit elements in both dGen_big_script and dGen_small_script, we know just DUP w and t for evaluation in small script and big script. Since dGen is deterministic it must be the case that dGen_big_script(w, t) always equals dGen_small_script(w, t). The trick is finding a w, t, s where dGen(w, t) = h(s) where s = s1 = s2. > 1). could a 160-bit hash collision attacker leverage some staticness of fields in bip341 sighash to lower the hardness under 2^109 ? As analyzed in appendix G. If I understand what you mean by staticness, the answer is no. Staticness should not provide any advantage to an attacker. In fact if the attacker does not sufficiently randomize the sighash on each query, they will have more difficulty, not less, finding collisions. > 2) The Schnorr trick assumes a signature where the pubkey and nonce are equivalent to the generator point. I think there could be some forgery of the covenanted transaction data, if an adversary can construct a transaction with still the same s1 and s2 to satisfy Big Script and Small Script. I'm not sure what you mean here. Can you provide a concrete example of this attack? Thanks, Ethan On Tue, Nov 12, 2024 at 12:41 PM Antoine Riard <antoine.riard@gmail•com> wrote: > > Hi Ethan, > > Thanks you for this astute paper. > > The crux of the paper relies on the equivalence check, which > in my understanding can be described as the following (correct > me if the set of algorithms differs). On one side, we have our > old good correct signatures on the stack. A signature is a > commitment to the signature hash fields. This signature can be > verified to be valid and it can be given to one of the 160-bits > hash functions, i.e OP_SHA1 or OP_RIPEMD160. > > E.g: <<signature> <OP_DUP> <pubkey> <OP_CHECKSIG> <OP_SHA1>> > > Doing the Schnorr trick, a data-carrying transaction can be > altered until its signature is equivalent to the SchnorrHash, > by selecting accordingly that pubkey P and nonce R are equal > to the generator. Those elements that the signature is well- > composed are further checked by the small script "signature > defragmentation" 32-bits integers opcodes. > > On the other side, we have the 32-bits integers opcodes > that can be used to re-implement "bitcoin script natively-ish" > cryptographic operations, e.g blake3. Giving the full script > would be too lengthy, though hash functions are just (very) > smart sequences of XORed seed, key, data that one can simulate > easy in bitcoin script. E.g to flip one bit of data. > > E.g: <<1-bit input_a> <0x1> <OP_EQUAL> <OP_IF> <0x0> <OP_ELSE> > <0x1> <OP_ENDIF>> > > So let's say we have some basic cryptographic operation > like OP_SHA1 in small script (for p2tr tapscript spend > the script size limit is the block size). If I'm understanding > correctly, the goal of the equivalence check is to find a `y` > such that `y <- h_big_script(s1)` and `y <- h_small_script(s2)` > are logically equal. Once such `y` is found, the data-carrying > transaction is grinded until s1 and s2 are equal. The hash `y` > outcome for both `h_big_script` and `h_small_script` will be > never compared themselves during the script execution, as > we *cannot*. The former is a plain data push and the remainder > an array of 32-bits script elements. > > Once the equivalence check has been done, the restrictions > on the signature construction from the Schnorr trick can > be checked, and then what covenant checks can be done in > the remainder of the 4MB weight unit can be play out. E.g > checking the spending transaction nAmount twice 32 bits > are less than a given value. > > <<32-bits> <first digit amount> <OP_LESSTHAN> > <32-bits> <second digit amount> <OP_LESSTHAN>> > > Withstanding the code proof that a OP_SHA1 or OP_RIPEMD160 > fips-180-1 implem in small script effectively fit in the > block size, I think the colliderscript equivalent check > construction as presented can be sound, though I have > few questions on the security model. > > 1) Let's say you have a 2 step smart contract as presented > in Figure 4. The locking script is committed in a tapscript > somewhere in the tree, and as such the collision `y` to found > cannot be observed ahead of the spending. > > Once the script is revealed and before the transaction confirms > every 10 block _in average_, an adversary with enormous > computational resources, could come to find another collision > (what I think you call a triple collision). While the s1 value, > i.e the main data fields of the data-carrying transaction > shouldn't be know ahead, for some use-cases they might very > standards. > > E.g if you take a vault protocol, only the spent outpoint and > pubkey might differs among vault instance belonging to different > users (e.g everyone use same emergency or revaulting timelocks by > default). So could a 160-bit hash collision attacker leverage > some staticness of fields in bip341 sighash to lower the > hardness under 2^109 ? As analyzed in appendix G. > > 2) The Schnorr trick assumes a signature where the pubkey and > nonce are equivalent to the generator point. I think there > could be some forgery of the covenanted transaction data, if > an adversary can construct a transaction with still the same > s1 and s2 to satisfy Big Script and Small Script. > > However, the transaction data would be a security downgrade > from the smart contract protocol. E.g a nLocktime committing > to a sooner chain tip than now, or even worst a malleated > output pubkey. I think it's easy to fix if the schnorr pubkey, > nonce are committed in the covenant locking script, and explicitly > verified as such in the small script. This is pointed out > in the section 2.4 about transaction grinding, but it's not > discussed further afaict e.g in the section 7 on the security > discussion. > > Best, > Antoine > ots hash: b47373e430c25a96e642ddad3cc330ee364f06c06f81a63238926a9ebbcb6795 > Le jeudi 7 novembre 2024 à 17:48:03 UTC, Ethan Heilman a écrit : >> >> 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 bitcoindev+unsubscribe@googlegroups•com. > To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/fc031fe3-444c-446d-a5c1-f2d7a430b478n%40googlegroups.com. -- 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 bitcoindev+unsubscribe@googlegroups•com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BV2YqRZhvNrgoxMbmaz%3Di94%3DhkAj%3D5HaTErKsOzYq6R4w%40mail.gmail.com. ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [bitcoindev] Re: ColliderScript: Covenants in Bitcoin via 160-bit hash collisions 2024-11-13 22:06 ` Ethan Heilman @ 2024-11-25 3:42 ` Antoine Riard 2024-11-27 22:37 ` Ethan Heilman 0 siblings, 1 reply; 5+ messages in thread From: Antoine Riard @ 2024-11-25 3:42 UTC (permalink / raw) To: Bitcoin Development Mailing List [-- Attachment #1.1: Type: text/plain, Size: 22461 bytes --] Hi Ethan, Thanks for the additional thoughts. > You have the basic idea correct but I think you might be missing one > piece of this (or perhaps you just simplified some details). Reading again the paper, my example and your new example, I don't understand yet all the details for sure, though on the fundamental trick, I believe we're saying more or less the same thing. If I'm understanding correctly, the trick is about proving that y(y1 = y2) both in Big Script and Small Script. > For an honest party spending a covenant the s1 and s2 they generate > are always equal. This means that y1 <- h_big_script(s1) and y2 <- > h_small_script(s2) will generate the same y (y1 = y2). As you point > out we can't compare y1 to y2 because they are encoded differently. Where s1 and s2 is the byte-for-byte equivalent spent transactions. For the security definition you're giving of the equivalence check, I don't think it matters that a party in a multi-party colliderscript-based vault protocol being honest. Either, the equivalence check is sound, and it's immutable once the UTXO's containing the lock script is confirmed in the chain, the covenant creator cannot himself generate not equal s1 and s2 _and_ successfully spend the coin. The lemma in terms of security model, I think for multi-party protocol, is that all the participant should verify the soundness of the y(y1 = y2), before to engage in the protocol (e.g staking more coins under the locking script or doing a swap). > we know just DUP w and t for evaluation in > small script and big script. Since dGen is deterministic it must be > the case that dGen_big_script(w, t) always equals dGen_small_script(w, > t). The trick is finding a w, t, s where dGen(w, t) = h(s) where s = > s1 = s2. Do we really need to OP_DUP w and t on the script stack ? Like isn't the s signature verified by Big Script is enough to then decompose the data payload in Small Script 32-bit inputs. I don't see where w, t are formally defined in the paper, though I browsed again the section 4. about realizing Bitcoin equivalence tester sets. There are just given as parameters, ||w|| = 33 and 35 <= || t || <= 75, and it doesn't say if there are data elements or transaction fields feeded in the signature digest. > If I understand what you mean by staticness, the answer is no. > Staticness should not provide any advantage to an attacker. In fact if > the attacker does not sufficiently randomize the sighash on each > query, they will have more difficulty, not less, finding collisions. Yes, for example for staticness if you take bip143 signature digest, the nVersion field is going to be the same for all the v2 transaction or v3 transaction. I see the introduction of the randomness p in the section 3 about equivalence check in bitcoin, though at the same time the idea is to find a semantically equivalent transaction to get s of tx(p). So for a given s signature, is there an existing efficient NP algorithm, that could find tx1 and tx2 for a same randomness p, where tx1 and tx2 are not semantically equivalent...? I think it's an interesting problem, and I don't see the paper is introducing a formal notion of semantically equivalent. > I'm not sure what you mean here. Can you provide a concrete example of > this attack? Let's recall the Schnorr signing algorithm, G^s = R + P^hash(R || m). Given m is the transaction data and G the generator, R the nonce and P the public key point, and all of same are equivalent, can I grind any of G, R or P to find 2 valid curve points for the same signature s where the curve point would correspond to 2 messages m1, m2 ? I think it's as hard as breaking the DL problem, though I'm not sure if they have been new cryptanalysis of the Schnorr trick, compared to existent proofs for Schnorr under the RO / GGM models. Best, Antoine ots hash: 27b5b4bdeea168147580d96769fda7bb395619435832a2e1d0aee0f03b22f27b Le mercredi 13 novembre 2024 à 22:23:29 UTC, Ethan Heilman a écrit : > > If I'm understanding correctly, the goal of the equivalence check is to > find a `y` such that `y <- h_big_script(s1)` and `y <- h_small_script(s2)` > are logically equal. Once such `y` is found, the data-carrying > transaction is grinded until s1 and s2 are equal. > > You have the basic idea correct but I think you might be missing one > piece of this (or perhaps you just simplified some details). > > For an honest party spending a covenant the s1 and s2 they generate > are always equal. This means that y1 <- h_big_script(s1) and y2 <- > h_small_script(s2) will generate the same y (y1 = y2). As you point > out we can't compare y1 to y2 because they are encoded differently. > > > The hash `y` outcome for both `h_big_script` and `h_small_script` will > be never compared themselves during the script execution, as we *cannot*. > The former is a plain data push and the remainder an array of 32-bits > script elements. > > To show equivalence between s1 and s2, we find a value d <-- dGen(w,t) > which is equal to y. > > y1 <- h_big_script(s1) > d1 <-- dGen_big_script(w, t) > y1 == d1? > > y2 <- h_small_script(s2) > d2 <-- dGen_small_script(w, t) > y2 == d2? > > Since the inputs to dGen are 32-bit elements in both dGen_big_script > and dGen_small_script, we know just DUP w and t for evaluation in > small script and big script. Since dGen is deterministic it must be > the case that dGen_big_script(w, t) always equals dGen_small_script(w, > t). The trick is finding a w, t, s where dGen(w, t) = h(s) where s = > s1 = s2. > > > 1). could a 160-bit hash collision attacker leverage some staticness of > fields in bip341 sighash to lower the hardness under 2^109 ? As analyzed in > appendix G. > > If I understand what you mean by staticness, the answer is no. > Staticness should not provide any advantage to an attacker. In fact if > the attacker does not sufficiently randomize the sighash on each > query, they will have more difficulty, not less, finding collisions. > > > 2) The Schnorr trick assumes a signature where the pubkey and nonce are > equivalent to the generator point. I think there could be some forgery of > the covenanted transaction data, if an adversary can construct a > transaction with still the same s1 and s2 to satisfy Big Script and Small > Script. > > I'm not sure what you mean here. Can you provide a concrete example of > this attack? > > Thanks, > Ethan > > On Tue, Nov 12, 2024 at 12:41 PM Antoine Riard <antoin...@gmail•com> > wrote: > > > > Hi Ethan, > > > > Thanks you for this astute paper. > > > > The crux of the paper relies on the equivalence check, which > > in my understanding can be described as the following (correct > > me if the set of algorithms differs). On one side, we have our > > old good correct signatures on the stack. A signature is a > > commitment to the signature hash fields. This signature can be > > verified to be valid and it can be given to one of the 160-bits > > hash functions, i.e OP_SHA1 or OP_RIPEMD160. > > > > E.g: <<signature> <OP_DUP> <pubkey> <OP_CHECKSIG> <OP_SHA1>> > > > > Doing the Schnorr trick, a data-carrying transaction can be > > altered until its signature is equivalent to the SchnorrHash, > > by selecting accordingly that pubkey P and nonce R are equal > > to the generator. Those elements that the signature is well- > > composed are further checked by the small script "signature > > defragmentation" 32-bits integers opcodes. > > > > On the other side, we have the 32-bits integers opcodes > > that can be used to re-implement "bitcoin script natively-ish" > > cryptographic operations, e.g blake3. Giving the full script > > would be too lengthy, though hash functions are just (very) > > smart sequences of XORed seed, key, data that one can simulate > > easy in bitcoin script. E.g to flip one bit of data. > > > > E.g: <<1-bit input_a> <0x1> <OP_EQUAL> <OP_IF> <0x0> <OP_ELSE> > > <0x1> <OP_ENDIF>> > > > > So let's say we have some basic cryptographic operation > > like OP_SHA1 in small script (for p2tr tapscript spend > > the script size limit is the block size). If I'm understanding > > correctly, the goal of the equivalence check is to find a `y` > > such that `y <- h_big_script(s1)` and `y <- h_small_script(s2)` > > are logically equal. Once such `y` is found, the data-carrying > > transaction is grinded until s1 and s2 are equal. The hash `y` > > outcome for both `h_big_script` and `h_small_script` will be > > never compared themselves during the script execution, as > > we *cannot*. The former is a plain data push and the remainder > > an array of 32-bits script elements. > > > > Once the equivalence check has been done, the restrictions > > on the signature construction from the Schnorr trick can > > be checked, and then what covenant checks can be done in > > the remainder of the 4MB weight unit can be play out. E.g > > checking the spending transaction nAmount twice 32 bits > > are less than a given value. > > > > <<32-bits> <first digit amount> <OP_LESSTHAN> > > <32-bits> <second digit amount> <OP_LESSTHAN>> > > > > Withstanding the code proof that a OP_SHA1 or OP_RIPEMD160 > > fips-180-1 implem in small script effectively fit in the > > block size, I think the colliderscript equivalent check > > construction as presented can be sound, though I have > > few questions on the security model. > > > > 1) Let's say you have a 2 step smart contract as presented > > in Figure 4. The locking script is committed in a tapscript > > somewhere in the tree, and as such the collision `y` to found > > cannot be observed ahead of the spending. > > > > Once the script is revealed and before the transaction confirms > > every 10 block _in average_, an adversary with enormous > > computational resources, could come to find another collision > > (what I think you call a triple collision). While the s1 value, > > i.e the main data fields of the data-carrying transaction > > shouldn't be know ahead, for some use-cases they might very > > standards. > > > > E.g if you take a vault protocol, only the spent outpoint and > > pubkey might differs among vault instance belonging to different > > users (e.g everyone use same emergency or revaulting timelocks by > > default). So could a 160-bit hash collision attacker leverage > > some staticness of fields in bip341 sighash to lower the > > hardness under 2^109 ? As analyzed in appendix G. > > > > 2) The Schnorr trick assumes a signature where the pubkey and > > nonce are equivalent to the generator point. I think there > > could be some forgery of the covenanted transaction data, if > > an adversary can construct a transaction with still the same > > s1 and s2 to satisfy Big Script and Small Script. > > > > However, the transaction data would be a security downgrade > > from the smart contract protocol. E.g a nLocktime committing > > to a sooner chain tip than now, or even worst a malleated > > output pubkey. I think it's easy to fix if the schnorr pubkey, > > nonce are committed in the covenant locking script, and explicitly > > verified as such in the small script. This is pointed out > > in the section 2.4 about transaction grinding, but it's not > > discussed further afaict e.g in the section 7 on the security > > discussion. > > > > Best, > > Antoine > > ots hash: > b47373e430c25a96e642ddad3cc330ee364f06c06f81a63238926a9ebbcb6795 > > Le jeudi 7 novembre 2024 à 17:48:03 UTC, Ethan Heilman a écrit : > >> > >> 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 bitcoindev+...@googlegroups•com. > > To view this discussion visit > https://groups.google.com/d/msgid/bitcoindev/fc031fe3-444c-446d-a5c1-f2d7a430b478n%40googlegroups.com > . > -- 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 bitcoindev+unsubscribe@googlegroups•com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/5b69515c-b5b1-4333-88e2-7653face1a3bn%40googlegroups.com. [-- Attachment #1.2: Type: text/html, Size: 27160 bytes --] ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [bitcoindev] Re: ColliderScript: Covenants in Bitcoin via 160-bit hash collisions 2024-11-25 3:42 ` Antoine Riard @ 2024-11-27 22:37 ` Ethan Heilman 0 siblings, 0 replies; 5+ messages in thread From: Ethan Heilman @ 2024-11-27 22:37 UTC (permalink / raw) To: Antoine Riard; +Cc: Bitcoin Development Mailing List > If I'm understanding correctly, the trick is about proving that y(y1 = y2) both in Big Script and Small Script. Yes, the trick is about proving that y1 = y2 where the script has y1 and <y2>32. > For the security definition you're giving of the equivalence check, I don't think it matters that a party in a multi-party colliderscript-based vault protocol being honest. We don't make any honest assumptions, this is purely based on cryptographic soundness. >Do we really need to OP_DUP w and t on the script stack ? Like isn't the s signature verified by Big Script is enough to then decompose the data payload in Small Script 32-bit inputs. I was using OP_DUP here to demonstrate that we know with 100% certainty that the (w,t) that Small Script sees is the exact same value as what Big Script sees. > I don't see where w, t are formally defined in the paper, though I browsed again the section 4. about realizing Bitcoin equivalence tester sets. w is a 33-bit stack element, e.g. the number 23412 t is a bit vector consisting of many stack elements, e.g. the bit string 1,1,0,1,0,0,1,1,0,1,01, ... They are supplied as witness stack elements by the spending transaction. See Figure 1, elements pushed on the stack from the spending transaction are colored purple. > I don't see the paper is introducing a formal notion of semantically equivalent. Let's say two transactions, Txn1, Txn2 are the same in every bit except: Txn1's locking script does: PUSH 0x2432423423432423424 DROP Txn2 locking script does: PUSH 0x6767567567685758676 DROP Both transactions will have a different hash, but be semantically equivalent I'm not sure what your attack is attempting to achieve. Can you frame as Alice locks coins under covenant that does X and Eve wants to do Y On Sun, Nov 24, 2024 at 11:24 PM Antoine Riard <antoine.riard@gmail•com> wrote: > > Hi Ethan, > > Thanks for the additional thoughts. > > > You have the basic idea correct but I think you might be missing one > > piece of this (or perhaps you just simplified some details). > > Reading again the paper, my example and your new example, I don't understand > yet all the details for sure, though on the fundamental trick, I believe > we're saying more or less the same thing. If I'm understanding correctly, > the trick is about proving that y(y1 = y2) both in Big Script and Small Script. > > > For an honest party spending a covenant the s1 and s2 they generate > > are always equal. This means that y1 <- h_big_script(s1) and y2 <- > > h_small_script(s2) will generate the same y (y1 = y2). As you point > > out we can't compare y1 to y2 because they are encoded differently. > > Where s1 and s2 is the byte-for-byte equivalent spent transactions. > For the security definition you're giving of the equivalence check, > I don't think it matters that a party in a multi-party colliderscript-based > vault protocol being honest. Either, the equivalence check is sound, > and it's immutable once the UTXO's containing the lock script is > confirmed in the chain, the covenant creator cannot himself generate > not equal s1 and s2 _and_ successfully spend the coin. > > The lemma in terms of security model, I think for multi-party protocol, > is that all the participant should verify the soundness of the y(y1 = y2), > before to engage in the protocol (e.g staking more coins under the > locking script or doing a swap). > > > we know just DUP w and t for evaluation in > > small script and big script. Since dGen is deterministic it must be > > the case that dGen_big_script(w, t) always equals dGen_small_script(w, > > t). The trick is finding a w, t, s where dGen(w, t) = h(s) where s = > > s1 = s2. > > Do we really need to OP_DUP w and t on the script stack ? Like isn't > the s signature verified by Big Script is enough to then decompose the > data payload in Small Script 32-bit inputs. > > I don't see where w, t are formally defined in the paper, though I > browsed again the section 4. about realizing Bitcoin equivalence tester > sets. There are just given as parameters, ||w|| = 33 and 35 <= || t || > <= 75, and it doesn't say if there are data elements or transaction > fields feeded in the signature digest. > > > If I understand what you mean by staticness, the answer is no. > > Staticness should not provide any advantage to an attacker. In fact if > > the attacker does not sufficiently randomize the sighash on each > > query, they will have more difficulty, not less, finding collisions. > > Yes, for example for staticness if you take bip143 signature digest, > the nVersion field is going to be the same for all the v2 transaction > or v3 transaction. > > I see the introduction of the randomness p in the section 3 about > equivalence check in bitcoin, though at the same time the idea is > to find a semantically equivalent transaction to get s of tx(p). > > So for a given s signature, is there an existing efficient NP algorithm, > that could find tx1 and tx2 for a same randomness p, where tx1 and > tx2 are not semantically equivalent...? I think it's an interesting > problem, and I don't see the paper is introducing a formal notion of > semantically equivalent. > > > I'm not sure what you mean here. Can you provide a concrete example of > > this attack? > > Let's recall the Schnorr signing algorithm, G^s = R + P^hash(R || m). > > Given m is the transaction data and G the generator, R the nonce and > P the public key point, and all of same are equivalent, can I grind > any of G, R or P to find 2 valid curve points for the same signature > s where the curve point would correspond to 2 messages m1, m2 ? > > I think it's as hard as breaking the DL problem, though I'm not > sure if they have been new cryptanalysis of the Schnorr trick, > compared to existent proofs for Schnorr under the RO / GGM models. > > Best, > Antoine > ots hash: 27b5b4bdeea168147580d96769fda7bb395619435832a2e1d0aee0f03b22f27b > > Le mercredi 13 novembre 2024 à 22:23:29 UTC, Ethan Heilman a écrit : >> >> > If I'm understanding correctly, the goal of the equivalence check is to find a `y` such that `y <- h_big_script(s1)` and `y <- h_small_script(s2)` >> are logically equal. Once such `y` is found, the data-carrying >> transaction is grinded until s1 and s2 are equal. >> >> You have the basic idea correct but I think you might be missing one >> piece of this (or perhaps you just simplified some details). >> >> For an honest party spending a covenant the s1 and s2 they generate >> are always equal. This means that y1 <- h_big_script(s1) and y2 <- >> h_small_script(s2) will generate the same y (y1 = y2). As you point >> out we can't compare y1 to y2 because they are encoded differently. >> >> > The hash `y` outcome for both `h_big_script` and `h_small_script` will be never compared themselves during the script execution, as we *cannot*. The former is a plain data push and the remainder an array of 32-bits script elements. >> >> To show equivalence between s1 and s2, we find a value d <-- dGen(w,t) >> which is equal to y. >> >> y1 <- h_big_script(s1) >> d1 <-- dGen_big_script(w, t) >> y1 == d1? >> >> y2 <- h_small_script(s2) >> d2 <-- dGen_small_script(w, t) >> y2 == d2? >> >> Since the inputs to dGen are 32-bit elements in both dGen_big_script >> and dGen_small_script, we know just DUP w and t for evaluation in >> small script and big script. Since dGen is deterministic it must be >> the case that dGen_big_script(w, t) always equals dGen_small_script(w, >> t). The trick is finding a w, t, s where dGen(w, t) = h(s) where s = >> s1 = s2. >> >> > 1). could a 160-bit hash collision attacker leverage some staticness of fields in bip341 sighash to lower the hardness under 2^109 ? As analyzed in appendix G. >> >> If I understand what you mean by staticness, the answer is no. >> Staticness should not provide any advantage to an attacker. In fact if >> the attacker does not sufficiently randomize the sighash on each >> query, they will have more difficulty, not less, finding collisions. >> >> > 2) The Schnorr trick assumes a signature where the pubkey and nonce are equivalent to the generator point. I think there could be some forgery of the covenanted transaction data, if an adversary can construct a transaction with still the same s1 and s2 to satisfy Big Script and Small Script. >> >> I'm not sure what you mean here. Can you provide a concrete example of >> this attack? >> >> Thanks, >> Ethan >> >> On Tue, Nov 12, 2024 at 12:41 PM Antoine Riard <antoin...@gmail•com> wrote: >> > >> > Hi Ethan, >> > >> > Thanks you for this astute paper. >> > >> > The crux of the paper relies on the equivalence check, which >> > in my understanding can be described as the following (correct >> > me if the set of algorithms differs). On one side, we have our >> > old good correct signatures on the stack. A signature is a >> > commitment to the signature hash fields. This signature can be >> > verified to be valid and it can be given to one of the 160-bits >> > hash functions, i.e OP_SHA1 or OP_RIPEMD160. >> > >> > E.g: <<signature> <OP_DUP> <pubkey> <OP_CHECKSIG> <OP_SHA1>> >> > >> > Doing the Schnorr trick, a data-carrying transaction can be >> > altered until its signature is equivalent to the SchnorrHash, >> > by selecting accordingly that pubkey P and nonce R are equal >> > to the generator. Those elements that the signature is well- >> > composed are further checked by the small script "signature >> > defragmentation" 32-bits integers opcodes. >> > >> > On the other side, we have the 32-bits integers opcodes >> > that can be used to re-implement "bitcoin script natively-ish" >> > cryptographic operations, e.g blake3. Giving the full script >> > would be too lengthy, though hash functions are just (very) >> > smart sequences of XORed seed, key, data that one can simulate >> > easy in bitcoin script. E.g to flip one bit of data. >> > >> > E.g: <<1-bit input_a> <0x1> <OP_EQUAL> <OP_IF> <0x0> <OP_ELSE> >> > <0x1> <OP_ENDIF>> >> > >> > So let's say we have some basic cryptographic operation >> > like OP_SHA1 in small script (for p2tr tapscript spend >> > the script size limit is the block size). If I'm understanding >> > correctly, the goal of the equivalence check is to find a `y` >> > such that `y <- h_big_script(s1)` and `y <- h_small_script(s2)` >> > are logically equal. Once such `y` is found, the data-carrying >> > transaction is grinded until s1 and s2 are equal. The hash `y` >> > outcome for both `h_big_script` and `h_small_script` will be >> > never compared themselves during the script execution, as >> > we *cannot*. The former is a plain data push and the remainder >> > an array of 32-bits script elements. >> > >> > Once the equivalence check has been done, the restrictions >> > on the signature construction from the Schnorr trick can >> > be checked, and then what covenant checks can be done in >> > the remainder of the 4MB weight unit can be play out. E.g >> > checking the spending transaction nAmount twice 32 bits >> > are less than a given value. >> > >> > <<32-bits> <first digit amount> <OP_LESSTHAN> >> > <32-bits> <second digit amount> <OP_LESSTHAN>> >> > >> > Withstanding the code proof that a OP_SHA1 or OP_RIPEMD160 >> > fips-180-1 implem in small script effectively fit in the >> > block size, I think the colliderscript equivalent check >> > construction as presented can be sound, though I have >> > few questions on the security model. >> > >> > 1) Let's say you have a 2 step smart contract as presented >> > in Figure 4. The locking script is committed in a tapscript >> > somewhere in the tree, and as such the collision `y` to found >> > cannot be observed ahead of the spending. >> > >> > Once the script is revealed and before the transaction confirms >> > every 10 block _in average_, an adversary with enormous >> > computational resources, could come to find another collision >> > (what I think you call a triple collision). While the s1 value, >> > i.e the main data fields of the data-carrying transaction >> > shouldn't be know ahead, for some use-cases they might very >> > standards. >> > >> > E.g if you take a vault protocol, only the spent outpoint and >> > pubkey might differs among vault instance belonging to different >> > users (e.g everyone use same emergency or revaulting timelocks by >> > default). So could a 160-bit hash collision attacker leverage >> > some staticness of fields in bip341 sighash to lower the >> > hardness under 2^109 ? As analyzed in appendix G. >> > >> > 2) The Schnorr trick assumes a signature where the pubkey and >> > nonce are equivalent to the generator point. I think there >> > could be some forgery of the covenanted transaction data, if >> > an adversary can construct a transaction with still the same >> > s1 and s2 to satisfy Big Script and Small Script. >> > >> > However, the transaction data would be a security downgrade >> > from the smart contract protocol. E.g a nLocktime committing >> > to a sooner chain tip than now, or even worst a malleated >> > output pubkey. I think it's easy to fix if the schnorr pubkey, >> > nonce are committed in the covenant locking script, and explicitly >> > verified as such in the small script. This is pointed out >> > in the section 2.4 about transaction grinding, but it's not >> > discussed further afaict e.g in the section 7 on the security >> > discussion. >> > >> > Best, >> > Antoine >> > ots hash: b47373e430c25a96e642ddad3cc330ee364f06c06f81a63238926a9ebbcb6795 >> > Le jeudi 7 novembre 2024 à 17:48:03 UTC, Ethan Heilman a écrit : >> >> >> >> 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 bitcoindev+...@googlegroups•com. >> > To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/fc031fe3-444c-446d-a5c1-f2d7a430b478n%40googlegroups.com. > > -- > 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 bitcoindev+unsubscribe@googlegroups•com. > To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/5b69515c-b5b1-4333-88e2-7653face1a3bn%40googlegroups.com. -- 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 bitcoindev+unsubscribe@googlegroups•com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BUs1xjibAgyskvmti2GuvgNKLzPs6APUaTJZUX%2B4eQ5SA%40mail.gmail.com. ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2024-11-27 22:54 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2024-11-07 17:44 [bitcoindev] ColliderScript: Covenants in Bitcoin via 160-bit hash collisions Ethan Heilman 2024-11-12 17:38 ` [bitcoindev] " Antoine Riard 2024-11-13 22:06 ` Ethan Heilman 2024-11-25 3:42 ` Antoine Riard 2024-11-27 22:37 ` Ethan Heilman
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox