Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id EF91CC0032 for ; Fri, 15 Sep 2023 00:23:45 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id CB48661166 for ; Fri, 15 Sep 2023 00:23:45 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org CB48661166 Authentication-Results: smtp3.osuosl.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20221208 header.b=S7D7h48N 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 smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id IAYV05AMvM9J for ; Fri, 15 Sep 2023 00:23:44 +0000 (UTC) Received: from mail-io1-xd31.google.com (mail-io1-xd31.google.com [IPv6:2607:f8b0:4864:20::d31]) by smtp3.osuosl.org (Postfix) with ESMTPS id 2C44460E80 for ; Fri, 15 Sep 2023 00:23:44 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 2C44460E80 Received: by mail-io1-xd31.google.com with SMTP id ca18e2360f4ac-792717ef3c9so54892539f.3 for ; Thu, 14 Sep 2023 17:23:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1694737423; x=1695342223; darn=lists.linuxfoundation.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=siHmN9UrL161y2CRva0WhFJM/Rtliejb26v7teKwpqE=; b=S7D7h48N10h9AaVwFb0CREfGTRKCb6jlYJyOIyJRZA6lE2GvZDppsCGG9hXpfO0Svg L0Ee+xSeihoMC3UimX1VQDKh7GLHLYowoV+BWAY3A948RyCb2wZZKxo4I59RDy0v62VS la9UrdNEr02c6AO5T/LNMdacYbfSdokBy8RWtkKCRuyvwCUMAcj5iy36ry1faPA/yyNy 7dDiLbSfpLrPGsRXsJk9w/wvCV7Qx06+LVTGxkFx3QES5kkSLNkkCP8302VrtF+fs3SO JjwVxjN/XZr0LMLT5/pgibc6+XXegEvAnMaovvsveBq5EvpCYhk6+Q1GZ6nTpzTWHX5u T7Jg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1694737423; x=1695342223; h=cc: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=siHmN9UrL161y2CRva0WhFJM/Rtliejb26v7teKwpqE=; b=KvPQNulwTb6aFF+ZCZC0CPBGu6KFSnokZkxQLwJ5SsBO1+WPHyB2ygZJnpP+gnjOvH zB9I3ZpvwG4Gc3B56g01hS2uC9K9N9aVtVFJF4g6npH/V736xFWGMDpBxSKkCEeWqg+E pG22aIiX4/Kiv5F8Ohkmp3kH/L2ngVC7kBCOxLNnY0N1pe1yy/s25AVsRA5y6gsNxEda u5JjJVsMh5GFVd3eZbZZzm52myyR5RVOcNwrcCdI/XekMT1UPNqERntmIASYi9+oXHaY qZ4tH+b+zCb9aAs6iakU9TiH5hYiVlKiQrCItkQu/oamiQ7e+cB0lqN+YSBGvrk32566 16/g== X-Gm-Message-State: AOJu0YxuUfdtMPhRbgoZeb/jfG2PsHRDD9dfOFVu79/KOKYpnZRNJ1k2 44OksK1FUbdUYAAmCYdJTmyng0yM6fwSh6+hFmr/GwxU9QCiIw== X-Google-Smtp-Source: AGHT+IFOuKIVqPyy0dJObKeOlcXIkcDwYWWAHU/Wp9sMNNwYhd24MivzCJdtsrMvEh57WXl40K2Yn4jB5KRCnZ0PhKw= X-Received: by 2002:a05:6602:220b:b0:784:314f:8d68 with SMTP id n11-20020a056602220b00b00784314f8d68mr65707ion.1.1694737423030; Thu, 14 Sep 2023 17:23:43 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Antoine Riard Date: Fri, 15 Sep 2023 01:23:31 +0100 Message-ID: To: Salvatore Ingala Content-Type: multipart/alternative; boundary="000000000000165ff306055aceca" X-Mailman-Approved-At: Fri, 15 Sep 2023 13:48:53 +0000 Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Concrete MATT opcodes 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: Fri, 15 Sep 2023 00:23:46 -0000 --000000000000165ff306055aceca Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Salvatore, Thanks for the additional insights. > At this time, my goal is to facilitate maximum experimentation; it's safe to open Pandora's box in a sandbox, as that's the only way to know if it's empty. > Concerns will of course need to be answered when a soft-fork proposal is made, and restrictions can be added if necessary. Thinking more, I wonder if the following conjecture could be sketched out e.g "any utxo-inspecting based miners bribing contracts know a `counter-bribing` contract that can be offered by a honest Lightning channel counterparty". UTXO-inspection can be leveraged to offer "fee bounties" if a Lightning funding UTXO is unspent after X and there is some ongoing anomaly suspected (e.g miner-censorship) > Cross-input introspection seems very likely to have use cases; for example, I drafted some notes on how it could be used to implement eltoo-style replacement for lightning > (or arbitrary state channels) when combined with ANYONECANPAY: https://gist.github.com/bigspider/041ebd0842c0dcc74d8af087c1783b63 . Although, it would be much ? > easier with CCV+CHECKSIGFROMSTACK, and in that case cross-input introspection is not needed. I looked at the gist and the sequence of transactions is still a bit unclear to me. From my understanding: - Alice and Bob both creates virtual UTXOs - the asymmetric update transactions are valid at the condition of spending a lower-state number virtual UTXO - any new update transaction is committing to an on-chain virtual UTXO of a higher state number If I'm correct the construction sounds work to me, however I think it sounds slightly less economically efficient than OG Eltoo (as presented in 2018 paper). > Similarly, some people raised concerns with recursivity of covenant opcodes; that also could be artificially limited in CCV if desired, but it would prevent some use cases. I think this is still a good design question if we could prevent recursive covenants that could be hijacked by censorship adversaries. Maybe recursivity-enablement could be safeguarded on a timelock allowing escape out of the recursivity after X blocks. > The flags alter the semantic behavior of the opcode; perhaps you rather refer to generalizing the index parameter so that it can refer to a group of inputs/outputs, instead? Yes, the link about sighash_group-like talk about the use-case of (non-interactive) aggregation of pre-signed LN commitment transactions with a single pair of input / output iirc. Witness space efficiency benefit for LSP and Lightning nodes with hundreds of channels to be closed. > How would these "tags" interact with CHECKCONTRACTVERIFY? I don't quite understand the use case. https://github.com/bitcoin/bips/pull/1381 and let's say you have `OP_PUSH_ANNEX_TAG(t)` where `t` is the type of tag queried. I wonder if you could re-build a more powerful CHECKSIGFROMSTACK combined with CHECKCONTRACTVERIFY. > More generic introspection might not fit well within the semantics of CCV, but it could (and probably should) be added with separate opcodes. I think more witness space efficiency could be obtained by casting the CCV hash as a merkle tree and traverse it a la g'root https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016249.ht= ml > I personally find OP_CHECKSIGFROMSTACK more natural when thinking about constructions with CCV; but most likely either would work here. I agree it's more natural to leverage OP_CHECKSIGFROMSTACK to enable amount transfer validation, however far less efficient in terms of witness space. > The DeferredChecks added specifically for CCV has negligible cost, as it's just O(n_outputs + n_ccv_out) where n_ccv_out is the number of execute= d > OP_CHECKCONTRACTVERIFY opcodes (transaction-wide) that check the output amount. At first sight, n_outputs + n_ccv_out sounds indeed cheap. Though I think this is yet to see how it interferes with spending script max opcode limits and max transaction size. Best, Antoine Le ven. 18 ao=C3=BBt 2023 =C3=A0 16:08, Salvatore Ingala a =C3=A9crit : > Hi Antoine, > > Thanks for your comments and insights. > > On Mon, 14 Aug 2023 at 05:01, Antoine Riard > wrote: > >> I think cross-input inspection (not cross-input signature >> aggregation which is different) is opening a pandora box in terms of >> "malicious" off-chain contracts than one could design. E.g miners bribin= g >> contracts to censor the confirmation of time-sensitive lightning channel >> transactions, where the bribes are paid on the hashrate distribution of >> miners during the previous difficulty period, thanks to the coinbase pub= key. >> > > At this time, my goal is to facilitate maximum experimentation; it's safe > to open Pandora's box in a sandbox, as that's the only way to know if it'= s > empty. > Concerns will of course need to be answered when a soft-fork proposal is > made, and restrictions can be added if necessary. > > Cross-input introspection seems very likely to have use cases; for > example, I drafted some notes on how it could be used to implement > eltoo-style replacement for lightning (or arbitrary state channels) when > combined with ANYONECANPAY: > https://gist.github.com/bigspider/041ebd0842c0dcc74d8af087c1783b63 > . > Although, it would be much easier with CCV+CHECKSIGFROMSTACK, and in that > case cross-input introspection is not needed. > > Similarly, some people raised concerns with recursivity of covenant > opcodes; that also could be artificially limited in CCV if desired, but i= t > would prevent some use cases. > > I have some thoughts on why the fear of covenants might generally be > unjustified, which I hope to write in long form at some point. > > More than a binary flag like a matrix could be introduced to encode subse= t >> of introspected inputs /outputs to enable sighash_group-like semantic: >> >> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019243= .html >> > > The flags alter the semantic behavior of the opcode; perhaps you rather > refer to generalizing the index parameter so that it can refer to a group > of inputs/outputs, instead? > I'm not aware of the use cases at this time, feel free to expand further. > > >> Or even beyond a matrix, it could be a set of "tags". There could be a >> generalized tag for unstructured data, and another one for bitcoin >> transaction / script data types (e.g scriptpubkey, amount, nsequence, >> merkle branch) that could be fetched from the taproot annex. >> > > How would these "tags" interact with CHECKCONTRACTVERIFY? I don't quite > understand the use case. > > I think this generic framework is interesting for joinpool / coinpool / >> payment pool, as you can check that any withdrawal output can be committ= ed >> as part of the input scriptpubkey, and spend it on >> blessed-with-one-participant-sig script. There is still a big open quest= ion >> if it's efficient in terms of witness space consumed. >> > > More generic introspection might not fit well within the semantics of CCV= , > but it could (and probably should) be added with separate opcodes. > > That said, I still think you would need at least ANYPREVOUT and more >> malleability for the amount transfer validation as laid out above. >> > > I personally find OP_CHECKSIGFROMSTACK more natural when thinking about > constructions with CCV; but most likely either would work here. > > Looking on the `DeferredCheck` framework commit, one obvious low-level >> concern is the DoS risk for full-nodes participating in transaction-rela= y, >> and that maybe policy rules should be introduced to keep the worst-CPU >> input in the ranges of current transaction spend allowed to propagate on >> the network today. >> > > Of course, care needs to be taken in general when designing new deferred > checks, to avoid any sort of quadratic validation cost. > The DeferredChecks added specifically for CCV has negligible cost, as it'= s > just O(n_outputs + n_ccv_out) where n_ccv_out is the number of executed > OP_CHECKCONTRACTVERIFY opcodes (transaction-wide) that check the output > amount. > > Best, > Salvatore > > --000000000000165ff306055aceca Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Salvatore,

Thanks for the additional= insights.

> At this time, my=C2=A0goal is to f= acilitate maximum experimentation; it's safe to open Pandora's box = in a sandbox, as that's the only way to know if it's empty.
>= Concerns will of course need to be answered when a soft-fork proposal is m= ade, and restrictions can be added if necessary.

Thinking more, I wonder if the following conjecture could be sketched ou= t e.g "any utxo-inspecting based miners bribing contracts know a `coun= ter-bribing` contract that can be offered by a honest Lightning channel cou= nterparty".

UTXO-inspection can be leveraged = to offer "fee bounties" if a Lightning funding UTXO is unspent af= ter X and there is some ongoing anomaly suspected (e.g miner-censorship)=C2= =A0

> Cross-input introspection seems very like= ly to have use cases; for example, I drafted some notes on how it could be = used to implement eltoo-style replacement for lightning
> (or = arbitrary state channels) when combined with ANYONECANPAY:=C2=A0=C2=A0https://gist.github.com/bigspider/041ebd0842c0dcc74d8af08= 7c1783b63. Although, it would be much ?
> easier with CCV+= CHECKSIGFROMSTACK, and in that case cross-input introspection=C2=A0is not n= eeded.

I looked at the gist and the sequence o= f transactions is still a bit unclear to me. From my understanding:
- Alice and Bob both creates virtual UTXOs
- the asymmetric up= date transactions are valid at the condition of spending a lower-state numb= er virtual UTXO
- any new update transaction is committing to an = on-chain virtual UTXO of a higher state number

If = I'm correct the construction sounds work to me, however I think it soun= ds slightly less economically efficient than OG Eltoo (as presented in 2018= paper).

> Similarly, some people raised concer= ns with recursivity of covenant opcodes; that also could be artificially li= mited in CCV if desired, but it would prevent some use cases.

I think this is still a good design question if we could pr= event recursive covenants that could be hijacked by censorship adversaries.= Maybe recursivity-enablement could be safeguarded on a timelock allowing e= scape out of the recursivity after X blocks.

> = The flags alter the semantic behavior of the opcode; perhaps you rather ref= er to generalizing the index parameter so that it can refer to a group of i= nputs/outputs, instead?

Yes, the link about sighash_group= -like talk about the use-case of (non-interactive) aggregation of pre-signe= d LN commitment transactions with a single pair of input / output iirc. Wit= ness space efficiency=C2=A0benefit for LSP and Lightning nodes with hundred= s of channels to be closed.

> How would th= ese "tags" interact with CHECKCONTRACTVERIFY? I don't quite u= nderstand the use case.

https://github.com/bitcoin/bips/pull/1381 a= nd let's say you have `OP_PUSH_ANNEX_TAG(t)` where `t` is the type of t= ag queried. I wonder if you could re-build a more powerful CHECKSIGFROMSTAC= K=C2=A0combined with CHECKCONTRACTVERIFY.

>= More generic introspection might not fit well within the semantics of CCV,= but it could (and probably should) be added with separate opcodes.

I think more witness space efficiency could be obtain= ed by casting the CCV hash as a merkle tree and traverse it a la g'root= =C2=A0https://lists.linuxfoundation.org/pipermail/bitcoin-de= v/2018-July/016249.html

> I personally find= OP_CHECKSIGFROMSTACK more natural when thinking about constructions with C= CV; but most likely either would work here.

I = agree it's more natural to leverage OP_CHECKSIGFROMSTACK to enable amou= nt transfer validation, however far less efficient in terms of witness spac= e.

> The DeferredChecks added specifically for = CCV has negligible cost, as it's just O(n_outputs=C2=A0+ n_ccv_out) whe= re n_ccv_out=C2=A0is the number of executed
> OP_CHECKCONTRACT= VERIFY opcodes (transaction-wide) that check the output amount.

At first sight, n_outputs=C2=A0+ n_ccv_out sounds indeed = cheap. Though I think this is yet to see how it interferes with spending sc= ript max opcode limits and max transaction size.

B= est,
Antoine

Le=C2=A0ven. 18 ao=C3=BBt 2023 =C3=A0=C2= =A016:08, Salvatore Ingala <salvatore.ingala@gmail.com> a =C3=A9crit=C2=A0:
Hi Antoine,

Thanks f= or your comments and insights.

On Mon, 14 Aug 2023 at 05:01, Antoine Riard &= lt;antoine.ria= rd@gmail.com> wrote:
I think cross-input inspection (not cross-input signature aggregation=C2= =A0which is different) is opening a pandora box in terms of "malicious= " off-chain contracts than one could design. E.g miners bribing contra= cts to censor the confirmation of time-sensitive lightning=C2=A0channel tra= nsactions, where the bribes=C2=A0are paid on the hashrate=C2=A0distribution= of miners during the previous difficulty period, thanks to the coinbase pu= bkey.

At this time, my=C2=A0goal is to fac= ilitate maximum experimentation; it's safe to open Pandora's box in= a sandbox, as that's the only way to know if it's empty.
Concer= ns will of course need to be answered when a soft-fork proposal is made, an= d restrictions can be added if necessary.

Cross-input introsp= ection seems very likely to have use cases; for example, I drafted some not= es on how it could be used to implement eltoo-style replacement for lightni= ng (or arbitrary state channels) when combined with ANYONECANPAY:=C2=A0=C2=A0https://gist.github.com/bigspider/041ebd0842c0dcc74= d8af087c1783b63. Although, it would be much easier with CCV+CHECKSIGFRO= MSTACK, and in that case cross-input introspection=C2=A0is not needed.
<= /div>

Similarly, some people raised concerns with recurs= ivity of covenant opcodes; that also could be artificially limited in CCV i= f desired, but it would prevent some use cases.

I have so= me thoughts on why the fear of covenants=C2=A0might generally be unjustifie= d,=C2=A0which I hope to write in=C2=A0long form at some point.

More than a binary flag like a matr= ix could be introduced to encode subset of introspected inputs /outputs to = enable sighash_group-like semantic:

The flags alter the semanti= c behavior of the opcode; perhaps you rather refer to generalizing the inde= x parameter so that it can refer to a group of inputs/outputs, instead?
= I'm not aware of the use cases at this time, feel free to expand furthe= r.
=C2=A0
Or even bey= ond a matrix, it could be a set of "tags". There could be a gener= alized tag for unstructured data, and another one for bitcoin transaction /= script data types (e.g scriptpubkey, amount, nsequence, merkle branch) tha= t could be fetched from the taproot annex.
How would these "tags" interact with CHECKCONTRACTVER= IFY? I don't quite understand the use case.

I think this generic framework is interesti= ng for joinpool / coinpool / payment pool, as you can check that any withdr= awal output can be committed as part of the input scriptpubkey, and spend i= t on blessed-with-one-participant-sig script. There is still a big open que= stion if it's efficient in terms of witness space consumed.
=

More generic introspection might not fit well within = the semantics of CCV, but it could (and probably should) be added with sepa= rate opcodes.

That said= , I still think you would need at least ANYPREVOUT and more malleability fo= r the amount transfer validation as laid out above.

I personally find OP_CHECKSIGFROMSTACK more natural when thinking= about constructions with CCV; but most likely either would work here.
<= br>
Looking on the `DeferredChe= ck` framework commit, one obvious low-level concern is the DoS risk for ful= l-nodes participating in transaction-relay, and that maybe policy rules sho= uld be introduced to keep the worst-CPU input in the ranges of current tran= saction spend allowed to propagate on the network today.

Of course, care needs to be taken in general when designing = new deferred checks, to avoid any sort of quadratic validation cost.
The= DeferredChecks added specifically for CCV has negligible cost, as it's= just O(n_outputs=C2=A0+ n_ccv_out) where n_ccv_out=C2=A0is the number of e= xecuted OP_CHECKCONTRACTVERIFY opcodes (transaction-wide) that check the ou= tput amount.

Best,
Salvatore

--000000000000165ff306055aceca--