path: root/b9/f0b354a7c4c35284f130d60e2571f38e442c64

Return-Path: <antoine.riard@gmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 11D47C002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 10 May 2022 00:38:52 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp3.osuosl.org (Postfix) with ESMTP id DC87860D74
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 10 May 2022 00:38:51 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level: 
X-Spam-Status: No, score=-2.098 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,
 HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: smtp3.osuosl.org (amavisd-new);
 dkim=pass (2048-bit key) header.d=gmail.com
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 296NxGUUUR0b
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 10 May 2022 00:38:48 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-yw1-x112b.google.com (mail-yw1-x112b.google.com
 [IPv6:2607:f8b0:4864:20::112b])
 by smtp3.osuosl.org (Postfix) with ESMTPS id 4560160BE2
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 10 May 2022 00:38:48 +0000 (UTC)
Received: by mail-yw1-x112b.google.com with SMTP id
 00721157ae682-2f7c57ee6feso163208917b3.2
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 09 May 2022 17:38:48 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=Jpj+c8z+h5zpUko6+haebDfXCRWXLgDfHMkgogxCKf4=;
 b=HIGjn5SLWRzMVMc3NodaWuWcqjPeWls6mRQYaWvHys953FIooLULjzyfUdjl6cBNaj
 I+nNs591wwMBA9/2Hkkb1YZ9kBJ9+nnjBddZkzEZe/xHflYmpZar/nOcmPefeMNV3Brx
 goFlVHE3rBtkTeOFEC7vx8NgfHo/mSYcNlsfw4ZqFfkkmtapjnqkBVgwqMXHlNHAtWn8
 O+LoeZw4zg2XJsz2L2H03gW153K+m+WcFdczPY9qiqVBlwTI2YTr4ijjzTqsYSv4y31K
 p3TTv0tByuV1MZBWAzFAkVH1vDQT6BbXGoL5OwPOlMKemGpN890V+8MFBLUHumKkGimt
 skrA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=Jpj+c8z+h5zpUko6+haebDfXCRWXLgDfHMkgogxCKf4=;
 b=y12FnpiI3OvifrtBPs8yIHzPnnhcf/EIjcdo+OrlJ0a46o1ZP97ofb/c2bYTq+38NU
 CYutYm2MxBjDF7P8IgfewI+BKtQfITJlrH2aKY8XFXs9z67yPWgw74Al5ocOmHCNinQz
 DS/4ugQx1Cz6e3dFlYHeRN/EAlEVFj3dy2N/hjTGBnc19tktiPWd2wi6NGOdGjdatVBd
 IbH59tDKp59Gb9mVcXHSVBzM99uCP5EBX0B8Tj3ahmAlX645jeAMwUBEu9KWVyqmQB5w
 9+qgp9tOilzkbdurqyRYcFSZVQf1ik2fp8DsVrjnbUFEOPMljccVF0HTMUJsqh9O8mvb
 UucA==
X-Gm-Message-State: AOAM533j20ymMgbaCggfqnT8+f1wQ3v2kGmipiomy8iczI2mzJVVy8At
 nclcax59hAKQjzU7AFHpY163Q5tKi2PMeZYeuYM=
X-Google-Smtp-Source: ABdhPJy4ETsknbxaQs7fzsVxN/3/hn3QiWA/tJjd2WYWg5l85rCnOL+NOXpsp52vaoIxIlBJulPThPpAxkxe5ohrYY8=
X-Received: by 2002:a81:4a8a:0:b0:2f4:c511:a0af with SMTP id
 x132-20020a814a8a000000b002f4c511a0afmr16877846ywa.68.1652143127055; Mon, 09
 May 2022 17:38:47 -0700 (PDT)
MIME-Version: 1.0
References: <CALZpt+GNoRdbtfeBtpnitiAZ4jGwSsRpSRXOyX7mzrhwewmBcw@mail.gmail.com>
 <CAGpPWDa2wofye=KSq-vVNS0SOU34st9wm-hMhiYzGLTKMGuP5w@mail.gmail.com>
In-Reply-To: <CAGpPWDa2wofye=KSq-vVNS0SOU34st9wm-hMhiYzGLTKMGuP5w@mail.gmail.com>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Mon, 9 May 2022 20:38:36 -0400
Message-ID: <CALZpt+FTB9y6zO4Ap44GwZKVGj17Hv8+fYP02eoevOFA1MO5LA@mail.gmail.com>
To: Billy Tetrud <billy.tetrud@gmail.com>
Content-Type: multipart/alternative; boundary="00000000000034d3f205de9d8c27"
X-Mailman-Approved-At: Tue, 10 May 2022 00:54:46 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Conjectures on solving the high interactivity
 issue in payment pools and channel factories
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: Tue, 10 May 2022 00:38:52 -0000

--00000000000034d3f205de9d8c27
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Billy,

Thanks for reading.

> A. Create sub-pools when the whole group is live that can be used by the
> sub- pool participants later without the whole group's involvement. The
> whole group is needed to change the whole group's state (eg close or open
> sub-pools), but sub-pool states don't need to involve the whole group.

Yes this could be a direction. Assume you have a fan-out transaction
spending the Update transaction to a combination of sub-pools. I think you
have two problems arising.

The first one it's hard to predict in advance the subset of pool
participants which will be inactive, and thus guaranteeing stale-free
sub-pools. Further, it's also hard to predict in advance the liquidity
needs of the sub-pools. So I think this prediction of these two factors is
unlikely to be correct, this statement getting more sound as the number of
pool participants increases.

The second one, this fan-out transaction could interfere with the
confirmation of the simple withdraw transactions, and thus the uplifted
constructions (e.g a LN channel). So there is an open question about the
"honest" usage of the sub-pool states themselves.

> B. Have an always-online system empowered to sign only for group updates
> that *do not* change the owner's balance in the group. This could be done
> with a hardware-wallet like device, or could be done with some kind of ne=
w
> set of opcodes that can be used to verify that a particular transaction
> isn't to the owner's detriment.

Sure, one could envision an accumulator committing directly to balances
too. State transition would be allowed only if the non-involved users
balances are immutably preserved to, only the active users balances are
mixed. I think the challenge is to find a compact accumulator with those
properties.

About the "hardware-wallet like device"/"towers" solution, yes this is a
known technique to solve interactivity. Sadly, this can be a significant
requirement for a lot of users to run an additional always-online process.
It's more likely a lot of them will delegate this operation to third-party
providers, with the known reductions in terms of trust-minimizations.

> Come to think of it tho, this doesn't actually solve the double spending
> problem. The fundamental issue is that if you have a subset of
participants
> creating partitions like this, without the involvement of the whole group=
,
> its impossible for any subset of participants to know for sure that there
> isn't a double-spending partition amongst another set of members of the
> group.

Yes, it seems we agree that equivocation opening the way to balance
double-spend is the hard issue with partitioning multi-party constructions.

> I had a conceptual idea a while back (that I can't find at the moment)
> about offline lightning receiving. The concept is that each lightning nod=
e
> in a channel has two separate keys: a spending-key and a receiving-key.
The
> spending-key must be used manually by the node owner to send payments,
> however the receiving-key can be given to an always-online service that
can
> use that key only to either receive funds (ie update the state to a more
> favorable state).

Hmmm, how could you prevent the always-online service from using the
receiving-key in "spending" mode if the balance stacked there becomes
relevant ?

> You could do this logic inside a hardware-wallet-like device that checks
> the proposed updates and verifies the new state is favorable before
> signing. This could go a long way to hardening lightning nodes against
> potential compromise.

Yes, see https://gitlab.com/lightning-signer/docs for wip in that direction=
.

> This kind of thing might be a way of working around interactivity
> requirements of payment pools and the like. All participants still have t=
o
> be aware of the whole state (eg of the payment pool), but this awareness
> can be delegated to a system you have limited trust in. Payment pool
> participants could delegate an always-online system empowered with a
> separate key to sign payment pool updates that user's state isn't changed
> for, allowing the payment pool to do its thing without exposing the user
to
> hot-key vulnerabilities in that always-online system. Double spending is
> prevented because the user can access their always-online system to get
the
> full payment pool state.

While I would be curious to see such Script-based "receiving-key" only
mechanism (maybe with IN_OUT_AMOUNT-style of covenant) I wonder if it would
solve equivocation fully. A malicious pool participant could still commit
her off-chain balance in two partitions and send spends to the A&B hosting
"receiving-keys" entities without them being aware of the conflict, in the
lack of a reconciliation such as a publication space ? Or do you have
another thinking ?

Antoine

Le dim. 1 mai 2022 =C3=A0 18:53, Billy Tetrud <billy.tetrud@gmail.com> a =
=C3=A9crit :

> Hi Antoine,
>
> Very interesting exploration. I think you're right that there are issues
> with the kind of partitioning you're talking about. Lightning works becau=
se
> all participants sign all offchain states (barring data loss). If a
> participant can be excluded from needing to agree to a new state, there
> must be an additional mechanism to ensure the relevant state for that
> participant isn't changed to their detriment.
>
> To summarize my below email, the two techniques I can think for solving
> this problem are:
>
> A. Create sub-pools when the whole group is live that can be used by the
> sub- pool participants later without the whole group's involvement. The
> whole group is needed to change the whole group's state (eg close or open
> sub-pools), but sub-pool states don't need to involve the whole group.
> B. Have an always-online system empowered to sign only for group updates
> that *do not* change the owner's balance in the group. This could be done
> with a hardware-wallet like device, or could be done with some kind of ne=
w
> set of opcodes that can be used to verify that a particular transaction
> isn't to the owner's detriment.
>
> I had some thoughts that I think don't pan out, but here they are anyway:
>
> What if the pool state transaction (that returns everyone's money) has
> each participant sign the input + their personal output (eg with sighash
> flags)? That way the transaction could have outputs swapped out by a subs=
et
> of participants as needed. Some kind of eltoo mechanism could then ensure
> that the latest transaction can override earlier transactions. As far as
> the non-participating members are concerned, they don't care whether the
> newest state is published or whether the newest state they participated i=
n
> is published - because their output is identical either way. However, I c=
an
> see that there might be problems related to separate groups of participan=
ts
> creating conflicting transactions, ie A B & C create a partition like thi=
s,
> and so do D E & F, but they don't know about each other's state. If they
> have some always-online coordination mechanism, this could be solved as
> long as the participants aren't malicious. But it still leaves open the
> possibility that some participants could intentionally grief others by
> intentionally creating conflicting state transactions. Theoretically it
> could be structured so that no funds could be directly stolen, but it see=
ms
> unavoidable that some group of members could create a secret transaction
> that when published makes the most recent honest state not minable.
>
> Come to think of it tho, this doesn't actually solve the double spending
> problem. The fundamental issue is that if you have a subset of participan=
ts
> creating partitions like this, without the involvement of the whole group=
,
> its impossible for any subset of participants to know for sure that there
> isn't a double-spending partition amongst another set of members of the
> group.
>
> On-chain bitcoin transactions prevent double spending by ensuring that
> everyone knows what outputs have been spent. Payment channels prevent
> double spending by ensuring that everyone that's part of the channel know=
s
> what the current channel state is. Any 3rd layer probably needs this exac=
t
> property: everyone involved must know the state. So you should be able to
> create a partition when the whole group is live, and thereafter the membe=
rs
> of that partition can use that partition without involving the rest of th=
e
> group. I think that pattern can work to any level of depth. After thinkin=
g
> about this, I conjecture it might be a fundamental property of the double
> spending problem. All participants must be aware of the whole state
> otherwise the double spending problem exists for those who aren't aware o=
f
> the whole state.
>
> > this is forcing the pool/factory user to share their key materials with
> potentially lower trusted entities, if they don't self-host the tower
> instances.
>
> I had a conceptual idea a while back (that I can't find at the moment)
> about offline lightning receiving. The concept is that each lightning nod=
e
> in a channel has two separate keys: a spending-key and a receiving-key. T=
he
> spending-key must be used manually by the node owner to send payments,
> however the receiving-key can be given to an always-online service that c=
an
> use that key only to either receive funds (ie update the state to a more
> favorable state).
>
> Right now with just a single-hot-key setup you need to trust your online
> system to only sign receiving transactions and would refuse to sign any
> proposed channel update not in the owner's favor. However, if the node wa=
s
> compromised all bets are off - the entire channel balance could be stolen=
.
>
> You could do this logic inside a hardware-wallet-like device that checks
> the proposed updates and verifies the new state is favorable before
> signing. This could go a long way to hardening lightning nodes against
> potential compromise.
>
> But if we go a step further, what if we enable that logic of ensuring the
> state is more favorable with an on-chain mechanism? This was where my ide=
a
> got a bit hand wavy, but I think it could theoretically be done. The
> receiving-key would be able to sign receiving transactions that would onl=
y
> be valid when the most recent state signed by the spending-key is also
> included in the script sig in some way. Some Script would then validate
> that the receiving-key state being published is more favorable than the
> spending-key state in that transaction's outputs. You'd have a couple
> guarantees:
>
> 1. The usual guarantee that if the presented last spending-key state is
> actually out of date, the transaction could be overridden by the newer
> state in some way (eg eltoo style or punishment).
> 2. The state being published can be no worse than the presented
> spending-key state. Yes, your channel partner could compromise your
> receiving/routing node and then publish an out of date receiving-key
> channel state that's based on the most-recent spending-key state, but it
> would limit your losses to at most the amount of money you've received
> since the last time you manually signed a channel state with your
> spending-key. Because the always-online system empowered to receive does
> *not* have the spending-key, anyone that compromises that node can't spen=
d
> and the damage is limited.
>
> While less straight-forward than for receiving, in principle it seems lik=
e
> something similar could be done for routing (which would require presenti=
ng
> the state of multiple channels, and so has some additional complexities
> there I haven't worked out).
>
> This kind of thing might be a way of working around interactivity
> requirements of payment pools and the like. All participants still have t=
o
> be aware of the whole state (eg of the payment pool), but this awareness
> can be delegated to a system you have limited trust in. Payment pool
> participants could delegate an always-online system empowered with a
> separate key to sign payment pool updates that user's state isn't changed
> for, allowing the payment pool to do its thing without exposing the user =
to
> hot-key vulnerabilities in that always-online system. Double spending is
> prevented because the user can access their always-online system to get t=
he
> full payment pool state.
>
> So in short, while I think there may be no way to fundamentally not
> require interactivity, there are workarounds that can limit how often ful=
l
> interactivity is needed as well as ways to make it easier to provide that
> full interactivity without compromising other aspects of each participant=
's
> security.
>
> On Thu, Apr 28, 2022 at 8:20 AM Antoine Riard via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Hi,
>>
>> This post recalls the noticeable interactivity issue encumbering payment
>> pools and channel factories in the context of a high number of
>> participants, describes how the problem can be understood and proposes f=
ew
>> solutions with diverse trust-minizations and efficiency assumptions. It =
is
>> intended to capture the theoretical bounds of the "interactivity issue",
>> where technical completeness of the solutions is exposed in future works=
.
>>
>> The post assumes a familiarity with the CoinPool paper concepts and
>> terminology [0].
>>
>> # The interactivity requirement grieving payment pools/channel factories
>>
>> Payment pools and channel factories are multi-party constructions
>> enabling to share the ownership of a single on-chain UTXO among many
>> off-chain/promised balances. Payment pool improves on the channel factor=
y
>> construction fault-tolerance by reducing the number of balance outputs
>> disclosed  on-chain to a single one in case of unilateral user exits.
>>
>> However, those constructions require all the users to be online and
>> exchange rounds of signatures to update the balance distribution. Those
>> liveliness/interactivity requirements are increasing with the number of
>> users, as there are higher odds of *one* lazzy/buggy/offline user stalli=
ng
>> the pool/factory updates.
>>
>> In echo, the design of LN was envisioned for a network of
>> always-online/self-hosted participants, the early deployment of LN showe=
d
>> the resort to delegated channel hosting solutions, relieving users from =
the
>> liveliness requirement. While the trust trade-offs of those solutions ar=
e
>> significant, they answer the reality of a world made of unreliable netwo=
rks
>> and mobile devices.
>>
>> Minding that observation, the attractiveness of pools/factories might be
>> questioned.
>>
>> # The interactivity requirement palliatives and their limits
>>
>> Relatively straightforward solutions to lower the interactivity
>> requirement, or its encumbered costs, can be drawn out. Pools/factories
>> users could own (absolute) timelocked kick-out abilities to evict offlin=
e
>> users who are not present before expiration.
>>
>> E.g, let's say you have Alice, Bob, Caroll and Dave as pool participants=
.
>> Each of them owns a Withdraw transaction to exit their individual balanc=
es
>> at any time. Each user should have received the pre-signed components fr=
om
>> the others guaranteeing the unilateral ability to publish the Withdraw.
>>
>> A kick-out ability playable by any pool user could be provided by
>> generating a second set of Withdraw transactions, with the difference of
>> the nLocktime field setup to an absolute height T + X, where T is the
>> height at which the corresponding Update transaction is generated and X =
the
>> kick-out delay.  For this set of kick-out transactions, the complete
>> witnesses should be fully shared among Alice, Bob, Caroll and Dave. That
>> way, if Caroll is unresponsive to move the pool state forward after X, a=
ny
>> one of Alice, Bob or Dave can publish the Caroll kick-out Withdraw
>> transaction, and pursue operations without that unresponsive party.
>>
>> While decreasing the interactivity requirement to the timelock delay,
>> this solution is constraining the kicked user to fallback on-chain
>> encumbering the UTXO set with one more entry.
>>
>> Another solution could be to assume the widespread usage of node towers
>> among the pool participants. Those towers would host the full logic and =
key
>> state necessary to receive an update request and produce a user's approv=
al
>> of it. As long as one tower instance is online per-user, the pool/factor=
y
>> can move forward. Yet this is forcing the pool/factory user to share the=
ir
>> key materials with potentially lower trusted entities, if they don't
>> self-host the tower instances.
>>
>> Ideally, I think we would like a trust-minimized solution enabling
>> non-interactive, off-chain updates of the pool/factory, with no or minim=
al
>> consumption of blockspace.
>>
>> For the remainder of this post, only the pool use-case will be mentioned=
.
>> Though, I think the observations/implications can be extended to factori=
es
>> as well.
>>
>> # Non-interactive Off-chain Pool Partitions
>>
>> If a pool update fails because of lack of online unanimity, a partition
>> request could be exchanged among the online subset of users ("the
>> actives"). They decide to partition the pool by introducing a new layer =
of
>> transactions gathering the promised/off-chain outputs of the actives. Th=
e
>> set of outputs belonging to the passive users remains unchanged.
>>
>> The actives spend their Withdraw transactions `user_balance` outputs bac=
k
>> to a new intermediate Update transaction. This "intermediate" Update
>> transaction is free to re-distribute the pool balances among the active
>> users. To guarantee the unilateral withdraw ability of a partitioned-up
>> balance, the private components of the partitioned Withdraw transactions
>> should be revealed among the set of active users.
>>
>> E.g, let's say you have Alice, Bob, Caroll and Dave as pool participants=
.
>> Pool is at state N, Bob and Dave are offline. Alice and Caroll agree to
>> partition the pool, each of them owns a Withdraw transaction
>> ready-to-be-attached on the Update transaction N. They generate a new
>> partitioning Update transaction with two inputs spending respectively
>> Alice's Withdraw transaction `user_balance` output and Caroll's Withdraw
>> transaction `user-balance` output. From this partitioning Update
>> transaction, two new second-layer Withdraw ones are issued.
>>
>> Alice and Caroll reveal to each other the private components of their
>> first-layer Withdraw transactions, allowing to publish the full branch :
>> first-layer Update transaction, first-layer Withdraw transactions,
>> second-layer partitioning Update transaction, second-layer partitioned
>> Withdraw transaction. At that step, I think the partitioning should be
>> complete.
>>
>> Quickly, a safety issue arises with pool partitioning. A participant of
>> the active set A could equivocate the partition state by signing another
>> spend of her Withdraw transaction allocating her balance to an Update
>> transaction of a "covert" set of active users B.
>>
>> This equivocation exists because there is no ordering of the off-chain
>> spend of the Withdraw transactions and any Withdraw transaction can be
>> freely spent by its owner. This issue appears as similar to solving the
>> double-spend problem.
>>
>> Equivocation is a different case than multiple *parallel* partitions,
>> where there is no intersection between the partitioned balances. The
>> parallel partitions are still rooting from the same Update transaction N=
. I
>> think the safety of parallel partitions is yet to be explored.
>>
>> # Current solutions to the double-spend problem : Bitcoin base-layer &
>> Lightning Network
>>
>> Of course, the double-spend issue is already addressed on the Bitcoin
>> base-layer due to nodes consensus convergence on the most-proof-of-work
>> accumulated valid chain of blocks. While reorg can happen, a UTXO cannot=
 be
>> spent twice on the same chain. This security model can be said to be
>> prophylactic, i.e an invalid block cannot be applied to a node's state a=
nd
>> should be rejected.
>>
>> The double-spend issue is also solved in its own way in payment channels=
.
>> If a transaction is published, of which the correctness has been revoked
>> w.r.t negotiated, private channel state, the wronged channel users must
>> react in consequence. This security model can be said to be corrective,
>> states updates are applied first on the global ledger then eventually
>> corrected.
>>
>> A solution to the pool partition equivocation issue appears as either
>> based on a prophylactic one or a corrective security model.
>>
>> Let's examine first, a reactive security model similar to LN-Penalty. At
>> pool partition proposals, the owners of the partitioned-up Withdraw
>> transactions could reveal a revocation secret enabling correction in cas=
e
>> of wrongdoing (e.g single-show signatures). However, such off-chain
>> revocation can be committed towards multiple sets of honest "active" use=
rs.
>> Only one equivocating balance spend can succeed, letting the remaining s=
et
>> of honest users still be deprived of their expected partitioned balances=
.
>>
>> E.g, let's say you have Alice, Bob, Caroll and Dave as pool participants=
.
>> Alice contacts Bob to form a first partition, then Caroll to form a seco=
nd
>> one, then Dave to form a last one. If she is successful in that
>> equivocation trick, she can *triple*-spend her balance against any goods=
 or
>> out-of-pool payments.
>>
>> Assuming the equivocation is discovered once realized, Bob, Caroll and
>> Dave are all left with a branch of transactions all including Alice's
>> Withdraw one. However only one branch can be fully published, as a Withd=
raw
>> transaction can be played only once following the pool semantic.
>> Game-theory-wise, Bob, Caroll and Dave have an interest to enter in a fe=
e
>> race to be the first to confirm and earn the Alice balance spend.
>>
>> The equivocation is only bounded by the maximal number of equivocating
>> sets one can form, namely the number of pool users. However, correction =
can
>> only be limited to the equivocated balance. Therefore, it appears that
>> corrective security models in the context of multi-party are always
>> producing an economic disequilibrium.
>>
>> An extension of this corrective model could be to require off-pool
>> collaterals locked-up, against which the revocation secret would be
>> revealed at partition generation. However, this fix is limited to the
>> collateral liquidity available. One collateral balance should be guarant=
eed
>> for each potential victim, thus the collateral liquidity should be equal=
 to
>> the number of pool users multiplied by the equivocatable balance amount.
>>
>> It sounds like a more economic-efficient security model of the pool
>> partitioning can be established with a prophylactic technique.
>>
>> # Trusted coordinator
>>
>> A genuine solution could be to rely on a coordinator collecting the
>> partition declaration and order them canonically. The pool partition
>> candidates can then fetch them and decide their partitions acceptance
>> decisions on that. Of course, the coordinator is trusted and can drop or
>> dissimulate any partition, thus enabling partitioned balance equivocatio=
n.
>>
>> # Trust-minimized : Partition Statements
>>
>> A pool partition invalidity can be defined by the existence of two
>> second-layer Update transactions at the same state number spending the s=
ame
>> Withdraw transaction balance output. Each Update transaction signature c=
an
>> be considered as a "partition statement". A user wishing to join a
>> partition should ensure there is no conflicting partition statement befo=
re
>> applying the partition to her local state.
>>
>> The open question is from where the conflict should be observed. A
>> partition statement log could be envisioned and monitored by pool users
>> before to accept any partition.
>>
>> I think multiple partition statement publication spaces can be drawn out=
,
>> with different trust-minization trade-offs.
>>
>> # Publication space : Distributed Bulletin Boards
>>
>> The set of "active" pool users could host their own boards of partition
>> statements. They would coordinate on the statement order through a
>> consensus algorithm (e.g Raft). For redundancy, a user can have multiple
>> board instances. If a user falls offline, they can fetch the statement
>> order from the other users boards.
>>
>> However, while this solution distributes the trust across all the other
>> users, it's not safe in case of malicious user coalitions agreeing among
>> themselves to drop a partition statement. Therefore, a user catching up
>> online can be feeded with an incorrect view of the existing partitions, =
and
>> thus enter into an equivocated partition.
>>
>> # Publication space : On-chain Authoritative Board
>>
>> Another solution could be to designate an authoritative UTXO at pool
>> setup. This UTXO could be spent by any user of the pool set (1-of-N) to =
a
>> covenanted transaction sending back to a Taproot output with the same
>> internal key. The Merkelized tree tweaked could be modified by the spend=
er
>> to stamp the partition statements as leaves hashes. The statement data i=
s
>> not committed in the leaves itself and the storage can be delegated to
>> out-of-band archive servers.
>>
>> E.g, let's say you have Alice, Bob, Caroll and Dave as pool participants=
.
>> Alice and Bob decide to start a partition, they commit a hash of the
>> partitioning Update transaction as a Taproot tree leaf and they spend th=
e
>> pool authoritative UTXO. They also send a copy of the Update transaction=
 to
>> an archive server.
>>
>> At a later time, Alice proposes to Caroll to start a partition. Caroll
>> follows the chain of transactions forming the on-chain authoritative boa=
rd,
>> she fetches the merkle branches and leaves data payload from an archive
>> server, verifying the authenticity of the branches and payload. As Alice
>> has already published a partition statement spending her Withdraw, Carol=
l
>> should refuse the partition proposal.
>>
>> Even if a pool user goes offline, she can recover the correct partition
>> statement logs, as it has been committed in the chain from the
>> authoritative UTXO. If the statement data is not available from servers,
>> the pool user should not engage in partitions.
>>
>> Assuming the spend confirms in every block, this solution enables
>> partitions every 10min. The cost can be shared across pool instances, if
>> the authoritative signers set is made of multiple pool instances signers
>> sets. A threshold signature scheme could be used to avoid interactivity
>> beyond the aggregated key setup. However, batching across pool instances
>> increases the set of data to verify by the partition candidate users, wh=
ich
>> could be a grievance for bandwidth-constrained clients.
>>
>> # Fiability of the Publication of Partition Statements
>>
>> Whatever ends up being used as a partition statement log, there is still
>> the question of the incentives of pool users to publish the partition
>> statements. A malicious user could act in coalition with the equivocatin=
g
>> entity to retain the publication of her partition statement. Thus, an
>> honest user would only be aware of her own partition statement and accep=
t
>> the partition proposal from the will-be equivocating entity.
>>
>> I think that leveraging covenants a revocation mechanism could be
>> attached on any equivocating branch of transactions, allowing in the abo=
ve
>> case a single honest user to punish the publication. While a revocation
>> mechanism does not work in case of multiple defrauded users, I believe t=
he
>> existence of a revocation mechanism makes the formation of malicious
>> coalitions unsafe for their conjurers.
>>
>> Indeed, any user entering in the coalition is not guaranteed to be
>> blinded to other equivocating branches generated by the partition
>> initiator. Therefore, the publication of a partition statement by everyo=
ne
>> is holistically optimal to discover any equivocating candidate among the
>> pool users.
>>
>> Further research should establish the soundness of the partition
>> statement publication game-theory.
>>
>> # Writing the Partition Statements to a new Consensus Data Structure
>>
>> To avoid a solution relying on game-theory, a new consensus data
>> structure could be introduced to register and order the partition
>> statements. This off-chain contract register could be a Merkle tree, whe=
re
>> every leaf is a pool balance identified by a key. This register would be
>> established on-chain at the same time the pool is set up.
>>
>> Every time the pool is partitioned, the tree leaves would be updated wit=
h
>> the partition statement committed to. Only one partition could be
>> registered per user by state number. The publication branch would be
>> invalid if it doesn't point back to the corresponding contract register
>> tree entries. When the first-layer pool Update transaction is replaced, =
the
>> tree should transition to a blank state too.
>>
>> Beyond the high cost of yet-another softfork to introduce such consensus
>> data structure, the size of the witness to write into the contract regis=
ter
>> could be so significant that the economic attractiveness of pool
>> partitioning is decreased in consequence.
>>
>> If you have read so far, thank you. And curious if anyone has more ideas
>> or thoughts on  the high interactivity issue ?
>>
>> Thanks Gleb for the review.
>>
>> Cheers,
>> Antoine
>>
>> [0] https://coinpool.dev/
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>

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

<div dir=3D"ltr">Hi Billy,<br><br>Thanks for reading.<br><br>&gt; A. Create=
 sub-pools when the whole group is live that can be used by the<br>&gt; sub=
- pool participants later without the whole group&#39;s involvement. The<br=
>&gt; whole group is needed to change the whole group&#39;s state (eg close=
 or open<br>&gt; sub-pools), but sub-pool states don&#39;t need to involve =
the whole group.<br><br>Yes this could be a direction. Assume you have a fa=
n-out transaction spending the Update transaction to a combination of sub-p=
ools. I think you have two problems arising.<br><br>The first one it&#39;s =
hard to predict in advance the subset of pool participants which will be in=
active, and thus guaranteeing stale-free sub-pools. Further, it&#39;s also =
hard to predict in advance the liquidity needs of the sub-pools. So I think=
 this prediction of these two factors is unlikely to be correct, this state=
ment getting more sound as the number of pool participants increases.<br><b=
r>The second one, this fan-out transaction could interfere with the confirm=
ation of the simple withdraw transactions, and thus the uplifted constructi=
ons (e.g a LN channel). So there is an open question about the &quot;honest=
&quot; usage of the sub-pool states themselves.<br><br>&gt; B. Have an alwa=
ys-online system empowered to sign only for group updates<br>&gt; that *do =
not* change the owner&#39;s balance in the group. This could be done<br>&gt=
; with a hardware-wallet like device, or could be done with some kind of ne=
w<br>&gt; set of opcodes that can be used to verify that a particular trans=
action<br>&gt; isn&#39;t to the owner&#39;s detriment.<br><br>Sure, one cou=
ld envision an accumulator committing directly to balances too. State trans=
ition would be allowed only if the non-involved users balances are immutabl=
y preserved to, only the active users balances are mixed. I think the chall=
enge is to find a compact accumulator with those properties.<br><br>About t=
he &quot;hardware-wallet like device&quot;/&quot;towers&quot; solution, yes=
 this is a known technique to solve interactivity. Sadly, this can be a sig=
nificant requirement for a lot of users to run an additional always-online =
process. It&#39;s more likely a lot of them will delegate this operation to=
 third-party providers, with the known reductions in terms of trust-minimiz=
ations.<br><br>&gt; Come to think of it tho, this doesn&#39;t actually solv=
e the double spending<br>&gt; problem. The fundamental issue is that if you=
 have a subset of participants<br>&gt; creating partitions like this, witho=
ut the involvement of the whole group,<br>&gt; its impossible for any subse=
t of participants to know for sure that there<br>&gt; isn&#39;t a double-sp=
ending partition amongst another set of members of the<br>&gt; group.<br><b=
r>Yes, it seems we agree that equivocation opening the way to balance doubl=
e-spend is the hard issue with partitioning multi-party constructions.<br><=
br>&gt; I had a conceptual idea a while back (that I can&#39;t find at the =
moment)<br>&gt; about offline lightning receiving. The concept is that each=
 lightning node<br>&gt; in a channel has two separate keys: a spending-key =
and a receiving-key. The<br>&gt; spending-key must be used manually by the =
node owner to send payments,<br>&gt; however the receiving-key can be given=
 to an always-online service that can<br>&gt; use that key only to either r=
eceive funds (ie update the state to a more<br>&gt; favorable state).<br><b=
r>Hmmm, how could you prevent the always-online service from using the rece=
iving-key in &quot;spending&quot; mode if the balance stacked there becomes=
 relevant ?<br><br>&gt; You could do this logic inside a hardware-wallet-li=
ke device that checks<br>&gt; the proposed updates and verifies the new sta=
te is favorable before<br>&gt; signing. This could go a long way to hardeni=
ng lightning nodes against<br>&gt; potential compromise.<br><br>Yes, see <a=
 href=3D"https://gitlab.com/lightning-signer/docs">https://gitlab.com/light=
ning-signer/docs</a> for wip in that direction.<br><br>&gt; This kind of th=
ing might be a way of working around interactivity<br>&gt; requirements of =
payment pools and the like. All participants still have to<br>&gt; be aware=
 of the whole state (eg of the payment pool), but this awareness<br>&gt; ca=
n be delegated to a system you have limited trust in. Payment pool<br>&gt; =
participants could delegate an always-online system empowered with a<br>&gt=
; separate key to sign payment pool updates that user&#39;s state isn&#39;t=
 changed<br>&gt; for, allowing the payment pool to do its thing without exp=
osing the user to<br>&gt; hot-key vulnerabilities in that always-online sys=
tem. Double spending is<br>&gt; prevented because the user can access their=
 always-online system to get the<br>&gt; full payment pool state.<br><br>Wh=
ile I would be curious to see such Script-based &quot;receiving-key&quot; o=
nly mechanism (maybe with IN_OUT_AMOUNT-style of covenant) I wonder if it w=
ould solve equivocation fully. A malicious pool participant could still com=
mit her off-chain balance in two partitions and send spends to the A&amp;B =
hosting &quot;receiving-keys&quot; entities without them being aware of the=
 conflict, in the lack of a reconciliation such as a publication space ? Or=
 do you have another thinking ?<br><br>Antoine<br></div><br><div class=3D"g=
mail_quote"><div dir=3D"ltr" class=3D"gmail_attr">Le=C2=A0dim. 1 mai 2022 =
=C3=A0=C2=A018:53, Billy Tetrud &lt;<a href=3D"mailto:billy.tetrud@gmail.co=
m">billy.tetrud@gmail.com</a>&gt; a =C3=A9crit=C2=A0:<br></div><blockquote =
class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px sol=
id rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr">Hi Antoine,<div><br>=
</div><div>Very interesting exploration. I think you&#39;re right that ther=
e are issues with the kind of partitioning you&#39;re talking about. Lightn=
ing works because all participants sign all=C2=A0offchain states (barring d=
ata loss). If a participant can be excluded from needing to agree to a new =
state, there must be an additional mechanism to ensure the relevant state f=
or that participant isn&#39;t changed to their detriment.=C2=A0</div><div><=
br></div><div><div>To summarize my below email, the two techniques I can th=
ink for solving this problem are:</div><div><br></div><div>A. Create sub-po=
ols when the whole group is live that can be used by the sub-

pool=C2=A0participants later without the whole group&#39;s involvement. The=
 whole group is needed to change the whole group&#39;s state (eg close or o=
pen sub-pools), but sub-pool=C2=A0states don&#39;t need to involve the whol=
e group.</div></div><div>B. Have an always-online system empowered to sign =
only for group updates that *do not* change the owner&#39;s balance in the =
group. This could be done with a hardware-wallet like device, or could be d=
one with some kind of new set of opcodes that can be used to verify that a =
particular transaction isn&#39;t to the owner&#39;s detriment.</div><div><b=
r></div><div>I had some thoughts that I think don&#39;t pan out, but here t=
hey are anyway:</div><div><br></div><div>What if the pool state transaction=
 (that returns everyone&#39;s money) has each participant sign the input=C2=
=A0+ their personal output (eg with sighash flags)? That way the transactio=
n could have=C2=A0outputs swapped out by a subset of participants as needed=
. Some kind of eltoo mechanism could then ensure that the latest transactio=
n can override earlier=C2=A0transactions. As far as the non-participating m=
embers are concerned, they don&#39;t care whether the newest state is publi=
shed or whether the newest state they participated in is published - becaus=
e their output is identical either way. However, I can see that there might=
 be problems related to separate groups of participants creating conflictin=
g transactions, ie A B &amp; C create a partition like this, and so do D E =
&amp; F, but they don&#39;t know about each other&#39;s=C2=A0state. If they=
 have some always-online coordination mechanism, this could be solved as lo=
ng as the participants aren&#39;t malicious. But it still leaves open the p=
ossibility that some participants could intentionally grief others by inten=
tionally creating conflicting state transactions. Theoretically it could be=
 structured so that no funds could be directly stolen, but it seems unavoid=
able that some group of members could create a secret transaction that when=
 published makes the most recent honest state not minable.=C2=A0</div><div>=
<br></div><div>Come to think of it tho, this doesn&#39;t actually solve the=
 double spending problem. The fundamental issue is that if you have a subse=
t of participants creating partitions like this, without the involvement of=
 the whole group, its impossible for any subset of participants to know for=
 sure that there isn&#39;t a double-spending partition amongst=C2=A0another=
 set of members of the group.</div><div><br></div><div>On-chain bitcoin tra=
nsactions prevent double spending by ensuring that everyone knows what outp=
uts have been spent. Payment channels prevent double spending by ensuring t=
hat everyone that&#39;s part of the channel knows what the current channel =
state is. Any 3rd layer probably needs this exact property: everyone involv=
ed must know the state. So you should be able to create a partition when th=
e whole group is live, and thereafter the members of that partition can use=
 that partition without involving the rest of the group. I think that patte=
rn can work to any level of depth. After thinking about this, I conjecture =
it might be a fundamental property of the double spending problem. All part=
icipants must be aware of the whole state otherwise the double spending pro=
blem exists for those who aren&#39;t aware of the whole state.</div><div><b=
r></div><div>&gt; this is forcing the pool/factory user to share their key =
materials with potentially lower trusted entities, if they don&#39;t self-h=
ost the tower instances.</div><div><br></div><div>I had a conceptual idea a=
 while back (that I can&#39;t find at the moment) about offline lightning r=
eceiving. The concept is that each lightning node in a channel has two sepa=
rate keys: a spending-key and a receiving-key. The spending-key must be use=
d manually by the node owner to send payments, however the receiving-key ca=
n be given to an always-online service that can use that key only to either=
 receive funds (ie update the state to a more favorable state).=C2=A0</div>=
<div><br></div><div>Right now with just a single-hot-key setup you need to =
trust your online system to only sign receiving transactions and would refu=
se to sign any proposed channel update not in the owner&#39;s favor. Howeve=
r, if the node was compromised all bets are off - the entire channel balanc=
e could be stolen.=C2=A0</div><div><br></div><div>You could do this logic i=
nside a hardware-wallet-like device that checks the proposed updates and ve=
rifies the new state is favorable before signing. This could go a long way =
to hardening=C2=A0lightning nodes against potential compromise.=C2=A0</div>=
<div><br></div><div>But if we go a step further, what if we enable that log=
ic of ensuring the state is more favorable with an on-chain mechanism? This=
 was where my idea got a bit hand wavy, but I think it could theoretically =
be done. The receiving-key would be able to sign receiving transactions tha=
t would only be valid when the most recent state signed by the spending-key=
 is also included in the script sig in some way. Some Script would then val=
idate that the receiving-key state being published is more favorable than t=
he spending-key state in that transaction&#39;s outputs. You&#39;d have a c=
ouple guarantees:</div><div><br></div><div>1. The usual guarantee that if t=
he presented last spending-key state is actually out of date, the transacti=
on could be overridden by the newer state in some way (eg eltoo style or pu=
nishment).</div><div>2. The state being published can be no worse than the =
presented spending-key state. Yes, your channel partner could compromise yo=
ur receiving/routing node and then publish an out of date receiving-key cha=
nnel state that&#39;s based on the most-recent spending-key state, but it w=
ould limit your losses to at most the amount of money you&#39;ve received s=
ince the last time you manually signed a channel state with your spending-k=
ey. Because the always-online system empowered to receive does *not* have t=
he spending-key, anyone that compromises that node can&#39;t spend and the =
damage is limited.</div><div><br></div><div><div>While less straight-forwar=
d=C2=A0than for receiving, in principle it seems like something similar cou=
ld be done for routing (which would require presenting the state of multipl=
e channels,=C2=A0and so has some additional complexities there I haven&#39;=
t worked out).=C2=A0<br></div><div><br></div><div>This kind of thing might =
be a way of working around interactivity requirements of payment pools and =
the like. All participants still have to be aware of the whole state (eg of=
 the payment pool), but this awareness can be delegated to a system you=C2=
=A0have limited trust in. Payment pool participants could delegate an alway=
s-online system empowered with a separate key to sign payment pool updates =
that user&#39;s state isn&#39;t changed for, allowing the payment pool to d=
o its thing without exposing the user to hot-key vulnerabilities in that al=
ways-online system. Double spending is prevented because the user can acces=
s their always-online system to get the full payment pool state.</div></div=
><div><br></div><div>So in short, while I think there may be no way to fund=
amentally not require interactivity, there are workarounds that can limit h=
ow often full interactivity is needed as well as ways to make it easier to =
provide that full interactivity without compromising other aspects of each =
participant&#39;s security.=C2=A0</div></div><br><div class=3D"gmail_quote"=
><div dir=3D"ltr" class=3D"gmail_attr">On Thu, Apr 28, 2022 at 8:20 AM Anto=
ine Riard via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoun=
dation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;=
 wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=
=3D"ltr">Hi,<br><br>This post recalls the noticeable interactivity issue en=
cumbering payment pools and channel factories in the context of a high numb=
er of participants, describes how the problem can be understood and propose=
s few solutions with diverse trust-minizations and efficiency assumptions. =
It is intended to capture the theoretical bounds of the &quot;interactivity=
 issue&quot;, where technical completeness of the solutions is exposed in f=
uture works.<br><br>The post assumes a familiarity with the CoinPool paper =
concepts and terminology [0].<br><br># The interactivity requirement grievi=
ng payment pools/channel factories<br><br>Payment pools and channel factori=
es are multi-party constructions enabling to share the ownership of a singl=
e on-chain UTXO among many off-chain/promised balances. Payment pool improv=
es on the channel factory construction fault-tolerance by reducing the numb=
er of balance outputs disclosed=C2=A0 on-chain to a single one in case of u=
nilateral user exits.<br><br>However, those constructions require all the u=
sers to be online and exchange rounds of signatures to update the balance d=
istribution. Those liveliness/interactivity requirements are increasing wit=
h the number of users, as there are higher odds of *one* lazzy/buggy/offlin=
e user stalling the pool/factory updates.<br><br>In echo, the design of LN =
was envisioned for a network of always-online/self-hosted participants, the=
 early deployment of LN showed the resort to delegated channel hosting solu=
tions, relieving users from the liveliness requirement. While the trust tra=
de-offs of those solutions are significant, they answer the reality of a wo=
rld made of unreliable networks and mobile devices.<br><br>Minding that obs=
ervation, the attractiveness of pools/factories might be questioned.<br><br=
># The interactivity requirement palliatives and their limits<br><br>Relati=
vely straightforward solutions to lower the interactivity requirement, or i=
ts encumbered costs, can be drawn out. Pools/factories users could own (abs=
olute) timelocked kick-out abilities to evict offline users who are not pre=
sent before expiration.<br><br>E.g, let&#39;s say you have Alice, Bob, Caro=
ll and Dave as pool participants. Each of them owns a Withdraw transaction =
to exit their individual balances at any time. Each user should have receiv=
ed the pre-signed components from the others guaranteeing the unilateral ab=
ility to publish the Withdraw.<br><br>A kick-out ability playable by any po=
ol user could be provided by generating a second set of Withdraw transactio=
ns, with the difference of the nLocktime field setup to an absolute height =
T + X, where T is the height at which the corresponding Update transaction =
is generated and X the kick-out delay.=C2=A0 For this set of kick-out trans=
actions, the complete witnesses should be fully shared among Alice, Bob, Ca=
roll and Dave. That way, if Caroll is unresponsive to move the pool state f=
orward after X, any one of Alice, Bob or Dave can publish the Caroll kick-o=
ut Withdraw transaction, and pursue operations without that unresponsive pa=
rty.<br><br>While decreasing the interactivity requirement to the timelock =
delay, this solution is constraining the kicked user to fallback on-chain e=
ncumbering the UTXO set with one more entry.<br><br>Another solution could =
be to assume the widespread usage of node towers among the pool participant=
s. Those towers would host the full logic and key state necessary to receiv=
e an update request and produce a user&#39;s approval of it. As long as one=
 tower instance is online per-user, the pool/factory can move forward. Yet =
this is forcing the pool/factory user to share their key materials with pot=
entially lower trusted entities, if they don&#39;t self-host the tower inst=
ances.<br><br>Ideally, I think we would like a trust-minimized solution ena=
bling non-interactive, off-chain updates of the pool/factory, with no or mi=
nimal consumption of blockspace.<br><br>For the remainder of this post, onl=
y the pool use-case will be mentioned. Though, I think the observations/imp=
lications can be extended to factories as well.<br><br># Non-interactive Of=
f-chain Pool Partitions<br><br>If a pool update fails because of lack of on=
line unanimity, a partition request could be exchanged among the online sub=
set of users (&quot;the actives&quot;). They decide to partition the pool b=
y introducing a new layer of transactions gathering the promised/off-chain =
outputs of the actives. The set of outputs belonging to the passive users r=
emains unchanged.<br><br>The actives spend their Withdraw transactions `use=
r_balance` outputs back to a new intermediate Update transaction. This &quo=
t;intermediate&quot; Update transaction is free to re-distribute the pool b=
alances among the active users. To guarantee the unilateral withdraw abilit=
y of a partitioned-up balance, the private components of the partitioned Wi=
thdraw transactions should be revealed among the set of active users.<br><b=
r>E.g, let&#39;s say you have Alice, Bob, Caroll and Dave as pool participa=
nts. Pool is at state N, Bob and Dave are offline. Alice and Caroll agree t=
o partition the pool, each of them owns a Withdraw transaction ready-to-be-=
attached on the Update transaction N. They generate a new partitioning Upda=
te transaction with two inputs spending respectively Alice&#39;s Withdraw t=
ransaction `user_balance` output and Caroll&#39;s Withdraw transaction `use=
r-balance` output. From this partitioning Update transaction, two new secon=
d-layer Withdraw ones are issued.<br><br>Alice and Caroll reveal to each ot=
her the private components of their first-layer Withdraw transactions, allo=
wing to publish the full branch : first-layer Update transaction, first-lay=
er Withdraw transactions, second-layer partitioning Update transaction, sec=
ond-layer partitioned Withdraw transaction. At that step, I think the parti=
tioning should be complete.<br><br>Quickly, a safety issue arises with pool=
 partitioning. A participant of the active set A could equivocate the parti=
tion state by signing another spend of her Withdraw transaction allocating =
her balance to an Update transaction of a &quot;covert&quot; set of active =
users B.<br><br>This equivocation exists because there is no ordering of th=
e off-chain spend of the Withdraw transactions and any Withdraw transaction=
 can be freely spent by its owner. This issue appears as similar to solving=
 the double-spend problem.<br><br>Equivocation is a different case than mul=
tiple *parallel* partitions, where there is no intersection between the par=
titioned balances. The parallel partitions are still rooting from the same =
Update transaction N. I think the safety of parallel partitions is yet to b=
e explored.<br><br># Current solutions to the double-spend problem : Bitcoi=
n base-layer &amp; Lightning Network<br><br>Of course, the double-spend iss=
ue is already addressed on the Bitcoin base-layer due to nodes consensus co=
nvergence on the most-proof-of-work accumulated valid chain of blocks. Whil=
e reorg can happen, a UTXO cannot be spent twice on the same chain. This se=
curity model can be said to be prophylactic, i.e an invalid block cannot be=
 applied to a node&#39;s state and should be rejected.<br><br>The double-sp=
end issue is also solved in its own way in payment channels. If a transacti=
on is published, of which the correctness has been revoked w.r.t negotiated=
, private channel state, the wronged channel users must react in consequenc=
e. This security model can be said to be corrective, states updates are app=
lied first on the global ledger then eventually corrected.<br><br>A solutio=
n to the pool partition equivocation issue appears as either based on a pro=
phylactic one or a corrective security model.<br><br>Let&#39;s examine firs=
t, a reactive security model similar to LN-Penalty. At pool partition propo=
sals, the owners of the partitioned-up Withdraw transactions could reveal a=
 revocation secret enabling correction in case of wrongdoing (e.g single-sh=
ow signatures). However, such off-chain revocation can be committed towards=
 multiple sets of honest &quot;active&quot; users. Only one equivocating ba=
lance spend can succeed, letting the remaining set of honest users still be=
 deprived of their expected partitioned balances.<br><br>E.g, let&#39;s say=
 you have Alice, Bob, Caroll and Dave as pool participants. Alice contacts =
Bob to form a first partition, then Caroll to form a second one, then Dave =
to form a last one. If she is successful in that equivocation trick, she ca=
n *triple*-spend her balance against any goods or out-of-pool payments.<br>=
<br>Assuming the equivocation is discovered once realized, Bob, Caroll and =
Dave are all left with a branch of transactions all including Alice&#39;s W=
ithdraw one. However only one branch can be fully published, as a Withdraw =
transaction can be played only once following the pool semantic. Game-theor=
y-wise, Bob, Caroll and Dave have an interest to enter in a fee race to be =
the first to confirm and earn the Alice balance spend.<br>=C2=A0<br>The equ=
ivocation is only bounded by the maximal number of equivocating sets one ca=
n form, namely the number of pool users. However, correction can only be li=
mited to the equivocated balance. Therefore, it appears that corrective sec=
urity models in the context of multi-party are always producing an economic=
 disequilibrium.<br><br>An extension of this corrective model could be to r=
equire off-pool collaterals locked-up, against which the revocation secret =
would be revealed at partition generation. However, this fix is limited to =
the collateral liquidity available. One collateral balance should be guaran=
teed for each potential victim, thus the collateral liquidity should be equ=
al to the number of pool users multiplied by the equivocatable balance amou=
nt.<br><br>It sounds like a more economic-efficient security model of the p=
ool partitioning can be established with a prophylactic technique.<br><br>#=
 Trusted coordinator<br><br>A genuine solution could be to rely on a coordi=
nator collecting the partition declaration and order them canonically. The =
pool partition candidates can then fetch them and decide their partitions a=
cceptance decisions on that. Of course, the coordinator is trusted and can =
drop or dissimulate any partition, thus enabling partitioned balance equivo=
cation.<br><br># Trust-minimized : Partition Statements<br><br>A pool parti=
tion invalidity can be defined by the existence of two second-layer Update =
transactions at the same state number spending the same Withdraw transactio=
n balance output. Each Update transaction signature can be considered as a =
&quot;partition statement&quot;. A user wishing to join a partition should =
ensure there is no conflicting partition statement before applying the part=
ition to her local state.<br><br>The open question is from where the confli=
ct should be observed. A partition statement log could be envisioned and mo=
nitored by pool users before to accept any partition.<br><br>I think multip=
le partition statement publication spaces can be drawn out, with different =
trust-minization trade-offs.<br><br># Publication space : Distributed Bulle=
tin Boards<br><br>The set of &quot;active&quot; pool users could host their=
 own boards of partition statements. They would coordinate on the statement=
 order through a consensus algorithm (e.g Raft). For redundancy, a user can=
 have multiple board instances. If a user falls offline, they can fetch the=
 statement order from the other users boards.<br><br>However, while this so=
lution distributes the trust across all the other users, it&#39;s not safe =
in case of malicious user coalitions agreeing among themselves to drop a pa=
rtition statement. Therefore, a user catching up online can be feeded with =
an incorrect view of the existing partitions, and thus enter into an equivo=
cated partition.<br><br># Publication space : On-chain Authoritative Board<=
br><br>Another solution could be to designate an authoritative UTXO at pool=
 setup. This UTXO could be spent by any user of the pool set (1-of-N) to a =
covenanted transaction sending back to a Taproot output with the same inter=
nal key. The Merkelized tree tweaked could be modified by the spender to st=
amp the partition statements as leaves hashes. The statement data is not co=
mmitted in the leaves itself and the storage can be delegated to out-of-ban=
d archive servers.<br><br>E.g, let&#39;s say you have Alice, Bob, Caroll an=
d Dave as pool participants. Alice and Bob decide to start a partition, the=
y commit a hash of the partitioning Update transaction as a Taproot tree le=
af and they spend the pool authoritative UTXO. They also send a copy of the=
 Update transaction to an archive server.<br><br>At a later time, Alice pro=
poses to Caroll to start a partition. Caroll follows the chain of transacti=
ons forming the on-chain authoritative board, she fetches the merkle branch=
es and leaves data payload from an archive server, verifying the authentici=
ty of the branches and payload. As Alice has already published a partition =
statement spending her Withdraw, Caroll should refuse the partition proposa=
l.<br><br>Even if a pool user goes offline, she can recover the correct par=
tition statement logs, as it has been committed in the chain from the autho=
ritative UTXO. If the statement data is not available from servers, the poo=
l user should not engage in partitions.<br><br>Assuming the spend confirms =
in every block, this solution enables partitions every 10min. The cost can =
be shared across pool instances, if the authoritative signers set is made o=
f multiple pool instances signers sets. A threshold signature scheme could =
be used to avoid interactivity beyond the aggregated key setup. However, ba=
tching across pool instances increases the set of data to verify by the par=
tition candidate users, which could be a grievance for bandwidth-constraine=
d clients.<br><br># Fiability of the Publication of Partition Statements<br=
><br>Whatever ends up being used as a partition statement log, there is sti=
ll the question of the incentives of pool users to publish the partition st=
atements. A malicious user could act in coalition with the equivocating ent=
ity to retain the publication of her partition statement. Thus, an honest u=
ser would only be aware of her own partition statement and accept the parti=
tion proposal from the will-be equivocating entity.<br><br>I think that lev=
eraging covenants a revocation mechanism could be attached on any equivocat=
ing branch of transactions, allowing in the above case a single honest user=
 to punish the publication. While a revocation mechanism does not work in c=
ase of multiple defrauded users, I believe the existence of a revocation me=
chanism makes the formation of malicious coalitions unsafe for their conjur=
ers.<br><br>Indeed, any user entering in the coalition is not guaranteed to=
 be blinded to other equivocating branches generated by the partition initi=
ator. Therefore, the publication of a partition statement by everyone is ho=
listically optimal to discover any equivocating candidate among the pool us=
ers.<br><br>Further research should establish the soundness of the partitio=
n statement publication game-theory.<br><br># Writing the Partition Stateme=
nts to a new Consensus Data Structure<br><br>To avoid a solution relying on=
 game-theory, a new consensus data structure could be introduced to registe=
r and order the partition statements. This off-chain contract register coul=
d be a Merkle tree, where every leaf is a pool balance identified by a key.=
 This register would be established on-chain at the same time the pool is s=
et up. <br><br>Every time the pool is partitioned, the tree leaves would be=
 updated with the partition statement committed to. Only one partition coul=
d be registered per user by state number. The publication branch would be i=
nvalid if it doesn&#39;t point back to the corresponding contract register =
tree entries. When the first-layer pool Update transaction is replaced, the=
 tree should transition to a blank state too.<br><br>Beyond the high cost o=
f yet-another softfork to introduce such consensus data structure, the size=
 of the witness to write into the contract register could be so significant=
 that the economic attractiveness of pool partitioning is decreased in cons=
equence.<br><br>If you have read so far, thank you. And curious if anyone h=
as more ideas or thoughts on=C2=A0 the high interactivity issue ?<br><br>Th=
anks Gleb for the review.<br><br>Cheers,<br>Antoine<br><br>[0] <a href=3D"h=
ttps://coinpool.dev/" target=3D"_blank">https://coinpool.dev/</a><br></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>
</blockquote></div>

--00000000000034d3f205de9d8c27--