[bitcoin-dev] MAD-HTLC

[bitcoin-dev] MAD-HTLC

[Stanga]

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

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

Essentially, we find that HTLC security relies on miners being altruistic,
or at least myopic. This might be enough for some time, but it took us 150
lines of code to make bitcoind non-myopic.

On the positive side, we discovered an alternative to HTLC that we call
MAD-HTLC, which is provably secure -- everyone's best interest is to behave
as desired.

We've notified relevant teams in advance.

We'll appreciate any comments.

Best,
Itay, Ittay, and Matan

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

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj]

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

Re: [bitcoin-dev] MAD-HTLC

[Stanga]

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

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 <ZmnSCPxj@protonmail.com> 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 (miner), with both preimages "A" and "B", timeout T

Only Bob initially knows preimage "B", and is required to reveal it if he
wishes to get the Deposit tokens.

Consider first the case where Alice publishes 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 does not publish 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.

Best,
Ittay

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

Re: [bitcoin-dev] MAD-HTLC

[Stanga]

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

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 <stanga@gmail.com> 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 <ZmnSCPxj@protonmail.com> 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 (miner), with both preimages "A" and "B", timeout T
>
> Only Bob initially knows preimage "B", and is required to reveal it if he
> wishes to get the Deposit tokens.
>
> Consider first the case where Alice publishes 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 does not publish 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.
>
> Best,
> Ittay
>
>

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

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj]

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 <ZmnSCPxj@protonmail.com> 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 the HTLC amount. Mutual destruction is only assured under certain assumptions in HTLC. MAD-HTLC achieves security without relying on such assumptions. 

Alice already knows that a rational Bob (who it might never interact with again in the future) will take the funds at the locktime L.
Thus, Alice can offer, at time L - 1, the entire fund, minus 1 satoshi, to miners.
Alice getting 1 satoshi versus 0 satoshi is a no-brainer for Alice.
Bob can only  beat this offer by offering the entire fund, at which point Bob earns nothing and it performed an attack for no benefit.

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


> >  
> >
> > > --
> > >
> > > 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 (miner), with both preimages "A" and "B", timeout T
> >
> > Only Bob initially knows preimage "B", and is required to reveal it if he wishes to get the Deposit tokens.
> >
> > Consider first the case where Alice publishes 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 does not publish 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.

Thank you for the clarification.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] MAD-HTLC

[Nadav Ivgi]

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

> 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 <ZmnSCPxj@protonmail.com>
> 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
> the HTLC amount. Mutual destruction is only assured under certain
> assumptions in HTLC. MAD-HTLC achieves security without relying on such
> assumptions.
>
> Alice already knows that a rational Bob (who it might never interact with
> again in the future) will take the funds at the locktime L.
> Thus, Alice can offer, at time L - 1, the entire fund, minus 1 satoshi, to
> miners.
> Alice getting 1 satoshi versus 0 satoshi is a no-brainer for Alice.
> Bob can only  beat this offer by offering the entire fund, at which point
> Bob earns nothing and it performed an attack for no benefit.
>
> I and some number of Lightning devs consider this to be sufficient
> disincentive to Bob not attacking in the first place.
>
>
> > >
> > >
> > > > --
> > > >
> > > > 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 (miner), with both preimages "A" and "B", timeout T
> > >
> > > Only Bob initially knows preimage "B", and is required to reveal it if
> he wishes to get the Deposit tokens.
> > >
> > > Consider first the case where Alice publishes 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 does not publish 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.
>
> Thank you for the clarification.
>
> Regards,
> ZmnSCPxj
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj]

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

Re: [bitcoin-dev] MAD-HTLC

[Nadav Ivgi]

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

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 <ZmnSCPxj@protonmail.com> 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
>

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

Re: [bitcoin-dev] MAD-HTLC

[Bastien TEINTURIER]

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

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 <ZmnSCPxj@protonmail.com> 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
>

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

Re: [bitcoin-dev] MAD-HTLC

[David A. Harding]

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

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 simply increasing the
    timeout does contribute to HTLC’s security."  This implies that
    Alice, after she sees Bob's attempted bribe, could offer a counter
    bribe that spends all output value to fees (the scorched earth
    policy ZmnSCPxj describes) with a timelock set to the maximum
    single-transaction value (block 500 million, due to be mined in
    about 10 millennia, give or take a few centuries) and miners would
    hold on to it until then, never mining Bob's lower-feerate bribe.
    That's ridiculous, but it's understandable in your paper because
    you're mainly analyzing time periods so short that you don't need to
    worry much about the time-value-of-money discount (also mentioned by
    ZmnSCPxj); however, your paper also says that your Python
    implementation uses the same formulas in your paper to determine
    whether or not a bribe will profitable, which would obviously be
    wrong for a 10,000-year timelock.

[2] See the never ending discussions on this list and Lightning-Dev
    about ancestor mining package size/depth limits and BIP125 opt-in
    RBF rule #3.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] MAD-HTLC

[David A. Harding]

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

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 <ZmnSCPxj@protonmail.com> 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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli]

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

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.

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

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj]

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]

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

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
<https://ieeexplore.ieee.org/abstract/document/8802377>," *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 <ZmnSCPxj@protonmail.com> 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
>

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

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli]

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

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
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj]

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 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 business.
Alice gets, as a side effect of this competitiveness of miners (which leads to miners adopting myopic strategies in order to gain an edge over non-myopic miners), improved security of their HTLCs without requiring slashable fidelity bonds or such-like that MAD-HTLC proposes.


Using this model, it seems to me that non-myopic miners can only maintain hold over the blockchain if all miners agree to use non-myopic strategy.
This is basically all miners forming a cartel / monopoly, which we know is detrimental to customers of the monopoly, and is the reason why we prefer decentralization.


Regards,
ZmnSCPxj




> 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
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli]

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

On Wed, Jul 1, 2020 at 6:58 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> 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?

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

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli]

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

On Wed, Jul 1, 2020 at 6:58 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> 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 business.
> Alice gets, as a side effect of this competitiveness of miners (which
> leads to miners adopting myopic strategies in order to gain an edge over
> non-myopic miners), improved security of their HTLCs without requiring
> slashable fidelity bonds or such-like that MAD-HTLC proposes.
>

Yes. And in the context of Lightning, both Alice and Bob need to have
fidelity bonds, which triples the already bad channel-lockin cost.


> Using this model, it seems to me that non-myopic miners can only maintain
> hold over the blockchain if all miners agree to use non-myopic strategy.
> This is basically all miners forming a cartel / monopoly, which we know is
> detrimental to customers of the monopoly, and is the reason why we prefer
> decentralization.
>

If miners form a cartel and get to 51%, we are all doomed anyway.

Thanks for the detailed reply. And apologies for splitting my email into
two parts.

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

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj]

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 another way, if you use a modern offchain updateable cryptocurrency system at all, you are still vulnerable to the MAD-HTLC argument even if you never instantiate HTLCs inside the offchain system.

Thus, other proposed systems that (could) use any of the channel mechanisms, but do ***not*** necessarily use HTLCs, such as CoinPools, channel factories, and statechains, are also vulnerable to the MAD-HTLC argument.

In particular, if the MAD-HTLC argument holds, we should take note that e.g. Lightning channels have to be at least as large as any HTLC they contain, and since the MAD-HTLC argument applies to the channel itself (in addition to any HTLCs they contain), the application of that argument implies greater loss, as it is the entire channel that is at risk, not just any HTLCs it might contain.

Spilman
=======

A Spilman channel is a unidirectional single-funded channel.

The overall idea was presented pre-SegWit, and needed `OP_CHECKLOCKTIMEVERIFY` to be malleation-safe.
I will describe here a modernized version that uses SegWit (and thus is malleation safe) instead.

Suppose Bob wishes to make a Spilman channel to Alice.
The setup is as follows:

* Bob creates but does *NOT* sign a funding transaction, paying out to a 2-of-2 between Alice and Bob, and hands over this txid and the output number to Alice.
* Alice creates a timeout transaction, `nLockTime`d to a pre-agreed locktime, spending the above txout, and returning the funds to Bob, and signs this transaction and hands over the signature and tx to Bob.
* Bob signs the funding transaction and broadcasts it.
* Alice and Bob wait for deep confirmation of the funding tx.

At each payment from Bob to Alice, Bob signs a non-`nLockTime`d (or one with current blockheight) transaction that spends the funding txout and assigns more of the fund to Alice, then sends the signature and tx to Alice.

At any time, Alice can unilaterally close the channel using any of the signatures given by Bob.
Rationally, it will publish the one that gives it the most money, which is the latest such transaction, thus leading to the unidirectional nature of Spilman channels.
Alice needs to perform this unilateral close far before the pre-agreed locktime.

Under the MAD-HTLC argument, Bob can bribe miners to ignore the Alice unilateral close transaction, and the initial timeout transaction by Bob gets confirmed even if within the channel mechanism Alice is supposed to own most or all of the funds.

Poon-Dryja
==========

A Poon-Dryja channel is a modern two-participant bidirectional channel.

The core of security of Poon-Dryja involves "revocable outputs".
A revocable output is an output that, when published onchain, is owned by one entity (the owner), but that entity may reveal a secret, the revocation secret, to another entity (the revoker).
Once that other entity knows the revocation secret, if the output is ever published onchain, it can revoke the output and claim its value.

Poon-Dryja uses this building block to implement an updateable state.
All states are represented by commitment transactions that have revocable outputs.
In order to advance to a new state, the revocable outputs of previous states are revoked by exchanging revocation secrets.
Thus, the security of Poon-Dryja is dependent on the correct operation of revocation.

Revocable outputs are implemented by imposing a relative locktime on the owner of the output, and requiring knowledge of two secrets from the revoker.

Thus, a revocable output has two branches:

* Revocation branch: with the revoker privkey and knowledge of a revocaation secret, the revoker can claim the fund immediately.
* Claim branch: with the owner privkey and a relative locktime, the owner can claim the fund after a pre-agreed number of blocks (`to_self_delay` in Lightning) since the output is confirmed onchain.

Under the MAD-HTLC argument, the owner of the revoked output can bribe miners to ignore attempts by the revoker to claim the funds until the claim branch is valid and confirmable.
Thus, a thief can publish old state, then apply the MAD-HTLC argument to get miners to ignore the revoker of the old state.

Decker-Wattenhofer decrementing-`nSequence`
===========================================

Decker-Wattenhofer ("Duplex Micropayment Channels") is a modern multi-participant (N >= 2) offchain updateable cryptocurrency mechanism.

Decker-Wattenhofer chains together two different mechanisms, embedding them one inside the other, in order to balance the tradeoffs of one with the tradeoffs of the other.

* One or more decrementing-`nSequence` mechanisms, chained one inside the other.
* Two ("duplex") unidirectional Spilman variants, using a relative locktime instead of an absolute locktime, one in both directions of the channel, inside the innermost decrementing-`nSequence` mechanism.

The decrementing-`nSequence` mechanisms by themselves are multiparticipant (N >= 2), and if we focus only on having one or more of these mechanisms chained together, we can consider Decker-Wattenhofer as multiparticipant.

In the decrementing-`nSequence` mechanism, there is a kickoff transaction which spends from the n-of-n funding outpoint, and sends it to yet another n-of-n output between the participants.
Then, the second n-of-n is spent by a transaction with a relative-locktime `nSequence` transaction, which then distributes the money among various participants.

When a new state is created, the participants create and sign a new relative-locktime `nSequence` transaction spending the kickoff n-of-n outpoint.
The new state transaction has a lower `nSequence` than the most previous state transaction, hence decrementing-`nSequence`.
Once the latest state transaction has a 0-block relative locktime, a newer state can no longer be added to the mechanism.

The kickoff n-of-n outpoint thus has multiple branches, one for each created state.
The most recent state is assumed to supersede previous states, because it has the smallest relative locktime among all states.

Under the MAD-HTLC argument, a participant which prefers an older state can bribe miners to defer confirmation of all more recent states.
Thus, that participant can publish the kickoff and bribe miners to defer more recent states until its preferred state is confirmable onchain.

Decker-Russell-Osuntokun
========================

Decker-Russell-Osuntokun ("eltoo") is a futuristic multiparticipant (N >= 2) offchain updateable cryptocurrency system.

Decker-Russell-Osuntokun uses a proposed new `SIGHASH_NOINPUT` flag, which does not commit to the specific output being spent, allowing a signature that signs using `SIGHASH_NOINPUT` to be used to spend a different transaction outpoint, as long as the same pubkey is used for that outpoint.

As is typical for channel mechanisms, a funding outpoint is created, which is an n-of-n of all participants.
The funding outpoint is spent by an update transaction with a single output, which has the following branches:

* Update branch: can be spent by the same n-of-n pubkeys as the funding outpoint, as long as the spending transaction has a higher `nLockTime` than the update transaction.
* State branch: can be spent by a different n-of-n pubkeys from the same participants, after a relative locktime.
  * Each update transaction has its own unique set of n-of-n pubkeys for the state branch, given by the same participant set.

Of note is that the `nLockTime` used in Decker-Russell-Osuntokun are always past `nLockTime`s, so that the update branch is always confirmable at the current tip, from now until forever.
Only the state branch has an actual timelock that could prevent immediate confirmation of a transaction spending that branch.

Update transactions (awesomely mis)use `nLockTime` as a sequence number; the first update transaction has the lowest `nLockTime`, then each succeeding update transaction has a higher `nLockTime`, until they reach the present time.

Update transactions are signed with `SIGHASH_NOINPUT`.
This allows the update transaction to not only spend the funding outpoint itself, but also to spend any previous update transaction.

Thus, if an old update transaction is published onchain, its output can be re-spent by any newer update transaction before the state transaction for that update can come into play.
Any other participant who notices this event can simply publish the newest update transaction it knows, as that would supersede the state transaction, which can only be confirmed after a time delay.

Under the MAD-HTLC argument, a participant who prefers an older state can publish the update transaction for the older state, then bribe miners to defer confirmation of newer update transactions, until the state transaction for that update transaction can be confirmed.

Conclusion
==========

All the above mechanisms use a timelock, and implicitly have the assumption that "a transaction, that can be confirmed now, supersedes any transaction that has a timelock that forces it to be confirmed later".

It seems likely to me that even future mechanisms will use the same assumption as well.

In particular, many proposed mechanisms for non-federated sidechains often include some kind of delay between when a sidechain coin is burned and the corresponding mainchain coin is released (i.e. side-to-main peg).
Often, this delay exists in order to allow showing of a counterproof that the supposed side-to-main transfer did not actually exist in the sidechain (or was later reorged out, or whatever).
It seems to me that the MAD-HTLC argument would also apply to such mechanisms (if anyone still wants to go push sidechains, anyway).

Thus, we really need to carefully investigate the MAD-HTLC argument.

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



Regards,
ZmnSCPxj

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli]

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

On Thu, Jul 2, 2020 at 6:06 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> 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
<https://nms.kcl.ac.uk/patrick.mccorry/thesis.pdf>, 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 <ZmnSCPxj@protonmail.com> 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 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 another way, if you use a modern offchain updateable cryptocurrency
> system at all, you are still vulnerable to the MAD-HTLC argument even if
> you never instantiate HTLCs inside the offchain system.
>
> Thus, other proposed systems that (could) use any of the channel
> mechanisms, but do ***not*** necessarily use HTLCs, such as CoinPools,
> channel factories, and statechains, are also vulnerable to the MAD-HTLC
> argument.
>
> In particular, if the MAD-HTLC argument holds, we should take note that
> e.g. Lightning channels have to be at least as large as any HTLC they
> contain, and since the MAD-HTLC argument applies to the channel itself (in
> addition to any HTLCs they contain), the application of that argument
> implies greater loss, as it is the entire channel that is at risk, not just
> any HTLCs it might contain.
>
> Spilman
> =======
>
> A Spilman channel is a unidirectional single-funded channel.
>
> The overall idea was presented pre-SegWit, and needed
> `OP_CHECKLOCKTIMEVERIFY` to be malleation-safe.
> I will describe here a modernized version that uses SegWit (and thus is
> malleation safe) instead.
>
> Suppose Bob wishes to make a Spilman channel to Alice.
> The setup is as follows:
>
> * Bob creates but does *NOT* sign a funding transaction, paying out to a
> 2-of-2 between Alice and Bob, and hands over this txid and the output
> number to Alice.
> * Alice creates a timeout transaction, `nLockTime`d to a pre-agreed
> locktime, spending the above txout, and returning the funds to Bob, and
> signs this transaction and hands over the signature and tx to Bob.
> * Bob signs the funding transaction and broadcasts it.
> * Alice and Bob wait for deep confirmation of the funding tx.
>
> At each payment from Bob to Alice, Bob signs a non-`nLockTime`d (or one
> with current blockheight) transaction that spends the funding txout and
> assigns more of the fund to Alice, then sends the signature and tx to Alice.
>
> At any time, Alice can unilaterally close the channel using any of the
> signatures given by Bob.
> Rationally, it will publish the one that gives it the most money, which is
> the latest such transaction, thus leading to the unidirectional nature of
> Spilman channels.
> Alice needs to perform this unilateral close far before the pre-agreed
> locktime.
>
> Under the MAD-HTLC argument, Bob can bribe miners to ignore the Alice
> unilateral close transaction, and the initial timeout transaction by Bob
> gets confirmed even if within the channel mechanism Alice is supposed to
> own most or all of the funds.
>
> Poon-Dryja
> ==========
>
> A Poon-Dryja channel is a modern two-participant bidirectional channel.
>
> The core of security of Poon-Dryja involves "revocable outputs".
> A revocable output is an output that, when published onchain, is owned by
> one entity (the owner), but that entity may reveal a secret, the revocation
> secret, to another entity (the revoker).
> Once that other entity knows the revocation secret, if the output is ever
> published onchain, it can revoke the output and claim its value.
>
> Poon-Dryja uses this building block to implement an updateable state.
> All states are represented by commitment transactions that have revocable
> outputs.
> In order to advance to a new state, the revocable outputs of previous
> states are revoked by exchanging revocation secrets.
> Thus, the security of Poon-Dryja is dependent on the correct operation of
> revocation.
>
> Revocable outputs are implemented by imposing a relative locktime on the
> owner of the output, and requiring knowledge of two secrets from the
> revoker.
>
> Thus, a revocable output has two branches:
>
> * Revocation branch: with the revoker privkey and knowledge of a
> revocaation secret, the revoker can claim the fund immediately.
> * Claim branch: with the owner privkey and a relative locktime, the owner
> can claim the fund after a pre-agreed number of blocks (`to_self_delay` in
> Lightning) since the output is confirmed onchain.
>
> Under the MAD-HTLC argument, the owner of the revoked output can bribe
> miners to ignore attempts by the revoker to claim the funds until the claim
> branch is valid and confirmable.
> Thus, a thief can publish old state, then apply the MAD-HTLC argument to
> get miners to ignore the revoker of the old state.
>
> Decker-Wattenhofer decrementing-`nSequence`
> ===========================================
>
> Decker-Wattenhofer ("Duplex Micropayment Channels") is a modern
> multi-participant (N >= 2) offchain updateable cryptocurrency mechanism.
>
> Decker-Wattenhofer chains together two different mechanisms, embedding
> them one inside the other, in order to balance the tradeoffs of one with
> the tradeoffs of the other.
>
> * One or more decrementing-`nSequence` mechanisms, chained one inside the
> other.
> * Two ("duplex") unidirectional Spilman variants, using a relative
> locktime instead of an absolute locktime, one in both directions of the
> channel, inside the innermost decrementing-`nSequence` mechanism.
>
> The decrementing-`nSequence` mechanisms by themselves are multiparticipant
> (N >= 2), and if we focus only on having one or more of these mechanisms
> chained together, we can consider Decker-Wattenhofer as multiparticipant.
>
> In the decrementing-`nSequence` mechanism, there is a kickoff transaction
> which spends from the n-of-n funding outpoint, and sends it to yet another
> n-of-n output between the participants.
> Then, the second n-of-n is spent by a transaction with a relative-locktime
> `nSequence` transaction, which then distributes the money among various
> participants.
>
> When a new state is created, the participants create and sign a new
> relative-locktime `nSequence` transaction spending the kickoff n-of-n
> outpoint.
> The new state transaction has a lower `nSequence` than the most previous
> state transaction, hence decrementing-`nSequence`.
> Once the latest state transaction has a 0-block relative locktime, a newer
> state can no longer be added to the mechanism.
>
> The kickoff n-of-n outpoint thus has multiple branches, one for each
> created state.
> The most recent state is assumed to supersede previous states, because it
> has the smallest relative locktime among all states.
>
> Under the MAD-HTLC argument, a participant which prefers an older state
> can bribe miners to defer confirmation of all more recent states.
> Thus, that participant can publish the kickoff and bribe miners to defer
> more recent states until its preferred state is confirmable onchain.
>
> Decker-Russell-Osuntokun
> ========================
>
> Decker-Russell-Osuntokun ("eltoo") is a futuristic multiparticipant (N >=
> 2) offchain updateable cryptocurrency system.
>
> Decker-Russell-Osuntokun uses a proposed new `SIGHASH_NOINPUT` flag, which
> does not commit to the specific output being spent, allowing a signature
> that signs using `SIGHASH_NOINPUT` to be used to spend a different
> transaction outpoint, as long as the same pubkey is used for that outpoint.
>
> As is typical for channel mechanisms, a funding outpoint is created, which
> is an n-of-n of all participants.
> The funding outpoint is spent by an update transaction with a single
> output, which has the following branches:
>
> * Update branch: can be spent by the same n-of-n pubkeys as the funding
> outpoint, as long as the spending transaction has a higher `nLockTime` than
> the update transaction.
> * State branch: can be spent by a different n-of-n pubkeys from the same
> participants, after a relative locktime.
>   * Each update transaction has its own unique set of n-of-n pubkeys for
> the state branch, given by the same participant set.
>
> Of note is that the `nLockTime` used in Decker-Russell-Osuntokun are
> always past `nLockTime`s, so that the update branch is always confirmable
> at the current tip, from now until forever.
> Only the state branch has an actual timelock that could prevent immediate
> confirmation of a transaction spending that branch.
>
> Update transactions (awesomely mis)use `nLockTime` as a sequence number;
> the first update transaction has the lowest `nLockTime`, then each
> succeeding update transaction has a higher `nLockTime`, until they reach
> the present time.
>
> Update transactions are signed with `SIGHASH_NOINPUT`.
> This allows the update transaction to not only spend the funding outpoint
> itself, but also to spend any previous update transaction.
>
> Thus, if an old update transaction is published onchain, its output can be
> re-spent by any newer update transaction before the state transaction for
> that update can come into play.
> Any other participant who notices this event can simply publish the newest
> update transaction it knows, as that would supersede the state transaction,
> which can only be confirmed after a time delay.
>
> Under the MAD-HTLC argument, a participant who prefers an older state can
> publish the update transaction for the older state, then bribe miners to
> defer confirmation of newer update transactions, until the state
> transaction for that update transaction can be confirmed.
>
> Conclusion
> ==========
>
> All the above mechanisms use a timelock, and implicitly have the
> assumption that "a transaction, that can be confirmed now, supersedes any
> transaction that has a timelock that forces it to be confirmed later".
>
> It seems likely to me that even future mechanisms will use the same
> assumption as well.
>
> In particular, many proposed mechanisms for non-federated sidechains often
> include some kind of delay between when a sidechain coin is burned and the
> corresponding mainchain coin is released (i.e. side-to-main peg).
> Often, this delay exists in order to allow showing of a counterproof that
> the supposed side-to-main transfer did not actually exist in the sidechain
> (or was later reorged out, or whatever).
> It seems to me that the MAD-HTLC argument would also apply to such
> mechanisms (if anyone still wants to go push sidechains, anyway).
>
> Thus, we really need to carefully investigate the MAD-HTLC argument.
>
> 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.
> 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.
>
>
>
> Regards,
> ZmnSCPxj
>

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

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj]

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 <A> OP_ELSE <1 day> OP_CHECKSEQUENCEVERIFY OP_DROP <B> 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 `<A>` 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 implemented using Decker-Wattenhofer, assuming  it gets any details or support behind it sufficiently to push it before `SIGHASH_ANYPREVOUT` gets deployed.

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

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.


Regards,
ZmnSCPxj

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli]

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

On Fri, Jul 3, 2020 at 12:17 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> 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 :-)

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

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj]

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 funds than their non-myopic competitors and thus dominate, shifting the percentages until almost all miners are using myopic strategies.
That they require less processing ("keep it simple, sir") is just gravy on top.


The only way for non-myopic miners to win is to form a cartel, and a miner cartel with >50% hashpower would be the end of Bitcoin anyway.


Regards,
ZmnSCPxj

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj]

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

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj]

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

Re: [bitcoin-dev] MAD-HTLC

[Stanga]

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

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 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 funds than their non-myopic competitors
> and thus dominate, shifting the percentages until almost all miners are
> using myopic strategies.
> That they require less processing ("keep it simple, sir") is just gravy on
> top.
>
>
> The only way for non-myopic miners to win is to form a cartel, and a miner
> cartel with >50% hashpower would be the end of Bitcoin anyway.
>
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli]

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

On Fri, Jul 3, 2020 at 1:49 PM Itay Tsabary <sitay@campus.technion.ac.il>
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?

>

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