From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 6B9F8C0032 for ; Tue, 26 Sep 2023 15:36:40 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 3976360FA6 for ; Tue, 26 Sep 2023 15:36:40 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 3976360FA6 Authentication-Results: smtp3.osuosl.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=jGv7L+TL 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 VBj64UEKOvK3 for ; Tue, 26 Sep 2023 15:36:38 +0000 (UTC) Received: from mail-il1-x12f.google.com (mail-il1-x12f.google.com [IPv6:2607:f8b0:4864:20::12f]) by smtp3.osuosl.org (Postfix) with ESMTPS id 76BC760BE8 for ; Tue, 26 Sep 2023 15:36:38 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 76BC760BE8 Received: by mail-il1-x12f.google.com with SMTP id e9e14a558f8ab-3512fae02ecso18660055ab.2 for ; Tue, 26 Sep 2023 08:36:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1695742597; x=1696347397; 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=FBQ2ZWW0bk3B9rBFFulZ1LSrPA0mqAGmFas+XeIXazM=; b=jGv7L+TLSfU36B/XCUhVmE+p0+EMDORCxQon+x8JRNeHF13dkxdzCXjEmjLb5tOTYn QD4JQqK+FmMDOBfpo0Ghb45/hB6piuMBU6CV57uq4hZB+MI1o3qpEeC8/b7UynkVtYn2 tpl53JHZPKk+orcu1lxLwlggsAy6BEv7f6yBoXGf/2g0/XUtP3jCLt1r7Mj6OOu+RcUp 8AjOe3HPMiVpU4wFe5qIrzN+q2KBq/tIXLe9zwwsEHYIZHYR1Ee9U2gUhTg+TAeTyDmN 6XE3e5i44kEUfFdrzv0qQYBdn9q++7qJuOTNfT215qdPx+1sPoRlrpmJ2y+D6m3OCku/ SPaQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1695742597; x=1696347397; 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=FBQ2ZWW0bk3B9rBFFulZ1LSrPA0mqAGmFas+XeIXazM=; b=kGdRKCkJzAAMSIiTrwEbGSV2XIsFBzALCUnFWwrgChpQXJaivQtO4AqNoawMwWLKW9 kLaI9l+AiqXkKnLZpU8L9FBXiXWk6Iy1iUGVIAb0qhCVV9fFCCRWMW8y36t7p4wjxuSg YamVizZ3ROIANTEV/lBGDmwWxGGmWDwnTRAy46+aokCjO09mYcaFIZow8lXbjt+6FqZd F27GDpKS+mpTd02/+RhX6WEQgNjBjH+vKZ5QGcUsrHDEpmZkBGG0+cGhOFH3kR6GhG7I BqEV/VZLAHvwKQqeWkstF0Z8Rb6tf0wRT1YJufacecRQ/FQ3KUmRxvSOuLOCD2CIZkaI eAvQ== X-Gm-Message-State: AOJu0YxILD6vi1+IR3cvILKUL3qc2XYQu8A1UteYZ4uo8TdZCNS9pKjP jzF+UwRk4w+DlkMZkRAbcm0PNpVROi/iZT2Q07Q= X-Google-Smtp-Source: AGHT+IEgHS2hqd8i/7pyK1r6SVTVc7LapAtPZDqH+Uh4lEnPzNWyIx8DvHFiIvmDZ1voMK2agN8sSVprzAjJjWu+I38= X-Received: by 2002:a05:6e02:1210:b0:34f:234d:4b5a with SMTP id a16-20020a056e02121000b0034f234d4b5amr9837391ilq.29.1695742597227; Tue, 26 Sep 2023 08:36:37 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Antoine Riard Date: Tue, 26 Sep 2023 16:36:26 +0100 Message-ID: To: ZmnSCPxj Content-Type: multipart/alternative; boundary="000000000000236d2b060644d78a" X-Mailman-Approved-At: Wed, 27 Sep 2023 10:07:37 +0000 Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Solving CoinPool high-interactivity issue with cut-through update of Taproot leaves 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: Tue, 26 Sep 2023 15:36:40 -0000 --000000000000236d2b060644d78a Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Zeeman, See my comments at the time of OP_EVICT original publication. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-February/01993= 9.html "I think in the context of (off-chain) payment pool, OP_EVICT requires participant cooperation *after* the state update to allow a single participant to withdraw her funds. I believe this is unsafe if we retain as an off-chain construction security requirement that a participant should have the unilateral means to enforce the latest agreed upon state at any time during the construction lifetime". I think this level of covenant flexibility is still wished for CoinPool as a fundamental property, and this is offered by TLUV or MERKLESUB. On the other hand, I think OP_EVICT introduces this idea of *subgroup novation* (i.e `K-of-N`) of a PT2R scriptpubkey. To the best of my understanding, I think there is not yet any sound covenant proposal aiming to combine TLUV and EVICT-like semantics in a consistent set of Script primitives to enable "cut-through" updates, while still retaining the key property of unilateral withdraw of promised balances in any-order. I might go to work on crafting one, though for now I'm still interested to understand better if on-chain "cut-through" is the best direction to solve the fundamental high interactivity issue of channel factory and payment pool over punishment-based ideas. Best, Antoine Le mar. 26 sept. 2023 =C3=A0 07:51, ZmnSCPxj a = =C3=A9crit : > Good morning Antoine, > > Does `OP_EVICT` not fit? > > > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-February/019= 926.html > > Regards, > ZmnSCPxj > > > Sent with Proton Mail secure email. > > ------- Original Message ------- > On Monday, September 25th, 2023 at 6:18 PM, Antoine Riard via bitcoin-dev= < > bitcoin-dev@lists.linuxfoundation.org> wrote: > > > > Payment pools and channel factories are afflicted by severe > interactivity constraints worsening with the number of users owning an > off-chain balance in the construction. The security of user funds is > paramount on the ability to withdraw unilaterally from the off-chain > construction. As such any update applied to the off-chain balances requir= es > a signature contribution from the unanimity of the construction users to > ensure this ability is conserved along updates. > > As soon as one user starts to be offline or irresponsive, the updates o= f > the off-chain balances must have to be halted and payments progress are > limited among subsets of 2 users sharing a channel. Different people have > proposed solutions to this issue: introducing a coordinator, partitioning > or layering balances in off-chain users subsets. I think all those > solutions have circled around a novel issue introduced, namely equivocati= on > of off-chain balances at the harm of construction counterparties [0]. > > > > As ZmnSCPxj pointed out recently, one way to mitigate this equivocation > consists in punishing the cheating pre-nominated coordinator on an extern= al > fidelity bond. One can even imagine more trust-mimized and decentralized > fraud proofs to implement this mitigation, removing the need of a > coordinator [1]. > > > > However, I believe punishment equivocation to be game-theory sound > should compensate a defrauded counterparty of the integrity of its lost > off-chain balance. As one cheating counterparty can equivocate in the > worst-case against all the other counterparties in the construction, one > fidelity bond should be equal to ( C - 1 ) * B satoshi amount, where C is > the number of construction counterparty and B the initial off-chain balan= ce > of the cheating counterparty. > > > > Moreover, I guess it is impossible to know ahead of a partition or > transition who will be the "honest" counterparties from the "dishonest" > ones, therefore this ( C - 1 ) * B-sized fidelity bond must be maintained > by every counterparty in the pool or factory. On this ground, I think thi= s > mitigation and other corrective ones are not economically practical for > large-scale pools among a set of anonymous users. > > > > I think the best solution to solve the interactivity issue which is > realistic to design is one ruling out off-chain group equivocation in a > prophylactic fashion. The pool or factory funding utxo should be edited i= n > an efficient way to register new off-chain subgroups, as lack of > interactivity from a subset of counterparties demands it. > > > > With CoinPool, there is already this idea of including a user pubkey an= d > balance amount to each leaf composing the Taproot tree while preserving t= he > key-path spend in case of unanimity in the user group. Taproot leaves can > be effectively regarded as off-chain user accounts available to realize > privacy-preserving payments and contracts. > > > > I think one (new ?) idea can be to introduce taproot leaves > "cut-through" spends where multiple leaves are updated with a single > witness, interactively composed by the owners of the spent leaves. This > spend sends back the leaves amount to a new single leaf, aggregating the > amounts and user pubkeys. The user leaves not participating in this > "cut-through" are inherited with full integrity in the new version of the > Taproot tree, at the gain of no interactivity from their side. > > > > Let's say you have a CoinPool funded and initially set with Alice, Bob, > Caroll, Dave and Eve. Each pool participant has a leaf L.x committing to = an > amount A.x and user pubkey P.x, where x is the user name owning a leaf. > > > > Bob and Eve are deemed to be offline by the Alice, Caroll and Dave > subset (the ACD group). > > > > The ACD group composes a cut-through spend of L.a + L.c + L.d. This > spends generates a new leaf L.(acd) leaf committing to amount A.(acd) and > P.(acd). > > > > Amount A.(acd) =3D A.a + A.c + A.d and pubkey P.(acd) =3D P.a + P.c + P= .d. > > > > Bob's leaf L.b and Eve's leaf L.e are left unmodified. > > > > The ACD group generates a new Taproot tree T' =3D L.(acd) + L.b + L.e, > where the key-path K spend including the original unanimity of pool > counterparties is left unmodified. > > > > The ACD group can confirm a transaction spending the pool funding utxo > to a new single output committing to the scriptpubkey K + T'. > > > > From then, the ACD group can pursue off-chain balance updates among the > subgroup thanks to the new P.(acd) and relying on the known Eltoo > mechanism. There is no possibility for any member of the ACD group to > equivocate with Bob or Eve in a non-observable fashion. > > > > Once Bob and Eve are online and ready to negotiate an on-chain pool > "refresh" transaction, the conserved key-path spend can be used to > re-equilibrate the Taproot tree, prune out old subgroups unlikely to be > used and provision future subgroups, all with a compact spend based on > signature aggregation. > > > > Few new Taproot tree update script primitives have been proposed, e.g > [2]. Though I think none with the level of flexibility offered to generat= e > leaves cut-through spends, or even batch of "cut-through" where M subgrou= ps > are willing to spend N leaves to compose P new subgroups fan-out in Q new > outputs, with showing a single on-chain witness. I believe such a > hypothetical primitive can also reduce the chain space consumed in the > occurrence of naive mass pool withdraws at the same time. > > > > I think this solution to the high-interactivity issue of payment pools > and factories shifts the burden on each individual user to pre-commit fas= t > Taproot tree traversals, allowing them to compose new pool subgroups as > fluctuations in pool users' level of liveliness demand it. Pool efficienc= y > becomes the sum of the quality of user prediction on its counterparties' > liveliness during the construction lifetime. Recursive taproot tree spend= s > or more efficient accumulator than merkle tree sounds ideas to lower the > on-chain witness space consumed by every pool in the average > non-interactive case. > > > > Cheers, > > Antoine > > > > [0] > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020370= .html > > [1] > https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-August/004= 043.html > > [2] > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-September/01= 9420.html > --000000000000236d2b060644d78a Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Zeeman,

See my comments at the time = of OP_EVICT original publication.


"I think in the context of = (off-chain) payment pool, OP_EVICT requires
participant cooperati= on *after* the state update to allow a single
participant to with= draw her funds.

I believe this is unsafe if we ret= ain as an off-chain construction security
requirement that a part= icipant should have the unilateral means to enforce
the latest ag= reed upon state at any time during the construction lifetime".

I think this level of covenant flexibility is still wishe= d for CoinPool as a fundamental property, and this is offered by TLUV or ME= RKLESUB.
On the other hand, I think OP_EVICT introduces this idea= of *subgroup novation* (i.e `K-of-N`) of a PT2R scriptpubkey.
To the best of my understanding, I think there is not yet any = sound covenant proposal aiming to combine TLUV and EVICT-like semantics in = a consistent=C2=A0set of Script primitives to enable "cut-through"= ; updates, while still retaining the key property of unilateral withdraw of= promised balances in any-order.

I might go to wor= k on crafting one, though for now I'm still interested to understand be= tter if on-chain "cut-through" is the best direction to solve the= fundamental high interactivity issue of channel factory and payment pool o= ver punishment-based ideas.

Best,
Antoin= e

Le=C2=A0mar. 26 sept. 2023 =C3=A0=C2=A007:51, ZmnSCPxj <ZmnSCPxj@protonmail.com> a =C3= =A9crit=C2=A0:
Good morning Antoine,

Does `OP_EVICT` not fit?

https://lists.linux= foundation.org/pipermail/bitcoin-dev/2022-February/019926.html

Regards,
ZmnSCPxj


Sent with Proton Mail secure email.

------- Original Message -------
On Monday, September 25th, 2023 at 6:18 PM, Antoine Riard via bitcoin-dev &= lt;bitcoin-dev@lists.linuxfoundation.org> wrote:


> Payment pools and channel factories are afflicted by severe interactiv= ity constraints worsening with the number of users owning an off-chain bala= nce in the construction. The security of user funds is paramount on the abi= lity to withdraw unilaterally from the off-chain construction. As such any = update applied to the off-chain balances requires a signature contribution = from the unanimity of the construction users to ensure this ability is cons= erved along updates.
> As soon as one user starts to be offline or irresponsive, the updates = of the off-chain balances must have to be halted and payments progress are = limited among subsets of 2 users sharing a channel. Different people have p= roposed solutions to this issue: introducing a coordinator, partitioning or= layering balances in off-chain users subsets. I think all those solutions = have circled around a novel issue introduced, namely equivocation of off-ch= ain balances at the harm of construction counterparties [0].
>
> As ZmnSCPxj pointed out recently, one way to mitigate this equivocatio= n consists in punishing the cheating pre-nominated coordinator on an extern= al fidelity bond. One can even imagine more trust-mimized and decentralized= fraud proofs to implement this mitigation, removing the need of a coordina= tor [1].
>
> However, I believe punishment equivocation to be game-theory sound sho= uld compensate a defrauded counterparty of the integrity of its lost off-ch= ain balance. As one cheating counterparty can equivocate in the worst-case = against all the other counterparties in the construction, one fidelity bond= should be equal to ( C - 1 ) * B satoshi amount, where C is the number of = construction counterparty and B the initial off-chain balance of the cheati= ng counterparty.
>
> Moreover, I guess it is impossible to know ahead of a partition or tra= nsition who will be the "honest" counterparties from the "di= shonest" ones, therefore this ( C - 1 ) * B-sized fidelity bond must b= e maintained by every counterparty in the pool or factory. On this ground, = I think this mitigation and other corrective ones are not economically prac= tical for large-scale pools among a set of anonymous users.
>
> I think the best solution to solve the interactivity issue which is re= alistic to design is one ruling out off-chain group equivocation in a proph= ylactic fashion. The pool or factory funding utxo should be edited in an ef= ficient way to register new off-chain subgroups, as lack of interactivity f= rom a subset of counterparties demands it.
>
> With CoinPool, there is already this idea of including a user pubkey a= nd balance amount to each leaf composing the Taproot tree while preserving = the key-path spend in case of unanimity in the user group. Taproot leaves c= an be effectively regarded as off-chain user accounts available to realize = privacy-preserving payments and contracts.
>
> I think one (new ?) idea can be to introduce taproot leaves "cut-= through" spends where multiple leaves are updated with a single witnes= s, interactively composed by the owners of the spent leaves. This spend sen= ds back the leaves amount to a new single leaf, aggregating the amounts and= user pubkeys. The user leaves not participating in this "cut-through&= quot; are inherited with full integrity in the new version of the Taproot t= ree, at the gain of no interactivity from their side.
>
> Let's say you have a CoinPool funded and initially set with Alice,= Bob, Caroll, Dave and Eve. Each pool participant has a leaf L.x committing= to an amount A.x and user pubkey P.x, where x is the user name owning a le= af.
>
> Bob and Eve are deemed to be offline by the Alice, Caroll and Dave sub= set (the ACD group).
>
> The ACD group composes a cut-through spend of L.a + L.c + L.d. This sp= ends generates a new leaf L.(acd) leaf committing to amount A.(acd) and P.(= acd).
>
> Amount A.(acd) =3D A.a + A.c + A.d and pubkey P.(acd) =3D P.a + P.c + = P.d.
>
> Bob's leaf L.b and Eve's leaf L.e are left unmodified.
>
> The ACD group generates a new Taproot tree T' =3D L.(acd) + L.b + = L.e, where the key-path K spend including the original unanimity of pool co= unterparties is left unmodified.
>
> The ACD group can confirm a transaction spending the pool funding utxo= to a new single output committing to the scriptpubkey K + T'.
>
> From then, the ACD group can pursue off-chain balance updates among th= e subgroup thanks to the new P.(acd) and relying on the known Eltoo mechani= sm. There is no possibility for any member of the ACD group to equivocate w= ith Bob or Eve in a non-observable fashion.
>
> Once Bob and Eve are online and ready to negotiate an on-chain pool &q= uot;refresh" transaction, the conserved key-path spend can be used to = re-equilibrate the Taproot tree, prune out old subgroups unlikely to be use= d and provision future subgroups, all with a compact spend based on signatu= re aggregation.
>
> Few new Taproot tree update script primitives have been proposed, e.g = [2]. Though I think none with the level of flexibility offered to generate = leaves cut-through spends, or even batch of "cut-through" where M= subgroups are willing to spend N leaves to compose P new subgroups fan-out= in Q new outputs, with showing a single on-chain witness. I believe such a= hypothetical primitive can also reduce the chain space consumed in the occ= urrence of naive mass pool withdraws at the same time.
>
> I think this solution to the high-interactivity issue of payment pools= and factories shifts the burden on each individual user to pre-commit fast= Taproot tree traversals, allowing them to compose new pool subgroups as fl= uctuations in pool users' level of liveliness demand it. Pool efficienc= y becomes the sum of the quality of user prediction on its counterparties&#= 39; liveliness during the construction lifetime. Recursive taproot tree spe= nds or more efficient accumulator than merkle tree sounds ideas to lower th= e on-chain witness space consumed by every pool in the average non-interact= ive case.
>
> Cheers,
> Antoine
>
> [0] https://lists= .linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020370.html
> [1] https://li= sts.linuxfoundation.org/pipermail/lightning-dev/2023-August/004043.html=
> [2] https://l= ists.linuxfoundation.org/pipermail/bitcoin-dev/2021-September/019420.html
--000000000000236d2b060644d78a--