Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli via bitcoin-dev]

On Fri, Jul 3, 2020 at 1:49 PM Itay Tsabary 
wrote:

> Note the required token amount for the collateral contract is low and
> independent of the required deposit tokens -- only a relatively small
> incentive is required to make "acting honestly" Bob's preferred choice.
> So, this is basically a negligible overhead, token-wise. As a downside, it
> does create slightly larger transactions (another UTXO, etc.).
>

I read the MAD-HTLC paper and I think it actually doesn't get into the size
of the collateral (v^{col}). I might have missed it though. Can you please
point me to the section in the paper where the amount is discussed?

I assumed that v^{col} has to be at least the size of v^{dep}. Otherwise,
Bob can threaten Alice with an HTLC bribery attack, and Alice knows that
Bob has very little to lose. Bob *should* have the same amount to lose, to
make it work - no?

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

Re: [bitcoin-dev] MAD-HTLC

[Stanga via bitcoin-dev]

Hi ZmnSCPxj,

1. If all miners are rational and non-myopic, they will support the attack.
They don't need to cooperate, it's not the end of Bitcoin, but they all
have to know everyone is rational and non-myopic. If you want to be secure
in a situation like this then mad-htlc helps. Otherwise you can stick with
htlc. To be clear, assuming it away means assuming at least some miners are
altruistic or suboptimal.

2. I believe what Itay meant when he said myopic is included in non-myopic
is that non-myopic will never choose a worse strategy than myopic. They
both have the same utility function, but the non-myopic has more freedom.
Specifically, if there are enough miners that are either irrational or
myopic, and the bribe is small, then the best non-myopic strategy and the
best myopic strategy is to not accept the bribe. (I think we're all in
agreement on this one, it's just about terminology)

Best,
Ittay


On Fri, Jul 3, 2020 at 3:38 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Ittay,
>
> > Hi all,
> >
> > Itay from MAD-HTLC here. I feel like some details got lost along the way
> so please let me get these sorted out.
> >
> > 1. Myopic and non-myopic miners:
> > When we use the term myopic we mean a miner that optimizes transaction
> selection for the next block with respect only to the next block. The
> term non-myopic refers to a miner that optimizes transaction selection for
> the next block with respect to several future blocks. To accommodate for
> the stochastic nature of block creation these optimizations are of
> the expected revenue. However, neither of these mean that these miners
> choose to act in a way that reduces their expected revenue -- specifically,
> if from a non-myopic's miner perspective including Alice's immediate
> transaction is better off than waiting for Bob's future transaction, then
> this is what they do.
> >
> > Consequently, saying that "being myopic" dominates "being non-myopic" is
> incorrect -- myopic is included in being non-myopic, thus cannot be better
> than it.
>
> The term "dominates" here is a technical term in game theory.
>
> A strategy dominates over another strategy if, in a mixed environment, the
> first strategy always wins more points than the second strategy, no matter
> what proportion they may initially start in the mixed environment.
>
> For example, in an environment of prisoner dilemma games, a tit-for-tat
> strategy dominates over the always-betray strategy, which dominates over
> always-cooperate strategy.
>
> The above is the use of the term "dominate", and not that somehow one
> strategy "contains" the other.
> Always-betray does not contain always-cooperate.
>
> It is immaterial that the non-myopic "contains" myopic strategy as a
> sub-strategy.
> Sometimes, overriding a sub-strategy can lead to worse outcomes and you
> are better off sticking to the sub-strategy rather than an extended
> strategy that sometimes overrides the sub-strategy
>
> (notice how mixed teams of computer+human are no longer dominant in chess,
> because computer chess AIs are now so sophisticated that on average, the
> human overriding the computer strategy often leads to worse outcomes than
> just following the computer; yet about a decade ago such mixed
> computer+human teams were dominant over pure-computer and pure-human teams;
> yet you could say the same, that the computer+human "includes" the
> pure-computer strategy, but nowadays does ***not*** dominate it).
>
> Or: worse is better.
>
>
> What matters is, if you make them compete in an environment, myopic
> strategies will consistently beat non-myopic strategies because the myopic
> miners will impose costs on the non-myopic miners.
>
>
> >
> > So, the next issue to address is estimation of how much of the hash rate
> is actually non-myopic. Currently that answer is simple -- probably 0.
> Bitcoin Core (97% of the blocks) doesn't offer these optimizations, and
> most likely other clients do not have these as well. But, we showed this is
> rather trivial to implement (150 LoC in Bitcoin Core), and theoretically
> can be included in Core's next version AFAIK. Moreover, any miner can
> simply apply our patch independently, achieving the same effect.
> >
> > Please note more elaborate optimizations are in miners' best interest,
> especially as mining incentives transition from block minting to fees --
> the latter are becoming the main income source, and I believe less
> sophisticated miners will miss out substantially. You can check out Phil
> Daian's paper about front-running in Ethereum for example:
> https://arxiv.org/abs/1904.05234
>
> Yes, but again: myopic strategies dominate over non-myopic strategies,
> thus implementing non-myopic strategies is pointless, since they will lose
> revenue in an environment where even a single miner is myopic.
>
> It is immaterial that it takes only 150 LoC to implement non-myopia: if it
> earns less money in an environment where even a

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj via bitcoin-dev]

Good morning Dave,


> > > -   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.


This note seems to have gotten missed in discussion.

Another note is that from what I can tell, the preimages "A" and "B" can be 
provided by any miner.

If the fund value plus the collateral is large enough, it may incentivize 
competing miners to reorg the chain, redirecting the funds of the MAD-HTLC to 
themselves, rather than advance the blockchain state, at least until 
alternative transctions bump their fees up enough that the collateral + fund is 
matched.

This may not apply to Lightning at least if you do not go beyond the Wumbo 
limit, but *could* apply to e.g. SwapMarket, if it uses MAD-HTLCs.

Regards,
ZmnSCPxj

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

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj via bitcoin-dev]

Good morning Ittay,


> The analysis in our MAD-HTLC paper shows that when all players are 
rational (i.e., make the best decisions), and have the greater strategy space 
(which is easy to achieve, 150 Loc), the subgame-perfect-equilibrium strategy 
(this is like Nash-equilibrium for dynamic 
games https://en.wikipedia.org/wiki/Subgame_perfect_equilibrium) for even 
relatively-small fee is to support the attack. Putting it in game-theory terms 
-- strategy "exclude-Alice-until-timeout-then-include-Bob" results with higher 
utility than strategy "include-Alice-Tx-now" (and by definition, 
"include-Alice-Tx-now" does not dominante  
"exclude-Alice-until-timeout-then-include-Bob").

It may be helpful to think in terms of Prisoner Dilemma.


   | cooperate | betray
---+---+-
cooperate  | -1, -1| 0, -3
---+---+-
betray | -3, 0 | -2, -2

"include-Alice-Tx-now" imposes a greater cost on those playing 
"exclude-Alice-until-timeout-then-include-Bob" players, than the benefit that 
both miners play "exclude-Alice-until-timeout-then-include-Bob".

Basically, "cooperate" == "exclude-Alice-until-timeout-then-include-Bob", 
"betray" == "include-Alice-Tx-now".

One way to get around this is to invoke Iterated Prisoner Dilemma, but that 
requires that miners can identify other miners and to be able to act 
accordingly to how those other miners have acted in the past.
The entire point of Bitcoin mining is to allow strong anonymity of miners (not 
that this commonly happens in practice, given the habit of putting identifying 
information in coinbases).

Another way would be to have a higher system that polices its constituents and 
ensures that every miner plays "exclude-Alice-until-timeout-then-include-Bob", 
and punishes "include-Alice-Tx-now".
But that would be equivalent to a centralized cartel, and would be the death of 
Bitcoin anyway, at which point, all Bitcoin tokens will be worthless.


Regards,
ZmnSCPxj

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

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj via bitcoin-dev]

Good morning Ittay,

> Hi all,
>
> Itay from MAD-HTLC here. I feel like some details got lost along the way so 
> please let me get these sorted out.
>
> 1. Myopic and non-myopic miners:
> When we use the term myopic we mean a miner that optimizes transaction 
> selection for the next block with respect only to the next block. The term 
> non-myopic refers to a miner that optimizes transaction selection for the 
> next block with respect to several future blocks. To accommodate for the 
> stochastic nature of block creation these optimizations are of the expected 
> revenue. However, neither of these mean that these miners choose to act in a 
> way that reduces their expected revenue -- specifically, if from a 
> non-myopic's miner perspective including Alice's immediate transaction is 
> better off than waiting for Bob's future transaction, then this is what they 
> do.
>
> Consequently, saying that "being myopic" dominates "being non-myopic" is 
> incorrect -- myopic is included in being non-myopic, thus cannot be better 
> than it.

The term "dominates" here is a technical term in game theory.

A strategy dominates over another strategy if, in a mixed environment, the 
first strategy always wins more points than the second strategy, no matter what 
proportion they may initially start in the mixed environment.

For example, in an environment of prisoner dilemma games, a tit-for-tat 
strategy dominates over the always-betray strategy, which dominates over 
always-cooperate strategy.

The above is the use of the term "dominate", and not that somehow one strategy 
"contains" the other.
Always-betray does not contain always-cooperate.

It is immaterial that the non-myopic "contains" myopic strategy as a 
sub-strategy.
Sometimes, overriding a sub-strategy can lead to worse outcomes and you are 
better off sticking to the sub-strategy rather than an extended strategy that 
sometimes overrides the sub-strategy

(notice how mixed teams of computer+human are no longer dominant in chess, 
because computer chess AIs are now so sophisticated that on average, the human 
overriding the computer strategy often leads to worse outcomes than just 
following the computer; yet about a decade ago such mixed computer+human teams 
were dominant over pure-computer and pure-human teams; yet you could say the 
same, that the computer+human "includes" the pure-computer strategy, but 
nowadays does ***not*** dominate it).

Or: worse is better.


What matters is, if you make them compete in an environment, myopic strategies 
will consistently beat non-myopic strategies because the myopic miners will 
impose costs on the non-myopic miners.


>
> So, the next issue to address is estimation of how much of the hash rate is 
> actually non-myopic. Currently that answer is simple -- probably 0. Bitcoin 
> Core (97% of the blocks) doesn't offer these optimizations, and most likely 
> other clients do not have these as well. But, we showed this is rather 
> trivial to implement (150 LoC in Bitcoin Core), and theoretically can be 
> included in Core's next version AFAIK. Moreover, any miner can simply apply 
> our patch independently, achieving the same effect.
>
> Please note more elaborate optimizations are in miners' best interest, 
> especially as mining incentives transition from block minting to fees -- the 
> latter are becoming the main income source, and I believe less sophisticated 
> miners will miss out substantially. You can check out Phil Daian's paper 
> about front-running in Ethereum for example: https://arxiv.org/abs/1904.05234

Yes, but again: myopic strategies dominate over non-myopic strategies, thus 
implementing non-myopic strategies is pointless, since they will lose revenue 
in an environment where even a single miner is myopic.

It is immaterial that it takes only 150 LoC to implement non-myopia: if it 
earns less money in an environment where even a minority of blocks are created 
by myopic miners (much less 97%), nobody will use the non-myopic strategy and 
they will remain at negligible near-0% hashrate.

As they say, "you can't get to there from here".


> As common in game-theory papers, our analysis does assume Common Knowledge -- 
> all participants know all other participants, their available strategies and 
> utilities (Tejaswi et al.'s paper makes the same assumption). As commented 
> before, true, this is not always the case -- nodes might have different 
> mempools, and some might not have applied the optimization patch and act 
> myopically. Such miners are therefore "resisting" the attack -- as stated, by 
> including Alice's transaction they ruin other miners' potential profit from 
> Bob's high fee transaction.

The only additional assumption you are missing is that miners care about 
*themselves* and not about *all miners*.

Non-myopia may earn more money for *all* miners if *all* miners use it, but if 
a *single* miner starts using myopic strategies in a non-myopic environment, 
they will earn more

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli via bitcoin-dev]

On Fri, Jul 3, 2020 at 12:17 PM ZmnSCPxj  wrote:

>
> > In fact, one rule of thumb might be that wherever watchtowers are
> required, a timelocked bribe might be possible.
>
> I think a better heuristic is that, if the logic of the construction
> assumes "transaction with earlier locktime supersedes transaction with
> later locktime", then it is timelocked-bribery-vulnerable.
>

That's true by definition. Timelocked bribes are, well, going to be
possible when there are timelocks. I was going more for an "indirect clue"
that wherever a watchtower is proposed, a timelocked bribe is possible.
This is entirely a pedantic point :-)
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj via bitcoin-dev]

Good morning Tejaswi,



> > But if an attack happens during a fee spike, then even though we retain our 
> > current default `to_self_delay` of 144, we still have the ability to 
> > gradually and automatically move to higher fee regions until our 
> > transaction confirms, and we have a good excuse for it to present to users: 
> > "a fee spike was happening at the time, so you had to pay some extra miner 
> > fees".
>
> Agree on the UX. There is a tradeoff between the timelocked value of the 
> channel balance to Alice during benign vs malicious abandonment by Bob. In 
> your opinion, increasing the fees beyond 1% (and thereby cutting into Alice's 
> share itself) is a slightly better tradeoff than increasing to_self_delay. 

Currently, we say `to_self_delay` is a parameter of how long you can be 
offline, and is imposed on your counterparty (so its effect on you is to allow 
the counterparty to safely be offline for that long).
This explanation seems palatable to users; they understand that it is the 
counterparty which is asking this of them, and that they ask a similar number 
of their counterparty, which is also their own protection.

On the other hand, we do not really expect to get beyond 1% unless we are under 
attack, *or* the fee spikes are really, really bad.
So this seems a practical tradeoff for us over in Lightning-land.


> > And since you and your paper openly discusses it anyway, I would like to 
> > reveal that the MAD-HTLC argument does not apply to *just* HTLCs.
>
> We know. Maybe we should have made it clear in the paper that when we use the 
> Poon-Dryja channel construction, we use the idea that the knowledge of the 
> preimage of a hash is equivalent to knowing the private key of the revocation 
> public key. In fact, this is how the Poon-Dryja construction is explained in 
> McCorry's Ph.D thesis, and IMHO is easier to understand than the original 
> description in the Poon-Dryja paper (or Bolt #3, for that matter). 

Yes, I realized it a little after reading MAD-HTLC that it applied to all the 
other known channel mechanisms as well, not just HTLCs, and decided to 
investigate this topic further, and have been circumspect regarding this.

> You could further argue that the hashlock is an incidental artefact, and our 
> paper mostly refers to timelocked transactions. And the rest of your email 
> describes applications of timelocked (and obviously presigned) transactions, 
> which are all vulnerable to the same bribing attack. Additionally, the 
> Wattehnofer in our paper is the same Wattenhofer from the Duplex Channel 
> paper.

Yes, I agree that the hashlock is an incidental artefact.

What MAD-HTLC questions is our assumption that a valid transaction with an 
earlier locktime supersedes a valid transaction spending the same txout with a 
later locktime.
Whether it involves presigned transactions or hashlocks are incidental 
artefacts.
So for example, a SCRIPT `OP_IF  OP_ELSE <1 day> OP_CHECKSEQUENCEVERIFY 
OP_DROP  OP_ENDIF OP_CHECKSIG` would also be vulnerable to the MAD-HTLC 
argument.

(Indeed, BOLT spec uses something very much like that script, now that I look 
at it again; in our case the `` is a combination of keys from both parties, 
that cannot be signed with unless one party knows both sub-keys.)

>
> > My current analysis suggests that in practice, the MAD-HTLC argument does 
> > not apply at all (else I would not be revealing that all channel mechanisms 
> > are broken **if** the MAD-HTLC argument *does* apply), since the myopic 
> > strategy seems to be pretty much inevitably dominant at stable states.
>
> We agree. 
>  
>
> > But it would still be best to investigate further until we are fully 
> > convinced that the MAD-HTLC argument ("'earlier supersedes later' might be 
> > falsified by bribery") does not apply.
>
> I think this is the analysis our paper does, and perhaps it's our mistake 
> that we do not set the context better. We only mention (and propose fixes 
> for) Poon-Dryja channel construction, and Tier Nolan's Atomic Swap 
> construction. 
>
> We could have addressed Spilman's one-way channels or Decker-Wattenhofer 
> duplex channels, but that would have been pointless as they were never going 
> to make it into production after Poon-Dryja and subsequently, Eltoo were 
> proposed.

I suggested that, until `SIGHASH_ANYPREVOUT` gets enabled, the 
Decker-Wattenhofer construction (removing the duplex Spilman-like channels at 
the end and leaving just the decrementing-`nSequence` constructions) could be 
used for Ruben Somsen StateChains, so you might not want to dismiss that so 
readily.

The decrementing-`nSequence` mechanisms have the advantage that it does not 
require a punishment/revocation branch, similar to Decker-Russell-Osuntokun 
"eltoo", and thus would work just as well to implement statechains, at least 
until all the debates around `SIGHASH_ANYPREVOUT` settle and it gets deployed.

Similarly, the proposed CoinPool as well could be implemente

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli via bitcoin-dev]

On Thu, Jul 2, 2020 at 6:06 PM ZmnSCPxj  wrote:

> At fee spikes, this x will go higher, and thus (f - x) / (b - x) will be
> far smaller than f / b and might even become negative, in which case the
> Alice transaction will not be confirmed even by myopic miners, because the
> Alice transaction will be below the top 4Mweight transactions in the
> mempool.
>

I agree. The MAD-HTLC authors actually keep the base fee in their
calculations, and we deliberately decided to ignore this. We believe that
this base fee to be much lower than the typical 1% channel balance, and it
actually doesn't change any of our results. This was brushed under the
"without loss of generality" rug. I admit that we should have made this
clear in our Assumptions section though. Point taken.


> But if an attack happens during a fee spike, then even though we retain
> our current default `to_self_delay` of 144, we still have the ability to
> gradually and automatically move to higher fee regions until our
> transaction confirms, and we have a good excuse for it to present to users:
> "a fee spike was happening at the time, so you had to pay some extra miner
> fees".
>

Agree on the UX. There is a tradeoff between the timelocked value of the
channel balance to Alice during benign vs malicious abandonment by Bob. In
your opinion, increasing the fees beyond 1% (and thereby cutting into
Alice's share itself) is a slightly better tradeoff than increasing
to_self_delay.


> And since you and your paper openly discusses it anyway, I would like to
> reveal that the MAD-HTLC argument does not apply to *just* HTLCs.
>

We know. Maybe we should have made it clear in the paper that when we use
the Poon-Dryja channel construction, we use the idea that the knowledge of
the preimage of a hash is equivalent to knowing the private key of the
revocation public key. In fact, this is how the Poon-Dryja construction is
explained in McCorry's Ph.D thesis
, and IMHO is easier to
understand than the original description in the Poon-Dryja paper (or Bolt
#3, for that matter).

You could further argue that the hashlock is an incidental artefact, and
our paper mostly refers to timelocked transactions. And the rest of your
email describes applications of timelocked (and obviously presigned)
transactions, which are all vulnerable to the same bribing attack.
Additionally, the Wattehnofer in our paper is the same Wattenhofer from the
Duplex Channel paper.

My current analysis suggests that in practice, the MAD-HTLC argument does
> not apply at all (else I would not be revealing that all channel mechanisms
> are broken **if** the MAD-HTLC argument *does* apply), since the myopic
> strategy seems to be pretty much inevitably dominant at stable states.
>

We agree.


> But it would still be best to investigate further until we are fully
> convinced that the MAD-HTLC argument ("'earlier supersedes later' might be
> falsified by bribery") does not apply.
>

I think this is the analysis our paper does, and perhaps it's our mistake
that we do not set the context better. We only mention (and propose fixes
for) Poon-Dryja channel construction, and Tier Nolan's Atomic Swap
construction.

We could have addressed Spilman's one-way channels or Decker-Wattenhofer
duplex channels, but that would have been pointless as they were never
going to make it into production after Poon-Dryja and subsequently, Eltoo
were proposed. But not addressing Eltoo in the paper is an omission that I
am a bit upset about. We additionally do not address more sophisticated
atomic swaps from Somsen or Fournier. Nor do we address Kanzure's vault
proposal. In fact, one rule of thumb might be that wherever watchtowers are
required, a timelocked bribe might be possible.

And again, thanks for the detailed analysis.

On Thu, Jul 2, 2020 at 6:06 PM ZmnSCPxj  wrote:

> Good morning Tejaswi,
>
> > > So it looks to me that scorched-earth is a possible mitigation against
> this attack.
> >
> > I don't follow this. We show that a reasonable value of fees and
> timelock are enough to avoid the attack. Why scorch the earth?
>
> Because your model only considers that a block might have only 0 or 1
> transactions, and there is no such thing as a mempool containing
> alternative, fee-paying transactions that the miner could include *instead*.
>
> In reality, what a miner can earn from adding Alice transaction is the
> *difference* between the Alice transaction fee and the transaction that
> *just* misses getting included in the block because of feerate.
>
> Thus, the f will not, in fact, *quite* be the Alice fee, but instead less
> than that.
>
> Indeed if the Alice transaction fee is lower than the top 4 Mweight
> transactions in the mempool, the miner would be *losing* funds by including
> the Alice transaction.
>
> My understanding is that we expect mempools to eventually never empty, as
> the block subsidy reduces over time, thus the payoff f for including the
> Alice

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj via bitcoin-dev]

Good morning Tejaswi,

> > So it looks to me that scorched-earth is a possible mitigation against this 
> > attack.
>
> I don't follow this. We show that a reasonable value of fees and timelock are 
> enough to avoid the attack. Why scorch the earth?

Because your model only considers that a block might have only 0 or 1 
transactions, and there is no such thing as a mempool containing alternative, 
fee-paying transactions that the miner could include *instead*.

In reality, what a miner can earn from adding Alice transaction is the 
*difference* between the Alice transaction fee and the transaction that *just* 
misses getting included in the block because of feerate.

Thus, the f will not, in fact, *quite* be the Alice fee, but instead less than 
that.

Indeed if the Alice transaction fee is lower than the top 4 Mweight 
transactions in the mempool, the miner would be *losing* funds by including the 
Alice transaction.

My understanding is that we expect mempools to eventually never empty, as the 
block subsidy reduces over time, thus the payoff f for including the Alice 
transaction *instead of* some other transaction will be less than the Alice fee.


This effect also holds for Bob, but we can probably expect, all things being 
equal, that approximately the same value will be deducted from both the Bob 
bribe and Alice fee by the mempool effect.
Thus the ratio should really be (f - x) / (b - x), where x is the 
fee-of-transaction-that-just-misses-the-block.
At fee spikes, this x will go higher, and thus (f - x) / (b - x) will be far 
smaller than f / b and might even become negative, in which case the Alice 
transaction will not be confirmed even by myopic miners, because the Alice 
transaction will be below the top 4Mweight transactions in the mempool.


So it seems to me reasonable to use a *gradual* scorched earth policy, as it is 
not only resilient against this attack, but also to fee spikes.
Alice starts at the 1% reserve, then for every block that goes by, bumps up the 
fee.
Then Alice will settle at an (f - x) / (b - x) level that achieves the least 
weak miner that is known to run the myopic strategy.


I believe this is also better for UX --- people already accept that during high 
fee spikes, they end up paying more for onchain activities.
But boosting up `to_self_delay` is bad because it makes honest unilateral 
closes take longer, and we already get frownie faces from users about this 
parameter.
By using a gradual scorched-earth strategy we can start at the reserve level, 
and if we are not under attack and there is no fee spike, do not lose anything 
other than the reserve funds of the thief (which is not ours, but is instead 
that of the thief).
But if an attack happens during a fee spike, then even though we retain our 
current default `to_self_delay` of 144, we still have the ability to gradually 
and automatically move to higher fee regions until our transaction confirms, 
and we have a good excuse for it to present to users: "a fee spike was 
happening at the time, so you had to pay some extra miner fees".




And since you and your paper openly discusses it anyway, I would like to reveal 
that the MAD-HTLC argument does not apply to *just* HTLCs.
You make recommendations about `to_self_delay` and `channel_reserve_satoshis`, 
which are not parameters of Lightning HTLCs (those are stuff like `cltv_delta` 
and `final_cltv`), but are channel parameters.

The MAD-HTLC argument applies just as well to channel mechanisms themselves, 
***independently of*** any HTLCs they transport.

The MAD-HTLC paper has the following core argument:

* We currently assume that currently-valid transactions will inevitably 
supersede alternate transactions that are valid at a later block height, simply 
because of the time advantage.
  * However, the owner of a later-block-height transaction can bribe miners to 
defer confirmation of currently-valid transactions, until its 
later-block-height transaction is valid and confirms.

The above core argument is presented as applying to HTLCs.

However, the same argument actually **also** applies to all current offchain 
multiparticipant cryptocurrency systems (i.e. "channel mechanisms").

* Spilman
* Poon-Dryja (what we currently use in Lightning)
* Decker-Wattenhofer decrementing-`nSequence`
* Decker-Russell-Osuntokun

The [Khabbazian-Nadahalli-Wattenhofer "Timelocked Bribing" 
paper](https://eprint.iacr.org/2020/774.pdf) mentions the use of revoked 
transactions in a Poon-Dryja mechanism, but seems to imply that the issue is 
with the HTLC instantiated inside the revoked transaction.
But note that the paper describes recommendations for the `to_self_delay` 
parameter and also analyzes the `channel_reserve_satoshis` parameter, which are 
parameters of the ***Poon-Dryja*** mechanism, and **not** of the HTLCs 
instantiated inside it.

So, to be very clear, the MAD-HTLC argument applies to all the above mechanisms 
*even if HTLCs are not used at all*.
Or put anot

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli via bitcoin-dev]

On Wed, Jul 1, 2020 at 6:58 PM ZmnSCPxj  wrote:

> And your paper posits that if a miner is weak, its best strategy is to
> take the myopic strategy and include the currently-valid Alice transaction.
>

Yes. The proof is quite trivial and follows from the definition of weak: if
the myopic miner's hashpower percentage is p_i, and it's lower than f/b,
that means that f > b*p_i. By including the currently-valid Alice
transaction, the myopic miner could make f, which is higher than their
expected gain, which is b*p_i. The myopic miner has a p_i chance of mining
the first block when Bob's transaction becomes valid, and it's most likely
to stay valid for just 1 block, as every miner would want that immediately
when it gets valid. This is where we disagree with the MAD-HTLC paper. They
assume that there are not any miners with sub-1% hashrate around. We find
that there are many such miners, and with channel_reserve_satoshi set to 1%
of the channel value, Alice can bump her fees to at least 1% of the channel
value without worry (because she will get Bob's channel_reserve_satoshi's
for herself if Bob is cheating by releasing a previous commitment TXN).

We additionally also show that when strong miners know that weak miners are
around, some of their strategies get dominated as well, and they will be
forced to include Alice's transaction as well. This, if there is just one
*known* weak miner, things are good for Alice. As an FYI, in our paper
Alice is the cheater and Bob is the victim. There were reasons to "reverse
the convention", so to speak - but that's for another day :-)


>
> Thus, if Alice even *matches* Bob, it seems to me that this ratio f / b is
> 1.0 implying a miner can only be powerful if it has already 51%-attacked
> Bitcoin (which tends to invalidate all our security assumptions of
> higher-layer protocols anyway, since a 51% attacker can censor anything
> with impunity).
>

We assume that Bob will bribe with the entire channel value - because he
has received commensurate goods and services off-chain. So, Alice will find
it difficult to match Bob's bribe, but she doesn't have to.


>
> Of course, Bob can offer up to the entire fund amount, for free, to miners
> as a bribe, without loss to Bob.
>

Yes. Precisely.


>
> For more realistic scenarios where no miner has 100% hashrate, then Alice
> can make all miners weak by being willing to pay up to 50% of the fund as
> fee, as a miner that achieves greater than 50% hashrate share would already
> effectively pwnzored Bitcoin and gained UNLIMITED POWAH anyway.
>

But she doesn't have to go as far as 50%. Just 1% seems quite reasonable,
given a reasonable timelock. We have a closed form solution for the
timelock T as well. In Lightning's case, with 1% channel_reserve_satoshis
around, we arrive at T = 316, which is much longer than the current default
of 144.


>
> So it looks to me that scorched-earth is a possible mitigation against
> this attack.
>

I don't follow this. We show that a reasonable value of fees and timelock
are enough to avoid the attack. Why scorch the earth?
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli via bitcoin-dev]

On Wed, Jul 1, 2020 at 6:58 PM ZmnSCPxj  wrote:

> Another analysis, similar but a little off-tangent to yours, would be to
> consider miners as a breeding group with various strategies, and see which
> one is able to gain more utilons (with which it creates more miners) and
> outbreed the other miners.
>
> This models the fact that miners can use their earnings to reinvest into
> their mining operations and increase their mining hashrate, and the amount
> they can reinvest is proportional to their earnings.
> A miner that "gives birth" to a child miner with the same strategy is, in
> the so-called "real world", simply a miner that has earned enough and
> reinvested those earnings to double the hashrate of their business (which,
> logically speaking, would use the same strategy throughout the entire
> business).
>
> Let us start with a population of 4 miners, 3 of which follow the
> non-myopic strategy, and the remaining following the myopic strategy.
> Let us postulate that all miners have the same unit hashrate.
> Thus, this starting population is 75% non-myopic, 25% myopic.
>
> If there exists a timelocked bribe, then if non-myopic miner is chosen at
> a block, it will have to sacrifice the Alice fee minus whatever lesser
> transaction fee it can replace in its block.
> If the Alice transaction is successfully delayed until the Bob transaction
> is valid, then the non-myopic miners can get the Bob transaction confirmed.
>
> However, even in the case that the Alice transaction is delayed, the
> myopic miner still has its 25% chance --- equal to the 25% chance of the
> three non-myopic miners --- to confirm the Bob transaction and earn the
> increased bribe that Bob offers.
>
> Thus, the non-myopic miners can end up sacrificing fee earnings, and in
> the end the myopic miner still has the 25% chance to get the Bob
> transaction fee later when it becomes valid.
> So the non-myopic miners do not impose any loss on myopic miners.
>
> On the other hand, if the non-myopic miners sacrificed their chances to
> include the Alice transaction in the hope of getting the later 25% chance
> to get the Bob higher-fee timelocked transaction, and then the myopic miner
> gets the next block, the myopic miner gets the Alice transaction confirmed
> and the 25% chance to get the Bob higher fee is lost by the non-myopic
> miners.
> Thus, the myopic miner is able to impose costs on their non-myopic
> competitors.
>
> So even if by chance for the entire locktime, only the non-myopic miners
> are selected, the myopic miner still retains its 25% chance of getting the
> block at locktime + 1 and confirming and earning the bigger Bob fee.
>
> Thus, we expect that the myopic miner will earn more than 25% of subsidies
> and fees than the non-myopic miners, in such a mixed environment.
>

This is exactly our analysis, and is covered in section 2.5 of our paper.
We formalize the ideas a bit more, and are able to relate the values of
Alice-fee, Bob-bribe, timelock, and miner's hashpower percentage. We go a
bit further into #reckless territory as well - reducing the timelock value
to super low values. That's in Algorithm #1 of our paper, and is a bit more
involved.


>
> We can then consider that the myopic miner, being able to earn more, is
> able to increase its progeny (i.e. expand its mining business and inspire
> new miners to follow its strategy towards success) faster than the
> non-myopic miners.
>
> We can thus conclude that the myopic miners will eventually dominate over
> the breeding population and drive the non-myopic miners to near-extinction.
>

This is an interesting direction that we chose to not look at. Like the
MAD-HTLC authors, we assume a constant hash-rate distribution across time,
which is obviously not a great assumption. It might work in the local
context of an HTLC's timelock, but in our approach, we are also interested
in *weak* miners, and finding them across 1000's of blocks might get tricky.


> It is helpful to remember that rationality is about success *in the
> universe you exist in*.
> While miners may step back and consider that, ***if*** all of them were to
> use non-myopic strategy, they would all earn more, the fact of the matter
> is that each miner works for themselves, and themselves alone, in a highly
> competitive environment.
> Thus, even though they know *all of them* will benefit if they use the
> non-myopic strategy, they cannot be sure, unless they are all perfectly
> synchronized mind-clones of each other, that the other miners will rather
> be selfish and mine for themselves, even if in the end every miner earns
> less
> The standard for success is to earn more *than your competitors*, not
> ensure that *every* miner earns more.
>
> Fortunately, since miners are running a business, this competition leads
> to better services to the the customers of the mining business, a known
> phenomenon of the free market, yay free market greed is good.
> The user Alice is a customer of the mining bus

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj via bitcoin-dev]

Good morning Tejaswi,

> Hello ZmnSCPxj (as there would be no better way to start an email to you :-),
>
> I posted a reply to Dave in the other sub-thread of this main thread. We have 
> a paper about something similar to what you have said - where we look at 
> "weak" and "strong" miners, and how even if there are a few weak miners, they 
> have a dominating strategy, etc. 
>

By my reading, it seems to me that you divide miners into "weak" and "powerful".
Weak miners have lower hashrate than powerful ones.
The dividing point depends on how much Alice and Bob fees are.
If the hashrate share of a miner is less than the ratio of Alice (honest) fee 
to Bob (bribing) fee, then the miner is weak.

And your paper posits that if a miner is weak, its best strategy is to take the 
myopic strategy and include the currently-valid Alice transaction.

Thus, if Alice even *matches* Bob, it seems to me that this ratio f / b is 1.0 
implying a miner can only be powerful if it has already 51%-attacked Bitcoin 
(which tends to invalidate all our security assumptions of higher-layer 
protocols anyway, since a 51% attacker can censor anything with impunity).

Of course, Bob can offer up to the entire fund amount, for free, to miners as a 
bribe, without loss to Bob.

For more realistic scenarios where no miner has 100% hashrate, then Alice can 
make all miners weak by being willing to pay up to 50% of the fund as fee, as a 
miner that achieves greater than 50% hashrate share would already effectively 
pwnzored Bitcoin and gained UNLIMITED POWAH anyway.

So it looks to me that scorched-earth is a possible mitigation against this 
attack.

--

Another analysis, similar but a little off-tangent to yours, would be to 
consider miners as a breeding group with various strategies, and see which one 
is able to gain more utilons (with which it creates more miners) and outbreed 
the other miners.

This models the fact that miners can use their earnings to reinvest into their 
mining operations and increase their mining hashrate, and the amount they can 
reinvest is proportional to their earnings.
A miner that "gives birth" to a child miner with the same strategy is, in the 
so-called "real world", simply a miner that has earned enough and reinvested 
those earnings to double the hashrate of their business (which, logically 
speaking, would use the same strategy throughout the entire business).

Let us start with a population of 4 miners, 3 of which follow the non-myopic 
strategy, and the remaining following the myopic strategy.
Let us postulate that all miners have the same unit hashrate.
Thus, this starting population is 75% non-myopic, 25% myopic.

If there exists a timelocked bribe, then if non-myopic miner is chosen at a 
block, it will have to sacrifice the Alice fee minus whatever lesser 
transaction fee it can replace in its block.
If the Alice transaction is successfully delayed until the Bob transaction is 
valid, then the non-myopic miners can get the Bob transaction confirmed.

However, even in the case that the Alice transaction is delayed, the myopic 
miner still has its 25% chance --- equal to the 25% chance of the three 
non-myopic miners --- to confirm the Bob transaction and earn the increased 
bribe that Bob offers.

Thus, the non-myopic miners can end up sacrificing fee earnings, and in the end 
the myopic miner still has the 25% chance to get the Bob transaction fee later 
when it becomes valid.
So the non-myopic miners do not impose any loss on myopic miners.

On the other hand, if the non-myopic miners sacrificed their chances to include 
the Alice transaction in the hope of getting the later 25% chance to get the 
Bob higher-fee timelocked transaction, and then the myopic miner gets the next 
block, the myopic miner gets the Alice transaction confirmed and the 25% chance 
to get the Bob higher fee is lost by the non-myopic miners.
Thus, the myopic miner is able to impose costs on their non-myopic competitors.

So even if by chance for the entire locktime, only the non-myopic miners are 
selected, the myopic miner still retains its 25% chance of getting the block at 
locktime + 1 and confirming and earning the bigger Bob fee.

Thus, we expect that the myopic miner will earn more than 25% of subsidies and 
fees than the non-myopic miners, in such a mixed environment.

We can then consider that the myopic miner, being able to earn more, is able to 
increase its progeny (i.e. expand its mining business and inspire new miners to 
follow its strategy towards success) faster than the non-myopic miners.

We can thus conclude that the myopic miners will eventually dominate over the 
breeding population and drive the non-myopic miners to near-extinction.

It is helpful to remember that rationality is about success *in the universe 
you exist in*.
While miners may step back and consider that, ***if*** all of them were to use 
non-myopic strategy, they would all earn more, the fact of the matter is that 
each miner works

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli via bitcoin-dev]

Hello ZmnSCPxj (as there would be no better way to start an email to you
:-),

I posted a reply to Dave in the other sub-thread of this main thread. We
have a paper about something similar to what you have said - where we look
at "weak" and "strong" miners, and how even if there are a few weak miners,
they have a dominating strategy, etc.

On Mon, Jun 29, 2020 at 8:05 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Dave, et al.,
>
>
> > >  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.)
>
> A thought occurs to me, that we should not be so hasty to call non-myopic
> strategy "rational".
> Let us consider instead "myopic" and "non-myopic" strategies in a
> population of miners.
>
> I contend that in a mixed population of "myopic" and "non-myopic" miners,
> the myopic strategy is dominant in the game-theoretic sense, i.e. it might
> earn less if all miners were myopic, but if most miners were non-myopic and
> a small sub-population were myopic and there was no easy way for non-myopic
> miners to punish myopic miners, then the myopic miners will end up earning
> more (at the expense of the non-myopic miners) and dominate over non-myopic
> miners.
> Such dominant result should prevent non-myopic miners from arising in the
> first place.
>
> The dominance results from the fact that by accepting the Alice
> transaction, myopic miners are effectively deducting the fees earned by
> non-myopic miners by preventing the Bob transaction from being confirmable.
> On the other hand, even if the non-myopic miners successfully defer the
> Alice transaction, the myopic miner still has a chance equal to its
> hashrate of getting the Bob transaction and its attached fee.
> Thus, myopic miners impose costs on their non-myopic competitors that
> non-myopic miners cannot impose their myopic competitors.
> If even one myopic miner successfully gets the Alice transaction
> confirmed, all the non-myopic miners lose out on the Bob bribe fee.
>
> So I think the myopic strategy will be dominant and non-myopic miners will
> not arise in the first place.
>
>
> Regards,
> ZmnSCPxj
> ___

Re: [bitcoin-dev] MAD-HTLC

[Stanga via bitcoin-dev]

Hi ZmnSCPxj,

That's a good point. Basically there are two extremes, if everyone is
non-myoptic (rational), they should wait even for a small fee (our mad-htlc
result), and if everyone else is myopic (rational), a non-myopic miner
should only wait for a fairly large fee, depending on miner sizes and the
timeout -- this is analyzed in an earlier paper by Winzer, Herd and Faust
[1]. In a mixed situation the calculation becomes slightly more involved,
but qualitatively it's closer to the Wizner et al. result, namely the bribe
should grow exponentially with the timeout, which is bad for the attacker.
But mad-htlc avoids myopic assumptions, allowing you to keep your contracts
safe either way.

Best,
Ittay

[1] F. Winzer, B. Herd and S. Faust, "Temporary Censorship Attacks in the
Presence of Rational Miners
," *2019 IEEE
European Symposium on Security and Privacy Workshops (EuroS&PW)*,
Stockholm, Sweden, 2019, pp. 357-366, doi: 10.1109/EuroSPW.2019.00046.

On Mon, Jun 29, 2020 at 9:05 PM ZmnSCPxj  wrote:

> Good morning Dave, et al.,
>
>
> > >  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.)
>
> A thought occurs to me, that we should not be so hasty to call non-myopic
> strategy "rational".
> Let us consider instead "myopic" and "non-myopic" strategies in a
> population of miners.
>
> I contend that in a mixed population of "myopic" and "non-myopic" miners,
> the myopic strategy is dominant in the game-theoretic sense, i.e. it might
> earn less if all miners were myopic, but if most miners were non-myopic and
> a small sub-population were myopic and there was no easy way for non-myopic
> miners to punish myopic miners, then the myopic miners will end up earning
> more (at the expense of the non-myopic miners) and dominate over non-myopic
> miners.
> Such dominant result should prevent non-myopic miners from arising in the
> first place.
>
> The dominance results from the fact that by accepting the Alice
> transaction, myopic miners are effectively deducting the fees earned by
> non-myopic miners by preventing the Bob transaction from being confirmable.
> On the other hand, even if the non-myopi

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj via bitcoin-dev]

Good morning Dave, et al.,


> >  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.)

A thought occurs to me, that we should not be so hasty to call non-myopic 
strategy "rational".
Let us consider instead "myopic" and "non-myopic" strategies in a population of 
miners.

I contend that in a mixed population of "myopic" and "non-myopic" miners, the 
myopic strategy is dominant in the game-theoretic sense, i.e. it might earn 
less if all miners were myopic, but if most miners were non-myopic and a small 
sub-population were myopic and there was no easy way for non-myopic miners to 
punish myopic miners, then the myopic miners will end up earning more (at the 
expense of the non-myopic miners) and dominate over non-myopic miners.
Such dominant result should prevent non-myopic miners from arising in the first 
place.

The dominance results from the fact that by accepting the Alice transaction, 
myopic miners are effectively deducting the fees earned by non-myopic miners by 
preventing the Bob transaction from being confirmable.
On the other hand, even if the non-myopic miners successfully defer the Alice 
transaction, the myopic miner still has a chance equal to its hashrate of 
getting the Bob transaction and its attached fee.
Thus, myopic miners impose costs on their non-myopic competitors that 
non-myopic miners cannot impose their myopic competitors.
If even one myopic miner successfully gets the Alice transaction confirmed, all 
the non-myopic miners lose out on the Bob bribe fee.

So I think the myopic strategy will be dominant and non-myopic miners will not 
arise in the first place.


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

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli via bitcoin-dev]

On Sun, Jun 28, 2020 at 2:16 PM David A. Harding via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> 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).
>

We were separately working on a similar problem, and wrote a paper as well:
https://eprint.iacr.org/2020/774 *

We look at the Alice's-Fees/Bob's-Bribe ratio. We also look at "strong" and
"weak" miners in this context. If a miner is weak, their hash-rate is lower
than this fees/bribe ratio. If they are strong, their hash rate is more
than this fees/bribe ratio. In this setting, it turns out that if there are
only strong miners, Bob will win. If there is at least one weak miner,
Alice has to win, given a reasonable timeout value. We found it awesome
that lightning has a parameter called "channel-reserve_satoshis", which
directly helps in countering this bribe by giving Alice some leeway in fees.

* Ph.D students want to write papers, unfortunately.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] MAD-HTLC

[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

[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 

Re: [bitcoin-dev] MAD-HTLC

[Bastien TEINTURIER via bitcoin-dev]

Good morning list,

This is an interesting and simple idea, thanks for sharing this paper!

However I think there are a couple of important issues (but it could be me
misunderstanding):

* the assumption that the mempool is a shared resource is flawed: it's
entirely possible
  to have very different mempools in different areas of the network, for a
potentially long
  period of time (see the RBF pinning thread [1]), and an attacker can
leverage this fact
* a corollary is that Bob may not know that Alice has published her
transaction, and will
  end up publishing his timeout tx, unknowingly giving the two preimages to
the miners
* a corollary of that is a very unhealthy incentive to miners, when they
receive an HTLC
  success tx, to always wait for the timeout before confirming the
transaction, in hope that
  they'll receive the second preimage and will be able to claim the funds
for themselves
  (whereas currently they don't gain anything by waiting before confirming
these txs)

To be fair the paper states that it doesn't address issues of malicious
miners or an attacker
colluding with a miner, but I think that even honest miners now have an
unhealthy incentive
regarding htlc success confirmation.

Let me know if I misunderstood something, or if you have ideas on how to
explore that
threat model in the future.

Cheers,
Bastien

[1]
https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-April/002639.html



Le jeu. 25 juin 2020 à 14:45, Nadav Ivgi via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> a écrit :

> Hi ZmnSCPxj,
>
> You are of course correct. I had considered the effect of reorgs, but the
> email seemed to be getting too lengthy to mention that too.
>
> You would need a few spare blocks in which Bob won't be accused of bribery
> as a safety margin, which does reduce the time frame in which Alice can get
> her transaction confirmed in order to have a valid bribery fraud. This
> seems workable if the time frame was long enough (over a few hours should
> be sufficient, assuming we consider reorgs of over 3-4 blocks to be
> unlikely), but could indeed be problematic if the time frame is already
> short to begin with.
>
> Nadav
>
> On Thu, Jun 25, 2020 at 7:04 AM ZmnSCPxj  wrote:
>
>> Good morning Nadav,
>>
>> > > I and some number of Lightning devs consider this to be sufficient
>> disincentive to Bob not attacking in the first place.
>> >
>> > An additional disincentive could be introduced in the form of bribery
>> proofs for failed attempts.
>> >
>> > If we assume that "honest" users of the LN protocol won't reveal their
>> timelocked transactions before reaching the timelock expiry (they shouldn't
>> anyway because standard full node implementations won't relay them), we can
>> prove that Bob attempted bribery and failed to an outside observer by
>> showing Bob's signed timelocked transaction, spending an output that was in
>> reality spent by a different transaction prior to the locktime expiry,
>> which should not be possible if Bob had waited.
>>
>>
>> Unfortunately this could be subject to an inversion of this attack.
>>
>> Alice can wait for the timelock to expire, then bribe miners to prevent
>> confirmation of the Bob timelocked transaction, getting the Alice
>> hashlocked transaction confirmed.
>>
>> Now of course you do mention "prior to the locktime expiry" but there is
>> now risk at around locktime.
>>
>> Particularly, "natural" orphaned blocks and short-term chainsplits can
>> exist.
>> Bob might see that the locktime has arrived and broadcast the signed
>> timelocked transaction, then Alice sees the locktime has not yet arrived
>> (due to short-term chainsplits/propagation delays) and broadcast the signed
>> hashlocked transaction, then in the end the Alice side of the short-term
>> chainsplit is what solidifies into reality due to random chance on which
>> miner wins which block.
>> Then Bob can now be accused of bribery, even though it acted innocently;
>> it broadcasted the timelock branch due to a natural chainsplit but Alice
>> hashlocked branch got confirmed.
>>
>> Additional complications can be added on top to help mitigate this edge
>> case but more complex == worse in general.
>> For example it could "prior to locktime expiry" can ignore a few blocks
>> before the actual timelock, but this might allow Bob to mount the attack by
>> initiating its bribery behavior earlier by those few blocks.
>>
>> Finally, serious attackers would just use new pseudonyms, the important
>> thing is to make pseudonyms valuable and costly to lose, so it is
>> considered sufficient that LN nodes need to have some commitment to the LN
>> in the form of actual channels (which are valuable, potentially
>> money-earning constructs, and costly to set up).
>>
>> Other HTLC-using systems, such as the "SwapMarket" being proposed by
>> Chris Belcher, could use similar disincentivizing; I know Chris is planning
>> a fidelity bond system for SwapMarket makers, for example, which would
>> mimic 

Re: [bitcoin-dev] MAD-HTLC

[Nadav Ivgi via bitcoin-dev]

Hi ZmnSCPxj,

You are of course correct. I had considered the effect of reorgs, but the
email seemed to be getting too lengthy to mention that too.

You would need a few spare blocks in which Bob won't be accused of bribery
as a safety margin, which does reduce the time frame in which Alice can get
her transaction confirmed in order to have a valid bribery fraud. This
seems workable if the time frame was long enough (over a few hours should
be sufficient, assuming we consider reorgs of over 3-4 blocks to be
unlikely), but could indeed be problematic if the time frame is already
short to begin with.

Nadav

On Thu, Jun 25, 2020 at 7:04 AM ZmnSCPxj  wrote:

> Good morning Nadav,
>
> > > I and some number of Lightning devs consider this to be sufficient
> disincentive to Bob not attacking in the first place.
> >
> > An additional disincentive could be introduced in the form of bribery
> proofs for failed attempts.
> >
> > If we assume that "honest" users of the LN protocol won't reveal their
> timelocked transactions before reaching the timelock expiry (they shouldn't
> anyway because standard full node implementations won't relay them), we can
> prove that Bob attempted bribery and failed to an outside observer by
> showing Bob's signed timelocked transaction, spending an output that was in
> reality spent by a different transaction prior to the locktime expiry,
> which should not be possible if Bob had waited.
>
>
> Unfortunately this could be subject to an inversion of this attack.
>
> Alice can wait for the timelock to expire, then bribe miners to prevent
> confirmation of the Bob timelocked transaction, getting the Alice
> hashlocked transaction confirmed.
>
> Now of course you do mention "prior to the locktime expiry" but there is
> now risk at around locktime.
>
> Particularly, "natural" orphaned blocks and short-term chainsplits can
> exist.
> Bob might see that the locktime has arrived and broadcast the signed
> timelocked transaction, then Alice sees the locktime has not yet arrived
> (due to short-term chainsplits/propagation delays) and broadcast the signed
> hashlocked transaction, then in the end the Alice side of the short-term
> chainsplit is what solidifies into reality due to random chance on which
> miner wins which block.
> Then Bob can now be accused of bribery, even though it acted innocently;
> it broadcasted the timelock branch due to a natural chainsplit but Alice
> hashlocked branch got confirmed.
>
> Additional complications can be added on top to help mitigate this edge
> case but more complex == worse in general.
> For example it could "prior to locktime expiry" can ignore a few blocks
> before the actual timelock, but this might allow Bob to mount the attack by
> initiating its bribery behavior earlier by those few blocks.
>
> Finally, serious attackers would just use new pseudonyms, the important
> thing is to make pseudonyms valuable and costly to lose, so it is
> considered sufficient that LN nodes need to have some commitment to the LN
> in the form of actual channels (which are valuable, potentially
> money-earning constructs, and costly to set up).
>
> Other HTLC-using systems, such as the "SwapMarket" being proposed by Chris
> Belcher, could use similar disincentivizing; I know Chris is planning a
> fidelity bond system for SwapMarket makers, for example, which would mimic
> the properties of LN channels (costly to set up, money-earning).
>
> Regards,
> ZmnSCPxj
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] MAD-HTLC

[Nadav Ivgi via bitcoin-dev]

> I and some number of Lightning devs consider this to be sufficient
disincentive to Bob not attacking in the first place.

An additional disincentive could be introduced in the form of bribery
proofs for failed attempts.

If we assume that "honest" users of the LN protocol won't reveal their
timelocked transactions before reaching the timelock expiry (they shouldn't
anyway because standard full node implementations won't relay them), we can
prove that Bob attempted bribery and failed to an outside observer by
showing Bob's signed timelocked transaction, spending an output that was in
reality spent by a different transaction prior to the locktime expiry,
which should not be possible if Bob had waited.

These proofs would be gossiped, and lightning network participants could
choose not to peer with Bob when they see them. This might require some
sort of a scoring/reputation scheme that makes it harder for Bob to attack
with new throw-away identities to be effective. (i.e. limiting your
exposure to peers to some BTC amount based on their historical public
channels records, using fidelity bonds, etc.)

Bob could still send these bribery transactions privately to selected
miners, but not making them public would greatly reduce the participating
miners' confidence that there is enough participating hashpower for the
attack to be profitable.

Nadav

On Thu, Jun 25, 2020 at 4:38 AM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Stanga et al,
>
>
> > > Hi ZmnSCPxj,
> > >
> > > Thank you for taking the time to respond, these are very good points.
> Responses inline.
> > >
> > > On Tue, Jun 23, 2020 at 12:48 PM ZmnSCPxj 
> wrote:
> > >
> > > > Good morning Itay, Ittay, and Matan,
> > > >
> > > > I believe an unstated assumption in Bitcoin is that miners are
> short-sighted.
> > > >
> > > > The reasoning for this assumption is:
> > > >
> > > > * Deployment of new mining hardware controlled by others may occur
> at any time you do not control.
> > > >   * Thus, any transactions you leave on the table are potentially
> taken by somebody else and not by you.
> > > >   * Sudden changes in hashpower distribution may reduce your
> expected future earnings, so any future theoretical earnings should be
> discounted (*in addition to* expected return-on-investment on getting money
> you can invest *now*).
> > >
> > > Our analysis assumes constant difficulty, i.e., no significant changes
> of the miners set. Indeed, hash-rate changes typically occur at a much
> larger granularity than your average HTLC timeout. For instance, we noticed
> plenty of lightning nodes use timeouts of a day. So, we do not consider
> optimization at infinity, just a day ahead, and within this time frame all
> the factors you mentioned are not expected to dramatically change.
> > >
> > > That being said, it would be interesting to analyze the effect of
> miners joining during the HTLC duration. Intuitively, this shouldn’t affect
> the results, as those new miners have the same incentive to wait for the
> higher-paying tx.
>
> We already know that hashrate tends to trend upwards, and that we do not
> expect hashrate to fall except for occasional transients.
>
> The expectation is not that new miners have different incentives.
> Instead, the expectation is that current miners discount future possible
> gains because in the future, they expect to have less hashrate share than
> right now.
>
> The only trustless way for Bob to bribe miners into deferring Alice tx is
> to attach the bribe to the future confirmation of the Bob tx, thus Bob is
> offering future-coins, not present-coins like Alice can offer, and the fact
> that miners expect an overall uptrend in total hashrate (leading to an
> overall downtrend in their hashrate share) means that miners discount the
> Bob offered future-coins.
> The discounting is proportional to the time delay involved, as a larger
> delay implies greater reduction in hashrate share.
>
> This discounting is, again, *in addition to* natural discounting a.k.a. "I
> will gladly pay you Thursday for a hamburger today", the hamburger seller
> will want some pretty stiff assurances plus a bigger payment on Thursday
> for giving you a hamburger today, due to expected returns on investment.
>
>
> > >
> > >
> > > > It also strikes me that, in a world with RBF and CPFP, the same
> endpoint (i.e. miners earn the entire fund of the HTLC) is achieved by
> existing HTLCs, without the additional branch and script opcodes needed by
> MAD-HTLC.
> > > > For example, if an HTLC is confirmed but the hashlock-claiming
> transaction is not being confirmed (because miners are holding it up
> because Bob is offering a much higher fee in the future for the
> timelock-claiming transaction), then Alice can, regardless of the reason
> why it is not being confirmed, bump up the fee with RBF or CPFP.
> > > >
> > > > If the fee bump offered by Alice is sufficiently large, then miners
> will start re-preferring the

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj via bitcoin-dev]

Good morning Nadav,

> > I and some number of Lightning devs consider this to be sufficient 
> > disincentive to Bob not attacking in the first place.
>
> An additional disincentive could be introduced in the form of bribery proofs 
> for failed attempts.
>
> If we assume that "honest" users of the LN protocol won't reveal their 
> timelocked transactions before reaching the timelock expiry (they shouldn't 
> anyway because standard full node implementations won't relay them), we can 
> prove that Bob attempted bribery and failed to an outside observer by showing 
> Bob's signed timelocked transaction, spending an output that was in reality 
> spent by a different transaction prior to the locktime expiry, which should 
> not be possible if Bob had waited.


Unfortunately this could be subject to an inversion of this attack.

Alice can wait for the timelock to expire, then bribe miners to prevent 
confirmation of the Bob timelocked transaction, getting the Alice hashlocked 
transaction confirmed.

Now of course you do mention "prior to the locktime expiry" but there is now 
risk at around locktime.

Particularly, "natural" orphaned blocks and short-term chainsplits can exist.
Bob might see that the locktime has arrived and broadcast the signed timelocked 
transaction, then Alice sees the locktime has not yet arrived (due to 
short-term chainsplits/propagation delays) and broadcast the signed hashlocked 
transaction, then in the end the Alice side of the short-term chainsplit is 
what solidifies into reality due to random chance on which miner wins which 
block.
Then Bob can now be accused of bribery, even though it acted innocently; it 
broadcasted the timelock branch due to a natural chainsplit but Alice 
hashlocked branch got confirmed.

Additional complications can be added on top to help mitigate this edge case 
but more complex == worse in general.
For example it could "prior to locktime expiry" can ignore a few blocks before 
the actual timelock, but this might allow Bob to mount the attack by initiating 
its bribery behavior earlier by those few blocks.

Finally, serious attackers would just use new pseudonyms, the important thing 
is to make pseudonyms valuable and costly to lose, so it is considered 
sufficient that LN nodes need to have some commitment to the LN in the form of 
actual channels (which are valuable, potentially money-earning constructs, and 
costly to set up).

Other HTLC-using systems, such as the "SwapMarket" being proposed by Chris 
Belcher, could use similar disincentivizing; I know Chris is planning a 
fidelity bond system for SwapMarket makers, for example, which would mimic the 
properties of LN channels (costly to set up, money-earning).

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

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj via bitcoin-dev]

Good morning Stanga et al,


> > Hi ZmnSCPxj, 
> >
> > Thank you for taking the time to respond, these are very good points. 
> > Responses inline.
> >
> > On Tue, Jun 23, 2020 at 12:48 PM ZmnSCPxj  wrote:
> >
> > > Good morning Itay, Ittay, and Matan,
> > >
> > > I believe an unstated assumption in Bitcoin is that miners are 
> > > short-sighted.
> > >
> > > The reasoning for this assumption is:
> > >
> > > * Deployment of new mining hardware controlled by others may occur at any 
> > > time you do not control.
> > >   * Thus, any transactions you leave on the table are potentially taken 
> > > by somebody else and not by you.
> > >   * Sudden changes in hashpower distribution may reduce your expected 
> > > future earnings, so any future theoretical earnings should be discounted 
> > > (*in addition to* expected return-on-investment on getting money you can 
> > > invest *now*).
> >
> > Our analysis assumes constant difficulty, i.e., no significant changes of 
> > the miners set. Indeed, hash-rate changes typically occur at a much larger 
> > granularity than your average HTLC timeout. For instance, we noticed plenty 
> > of lightning nodes use timeouts of a day. So, we do not consider 
> > optimization at infinity, just a day ahead, and within this time frame all 
> > the factors you mentioned are not expected to dramatically change. 
> >
> > That being said, it would be interesting to analyze the effect of miners 
> > joining during the HTLC duration. Intuitively, this shouldn’t affect the 
> > results, as those new miners have the same incentive to wait for the 
> > higher-paying tx.

We already know that hashrate tends to trend upwards, and that we do not expect 
hashrate to fall except for occasional transients.

The expectation is not that new miners have different incentives.
Instead, the expectation is that current miners discount future possible gains 
because in the future, they expect to have less hashrate share than right now.

The only trustless way for Bob to bribe miners into deferring Alice tx is to 
attach the bribe to the future confirmation of the Bob tx, thus Bob is offering 
future-coins, not present-coins like Alice can offer, and the fact that miners 
expect an overall uptrend in total hashrate (leading to an overall downtrend in 
their hashrate share) means that miners discount the Bob offered future-coins.
The discounting is proportional to the time delay involved, as a larger delay 
implies greater reduction in hashrate share.

This discounting is, again, *in addition to* natural discounting a.k.a. "I will 
gladly pay you Thursday for a hamburger today", the hamburger seller will want 
some pretty stiff assurances plus a bigger payment on Thursday for giving you a 
hamburger today, due to expected returns on investment.


> >  
> >
> > > It also strikes me that, in a world with RBF and CPFP, the same endpoint 
> > > (i.e. miners earn the entire fund of the HTLC) is achieved by existing 
> > > HTLCs, without the additional branch and script opcodes needed by 
> > > MAD-HTLC.
> > > For example, if an HTLC is confirmed but the hashlock-claiming 
> > > transaction is not being confirmed (because miners are holding it up 
> > > because Bob is offering a much higher fee in the future for the 
> > > timelock-claiming transaction), then Alice can, regardless of the reason 
> > > why it is not being confirmed, bump up the fee with RBF or CPFP.
> > >
> > > If the fee bump offered by Alice is sufficiently large, then miners will 
> > > start re-preferring the Alice hashlock transaction.
> > > To counter this, Bob has to bid up its version higher.
> > >
> > > As the timeout approaches, Alice can bump up its fee until it is just 1 
> > > satoshi short of the total fund.
> > > It is rational for Alice to do so since at timeout, it can expect to lose 
> > > the entire fund.
> > > In order for Bob to win, it has to beat that fee, at which point it 
> > > equals or exceeds the total fund, and miners get the total fund (or more).
> > >
> > > Knowing this end-point, rational Bob will not even begin this game.
> > >
> > > I think this research considers these two endpoints to be distinct:
> > >
> > > * Bob misbehaves and the entire fund is punished by miners, leaving 
> > > miners with the fund and Alice and Bob without money (MAD-HTLC).
> > > * Bob misbehaves, Alice counters, and the ensuing fee war leads to fees 
> > > approaching the fund value, leaving miners with the fund and Alice and 
> > > Bob without money (standard HTLC).
> > >
> > > But in practice I think both endpoints are essentially equivalent.
> >
> > These are not the same scenario, since in HTLC there is a race between 
> > Alice and Bob. Alice might not wish to pay the full HTLC amount once she 
> > sees Bob is trying to cheat. She could wait until close to the timeout so 
> > as to reduce the time Bob can respond. Of course Bob would do the same. So 
> > this is an actual race, and Bob takes no risk since his payment is all from

Re: [bitcoin-dev] MAD-HTLC

[Stanga via bitcoin-dev]

Of course the order at the end should have been switched:

Consider first the case where Alice *does not* publish preimage "A": Bob
can safely publish preimage "B" and get both the Deposit and Collateral
tokens after the timeout.
Now, consider the case where Alice *publishes* preimage "A": If Bob
publishes preimage "B" he gets nothing (and so does Alice - this is the
mutual assured destruction), and if he doesn't, he gets the Collateral
tokens.


On Tue, Jun 23, 2020 at 3:47 PM Stanga  wrote:

> Hi ZmnSCPxj,
>
> Thank you for taking the time to respond, these are very good points.
> Responses inline.
>
> On Tue, Jun 23, 2020 at 12:48 PM ZmnSCPxj  wrote:
>
>> Good morning Itay, Ittay, and Matan,
>>
>> I believe an unstated assumption in Bitcoin is that miners are
>> short-sighted.
>>
>> The reasoning for this assumption is:
>>
>> * Deployment of new mining hardware controlled by others may occur at any
>> time you do not control.
>>   * Thus, any transactions you leave on the table are potentially taken
>> by somebody else and not by you.
>>   * Sudden changes in hashpower distribution may reduce your expected
>> future earnings, so any future theoretical earnings should be discounted
>> (*in addition to* expected return-on-investment on getting money you can
>> invest *now*).
>>
>
> Our analysis assumes constant difficulty, i.e., no significant changes of
> the miners set. Indeed, hash-rate changes typically occur at a much larger
> granularity than your average HTLC timeout. For instance, we noticed plenty
> of lightning nodes use timeouts of a day. So, we do not consider
> optimization at infinity, just a day ahead, and within this time frame all
> the factors you mentioned are not expected to dramatically change.
>
> That being said, it would be interesting to analyze the effect of miners
> joining during the HTLC duration. Intuitively, this shouldn’t affect the
> results, as those new miners have the same incentive to wait for the
> higher-paying tx.
>
>
>>
>> It also strikes me that, in a world with RBF and CPFP, the same endpoint
>> (i.e. miners earn the entire fund of the HTLC) is achieved by existing
>> HTLCs, without the additional branch and script opcodes needed by MAD-HTLC.
>> For example, if an HTLC is confirmed but the hashlock-claiming
>> transaction is not being confirmed (because miners are holding it up
>> because Bob is offering a much higher fee in the future for the
>> timelock-claiming transaction), then Alice can, regardless of the reason
>> why it is not being confirmed, bump up the fee with RBF or CPFP.
>>
>> If the fee bump offered by Alice is sufficiently large, then miners will
>> start re-preferring the Alice hashlock transaction.
>> To counter this, Bob has to bid up its version higher.
>>
>> As the timeout approaches, Alice can bump up its fee until it is just 1
>> satoshi short of the total fund.
>> It is rational for Alice to do so since at timeout, it can expect to lose
>> the entire fund.
>> In order for Bob to win, it has to beat that fee, at which point it
>> equals or exceeds the total fund, and miners get the total fund (or more).
>>
>> Knowing this end-point, rational Bob will not even begin this game.
>>
>> I think this research considers these two endpoints to be distinct:
>>
>> * Bob misbehaves and the entire fund is punished by miners, leaving
>> miners with the fund and Alice and Bob without money (MAD-HTLC).
>> * Bob misbehaves, Alice counters, and the ensuing fee war leads to fees
>> approaching the fund value, leaving miners with the fund and Alice and Bob
>> without money (standard HTLC).
>>
>> But in practice I think both endpoints are essentially equivalent.
>>
>
> These are not the same scenario, since in HTLC there is a race between
> Alice and Bob. Alice might not wish to pay the full HTLC amount once she
> sees Bob is trying to cheat. She could wait until close to the timeout so
> as to reduce the time Bob can respond. Of course Bob would do the same. So
> this is an actual race, and Bob takes no risk since his payment is all from
> the HTLC amount. Mutual destruction is only assured under certain
> assumptions in HTLC. MAD-HTLC achieves security without relying on such
> assumptions.
>
>
>>
>> --
>>
>> What MAD-HTLC can do would be to make different claims:
>>
>> * 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
>>
>> This is an actual improvement over HTLC: Bob misbehavior leads to loss of
>> the fidelity bond.
>> The above cases can be assured by requiring both Alice and Bob to sign in
>> the alice-hashlock branch, so that the splitting of the fund is enforced,
>> and SegWit signing s

Re: [bitcoin-dev] MAD-HTLC

[Stanga via bitcoin-dev]

Hi ZmnSCPxj,

Thank you for taking the time to respond, these are very good points.
Responses inline.

On Tue, Jun 23, 2020 at 12:48 PM ZmnSCPxj  wrote:

> Good morning Itay, Ittay, and Matan,
>
> I believe an unstated assumption in Bitcoin is that miners are
> short-sighted.
>
> The reasoning for this assumption is:
>
> * Deployment of new mining hardware controlled by others may occur at any
> time you do not control.
>   * Thus, any transactions you leave on the table are potentially taken by
> somebody else and not by you.
>   * Sudden changes in hashpower distribution may reduce your expected
> future earnings, so any future theoretical earnings should be discounted
> (*in addition to* expected return-on-investment on getting money you can
> invest *now*).
>

Our analysis assumes constant difficulty, i.e., no significant changes of
the miners set. Indeed, hash-rate changes typically occur at a much larger
granularity than your average HTLC timeout. For instance, we noticed plenty
of lightning nodes use timeouts of a day. So, we do not consider
optimization at infinity, just a day ahead, and within this time frame all
the factors you mentioned are not expected to dramatically change.

That being said, it would be interesting to analyze the effect of miners
joining during the HTLC duration. Intuitively, this shouldn’t affect the
results, as those new miners have the same incentive to wait for the
higher-paying tx.


>
> It also strikes me that, in a world with RBF and CPFP, the same endpoint
> (i.e. miners earn the entire fund of the HTLC) is achieved by existing
> HTLCs, without the additional branch and script opcodes needed by MAD-HTLC.
> For example, if an HTLC is confirmed but the hashlock-claiming transaction
> is not being confirmed (because miners are holding it up because Bob is
> offering a much higher fee in the future for the timelock-claiming
> transaction), then Alice can, regardless of the reason why it is not being
> confirmed, bump up the fee with RBF or CPFP.
>
> If the fee bump offered by Alice is sufficiently large, then miners will
> start re-preferring the Alice hashlock transaction.
> To counter this, Bob has to bid up its version higher.
>
> As the timeout approaches, Alice can bump up its fee until it is just 1
> satoshi short of the total fund.
> It is rational for Alice to do so since at timeout, it can expect to lose
> the entire fund.
> In order for Bob to win, it has to beat that fee, at which point it equals
> or exceeds the total fund, and miners get the total fund (or more).
>
> Knowing this end-point, rational Bob will not even begin this game.
>
> I think this research considers these two endpoints to be distinct:
>
> * Bob misbehaves and the entire fund is punished by miners, leaving miners
> with the fund and Alice and Bob without money (MAD-HTLC).
> * Bob misbehaves, Alice counters, and the ensuing fee war leads to fees
> approaching the fund value, leaving miners with the fund and Alice and Bob
> without money (standard HTLC).
>
> But in practice I think both endpoints are essentially equivalent.
>

These are not the same scenario, since in HTLC there is a race between
Alice and Bob. Alice might not wish to pay the full HTLC amount once she
sees Bob is trying to cheat. She could wait until close to the timeout so
as to reduce the time Bob can respond. Of course Bob would do the same. So
this is an actual race, and Bob takes no risk since his payment is all from
the HTLC amount. Mutual destruction is only assured under certain
assumptions in HTLC. MAD-HTLC achieves security without relying on such
assumptions.


>
> --
>
> What MAD-HTLC can do would be to make different claims:
>
> * 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
>
> This is an actual improvement over HTLC: Bob misbehavior leads to loss of
> the fidelity bond.
> The above cases can be assured by requiring both Alice and Bob to sign in
> the alice-hashlock branch, so that the splitting of the fund is enforced,
> and SegWit signing so that the dependent transaction is signed before the
> HTLC-funding transaction is.
> It can also be implemented with `OP_CHECKTEMPLATEVERIFY`.


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 (mine

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj via bitcoin-dev]

Good morning Itay, Ittay, and Matan,

I believe an unstated assumption in Bitcoin is that miners are short-sighted.

The reasoning for this assumption is:

* Deployment of new mining hardware controlled by others may occur at any time 
you do not control.
  * Thus, any transactions you leave on the table are potentially taken by 
somebody else and not by you.
  * Sudden changes in hashpower distribution may reduce your expected future 
earnings, so any future theoretical earnings should be discounted (*in addition 
to* expected return-on-investment on getting money you can invest *now*).

It also strikes me that, in a world with RBF and CPFP, the same endpoint (i.e. 
miners earn the entire fund of the HTLC) is achieved by existing HTLCs, without 
the additional branch and script opcodes needed by MAD-HTLC.
For example, if an HTLC is confirmed but the hashlock-claiming transaction is 
not being confirmed (because miners are holding it up because Bob is offering a 
much higher fee in the future for the timelock-claiming transaction), then 
Alice can, regardless of the reason why it is not being confirmed, bump up the 
fee with RBF or CPFP.

If the fee bump offered by Alice is sufficiently large, then miners will start 
re-preferring the Alice hashlock transaction.
To counter this, Bob has to bid up its version higher.

As the timeout approaches, Alice can bump up its fee until it is just 1 satoshi 
short of the total fund.
It is rational for Alice to do so since at timeout, it can expect to lose the 
entire fund.
In order for Bob to win, it has to beat that fee, at which point it equals or 
exceeds the total fund, and miners get the total fund (or more).

Knowing this end-point, rational Bob will not even begin this game.

I think this research considers these two endpoints to be distinct:

* Bob misbehaves and the entire fund is punished by miners, leaving miners with 
the fund and Alice and Bob without money (MAD-HTLC).
* Bob misbehaves, Alice counters, and the ensuing fee war leads to fees 
approaching the fund value, leaving miners with the fund and Alice and Bob 
without money (standard HTLC).

But in practice I think both endpoints are essentially equivalent.

--

What MAD-HTLC can do would be to make different claims:

* 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

This is an actual improvement over HTLC: Bob misbehavior leads to loss of the 
fidelity bond.
The above cases can be assured by requiring both Alice and Bob to sign in the 
alice-hashlock branch, so that the splitting of the fund is enforced, and 
SegWit signing so that the dependent transaction is signed before the 
HTLC-funding transaction is.
It can also be implemented with `OP_CHECKTEMPLATEVERIFY`.

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