Set CTV to show payment pool support

Idk how I feel about this. For me the property of having a single-tx unilateral exit option instead of shattering the pool into log(n) subpools on unilateral exit is pretty central to the benefits.

I could see the argument that a pool is only as useful as long as the entire party can cooperate, but imagine one party going offline, in a CTV pool, the remaining n-1 parties would have to shatter the pool into pieces while in a TLUV-style pool they could just evict the one party and continue among themselves in a single tx.

just in terms of asymptotics (feel free to count the bytes!), a single tx witha log(n) sized script is equivalent to a log(n) shattering and log(n) rezipping with constant sized scripts.

usually the unilateral exit scripts are at least O(log n) e.g. taproot leaves.

Further, once "online" you can backfill presigned unilateral exits.

below the break, an old mailing list post of mine responding to TLUV:

I like this proposal, I think it has interesting use cases! I'm quick to charitably Matt's comment, "I’ve been saying we need more covenants research and proposals before we move forward with one", as before we move forward with any. I don't think that these efforts are rival -- different opcodes for different nodes as they say.

I've previously done some analysis comparing Coin / Payment Pools with CTV to TapLeafUpdate which make CTV out favorably in terms of chain load and privacy.

On the "anyone can withdraw themselves in O(1) transactions" front, is that if you contrast a CTV-style tree, the withdraws are O(log(n)) but E[O(1)] for all participants, e.g. summing over the entire tree as it splits to evict a bad actor ends up being O(N) total work over N participants, so you do have to look at the exact transactions that come out w.r.t. script size to determine which Payment Pool has overall less chain work to trustlessly withdraw. This is compounded by the fact that a Taproot for N participants uses a O(log N) witness.

Let's do out that basic math. First, let's assume we have 30 participants. The basic script for each node would be:

TLUV: Taproot(Tweaked Key, { DUP "" 1 TLUV CHECKSIGVERIFY IN_OUT_AMOUNT SUB GREATERTHANOREQUAL, ...})

Under this, the first withdraw for TLUV would require in witnesses stack: Assume average amount is 0.005BTC, so we have 4.2 B users = 18.9 bits =3 bytes

1 signature (1+64 bytes) + (1 Script = (+ 1 1 32 1 1 1 1 1 1 1 3 1 1) = 46 bytes) + (1 taproot path = 2 + 33 + log2(N)32) = 146+log2(N)32.

now, because we delete the key, we need to sum this from N=0 to N=30:

sum([65+46+35+math.log(N,2)*32 for N in range(1, 31)]) 7826.690154943152 bytes of witness data

Each transaction should have 1 input (40 bytes), 2 outputs (2* (34+8) = 84), 4 bytes locktime, 4 bytes version, 2 byte witness flag, 1 byte in counter 1 byte out counter = 136 bytes (we already count witnesses above)

136 * 30 + 7827 = 11907 bytes to withdraw all trustlessly

Now for CTV: -CTV: Taproot(MuSigKey(subparties), <H splits pool with radix 4> CTV)

sidebar: why radix 4? A while ago, I did the math out and a radix of 4 or 5 was optimal for bare script... assuming this result holds with taproot.

balance holders: 0..30 you have a base set of transactions paying out: 0..4 4..8 8..12 12..16 16..20 20..24 24..27 27..30 interior nodes covering: 0..16 16..30 root node covering: 0..30

The witness for each of these looks like:

(Taproot Script = 1+1+32+1) + (Taproot Control = 33) = 68 bytes

A transaction with two outputs should have 1 input (40 bytes), 2 outputs (2 (34+8) = 84), 4 bytes locktime, 4 bytes version, 2 byte witness flag, 1 byte in counter 1 byte out counter = 136 bytes + 68 bytes witness = 204 A transaction with three outputs should have 1 input (40 bytes), 3 outputs (3 (34+8) = 126), 4 bytes locktime, 4 bytes version, 2 byte witness flag, 1 byte in counter 1 byte out counter = 178 bytes + 68 bytes witness = 246 A transaction with 4 outputs should have 1 input (40 bytes), 4 outputs (4* (34+8) = 126), 4 bytes locktime, 4 bytes version, 2 byte witness flag, 1 byte in counter 1 byte out counter = 220 bytes + 68 bytes witness = 288

204 + 2886 + 2462 = 2424 bytes

Therefore the CTV style pool is, in this example, about 5x more efficient in block space utilization as compared to TLUV at trustlessly withdrawing all participants. This extra space leaves lots of headroom to e.g. including things like OP_TRUE anchor outputs (12*10) = 120 bytes total for CPFP; an optional script path with 2 inputs for a gas-paying input (cost is around 32 bytes for taproot?). The design also scales beyond 30 participants, where the advantage grows further (iirc, sum i = 0 to n log i is relatively close to n log n).

In the single withdrawal case, the cost to eject a single participant with CTV is 204+288 = 492 bytes, compared to 65+46+35+math.log(30,2)*32+136 = 439 bytes. The cost to eject a second participant in CTV is much smaller as it amortizes -- worst case is 288, best case is 0 (already expanded), whereas in TLUV there is limited amortization so it would be about 438 bytes.

The protocols are identical in the cooperative case.

In terms of privacy, the CTV version is a little bit worse. At every splitting, radix of the root nodes total value gets broadcast. So to eject a participant, you end up leaking a bit more information. However, it might be a reasonable assumption that if one of your counterparties is uncooperative, they might dox you anyways. CTV trees are also superior during updates for privacy in the cooperative case. With the TLUV pool, you must know all tapleafs and the corresponding balances. Whereas in CTV trees, you only need to know the balances of the nodes above you. E.g., we can update the balances

from: [[1 Alice, 2 Bob], [3 Carol, 4 Dave]] to: [[2.5 Alice, 0.5 Bob], [3 Carol, 4 Dave]]

without informing Carol or Dave about the updates in our subtree, just that our slice of participants signed off on it. So even in the 1 party uncooperative case, 3/4 the pool has update privacy against them, and the subtrees that share a branch with the uncooperative also have this privacy recursively to an extent.

CTV's TXID stability also lets you embed payment channels a bit easier, but perhaps TLUV would be in an ANYPREVOUT universe w.r.t. channel protocols so that might matter less across the designs. Nevertheless, I think it's exciting to think about these payment pools where every node is an updatable channel.

@stevenroose Any update on this pull request?

I don't know, it might be a semantic disagreement on what a "payment pool" is, but for me, if you have to break the output up permanently in 2 suboutputs to non-interactively exit a single user, I don't consider it a real payment pool. The whole point is that you have collaborative updates and non-interactive exits of a single user.

Like if n << N of users disappears, the N-n active users should be able to kick out the n users in O(n) transactions (ideally exactly n) and continue with the N-n users from there.

if you want to find a term that covers "design that I favor" and doesn't cover "design that I disfavor", that's OK with me. But I do not think it works to take the term as it was originally used and exclude the original reference, and I guess it's on me to defend that since I kinda invented it and the term was coined by Greg to describe my work.

Some loose history below on the evolution of payment pools...

I think the first (recorded) use of the specific term payment pool is here is May 21st 2019:

09:28 what do you think of my payment pool example? that wasn't (directly) in Jeremyrubin's presentation. (he was more concerned with the 'exchange or mining pool pays lots of people at once' sort of model.

After Greg watched my presentation, the slides for which are here:

https://docs.google.com/presentation/d/1BuIJj8KkGFM8uOCXuQDgnwTLOHyUM72j6ofrkxwj_qg/edit#slide=id.p

as well as the BIP which was authored before the presentation https://github.com/JeremyRubin/bips/blob/op-checkoutputshashverify/bip-coshv.mediawiki#user-content-Implementations

Notably, the BIP details in the congestion control case the structure of Taproot key at each level to elide further expansion, nearly identical to today's CTV payment pool contract.

Greg's claim that the N-of-N model wasn't directly in my presentation, just mining pool or exchange, is sort of accurate. I did mention that these taproot key path opt-outtable utxo accumulators could be used for Coin Joins, and it was in the BIP as well. I don't recall what I actually presented, precisely, and in my Bitdevs presentation I remember I opted for as-simple-as-possible presentation since I was worried people would completely tune out and fail to understand how simply COSHV could be used, but I don't remember in what extra detail we got into in the discussion portion, but I remember covering a lot.

In particular the draft BIP says

Critically, because this is a Tapscript, it is intended that participants may collaborate to replace the Tapscript path with a signature. This lifts the requirement of the output being spent alone and the exact match of output hashes, if other dependencies (like channel state) can be updated.

and

If desired, the Tapscript path can be usurped by a signature based spend to improve fungibility.

Which was intended to make clear that the higher up tree nodes should be replaced with the parties minding the state below the tree. E.g., rolling bundles of lightnign channels.

If I recall, the reason why I didn't emphasize N people doing this on a running basis (while keeping the N coallition alive) is I felt that it was "more private" if transitions from payment pool state S1 to state S{n+1} were not assumed to be the default mode, but rather that new pools, channels, etc, might be being formed "under the hood" without the shared knowledge of the parent of the pool.

I do think that Greg did a great job at clarifying and understanding my presentation. It wasn't abundantly clear from the slide or BIP that the N-of-N opting out includes recursing into new payment pools, and presenting it as a rolling-but-mostly static set of participants is a highly likely outcome, and an easier one to reason about than more dynamic membership sets. Giving it a tidy name made it stick to this day. I can't find a reference on me using the term payment pool earlier, and I don't think I used it at the bitdevs ;)

I don't know, it might be a semantic disagreement on what a "payment pool" is, but for me, if you have to break the output up permanently in 2 suboutputs to non-interactively exit a single user, I don't consider it a real payment pool. The whole point is that you have collaborative updates and non-interactive exits of a single user.

Like if n << N of users disappears, the N-n active users should be able to kick out the n users in O(n) transactions (ideally exactly n) and continue with the N-n users from there.

more substantively, with a basic CTV pool, radix 2, it ends up costing O(n log_R N) txns to exit pessimal case, but it might be substantially improved by grouping users together smartly. However the other payment pool designs I've been shown cost O(n) txns to exit but those txns are size O(log_2 N) because of the taptree. The constant factors end up mattering, and CTV uses fewer bytes. Further, CTV can expand using higher radixes such as 4, which mean that the log_R N grows much slower than log2(N). These splits are not "permanent". With a radix of 4 and say 1024 users, you are looking at 5 txns to exit 1 user. Let's say you're exiting 4 users who are offline (n << N). There are a bunch of cases, but if they are clustered in the same 25%, then immediately the remaining 75% can do one constant R sized transaction to "rezip" and get back online and operation. This concept applies essentially recursively, you can do the math. The pessimal per level is when each bucket has one failure, but if each bucket has an equal number of failures, then at the next level, only one bucket has a failure. Further, when you rezip, you don't need to do so eagerly, you can wait till you have an actual update or other peers you want to work with. Further, depending on your assumptions of behavior and if failures are random, after kicking out bad peers you're "lost" your stragglers and your failure rate should decrease. This lends to a natural rule to order the participants in a tree in the order of how long they've been a pool member. This shakes the failures to one side of the tree, giving most of the users great uptime. Another way to think of this is letting each level in the tree be a histogram of reliability with as much precision as you like.

So unless you have a O(N) txns with O(1) witnesses size, that leads to fewer bytes overall, I find the distinction less interesting.

What I do find interesting is that you can use exotic trees with CTV to emulate all kinds of behavior. Lately I've been excited in particular about SPlexit, where at every node you split-and-exit one. It ends up having the nice "one tx to exit one person" behavior, but not having too much precomputation.

Feel free to play with it below (really unoptimized, just doing basic research rn)

import itertools
import math
def chunk_into_n(lst, n):
    size = math.ceil(len(lst) / n)
    x = list(
    map(lambda x: lst[x * size:x * size + size],
    list(range(n)))
      )
    if len(x[-1]) < len(x[-2])/2:
        y = x.pop()
        x[-1] += y # TODO, maybe equally distribute?
    return x

def exit_and_split(parties, txns, radix=2, min_tx_outs = 4):
    L = len(parties)
    if tuple(parties) in txns: return
    if L <= radix+1 or L <= min_tx_outs:
        # TODO: Who to ascribe this to?
        txns.add((parties[0], (tuple(parties[1:]),)))
    else:
        for i in range(len(parties)):
            p = parties.copy()
            exited = p.pop(i)
            L = len(p)
            groups = list(chunk_into_n(p, radix))
            txns.add((exited, tuple(map(tuple, groups))))
            for a in groups:
                exit_and_split(a, txns, radix)

txns = set([])
radix = 4
exit_and_split(list(range(200)), txns, radix=radix)
import collections
txn_by_exiter = collections.defaultdict(lambda: [])
for txn in txns:
    txn_by_exiter[txn[0]].append(txn)
print(len(txns))
max_size = 0
for tx in (txn_by_exiter[(3)]):

    mprint = lambda *k:  None #print(*k)

    mprint(f"Exiting {tx[0]}")
    mprint("Inputs:")
    mprint("   -  1")
    depth = math.log2(max(sum(map(len, (map(list, list(tx[1]))))), 1))

    mprint(f"      Tap Branch Cost {depth} depth, ~{32*depth} bytes")
    mprint("Outputs:")
    mprint("    -  Anchor Output")
    mprint("    - ", tx[0])
    [mprint("    - ", t) for t in list(tx[1])]
    mprint("__________________________")
    expr = """sum([
    (36 + 4 + depth * 32 + 32), # Input + Witness
    (radix + 1) * (32 + 1 + 8), # Normal Taproot Outputs
    1*(8+1), # Anchor Output
    4+4+4, # NlockTime, Version, Book Keeping Estimate
    ])
"""
    size_est = eval(expr)
    mprint(f"Size Estimate:\n   {size_est} bytes = {expr}")
    c = "size_est + (36 + 4) + (4 + 4 + 4) + (32 + 1 + 8)"
    size_est_with_anchor = eval(c)
    mprint(f"Plus Anchor Spend:\n   {size_est_with_anchor} bytes = {c}")
    mprint()
    max_size = max(max_size, size_est_with_anchor)
print(max_size)

The argument that the idea of payment pools originated with COSHV/CTV matches my recollection of history. For example, we described Jeremy's original COSHV proposal in Optech Newsletter #48 and our draft included an extended section on payment pools (we used Maxwell's other name for it, "join-pool", which we still use for Optech's topic page).

Isn't the 2018 channel factory paper essentially a precursor to payment pools? And I feel the general idea of sharing a UTXO has been around for even longer than that.

I do think the distinction Steven is trying to make is a useful one, regardless of whether the term "payment pool" covers it or not. Perhaps a more specific term could be used to differentiate the two designs.

I think the channel factory paper came out in late 2017, a bit earlier than you said. I think it's very reasonable to consider Channel Factories as a seminal part of Payment Pool history. For me in particular, I don't recall them as a direct inspiration for my work on payment pools, though I think I was aware of them at some point, and when someone drew the connection it made sense that the concepts were related. I also don't particularly think any of the Channel Factory authors were directly aware of my research into covenants -- had they been, they probably would have described Payment Pools in their paper :)

Just writing some off-the-cuff best effort history from my perspective, since I guess it's of intrigue...

There was a a little bit of that kind of stuff floating around at the time, I remember discussing a related concept of "meta channels" with some LN people around that time too (unfortunately, I can't find any notes on what in particular, although I do remember no one could understand what I was talking about with channels inside of channels because it was unclear why you'd want subchannels with less liquidity than the parents). I think that was towards the end of 2016.

For me, I came to "payment pool" like stuff out of a growth of my research on covenants, which I presented in early 2017 https://btctranscripts.com/blockchain-protocol-analysis-security-engineering/2017/2017-01-26-jeremy-rubin-covenants/. I was starting around this point to think about congestion issues and using batched operations across every step of lighting to better share resources, but it wasn't quite a payment pool since I focused on defering HTLC resolution in this presentation.

After that presentation, I wanted to bring covenants to Bitcoin so I started implementing the concepts I discussed, which you can see in my experimental bitcoin fork here. The main things I added were a total memory limited OP_CAT, SUBSTR, math ops, GETBLOCKHASH, GETINPUT, CSFS, and UTXOEXISTS.

Around this time (2017-2018?) I was also doing some part time technical consulting for Stellar, where I was working on a version of payment channels https://stellar.org/blog/developers/lightning-on-stellar-roadmap based on an Eltoo style ratchet. During that work I helped design a concept of Deterministic Accounts (and Sequence Bumping) https://github.com/stellar/stellar-protocol/blob/4390aaa82fdd6681e60f09416007c3a5dc24e352/core/cap-0007.md which if you squint has similarities to a covenant/APO ratchet in Bitcoin. During this time we were also talking about multiparty keyed channels as well as emitting channels-from-channels. The way Stellar works account creation was not reliable (could be front run) and was also unspecified (you get an arbitrary start nonce), and in order to be able to create channels out of channels we needed them to have a known start state. It required a non interactive channel creation capability (unlike bitcoin, where the interactivity is just prohibitive).

As I failed to garner much support for the bag of opcodes research direction, I started working on Lazuli as a purely user level way of accomplishing some of the covenants I was interested in with an efficient ECDSA presigning protocol. No one wanted to hear about fancy crypto with ECDSA though and there are limitations with what you can do in an N-Party context. In Lazuli, I did focus more on congestion control for channel

After failing to get any eyes on Lazuli, I went back to a direct covenants approach and made OP_COSHV which became CTV.

The original Channel Factory paper needed a plain checkmultisig, so each layer was O(N) sized, meaning N log N exit cost, although the paper says Schnorr might one day have aggregate multisig. You also needed to do one round to set up the whole tree, do all the signatures across all of those, and then do a final round signature on the last one to "fund" it. Even with Lazuli's ecdsa presigning protocol, though you could have constant sized sigs, it would make signing require a lot more interactivity and use my unproven algorithm for n party ecdsa. Channel Factories were also only really designed to be hosts for Payment Channels, as opposed to being usable for more general purpose. This also led to some weirdness in original channel factories around workable revocation states for parent-node txns.

I think the core innovation that distinguishes COSHV and the payment pools possible with it is the non-interactivity benefits of adding covenants. Without a covenant, Payment Pools would be are prohibitive to set up, maintain, and require massive presigning + state storage compared. Covenant based designis naturally can support many more users. And so I think that's where as a concept Payment Pools were a clean separation fromchannel factories because the addition of covenants were the key enabling technologies to make utxo sharing practical.

stevenroose / covenants.info

Set CTV to show payment pool support #16

below the break, an old mailing list post of mine responding to TLUV: