MIME-Version: 1.0
References: <CALZpt+F26bArqU7aZj8VN-zDN-3_VZS1K1ibaJOeCrsLDL2_4Q@mail.gmail.com>
 <OUAbM8ii-HE8M-kRAkMvdDkbiwKuG_wcYlrvC276eIsKXcW6Yh6iNcxy_PtchHNL3jIIc-nz-ucv2H11EznrZbYhKqyVPhE8__GeIDLxPNw=@protonmail.com>
In-Reply-To: <OUAbM8ii-HE8M-kRAkMvdDkbiwKuG_wcYlrvC276eIsKXcW6Yh6iNcxy_PtchHNL3jIIc-nz-ucv2H11EznrZbYhKqyVPhE8__GeIDLxPNw=@protonmail.com>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Tue, 26 Sep 2023 16:36:26 +0100
Message-ID: <CALZpt+Gyo1STD4zrge3yiuC1j_NpJ8ZDYzzzAGCcZpjKw0_9-w@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="000000000000236d2b060644d78a"
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
Precedence: list

--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 <ZmnSCPxj@protonmail.com> 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

<div dir=3D"ltr">Hi Zeeman,<div><br></div><div>See my comments at the time =
of OP_EVICT original publication.</div><div><br></div><div><a href=3D"https=
://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-February/019939.htm=
l">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-February/01=
9939.html</a><br></div><div><br></div><div>&quot;I think in the context of =
(off-chain) payment pool, OP_EVICT requires</div><div>participant cooperati=
on *after* the state update to allow a single</div><div>participant to with=
draw her funds.</div><div><br></div><div>I believe this is unsafe if we ret=
ain as an off-chain construction security</div><div>requirement that a part=
icipant should have the unilateral means to enforce</div><div>the latest ag=
reed upon state at any time during the construction lifetime&quot;.</div><d=
iv><br></div><div>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.</div><div>On the other hand, I think OP_EVICT introduces this idea=
 of *subgroup novation* (i.e `K-of-N`) of a PT2R scriptpubkey.</div><div><b=
r></div><div>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 &quot;cut-through&quot=
; updates, while still retaining the key property of unilateral withdraw of=
 promised balances in any-order.</div><div><br></div><div>I might go to wor=
k on crafting one, though for now I&#39;m still interested to understand be=
tter if on-chain &quot;cut-through&quot; is the best direction to solve the=
 fundamental high interactivity issue of channel factory and payment pool o=
ver punishment-based ideas.</div><div><br></div><div>Best,</div><div>Antoin=
e</div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail=
_attr">Le=C2=A0mar. 26 sept. 2023 =C3=A0=C2=A007:51, ZmnSCPxj &lt;<a href=
=3D"mailto:ZmnSCPxj@protonmail.com">ZmnSCPxj@protonmail.com</a>&gt; a =C3=
=A9crit=C2=A0:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0=
px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-=
color:rgb(204,204,204);padding-left:1ex">Good morning Antoine,<br>
<br>
Does `OP_EVICT` not fit?<br>
<br>
<a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-Feb=
ruary/019926.html" rel=3D"noreferrer" target=3D"_blank">https://lists.linux=
foundation.org/pipermail/bitcoin-dev/2022-February/019926.html</a><br>
<br>
Regards,<br>
ZmnSCPxj<br>
<br>
<br>
Sent with Proton Mail secure email.<br>
<br>
------- Original Message -------<br>
On Monday, September 25th, 2023 at 6:18 PM, Antoine Riard via bitcoin-dev &=
lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blan=
k">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br>
<br>
<br>
&gt; 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.<br>
&gt; 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].<br>
&gt; <br>
&gt; 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].<br>
&gt; <br>
&gt; 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.<br>
&gt; <br>
&gt; Moreover, I guess it is impossible to know ahead of a partition or tra=
nsition who will be the &quot;honest&quot; counterparties from the &quot;di=
shonest&quot; 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.<br>
&gt; <br>
&gt; 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.<br>
&gt; <br>
&gt; 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.<br>
&gt; <br>
&gt; I think one (new ?) idea can be to introduce taproot leaves &quot;cut-=
through&quot; 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 &quot;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.<br>
&gt; <br>
&gt; Let&#39;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.<br>
&gt; <br>
&gt; Bob and Eve are deemed to be offline by the Alice, Caroll and Dave sub=
set (the ACD group).<br>
&gt; <br>
&gt; 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).<br>
&gt; <br>
&gt; Amount A.(acd) =3D A.a + A.c + A.d and pubkey P.(acd) =3D P.a + P.c + =
P.d.<br>
&gt; <br>
&gt; Bob&#39;s leaf L.b and Eve&#39;s leaf L.e are left unmodified.<br>
&gt; <br>
&gt; The ACD group generates a new Taproot tree T&#39; =3D L.(acd) + L.b + =
L.e, where the key-path K spend including the original unanimity of pool co=
unterparties is left unmodified.<br>
&gt; <br>
&gt; The ACD group can confirm a transaction spending the pool funding utxo=
 to a new single output committing to the scriptpubkey K + T&#39;.<br>
&gt; <br>
&gt; 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.<br>
&gt; <br>
&gt; Once Bob and Eve are online and ready to negotiate an on-chain pool &q=
uot;refresh&quot; 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.<br>
&gt; <br>
&gt; 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 &quot;cut-through&quot; 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.<br>
&gt; <br>
&gt; 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&#39; 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.<br>
&gt; <br>
&gt; Cheers,<br>
&gt; Antoine<br>
&gt; <br>
&gt; [0] <a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev=
/2022-April/020370.html" rel=3D"noreferrer" target=3D"_blank">https://lists=
.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020370.html</a><br>
&gt; [1] <a href=3D"https://lists.linuxfoundation.org/pipermail/lightning-d=
ev/2023-August/004043.html" rel=3D"noreferrer" target=3D"_blank">https://li=
sts.linuxfoundation.org/pipermail/lightning-dev/2023-August/004043.html</a>=
<br>
&gt; [2] <a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev=
/2021-September/019420.html" rel=3D"noreferrer" target=3D"_blank">https://l=
ists.linuxfoundation.org/pipermail/bitcoin-dev/2021-September/019420.html</=
a><br>
</blockquote></div>

--000000000000236d2b060644d78a--