Re: [bitcoin-dev] MAD-HTLC

2020-07-05 Thread Stanga via bitcoin-dev
Hi ZmnSCPxj,

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

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

Best,
Ittay


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

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

Re: [bitcoin-dev] MAD-HTLC

2020-06-30 Thread Stanga via bitcoin-dev
Hi ZmnSCPxj,

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

Best,
Ittay

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

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

> Good morning Dave, et al.,
>
>
> > >  Myopic Miners: This bribery attack relies on all miners
> > >
> > >
> > > being rational, hence considering their utility at game conclu-
> > > sion instead of myopically optimizing for the next block. If
> > > a portion of the miners are myopic and any of them gets to
> > > create a block during the first T − 1 rounds, that miner would
> > > include Alice’s transaction and Bob’s bribery attempt would
> > > have failed.
> > > In such scenarios the attack succeeds only with a certain
> > > probability – only if a myopic miner does not create a block
> > > in the first T − 1 rounds. The success probability therefore
> > > decreases exponentially in T . Hence, to incentivize miners
> > > to support the attack, Bob has to increase his offered bribe
> > > exponentially in T .
> >
> > This is a good abstract description, but I think it might be useful for
> > readers of this list who are wondering about the impact of this attack
> > to put it in concrete terms. I'm bad at statistics, but I think the
> > probability of bribery failing (even if Bob offers a bribe with an
> > appropriately high feerate) is 1-exp(-b*h) where `b` is the number of
> > blocks until timeout and `h` is a percentage of the hashrate controlled
> > by so-called myopic miners. Given that, here's a table of attack
> > failure probabilities:
> >
> > "Myopic" hashrate
> > B 1% 10% 33% 50%
> > l +-
> > o 6 | 5.82% 45.12% 86.19% 95.02%
> > c 36 | 30.23% 97.27% 100.00% 100.00%
> > k 144 | 76.31% 100.00% 100.00% 100.00%
> > s 288 | 94.39% 100.00% 100.00% 100.00%
> >
> > So, if I understand correctly, even a small amount of "myopic" hashrate
> > and long timeouts---or modest amounts of hashrate and short
> > timeouts---makes this attack unlikely to succeed (and, even in the cases
> > where it does succeed, Bob will have to offer a very large bribe to
> > compensate "rational" miners for their high chance of losing out on
> > gaining any transaction fees).
> >
> > Additionally, I think there's the problem of measuring the distribution
> > of "myopic" hashrate versus "rational" hashrate. "Rational" miners need
> > to do this in order to ensure they only accept Bob's timelocked bribe if
> > it pays a sufficiently high fee. However, different miners who try to
> > track what bribes were relayed versus what transactions got mined may
> > come to different conclusions about the relative hashrate of "myopic"
> > miners, leading some of them to require higher bribes, which may lead
> > those those who estimated a lower relative hash rate to assume the rate
> > of "myopic" mining in increasing, producing a feedback loop that makes
> > other miners think the rate of "myopic" miners is increasing. (And that
> > assumes none of the miners is deliberately juking the stats to mislead
> > its competitors into leaving money on the table.)
>
> A thought occurs to me, that we should not be so hasty to call non-myopic
> strategy "rational".
> Let us consider instead "myopic" and "non-myopic" strategies in a
> population of miners.
>
> I contend that in a mixed population of "myopic" and "non-myopic" miners,
> the myopic strategy is dominant in the game-theoretic sense, i.e. it might
> earn less if all miners were myopic, but if most miners were non-myopic and
> a small sub-population were myopic and there was no easy way for non-myopic
> miners to punish myopic miners, then the myopic miners will end up earning
> more (at the expense of the non-myopic miners) and dominate over non-myopic
> miners.
> Such dominant result should prevent non-myopic miners from arising in the
> first place.
>
> The dominance results from the fact that by accepting the Alice
> transaction, myopic miners are effectively deducting the fees earned by
> non-myopic miners by preventing the Bob transaction from being confirmable.
> On the other hand, even if the non-myopic 

Re: [bitcoin-dev] MAD-HTLC

2020-06-23 Thread Stanga via bitcoin-dev
Of course the order at the end should have been switched:

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


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

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

Re: [bitcoin-dev] MAD-HTLC

2020-06-23 Thread Stanga via bitcoin-dev
Hi ZmnSCPxj,

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

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

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

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

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


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

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


>
> --
>
> What MAD-HTLC can do would be to make different claims:
>
> * Inputs:
>   * Bob 1 BTC - HTLC amount
>   * Bob 1 BTC - Bob fidelity bond
>
> * Cases:
>   * Alice reveals hashlock at any time:
> * 1 BTC goes to Alice
> * 1 BTC goes to Bob (fidelity bond refund)
>   * Bob reveals bob-hashlock after time L:
> * 2 BTC goes to Bob (HTLC refund + fidelity bond refund)
>   * Bob cheated, anybody reveals both hashlock and bob-hashlock:
> * 2 BTC goes to miner
>
> This is an actual improvement over HTLC: Bob misbehavior leads to loss of
> the fidelity bond.
> The above cases can be assured by requiring both Alice and Bob to sign in
> the alice-hashlock branch, so that the splitting of the fund is enforced,
> and SegWit signing so that the dependent transaction is signed before the
> HTLC-funding transaction is.
> It can also be implemented with `OP_CHECKTEMPLATEVERIFY`.


The cases you present are exactly how MAD-HTLC works. It comprises two
contracts (UTXOs):
* Deposit (holding the intended HTLC tokens), with three redeem paths:
- Alice (signature), with preimage "A", no timeout
- Bob (signature), with preimage "B", timeout T
- Any entity (miner), with both preimages "A" and "B", no timeout
* Collateral (the fidelity bond, doesn't have to be of the same amount)
- Bob (signature), no preimage, timeout T
- Any entity 

[bitcoin-dev] MAD-HTLC

2020-06-23 Thread Stanga via bitcoin-dev
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
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev