[Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Sergio Lerner]

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

I would like to share with you a vulnerability in the Bitcoin protocol
I've been thinking of which might have impact on the future of Bitcoin.
Please criticize it!

*The Freeze on Transaction Problem
*

The freeze problem occurs if someone publishes a transaction with fees
much higher than the block subsidy. I don't remember who described the
attack first. Suppose that, by mistake, a transaction is published with
50 BTC in fees. The transaction is included in a block at height n. If
everyone acts rationally in his own interest, then the best choice for
the remaining miners is to try to mine a competing block at the same
height n including the high-fee transaction, to collect the fee for
themselves. All the miners having solved the block at height n, now move
on mining at height (n+1). But they won't choose each other branches
until one branch is sufficiently longer so that it is better to switch
to it and abandon their own branch rather than try to keep the block
with the high fee. This case is different from the real block
competition case we see periodically on the blockchain, where the miners
are generally split between two branches. Here there are multiple
branches competing. If there are 10 "top" miners each having 10% of the
network hashing power, then 10 different branches will compete. The
analysis for this case is similar to the Gambler's Ruin problem analysis
present in the Satoshi paper, but with a fixed constant monetary
incentive not to switch. Since the incentive to switch grows
exponentially with the branch length difference, any initial constant is
diluted. In the special and rare case that all the miners have exactly
the same hashing power, then the network diverges, and this is
equivalent as having two miners having exactly 50% of the hashing power
each. So in principle the freeze on transaction problem is just a
temporary disruption in the network, but not a fatal halt. Nevertheless,
since during the freeze period each miner is mining on his own branch,
it also means that moving forward with blocks is a lot slower. Assuming
10 miners having 10% of the total hashing power each (+/- 3%), the
network becomes 10 times slower. I simulated it with a 50 BTC tx freeze
fee, and 10 miners, and it takes approximately 6 blocks to converge, so
the freeze time is approximately 60 times the block interval, or 10
hours. If the distribution is approximately 25% of the hashing power for
each top miner, the freeze time is 4 hours.

Obviously what's needed for the freeze problem to occur is that miners
are 100% rational, greedy and prepared. They need to have a modified
version of bitcoind which can automatically detect a high-fee
transaction and prevent adding to the best chain a not-owned block
containing such transaction. There will be no time for the miners to
patch bitcoind if such transaction is manually spotted. Also the latest
versions of bitcoind have preventions not to allow high fees by mistake.
So the freeze problem is currently non-existent, but may pop up in the
future in form of a state-sponsored attack.

*The Freeze problem as an Attack*

If an attacker plans to repeat such attack periodically at the expense
of wasting a lot of BTC, there is little the current protocol can do,
because miners will be prepared to take advantage of the attack. If the
attacker issues a new fee burning transaction before the network
converges, then the attacker can maintain incentives to keep every miner
separated in his own branch. So wasting 50 BTC every 4 hours, an
attacker can maintain the network frozen forever.  Even if we restrict
the maximum fee per transaction, the scripting system has infinite ways
to create transactions whose output can be taken by anyone, and the
attacker can announce the method miners can use to collect those BTC and
even prepare and publish the bitcoind patches to automate collecting
those transaction outputs.

The best thing the community can do is act together and cooperate to
share the high transaction fee. This will neutralize the attack
completely and allow miners to earn extra bitcoins. But cooperation in
the Bitcoin community has never been easy. There is a technical solution
which is to modify the Bitcoin protocol so that every transaction output
has a maturity time of 6 blocks, and if a transaction output is redeemed
multiple times in a 6 block interval, then the BTC amount is split
between all redeemers, and also fees would be automatically shared in a
6 block sliding window. At a first glance, this provides a way for
miners to cooperate even anonymously and there is no immediate drawback,
but an in depth analysis is necessary.


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

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Gregory Maxwell]

On Sun, Oct 5, 2014 at 4:00 PM, Sergio Lerner <sergiolerner@certimix.com> wrote:
> I would like to share with you a vulnerability in the Bitcoin protocol I've
> been thinking of which might have impact on the future of Bitcoin. Please
> criticize it!
> The Freeze on Transaction Problem

I should point you to some of the tools that have been discussed in
the past which are potentially helpful here:

The first is the use of locktime on normal transactions.  This
behavior is already in Bitcoin core git:   The idea is that users of
the system should locktime their transaction at a point as high as
they expect it to get included.  If used well this means that there
should always be a base of fees which can only be collected by future
blocks, creating an incentive to move forward.  This may be
particularly effective if the limitations on blocksize mean that there
is always a healthy standing load.

The second is having block commitments in transactions
(https://en.bitcoin.it/wiki/User:Gmaxwell/alt_ideas). The idea is that
the data under signature in a transaction could commit to some recent
block which _must_ be in the chain or the transaction's fee cannot be
collected (or, at least, not all of the fee).  This would allow
transacting users to 'vote with their fees' on the honest chain.
Arguably this could also be used to pay for doublespending forks, but
you can already do that by paying fees via a chain that stems from the
doublespend.  This greatly complicates strategy for forking miners,
since future transactions which you haven't even seen yet may have
fees conditional on the honest chain.

I think both of the above are obviously useful, should be done, but
don't completely address the concern, they may be adequate.

The third is fee forwarding.  An example form would be that the miner
gets half the fees, the rest are added to a pool which pays out half
in every successive block.  This can prevent unusually high fees from
making as much reorg pressure and more correctly models what people
would like to pay for: getting their txn buried.   The huge problem
with this class is that miners can demand users pay fees "out of
band", e.g. with additional txouts (just make a different version of
the tx for each miner you wish to pay) and escape the process.  I have
had some notions about fees that come in the form of adjusting the
difficulty of creating a block slightly (which is something that can't
be paid out of band), but such schemes becomes very complicated very
fast.  I am unsure if any form of fee forwarding is workable.

Something you might want to try to formalize in your analysis is the
proportion of the network which is "rational" vs
"honest"/"altruistic".  Intuitively, if there is a significant amount
of honest hashrate which is refusing to aid the greedy behavior even
at a potential loss to themselves this strategy becomes a loser even
for the purely greedy participants. It would be interesting to
characterize the income tradeoffs for different amounts of altruism,
or whatever convergence problems an attempt by altruistic
participaints to punish the forkers might create.

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Gregory Maxwell]

On Sun, Oct 5, 2014 at 4:40 PM, Gregory Maxwell <gmaxwell@gmail.com>
> I should point you to some of the tools that have been discussed in
> the past which are potentially helpful here:

Ah, I should also mention a somewhat more far out approach which helps
here as a side effect:

If transactions were using the BLS short signature scheme (a very
compact EC signature based on pairing cryptography) there is a scheme
so that you securely can aggregate the signatures from multiple
messages into a single signature (also has nice bandwidth properties)
and still verify it. It also works recursively, so aggregates can be
further aggregated.

A consequence of this is that you cannot remove a (set of)
signature(s) from the aggregate without knowing the (set of)
signature(s) by itself.

If the coinbase transaction also contains a signature and if some
non-trivial portion of fee paying users relayed their transaction
privately to miners it,  then other miners would only learn of the
transaction in aggregated form.  Without knowing the transaction by
itself they could not pull it out of a block separately from the
coinbase payment and add it to their own block in a fork.

(In general this provides several anti-censorship properties, since if
someone passed you an aggregate of several transactions you could only
accept or reject them as a group unless you knew the members
separately).

The use in aggregation can be done in a way which is purely additive
(e.g. in addition to regular DSA signatures), so even if the
cryptosystem is broken the only harm would be allowing
disaggregation... but unfortunately the pairing crypto is pretty slow
(verification takes a 0.5ms-ish pairing operation per transaction).

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Jorge Timón]

On Mon, Oct 6, 2014 at 1:40 AM, Gregory Maxwell <gmaxwell@gmail.com> wrote:
> Something you might want to try to formalize in your analysis is the
> proportion of the network which is "rational" vs
> "honest"/"altruistic".  Intuitively, if there is a significant amount
> of honest hashrate which is refusing to aid the greedy behavior even
> at a potential loss to themselves this strategy becomes a loser even
> for the purely greedy participants. It would be interesting to
> characterize the income tradeoffs for different amounts of altruism,
> or whatever convergence problems an attempt by altruistic
> participaints to punish the forkers might create.

Not only that, greedy miners may actually have an incentive to just
follow the longest chain. Say I'm a small miner and I know that the
chances of re-mining the high tx and getting that block into the
longest chain are minimal or null. Then I will probably prefer to just
mine on top of the longest chain.
So "If everyone acts rationally in his own interest, then the best
choice for the remaining miners is to try to mine a competing block at
the same height n including the high-fee transaction, to collect the
fee for themselves" is not necessarily true.
p * 50 can be lower than q * 25 if p < 2*q. P and q depend on what
everyone is doing, not just you.

In any case, it is interesting to think about this things since mining
subsidies will eventually disappear and then transaction fees will
ALWAYS be higher than subsidies.

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Gregory Maxwell]

On Sun, Oct 5, 2014 at 4:54 PM, Jorge Timón <jtimon@blockstream.io> wrote:
> In any case, it is interesting to think about this things since mining
> subsidies will eventually disappear and then transaction fees will
> ALWAYS be higher than subsidies.

You can imagine that instead of subsidy Bitcoin came with a initial
set of nlocktimed transactions that pay fees, one block at a time, for
each block from the start until the subsidy goes away.

Perhaps that mental model might make it clear why some people think
that the nlocked transactions and the block size being lower than the
instant offered demand (there is always a backlog) are both things
which address the concern of this thread. :)

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Alex Mizrahi]

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

I've heard about this idea from TierNolan. Here's some quick an dirty
analysis:

Suppose the last known block claimed a large tx fee of L. A miner who owns
1/N of the total hashrate needs to choose between two strategies:

1. Mine on top of that block and win usual reward R with probability 1/N.
2. Mine on top of the previous block, trying to make two blocks in a row,
might get reward L with probability 1/N^2.

Thus for the first strategy expected payoff is R/N, and for the second the
expected pay-off is L/N^2.

Second strategy is viable if R/N < L/N^2,
 R < L/N.

Now suppose the miner who claimed the unusually large reward will share it
with the next miner, for example, using coinbase output with OP_TRUE. If
that shared reward Rs is higher than L/N^2, then the next miner will be
better off mining on top of that block.

This doesn't require protocol changes(*) and can be simply incorporated
into a piece of code which decides what to do when a transaction with
unusually large fee appears. (I.e. it will automatically share the fee, and
others will recognize that). And if the biggest miner has 25% of all
hashrate, sharing 25% of your loot doesn't sound that bad.

(*) Except one problem: coinbase maturity rules won't allow one to share
the fee with the next miner.
So some protocol changes are required. But changes which affect coinbase
maturity and sharing are probably going to be simpler and smaller than what
Sergio have proposed.

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

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Mike Hearn]

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

>
> the block size being lower than the instant offered demand (there is
> always a backlog) are both things which address the concern of this thread.
> :)


I'm skeptical such a situation can ever be stable. People have no incentive
to create a transaction that will remain stuck in the backlog forever,
regardless of the effect it may have on the rest of the system.

If someone invents a business model in which lots of payments are made,
with fees, but that only clear probabilistically, perhaps such a situation
could occur. But otherwise I think we have to assume that people won't make
transactions that will lose the competition game, and instant demand would
only ever be roughly equal to supply.

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

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Tamas Blummer]

Note that the problem might arise also by a bug / accident and not as an attack.

Since value spent is not part of the signature it is easy to create an arbitrary fee by a defective wallet software.
Collecting that huge fee might provide a higher incentive to miner than the block subsidy on the trunk.

Assuming miner are fully rational, they might even form a temporary coalition to claim the fee:
The miner who mines forking block might offer part of the fee gained in a similar transaction to
other miners, so they help to extend his fork. A sufficiently high stake could trigger a long
fork “battle” of ad-hoc coalitions.

Addressing the known bug of the signature hash, that it does not include the value spent,
would have other positive effects, e.g. for resource limited hardware wallets.

Interpretation of an OP_NOP for a value hashing signature check were suggested by Alan Reiner
discussed earlier on bitcointalk.

Tamas Blummer

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Sergio Lerner]

Comments between lines...

On 06/10/2014 03:42 a.m., Alex Mizrahi wrote:
> .....
>
> This doesn't require protocol changes(*) and can be simply
> incorporated into a piece of code which decides what to do when a
> transaction with unusually large fee appears. (I.e. it will
> automatically share the fee, and others will recognize that). And if
> the biggest miner has 25% of all hashrate, sharing 25% of your loot
> doesn't sound that bad.
The problem with this approach is that once the bitcoind has been
modified to allow this sharing of the high-tx fee by delegation, then
the same system can be used for an attack.
Let's call a system that makes the Optimum Rational Best-chain Selection
for maximizing profit "ORBS", just to give it a name. The system assures
that the best chain chosen is always the optimum in terms of profit,
taking into account fee delegation and all the game-theoretic incentives
derived. It's only a theoretical abstraction, but could be approximated
in practice.

The attack is called Chained Kickback DOuble-spend attack (or “CHAKIDO”)
and is an extension of Bonneau's kickback attack. Basically the attack
is to create the ORBS patch, and start convincing miners to use it,
sending some probe high-fees tx.
Once you have ORBS working in a majority of the mining nodes, you can
perform a double-spend against a target like an exchange by:
- Buy some btc X
- Send those btc to an exchange (suppose the exchange requires 6
confirmations) in a transaction TX
- Immediately convert those btc to an alt-coin, and collect the alt-coins
- Create a high fee tx that is a double-spend of TX having a high fee Y
such that Y < X but Y triggers a ORBS reorganization.
- Profit
(This rollback attack was performed against whitecoin, I think)

This attack gets terrible powerful if there is no subsidy. You may need
500 blocks of confirmation to protect from a 10 BTC spend with current
fees and no subsidy. This is because once 100% of the nodes use ORBS,
the fee delegation is linear (it doesn't grow exponentially with the
number of blocks). So ORBS should never be implemented without
additional protective measures in merchant applications.
If we had a closed formula for ORBS, then all merchants could compute
the minimum confirmation blocks such that always Y > X, but such formula
involves many unknowns which would need to be dynamically estimated, and
also it should take into account the number of simultaneous payment
attempts.

My conclusions are:
- We should never allow ORBS to be implemented unless merchants are also
aware of it. If are aware of ORBS then Bitcoin with no subsidy will be
become a terrible slow payment system so ...
- We could implement the protections that work even if some nodes
implement ORBS, such as fee and burn btc sharing, as I described before
- Or we need some high percentage of miners to be irrational, to force
ORBS fee delegation have an exponential decay.

Best regards,
Sergio.

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Tamas Blummer]

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

Sergio,

you can call this an ORBS attack or an attempt of ad-hoc coalition forming for a fork.

Preparation Step:
Include a transaction sending a sizable amount between two of your own addresses in every block.
Miner can do this at zero cost in their own blocks.

Execution:
Embed into the preferred fork a transaction double spending the regular do-nothing transaction with one that offers a sufficiently high fee. This offers inceptive to rational miner to join the ad-hoc coalition for that fork.

Attempting to form an ad-hoc coalition using above steps is open to anyone, just cheaper and easier to execute for a miner. 

Fortunately cost for (cumulative) proof-of-work creates a lower bound to the incentive that need to be offered. So your worry
of times where block subsidy is low is unwarranted as cost of POW will be high.

I do not think “disallowing” the implementation of rational mining is a viable option, since no one needs permission to implement whatever optimization he thinks is profitable and within the rules.

Tamas Blummer

[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 496 bytes --]

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Mike Hearn]

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

>
> Yes, you're right. I didn't consider that case. But the problem is that
> this is not automatic. Currently there is a clear division between
> miners how will not take the kickback (irrrational) and miners who will
> (rational).


This seems to come up a lot. Your definition of rational is a short term
rationality only. I can pass up a short term profit in return for more
stable longer term profits and be completely rational, by a reasonable
definition of the word.

I think it's clear by now that if most or even some miners decide to
prioritise short term profit over the long term health of the system (i.e.
longer term profit), Bitcoin basically doesn't work right. This attack is
only one of several such things that can happen. This certainly can be a
problem when difficulty is skyrocketing because a mining investment is I
guess quite short term anyway, but presumably at some point the mining arms
race will end and miners will become more settled in.

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

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Sergio Lerner]

On 07/10/2014 04:16 p.m., Gregory Maxwell wrote:
> Then I spend the output of the fraudulent spend nlocked
> one block higher, and spend the output of that one again, nlocked one
> block higher, and so on... each step paying fees.
Yes, you're right. I didn't consider that case. But the problem is that
this is not automatic. Currently there is a clear division between
miners how will not take the kickback (irrrational) and miners who will
(rational).
If somebody modifies the bitcoind to make this choice automatic, then
DECOR+ is the only solution I know about to avoid people doing anonymous
double-spends (with chained kickbacks, as you mention).
The  "locktime on normal transactions" you proposed does not solve the
problem, just diminishes it in a constant value (which currently is very
low)

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Gregory Maxwell]

On Tue, Oct 7, 2014 at 7:04 PM, Sergio Lerner <sergiolerner@certimix.com> wrote:
> Using the my previous terminology, automatic fee-sharing ("ORBS") is a
> solution to the freeze problem ("FRONT") but opens the windows to
> "CHAKIDO" double-spending. and CHAKIDO double-spending is a much worse
> problem than FRONT.

I'm not following this. Perhaps I'm getting lost in terminology here.

It's already to provide double spending bounties to greedy-rational
miners, via a simple approach that has been known since at least early
in 2011.    I pay someone then create a later fraudulent doublespend
which is nlocked at the height the original payment occurred, paying
large fees. Then I spend the output of the fraudulent spend nlocked
one block higher, and spend the output of that one again, nlocked one
block higher, and so on... each step paying fees.

A hypothetical purely greedy miner which considers all sequences of
acceptable forks and transactions would see that they have higher
expected returns assisting the theft (assuming the honest party
doesn't fight back by also adopting a similar strategy), at least if
the population of greedy miners is large relative to altruistic ones.

I don't see how miners being able to roll forward fees makes anything
worse, since the transactions themselves can also roll forward fees.

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Sergio Lerner]

On 06/10/2014 08:43 p.m., Tom Harding wrote:
> On 10/5/2014 4:00 PM, Sergio Lerner wrote:
>> If everyone acts rationally in his own interest, then the best choice
>> for the remaining miners is to try to mine a competing block at the
>> same height n including the high-fee transaction, to collect the fee
>> for themselves.
>
> Sergio --
>
> Just some thoughts on your interesting problem.
>
>
> Since everybody but M10 is on equal footing, I would expect M10 to
> have some fixed advantage depending on assumptions, and the bigger the
> advantage, the shorter the "freeze time".
>

Yes, that's how simulation works. The problem is that the existence of
high-fee delays the decision to switch to M10. Since the network is
moving slower (because of fragmentation) the effect of the high-fee is
twofold: it delays the convergence because it promotes selfishness and
it delays convergence because it promotes fragmentation.

During that time window where the network is frozen, any other high-fee
transaction only makes things worse.  This is a very rare example where
a well distributed network (100 miners having 1% each) is much much
worse than 3 miners having 33% each.

Using the my previous terminology, automatic fee-sharing ("ORBS") is a
solution to the freeze problem ("FRONT") but opens the windows to
"CHAKIDO" double-spending. and CHAKIDO double-spending is a much worse
problem than FRONT.
But as Tamas pointed out, sooner or later someone will implement
something like ORBS, get over the critical mass of miner adoption, and
then the CHAKIDO problem will be inevitable.

The only clean solution to this problem is the DECOR+ protocol, which
shares block-rewards by including "uncles" (as GHOST does) and splitting
the reward between all miners at the same height until coinbase maturity
is over. This way the best choice is always cooperative.

PS: Using so many acronyms makes arguments much more concise, but
suggest we should have all the attack terminology described in a single
"Bitcoin Security Wiki"...