public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Stanga <stanga@gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists.linuxfoundation.org>
Cc: Matan Yehieli <matany@campus.technion.ac.il>,
	Itay Tsabary <sitay@campus.technion.ac.il>
Subject: Re: [bitcoin-dev] MAD-HTLC
Date: Sun, 5 Jul 2020 12:03:14 +0300	[thread overview]
Message-ID: <CABT1wWnFq1yt-3bbNu_8xrTFq6SWDu92-pgQdSuyP0ife5zQEg@mail.gmail.com> (raw)
In-Reply-To: <aclYsaioe3eOlsNxU1STxY6TOHstjBAsqxDKGln-D0A-p9J5-y2evQJdOe8DtWsK_iQioHxuc8J8eM8hXBihah_DudLzdKQ6mPPE8Dn5xkY=@protonmail.com>

[-- 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 --]

  parent reply	other threads:[~2020-07-05  9:03 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 ` [bitcoin-dev] MAD-HTLC 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
     [not found]                         ` <CAF-fr9YhiOFD4n8rGF-MBkWeZmzBWfOJz+p8ggfLuDpioVRvyQ@mail.gmail.com>
2020-07-04 20:58                           ` ZmnSCPxj
2020-07-05  9:03                         ` Stanga [this message]
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=CABT1wWnFq1yt-3bbNu_8xrTFq6SWDu92-pgQdSuyP0ife5zQEg@mail.gmail.com \
    --to=stanga@gmail.com \
    --cc=ZmnSCPxj@protonmail.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=matany@campus.technion.ac.il \
    --cc=sitay@campus.technion.ac.il \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
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