[bitcoin-dev] Pinning : The Good, The Bad, The Ugly

2020-06-28 Thread Antoine Riard via bitcoin-dev
(tl;dr Ideally network mempools should be an efficient marketplace leading
to discovery of best-feerate blockspace demand by miners. It's not due to
current anti-DoS rules assumptions and it's quite harmful for shared-utxo
protocols like LN)

Hello all,

Lightning security model relies on the unilateral capability for a channel
participant to confirm transactions, like timing out an outgoing HTLC,
claiming an incoming HTLC or punishing a revoked commitment transaction and
thus enforcing onchain a balance negotiated offchain. This security model
is actually turning back the double-spend problem to a private matter,
making the duty of each channel participant to timely enforce its balance
against the competing interest of its counterparties. Or laid out
otherwise, contrary to a miner violating a consensus rules, base layer
peers don't care about your LN node failing to broadcast a justice
transaction before the corresponding timelock expiration (CSV delay).

Ensuring effective propagation and timely confirmation of LN transactions
is so a critical-safety operation.  Its efficiency should be always
evaluated with regards to base layer network topology, tx-relay propagation
rules, mempools behaviors, consistent policy applied by majority of nodes
and ongoing blockspace demand. All these components are direct parameters
of LN security. Due to the network being public, a malicious channel
counterparty do have an incentive to tweak them to steal from you.

The pinning attacks which have been discussed since a few months are a
direct illustration of this model. Before digging into each pinning
scenario, few properties of the base layer components should be evocated
[0].

Network mempools aren't guaranteed to be convergent, the local order of
events determines the next events accepted. I.e Alice may observe tx X, tx
Y, tx Z and Bob may observe tx Z, tx X, tx Y. If tx Z disable-RBF and tx X
try to replace Z, Alice accepts X and Bob rejects it. This divergence may
persevere until a new block.

Tx-relay topology can be observed by spying nodes [1]. An attacker can
exploit this fact to partition network mempools in different subset and
hamper propagation across them of same-spending output concurrent
transactions. If subset X observes Alice commitment transaction and subset
Y observes Bob commitment transaction, Alice's HTLC-timeout spending her
commitment won't propagate beyond the X-Y set boundaries. An attacker can
always win the propagation race through massive connections or bypassing
tx-relay privacy timers.

Miners mempools are likely identifiable, you could announce a series of
conflicting transactions to different subsets of the network and observe
"tainted" block composition to assign to each subset a miner mempool. I'm
not aware of any research on this, but it sounds plausible to identify all
power-miner mempool, i.e the ones likely to mine a block during the block
delay of the timelock you're looking to exploit. If you can't bid a
transaction in such miner mempools your channel state will stale and your
funds may be in danger.

### Scenario 1) HTLC-Preimage Pinning

As Matt previously explained in his original mail on RBF-pinning, a
malicious counterparty has an interest to pin a low-feerate HTLC-preimage
transaction in some network mempools and thus preventing a honest
HTLC-timeout to confirm. For details, refer to Optech newsletter [2].

This scenario doesn't bear any risk to the attacker, is easy to execute and
has double-digit rate of success. You don't assume network topologies
manipulation, mempools partitions or LN-node-to-full-node mapping [3] That
said this should be solved by implementing and deploying anchor outputs,
which effectively allows a party to unilaterally bump feerate of its
HTLC-timeout transactions.

### The Anchor Output Proposal

Anchor Output proposal is a current spec object implemented by the LN dev
community, it introduces the ability to _unilaterally_ and _dynamically_
bump feerate of any commitment transaction. It also opened the way to bump
local 2nd-stage transactions.

Beyond solving scenario 1), it makes LN node safe with regards to
unexpected mempool congestion. If your commitment transaction is stucking
in network mempools you can bump its feerate by attaching a CPFP on the new
`to_local` anchor. If the remote commitment gets stuck in network mempools,
you're able to bump it by attaching a CPFP on the `to_remote` anchor. This
should keep your safe against an unresponsive or lazy counterparty in case
of onchain funds to claim.

IMO, it comes with a trade-off as it introduces a mapping oracle, i.e a
linking vector between a LN node and its full-node. In this case, a spying
node may establish a dummy, low-value channel with a probed LN node, break
it by broadcasting thousands of different versions of the (revoked)
commitment and observes which one broadcast a CPFP first on the p2p layer.
Obviously, you can mitigate it by not chasing after low-value HTLC, but
that is a 

Re: [bitcoin-dev] MAD-HTLC

2020-06-28 Thread David A. Harding via bitcoin-dev
On Tue, Jun 23, 2020 at 03:47:56PM +0300, Stanga via bitcoin-dev wrote:
> On Tue, Jun 23, 2020 at 12:48 PM ZmnSCPxj  wrote:
> > * Inputs:
> >   * Bob 1 BTC - HTLC amount
> >   * Bob 1 BTC - Bob fidelity bond
> >
> > * Cases:
> >   * Alice reveals hashlock at any time:
> > * 1 BTC goes to Alice
> > * 1 BTC goes to Bob (fidelity bond refund)
> >   * Bob reveals bob-hashlock after time L:
> > * 2 BTC goes to Bob (HTLC refund + fidelity bond refund)
> >   * Bob cheated, anybody reveals both hashlock and bob-hashlock:
> > * 2 BTC goes to miner
> >
> > [...]
> 
> The cases you present are exactly how MAD-HTLC works. It comprises two
> contracts (UTXOs):
> * Deposit (holding the intended HTLC tokens), with three redeem paths:
> - Alice (signature), with preimage "A", no timeout
> - Bob (signature), with preimage "B", timeout T
> - Any entity (miner), with both preimages "A" and "B", no timeout
> * Collateral (the fidelity bond, doesn't have to be of the same amount)
> - Bob (signature), no preimage, timeout T
> - Any entity (miner), with both preimages "A" and "B", timeout T

I'm not these are safe if your counterparty is a miner.  Imagine Bob
offers Alice a MAD-HTLC.  Alice knows the payment preimage ("preimage
A").  Bob knows the bond preimage ("preimage B") and he's the one making
the payment and offering the bond.

After receiving the HTLC, Alice takes no action on it, so the timelock
expires.  Bob publicly broadcasts the refund transaction with the bond
preimage.  Unbeknownst to Bob, Alice is actually a miner and she uses her
pre-existing knowledge of the payment preimage plus her received
knowledge of the bond preimage to privately attempt mining a transaction
that pays her both the payment ("deposit") and the bond ("collateral").

Assuming Alice is a non-majority miner, she isn't guaranteed to
succeed---her chance of success depends on her percentage of the network
hashrate and how much fee Bob paid to incentivize other miners to
confirm his refund transaction quickly.  However, as long as Alice has a
non-trivial amount of hashrate, she will succeed some percentage of the
time in executing this type of attack.  Any of her theft attempts that
fail will leave no public trace, perhaps lulling users into a false
sense of security.

-Dave


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


Re: [bitcoin-dev] MAD-HTLC

2020-06-28 Thread David A. Harding via bitcoin-dev
On Tue, Jun 23, 2020 at 09:41:56AM +0300, Stanga via bitcoin-dev wrote:
> Hi all,
> 
> We'd like to bring to your attention our recent result concerning HTLC.
> Here are the technical report and a short post outlining the main points:
> 
> * https://arxiv.org/abs/2006.12031
> * https://ittayeyal.github.io/2020-06-22-mad-htlc

Thank you for your interesting research!  Further quotes are from your
paper:

>  Myopic Miners: This bribery attack relies on all miners
> being rational, hence considering their utility at game conclu-
> sion instead of myopically optimizing for the next block. If
> a portion of the miners are myopic and any of them gets to
> create a block during the first T − 1 rounds, that miner would
> include Alice’s transaction and Bob’s bribery attempt would
> have failed.
>In such scenarios the attack succeeds only with a certain
> probability – only if a myopic miner does not create a block
> in the first T − 1 rounds. The success probability therefore
> decreases exponentially in T . Hence, to incentivize miners
> to support the attack, Bob has to increase his offered bribe
> exponentially in T .

This is a good abstract description, but I think it might be useful for
readers of this list who are wondering about the impact of this attack
to put it in concrete terms.  I'm bad at statistics, but I think the
probability of bribery failing (even if Bob offers a bribe with an
appropriately high feerate) is 1-exp(-b*h) where `b` is the number of
blocks until timeout and `h` is a percentage of the hashrate controlled
by so-called myopic miners.  Given that, here's a table of attack
failure probabilities:

 "Myopic" hashrate
 B  1%  10% 33% 50%
 l   +-
 o  6|  5.82%   45.12%  86.19%  95.02%
 c  36   |  30.23%  97.27%  100.00% 100.00%
 k  144  |  76.31%  100.00% 100.00% 100.00%
 s  288  |  94.39%  100.00% 100.00% 100.00%

So, if I understand correctly, even a small amount of "myopic" hashrate
and long timeouts---or modest amounts of hashrate and short
timeouts---makes this attack unlikely to succeed (and, even in the cases
where it does succeed, Bob will have to offer a very large bribe to
compensate "rational" miners for their high chance of losing out on
gaining any transaction fees).

Additionally, I think there's the problem of measuring the distribution
of "myopic" hashrate versus "rational" hashrate.  "Rational" miners need
to do this in order to ensure they only accept Bob's timelocked bribe if
it pays a sufficiently high fee.  However, different miners who try to
track what bribes were relayed versus what transactions got mined may
come to different conclusions about the relative hashrate of "myopic"
miners, leading some of them to require higher bribes, which may lead
those those who estimated a lower relative hash rate to assume the rate
of "myopic" mining in increasing, producing a feedback loop that makes
other miners think the rate of "myopic" miners is increasing.  (And that
assumes none of the miners is deliberately juking the stats to mislead
its competitors into leaving money on the table.)

By comparison, "myopic" miners don't need to know anything special about
the past.  They can just take the UTXO set, block height, difficulty
target, and last header hash and mine whatever available transactions
will give them the greatest next-block revenue.

In conclusion, I think: 

1. Given that all known Bitcoin miners today are "myopic", there's no
   short-term issue (to be clear, you didn't claim there was).

2. A very large percentage of the hashrate would have to implement
   "rational" mining for the attack to become particularly effective.
   Hopefully, we'd learn about this as it was happening and could adapt
   before it became an issue.

3. So-called rational mining is probably a lot harder to implement
   effectively than just 150 loc in Python; it probably requires a lot
   more careful incentive analysis than just looking at HTLCs.[1]

4. Although I can't offer a proof, my intuition says that "myopic"
   mining is probably very close to optimal in the current subsidy-fee
   regime.  Optimizing transaction selection only for the next block has
   already proven to be quite challenging to both software and protocol
   developers[2] so I can't imagine how much work it would take to build
   something that effectively optimizes for an unbounded future.  In
   short, I think so-called myopic mining might actually be the most
   rational mining we're capable of.

Nevertheless, I think your results are interesting and that MAD-HTLC is
a useful tool that might be particularly desirable in contracts that
involve especially high value or especially short timeouts (perhaps
asset swaps or payment channels used by traders?).  Thank you again for
posting!

-Dave

[1] For example, your paper says "[...] the bribing cost required to
attack HTLC is independent in T, meaning that