path: root/93/3ae211b37744e7426a9fba0e412d16e0c47640

Delivery-date: Tue, 12 Nov 2024 09:41:30 -0800
Received: from mail-yb1-f183.google.com ([209.85.219.183])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBC3PT7FYWAMRBP5GZ24QMGQE6R7KMAQ@googlegroups.com>)
	id 1tAutM-0000gU-9y
	for bitcoindev@gnusha.org; Tue, 12 Nov 2024 09:41:29 -0800
Received: by mail-yb1-f183.google.com with SMTP id 3f1490d57ef6-e3314237b86sf10239418276.1
        for <bitcoindev@gnusha.org>; Tue, 12 Nov 2024 09:41:28 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1731433282; x=1732038082; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:sender:from
         :to:cc:subject:date:message-id:reply-to;
        bh=cNlqksVdZRebzHCluFzv+BwWQ8j/5KJeLslqDKSjKo4=;
        b=NC9Xg7zuVmVsOGkkC+1UXzJdKzT5qfUlNe20GIN9N8wjkkGfC42YAjuZMkrJT4Dyta
         AaE+bFtpGS6gjvN2tqN+EiFY+/h29kXdXEuUai/wHaQWyLsNJCBWvZPmKzkbonhNIu3u
         MnCE8V/AE5XodO+PI+wGg9bItYpNx6/E65zbo2lNlqpN96o15vpyVw7zvRScZ+Glz8aU
         aQgFPFfC0SEMJVyTIGDqwGyfwccQgLchkrfUs7Kr9ZkA0xBYWH/3JRBu4gYHb/WxA4L3
         /vATwXJvbXCShG6o4h5TIFkntfcLNDZNZQr3AFvKWVGBnXqowuiSa18MisDZSMkhsHAc
         ckYg==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1731433282; x=1732038082; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:from:to:cc
         :subject:date:message-id:reply-to;
        bh=cNlqksVdZRebzHCluFzv+BwWQ8j/5KJeLslqDKSjKo4=;
        b=bJb8EQAFW/EEakhD2a9qWcQGKJx2HUHItMBdJjB+nraAgo1LBX17GacA0sxkNITWsC
         0fyjXYP9KjQpPeHumbdduryQ9imL8t4Bm9nd9LYzxgg/k82XyHC67CjX8X0DigP67L2l
         cjHuvcjux9NGjAAzlH5UU27+Cg97kzDFbfz48ZltAJGSKJ4F4hiLa4GPkQbZZw0ozhhV
         /32QLrlrlYePab28kbZj1TlaqsDGhVRgMfolE1BZTynmuYTE44c5uUQA6O5Nt92nVxjr
         Wn5pFLxkXIx7eOBm9RjNktxgVklS2hiOBzItgOmCULnRbg8WfyA7Q2wEfJoz5mzq5K3q
         qyaw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1731433282; x=1732038082;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:x-beenthere
         :x-gm-message-state:sender:from:to:cc:subject:date:message-id
         :reply-to;
        bh=cNlqksVdZRebzHCluFzv+BwWQ8j/5KJeLslqDKSjKo4=;
        b=SehLHiSC8ZCkWjI9atuVjMpWoQ/KrXBHhl8A98uh6nxEAD6Ek9ZpLGoVIIXTqZ8DGA
         W/uFr9fjeD9htMg/kfy/83ACmTJ4+MvuCG1twPCe/Q2QrvG9M+p0G0zQBfACDksTvX5q
         tyrUTym5JmWjOtIGMwqeFjX5+bFiBll7n3nrsYULguZQ1r22ZXbF6/I554D5hixWgLz8
         WKqtxNII+nl90w5l0FKeE4caPe7KYx0cWy2wQ606M/9NVm5YBTO4VFTe//qcyo8dFxmV
         slwCux2y7EnsZUIsfzACNbd2tki7roXt6fVCRw8bCqZCAAsCKIImV4OfBfZIgLmzfVbU
         U8Yg==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCVM7n7mLrF1oNz1/5uEpggnP4LeSTojxXz+1GFGNcHk0g9V7mMGLMZuCLh99Bxpae5CpEtmI/Qy2rOR@gnusha.org
X-Gm-Message-State: AOJu0YxCQDAj8/ixBEdSl1AsdEpoQEwXZZGpbTJ3Vt1I6DSU5wbaH+SK
	OmMls/4KddN0oxeHloeUQJ431qIO1zbHWetz50yo5LFoMvI0GEL3
X-Google-Smtp-Source: AGHT+IEAJsQE2fFuep6C9IEafhYrw2dh0MAWBUyhLntrhjx7MVJx2M6f5HZwzlKRY1c8a/P4sD2hLA==
X-Received: by 2002:a05:6902:d48:b0:e25:ca37:b669 with SMTP id 3f1490d57ef6-e337f882556mr14623213276.24.1731433281879;
        Tue, 12 Nov 2024 09:41:21 -0800 (PST)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a25:7403:0:b0:e35:df28:2ec9 with SMTP id 3f1490d57ef6-e35df2830cdls1145961276.2.-pod-prod-06-us;
 Tue, 12 Nov 2024 09:41:19 -0800 (PST)
X-Received: by 2002:a05:690c:6b88:b0:6de:2ae:811f with SMTP id 00721157ae682-6eaddfbb941mr170693237b3.35.1731433279197;
        Tue, 12 Nov 2024 09:41:19 -0800 (PST)
Received: by 2002:a05:690c:6886:b0:6ea:3075:201e with SMTP id 00721157ae682-6eadc44856ams7b3;
        Tue, 12 Nov 2024 09:38:16 -0800 (PST)
X-Received: by 2002:a05:690c:4985:b0:6ea:4b07:31a6 with SMTP id 00721157ae682-6eadddb5b7cmr171895107b3.25.1731433095399;
        Tue, 12 Nov 2024 09:38:15 -0800 (PST)
Date: Tue, 12 Nov 2024 09:38:14 -0800 (PST)
From: Antoine Riard <antoine.riard@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <fc031fe3-444c-446d-a5c1-f2d7a430b478n@googlegroups.com>
In-Reply-To: <CAEM=y+W2jyFoJAq9XrE9whQ7EZG4HRST01TucWHJtBhQiRTSNQ@mail.gmail.com>
References: <CAEM=y+W2jyFoJAq9XrE9whQ7EZG4HRST01TucWHJtBhQiRTSNQ@mail.gmail.com>
Subject: [bitcoindev] Re: ColliderScript: Covenants in Bitcoin via 160-bit
 hash collisions
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_359264_719006925.1731433094970"
X-Original-Sender: antoine.riard@gmail.com
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.5 (/)

------=_Part_359264_719006925.1731433094970
Content-Type: multipart/alternative; 
	boundary="----=_Part_359265_414869183.1731433094970"

------=_Part_359265_414869183.1731433094970
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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 =C3=A0 17:48:03 UTC, Ethan Heilman a =C3=A9crit :

> 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 =E2=80=9Csurprise quantum computer=E2=80=9D which forces Bi=
tcoin 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
> =3D=3D=3D=3D
>
> 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=E2=80=99s 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 =3D=3D 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=20
> https://bitvmx.org/knowledge/optimizing-algorithms-for-bitcoin-script
>
> Let=E2=80=99s say you have a Small Script implementation of SHA-1 where i=
t
> treats [12345678, ABCDEF00] as an Small Script encoding of
> 12345678abcdef00. Does the following equivalence check work?
>
> OP_SHA1(12345678abcdef00) =3D=3D smallscript_SHA1([12345678, ABCDEF00])
>
> No, because OP_SHA1 will produce one big 160-bit (20 byte) stack element
> OP_SHA1(12345678abcdef00) =E2=86=92 a12d9ee23d07317c2d2d6887fe955819bc2d2=
4c5
> whereas the Small Script implementation of SHA1 will produce 5 32-bit
> (4 Byte) stack elements
> smallscript_SHA1([12345678, abcdef00]) =E2=86=92 [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) =3D=3D SHA1(X) is true
> AND
> 12345678abcdef00 !=3D X
> AND
> Size(X) =3D 32-bits
>
> You could do an equivalence check for 12345678abcdef00 by doing the=20
> following:
>
> In Big Script
> Check OP_SHA1(12345678abcdef00) =3D=3D OP_SHA1(X)
>
> In Small Script
> Check smallscript_SHA1([12345678, abcdef00]) =3D=3D 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) =3D=3D OP_SHA1(X)
> and
>
> Check smallscript_SHA1(B) =3D=3D 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) =3D SHA1(X) =3D SHA1(B)
>
> where A !=3D B, A!=3DX, B!=3DX
>
> 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 =3D SHA1(w)
> for b in t:
> If b =3D=3D 0:
> y =3D SHA1(y)
> If b =3D=3D 1:
>
> y =3D 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=3D312a123e, t=3D01101
> 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) =3D=3D BigScript-dGen(w, t) // Big script dGen using OP_SHA1
> and OP_RIPEMD160
> SHA1(B) =3D=3D 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 --=20
> 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
>

--=20
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 e=
mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/=
fc031fe3-444c-446d-a5c1-f2d7a430b478n%40googlegroups.com.

------=_Part_359265_414869183.1731433094970
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Ethan,<br /><br />Thanks you for this astute paper.<br /><br />The crux =
of the paper relies on the equivalence check, which<br />in my understandin=
g can be described as the following (correct<br />me if the set of algorith=
ms differs). On one side, we have our<br />old good correct signatures on t=
he stack. A signature is a<br />commitment to the signature hash fields. Th=
is signature can be<br />verified to be valid and it can be given to one of=
 the 160-bits<br />hash functions, i.e OP_SHA1 or OP_RIPEMD160.<br /><br />=
E.g: &lt;&lt;signature&gt; &lt;OP_DUP&gt; &lt;pubkey&gt; &lt;OP_CHECKSIG&gt=
; &lt;OP_SHA1&gt;&gt;<br /><br />Doing the Schnorr trick, a data-carrying t=
ransaction can be<br />altered until its signature is equivalent to the Sch=
norrHash,<br />by selecting accordingly that pubkey P and nonce R are equal=
<br />to the generator. Those elements that the signature is well-<br />com=
posed are further checked by the small script "signature<br />defragmentati=
on" 32-bits integers opcodes.<br /><br />On the other side, we have the 32-=
bits integers opcodes<br />that can be used to re-implement "bitcoin script=
 natively-ish"<br />cryptographic operations, e.g blake3. Giving the full s=
cript<br />would be too lengthy, though hash functions are just (very)<br /=
>smart sequences of XORed seed, key, data that one can simulate<br />easy i=
n bitcoin script. E.g to flip one bit of data.<br /><br />E.g: &lt;&lt;1-bi=
t input_a&gt; &lt;0x1&gt; &lt;OP_EQUAL&gt; &lt;OP_IF&gt; &lt;0x0&gt; &lt;OP=
_ELSE&gt;<br />&lt;0x1&gt; &lt;OP_ENDIF&gt;&gt;<br /><br />So let's say we =
have some basic cryptographic operation<br />like OP_SHA1 in small script (=
for p2tr tapscript spend<br />the script size limit is the block size). If =
I'm understanding<br />correctly, the goal of the equivalence check is to f=
ind a `y`<br />such that `y &lt;- h_big_script(s1)` and `y &lt;- h_small_sc=
ript(s2)`<br />are logically equal. Once such `y` is found, the data-carryi=
ng<br />transaction is grinded until s1 and s2 are equal. The hash `y`<br /=
>outcome for both `h_big_script` and `h_small_script` will be<br />never co=
mpared themselves during the script execution, as<br />we *cannot*. The for=
mer is a plain data push and the remainder<br />an array of 32-bits script =
elements.<br /><br />Once the equivalence check has been done, the restrict=
ions<br />on the signature construction from the Schnorr trick can<br />be =
checked, and then what covenant checks can be done in<br />the remainder of=
 the 4MB weight unit can be play out. E.g<br />checking the spending transa=
ction nAmount twice 32 bits<br />are less than a given value.<br /><br />&l=
t;&lt;32-bits&gt; &lt;first digit amount&gt; &lt;OP_LESSTHAN&gt;<br />&lt;3=
2-bits&gt; &lt;second digit amount&gt; &lt;OP_LESSTHAN&gt;&gt;<br /><br />W=
ithstanding the code proof that a OP_SHA1 or OP_RIPEMD160<br />fips-180-1 i=
mplem in small script effectively fit in the<br />block size, I think the c=
olliderscript equivalent check<br />construction as presented can be sound,=
 though I have<br />few questions on the security model.<br /><br />1) Let'=
s say you have a 2 step smart contract as presented<br />in Figure 4. The l=
ocking script is committed in a tapscript<br />somewhere in the tree, and a=
s such the collision `y` to found<br />cannot be observed ahead of the spen=
ding.<br /><br />Once the script is revealed and before the transaction con=
firms<br />every 10 block _in average_, an adversary with enormous<br />com=
putational resources, could come to find another collision<br />(what I thi=
nk you call a triple collision). While the s1 value,<br />i.e the main data=
 fields of the data-carrying transaction<br />shouldn't be know ahead, for =
some use-cases they might very<br />standards.<br /><br />E.g if you take a=
 vault protocol, only the spent outpoint and<br />pubkey might differs amon=
g vault instance belonging to different<br />users (e.g everyone use same e=
mergency or revaulting timelocks by<br />default). So could a 160-bit hash =
collision attacker leverage<br />some staticness of fields in bip341 sighas=
h to lower the<br />hardness under 2^109 ? As analyzed in appendix G.<br />=
<br />2) The Schnorr trick assumes a signature where the pubkey and<br />no=
nce are equivalent to the generator point. I think there<br />could be some=
 forgery of the covenanted transaction data, if<br />an adversary can const=
ruct a transaction with still the same<br />s1 and s2 to satisfy Big Script=
 and Small Script.<br /><br />However, the transaction data would be a secu=
rity downgrade<br />from the smart contract protocol. E.g a nLocktime commi=
tting<br />to a sooner chain tip than now, or even worst a malleated<br />o=
utput pubkey. I think it's easy to fix if the schnorr pubkey,<br />nonce ar=
e committed in the covenant locking script, and explicitly<br />verified as=
 such in the small script. This is pointed out<br />in the section 2.4 abou=
t transaction grinding, but it's not<br />discussed further afaict e.g in t=
he section 7 on the security<br />discussion.<br /><br />Best,<br />Antoine=
<div>ots hash: b47373e430c25a96e642ddad3cc330ee364f06c06f81a63238926a9ebbcb=
6795<br /></div><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail=
_attr">Le jeudi 7 novembre 2024 =C3=A0 17:48:03 UTC, Ethan Heilman a =C3=A9=
crit=C2=A0:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 =
0 0 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">W=
e wanted to make bitcoin-dev aware of our recently published draft on
<br>how to create and spend covenants on Bitcoin using Tapscript.
<br><a href=3D"https://colliderscript.co/colliderscript.pdf" target=3D"_bla=
nk" rel=3D"nofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=
=3Dfr&amp;q=3Dhttps://colliderscript.co/colliderscript.pdf&amp;source=3Dgma=
il&amp;ust=3D1731519426164000&amp;usg=3DAOvVaw0pO21MLr6emaLocGL_UrCG">https=
://colliderscript.co/colliderscript.pdf</a>
<br>
<br>Our approach does not require soft forks and should work on Bitcoin as
<br>it is currently deployed. While creating these covenants is as easy as
<br>creating a transaction with P2WSH output, spending these covenants
<br>requires substantial computation and involves creating very large
<br>bitcoin transactions.
<br>
<br>Spending such a covenant requires ~2^86 hash calls to SHA-1 and
<br>RIPEMD-160.  In comparison, mining a Bitcoin block at current
<br>difficulty requires ~2^78.3 hash calls to SHA256x2. Thus, spending
<br>such a covenant would require the same number of hash queries the
<br>entire Bitcoin network does in roughly ~33 hours. Such covenants could
<br>be created today, but spending them likely requires the creation of
<br>dedicated ASICs.
<br>
<br>While the computational costs limit the immediate applicability of our
<br>covenants, we are optimistic that future work can significantly
<br>improve these numbers. This approach is not a replacement for a
<br>covenant opcode because:
<br>1. High computational cost: Our approach is likely to be many orders
<br>of magnitude more computationally expensive than a covenant opcode.
<br>2. 4Mb transactions: Transaction size, computation cost trade-off
<br>exists that reduces the computational costs of these covenants by
<br>increasing the transaction size. Due to most of the cost being
<br>computational it is likely they always be just under 4MB in size even
<br>with efficiency gain. 4MB is the limit for valid transactions.
<br>
<br>Our approach is framed around covenants, but our approach enables
<br>arbitrary computation on Bitcoin transaction data. This arbitrary
<br>computation is bounded only by the circuit size we can pack into what
<br>is left of a 4Mb Bitcoin transaction after it contains all our
<br>necessary machinery. This means, for example, we can do Tapscript
<br>lamport signatures that sign the sighash of the spending transaction.
<br>
<br>One of the authors of our paper, Andrew Poelstra, proposes in the
<br>paper a very interesting use case for lamport signatures (Section 7.2)
<br>which I think is worth making the list aware of. Leveraging the fact
<br>that it is very cheap for users to write and deploy our covenants, it
<br>is only expensive to spend them, the following scheme is proposed. A
<br>user could create a covenant in a tapleaf whose spending condition
<br>requires a Lamport signature over spending transaction. While the
<br>resulting script will be very large, they can hide it in a Taproot
<br>leaf where it will never be serialized on-chain unless it is used. In
<br>the case of a =E2=80=9Csurprise quantum computer=E2=80=9D which forces =
Bitcoin to
<br>suddenly disable all elliptic curve cryptography including taproot key
<br>spends, such users will still be able to spend their coins (though at
<br>enormous cost). If a large quantity of users do this, it may be
<br>possible for the Bitcoin chain to survive such an event, even if no
<br>better solution is found or deployed.
<br>
<br>
<br>Our Technique
<br>=3D=3D=3D=3D
<br>
<br>We will now look at how our technique works by introducing the core
<br>problem we solve and then showing how by solving this problem we can
<br>enforce covenants.
<br>
<br>
<br>Let=E2=80=99s say you want to write a Bitcoin script that checks if
<br>12345678abcdef00 and [12345678, abcdef00] are equivalent. That is, if
<br>you treated 12345678 and abcdef00as a single element  would it be
<br>equal to 12345678abcdef00?
<br>
<br>If we had OP_CAT this would be easy:
<br>12345678abcdef00  =3D=3D CAT(12345678, abcdef00)
<br>
<br>We call checking if one element is the concatenation of a list of
<br>smaller elements, an equivalence check. We can ask is 12345678abcdef00
<br>equivalent to  [12345678, abcdef00]?
<br>In Bitcoin script, checking equivalence between a single big element
<br>and a list of small elements is quite challenging, below we will show
<br>how to do it.
<br>
<br>Before getting there we need to make a short digression first. It has
<br>been part of the lore for some time that Bitcoin script can perform
<br>arbitrary computation on inputs, so long as the inputs are encoded as
<br>a list of 32-bit stack elements. This uses opcodes like OP_ADD,
<br>OP_SUB, which only accept 32-bit inputs. We call functions written
<br>using 32-bit elements Small Script. People have built all sorts of
<br>things in Small Script,  for instance you can compute Blake3 in
<br>Tapscript in a bitcoin output using only 45,000 opcodes (a.k.a. 45,000
<br>bytes)! See <a href=3D"https://bitvmx.org/knowledge/optimizing-algorith=
ms-for-bitcoin-script" target=3D"_blank" rel=3D"nofollow" data-saferedirect=
url=3D"https://www.google.com/url?hl=3Dfr&amp;q=3Dhttps://bitvmx.org/knowle=
dge/optimizing-algorithms-for-bitcoin-script&amp;source=3Dgmail&amp;ust=3D1=
731519426164000&amp;usg=3DAOvVaw2xwRXvkh_ItnlmRxBOyJiq">https://bitvmx.org/=
knowledge/optimizing-algorithms-for-bitcoin-script</a>
<br>
<br>Let=E2=80=99s say you have a Small Script implementation of SHA-1 where=
 it
<br>treats [12345678, ABCDEF00] as an Small Script encoding of
<br>12345678abcdef00. Does the following equivalence check work?
<br>
<br>OP_SHA1(12345678abcdef00) =3D=3D  smallscript_SHA1([12345678, ABCDEF00]=
)
<br>
<br>No, because OP_SHA1 will produce one big 160-bit (20 byte) stack elemen=
t
<br>OP_SHA1(12345678abcdef00) =E2=86=92  a12d9ee23d07317c2d2d6887fe955819bc=
2d24c5
<br>whereas the Small Script implementation of SHA1 will produce 5 32-bit
<br>(4 Byte) stack elements
<br>smallscript_SHA1([12345678, abcdef00]) =E2=86=92 [a12d9ee2, 3d07317c,
<br>2d2d6887, fe955819, bc2d24c5]
<br>
<br>Checking if these are the same requires the equivalence check, the
<br>very thing we were trying to build. Ok, hear me out, what if you
<br>magically discovered a value X which was 32-bits in size and just so
<br>happened to collide with 12345678abcdef00. That is,
<br>SHA1(12345678abcdef00) =3D=3D SHA1(X) is true
<br>AND
<br>12345678abcdef00 !=3D X
<br>AND
<br>Size(X) =3D 32-bits
<br>
<br>You could do an equivalence check for 12345678abcdef00 by doing the fol=
lowing:
<br>
<br>In Big Script
<br>Check OP_SHA1(12345678abcdef00) =3D=3D OP_SHA1(X)
<br>
<br>In Small Script
<br>Check smallscript_SHA1([12345678, abcdef00]) =3D=3D smallscript_SHA1(X)
<br>
<br>If both of these return true, then we decide 12345678abcdef00 is
<br>equivalent to [12345678, abcdef00].
<br>
<br>Put more generally:
<br>Check OP_SHA1(A) =3D=3D OP_SHA1(X)
<br>and
<br>
<br>Check smallscript_SHA1(B) =3D=3D smallscript_SHA1(X)
<br>
<br>Now if A is equivalent to B, and X collides with A, then X will
<br>collide with B in Small Script because B is just the Small Script
<br>encoding of A. However if A is not equivalent to B then this implies a
<br>triple collision which is much more expensive to find:
<br>
<br>SHA1(A) =3D SHA1(X) =3D SHA1(B)
<br>
<br>where A !=3D B, A!=3DX, B!=3DX
<br>
<br>Given the choice between two possibles for an A and B that pass the che=
ck:
<br>1. A equivalent to B
<br>2. A not actually equivalent to B requires a triple collision that is
<br>computationally infeasible
<br>We argue that 1 is much more likely.
<br>
<br>Ok, but as some of the cryptographers are now typing, if X is only
<br>32-bits it is extremely unlikely to find an X that collides for any
<br>particular value. To exploit the birthday bound to find collisions
<br>with a 160-bit hash function you need the input to be &gt;80-bit in siz=
e.
<br>Overcoming this problem is the last trick of the paper. We introduce
<br>the function dGen(w, t) which can take any length of input and that
<br>input can be read by Small Script and Big Script.
<br>
<br>dGen(w, t):
<br>  y =3D SHA1(w)
<br>  for b in t:
<br>    If b =3D=3D 0:
<br>      y =3D SHA1(y)
<br>    If b =3D=3D 1:
<br>
<br>       y =3D RIPEMD160(y)
<br>  return y
<br>
<br>w is a 33-bit stack element, t is a series of 32-bit stack elements
<br>which we treat as a list of bits. For instance is w=3D312a123e, t=3D011=
01
<br>dGen would return the value created by running
<br>SHA1(RIPEMD160(SHA1(SHA1(RIPEMD160(SHA1(312a123e))))))
<br>
<br>dGen can be run using OP_SHA1 and OP_RIPEMD160 and can also be run in
<br>Small Script using Small Script implementations of SHA1 and RIPEMD160.
<br>Since both sides can use the same stack elements to compute the output
<br>it lets us build our equivalence check. We just need to find a (w, t)
<br>such that:
<br>
<br>OP_SHA1(A) =3D=3D BigScript-dGen(w, t) // Big script dGen using OP_SHA1
<br>and OP_RIPEMD160
<br>SHA1(B) =3D=3D SmallScript-dGen(w, t) // Small script dGen
<br>
<br>Finding (w,t) is the main computational expense of spending our
<br>covenant as our covenant depends on this equivalence check. That said
<br>finding collisions in 160-bit hash functions requires significantly
<br>less computation than the Bitcoin network regularly performs. See our
<br>paper for our collision algorithm and discussions of known weaknesses
<br>in SHA1.
<br>
<br>How do you turn this equivalence check into a covenant?
<br>
<br>Past work -- <a href=3D"https://www.wpsoftware.net/andrew/blog/cat-and-=
schnorr-tricks-i.html" target=3D"_blank" rel=3D"nofollow" data-saferedirect=
url=3D"https://www.google.com/url?hl=3Dfr&amp;q=3Dhttps://www.wpsoftware.ne=
t/andrew/blog/cat-and-schnorr-tricks-i.html&amp;source=3Dgmail&amp;ust=3D17=
31519426164000&amp;usg=3DAOvVaw1Sy5wzzbqcvK3F8Y_8UjdH">https://www.wpsoftwa=
re.net/andrew/blog/cat-and-schnorr-tricks-i.html</a>
<br>-- has shown that by structuring a Schnorr signature correctly, that
<br>Schnorr signature will be the hash of the spending transaction (see
<br>our paper for how we adapt this to our setting). At very high level
<br>our covenant works as follows:
<br>
<br>1. Get sighash of spending transaction onto stack
<br>2. Use equivalence check to show that small script encoded sighash is
<br>the same as the sighash we have on the stack
<br>3. Open the sighash in small script by showing bytes pushed on stack
<br>by the spending transaction hash to sighash are bytes of the spending
<br>transaction. Now we have the bytes of the spending transaction on the
<br>stack.
<br>4. Use Small Script to enforce covenant on the bytes of the spending
<br>transaction.
<br>
<br>See paper for full details. Thanks,
<br>Ethan
<br></blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/fc031fe3-444c-446d-a5c1-f2d7a430b478n%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/fc031fe3-444c-446d-a5c1-f2d7a430b478n%40googlegroups.com</a>.<br />

------=_Part_359265_414869183.1731433094970--

------=_Part_359264_719006925.1731433094970--