Re: [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories
Hi John, Thanks for the read! > Agreed that signing updates and monitoring the blockchain both create always-online requirements that are not compatible with casual users' desires. I think > it's helpful to separate these two cases, as they affect different parties and their solutions differ. > In particular, limited availability to sign updates affects one's partners and can be addressed by having fewer partners, not partnering with casual users, evicting > unresponsive users, etc. > Limited availability to monitor the blockchain affects the security of one's own funds and can be addressed by increasing one's safety parameters (such as the > to_self_delay parameter in Lightning). Yes, I think effectively the logical coordination of the signed off-chain updates and the chain monitoring is defining the problem space. Of course, there is the solution of having less off-chain partners and bumping safety timelocks. Though here I think it comes at the downside of more UTXO storage requirements for base-layer nodes and an average increase in the price of liquidity for LN users due to more extensive timevalue. I think an intermediary solution can be to make the signing updates (and the fraud proofs or "partition statements" in the post) a structure enforceable by Bitcoin Script in a way than all the "revoked" on-chain partitions can be punished, like with some OP_MERKLE_ADD/TAPROOT_LEAF_UPDATE_VERIFY to ensure the cheater cannot escape the clawback ? > I would argue that we want a completely trust-free solution, if at all possible, while respecting users' actual availability. > We should only consider solutions that require trust if we can't find a trust-free solution that meets all other requirements. I would love to find a completely trust-free solution. One of the hard things is defining trust :) Note, as soon as you start to consider off-chain Bitcoin trust models you have a multi-dimensional risks model to solve e.g miners incentives, network connectivity, mempools congestion, proactive security of your threshold signing shares in face of your counterparty liveliness, consensus upgrades altering network-wide transaction-relay rules, ... > Actually, there's a third class of solutions that are possible, namely ones that use separate control transactions and value transactions (where the value > transactions "spend", and therefore depend on, the control transactions). > If an invalid control transaction is put on-chain, it can be blocked by another user by spending its output(s) before the output(s) can affect the value transaction. > Thus, control transactions can be viewed as proposals for state updates, and those proposals are blocked if they aren't valid. > These solutions differ from prophylactic solutions, as they allow incorrect transactions to be put on-chain and require another user to block them. > They also differ from your definition of a corrective security model, as they never allow the state update to be applied to the value in the channel or pool, so > there's nothing to be corrected. > An example of this third class of solutions is the Tunable-Penalty Factory protocol [1]. > Of course, this example was not available when you noted that solutions are either prophylactic or corrective. FYI, I think the idea of separating control transactions and value transactions (as done in electronic engineering between control signal and actual voltage) has been explored in the past [0]. I still believe this family of solutions can be fitted in the corrective class, as you have an invalid control transaction that can be corrected by another *valid* control transaction, and I still think it's incentive-based as there is a risk of the valid control transaction never confirming ? Or the funds getting frozen due to a miscellaneous broadcast? > On the other hand, protocols that use separate control and value transactions do not have this limitation. > For example, the Tunable-Penalty Factory protocol is a multi-party protocol in which every dishonest party is penalized and there is no economic disequilibrium. Yes, I think this is a good observation. For the partitioned-payment pool this can be corrected by ensuring only the honest party can enforce the partitioned statement and you have to timestamp them in the chain for Bitcoin Script itself to order them, I think. Do the Tunable-Penalty Factory protocol have any "partition-throughput" limit due to a subsidiary reliance on the chain or the liveliness of the N counterparties ? > If I understand this correctly, I think a penalty mechanism that allows a "wronged" user to take some or all of a dishonest user's funds could be exploited by a malicious coalition. > Consider the case where Alice is an honest user who joins a partition with Bob, where Bob and Carol are in a malicious coalition. > Alice believes she has pooled her funds with Bob's and so she is able to work with Bob to implement an off-line update of their balances, with Alice believing > th
Re: [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories
Hi Antoine, Thanks for your insightful post on the interactivity issue. Some thoughts are inline below. > 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. Agreed that signing updates and monitoring the blockchain both create always-online requirements that are not compatible with casual users' desires. I think it's helpful to separate these two cases, as they affect different parties and their solutions differ. In particular, limited availability to sign updates affects one's partners and can be addressed by having fewer partners, not partnering with casual users, evicting unresponsive users, etc. Limited availability to monitor the blockchain affects the security of one's own funds and can be addressed by increasing one's safety parameters (such as the to_self_delay parameter in Lightning). > 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. I would argue that we want a completely trust-free solution, if at all possible, while respecting users' actual availability. We should only consider solutions that require trust if we can't find a trust-free solution that meets all other requirements. > 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. > 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. Actually, there's a third class of solutions that are possible, namely ones that use separate control transactions and value transactions (where the value transactions "spend", and therefore depend on, the control transactions). If an invalid control transaction is put on-chain, it can be blocked by another user by spending its output(s) before the output(s) can affect the value transaction. Thus, control transactions can be viewed as proposals for state updates, and those proposals are blocked if they aren't valid. These solutions differ from prophylactic solutions, as they allow incorrect transactions to be put on-chain and require another user to block them. They also differ from your definition of a corrective security model, as they never allow the state update to be applied to the value in the channel or pool, so there's nothing to be corrected. An example of this third class of solutions is the Tunable-Penalty Factory protocol [1]. Of course, this example was not available when you noted that solutions are either prophylactic or corrective. > 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. > 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. On the other hand, protocols that use separate control and value transactions do not have this limitation. For example, the Tunable-Penalty Factory protocol is a multi-party protocol in which every dishonest party is penalized and there is no economic disequilibrium. > I think that leveraging covenants a revocation mechanism could be attached > on any equivocating branch of transactions, allowin
Re: [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories
@Antoine > it's also hard to predict in advance the liquidity needs of the sub-pools. Definitely. Better than not being able to use the pool at all when someone's offline tho. > this fan-out transaction could interfere with the confirmation of the simple withdraw transactions > So there is an open question about the "honest" usage of the sub-pool states themselves. I don't follow this one. How would it interfere? How would it call into question the "honesty" of the sub-pools? Why would honesty matter? I would assume they can all be structured trustlessly. > one could envision an accumulator committing directly to balances too Are you suggesting that there would be some kind of opcode that operates on this accumulator to shift around balances of some participants without disturbing others? Sounds reasonable. > I think the challenge is to find a compact accumulator with those properties. The Merkle Sum Trees like are used in Taro sound like they could probably be useful for that. > 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. There is of course that limitation. But a third party empowered only to keep the pool functioning is much better than one given the ability to spend on your behalf without your confirmation. This would be a big improvement despite there still being minor privacy downsides. > 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 mean if your balance in the pool is 1000 sats and the service facilitates receiving 100 sats, that service could then steal those 100 sats? And you're asking how you could prevent that? Well first of all, if you're in a channel, not only does your service need to want to steal your funds, but your channel partner(s) must also sign for that as well - so they both must be malicious for these funds to be stolen. I can't see a way to prevent that, but at least this situation prevents them from stealing your whole 1100 sats, and can only steal 100 sats. > see https://gitlab.com/lightning-signer/docs for wip in that direction. Interesting. I'm glad someone's been working on this kind of thing > 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 ? Actually, I was envisioning that the always-online services holding a receive-only key would *all* be online. So all participants of the pool would have a representative, either one with a spending key or with just a receiving-key (which could also be used to simply sign pool state changes that don't negatively affect the balance of the user they represent). So there still would be agreement among all participants on pool state changes. I kind of think if both techniques (sub-pools and limited-trust services) are used, it might be able to substantially increase the ability for a pool to operate effectively (ie substantially decrease the average downtime). @ZmnSCPxj > Is this not just basically channel factories? It is. > To reduce the disruption if any one pool participant is down, have each sub-pool have only 2 participants each. Yes. But the benefit of the pool over just having individual 2 person channels is that you can change around the structure of the channels within the pool without doing on-chain transactions. As Antoine mentioned, it may often not be predictable which 2-person channels would be beneficial in the future. So you want the pool to be as responsive as possible to the changing needs of the pool. On Tue, May 10, 2022 at 11:45 AM ZmnSCPxj wrote: > Good morning Billy, > > > > 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. > > Is this not just basically channel factories? > > To reduce the disruption if any one pool participant is down, have each > sub-pool have only 2 participants each. > More participants means that the probability that one of them is offline > is higher, so you use the minimum number of participants in the sub-pool
Re: [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories
Good morning Billy, > 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. Is this not just basically channel factories? To reduce the disruption if any one pool participant is down, have each sub-pool have only 2 participants each. More participants means that the probability that one of them is offline is higher, so you use the minimum number of participants in the sub-pool: 2. This makes any arbitrary sub-pool more likely to be usable. But a 2-participant pool is a channel. So a large multiparticipant pool with sub-pools is just a channel factory for a bunch of channels. I like this idea because it has good tradeoffs, so channel factories ho. Regards, ZmnSCPxj ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories
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 a écrit : > Hi Antoine, > > Very interesting exploration. I think you're right that there are issues > with the kind of partitioning you're talking abou
Re: [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories
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
[bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories
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-att
