Re: [bitcoin-dev] CoinPool, exploring generic payment pools for Fun and Privacy
Good morning Antoine, Gleb, and list, In some ways, CoinPool is really part of a swarm of ideas: * CoinPool * Multiparticipant (N > 2) channels * Channel factories * Nodelets What CoinPool and multiparticipant channels buy us is better flexibility with forwarding. For example, if we compare a multiparty channel to a channel factory, suppose there exists three entities A, B, and C in the multiparty construction. In a channel factory, each entity has to decide how much of its liquidity to tie up in a channel with a specific other peer in the multiparty construction. This limits the practical payment forwarding when integrated into the Lightning Network. In a CoinPool, any of the entities can forward to any of the other entities, without tying their liquidity to a channel specifically with those entities. However, in a CoinPool, once any of the entities goes offline, the entire CoinPool can no longer update. This is in contrast with channel factories, where, if entity C goes offline, the channel between A and B remains useable for forwarding. In other words, channel factories degrade gracefully. Further, we already have a decent solution for liquidity redistribution: JIT Routing by Rene Pickhardt. Thus the liquidity issue with channel factories are somewhat mitigated (and if all participants are online, they also have the option of redistributing channel funds *inside* the factory as well, not just JIT routing), while gaining graceful degradation of the factory. Another is that pathfinding algorithms work best if graph edges are edges and not in fact some kind of twisted multi-edge that connects more than two nodes together. On the other hand, the participants of a CoinPool could create a "virtual node" that is a MuSig of their individual keys, and report that as the "real" node on LN gossip (each of them pretending to have a large channel with that virtual node), so that the rest of the network only sees edges that link two nodes (and existing pathfinding algos still work seamlessly, never realizing that this node is actually a virtual node that represents a CoinPool). This is basically them creating a sort of Nodelet node, which other nodes cannot make channels to, and which uses channels with the Nodelet node as proxies for the CoinPool as a whole. Regards, ZmnSCPxj ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] CoinPool, exploring generic payment pools for Fun and Privacy
Hi ZmnSCPxj, > I have not studied the proposal in close detail yet, but anyway, my main takeaway roughly is: > > * The core of CoinPool is some kind of multiparticipant (N > 2) offchain update mechanism (Decker-Wattenhofer or Decker-Russell-Osuntokun). > * The output at each state of the update mechanism is some kind of splitting construction (which I have not studied in detail). > * At each update of the state, all participants must sign off on the new state. Overall, that's a really accurate description. I would add you can embed a funding outpoint of any offchain protocol on the splitting construction, modulo some timelocks shenanigans. > In order to hide transfers from the elected WabiSabi server, participants can maintain two coins in every state, and move coins randomly across the two coins they own at each state update, in order to hide "real" transfers from the elected server. Yes I'm quite sure you can reuse WabiSabi as a communication channel between participants, assuming you support tapscript and merkle branch transports, and server build a tree. Generally, we tried to keep design as flexible as we can to reuse privacy tools. > Indeed, from what I can understand, in order to properly set up the splitting transactions in the first place, at each state every participant needs to know how much each other participant actually owns in the CoinPool at that point in time. Yes, that's part of future research, defining better *in-pool* observer. Sadly, right now, even if you use mask construction inside, it's quite easy to trace leaves by value weight. Of course, you can enforce equal-value leaves, as for a regular onchain CoinJoin. I think it comes with a higher onchain cost in case of pool breakage. > That way, output addresses can be to fresh pseudonyms of the participant, removing all linkages of participant to amount they own, and each participant can maintain multiple outputs per state for their own purposes and to mildly obscure exactly how much they own in total. That's right that an in-pool observer may learn a link between an exit and an onchain withdraw. There is a future optimization, if you can swap your withdraw with an already onchain output, therefore breaking heuristics. > We can do this by using `SIGHASH_ANYPREVOUT` to force whoever performs a unilateral close of the CoinPool to pay the onchain fees involved, so that it would have to be a good reason indeed to perform a unilateral close. Absolutely, for the fee structure, as the withdraw output is at the discretion of user, I was thinking some CPFP. There is maybe a better solution, haven't spend that much on the exact adequate, incentives-align mechanism beyond a "withdraw-must-pay-its-fees". Thanks for the high-quality review, as usual ;) Antoine Le ven. 12 juin 2020 à 04:39, ZmnSCPxj a écrit : > Good morning Antoine and Gleb, > > I have not studied the proposal in close detail yet, but anyway, my main > takeaway roughly is: > > * The core of CoinPool is some kind of multiparticipant (N > 2) offchain > update mechanism (Decker-Wattenhofer or Decker-Russell-Osuntokun). > * The output at each state of the update mechanism is some kind of > splitting construction (which I have not studied in detail). > * At each update of the state, all participants must sign off on the new > state. > > It seems to me that it would be possible to use a [WabiSabi protocol]( > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-June/017969.html) > during negotiation of a new state. > > Now, WabiSabi is a client-server protocol. > As all participants in the CoinPool are needed in order to ratify each new > state anyway, they can simply elect one of their number by drawing lots, to > act as server for a particular state update. > > Then the participants can operate as WabiSabi clients. > Each participant registers the outputs they currently own in the current > state, getting credentials that sum up to the correct value. > Then, during the WabiSabi run, they can exchange credentials among the > participants in order to perform value transfers inside the WabiSabi > construction. > Then, at output registration, they register new outputs to put in the next > state of the CoinPool. > > In order to hide transfers from the elected WabiSabi server, participants > can maintain two coins in every state, and move coins randomly across the > two coins they own at each state update, in order to hide "real" transfers > from the elected server. > > Then, after output registration, the participants ratify the new state by > signing off on the new state and revoking the previous state, using the > update mechanism. > > Of course, we should note that one desired feature for CoinPool in the > original proposal is that a participant can exit, and the CoinPool would > still remain valid, but only for the remaining participants. > > This is arguably a mild privacy leak: every other participant now knows > how much that particular participant
Re: [bitcoin-dev] CoinPool, exploring generic payment pools for Fun and Privacy
Good morning Antoine, By dropping the requirement that a participant can seamlessly leave the CoinPool, it allows participants to split up their coins among new aliases and to use a different identity for later claiming coins. With WabiSabi, none of the other participants can get a mapping between current-state aliases and the actual participants. Now, in order to authorize moving coins from an output on the current state to a new output on the next state, obviously the pool needs to get a signature from its current owner. Ideally, we would not want to have to implement SCRIPT inside the CoinPool software. And with Taproot, a pubkey can hide one or more SCRIPTs. If we use pubkeys as the identities of owners of coins, then it allows an alias to encode a SCRIPT. With the combination of both features, we can instantiate HTLCs (or, with `SIGHASH_ANYPREVOUT`, PTLCs) inside a CoinPool "alias" pubkey identity, allowing for interoperation with LN. Now suppose I have 1.0 BTC in a CoinPool. I want to make an HTLC with you (hashlocked to you, timelocked to me), for 0.5 BTC. I encode the HTLC SCRIPT, and put it into a Taproot whose internal pubkey is a MuSig of fresh identities of mine and yours. Then, inside the CoinPool, I split my 1.0BTC to a 0.5BTC coin to a fresh identity of mine, and 0.5BTC to our HTLC Taproot. If you can acquire the hash, you give it to me, and I am supposed to hand you a partial signature share to the HTLC Taproot that you can later complete and present to the CoinPool in the next update round in order to get the HTLC value. If I do not hand you the signature share even after you hand the hash, you just drop the entire CoinPool onchain, instantiating the HTLC Taproot output onchain, and using the SCRIPT branch to claim using the hash you know. If the timelock expires, I ask you to hand over your partial signature to the HTLC Taproot that I can later complete and present to the CoinPool in the next update round to recover the HTLC value. If you do not hand over the signature share, I drop the CoinPool onchain, which instantiates the HTLC Taproot output onchain, and use the SCRIPT branch to claim using the timelock branch. You can also ask to abort the HTLC "early", before the timelock expires, by handing over your partial signature to the HTLC Taproot, which I can later complete and present to the CoinPool in the next update round. This is equivalent to `update_fail_htlc` in the current LN BOLT spec. This allows operation of any SCRIPT, incidentally, without requiring that CoinPool software include a SCRIPT interpreter, only signature validation. Any time an output absolutely needs a SCRIPT, we just drop the CoinPool onchain and let onchain handle the SCRIPT interpretation. Regards, ZmnSCPxj ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] CoinPool, exploring generic payment pools for Fun and Privacy
Good morning Antoine, > Yes, that's part of future research, defining better *in-pool* observer. > Sadly, right now, even if you use mask construction inside, it's quite easy > to trace leaves by value weight. Of course, you can enforce equal-value > leaves, as for a regular onchain CoinJoin. I think it comes with a higher > onchain cost in case of pool breakage. Perhaps not necessarily. An advantage of WabiSabi is I can pretend to be two or more participants. For example, I can pretend to be "Alice" and "Bob", and pretend that "Alice" owes a life debt to "Bob". At initial state setup, I put a 1.0 BTC coin as "Alice" and a 0.5 BTC coin as "Bob". Now, at each state update I need to sign as "Alice" and "Bob". However, after the first initial state, I can use a new persona "Bobby" to *own* my coins, even though I still have to sign as "Alice" and "Bob" in every state update. What the other pool participants see is that the 1.0 BTC "Alice" coin and the 0.5 BTC "Bob" coin are merged into the 1.5 BTC "Bobby" coin. What they cannot be sure of is: * "Alice" paid to "Bob", who is now pretending to be "Bobby". * "Bob" paid to "Alice", who is now pretending to be "Bobby". * "Alice" and "Bob" are the same person, and is also pretending to be "Bobby". All the other participants know is that whoever owns the coin *now* is still part of the pool, but cannot be sure which participant *really* owns which coin, and whether participants are sockpuppets (which is why it should use n-of-n at each state update, incidentally). In effect, it "imports" the possibility of PayJoin inside the CoinPool construction. Regards, ZmnSCPxj ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] CoinPool, exploring generic payment pools for Fun and Privacy
Hi Jeremy, For the records, I didn't know between Greg and you was at the origin of payment pools. Thanks for your pioneer work here, obviously this draws inspiration from OP_CTV use cases and Channel Factories works, even if we picked up different assumptions and tried to address another set of issues. With regards to scalability, I hit it on my own while inquiring covenanted-Bitcoin contracts for international trade. I mentioned the any-order issue on such multi-party complex contracts in a talk last summer (https://github.com/ariard/talk-slides/blob/master/advanced-contracts.pdf). > All of these channels can be constructed and set up non-interatively using > CTV, and updated interactively. By default payments can happen with minimal > coordination of parties by standard lightning channel updates at the leaf > nodes, and channels can be rebalanced at higher layers with more > participation. Side review note on OP_CTV: I think it would be great to define non-interactivity better, namely at least between 3 phases: establishment, operation, closing. Even OP_CTV protocols assume interactivity at establishment, at least 1) to learn payees pubkeys endpoint (and internal leaves pubkeys if you want update at operation) 2) validate transaction tree correctness between participants. At operation, it depends if participants want to dynamically rebalance value across channels or not. If you desire dynamically rebalancing, assume internal leaves scriptpubkeys are (multisig-all OR OP_CTV'ed merkle_tree). Using OP_CTV is a saving in message rounds for every constant expression across tree updates. At closing, depends again if participants have committed update keys or not. If dynamic update, you can prune the whole tree and just commit final balances onchain, either with a O(N) fan-out transaction (N outputs) or a O(log(N)) congestion tree (N transactions). So I would say the originality of a hashchain covenant like OP_CTV is to provide onchain *immutability* (unforgeability?) of the offchain transaction tree and thus provides instant finality to payees. You can get the same semantic with off-chain covenant, pre-signed set of transactions, assuming more communications rounds and performance hit. That said, IMO, immutability comes with a security trade-off, namely if any payout key committed in your OP_CTV tree gets compromised your funds are at stake. And you can't update the tree anymore at the root to rotate keys. I think this should be weighted by anyone designing covenant protocols, especially vaults. > I don't think the following requirement: "A > CoinPool must satisfy the following *non-interactive any-order withdrawal* > property: at any point in time and any possible sequence of previous > CoinPool events, a participant should be able to move their funds from the > CoinPool to any address the participant wants without cooperation with > other CoinPool members." is desirable in O(1) space. With current design (Pool_tx+Split_tx) it's O(2) space. Pool_tx is similar to a commitment tx and thus enables off-chain novation of pool distribution. > Let's be favorable to Accumulators and assume O(1), but keep in mind constant may > be somewhat large/operations might be expensive in validation for updates. Using a Merkle Tree as an accumulator should be constant-size in space, but likely it has to be O(log(N) in computation (N set elements). This overhead in computation should be accounted for in accumulator sigops to avoid network validation resources free-riding, but I think it's a better trade-off minimizing chain footprint. > So in this context, CTV Pool has a clear benefit. The last recipient can > always clear in Log(N) time whereas in the accumulator pool, the last > recipient has to wait much much longer. There's no asymptotic difference in > Tx Size, but I suspect that CTV is at least as good or cheaper since it's > just one tx hash and doesn't depend on implementation. Yes I agree CTV pool performs better in the worst-case scenario. In my opinon what we should really look on is the probability of withdrawal scenarios. I see 2 failure cases: * a pool participant being offline, thus halting the pool * a pool participant with external protocol requirement to fulfill, like a HTLC to timeout onchain With regards to 1) we assume that watchtower infra are likely to become ubiquitous in the future (if you want a secure LN experience), so user uptime should be near to 100%. Of course, it's a new architecture which comes with trade-offs, but interesting to explore. With regards to 2) as of today channel-failure-rate (like unilateral close) it's still quite important (30% IIRC) so it plays in favor of OP_CTV pool but in the future I expect single-digit therefore making CoinPool far more competitive. Do we envision protocol more time-sensitive than LN in the future (atomic swaps...) ? Hard to gauge. Do you see other ways to refine model, like integrating out-of-pool liquidity needs rate ? Note, I think
Re: [bitcoin-dev] CoinPool, exploring generic payment pools for Fun and Privacy
Good morning Antoine and Gleb, I have not studied the proposal in close detail yet, but anyway, my main takeaway roughly is: * The core of CoinPool is some kind of multiparticipant (N > 2) offchain update mechanism (Decker-Wattenhofer or Decker-Russell-Osuntokun). * The output at each state of the update mechanism is some kind of splitting construction (which I have not studied in detail). * At each update of the state, all participants must sign off on the new state. It seems to me that it would be possible to use a [WabiSabi protocol](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-June/017969.html) during negotiation of a new state. Now, WabiSabi is a client-server protocol. As all participants in the CoinPool are needed in order to ratify each new state anyway, they can simply elect one of their number by drawing lots, to act as server for a particular state update. Then the participants can operate as WabiSabi clients. Each participant registers the outputs they currently own in the current state, getting credentials that sum up to the correct value. Then, during the WabiSabi run, they can exchange credentials among the participants in order to perform value transfers inside the WabiSabi construction. Then, at output registration, they register new outputs to put in the next state of the CoinPool. In order to hide transfers from the elected WabiSabi server, participants can maintain two coins in every state, and move coins randomly across the two coins they own at each state update, in order to hide "real" transfers from the elected server. Then, after output registration, the participants ratify the new state by signing off on the new state and revoking the previous state, using the update mechanism. Of course, we should note that one desired feature for CoinPool in the original proposal is that a participant can exit, and the CoinPool would still remain valid, but only for the remaining participants. This is arguably a mild privacy leak: every other participant now knows how much that particular participant took out from the CoinPool. Indeed, from what I can understand, in order to properly set up the splitting transactions in the first place, at each state every participant needs to know how much each other participant actually owns in the CoinPool at that point in time. To hide how much each participant owns in the CoinPool from other participants, we would have to make unilateral closes expose all the current outputs, without trying to identify *which* participant exited the CoinPool, and thus preventing anyone else from figuring out exactly how much each *other* participant actually owns in the CoinPool on exit. That way, output addresses can be to fresh pseudonyms of the participant, removing all linkages of participant to amount they own, and each participant can maintain multiple outputs per state for their own purposes and to mildly obscure exactly how much they own in total. If we drop that feature (of being able to exit a participant without closing the *entire* CoinPool), of course, we need to mildly disincentivize a participant closing unilaterally for trivial reasons. We can do this by using `SIGHASH_ANYPREVOUT` to force whoever performs a unilateral close of the CoinPool to pay the onchain fees involved, so that it would have to be a good reason indeed to perform a unilateral close. Regards, ZmnSCPxj ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] CoinPool, exploring generic payment pools for Fun and Privacy
Stellar work Antoine and Gleb! Really excited to see designs come out on payment pools. I've also been designing some payment pools (I have some not ready code I can share with you guys off list), and I wanted to share what I learned here in case it's useful. In my design of payment pools, I don't think the following requirement: "A CoinPool must satisfy the following *non-interactive any-order withdrawal* property: at any point in time and any possible sequence of previous CoinPool events, a participant should be able to move their funds from the CoinPool to any address the participant wants without cooperation with other CoinPool members." is desirable in O(1) space. I think it's much better to set the requirement to O(log(n)), and this isn't just because of wanting to use CTV, although it does help. Let me describe a quick CTV based payment pool: Build a payment pool for N users as N/2 channels between participants created in a payment tree with a radix of R, where every node has a multisig path for being used as a multi-party channel and the CTV branch has a preset timeout. E.g., with radix 2: Channel(a,b,c,d,e,f,g,h) / \ Channel(a,b,c,d) Channel(e,f,g,h) / \/ \ Channel(a,b)Channel(c,d) Channel(e,f) Channel(g,h) All of these channels can be constructed and set up non-interatively using CTV, and updated interactively. By default payments can happen with minimal coordination of parties by standard lightning channel updates at the leaf nodes, and channels can be rebalanced at higher layers with more participation. Now let's compare the first-person exit non cooperative scenario across pools: CTV-Pool: Wait time: Log(N). At each branch, you must wait for a timeout, and you have to go through log N to make sure there are no updated states. You can trade off wait time/fees by picking different radixes. TXN Size: Log(N) 1000 people with radix 4 --> 5 wait periods. 5*4 txn size. Radix 20 --> 2 wait periods. 2*20 txn size. Accumulator-Pool: Wait Time: O(1) TXN Size: Depending on accumulator: O(1), O(log N), O(N) bits. Let's be favorable to Accumulators and assumer O(1), but keep in mind constant may be somewhat large/operations might be expensive in validation for updates. This *seems* like a clear win for Accumulators. But not so fast. Let's look at the case where *everyone* exits non cooperatively from a payment pool. What is the total work and time? CTV Pool: Wait time: Log(N) Txn Size: O(N) (no worse than 2x factor overhead with radix 2, higher radixes dramatically less overhead) Accumulator Pool: Wait time: O(N) Txn Size: O(N) (bear in mind *maybe* O(N^2) or O(N log N) if we use an sub-optimal accumulator, or validation work may be expensive depending on the new primitive) So in this context, CTV Pool has a clear benefit. The last recipient can always clear in Log(N) time whereas in the accumulator pool, the last recipient has to wait much much longer. There's no asymptotic difference in Tx Size, but I suspect that CTV is at least as good or cheaper since it's just one tx hash and doesn't depend on implementation. Another property that is nice about the CTV pool style is the bisecting property. Every time you have to do an uncooperative withdrawal, you split the group into R groups. If your group is not cooperating because one person is permanently offline, then Accumulator pools *guarantee* you need to go through a full on-chain redemption. Not so with a CTV-style pool, as if you have a single failure among [1,2,3,4,5,6,7,8,9,10] channels (let's say channel 8 fails), then with a radix 4 setup your next steps are: [1,2,3,4,5,6,7,8,9,10] [1,2,3,4,5,6,7,X,9,10] [1,2,3,4] [5,6,7,X] [9,10] [1,2,3,4] 5 6 7 X [9,10] So you only need to do Log(N) chain work to exit the bad actor, but then it amortizes! A future failure (let's say of 5) only causes 5 to have to close their channel, and does not affect anyone else. With an accumulator based pool, if you re-pool after one failure, a second failure causes another O(N) work. So then total work in that case is O(N^2). You can improve the design by making the evict in any order option such that you can *kick out* a member in any order, that helps solve some of this nastiness (rather than them opting to leave). But I'm unclear how to make this safe w.r.t. updated states. You could also allow, perhaps, any number of operators to simultaneously leave in a tx. Also not sure how to do that. Availability: With CTV Pools, you can make a payment if just your immediate conterparty is online in your channel. Opportunistically, if people above you are online, you can make channel updates higher up in the tree which have better timeout properties. You can also create new channels, binding yourself to different parties if
