Date: Tue, 26 Sep 2023 06:50:50 +0000
To: Antoine Riard <antoine.riard@gmail.com>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <OUAbM8ii-HE8M-kRAkMvdDkbiwKuG_wcYlrvC276eIsKXcW6Yh6iNcxy_PtchHNL3jIIc-nz-ucv2H11EznrZbYhKqyVPhE8__GeIDLxPNw=@protonmail.com>
In-Reply-To: <CALZpt+F26bArqU7aZj8VN-zDN-3_VZS1K1ibaJOeCrsLDL2_4Q@mail.gmail.com>
References: <CALZpt+F26bArqU7aZj8VN-zDN-3_VZS1K1ibaJOeCrsLDL2_4Q@mail.gmail.com>
Feedback-ID: 2872618:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
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

Good morning Antoine,

Does `OP_EVICT` not fit?

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-February/01992=
6.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 abilit=
y to withdraw unilaterally from the off-chain construction. As such any upd=
ate applied to the off-chain balances requires a signature contribution fro=
m the unanimity of the construction users to ensure this ability is conserv=
ed 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 lim=
ited among subsets of 2 users sharing a channel. Different people have prop=
osed solutions to this issue: introducing a coordinator, partitioning or la=
yering balances in off-chain users subsets. I think all those solutions hav=
e circled around a novel issue introduced, namely equivocation of off-chain=
 balances at the harm of construction counterparties [0].
>=20
> As ZmnSCPxj pointed out recently, one way to mitigate this equivocation c=
onsists in punishing the cheating pre-nominated coordinator on an external =
fidelity bond. One can even imagine more trust-mimized and decentralized fr=
aud proofs to implement this mitigation, removing the need of a coordinator=
 [1].
>=20
> 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 aga=
inst all the other counterparties in the construction, one fidelity bond sh=
ould be equal to ( C - 1 ) * B satoshi amount, where C is the number of con=
struction counterparty and B the initial off-chain balance of the cheating =
counterparty.
>=20
> Moreover, I guess it is impossible to know ahead of a partition or transi=
tion who will be the "honest" counterparties from the "dishonest" ones, the=
refore this ( C - 1 ) * B-sized fidelity bond must be maintained by every c=
ounterparty in the pool or factory. On this ground, I think this mitigation=
 and other corrective ones are not economically practical for large-scale p=
ools among a set of anonymous users.
>=20
> I think the best solution to solve the interactivity issue which is reali=
stic to design is one ruling out off-chain group equivocation in a prophyla=
ctic fashion. The pool or factory funding utxo should be edited in an effic=
ient way to register new off-chain subgroups, as lack of interactivity from=
 a subset of counterparties demands it.
>=20
> 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 pri=
vacy-preserving payments and contracts.
>=20
> I think one (new ?) idea can be to introduce taproot leaves "cut-through"=
 spends where multiple leaves are updated with a single witness, interactiv=
ely composed by the owners of the spent leaves. This spend sends back the l=
eaves amount to a new single leaf, aggregating the amounts and user pubkeys=
. The user leaves not participating in this "cut-through" are inherited wit=
h full integrity in the new version of the Taproot tree, at the gain of no =
interactivity from their side.
>=20
> Let's say you have a CoinPool funded and initially set with Alice, Bob, C=
aroll, 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.
>=20
> Bob and Eve are deemed to be offline by the Alice, Caroll and Dave subset=
 (the ACD group).
>=20
> The ACD group composes a cut-through spend of L.a + L.c + L.d. This spend=
s generates a new leaf L.(acd) leaf committing to amount A.(acd) and P.(acd=
).
>=20
> Amount A.(acd) =3D A.a + A.c + A.d and pubkey P.(acd) =3D P.a + P.c + P.d=
.
>=20
> Bob's leaf L.b and Eve's leaf L.e are left unmodified.
>=20
> The ACD group generates a new Taproot tree T' =3D L.(acd) + L.b + L.e, wh=
ere the key-path K spend including the original unanimity of pool counterpa=
rties is left unmodified.
>=20
> The ACD group can confirm a transaction spending the pool funding utxo to=
 a new single output committing to the scriptpubkey K + T'.
>=20
> From then, the ACD group can pursue off-chain balance updates among the s=
ubgroup 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.
>=20
> Once Bob and Eve are online and ready to negotiate an on-chain pool "refr=
esh" transaction, the conserved key-path spend can be used to re-equilibrat=
e the Taproot tree, prune out old subgroups unlikely to be used and provisi=
on future subgroups, all with a compact spend based on signature aggregatio=
n.
>=20
> 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 lea=
ves cut-through spends, or even batch of "cut-through" where M subgroups ar=
e willing to spend N leaves to compose P new subgroups fan-out in Q new out=
puts, with showing a single on-chain witness. I believe such a hypothetical=
 primitive can also reduce the chain space consumed in the occurrence of na=
ive mass pool withdraws at the same time.
>=20
> I think this solution to the high-interactivity issue of payment pools an=
d factories shifts the burden on each individual user to pre-commit fast Ta=
proot tree traversals, allowing them to compose new pool subgroups as fluct=
uations in pool users' level of liveliness demand it. Pool efficiency becom=
es the sum of the quality of user prediction on its counterparties' livelin=
ess 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.
>=20
> Cheers,
> Antoine
>=20
> [0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/02=
0370.html
> [1] https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-August=
/004043.html
> [2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-Septembe=
r/019420.html