MIME-Version: 1.0
References: <CALZpt+GNoRdbtfeBtpnitiAZ4jGwSsRpSRXOyX7mzrhwewmBcw@mail.gmail.com>
In-Reply-To: <CALZpt+GNoRdbtfeBtpnitiAZ4jGwSsRpSRXOyX7mzrhwewmBcw@mail.gmail.com>
From: Billy Tetrud <billy.tetrud@gmail.com>
Date: Sun, 1 May 2022 17:53:13 -0500
Message-ID: <CAGpPWDa2wofye=KSq-vVNS0SOU34st9wm-hMhiYzGLTKMGuP5w@mail.gmail.com>
To: Antoine Riard <antoine.riard@gmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000f0e21605ddfb24fb"
Subject: Re: [bitcoin-dev] Conjectures on solving the high interactivity
 issue in payment pools and channel factories
Precedence: list

--000000000000f0e21605ddfb24fb
Content-Type: text/plain; charset="UTF-8"

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 because
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 new
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 subset 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 in is
published - because their output is identical either way. However, I can
see that there might be problems related to separate groups of participants
creating conflicting transactions, ie A B & C create a partition like this,
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 seems
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 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.

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 knows
what the current channel state is. Any 3rd layer probably needs this exact
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 members
of that partition can use that partition without involving the rest of the
group. I think that pattern 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 participants must be aware of the whole state
otherwise the double spending problem exists for those who aren't aware of
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 node
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).

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 was
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 idea
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 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 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 spend
and the damage is limited.

While less straight-forward than for receiving, in principle it seems like
something similar could be done for routing (which would require presenting
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 to
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.

So in short, while I think there may be no way to fundamentally not require
interactivity, there are workarounds that can limit how 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'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 few
> 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 factory
> 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 stalling
> 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 showed
> the resort to delegated channel hosting solutions, relieving users from the
> liveliness requirement. While the trust trade-offs of those solutions are
> significant, they answer the reality of a world made of unreliable networks
> 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 offline
> 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 balances
> at any time. Each user should have received the pre-signed components from
> 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, any
> 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 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 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 minimal
> 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 factories
> 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. The
> set of outputs belonging to the passive users remains unchanged.
>
> The actives spend their Withdraw transactions `user_balance` outputs back
> 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 and
> 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 case
> of wrongdoing (e.g single-show signatures). However, such off-chain
> revocation can be committed towards multiple sets of honest "active" users.
> Only one equivocating balance spend can succeed, letting the remaining set
> 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 second
> 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 Withdraw
> transaction can be played only once following the pool semantic.
> Game-theory-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.
>
> 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 guaranteed
> 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 equivocation.
>
> # 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 same
> Withdraw transaction balance output. Each Update transaction signature can
> be considered as a "partition statement". A user wishing to join a
> partition should ensure there is no conflicting partition statement before
> 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 spender
> to stamp the partition statements as leaves hashes. The statement data is
> 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 the
> 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 board,
> 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, Caroll
> 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, which
> 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 equivocating
> entity to retain the publication of her partition statement. Thus, an
> honest user would only be aware of her own partition statement and accept
> 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 above case a
> single honest user to punish the publication. While a revocation mechanism
> does not work in case of multiple defrauded users, I believe the 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 everyone 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, 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 set up.
>
> Every time the pool is partitioned, the tree leaves would be updated with
> 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 register
> 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
>

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

<div dir=3D"ltr">Hi Antoine,<div><br></div><div>Very interesting exploratio=
n. I think you&#39;re right that there are issues with the kind of partitio=
ning you&#39;re talking about. Lightning works because all participants sig=
n all=C2=A0offchain states (barring data loss). If a participant can be exc=
luded from needing to agree to a new state, there must be an additional mec=
hanism to ensure the relevant state for that participant isn&#39;t changed =
to their detriment.=C2=A0</div><div><br></div><div><div>To summarize my bel=
ow email, the two techniques I can think for solving this problem are:</div=
><div><br></div><div>A. Create sub-pools 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>

--000000000000f0e21605ddfb24fb--