MIME-Version: 1.0
From: Antoine Riard <antoine.riard@gmail.com>
Date: Mon, 25 Sep 2023 19:18:36 +0100
Message-ID: <CALZpt+F26bArqU7aZj8VN-zDN-3_VZS1K1ibaJOeCrsLDL2_4Q@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000004991b3060632fde0"
Subject: [bitcoin-dev] Solving CoinPool high-interactivity issue with
 cut-through update of Taproot leaves
Precedence: list

--0000000000004991b3060632fde0
Content-Type: text/plain; charset="UTF-8"

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 requires 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 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
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 equivocation
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 external
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 balance 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 this
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 in
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 and
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 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) = A.a + A.c + A.d and pubkey P.(acd) = 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' = 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 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
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 fast
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'
liveliness during the construction lifetime. Recursive taproot tree spends
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/004043.html
[2]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-September/019420.html

--0000000000004991b3060632fde0
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Payment pools and channel factories are afflicted by sever=
e interactivity constraints worsening with the number of users owning an of=
f-chain balance in the construction. The security of user funds is paramoun=
t on the ability to withdraw unilaterally from the off-chain construction. =
As such any update applied to the off-chain balances requires a signature c=
ontribution from the unanimity of the construction users to ensure this abi=
lity is conserved along updates.<div><br></div><div>As soon as one user sta=
rts to be offline or irresponsive, the updates of the off-chain balances mu=
st have to be halted and payments progress are limited among subsets of 2 u=
sers sharing a channel. Different people have proposed solutions to this is=
sue: introducing a coordinator, partitioning or layering balances in off-ch=
ain users subsets. I think all those solutions have circled around a novel =
issue introduced, namely equivocation of off-chain balances at the harm of =
construction counterparties [0].</div><div><br></div><div>As ZmnSCPxj point=
ed out recently, one way to mitigate this equivocation consists in punishin=
g the cheating pre-nominated coordinator on an external fidelity bond. One =
can even imagine more trust-mimized and decentralized fraud proofs to imple=
ment this mitigation, removing the need of a coordinator [1].</div><div><br=
></div><div>However, I believe punishment equivocation to be game-theory so=
und should compensate a defrauded counterparty of the integrity of its lost=
 off-chain balance. As one cheating counterparty can equivocate in the wors=
t-case against all the other counterparties in the construction, one fideli=
ty bond should be equal to ( C - 1 ) * B satoshi amount, where C is the num=
ber of construction counterparty and B the initial off-chain balance of the=
 cheating counterparty.</div><div><br></div><div>Moreover, I guess it is im=
possible to know ahead of a partition or transition who will be the &quot;h=
onest&quot; counterparties from the &quot;dishonest&quot; ones, therefore t=
his ( C - 1 ) * B-sized fidelity bond must be maintained by every counterpa=
rty in the pool or factory. On this ground, I think this mitigation and oth=
er corrective ones are not economically practical for large-scale pools amo=
ng a set of anonymous users.</div><div><br></div><div>I think the best solu=
tion to solve the interactivity issue which is realistic to design is one=
=C2=A0ruling out off-chain group equivocation in a prophylactic fashion. Th=
e pool or factory funding utxo should be edited in an efficient way to regi=
ster new off-chain subgroups, as lack of interactivity from a subset of cou=
nterparties demands it.</div><div><br></div><div>With CoinPool, there is al=
ready this idea of including a user pubkey and balance amount to each leaf =
composing the Taproot tree while preserving the key-path spend in case of u=
nanimity in the user group. Taproot leaves can be effectively regarded as o=
ff-chain user accounts available to realize privacy-preserving payments and=
 contracts.</div><div><br></div><div>I think one (new ?) idea can be to int=
roduce taproot leaves &quot;cut-through&quot; 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 l=
eaf, aggregating the amounts and user pubkeys. The user leaves not particip=
ating in this &quot;cut-through&quot; are inherited with full integrity in =
the new version of the Taproot tree, at the gain of no interactivity from t=
heir side.</div><div><br></div><div>Let&#39;s say you have a CoinPool funde=
d and initially set with Alice, Bob, Caroll, Dave and Eve. Each pool partic=
ipant 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.</div><div><br></div><div>Bob and Eve are=
 deemed to be offline by the Alice, Caroll and Dave subset (the ACD group).=
</div><div><br></div><div>The ACD group composes a cut-through spend of L.a=
=C2=A0+ L.c=C2=A0+ L.d. This spends generates a new leaf L.(acd) leaf commi=
tting to amount A.(acd) and P.(acd).</div><div><br></div><div>Amount A.(acd=
) =3D A.a=C2=A0+ A.c=C2=A0+ A.d and pubkey P.(acd) =3D P.a=C2=A0+ P.c=C2=A0=
+ P.d.</div><div><br></div><div>Bob&#39;s leaf L.b and Eve&#39;s leaf L.e a=
re left unmodified.</div><div><br></div><div>The ACD group generates a new =
Taproot tree T&#39; =3D L.(acd)=C2=A0+ L.b=C2=A0+ L.e, where the key-path K=
 spend including the original unanimity of pool counterparties is left unmo=
dified.</div><div><br></div><div>The ACD group can confirm a transaction sp=
ending the pool funding utxo to a new single output committing to the scrip=
tpubkey K=C2=A0+ T&#39;.</div><div><br></div><div>From then, the ACD group =
can pursue off-chain balance=C2=A0updates among the subgroup thanks to the =
new P.(acd) and relying on the known Eltoo mechanism. There is no possibili=
ty for any member of the ACD group to equivocate with Bob or Eve in a non-o=
bservable fashion.</div><div><br></div><div>Once Bob and Eve are online and=
 ready to negotiate an on-chain pool &quot;refresh&quot; transaction, the c=
onserved key-path spend can be used to re-equilibrate the Taproot tree, pru=
ne out old subgroups unlikely to be used and provision future subgroups, al=
l with a compact spend based on signature aggregation.</div><div><br></div>=
<div>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.</div><div><br></div>=
<div>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=C2=A0demand it. Pool effi=
ciency becomes the sum of the quality of user prediction on its counterpart=
ies&#39; liveliness during the construction lifetime. Recursive taproot tre=
e spends or more efficient accumulator than merkle tree sounds ideas to low=
er the on-chain witness space consumed by every pool in the average non-int=
eractive case.</div><div><br></div><div>Cheers,</div><div>Antoine</div><div=
><br></div><div>[0]=C2=A0<a href=3D"https://lists.linuxfoundation.org/piper=
mail/bitcoin-dev/2022-April/020370.html">https://lists.linuxfoundation.org/=
pipermail/bitcoin-dev/2022-April/020370.html</a></div><div>[1]=C2=A0<a href=
=3D"https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-August/0=
04043.html">https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-=
August/004043.html</a></div><div>[2]=C2=A0<a href=3D"https://lists.linuxfou=
ndation.org/pipermail/bitcoin-dev/2021-September/019420.html">https://lists=
.linuxfoundation.org/pipermail/bitcoin-dev/2021-September/019420.html</a></=
div></div>

--0000000000004991b3060632fde0--