Re: [bitcoin-dev] CoinPool, exploring generic payment pools for Fun and Privacy

[Antoine Riard <antoine.riard@gmail.com>]

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

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 for OP_CTV tree, increasing radix increases cooperation
requirement and failure, so there should be optimum somewhere.

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

That's right, that's a current shortcoming of this strawman design, I think
you can avoided by adding some timelocks, "if Alice doesn't anwser after X
days, initiate a kick-out", thus avoiding full onchain unrolling.

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

I'm still thinking on this too, especially in LN-context, ideally you do
want the same thing to kick-out a HTLC of your HTLC-tree while preserving
the rest of them. Technically it works, if you assume CSV delay on the
commitment/pool_tx and locktime on the HTLC, which is Eltoo tradeoff.

> With Accumulator pools, you need all parties online to make payments.

I think that our shortcoming here, but technically with protocol rebinding
on any withdrawal output of Split_tx, you can have M-of-N channels between
pool participants. Also we should aim to support any kind of protocol at
the leaves.

> Because Accumulator pools always require N signers, it's possible to build
> a better privacy model where N parties are essentially managing a chaumian
> ecash like server for updates, giving good privacy of who initiated
> payments.

Yes that what I've in mind is something with blind signatures or any
obfuscation of pool tree construction as privacy optimization. Still you
will leak value weight of leaves to an in-pool observer.

> Both protocols require new features in Bitcoin. CTV is relatively simple,
I
> would posit that accumulators + sighashnoinput are relatively not simple.

I agree design, review, deployment costs are an order of magnitude higher.
That said they are more powerful primitives which would cover use cases
beyond pools. A concern with OP_CTV is if we want semantic extensions we
may realize they don't rank that well compared to more generic "base"
primitives.

> In both designs, the payment pool can be created non-interactively. This
is
> *super* important as it means third parties (e.g., an exchange) can
> withdraw users funds *into* a payment pool.

See my point above, I think we need a better definition of
non-interactivity.

Thanks for the high-quality review of CoinPool !

Antoine

Le jeu. 11 juin 2020 à 13:21, Jeremy <jlrubin@mit.edu> a écrit :

> 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 there is a planned exit.
>
> With Accumulator pools, you need all parties online to make payments.
>
>
> Cooperation Case:
> CTV Pools and Accumulator pools, in a cooperative case, both just act like
> a N of N multisig.
>
> Privacy:
> Because Accumulator pools always require N signers, it's possible to build
> a better privacy model where N parties are essentially managing a chaumian
> ecash like server for updates, giving good privacy of who initiated
> payments. You *could* do this with CTV pools as well, but I expect users to
> prefer making updates at the 2 party channel layer for low latency, and to
> get privacy benefits out of the routability of the channels and ability to
> connect to the broader lightning network.
>
>
> Technical Complexity:
> Both protocols require new features in Bitcoin. CTV is relatively simple,
> I would posit that accumulators + sighashnoinput are relatively not simple.
>
> The actual protocol design for CTV pools is pretty simple and can be
> compatible with LN, I already have a rudimentary implementation of the
> required transactions (but not servers).
>
>
> Interactivity:
>
> In both designs, the payment pool can be created non-interactively. This
> is *super* important as it means third parties (e.g., an exchange) can
> withdraw users funds *into* a payment pool.
>
>
> Thanks for reading!
>
> Jeremy
>
>
>
> --
> @JeremyRubin <https://twitter.com/JeremyRubin>
> <https://twitter.com/JeremyRubin>
>
>

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