diff options
author | Salvatore Ingala <salvatore.ingala@gmail.com> | 2022-11-10 10:42:30 +0100 |
---|---|---|
committer | bitcoindev <bitcoindev@gnusha.org> | 2022-11-10 09:42:47 +0000 |
commit | 9d6cdf0045df50addd0f3cde2909f997da97289e (patch) | |
tree | 2f78c5c48837acc2cdd0b58ce2f8efef6c08b079 | |
parent | 5bd9518a3770cdadf81c2dd9f5538619099a5547 (diff) | |
download | pi-bitcoindev-9d6cdf0045df50addd0f3cde2909f997da97289e.tar.gz pi-bitcoindev-9d6cdf0045df50addd0f3cde2909f997da97289e.zip |
Re: [bitcoin-dev] Merkleize All The Things
-rw-r--r-- | 22/6ef9cb5c8a08541491a314edad69662f697a11 | 368 |
1 files changed, 368 insertions, 0 deletions
diff --git a/22/6ef9cb5c8a08541491a314edad69662f697a11 b/22/6ef9cb5c8a08541491a314edad69662f697a11 new file mode 100644 index 000000000..1190f7bc5 --- /dev/null +++ b/22/6ef9cb5c8a08541491a314edad69662f697a11 @@ -0,0 +1,368 @@ +Return-Path: <salvatore.ingala@gmail.com> +Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) + by lists.linuxfoundation.org (Postfix) with ESMTP id 62BD9C002D + for <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 10 Nov 2022 09:42:45 +0000 (UTC) +Received: by mail-lf1-x135.google.com with SMTP id g12so2139855lfh.3 + for <bitcoin-dev@lists.linuxfoundation.org>; + 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: <CAMhCMoH9uZPeAE_2tWH6rf0RndqV+ypjbNzazpFwFnLUpPsZ7g@mail.gmail.com> + <Vbb1PZfBzm6JBddqNIfikVE2G1fDmObt0BBt2BqhmHV_Tx7KLGU5SSQPPp0OaLZHAKrkKobA2f60tX4TOl996aE9ds1tZWaGAHbSr9wu5r0=@protonmail.com> +In-Reply-To: <Vbb1PZfBzm6JBddqNIfikVE2G1fDmObt0BBt2BqhmHV_Tx7KLGU5SSQPPp0OaLZHAKrkKobA2f60tX4TOl996aE9ds1tZWaGAHbSr9wu5r0=@protonmail.com> +From: Salvatore Ingala <salvatore.ingala@gmail.com> +Date: Thu, 10 Nov 2022 10:42:30 +0100 +Message-ID: <CAMhCMoErkp_i3Ho482B91Vects=r98jT_6hyy7F84CVw8f=79A@mail.gmail.com> +To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> +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 <bitcoin-dev.lists.linuxfoundation.org> +List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> +List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> +List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> +List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> +List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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 <ZmnSCPxj@protonmail.com> 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 <bram@chia.net> 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 <pete@petertodd.org> 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 <dave@dtrt.org> 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 + +<div dir=3D"ltr"><div>Hi ZmnSCPxj, Bram, Peter, David,</div><div><br></div>= +<div>Thanks for all your comments; replies below.<br></div><div><br></div><= +div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Tue, 8 N= +ov 2022 at 13:01, ZmnSCPxj <<a href=3D"mailto:ZmnSCPxj@protonmail.com">Z= +mnSCPxj@protonmail.com</a>> wrote:<br></div><blockquote class=3D"gmail_q= +uote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,2= +04);padding-left:1ex">Modulo bugs, operator error, misconfigurations, and o= +ther irrationalities of humans.<br></blockquote><div><br></div><div>I agree= + that making footguns impossible is a much more difficult problem to solve!= +</div><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px = +0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> +Rather than get taptree from the stack, just use the same taptree as in the= + revelation of the P2TR.<br> +This removes the need to include quining and similar techniques: just do th= +e quining in the SCRIPT interpreter.<br></blockquote><div><br></div><div>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.<br><br></div><div>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.</div><di= +v>=C2=A0</div><div>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.</d= +iv><div><br></div><div><br><div dir=3D"ltr" class=3D"gmail_attr">On Wed, 9 = +Nov 2022 at 00:34, Bram Cohen <<a href=3D"mailto:bram@chia.net">bram@chi= +a.net</a>> wrote:</div><blockquote class=3D"gmail_quote" style=3D"margin= +:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"= +><div dir=3D"ltr"><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmai= +l_attr">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></div><= +/div></blockquote><div><br>I actually struggle to find constructions that a= +re _not_ possible using such covenants; do you have any concrete example?<b= +r>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.</div><div><br></div><blockquote class=3D"gmail_qu= +ote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,20= +4);padding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_quote"><div></div= +><div>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.</div></div></div></blockquot= +e><div><br></div><div>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.</div><div>= +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.</div><div><br></div><div>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.</div></div><div><br></div><div><br></div><div><div dir=3D"ltr= +" class=3D"gmail_attr">On Wed, 9 Nov 2022 at 13:07, Peter Todd <<a href= +=3D"mailto:pete@petertodd.org">pete@petertodd.org</a>> wrote:<br></div><= +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<br>is arguably a mistake: they allow for degen= +erate, weak, security modes like SPV<br>that aren't clearly good for Bi= +tcoin as a whole.<br></blockquote></div><div><br></div><div>I disagree, as = +the title of this thread suggests! :)</div><div>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.</div><div><br></div><div><br></div><div><div dir=3D= +"ltr" class=3D"gmail_attr">On Thu, 10 Nov 2022 at 08:39, David A. Harding &= +lt;<a href=3D"mailto:dave@dtrt.org">dave@dtrt.org</a>> wrote:</div><bloc= +kquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:= +1px solid rgb(204,204,204);padding-left:1ex">> 1. Alice posts the statem= +ent =E2=80=9Cf(x) =3D y=E2=80=9D.<br>> 2. After a challenge period, if n= +o challenge occurs, Alice is free to<br>> continue and unlock the funds;= + the statement is true.<br>> 3. At any time before the challenge period = +expires, Bob can start a<br>> challenge: =E2=80=9Cactually, f(x) =3D z= +=E2=80=9D.<br><br>That looks to me very similar to Gregory Maxwell's sc= +ript from[1]<br></blockquote><div><br></div><div>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.<br><br>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].<br><br></div><div>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.<br><br>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.<br>= +<br>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.</div><div><br>I hope this=C2=A0clarifies the=C2=A0role of fra= +ud proofs in the construction.</div><div><br></div><div>Best,</div><div>Sal= +vatore<br><br><br>[*] - I'm not suggesting using the bitcoin=C2=A0block= +chain to play chess games, but it is a convenient academic example :)<br>[*= +*] - Pending someone more expert to double check that nothing is missing!<b= +r><br></div><div>[1] -=C2=A0<a href=3D"https://coinpool.dev">https://coinpo= +ol.dev</a></div></div><div>[2] -=C2=A0<a href=3D"https://bitcoinrollups.org= +">https://bitcoinrollups.org</a></div></div></div> + +--00000000000035492105ed1a9815-- + |