From: ZmnSCPxj <ZmnSCPxj@protonmail•com>
To: Itay Tsabary <sitay@campus•technion.ac.il>
Cc: Bitcoin Protocol Discussion
<bitcoin-dev@lists•linuxfoundation.org>,
Matan Yehieli <matany@campus•technion.ac.il>
Subject: Re: [bitcoin-dev] MAD-HTLC
Date: Fri, 03 Jul 2020 12:38:37 +0000 [thread overview]
Message-ID: <aclYsaioe3eOlsNxU1STxY6TOHstjBAsqxDKGln-D0A-p9J5-y2evQJdOe8DtWsK_iQioHxuc8J8eM8hXBihah_DudLzdKQ6mPPE8Dn5xkY=@protonmail.com> (raw)
In-Reply-To: <CAF-fr9Z7Xo8JmwtuQ7LE3k1=er+p7s9zPjH_8MNPwbxAfT1z7Q@mail.gmail.com>
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
next prev parent reply other threads:[~2020-07-03 12:38 UTC|newest]
Thread overview: 27+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <CABT1wW=X35HRVGuP-BHUhDrkBEw27+-iDkNnHWjRU-1mRkn0JQ@mail.gmail.com>
2020-06-23 6:41 ` Stanga
2020-06-23 9:48 ` ZmnSCPxj
2020-06-23 12:47 ` Stanga
2020-06-23 13:18 ` Stanga
2020-06-25 1:38 ` ZmnSCPxj
2020-06-25 3:26 ` Nadav Ivgi
2020-06-25 4:04 ` ZmnSCPxj
2020-06-25 4:35 ` Nadav Ivgi
2020-06-25 13:12 ` Bastien TEINTURIER
2020-06-28 16:41 ` David A. Harding
2020-07-04 21:05 ` ZmnSCPxj
2020-06-28 12:15 ` David A. Harding
2020-06-29 11:57 ` Tejaswi Nadahalli
2020-06-29 18:05 ` ZmnSCPxj
2020-06-30 6:28 ` Stanga
2020-06-30 6:45 ` Tejaswi Nadahalli
2020-07-01 16:58 ` ZmnSCPxj
2020-07-02 12:22 ` Tejaswi Nadahalli
2020-07-02 16:06 ` ZmnSCPxj
2020-07-03 9:43 ` Tejaswi Nadahalli
2020-07-03 10:16 ` ZmnSCPxj
2020-07-03 10:44 ` Tejaswi Nadahalli
[not found] ` <CAF-fr9Z7Xo8JmwtuQ7LE3k1=er+p7s9zPjH_8MNPwbxAfT1z7Q@mail.gmail.com>
2020-07-03 12:38 ` ZmnSCPxj [this message]
[not found] ` <CAF-fr9YhiOFD4n8rGF-MBkWeZmzBWfOJz+p8ggfLuDpioVRvyQ@mail.gmail.com>
2020-07-04 20:58 ` ZmnSCPxj
2020-07-05 9:03 ` Stanga
2020-07-06 11:13 ` Tejaswi Nadahalli
2020-07-02 12:39 ` Tejaswi Nadahalli
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='aclYsaioe3eOlsNxU1STxY6TOHstjBAsqxDKGln-D0A-p9J5-y2evQJdOe8DtWsK_iQioHxuc8J8eM8hXBihah_DudLzdKQ6mPPE8Dn5xkY=@protonmail.com' \
--to=zmnscpxj@protonmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=matany@campus$(echo .)technion.ac.il \
--cc=sitay@campus$(echo .)technion.ac.il \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox