public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
* [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories
@ 2022-04-28 13:18 Antoine Riard
  2022-05-01 22:53 ` Billy Tetrud
  2023-03-17 20:54 ` jlspc
  0 siblings, 2 replies; 7+ messages in thread
From: Antoine Riard @ 2022-04-28 13:18 UTC (permalink / raw)
  To: Bitcoin Protocol Discussion

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

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/

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

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories
  2022-04-28 13:18 [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories Antoine Riard
@ 2022-05-01 22:53 ` Billy Tetrud
  2022-05-10  0:38   ` Antoine Riard
  2022-05-10 16:45   ` ZmnSCPxj
  2023-03-17 20:54 ` jlspc
  1 sibling, 2 replies; 7+ messages in thread
From: Billy Tetrud @ 2022-05-01 22:53 UTC (permalink / raw)
  To: Antoine Riard, Bitcoin Protocol Discussion

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

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: 25364 bytes --]

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories
  2022-05-01 22:53 ` Billy Tetrud
@ 2022-05-10  0:38   ` Antoine Riard
  2022-05-10 16:45   ` ZmnSCPxj
  1 sibling, 0 replies; 7+ messages in thread
From: Antoine Riard @ 2022-05-10  0:38 UTC (permalink / raw)
  To: Billy Tetrud; +Cc: Bitcoin Protocol Discussion

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

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories
  2022-05-01 22:53 ` Billy Tetrud
  2022-05-10  0:38   ` Antoine Riard
@ 2022-05-10 16:45   ` ZmnSCPxj
  2022-05-12 17:36     ` Billy Tetrud
  1 sibling, 1 reply; 7+ messages in thread
From: ZmnSCPxj @ 2022-05-10 16:45 UTC (permalink / raw)
  To: Billy Tetrud, Bitcoin Protocol Discussion

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


^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories
  2022-05-10 16:45   ` ZmnSCPxj
@ 2022-05-12 17:36     ` Billy Tetrud
  0 siblings, 0 replies; 7+ messages in thread
From: Billy Tetrud @ 2022-05-12 17:36 UTC (permalink / raw)
  To: ZmnSCPxj; +Cc: Bitcoin Protocol Discussion

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

@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 <ZmnSCPxj@protonmail.com> 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: 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
>

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

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories
  2022-04-28 13:18 [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories Antoine Riard
  2022-05-01 22:53 ` Billy Tetrud
@ 2023-03-17 20:54 ` jlspc
  2023-04-18  3:38   ` Antoine Riard
  1 sibling, 1 reply; 7+ messages in thread
From: jlspc @ 2023-03-17 20:54 UTC (permalink / raw)
  To: Antoine Riard, Bitcoin Protocol Discussion

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

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

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 that she has gained ownership over some of Bob's funds.
However, when the partitioning Update transaction that joins Alice's and Bob's funds is put on-chain, Carol pretends to have been "wronged" by Bob and uses the penalty mechanism to seize Bob's funds.
In this case, Alice won't be able to get the funds that she thought she had obtained from Bob.

Does that make sense?

Regards,
John

[1] Law, "Efficient Factories For Lightning Channels", available at https://github.com/JohnLaw2/ln-efficient-factories.

Sent with [Proton Mail](https://proton.me/) secure email.

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

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories
  2023-03-17 20:54 ` jlspc
@ 2023-04-18  3:38   ` Antoine Riard
  0 siblings, 0 replies; 7+ messages in thread
From: Antoine Riard @ 2023-04-18  3:38 UTC (permalink / raw)
  To: jlspc; +Cc: Bitcoin Protocol Discussion

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

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
> that she has gained ownership over some of Bob's funds.
> However, when the partitioning Update transaction that joins Alice's and
Bob's funds is put on-chain, Carol pretends to have been "wronged" by Bob
and uses > the penalty mechanism to seize Bob's funds.
> In this case, Alice won't be able to get the funds that she thought she
had obtained from Bob.

Yes you need to order the "partition-statements" otherwise you're falling
on this issue and the ordering happening in a proof-of-non-publication
space, I think [1].

Best,
Antoine

[0] https://rubin.io/talks/2017/01/26/multi-txn-contracts/
[1] https://petertodd.org/2016/state-machine-consensus-building-blocks

Le ven. 17 mars 2023 à 20:55, jlspc <jlspc@protonmail.com> a écrit :

> 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, 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.
>
> 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 that she has gained ownership over some of Bob's funds.
> However, when the partitioning Update transaction that joins Alice's and Bob's funds is put on-chain, Carol pretends to have been "wronged" by Bob and uses the penalty mechanism to seize Bob's funds.
> In this case, Alice won't be able to get the funds that she thought she had obtained from Bob.
>
> Does that make sense?
>
> Regards,
> John
>
> [1] Law, "Efficient Factories For Lightning Channels", available at https://github.com/JohnLaw2/ln-efficient-factories.
>
>
>
>
> Sent with Proton Mail <https://proton.me/> secure email.
>
>
>

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

^ permalink raw reply	[flat|nested] 7+ messages in thread

end of thread, other threads:[~2023-04-18  3:39 UTC | newest]

Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-04-28 13:18 [bitcoin-dev] Conjectures on solving the high interactivity issue in payment pools and channel factories Antoine Riard
2022-05-01 22:53 ` Billy Tetrud
2022-05-10  0:38   ` Antoine Riard
2022-05-10 16:45   ` ZmnSCPxj
2022-05-12 17:36     ` Billy Tetrud
2023-03-17 20:54 ` jlspc
2023-04-18  3:38   ` Antoine Riard

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox