Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 62BD9C002D for ; Thu, 10 Nov 2022 09:42:47 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 42BA04035A for ; Thu, 10 Nov 2022 09:42:47 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 42BA04035A Authentication-Results: smtp4.osuosl.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20210112 header.b=Wr8AOIlL X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.098 X-Spam-Level: X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 9U5F1Q21ag6m for ; Thu, 10 Nov 2022 09:42:45 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 2A100402E8 Received: from mail-lf1-x135.google.com (mail-lf1-x135.google.com [IPv6:2a00:1450:4864:20::135]) by smtp4.osuosl.org (Postfix) with ESMTPS id 2A100402E8 for ; Thu, 10 Nov 2022 09:42:45 +0000 (UTC) Received: by mail-lf1-x135.google.com with SMTP id g12so2139855lfh.3 for ; Thu, 10 Nov 2022 01:42:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=/Twl21cZ0opDsu+eciK8ie7DHRxrxQkrHWxOjmNffuM=; b=Wr8AOIlL2K7IO37+/uPrmRs4NhhrHFYv+QyTlgz/D9fz+qKB9NS5Z3nnSMtmUOcPq2 b9ennaRR+my2LL/rdDFVKUTh6iublc1rJmgoXh5GvoIsE2OT2CB68p0YR9xG0cuNrwhC nFZ1A7YVr3W9ua+ojMz7K4chWpBsTiheKbkSmD5ANDLQcv60pKEwryS7r1+QRbspI6sP c/MgCfl2DiPGjZlRws9gNE7rpL6FXPYeXKveWI4/s2hRg53yQOpsBUhUdCXFkEQi3j04 i3G/26KjFxBmMMhx6RZLWaMkD+qkUxhhJxuC/aqmhcskiyFcoXG6Z4/xAm6KFuAn3lnC 1sRg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=/Twl21cZ0opDsu+eciK8ie7DHRxrxQkrHWxOjmNffuM=; b=2QJyINVOH4EXldwO9g4YOAJrZAcNvPkM9ycewlItnLcAEv5DMQJ155Q1w+E38oKZ8/ 8AbJcMFxZ7nKJPF6mSzLyK21BMAu0ZzE9DHPMd+W1iLOuQ1wbKNcJcDij9HuY9ADzynt YftzDPRig06xfjHqv0Z5XItqKGZWKFGzDYxsxAAZW1+SjvSGl6877rOal5cybklu3rVL fMvpfj28JRanh1wD7iAuXxXV0C25v1drIod7CJ5oTH9GWbV96vPacAlRch+hOWOxMP2w qeYindAqTjLewBqxBXjwH7H8Uu87H2ndb4778cEOGXZlcu882gLSx12lhZBLAmJTfA30 jKxg== X-Gm-Message-State: ACrzQf3ZbQIgQH4rhOO8JvZ8Phg3BUBmkmWdub2HUCLGCixl4yNoWBZB EKIhqq86Kl8Rk9HRYsp1HUzs1sLMJuV7RptpdccQ0AMUwrU= X-Google-Smtp-Source: AMsMyM57/CRTUhiJl8rwU7ivDTv0mUoJ48oyxWQF5BnFTaaikeUG2pfB4BdWMCJ6P/2K0XQEGZnbkqeBdZARokYLHUs= X-Received: by 2002:ac2:59cc:0:b0:4a0:5393:3791 with SMTP id x12-20020ac259cc000000b004a053933791mr21420020lfn.495.1668073362113; Thu, 10 Nov 2022 01:42:42 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Salvatore Ingala Date: Thu, 10 Nov 2022 10:42:30 +0100 Message-ID: To: Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="00000000000035492105ed1a9815" X-Mailman-Approved-At: Thu, 10 Nov 2022 14:49:37 +0000 Subject: Re: [bitcoin-dev] Merkleize All The Things X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 10 Nov 2022 09:42:47 -0000 --00000000000035492105ed1a9815 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi ZmnSCPxj, Bram, Peter, David, Thanks for all your comments; replies below. On Tue, 8 Nov 2022 at 13:01, ZmnSCPxj wrote: > Modulo bugs, operator error, misconfigurations, and other irrationalities > of humans. > I agree that making footguns impossible is a much more difficult problem to solve! Rather than get taptree from the stack, just use the same taptree as in the > revelation of the P2TR. > This removes the need to include quining and similar techniques: just do > the quining in the SCRIPT interpreter. > That's a possibility; I suspect it would be less efficient for many contracts (in particular, when the total number of states in the FSM is relatively large, but each of them has only few valid transitions). We could always allow both variants. Another reason I preferred to present it in this way is to show that it is possible to limit the design to covenants where recursion is not allowed / limited; I don't personally think recursion is bad at this time =E2=88=92 b= ut the covenants (and the protocol for fraud challenges) do not require it in order to be useful. Anyway, I suggested some opcodes only as a sketch. I'm not knowledgeable enough to suggest the best design, and maybe it will be easier to compare several variants once we implement something on top. On Wed, 9 Nov 2022 at 00:34, Bram Cohen wrote: > Hash chained covenants in general all have about the same plateau of > functionality, which seems roughly reasonable to add to Bitcoin as it is > today but suffer from being limited and hence likely only a stepping ston= e > to greater functionality and unless whatever's put in now cleanly extends > to supporting more in the future it's likely to turn into a legacy > appendage which has to be supported. So my generic suggestion for this so= rt > of thing is that it should be proposed along with a plan for how it could > be extended to support full-blown covenants in the future. > I actually struggle to find constructions that are _not_ possible using such covenants; do you have any concrete example? That would be very interesting in order to correctly classify the expressive power of UTXO+Script+covenants when compared to the "Turing-complete"+stateful models. Another probably unhelpful bit of feedback I have is that Bitcoin should > probably be taking verkle trees seriously because those can have > substantially lower size/cost/weight than merkle trees. That doesn't just > apply to this proposal, but to Bitcoin in general, which doesn't seem to > have any serious verkle tree proposals to date. > I am not an expert in Verkle trees, but I think the efficiency gain (if any) is not that interesting for many of the applications I'm suggesting, as most Merkle trees would be quite small. Therefore, I agree with Peter that the additional complexity might not be worth it at this time; if applications requiring large Merkle trees arise in practice, Verkle trees could always be added in the future as an optimization. Moreover, Verkle trees, or even any risky/fancy cryptography, could be used in layer-2 solutions enabled by the covenant, without impacting any funds not locked in the covenant in case of disasters. On Wed, 9 Nov 2022 at 13:07, Peter Todd wrote: > Particularly since even having merkle trees in Bitcoin > is arguably a mistake: they allow for degenerate, weak, security modes > like SPV > that aren't clearly good for Bitcoin as a whole. > I disagree, as the title of this thread suggests! :) Thanks to Merkle trees, we'll be able to keep layer 1 extremely light, so everyone can run a full node =E2=88=92 while all the complexity of fancy constructions is pushed to the application layer. On Thu, 10 Nov 2022 at 08:39, David A. Harding wrote: > > 1. Alice posts the statement =E2=80=9Cf(x) =3D y=E2=80=9D. > > 2. After a challenge period, if no challenge occurs, Alice is free to > > continue and unlock the funds; the statement is true. > > 3. At any time before the challenge period expires, Bob can start a > > challenge: =E2=80=9Cactually, f(x) =3D z=E2=80=9D. > > That looks to me very similar to Gregory Maxwell's script from[1] > Zero-Knowledge contingent payments do indeed solve the problem more elegantly in the specific case where swapping Alice's knowledge for x with a payment from Bob is the entire smart contract. The covenant adds the ability to carry over some sort of state. For example, imagine Alice and Bob want to play a game of chess, and the winner takes all the money [*]. The "state" in the covenant would be the entire chessboard, and a valid transition is a valid chess move. The covenant enforces that the game proceeds according to the rules, by only allowing correct updates to the "state". Moreover, the parties participating to a covenant don't necessarily need to be decided in advance, which is crucial for constructions like coinpool [1]= . Note that no this does not require any fraud proof, as the rules of chess are simple enough that each "transition" is a simple enough function. In fact, many contracts might not require fraud proofs at all. The point of the chapter on fraud proof is to prove that full generality in expressive power (that is: any state transition you can think of) is possible, as whenever a complex transition is required =E2=88=92 one could = instead replace it with the optimistic protocol (Alice makes a claim, counterparties can challenge if the claim is wrong). That allows to remove any expensive computation from hitting the blockchain. A particularly interesting example might be rollups (and similar constructions). There, the 'state' represents a separate ledger, and a transition takes the secondary ledger from a valid state to another valid state, using a zero-knowledge proof. In validity rollups [2], the chain is required to actually check the validity proof, which is a very expensive operation (plus, the state-of-the-art requires additional cryptographic assumptions in layer 1, as far as I understand). The covenant would allow us[**] to implement optimistic rollups, where the rollup operator just posts the new state and the proof, and other parties have time to challenge it if the proof is wrong. I hope this clarifies the role of fraud proofs in the construction. Best, Salvatore [*] - I'm not suggesting using the bitcoin blockchain to play chess games, but it is a convenient academic example :) [**] - Pending someone more expert to double check that nothing is missing! [1] - https://coinpool.dev [2] - https://bitcoinrollups.org --00000000000035492105ed1a9815 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi ZmnSCPxj, Bram, Peter, David,

=
Thanks for all your comments; replies below.

<= div class=3D"gmail_quote">
On Tue, 8 N= ov 2022 at 13:01, ZmnSCPxj <Z= mnSCPxj@protonmail.com> wrote:
Modulo bugs, operator error, misconfigurations, and o= ther irrationalities of humans.

I agree= that making footguns impossible is a much more difficult problem to solve!=

Rather than get taptree from the stack, just use the same taptree as in the= revelation of the P2TR.
This removes the need to include quining and similar techniques: just do th= e quining in the SCRIPT interpreter.

Th= at's a possibility; I suspect it would be less efficient for many contr= acts (in particular, when the total number of states in the FSM is relative= ly large, but each of them has only few valid transitions). We could always= allow both variants.

Another reason I preferred to prese= nt it in this way is to show that it is possible to limit the design to cov= enants where recursion is not allowed / limited; I don't personally thi= nk recursion is bad at this time =E2=88=92 but the covenants (and the proto= col for fraud challenges) do not require it in order to be useful.
=C2=A0
Anyway, I suggested some opcodes only as a sketch. I'= ;m not knowledgeable enough to suggest the best design, and maybe it will b= e easier to compare several variants once we implement something on top.


On Wed, 9 = Nov 2022 at 00:34, Bram Cohen <bram@chi= a.net> wrote:
Hash chained covenants in general all have about=C2=A0the same plat= eau of functionality, which seems roughly reasonable to add to Bitcoin as i= t is today but suffer from being limited and hence likely only a stepping s= tone to greater functionality and unless whatever's put in now cleanly = extends to supporting more in the future it's likely to turn into a leg= acy appendage which has to be supported. So my generic suggestion for this = sort of thing is that it should be proposed along with a plan for how it co= uld be extended to support full-blown covenants in the future.
<= /div>

I actually struggle to find constructions that a= re _not_ possible using such covenants; do you have any concrete example?That would be very interesting in order to correctly classify the express= ive power of UTXO+Script+covenants when compared to the "Turing-comple= te"+stateful models.

Another probably unhelpful bit of feedback I have is that Bitcoin sho= uld probably be taking verkle trees seriously because those can have substa= ntially lower size/cost/weight than merkle trees. That doesn't just app= ly to this proposal, but to Bitcoin in general, which doesn't seem to h= ave any serious verkle tree proposals to date.

I am not an expert in Verkle trees, but I think the e= fficiency gain (if any) is not that interesting for many of the application= s I'm suggesting, as most Merkle trees would be quite small.
= Therefore, I agree with=C2=A0Peter that the additional complexity might not= be worth it at this time; if applications requiring large Merkle trees ari= se in practice, Verkle trees could always be added in the future as an opti= mization.

Moreover, Verkle trees, or even any risk= y/fancy cryptography, could be used in layer-2 solutions enabled by the cov= enant,=C2=A0without impacting any funds not locked in the covenant in case = of disasters.


On Wed, 9 Nov 2022 at 13:07, Peter Todd <pete@petertodd.org> wrote:
<= blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l= eft:1px solid rgb(204,204,204);padding-left:1ex">Particularly since even ha= ving merkle trees in Bitcoin
is arguably a mistake: they allow for degen= erate, weak, security modes like SPV
that aren't clearly good for Bi= tcoin as a whole.

I disagree, as = the title of this thread suggests! :)
Thanks to Merkle trees, we&= #39;ll be able to keep layer 1 extremely light, so everyone can run a full = node =E2=88=92 while all the complexity of fancy constructions is pushed to= the application layer.


On Thu, 10 Nov 2022 at 08:39, David A. Harding &= lt;dave@dtrt.org> wrote:
> 1. Alice posts the statem= ent =E2=80=9Cf(x) =3D y=E2=80=9D.
> 2. After a challenge period, if n= o challenge occurs, Alice is free to
> continue and unlock the funds;= the statement is true.
> 3. At any time before the challenge period = expires, Bob can start a
> challenge: =E2=80=9Cactually, f(x) =3D z= =E2=80=9D.

That looks to me very similar to Gregory Maxwell's sc= ript from[1]

Zero-Knowledge contingent = payments do indeed solve the problem more elegantly in the specific case wh= ere swapping Alice's knowledge for x with a payment from Bob is the ent= ire smart contract.

The covenant adds the ability to carry over some= sort of state. For example, imagine Alice and Bob want to play a game of c= hess,=C2=A0and the winner takes=C2=A0all the money [*]. The "state&quo= t; in the covenant would be the entire chessboard, and a valid transition i= s a valid chess move. The covenant enforces that the game proceeds accordin= g to the rules, by only allowing correct updates to the "state".<= br>Moreover, the parties participating to a covenant don't necessarily = need to be decided in advance, which is crucial for constructions like coin= pool [1].

Note that no this does not require any fraud pr= oof, as the rules of chess are simple enough that each "transition&quo= t; is a simple enough function. In fact, many contracts might not require f= raud proofs at all.

The point of the chapter on fraud proof is to pr= ove that full generality in expressive power (that is: any state transition= you can think of) is possible, as whenever a complex transition is require= d =E2=88=92 one could instead replace it with the optimistic protocol (Alic= e makes a claim, counterparties can challenge if the claim is wrong). That = allows to remove any expensive computation from hitting the blockchain.
=
A particularly interesting example might be rollups (and similar constr= uctions). There, the 'state' represents a separate ledger, and a tr= ansition takes the secondary ledger from a valid state to another valid sta= te, using a zero-knowledge proof. In validity rollups [2], the chain is req= uired to actually check the validity proof, which is a very expensive opera= tion (plus, the state-of-the-art requires additional cryptographic assumpti= ons in layer 1, as far as I understand). The covenant would allow us[**] to= implement optimistic rollups, where the rollup operator just posts the new= state and the proof, and other parties have time to challenge it if the pr= oof is wrong.

I hope this=C2=A0clarifies the=C2=A0role of fra= ud proofs in the construction.

Best,
Sal= vatore


[*] - I'm not suggesting using the bitcoin=C2=A0block= chain to play chess games, but it is a convenient academic example :)
[*= *] - Pending someone more expert to double check that nothing is missing!
--00000000000035492105ed1a9815--