Re: [bitcoin-dev] [Lightning-dev] CPFP Carve-Out for Fee-Prediction Issues in Contracting Applications (eg Lightning)

[David A. Harding via bitcoin-dev]

On Mon, Oct 28, 2019 at 10:45:39AM +0100, Johan Torås Halseth wrote:
> Relay cost is the obvious problem with just naively removing all limits.
> Relaxing the current rules by allowing to add a child to each output as
> long as it has a single unconfirmed parent would still only allow free
> relay of O(size of parent) extra data (which might not be that bad? Similar
> to the carve-out rule we could put limits on the child size). 

A parent transaction near the limit of 100,000 vbytes could have almost
10,000 outputs paying OP_TRUE (10 vbytes per output).  If the children
were limited to 10,000 vbytes each (the current max carve-out size),
that allows relaying 100 mega-vbytes or nearly 400 MB data size (larger
than the default maximum mempool size in Bitcoin Core).

As Matt noted in discussion on #lightning-dev about this issue, it's
possible to increase second-child carve-out to nth-child carve-out but
we'd need to be careful about choosing an appropriately low value for n.

For example, BOLT2 limits the number of HTLCs to 483 on each side of the
channel (so 966 + 2 outputs total), which means the worst case free
relay to support the current LN protocol would be approximately:

(10 + 968 * 1) * 4 = ~39 MB

Even if the mempool was empty (as it sometimes is these days), it would
only cost an attacker about 1.5 BTC to fill it at the default minimum
relay feerate[1] so that they could execute this attack at the minimal
cost per iteration of paying for a few hundred or a few thousand vbytes
at slightly higher than the current mempool minimum fee.

Instead, with the existing rules (including second-child carve-out),
they'd have to iterate (39 MB / 400 kB = ~100) times more often to
achieve an equivalent waste of bandwidth, costing them proportionally
more in fees.

So, I think these rough numbers clearly back what Matt said about us
being able to raise the limits a bit if we need to, but that we have to
be careful not to raise them so far that attackers can make it
significantly more bandwidth expensive for people to run relaying full
nodes.

-Dave

[1] Several developers are working on lowering the default minimum in
Bitcoin Core, which would of course make this attack proportionally
cheaper.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[bitcoin-dev] Fwd: node-Tor is now open source in clear (and modular)

[Aymeric Vitte via bitcoin-dev]

FYI, javascript implementation of the Tor protocol on server side and
inside browsers

Not related directly to bitcoin-dev but might be of some use one day to
anonymize bitcoin apps (light wallets for example)


 Message transféré 
Sujet : node-Tor is now open source in clear (and modular)
Date :  Thu, 24 Oct 2019 18:02:42 +0200
De :Aymeric Vitte 
Pour :  tor-t...@lists.torproject.org



Please see https://github.com/Ayms/node-Tor and http://peersm.com/peersm2

This is a javascript implementation of the Tor protocol on server side
(nodejs) and inside browsers, please note that it is not intended to add
nodes into the Tor network, neither to implement the Tor Browser
features, it is intended to build projects using the Tor protocol from
the browser and/or servers (most likely P2P projects), the Onion Proxy
and Onion Router functions are available directly inside the browser
which establishes circuits with other nodes understanding the Tor
protocol (so it's not a "dumb" proxy), but it can of course establish
circuits with the Tor network nodes (see
https://github.com/Ayms/node-Tor#test-configuration-and-use) and act as
a Tor node

It is financed by NLnet via EU Horizon 2020 Next Generation Internet
Privacy & Trust Enhancing Technologies, now open source under a MIT
license and we made it modular, it is fast (extensively tested when
video streaming was there, especially with bittorrent or ORDB concept)
and the total unminified code
(https://github.com/Ayms/node-Tor/blob/master/html/browser.js) is only 1
MB (so ~600 kB minified) which is quite small for what it does, this is
not a browser extension/module but pure js

Possible next steps are to implement elliptic crypto and connections via
WebRTC Snowflake (peersm2 above uses WebSockets a bit the way flashproxy
was working, ie implementing the ws interface on bridges side), as well
as integrating it with "Discover and move your coins by yourself"
(https://peersm.com/wallet) for anonymous blockchain search and
anonymous sending of transactions from the browser

-- 
Move your coins by yourself (browser version): https://peersm.com/wallet
Bitcoin transactions made simple: https://github.com/Ayms/bitcoin-transactions
Zcash wallets made simple: https://github.com/Ayms/zcash-wallets
Bitcoin wallets made simple: https://github.com/Ayms/bitcoin-wallets
Get the torrent dynamic blocklist: http://peersm.com/getblocklist
Check the 10 M passwords list: http://peersm.com/findmyass
Anti-spies and private torrents, dynamic blocklist: http://torrent-live.org
Peersm : http://www.peersm.com
torrent-live: https://github.com/Ayms/torrent-live
node-Tor : https://www.github.com/Ayms/node-Tor
GitHub : https://www.github.com/Ayms

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] [Lightning-dev] CPFP Carve-Out for Fee-Prediction Issues in Contracting Applications (eg Lightning)

[Johan Torås Halseth via bitcoin-dev]

>
>
> I don’te see how? Let’s imagine Party A has two spendable outputs, now
> they stuff the package size on one of their spendable outlets until it is
> right at the limit, add one more on their other output (to meet the
> Carve-Out), and now Party B can’t do anything.

Matt: With the proposed change, party B would always be able to add a child
to its output, regardless of what games party A is playing.


Thanks for the explanation, Jeremy!


> In terms of relay cost, if an ancestor can be replaced, it will invalidate
> all it's children, meaning that no one paid for that broadcasting. This can
> be fixed by appropriately assessing Replace By Fee update fees to
> encapsulate all descendants, but there are some tricky edge cases that make
> this non-obvious to do.


Relay cost is the obvious problem with just naively removing all limits.
Relaxing the current rules by allowing to add a child to each output as
long as it has a single unconfirmed parent would still only allow free
relay of O(size of parent) extra data (which might not be that bad? Similar
to the carve-out rule we could put limits on the child size). This would be
enough for the current LN use case (increasing fee of commitment tx), but
not for OP_SECURETHEBAG I guess, as you need the tree of children, as you
mention.

I imagine walking the mempool wouldn't change much, as you would only have
one extra child per output. But here I'm just speculating, as I don't know
the code well enough know what the diff would look like.


> OP_SECURETHEBAG can help with the LN issue by putting all HTLCS into a
> tree where they are individualized leaf nodes with a preceding CSV. Then,
> the above fix would ensure each HTLC always has time to close properly as
> they would have individualized lockpoints. This is desirable for some
> additional reasons and not for others, but it should "work".


This is interesting for an LN commitment! You could really hide every
output of the commitment within OP_STB, which could either allow bypassing
the fee-pinning attack entirely (if the output cannot be spent unconfirmed)
or adding fees to the commitment using SIGHASH_SINGLE|ANYONECANPAY.

- Johan

On Sun, Oct 27, 2019 at 8:13 PM Jeremy  wrote:

> Johan,
>
> The issues with mempool limits for OP_SECURETHEBAG are related, but have
> distinct solutions.
>
> There are two main categories of mempool issues at stake. One is relay
> cost, the other is mempool walking.
>
> In terms of relay cost, if an ancestor can be replaced, it will invalidate
> all it's children, meaning that no one paid for that broadcasting. This can
> be fixed by appropriately assessing Replace By Fee update fees to
> encapsulate all descendants, but there are some tricky edge cases that make
> this non-obvious to do.
>
> The other issue is walking the mempool -- many of the algorithms we use in
> the mempool can be N log N or N^2 in the number of descendants. (simple
> example: an input chain of length N to a fan out of N outputs that are all
> spent, is O(N^2) to look up ancestors per-child, unless we're caching).
>
> The other sort of walking issue is where the indegree or outdegree for a
> transaction is high. Then when we are computing descendants or ancestors we
> will need to visit it multiple times. To avoid re-expanding a node, we
> currently cache it with a set. This uses O(N) extra memory and makes O(N
> Log N) (we use std::set not unordered_set) comparisons.
>
> I just opened a PR which should help with some of the walking issues by
> allowing us to cheaply cache which nodes we've visited on a run. It makes a
> lot of previously O(N log N) stuff O(N) and doesn't allocate as much new
> memory. See: https://github.com/bitcoin/bitcoin/pull/17268.
>
>
> Now, for OP_SECURETHEBAG we want a particular property that is very
> different from with lightning htlcs (as is). We want that an unlimited
> number of child OP_SECURETHEBAG txns may extend from a confirmed
> OP_SECURETHEBAG, and then at the leaf nodes, we want the same rule as
> lightning (one dangling unconfirmed to permit channels).
>
> OP_SECURETHEBAG can help with the LN issue by putting all HTLCS into a
> tree where they are individualized leaf nodes with a preceding CSV. Then,
> the above fix would ensure each HTLC always has time to close properly as
> they would have individualized lockpoints. This is desirable for some
> additional reasons and not for others, but it should "work".
>
>
>
> --
> @JeremyRubin 
> 
>
>
> On Fri, Oct 25, 2019 at 10:31 AM Matt Corallo 
> wrote:
>
>> I don’te see how? Let’s imagine Party A has two spendable outputs, now
>> they stuff the package size on one of their spendable outlets until it is
>> right at the limit, add one more on their other output (to meet the
>> Carve-Out), and now Party B can’t do anything.
>>
>> On Oct 24, 2019, at 21:05, Johan Torås Halseth  wrote:
>>
>> 
>> It essentially changes the rule to always allow CPFP-ing the

Re: [bitcoin-dev] [Lightning-dev] CPFP Carve-Out for Fee-Prediction Issues in Contracting Applications (eg Lightning)

[Johan Torås Halseth via bitcoin-dev]

It essentially changes the rule to always allow CPFP-ing the commitment as
long as there is an output available without any descendants. It changes
the commitment from "you always need at least, and exactly, one non-CSV
output per party. " to "you always need at least one non-CSV output per
party. "

I realize these limits are there for a reason though, but I'm wondering if
could relax them. Also now that jeremyrubin has expressed problems with the
current mempool limits.

On Thu, Oct 24, 2019 at 11:25 PM Matt Corallo 
wrote:

> I may be missing something, but I'm not sure how this changes anything?
>
> If you have a commitment transaction, you always need at least, and
> exactly, one non-CSV output per party. The fact that there is a size
> limitation on the transaction that spends for carve-out purposes only
> effects how many other inputs/outputs you can add, but somehow I doubt
> its ever going to be a large enough number to matter.
>
> Matt
>
> On 10/24/19 1:49 PM, Johan Torås Halseth wrote:
> > Reviving this old thread now that the recently released RC for bitcoind
> > 0.19 includes the above mentioned carve-out rule.
> >
> > In an attempt to pave the way for more robust CPFP of on-chain contracts
> > (Lightning commitment transactions), the carve-out rule was added in
> > https://github.com/bitcoin/bitcoin/pull/15681. However, having worked on
> > an implementation of a new commitment format for utilizing the Bring
> > Your Own Fees strategy using CPFP, I’m wondering if the special case
> > rule should have been relaxed a bit, to avoid the need for adding a 1
> > CSV to all outputs (in case of Lightning this means HTLC scripts would
> > need to be changed to add the CSV delay).
> >
> > Instead, what about letting the rule be
> >
> > The last transaction which is added to a package of dependent
> > transactions in the mempool must:
> >   * Have no more than one unconfirmed parent.
> >
> > This would of course allow adding a large transaction to each output of
> > the unconfirmed parent, which in effect would allow an attacker to
> > exceed the MAX_PACKAGE_VIRTUAL_SIZE limit in some cases. However, is
> > this a problem with the current mempool acceptance code in bitcoind? I
> > would imagine evicting transactions based on feerate when the max
> > mempool size is met handles this, but I’m asking since it seems like
> > there has been several changes to the acceptance code and eviction
> > policy since the limit was first introduced.
> >
> > - Johan
> >
> >
> > On Wed, Feb 13, 2019 at 6:57 AM Rusty Russell  > > wrote:
> >
> > Matt Corallo  > > writes:
> > >>> Thus, even if you imagine a steady-state mempool growth, unless
> the
> > >>> "near the top of the mempool" criteria is "near the top of the
> next
> > >>> block" (which is obviously *not* incentive-compatible)
> > >>
> > >> I was defining "top of mempool" as "in the first 4 MSipa", ie.
> next
> > >> block, and assumed you'd only allow RBF if the old package wasn't
> > in the
> > >> top and the replacement would be.  That seems incentive
> > compatible; more
> > >> than the current scheme?
> > >
> > > My point was, because of block time variance, even that criteria
> > doesn't hold up. If you assume a steady flow of new transactions and
> > one or two blocks come in "late", suddenly "top 4MWeight" isn't
> > likely to get confirmed until a few blocks come in "early". Given
> > block variance within a 12 block window, this is a relatively likely
> > scenario.
> >
> > [ Digging through old mail. ]
> >
> > Doesn't really matter.  Lightning close algorithm would be:
> >
> > 1.  Give bitcoind unileratal close.
> > 2.  Ask bitcoind what current expidited fee is (or survey your
> mempool).
> > 3.  Give bitcoind child "push" tx at that total feerate.
> > 4.  If next block doesn't contain unilateral close tx, goto 2.
> >
> > In this case, if you allow a simpified RBF where 'you can replace if
> > 1. feerate is higher, 2. new tx is in first 4Msipa of mempool, 3.
> > old tx isnt',
> > it works.
> >
> > It allows someone 100k of free tx spam, sure.  But it's simple.
> >
> > We could further restrict it by marking the unilateral close somehow
> to
> > say "gonna be pushed" and further limiting the child tx weight (say,
> > 5kSipa?) in that case.
> >
> > Cheers,
> > Rusty.
> > ___
> > Lightning-dev mailing list
> > lightning-...@lists.linuxfoundation.org
> > 
> > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
> >
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev