Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Jeremy <jlrubin@mit.edu>]

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

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, {<KEY> DUP "" 1 TLUV
    CHECKSIGVERIFY
    IN_OUT_AMOUNT SUB <BAL> 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 + 288*6 + 246*2 = 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.

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