Re: [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories

From: Antoine Riard <antoine.riard@gmail•com>
To: Billy Tetrud <billy.tetrud@gmail•com>
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
Date: Mon, 9 May 2022 20:38:36 -0400	[thread overview]
Message-ID: <CALZpt+FTB9y6zO4Ap44GwZKVGj17Hv8+fYP02eoevOFA1MO5LA@mail.gmail.com> (raw)
In-Reply-To: <CAGpPWDa2wofye=KSq-vVNS0SOU34st9wm-hMhiYzGLTKMGuP5w@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 30236 bytes --]

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 new
> 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 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).

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 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.

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 à 18:53, Billy Tetrud <billy.tetrud@gmail•com> a écrit :

> 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
>>
>

[-- Attachment #2: Type: text/html, Size: 31011 bytes --]