Return-Path: Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id D2D94C016F for ; Sun, 7 Jun 2020 22:45:32 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id CF4B087C7D for ; Sun, 7 Jun 2020 22:45:32 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id h00sA7A1bsFR for ; Sun, 7 Jun 2020 22:45:31 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11]) by hemlock.osuosl.org (Postfix) with ESMTPS id 8591887C76 for ; Sun, 7 Jun 2020 22:45:30 +0000 (UTC) Received: from mail-il1-f172.google.com (mail-il1-f172.google.com [209.85.166.172]) (authenticated bits=0) (User authenticated as jlrubin@ATHENA.MIT.EDU) by outgoing.mit.edu (8.14.7/8.12.4) with ESMTP id 057MjS16031509 (version=TLSv1/SSLv3 cipher=AES128-GCM-SHA256 bits=128 verify=NOT) for ; Sun, 7 Jun 2020 18:45:29 -0400 Received: by mail-il1-f172.google.com with SMTP id b5so15034269iln.5 for ; Sun, 07 Jun 2020 15:45:28 -0700 (PDT) X-Gm-Message-State: AOAM533f7Ml/5nZppBRqIM7k6NOcxUOr1JJuh4ZBL2/qoVPkQCr8pSX3 4hwsEmv3r8jWspaHBuri6sUP2abgT0tIgOkBuMA= X-Google-Smtp-Source: ABdhPJwxqgR8DiYl7p6MR9fUga09d4nKs3xwvH0HDVGXJf0uS6LBVVHVeSr+qHRL2a2IQRGSjYPQdoQWc7Bu9+MmYtE= X-Received: by 2002:a92:db0b:: with SMTP id b11mr18404653iln.90.1591569928062; Sun, 07 Jun 2020 15:45:28 -0700 (PDT) MIME-Version: 1.0 References: <1cQUGt1pX0_lWPJm-tFDr9fQCvrPd5vqmCorgN89jy7gUF0m9wsouUosrFm1eal3jO9oB1BvMtORGE2htLdFjyDD5lno_QkXCFn971LQNZY=@protonmail.com> In-Reply-To: <1cQUGt1pX0_lWPJm-tFDr9fQCvrPd5vqmCorgN89jy7gUF0m9wsouUosrFm1eal3jO9oB1BvMtORGE2htLdFjyDD5lno_QkXCFn971LQNZY=@protonmail.com> From: Jeremy Date: Sun, 7 Jun 2020 15:45:16 -0700 X-Gmail-Original-Message-ID: Message-ID: To: =?UTF-8?Q?Joachim_Str=C3=B6mbergson?= Content-Type: multipart/alternative; boundary="0000000000003290d805a786405b" Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 07 Jun 2020 22:45:32 -0000 --0000000000003290d805a786405b Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Joachim, Fantastic questions! I think it makes sense to think about it in terms of today, and then in terms of a long-dated future where wallets have much richer native understandings of these things. This helps preserve the purity of the arguments I'm making with respect to what it would look like today v.s. what it could look like with strong integration. Today: 1) I would expect that exchanges do this as a CTV txn that is one initial confirmation to a single output, and then that output expands to either all the payments in the batch, or to a histogram of single-layer CTVs based on priority/amount being spent. E.g, either A -> B -> {C,D,E,F,G...} or A->B->{C -> {D,E,F}, G -> {H, I J}, K -> ....}. I would further expect that the entire tree would include fees such that it will get into at least the bottom of the mempool. See https://utxos.org/analysis/batching_sim/ for more info. If txns land in the mempool, then users learn about it (even with an un-updated wallet) just like the learn of normal unconfirmed transactions. Even this simple two-step transaction can deliver massive batching savings. OpTech has some coverage of this simple commit-now-distribute-later scheme here https://bitcoinops.org/en/newsletters/2019/05/29/#proposed-new-opcode-for-t= ransaction-output-commitments . I'd also expect that exchanges in particular already store their outbound transactions in resilient storage (for audit and compliance as well as liability protection), so they would likely be able to make this data available to their customers on inquiry if discarded. I'm all for redundancy, so exchanges can also e.g. send an email with a backup file if they want to. But that's not necessary for it to work today, you can just watch the mempool like wallets already do. A slightly patched wallet can treat CTV outs as more confirmed (e.g., like an own-change address) than a normal unconfirmed out. 2) I would expect that exchanges pay a reasonable amount of fees for the transaction so it can expect to at least get to the bottom range of the mempool for children, and top of the mempool for the parent. Your question seems to be more about after this phase. First I would note that it is truly O(log(N)), but E[O(1)], because it amortizes. That is, to claim out all of the outputs is a total overhead of O(N), not O(N log N). Fees in this model are paid by CPFP. Because CPFP is currently *Child* pays for parent and not *Children* pay for parent, we don't (unfortunately) have rational txn selection for this case. Any wallet can construct this spend path by rebroadcasting (if evicted) the parents and spending the txn. The exchange can also 'bound' themselves to seeing a transaction to completion by including some change address at the leaf node layer (not much overhead depending on radix). Thus the payer of fees is the person who needs to spend. 3) Not exactly, the middle txns are immutable. but it may be possible to construct a low-fee longchain which can cause transaction pinning. If you do a shallow tree as described in (1), the current lightning carve should help to prevent this. Future: 1) Most likely the desirable radix for a tree is something like 4 or 5 which minimizes the amount of work on an individual basis (you can compute this by figuring out how deep the tree would be and the per-tx overheads, 4 or 5 pop out as being minimal overhead and the benefit is recursive). Mempool broadcast still should work, but it's possible that for privacy reasons it's preferred to not broadcast through mempool. It's also possible that all payouts are into non-interactive lightning channels with N-of-N taproot at each layer, so you receive a proof through your lightning wallet and can immediately route payments, and when you want to close opportunistically cooperate to reduce chain overhead. You can think of CTV as an anchor for bootstrapping these layer two protocols with an on-chain bisection algorithm to discover online participants to re-negotiate with. A privacy and scalability win! I further expect business wallets (like exchanges) to be able to credit deposits from CTV trees without requiring full expansion. This is also a privacy win, and can decrease latency of moving large value funds (e.g., exceeding inter exchange channel balances) and crediting funds for trading. 2) I think we'll eventually converge on a non-destructive way of adding fees. RBF is destructive in that you're replacing a TX. CPFP is destructive in that you have a spend a coin to drive progress. Without a new opcode you can emulate this with CTV by at nodes in the tree having a consumable output that serves as a CPFP hook/a RBF hook. You can see some discussion here (animated, so use pres mode) https://docs.google.com/presentation/d/1XDiZOz52XyJc4LDSbiD9_JAaJobyF5QDGtR= 3O9qD7yg/edit#slide=3Did.g7d267915e2_0_44. This adds some extra chain weight, but is possible without further extension. What I think we'll eventually land on is a way of doing a tx that contributes fee to another tx chain as a passive observer to them. While this breaks one abstraction around how dependencies between transactions are processed, it also could help resolve some really difficult challenges we face with application-DoS (pinning and other attacks) in the mempool beyond CTV. I have a napkin design for how this could work, but nothing quite ready to share yet. 3) Hopefully 2 solves pinning :) -- @JeremyRubin On Sun, Jun 7, 2020 at 9:51 AM Joachim Str=C3=B6mbergson < joachimstr@protonmail.com> wrote: > Hello everyone, > > regarding OP_CTV, I am considering the scaling use case, specifically an > exchange (or similar) who wants to batch pay to OP_CTV to many users, and= I > wonder > > 1) How do you expect the exchange to communicate the proof of the payment > to the user wallets such that they are able to construct the follow up > transactions and accept the payment. This is UI question. Do you expect > exchanges to provide a certain importable file/blob that the wallet will > allow you to entry? > > 2) Who pays the fees and how for the transaction within the structure tha= t > OP_CTVed output is committed to? Say there is a tree structure and I want > to get the coin out. Someone needs to send log(N) transactions to the cha= in > in order for me to get access to the final UTXO I am interested in. Who c= an > construct such transaction path and what do they need for it and who pays > fees on that (which input)? > > 3) Depending on 2) above, is it not possible for a malicious entity who i= s > among the many users being paid, but who has very small UTXO there relati= ve > to others, to construct this middle transaction and use a very small fee > rate in order to DoS other participants. Is it even possible for this > attacker to create the middle transaction with RBF disabled? > > Thank you, > Joachim > > > > Sent with ProtonMail Secure Email. > > =E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90 Original = Message =E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90 > On Tuesday, November 26, 2019 1:50 AM, Jeremy via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > > Bitcoin Developers, > > Pleased to announce refinements to the BIP draft for > OP_CHECKTEMPLATEVERIFY (replaces previous OP_SECURETHEBAG BIP). Primarily= : > > 1) Changed the name to something more fitting and acceptable to the > community > 2) Changed the opcode specification to use the argument off of the stack > with a primitive constexpr/literal tracker rather than script lookahead > 3) Permits future soft-fork updates to loosen or remove "constexpr" > restrictions > 4) More detailed comparison to alternatives in the BIP, and why > OP_CHECKTEMPLATEVERIFY should be favored even if a future technique may > make it semi-redundant. > > Please see: > BIP: https://github.com/JeremyRubin/bips/blob/ctv/bip-ctv.mediawiki > Reference Implementation: > https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify > > I believe this addresses all outstanding feedback on the design of this > opcode, unless there are any new concerns with these changes. > > I'm also planning to host a review workshop in Q1 2020, most likely in Sa= n > Francisco. Please fill out the form here > https://forms.gle/pkevHNj2pXH9MGee9 if you're interested in participating > (even if you can't physically attend). > > And as a "but wait, there's more": > > 1) RPC functions are under preliminary development, to aid in testing and > evaluation of OP_CHECKTEMPLATEVERIFY. The new command `sendmanycompacted` > shows one way to use OP_CHECKTEMPLATEVERIFY. See: > https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-rpcs. > `sendmanycompacted` is still under early design. Standard practices for > using OP_CHECKTEMPLATEVERIFY & wallet behaviors may be codified into a > separate BIP. This work generalizes even if an alternative strategy is us= ed > to achieve the scalability techniques of OP_CHECKTEMPLATEVERIFY. > 2) Also under development are improvements to the mempool which will, in > conjunction with improvements like package relay, help make it safe to li= ft > some of the mempool's restrictions on longchains specifically for > OP_CHECKTEMPLATEVERIFY output trees. See: https://github.com/bitcoin/bitc= oin/pull/17268 > This work offers an improvement irrespective of OP_CHECKTEMPLATEVERIFY's > fate. > > > Neither of these are blockers for proceeding with the BIP, as they are > ergonomics and usability improvements needed once/if the BIP is activated= . > > See prior mailing list discussions here: > > * > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016934.h= tml > * > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-June/016997.= html > > > Thanks to the many developers who have provided feedback on iterations of > this design. > > Best, > > Jeremy > -- > @JeremyRubin > > > > --0000000000003290d805a786405b Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Joachim,

Fantast= ic questions!

I think it makes sense to think about it in terms o= f today, and then in terms of a long-dated future where wallets have much r= icher native understandings of these things. This helps preserve the purity= of the arguments I'm making with respect to what it would look like to= day v.s. what it could look like with strong integration.

Today:
1) I would expect that exchanges do thi= s as a CTV txn that is one initial confirmation to a single output, and the= n that output expands to either all the payments in the batch, or to a hist= ogram of single-layer CTVs based on priority/amount being spent. E.g, eithe= r A -> B -> {C,D,E,F,G...} or A->B->{C -> {D,E,F}, G -> {= H, I J}, K -> ....}. I would further expect that the entire tree would i= nclude fees such that it will get into at least the bottom of the mempool. = See https://utxos.org/= analysis/batching_sim/ for more info. If txns land in the mempool, then= users learn about it (even with an un-updated wallet) just like the learn = of normal unconfirmed transactions. Even this simple two-step transaction c= an deliver massive batching savings. OpTech has some coverage of this simpl= e commit-now-distribute-later scheme here https://bitcoinops.org/en/newsletters/2019/05/29/#proposed-new-opc= ode-for-transaction-output-commitments.=C2=A0

I'd also expect= that exchanges in particular already store their outbound transactions in = resilient storage (for audit and compliance as well as liability protection= ), so they would likely be able to make this data available to their custom= ers on inquiry if discarded.

I'm all for redundancy, so exchanges= can also e.g. send an email with a backup file if they want to. But that&#= 39;s not necessary for it to work today, you can just watch the mempool lik= e wallets already do.

A slightly patched wallet can treat CTV outs as= more confirmed (e.g., like an own-change address) than a normal unconfirme= d out.

2) I would expect that exchanges pay a reasonable amount o= f fees for the transaction so it can expect to at least get to the bottom r= ange of the mempool for children, and top of the mempool for the parent. Yo= ur question seems to be more about after this phase.

First I would no= te that it is truly O(log(N)), but E[O(1)], because it amortizes. That is, = to claim out all of the outputs is a total overhead of O(N), not O(N log N)= . Fees in this model are paid by CPFP. Because CPFP is currently *Child* pa= ys for parent and not *Children* pay for parent, we don't (unfortunatel= y) have rational txn selection for this case. Any wallet can construct this= spend path by rebroadcasting (if evicted) the parents and spending the txn= . The exchange can also 'bound' themselves to seeing a transaction = to completion by including some change address at the leaf node layer (not = much overhead depending on radix).

Thus the payer of fees is the= person who needs to spend.

3) Not exactly, the middle txns are immut= able. but it may be possible to construct a low-fee longchain which can cau= se transaction pinning. If you do a shallow tree as described in (1), the c= urrent lightning carve should help to prevent this.

Future:
=
1) Most likely the desirable radix for a t= ree is something like 4 or 5 which minimizes the amount of work on an indiv= idual basis (you can compute this by figuring out how deep the tree would b= e and the per-tx overheads, 4 or 5 pop out as being minimal overhead and th= e benefit is recursive). Mempool broadcast still should work, but it's = possible that for privacy reasons it's preferred to not broadcast throu= gh mempool. It's also possible that all payouts are into non-interactiv= e lightning channels with N-of-N taproot at each layer, so you receive a pr= oof through your lightning wallet and can immediately route payments, and w= hen you want to close opportunistically cooperate to reduce chain overhead.= You can think of CTV as an anchor for bootstrapping these layer two protoc= ols with an on-chain bisection algorithm to discover online participants to= re-negotiate with. A privacy and scalability win!

I further expect b= usiness wallets (like exchanges) to be able to credit deposits from CTV tre= es without requiring full expansion. This is also a privacy win, and can de= crease latency of moving large value funds (e.g., exceeding inter exchange = channel balances) and crediting funds for trading.

2) I think we&= #39;ll eventually converge on a non-destructive way of adding fees. RBF is = destructive in that you're replacing a TX. CPFP is destructive in that = you have a spend a coin to drive progress. Without a new opcode you can emu= late this with CTV by at nodes in the tree having a consumable output that = serves as a CPFP hook/a RBF hook. You can see some discussion here (animate= d, so use pres mode) = https://docs.google.com/presentation/d/1XDiZOz52XyJc4LDSbiD9_JAaJobyF5QDGtR= 3O9qD7yg/edit#slide=3Did.g7d267915e2_0_44. This adds some extra chain w= eight, but is possible without further extension. What I think we'll ev= entually land on is a way of doing a tx that contributes fee to another tx = chain as a passive observer to them. While this breaks one abstraction arou= nd how dependencies between transactions are processed, it also could help = resolve some really difficult challenges we face with application-DoS (pinn= ing and other attacks) in the mempool beyond CTV. I have a napkin design fo= r how this could work, but nothing quite ready to share yet.

3) H= opefully 2 solves pinning :)


On Sun, Jun 7, 2020 at 9:51 AM Joachim Str=C3=B6mbergson <joachimstr@protonmail.com> = wrote:

Hello = everyone,

regarding OP_CTV, I am considering the scaling use case= , specifically an exchange (or similar) who wants to batch pay to OP_CTV to= many users, and I wonder

1) How do you expect the exchange to co= mmunicate the proof of the payment to the user wallets such that they are a= ble to construct the follow up transactions and accept the payment. This is= UI question. Do you expect exchanges to provide a certain importable file/= blob that the wallet will allow you to entry?

2) Who pays the fee= s and how for the transaction within the structure that OP_CTVed output is = committed to? Say there is a tree structure and I want to get the coin out.= Someone needs to send log(N) transactions to the chain in order for me to = get access to the final UTXO I am interested in. Who can construct such tra= nsaction path and what do they need for it and who pays fees on that (which= input)?

3) Depending on 2) above, is it not possible for a malic= ious entity who is among the many users being paid, but who has very small = UTXO there relative to others, to construct this middle transaction and use= a very small fee rate in order to DoS other participants. Is it even possi= ble for this attacker to create the middle transaction with RBF disabled?

Thank you,
Joachim

<= p>



Sent with ProtonMail Secure Email= .

=E2=80=90=E2=80=90=E2=80=90=E2=80=90= =E2=80=90=E2=80=90=E2=80=90 Original Message =E2=80=90=E2=80=90=E2=80=90=E2= =80=90=E2=80=90=E2=80=90=E2=80=90
On Tuesday, November 26, 2= 019 1:50 AM, Jeremy via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.o= rg> wrote:

Bitcoin Developers,

<= div style=3D"color:rgb(0,0,0);font-family:arial,helvetica,sans-serif;font-s= ize:small">Pleased to announce refinements to the BIP draft for OP_CHECKTEM= PLATEVERIFY (replaces previous OP_SECURETHEBAG BIP). Primarily:

1) Changed the name to something more fitti= ng and acceptable to the community
2) Changed the opco= de specification to use the argument off of the stack with a primitive cons= texpr/literal tracker rather than script lookahead
3) = Permits future soft-fork updates to loosen or remove "constexpr" = restrictions
4) More detailed comparison to alternativ= es in the BIP, and why OP_CHECKTEMPLATEVERIFY should be favored even if a f= uture technique may make it semi-redundant.

=
Please see:
<= div style=3D"color:rgb(0,0,0);font-family:arial,helvetica,sans-serif;font-s= ize:small">Reference Implementation: https://github.com/= JeremyRubin/bitcoin/tree/checktemplateverify

<= /div>
I believe this addresses all outstanding feedback on the d= esign of this opcode, unless there are any new concerns with these changes.=

I'm also planning to host a= review workshop in Q1 2020, most likely in San Francisco. Please fill out = the form here https://forms.gle/pkevHNj2pXH9MGee9 if you're interested in pa= rticipating (even if you can't physically attend).

And as a "but wait, there's more":

1) RPC functions are under prelimi= nary development, to aid in testing and evaluation of OP_CHECKTEMPLATEVERIF= Y. The new command `sendmanycompacted` shows one way to use OP_CHECKTEMPLAT= EVERIFY. See: https://github.com/JeremyRubin/bitcoi= n/tree/checktemplateverify-rpcs. `sendmanycompacted` is still under ear= ly design. Standard practices for using OP_CHECKTEMPLATEVERIFY & wallet= behaviors may be codified into a separate BIP. This work generalizes even = if an alternative strategy is used to achieve the scalability techniques of= OP_CHECKTEMPLATEVERIFY.
2) Also under development are= improvements to the mempool which will, in conjunction with improvements l= ike package relay, help make it safe to lift some of the mempool's rest= rictions on longchains specifically for OP_CHECKTEMPLATEVERIFY output trees= . See: https://github.com/bitcoin/bitcoin/pull/17268 This work offers = an improvement irrespective of OP_CHECKTEMPLATEVERIFY's fate.
=


Neither of these ar= e blockers for proceeding with the BIP, as they are ergonomics and usabilit= y improvements needed once/if the BIP is activated.
See prior mailing list discussions here:
=



Thanks= to the many developers who have provided feedback on iterations of this de= sign.

Best,

Jeremy

--0000000000003290d805a786405b--