Reminder: zero-conf is not safe; $1000USD reward posted for replace-by-fee patch

[phelix]

As a miner I would certainly not mine at a pool that implements this practice.

It would be nice to have a neighboorhood pool watch for pools that (probably) replace transactions because of higher fees.

I hope something like this will gain ground: https://bitcointalk.org/index.php?topic=163751 Mining Codex

[1714796233]

1714796233

[1714796233]

1714796233

[1714796233]

1714796233

[killerstorm]

0-conf transactions aren't replaceable by definition. The definition is the source code and it drops double spends against the memory pool. That's the whole point - peter wants to change the definition of what a zero-conf transaction means.

It is snake oil: these rules provide no protection whatsoever, but users now erroneously believe that probability of double-spend attack is very low.

Obviously, user who wishes to double-spend can communicate directly to miners who offer this kind of service.

For example, I can implement Bitcoin Wallet Double-Spending Edition(tm) which will automatically create a double-spend for each transaction (if user ticks a checkbox) and sends a double-spending tx to a feed. Miners who wish to participate in this program will fetch transactions from this feed to get higher fees.

So "definition in the source code" is absolutely irrelevant.

Like I said, what's the downside to being laissez-faire about this? Live and let live. The market will sort it out.

Miners aren't using replace-by-fee only because they do not care much about tx fees yet. Let's see how it will work in 4 years...

By the way, I don't buy an argument that miners will care about keeping zero-conf payments somewhat secure. If zero-conf payments are accepted by merchants, then users do not care much when their tx will get into a block, so they will pay a tiny fee.

So it is in the best interest of miners to show that accepting payments with no confirmations is insecure. Then more people will try to get their transaction into block as soon as possible, paying a competitive fee.

I think it's fair to say that being unable to buy basic things like food or drinks in person would reduce the utility of Bitcoin for a lot of people.

It is crucial to buy food and drinks with plain Bitcoin transactions?

There is a plenty of options: shared wallets, green addresses, multi-signature transactions...

It is definitely possible to make payments ACTUALLY secure, it just requires a bit more effort...

[Mike Hearn]

Reality check - when I look around at the complaints people have about Bitcoin, merchants constantly being double spent doesn't come up. It isn't "snake oil" to point this out and you should give the people actually using Bitcoin more credit - they know how to avoid losses.

Your double-spending wallet edition is just theoretical - you have to find miners that will take your double spends, and then you have to find users who are willing to accept that most often their attempts to double spend will fail because the bad miners won't find the next block. And then people who use it will discover that if they aren't perfectly anonymous then they will get taken to court for wire fraud, and most likely they will lose.

So there are lots of reasons why people might not do this. And that may explain why this topic is so old and stale. It was being brought up back in 2010 and here we are, years later, people still arguing about this topic and yet there are many more thousands of merchants still accepting these transactions and not losing money.

I remember another topic that used to create endless raging arguments, the 10 minute block interval. Eventually that was solved by Charlie creating Litecoin and now people who hate the 10 minute wait can just go use that instead of creating endless forum threads. I think it's a good way to resolve such disputes - go set up an alt coin that works the way you think it should and then let the market figure it out. Or maybe the Litecoin guys would be willing to incorporate such a change.

[jdillon]

So there are lots of reasons why people might not do this. And that may explain why this topic is so old and stale. It was being brought up back in 2010 and here we are, years later, people still arguing about this topic and yet there are many more thousands of merchants still accepting these transactions and not losing money.

Double-spending is not yet much of an issue because very few merchants are vulnerable to it. You have the BlockChain.info mixer, and SatoshiDice and its clones. The latter easily respond by spending double-spend attempts 100% to fees, and proving their honesty after the fact by keeping records of the double-spend.

On the other hand, the biggest use of Bitcoin for commercial transactions is buying drugs. (I exclude BitPay's Avalon orders because they are related to the system itself) The Silk Road requires six confirmations for a deposit, and implements an off-chain transaction system for privacy and convenience.

Code:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Peter pointed out that a DoS-resistant replace-by-fee implementation requires
the implementation of either recursive fee evaluation, or strictly limiting
unconfirmed depth.

He has told me he has taken the former approach, and is done most of a
recursive fee evaluation implementation with reasonable O() scaling. Along
those lines I've increased the reward to $1000USD, again with the advice that
the reward is for a proof of concept, and rigorous engineering is not required.
4-8 days of work should be your target effort to keep hourly reasonable to the
level of a professional early in their career.

Yes Peter, you still are in competition with anyone else taking on the
challenge. I stand by my comment about what you need to do to be taken
seriously. Good luck. :)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)

iQEcBAEBAgAGBQJRdn4OAAoJEEWCsU4mNhiPI3gIAKETBQlXqi20vQ81yKT83aDM
VMGuFFSs/PApy5B+24N3+UBlLql2rGpOJlQYCYHpSdTDcIwFtnYkAGzWL2VkF7RL
Pc6xk+TUEpWiPhITvxXp2e7Mi4zX2I0GVABSC9QjhgB5257pb1ufHcTYX2oTw0EA
XQUdz8wNw1VeyZkEg5bniveIRMZ/fOP3Fb2Xqlm/BxOOw7vNWi7UwmPmUAl/leGQ
P/o+qtYCkhjILlj4x2ORa29aiIEgGvrTlqGwmibNsbjovaA4s/47kY2/CGTaRpsR
/7nRqIzuWYq+/URa1b7VKfdUp/jRGW9QsDxux0L7fIhLt6a7eEghrjZEDDoeqkE=
=DX3c
-----END PGP SIGNATURE-----

[killerstorm]

Double-spending is not yet much of an issue because very few merchants are vulnerable to it. You have the BlockChain.info mixer, and SatoshiDice and its clones. The latter easily respond by spending double-spend attempts 100% to fees, and proving their honesty after the fact by keeping records of the double-spend.

From what I've heard a lot of merchants who have physical contact with customer (e.g. a restaurant) accept payments with zero confirmations. Each time this is mentioned on reddit, somebody says "don't worry, you just need to wait a couple of seconds". Yeah, right...

Is it still possible to make transaction which is unlikely to be included into a block? Perhaps just low-priority one (freshly sent coins) and no fee.

This will likely give you at least a few hours of opportunity to pull off a double-spend. So you can start once you're already far away from this merchant physically.

Also, I doubt that merchant will notice that money disappeared and associate it with you.


Once this patch is ready I'll try to help with the front end. I'm currently working on web wallet, so double-spending might become shockingly easy =)

[etotheipi]

I've spent a lot of time thinking about this, discussing it here, and on IRC with smart people.  I have some extra clarification and context to this discussion that is worth mentioning.  Apparently, my strong argument in favor of this is equally applicable to a feature of the network I had not realized would also be broken.  Not that it changes my argument, but it does expand the breadth of consequences of accepting that this will happen (which I still strong believe is true).

We need to separate the two concepts and make sure we're talking about the same thing:

(1):  You have final transaction that is sitting in miners' memory pools, waiting to go into a block.  Now a second final transaction comes along spending one of the same inputs, but with a higher fee.   What does the miner do?  Well, the current default behavior is to drop it and mine the first transaction they see.  This is the behavior of the majority of the network right now, but there is nothing stopping individual miners/pools from modifying their source code to do the "unethical" behavior of replacing the original with the higher-fee transaction.  This is what I originally thought this thread was about:  a call for a patch to make this "worst case" equal to the "best case" to prevent the system from adapting to a false reality.

But there's another situation we would all like to depend on (and perhaps, have assumed will be usable in the future),  but which is equally subject to the above argument:

(2):  You have a non-final, replaceable transaction that is sitting in miners' memory pools, waiting for the locktime to expire so they they can mine it into a block.  Now a second transaction comes along that meets all the requirements of transaction-replacement (increased sequence numbers, etc).   The intended behavior is that the miner will drop that the original transaction and replace it with the new one.  There doesn't even have to be an increased fee, especially because it's essentially zero-cost for the miner to update their memory pool with the new tx.  However, for similar reasons above... the miner doesn't have to replace the transaction, and if there was economic incentive to mine the old one (perhaps a second transaction with a huge fee that spends an older version of the replaced tx), then there's nothing stopping them from ignoring the replacements.  The original (to-be-replaced) transactions are completely valid to mine after the locktime, leading to a standard race between good and bad miners.  This allows for one party in a HFT (rapidly-adjusted micropayment) contract to have some probability of screwing over the other party.

This is troubling, because there's a lot of cool things that become possible with transaction replacement, but nodes are not obligated to replace transactions, they only have to allow it if they want.   Fortunately, these two situations are not exactly identical.  One thing that might save #2 is if you can change the locktime on the replacement to a couple blocks sooner, to almost guarantee it can be mined by honest parties, before the older one can mined by dishonest parties.  But I don't know if you can change the locktime on a replaced transaction, and it would severely limit how many replacements could be made.  But still better than nothing...


One last thing to consider is that, in #1 the exchange is usually happening between parties that have never met and have zero-trust (or at least one direction has zero trust).  Merchant has zero trust of this random customer that just walked into the store.   But #2 has the pretense that the parties already have some association with each other, and thus >zero trust, or else they wouldn't be setting up this replaceable/contract with each other.  It doesn't stop it from happening, but it does imply that one party may have recourse if the other one screws him over

[killerstorm]

(2):  You have a non-final, replaceable transaction that is sitting in miners' memory pools,

Currently non-final transactions are treated as non-standard, so they are not added to memory pools and are not propagated.

And that's good... We are no longer restricted by transactions replacement rules. Which are no more than inconvenience: they provide no guarantees, but make it hard to use a contract which require a different kind of replacement.

[etotheipi]

(2):  You have a non-final, replaceable transaction that is sitting in miners' memory pools,

Currently non-final transactions are treated as non-standard, so they are not added to memory pools and are not propagated.

And that's good... We are no longer restricted by transactions replacement rules. Which are no more than inconvenience: they provide no guarantees, but make it hard to use a contract which require a different kind of replacement.

My post was not about how it is at this moment, but under the assumption that tx-replacement become standard at some point.  It would become standard under the assumption that it would be useful for a variety of things discussed in the community over the past couple years.  I was just pointing out that it's not so clear-cut if you assume that miners will not follow "ethical" replacement rules.

[killerstorm]

My post was not about how it is at this moment, but under the assumption that tx-replacement become standard at some point.  It would become standard under the assumption that it would be useful for a variety of things discussed in the community over the past couple years.  I was just pointing out that it's not so clear-cut if you assume that miners will not follow "ethical" replacement rules.

If there are miners who do not follow "ethical" rules than the whole concept of replacement rules is completely useless as these rules cannot be relied on.

So we have two scenarios:

1. all miners are ethical: thus you can completely
2. some miners are not ethical: you cannot rely on replacement rules

Are you talking about third case where miners can violate some rules, but always honor other? Half-ethical miners?

[etotheipi]

My post was not about how it is at this moment, but under the assumption that tx-replacement become standard at some point.  It would become standard under the assumption that it would be useful for a variety of things discussed in the community over the past couple years.  I was just pointing out that it's not so clear-cut if you assume that miners will not follow "ethical" replacement rules.

If there are miners who do not follow "ethical" rules than the whole concept of replacement rules is completely useless as these rules cannot be relied on.

So we have two scenarios:

1. all miners are ethical: thus you can completely
2. some miners are not ethical: you cannot rely on replacement rules

Are you talking about third case where miners can violate some rules, but always honor other? Half-ethical miners?

#2 was jdillon's original point, and the one I was supporting.  But not in the context of non-final transactions -- I thought the post was about replacing already-final transactions, and I was pointing out there was no way to avoid some miners doing it, and thus undermining the usefulness of them.

But five posts back, I was pointing out my own revelation that any such arguments as made in #1 (already final tx), are necessarily applicable to #2 as well (replaceable tx).  And pointing out to readers that there are two distinct contexts here, that have been kind of jumbled together in this thread.   This revelation bothers me a bit, because the fact that already-final zero-conf tx are useless was not news to me.  But the fact that tx replacement may also be useless for the same reasons is unfortunate.  I hadn't considered that the same arguments applied.  

But I don't think it's a lost cause.  It's feasible that such transactions/contracts are useful enough because they aren't typically made between zero-trust parties... usually there is some degree of association between them, and the quantities of money at stake doesn't have to be very high.  And perhaps, if you only plan a couple dozen replacements, it still works as long as you reduce the locktime each time.  

It was really just food for thought.

[killerstorm]

This revelation bothers me a bit, because the fact that already-final zero-conf tx are useless was not news to me.  But the fact that tx replacement may also be useless for the same reasons is unfortunate.  I hadn't considered that the same arguments applied.  

1. Non-final transactions are still useful, you just shouldn't assume that you get automagic protection against double-spends.
2. You can protect against double-spends from your counter party using multi-signature scripts.

Basically, contracts which assume that double-spending is not possible are sloppily designed. Rewrite them in such a way that multi-signature script will be used, and they will become safe.

Moreover, they will become safe and implementable RIGHT NOW, not in a hypothetical future with ethical miners.

Any contract which relies on transaction replacement rules can be made secure with help of a third party.

So, basically, you do not need to rely on all miners being honest. You just need to rely on a third party which can be chosen by both parties of contract.

As a bonus, fidelity bond can be used to make sure that third party has incentive to be honest. So you can locally emulate features of proof-of-stake system.

[killerstorm]

Here's the theory, as I see it:

To make sure that "transaction replacement rules" actually work, you need to discourage miners from breaking them. For example, punishing them in some way.

 * Proof-of-work system must follow one main rule: longest valid chain wins. If you add other rules it becomes less stable. So it is hard, or even impossible, to add punishment as a rule, and you cannot punish miners in any other way because they are anonymous.
 * In proof-of-stake system punishment is very straightforward: if there is evidence that miner have broken the rule, his stake is just destroyed.

Thus proof-of-stake system is more flexible: it allows you to create pretty much arbitrarily complex rules as long as they are verifiable using cryptography.

Multi-signature scripts and fidelity bonds allow us to create an emulation of proof-of-stake system within proof-of-work system.

So I think it would be great if people abandon fantasies about "transaction replacement rules" and will instead listen retep: his ideas are much more sound and implementable.

[TierNolan]

* Proof-of-work system must follow one main rule: longest valid chain wins. If you add other rules it becomes less stable. So it is hard, or even impossible, to add punishment as a rule, and you cannot punish miners in any other way because they are anonymous.

You should mine on the chain that most likely has most of the miners on it.

Apparently, if you paint the horns of a prey animal, it greatly increases the chances of them being killed by predators.  The reason is that it helps coordination between the predators.  They don't have to communicate to pick a target, which can be helpful for stealth.

The same thing works with blocks.  The highest POW block is "painted" by custom, and so all try to build on it.

However, miners might be willing to mine on older blocks if the tx fees are high enough.

For example, imagine there was a block with a 500BTC tx fee (maybe a donation to miners or someone messed up).

You could build on that block and get nothing, or build on the previous block and possibly get the the fee.  If you win, maybe you pay out some of the tx fee to "true".  Paying to true is the same as paying to fee, since the next miner gets to direct it to their own address.

Maybe a miner might take the viewpoint that they should scan back along the blocks.

The latest block is block X and the previous blocks paid the following fees.

X-4) paid 27 in fees
X-3) paid 26 in fees
X-2) paid 1000 in fees
X-1) paid 29 in fees
X) paid 26 in fees

The "selfish" POW could be calculated as (block fees - (average fee)*depth).  That gives the X-2 block the highest POW.

If most miners use the selfish POW, then it fulfils itself.  Most will build on X-2, so you would be a fool to build on X.

What you want is a rule that is a Nash equilibrium.  It is in the best interests of a miner to stick to their current strategy as long as nobody else changes theirs.

Breaking ties against blocks that violate the customs adds an incentive to not break them.

A feature of the selfish POW is that it allows donors to dump fees into one block and forces miners to share them with later blocks.  If you take more than the average, then miners won't build on your block.

[Maged]

One last thing to consider is that, in #1 the exchange is usually happening between parties that have never met and have zero-trust (or at least one direction has zero trust).  Merchant has zero trust of this random customer that just walked into the store.

Why is this assumed to be true? Credit cards have proven that you can calculate a non-zero amount of trust for a large group of people. In fact, "pay-what-you-want" schemes, where each customer is trusted completely have also shown to be somewhat successful. Not everyone needs a system that requires zero-trust, so why should they be forced into one? Because of things like successful "pay-what-you-want" schemes working well-enough, I suspect that even if this patch was included in every Bitcoin client, some merchants would still depend on zero-conf transactions because they trust that their users will usually not reverse their transactions. A music store, for instance, might do that. All this would do is weaken the system.

[etotheipi]

One last thing to consider is that, in #1 the exchange is usually happening between parties that have never met and have zero-trust (or at least one direction has zero trust).  Merchant has zero trust of this random customer that just walked into the store.

Why is this assumed to be true? Credit cards have proven that you can calculate a non-zero amount of trust for a large group of people. In fact, "pay-what-you-want" schemes, where each customer is trusted completely have also shown to be somewhat successful. Not everyone needs a system that requires zero-trust, so why should they be forced into one? Because of things like successful "pay-what-you-want" schemes working well-enough, I suspect that even if this patch was included in every Bitcoin client, some merchants would still depend on zero-conf transactions because they trust that their users will usually not reverse their transactions. A music store, for instance, might do that. All this would do is weaken the system.

Because that was the goal of Bitcoin, to remove the requirement for pre-existing trust between transacting parties without a third-party.  That's how it's advertised.  I have no dispute with your statement that a lot of transactions happen right now that don't actually require zero-trust.  But if the system fails to meet that criteria in some contexts (like expecting your transaction to be replaced when it actually may not), users should be uniquely aware that it's not a good option for zero-trust situations.

Trust can go to zero as confirmations go to infinity.  But before inifinite confirmations, you have to have a trade-off between that security and the convenience/functionality.  The point of my post was to state the revelation that rapidly-adjusted micropayments are not trustless the way it was originally suggested.  It's critical to know that the next time I transact with someone in Nigeria, I do not use that technique.  

Your point is that it's not useless.  I agree -- I don't think it's useless.  I just think it's worth mentioning that it shouldn't be used in zero-trust situations.  And luckily, most people who would be using this, already have some degree of trust.  So it's not so bad, just use it carefully.

[killerstorm]

What you want is a rule that is a Nash equilibrium.  It is in the best interests of a miner to stick to their current strategy as long as nobody else changes theirs.

Well... What if there is some sort of collusion among majority of miners (i.e. they have more than 50% of hash power combined): they will agree to decide block to mine on top of using some set of rules and some sort of a practical Byzantine fault tolerant algorithm for synchronization?

They can simply drop blocks of miners which do not agree to participate in this PBFT-synced collusion, and as far as I can tell it is stable as long as colluding miners have a majority. (I'm not quite sure about that, but I guess it will be 'stable enough' for practical purposes.)

Within this collusion pretty much arbitrary rules can be enforced.

[TierNolan]

What you want is a rule that is a Nash equilibrium.  It is in the best interests of a miner to stick to their current strategy as long as nobody else changes theirs.

Well... What if there is some sort of collusion among majority of miners (i.e. they have more than 50% of hash power combined): they will agree to decide block to mine on top of using some set of rules and some sort of a practical Byzantine fault tolerant algorithm for synchronization?

A Nash equilibrium doesn't require any collusion at all.  It is something that just happens.

For example, lets say you play a game.  No communication is allowed between players and their moves are secret.

Each player picks a number from 1 to 10.  The results are announced and the players that picked the most popular number (say 7) are given $5.

The game is repeated, what number do you think will win?

Next, the referee says "For the next round, I strongly recommend 4.  You can still vote for any of the 10, but really, 4 is a great number".  Which one do you think would win?  7 might still win, but 4 has a pretty good chance.

They can simply drop blocks of miners which do not agree to participate in this PBFT-synced collusion, and as far as I can tell it is stable as long as colluding miners have a majority. (I'm not quite sure about that, but I guess it will be 'stable enough' for practical purposes.)

You don't need a majority.  Say there is one pool which has 10% of the power and they say that they will queue all blocks that have the 2nd (or later) of a double spent transaction in them for 5 minuted before building on them.

Other miners now know that if they add those txs into their blocks, only 90% of the hashing power of the network will build on them for the first 5 minutes.

Within this collusion pretty much arbitrary rules can be enforced.

There are limits before the Nash equilibrium breaks down. 

Simple Nash equilibrium are the best.  That is why build on the highest POW chain is so strong.

However, as I show in my previous post, with large fees, that Nash equilibrium can break down.

[jdillon]

#2 was my jdillon's original point, and the one I was supporting.  But not in the context of non-final transactions -- I thought the post was about replacing already-final transactions, and I was pointing out there was no way to avoid some miners doing it, and thus undermining the usefulness of them.

You mention that some miners may not honor replacement undermining the usefulness.

But remember they may not honor replacement not because of any decision by them but because of limitations of technology. Old software is obvious. Slow network connections is another.

Part of what worries me about zero-conf is that if people rely on it rules may be put into place that punish miners who  fail to honor replacements or detect double-spends because they happen to be behind bandwidth constrained network connections and simply did not get the information that other, larger, more centralized miners did.

It is ironic that unavoidable technical limitations means that with unlimited blocksizes zero-confirmation transactions definitely will not be safe requiring all the decentralized trust required by the off-chain transactions that make large blocks unrequired.

[jdillon]

An initial implementation is available for testing.

See new thread here: https://bitcointalk.org/index.php?topic=199947.0

[jonytk]

It should never allow you to reemplace a transaction, or to change outputs,
it should allow you to give more priority to a transaction that it's stuck on the limbo of 0 fee/smaller fee transactions.

Only replace the transaction if it's the same transaction with bigger fee. to the same outputs.

Any other thing is not bitcoin, btc is not reversible.
or you just killed satoshi dice.

But talking about improving you could also change the 10 min confirmation to 2 and slash the rewards 5 times.
then they will change to a 1or 2 confirmations .