Re: [bitcoin-dev] Is Bitcoin mempool synchronized?

[ZmnSCPxj via bitcoin-dev]

Good morning Hilda,

> Hi there,
>
> I have been assuming Bitcoin system to be well synchronized, including 
> mempools. But after being challenged, I started to think that I actually 
> cannot verify this without knocking the door of every miner in every single 
> second (just a time slice reasonable to me; stop torturing me by asking why). 
> Can anyone share any thoughts with me?


No, definitely not.

There is no good way to limit the amount of transactions someone can push at 
you, except by various heuristics.
Yet those very same heuristics mean that someone with a good knowledge of those 
heuristics can make your mempool desynchronized with that of somebody else.

Fortunately for Bitcoin, it is the blockchain itself that we synchronize on.
People cannot push blocks at you without doing the work of grinding towards the 
difficulty target, thus it is not possible to spam blocks.

TANSTAAGM - There Ain't No Such Thing As A Global Mempool

For this reason, any consensus rule has to refer only to data inside blocks, 
and never to data in mempools, are mempools are ephemeral and not synchronized 
across all nodes.

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

[bitcoin-dev] Is Bitcoin mempool synchronized?

[Hilda via bitcoin-dev]

Hi there,


I have been assuming Bitcoin system to be well synchronized, including 
mempools. But after being challenged, I started to think that I actually cannot 
verify this without knocking the door of every miner in every single second 
(just a time slice reasonable to me; stop torturing me by asking why). Can 
anyone share any thoughts with me?


Thank you,
Hilda___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli via bitcoin-dev]

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

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

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

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

Re: [bitcoin-dev] MAD-HTLC

[Stanga via bitcoin-dev]

Hi ZmnSCPxj,

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

Best,
Ittay

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

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

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