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>
In-Reply-To: <CALZpt+Gyo1STD4zrge3yiuC1j_NpJ8ZDYzzzAGCcZpjKw0_9-w@mail.gmail.com>
From: =?UTF-8?Q?Johan_Tor=C3=A5s_Halseth?= <johanth@gmail.com>
Date: Tue, 3 Oct 2023 13:24:20 +0200
Message-ID: <CAD3i26DpcfZJ4M0bjrOnGg6bcQ0Lg0hO-13cihzP2CjnCOq=EQ@mail.gmail.com>
To: Antoine Riard <antoine.riard@gmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] Solving CoinPool high-interactivity issue with
 cut-through update of Taproot leaves
Precedence: list

Hi, Antoine.

It sounds like perhaps OP_CHECKCONTRACTVERIFY can achieve what you are
looking for: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-M=
ay/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/019=
939.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 securi=
ty
> requirement that a participant should have the unilateral means to enforc=
e
> the latest agreed upon state at any time during the construction lifetime=
".
>
> I think this level of covenant flexibility is still wished for CoinPool a=
s a fundamental property, and this is offered by TLUV or MERKLESUB.
> On the other hand, I think OP_EVICT introduces this idea of *subgroup nov=
ation* (i.e `K-of-N`) of a PT2R scriptpubkey.
>
> To the best of my understanding, I think there is not yet any sound coven=
ant proposal aiming to combine TLUV and EVICT-like semantics in a consisten=
t set of Script primitives to enable "cut-through" updates, while still ret=
aining 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 t=
o understand better if on-chain "cut-through" is the best direction to solv=
e the fundamental high interactivity issue of channel factory and payment p=
ool 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/01=
9926.html
>>
>> Regards,
>> ZmnSCPxj
>>
>>
>> Sent with Proton Mail secure email.
>>
>> ------- Original Message -------
>> On Monday, September 25th, 2023 at 6:18 PM, Antoine Riard via bitcoin-de=
v <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 "dishonest" ones, =
therefore this ( C - 1 ) * B-sized fidelity bond must be maintained by ever=
y counterparty in the pool or factory. On this ground, I think this mitigat=
ion and other corrective ones are not economically practical for large-scal=
e 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-throu=
gh" spends where multiple leaves are updated with a single witness, interac=
tively composed by the owners of the spent leaves. This spend sends back th=
e leaves amount to a new single leaf, aggregating the amounts and user pubk=
eys. 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 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 counte=
rparties 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 "r=
efresh" transaction, the conserved key-path spend can be used to re-equilib=
rate the Taproot tree, prune out old subgroups unlikely to be used and prov=
ision future subgroups, all with a compact spend based on signature aggrega=
tion.
>> >
>> > 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 hypotheti=
cal 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 fl=
uctuations in pool users' level of liveliness demand it. Pool efficiency be=
comes the sum of the quality of user prediction on its counterparties' live=
liness during the construction lifetime. Recursive taproot tree spends or m=
ore efficient accumulator than merkle tree sounds ideas to lower the on-cha=
in 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-Aug=
ust/004043.html
>> > [2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-Septe=
mber/019420.html
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev