diff options
| author | Johan Torås Halseth <johanth@gmail.com> | 2023-10-05 09:38:24 +0200 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2023-10-05 07:38:38 +0000 |
| commit | 54ac69a4217ab1f1f438e9f3a73caaf1b7ee0722 (patch) | |
| tree | 1f335b435e1cdf94711b8eed87dd93a33487abaf /bf | |
| parent | 7fd6816ff54b79925c499f3784671a1814e48a42 (diff) | |
| download | pi-bitcoindev-54ac69a4217ab1f1f438e9f3a73caaf1b7ee0722.tar.gz pi-bitcoindev-54ac69a4217ab1f1f438e9f3a73caaf1b7ee0722.zip | |
Re: [bitcoin-dev] Solving CoinPool high-interactivity issue with cut-through update of Taproot leaves
Diffstat (limited to 'bf')
| -rw-r--r-- | bf/518dddc480cbb9bf130deef70a10e7dc909574 | 349 |
1 files changed, 349 insertions, 0 deletions
diff --git a/bf/518dddc480cbb9bf130deef70a10e7dc909574 b/bf/518dddc480cbb9bf130deef70a10e7dc909574 new file mode 100644 index 000000000..7d89cf8c7 --- /dev/null +++ b/bf/518dddc480cbb9bf130deef70a10e7dc909574 @@ -0,0 +1,349 @@ +Return-Path: <johanth@gmail.com> +Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136]) + by lists.linuxfoundation.org (Postfix) with ESMTP id DE10BC0032 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 5 Oct 2023 07:38:38 +0000 (UTC) +Received: from localhost (localhost [127.0.0.1]) + by smtp3.osuosl.org (Postfix) with ESMTP id C6EB86F51D + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 5 Oct 2023 07:38:38 +0000 (UTC) +DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org C6EB86F51D +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=fdLL+emN +X-Virus-Scanned: amavisd-new at osuosl.org +X-Spam-Flag: NO +X-Spam-Score: -2.099 +X-Spam-Level: +X-Spam-Status: No, score=-2.099 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, + 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 8NKti06Cqvu5 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 5 Oct 2023 07:38:37 +0000 (UTC) +Received: from mail-yb1-xb2a.google.com (mail-yb1-xb2a.google.com + [IPv6:2607:f8b0:4864:20::b2a]) + by smtp3.osuosl.org (Postfix) with ESMTPS id 304CA616E2 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 5 Oct 2023 07:38:37 +0000 (UTC) +DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 304CA616E2 +Received: by mail-yb1-xb2a.google.com with SMTP id + 3f1490d57ef6-d868d8363e6so782937276.2 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 05 Oct 2023 00:38:37 -0700 (PDT) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=gmail.com; s=20230601; t=1696491516; x=1697096316; + darn=lists.linuxfoundation.org; + h=content-transfer-encoding:cc:to:subject:message-id:date:from + :in-reply-to:references:mime-version:from:to:cc:subject:date + :message-id:reply-to; + bh=clvD2+SSCKbZpc01LIItZmWyvgF0rATpmCPOyx8zj4E=; + b=fdLL+emNORekYtGp3sdAh0TpKjjJSP401xXhFIhXi3JGv2AywffjU3JKhfbr26sktp + xV+UxdN0R17etNxp9BzwmO9b9nXthf0Aoy7GZsB/nCkXdKEVVUSsjrgrvRZbsyC/+nqK + pL8PpqvT8qsI9DTgoTXO9pgnnLxjEZfJQ1xmKi3Za+Zi8WjpUuhjsPlwFnK/aq8OPu2E + /9r6X+3sHcD7sKTlBqYYp+HxaeYQjAHuy0lATMR+pufqn/aIK9PdR2Wlrdpw89vmZz/s + 2wTHHF2iWkvDrQiMxt+fDzYPNzKAvs4jTuU2J6r0XtJ0GzXSaTkUaixOnrJwvzzCA8pJ + Kjtg== +X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=1e100.net; s=20230601; t=1696491516; x=1697096316; + h=content-transfer-encoding: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=clvD2+SSCKbZpc01LIItZmWyvgF0rATpmCPOyx8zj4E=; + b=PEMgQFHBSNu/96vVjGmDoACbrTMnDhH994WKZuPhIDpuf25FplVDpF5kMY9NBb/KfI + KW0R23gYHQ06ei8HBpqX5OBJ7wMHY6j5FPJYA8y2VqJGseOjLZMU77qbJRPdaSbSvLn9 + 5043fNt6y7hQJNMSSlfRCRRV/iaYzTSu/y/vJXpolSvgt95zlKJueS6qFlAHuf49wTf9 + oaG4GlLs/TTYDSHVK28oW+IWb+BVVNCg13sIjOBG1HDLYJLkzxhzbRBxAwGaBr3QJFiG + sTzP92MUC+Y6IDe+GpheOY6Dm7EXtsu2l5+VhN0/ZiXKDXS+cl3ydCGpWwhwgsg5JYE6 + TcBg== +X-Gm-Message-State: AOJu0YzCLM11J7CQz4P1ApjZ2IJhDTZXwzLxYIxJZ+ZBFviDFqHugaWs + pW1Mf9BQf3mUD/PL8nSPCDp7a4+WozME+I65Pao= +X-Google-Smtp-Source: AGHT+IHXEnsIpVRjsSFkvo6LLauYHPxgLf9yX5kBsvgwM96wjuh1mOjGpl/zx+BAsiX2FZ5P3Yi4mS3Wvhp98GoR3vQ= +X-Received: by 2002:a25:f624:0:b0:d81:c900:1f11 with SMTP id + t36-20020a25f624000000b00d81c9001f11mr4375423ybd.26.1696491515774; Thu, 05 + Oct 2023 00:38:35 -0700 (PDT) +MIME-Version: 1.0 +References: <CALZpt+F26bArqU7aZj8VN-zDN-3_VZS1K1ibaJOeCrsLDL2_4Q@mail.gmail.com> + <OUAbM8ii-HE8M-kRAkMvdDkbiwKuG_wcYlrvC276eIsKXcW6Yh6iNcxy_PtchHNL3jIIc-nz-ucv2H11EznrZbYhKqyVPhE8__GeIDLxPNw=@protonmail.com> + <CALZpt+Gyo1STD4zrge3yiuC1j_NpJ8ZDYzzzAGCcZpjKw0_9-w@mail.gmail.com> + <CAD3i26DpcfZJ4M0bjrOnGg6bcQ0Lg0hO-13cihzP2CjnCOq=EQ@mail.gmail.com> + <CALZpt+FT3qwP5MaZT4hbGYXvbECsAn7LvNbZC5vP-jGkbpOGVA@mail.gmail.com> +In-Reply-To: <CALZpt+FT3qwP5MaZT4hbGYXvbECsAn7LvNbZC5vP-jGkbpOGVA@mail.gmail.com> +From: =?UTF-8?Q?Johan_Tor=C3=A5s_Halseth?= <johanth@gmail.com> +Date: Thu, 5 Oct 2023 09:38:24 +0200 +Message-ID: <CAD3i26A2CC2Acr7dUnVMVrs+ag0nNdwnwTPSuVCxVpy+tC8eOg@mail.gmail.com> +To: Antoine Riard <antoine.riard@gmail.com> +Content-Type: text/plain; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable +X-Mailman-Approved-At: Thu, 05 Oct 2023 09:48:58 +0000 +Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> +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 <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, 05 Oct 2023 07:38:39 -0000 + +Hi, + +Yes, one would need to have the <data> be a merkle root of all +participants' keys and balances. Then, as you say, the scripts would +have to enforce that one correctly creates new merkle roots according +to the coin pool rules when spending it. + +- Johan + +On Thu, Oct 5, 2023 at 3:13=E2=80=AFAM Antoine Riard <antoine.riard@gmail.c= +om> wrote: +> +> Hi Johan, +> +> Thanks for the insight. +> +> From the proposed semantics of OP_CHECKCONTRACTVERIFY iirc: +> +> <data> <index> <pk> <taptree> <flags> +> +> I think this is not yet indicated how the participant's pubkeys and balan= +ces can be disaggregated from <data>, a partial subset push on the stack an= +d verifying that corresponding signatures are valid. +> +> One requirement of a cut-through update of taproot leaves is to verify th= +e authentication of the fan-out balances and pubkeys towards the "online" p= +artition. This subset is not known at pool setup, even if the contract or t= +ree construct can be equilibrated with some expectation. +> +> Otherwise, it sounds OP_CHECKCONTRACTVERIFY could be used to architect th= +e proposed design of coinpool and its cut-through mechanism. One hard issue= + sounds to be efficient traversal, inspection and modification of the contr= +act <data>. +> +> Best, +> Antoine +> +> Le mar. 3 oct. 2023 =C3=A0 12:24, Johan Tor=C3=A5s Halseth <johanth@gmail= +.com> a =C3=A9crit : +>> +>> Hi, Antoine. +>> +>> It sounds like perhaps OP_CHECKCONTRACTVERIFY can achieve what you are +>> looking for: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/202= +3-May/021719.html +>> +>> By committing the participants' pubkeys and balances in the dynamic +>> data instead of the taptree one can imagine a subset of online users +>> agreeing to pool their aggregated balances in a new output, while the +>> offline users' funds would remain inaccessible by them in a second +>> output. +>> +>> The way this would work is by spending the coinpool utxo with a +>> transaction having two outputs: one output that is the "remainder" of +>> the previous coinpool (the offline users), and the second output the +>> new coinpool among the online users*. +>> +>> When the offline users are back online, they could all agree to +>> continue using the original coinpool utxo. +>> +>> * assuming Eltoo in case an offline user comes back online and double +>> spends the UTXO. +>> +>> - Johan +>> +>> +>> On Wed, Sep 27, 2023 at 12:08=E2=80=AFPM Antoine Riard via bitcoin-dev +>> <bitcoin-dev@lists.linuxfoundation.org> wrote: +>> > +>> > Hi Zeeman, +>> > +>> > See my comments at the time of OP_EVICT original publication. +>> > +>> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-February/= +019939.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 sec= +urity +>> > requirement that a participant should have the unilateral means to enf= +orce +>> > the latest agreed upon state at any time during the construction lifet= +ime". +>> > +>> > I think this level of covenant flexibility is still wished for CoinPoo= +l 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 co= +venant proposal aiming to combine TLUV and EVICT-like semantics in a consis= +tent set of Script primitives to enable "cut-through" updates, while still = +retaining the key property of unilateral withdraw of promised balances in a= +ny-order. +>> > +>> > I might go to work on crafting one, though for now I'm still intereste= +d to understand better if on-chain "cut-through" is the best direction to s= +olve the fundamental high interactivity issue of channel factory and paymen= +t pool over punishment-based ideas. +>> > +>> > Best, +>> > Antoine +>> > +>> > Le mar. 26 sept. 2023 =C3=A0 07:51, ZmnSCPxj <ZmnSCPxj@protonmail.com>= + a =C3=A9crit : +>> >> +>> >> Good morning Antoine, +>> >> +>> >> Does `OP_EVICT` not fit? +>> >> +>> >> https://lists.linuxfoundation.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 <bitcoin-dev@lists.linuxfoundation.org> wrote: +>> >> +>> >> +>> >> > Payment pools and channel factories are afflicted by severe interac= +tivity constraints worsening with the number of users owning an off-chain b= +alance in the construction. The security of user funds is paramount on the = +ability to withdraw unilaterally from the off-chain construction. As such a= +ny update applied to the off-chain balances requires a signature contributi= +on from the unanimity of the construction users to ensure this ability is c= +onserved along updates. +>> >> > As soon as one user starts to be offline or irresponsive, the updat= +es of the off-chain balances must have to be halted and payments progress a= +re limited among subsets of 2 users sharing a channel. Different people hav= +e proposed solutions to this issue: introducing a coordinator, partitioning= + or layering balances in off-chain users subsets. I think all those solutio= +ns have circled around a novel issue introduced, namely equivocation of off= +-chain balances at the harm of construction counterparties [0]. +>> >> > +>> >> > As ZmnSCPxj pointed out recently, one way to mitigate this equivoca= +tion consists in punishing the cheating pre-nominated coordinator on an ext= +ernal fidelity bond. One can even imagine more trust-mimized and decentrali= +zed fraud proofs to implement this mitigation, removing the need of a coord= +inator [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-ca= +se against all the other counterparties in the construction, one fidelity b= +ond 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 che= +ating counterparty. +>> >> > +>> >> > Moreover, I guess it is impossible to know ahead of a partition or = +transition who will be the "honest" counterparties from the "dishonest" one= +s, therefore this ( C - 1 ) * B-sized fidelity bond must be maintained by e= +very counterparty in the pool or factory. On this ground, I think this miti= +gation and other corrective ones are not economically practical for large-s= +cale 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 pr= +ophylactic fashion. The pool or factory funding utxo should be edited in an= + efficient way to register new off-chain subgroups, as lack of interactivit= +y from a subset of counterparties demands it. +>> >> > +>> >> > With CoinPool, there is already this idea of including a user pubke= +y and balance amount to each leaf composing the Taproot tree while preservi= +ng the key-path spend in case of unanimity in the user group. Taproot leave= +s can be effectively regarded as off-chain user accounts available to reali= +ze privacy-preserving payments and contracts. +>> >> > +>> >> > I think one (new ?) idea can be to introduce taproot leaves "cut-th= +rough" spends where multiple leaves are updated with a single witness, inte= +ractively 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 p= +ubkeys. The user leaves not participating in this "cut-through" are inherit= +ed 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 lea= +f. +>> >> > +>> >> > 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 cou= +nterparties is left unmodified. +>> >> > +>> >> > The ACD group can confirm a transaction spending the pool funding u= +txo 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 mech= +anism. There is no possibility for any member of the ACD group to equivocat= +e 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-equi= +librate the Taproot tree, prune out old subgroups unlikely to be used and p= +rovision future subgroups, all with a compact spend based on signature aggr= +egation. +>> >> > +>> >> > Few new Taproot tree update script primitives have been proposed, e= +.g [2]. Though I think none with the level of flexibility offered to genera= +te leaves cut-through spends, or even batch of "cut-through" where M subgro= +ups are willing to spend N leaves to compose P new subgroups fan-out in Q n= +ew outputs, with showing a single on-chain witness. I believe such a hypoth= +etical 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 po= +ols and factories shifts the burden on each individual user to pre-commit f= +ast Taproot tree traversals, allowing them to compose new pool subgroups as= + fluctuations in pool users' level of liveliness demand it. Pool efficiency= + becomes the sum of the quality of user prediction on its counterparties' l= +iveliness during the construction lifetime. Recursive taproot tree spends o= +r more efficient accumulator than merkle tree sounds ideas to lower the on-= +chain witness space consumed by every pool in the average non-interactive c= +ase. +>> >> > +>> >> > Cheers, +>> >> > Antoine +>> >> > +>> >> > [0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-Ap= +ril/020370.html +>> >> > [1] https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-= +August/004043.html +>> >> > [2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-Se= +ptember/019420.html +>> > +>> > _______________________________________________ +>> > bitcoin-dev mailing list +>> > bitcoin-dev@lists.linuxfoundation.org +>> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev + |