[Bitcoin-development] 0 confirmation txs using replace-by-fee and game theory

[Bitcoin-development] 0 confirmation txs using replace-by-fee and game theory

[Jorge Timón]

Here is a solution to the problem of having 0 confirmation
transactions that relies on game
theory and most miners implementing replace-by-fee and child-pays-for-parent.

This has been proposed before
http://sourceforge.net/p/bitcoin/mailman/message/30876033/
I'm just going to describe the general idea in more detail.

Here's a small draft on how this could work:

Alice goes to Bob's store and wants to buy something cheaper than a
car, say a smartphone.
So Bob says, "it's 200 usd in btc, please pay me 400 usd in btc"
So Alice signs a tx with 400 and no fee with her old phone and she
just sends it to Bob rather than the network.
Bob creates a child transaction keeping 200 and giving 199.9 (0.1 usd
fee) back to Alice.

But you know, Alice wants to double spend.
She double spends 399.8 to herself (0.2 fee)
Bob thinks "last chance", he double-spends the child: 200 to Bob, back
199 to Alice (1 usd fee).
Alice is stubborn: 398 to Alice (2 usd fee).
Bob is really pissed off, double spends the child: 400 in fees.

So, ok, Bob lost the phone and got nothing but Alice has paid twice as
she needed for the phone.
Nobody's happy thus everybody's happy.

This is similar to the general game theory "stag hunt" case.
The payoff matrix could be something like this:

                        Bob returns change   Bob burns in fees
 ---------------------+--------------------+-------------------
  Alice behaves         + 1 , + 1            - 1, + 1
 ---------------------+--------------------+-------------------
  Alice double-spends   + 3, - 1             - 1, - 1

The game has two Nash equilibria, but cooperation is Pareto efficient.

Replace-by-fee and child-pays-for parent cannot be prohibited by a
protocol rule.
I believe all miners will eventually implement these policies because
it is the more rational way for them to prioritize transactions.
Finally I hope they do because it would make 0-confirmation
transactions possible as described in this post.
So I can't find any reasoning against replace-by-fee unless my example
is terribly flawed.
Am I missing something?

-- 
Jorge Timón

http://freico.in/

Re: [Bitcoin-development] 0 confirmation txs using replace-by-fee and game theory

[Mike Hearn]

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

>
> Am I missing something?


The scheme you described does nothing about Finney attacks, which is the
issue presently faced.

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

Re: [Bitcoin-development] 0 confirmation txs using replace-by-fee and game theory

[Chris Pacia]

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

This scheme would discourage people from attempting a Finney attack because
they would end up worse off if they did.

It would work but it's an ugly hack IMO. What do people do if they don't
have extra to pay when making a purchase? I have 200 mbtc and want to buy a
200 mbtc phone but I can't because I need 400 mbtc. Sucks for me.

I would much prefer the hassle of a green address notary than always having
to make sure I have double what I need to make a purchase.
On Apr 24, 2014 7:55 AM, "Mike Hearn" <mike@plan99.net> wrote:

> Am I missing something?
>
>
> The scheme you described does nothing about Finney attacks, which is the
> issue presently faced.
>
>
> ------------------------------------------------------------------------------
> Start Your Social Network Today - Download eXo Platform
> Build your Enterprise Intranet with eXo Platform Software
> Java Based Open Source Intranet - Social, Extensible, Cloud Ready
> Get Started Now And Turn Your Intranet Into A Collaboration Platform
> http://p.sf.net/sfu/ExoPlatform
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>

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

Re: [Bitcoin-development] 0 confirmation txs using replace-by-fee and game theory

[Mike Hearn]

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

>
> This scheme would discourage people from attempting a Finney attack
> because they would end up worse off if they did.
>
Phrased another way, it simply makes every block a Finney attack that
charges the maximum double spending fee possible. This doesn't solve the
problem.

Beyond needing to double balances, what if the shop is selling me a phone
on contract? So the actual cost of the phone is lower than the real price
on the assumption of future revenue. Alice double spends (aka steals) the
phone, paying double the artifically lower cost but still making a good
saving. Bob does not end up with "nothing", he ends up in the red.

But there's a much simpler way to dispose with this idea. Jorge, go down to
your local bars and cafes, and ask them if they'd be willing to accept a
form of payment that allows anyone to steal from them by simply paying
double the purchase price to some other random guy. They *will* look at you
as if you're crazy. Why would they ever do that?

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

Re: [Bitcoin-development] 0 confirmation txs using replace-by-fee and game theory

[Jorge Timón]

On 4/24/14, Mike Hearn <mike@plan99.net> wrote:
>>
>> This scheme would discourage people from attempting a Finney attack
>> because they would end up worse off if they did.
>>
> Phrased another way, it simply makes every block a Finney attack that
> charges the maximum double spending fee possible. This doesn't solve the
> problem.

This solves regular double-spends, not Finney attacks, but finney
attacks (which are not really the easiest attacks in the world) don't
get any worse.

On 4/24/14, Chris Pacia <ctpacia@gmail.com> wrote:
> It would work but it's an ugly hack IMO. What do people do if they don't
> have extra to pay when making a purchase? I have 200 mbtc and want to buy a
> 200 mbtc phone but I can't because I need 400 mbtc. Sucks for me.
>
> I would much prefer the hassle of a green address notary than always having
> to make sure I have double what I need to make a purchase.

This scheme wouldn't be mandatory. You can still wait for
confirmations or rely somehow on existing trust instead if that's
better for you on that situation.

> Beyond needing to double balances, what if the shop is selling me a phone
> on contract? So the actual cost of the phone is lower than the real price
> on the assumption of future revenue. Alice double spends (aka steals) the
> phone, paying double the artifically lower cost but still making a good
> saving. Bob does not end up with "nothing", he ends up in the red.

Sybil attacks aside, Alice can't save anything, period. If she tries
she will end up losing it all.
I don't see how signing a longer term contract protects her in any way.

> But there's a much simpler way to dispose with this idea. Jorge, go down to
> your local bars and cafes, and ask them if they'd be willing to accept a
> form of payment that allows anyone to steal from them by simply paying
> double the purchase price to some other random guy. They *will* look at you
> as if you're crazy. Why would they ever do that?

They would do that to avoid having to wait for a confirmation or two
(I think one is good enough for most small purchases) when being paid
by people they don't trust just before they leave.
Maybe they prefer to just make people wait if they think that will
make them pay up-front.
This is completely optional and only an improvement on the current situation.

Of course if we're not comparing this with Bitcoin today and we're
comparing it to some theoretical mechanism for instant p2p
serialization without requiring proof of work then, yes, this concept
is not very interesting.

Re: [Bitcoin-development] 0 confirmation txs using replace-by-fee and game theory

[Mike Hearn]

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

>
> Of course if we're not comparing this with Bitcoin today and we're
> comparing it to some theoretical mechanism for instant p2p
> serialization without requiring proof of work then, yes, this concept
> is not very interesting.
>

Bitcoin's competition is not some theoretical perfect p2p system but
rather, bank notes and credit cards.

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

Re: [Bitcoin-development] 0 confirmation txs using replace-by-fee and game theory

[Jannis Froese]

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

On 24.04.2014 14:15, Mike Hearn wrote:
> Beyond needing to double balances, what if the shop is selling me a
> phone on contract? So the actual cost of the phone is lower than
> the real price on the assumption of future revenue. Alice double
> spends (aka steals) the phone, paying double the artifically lower
> cost but still making a good saving. Bob does not end up with
> "nothing", he ends up in the red.

Nearly every payment system in existence has this problem: you have to
be able to enforce the contract out-of-band. The scenario you describe
is no worse than a payment network with instant, secure confirmations
because Alice could just as well refuse to make the second payment.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.22 (MingW32)
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/

iQIcBAEBAgAGBQJTWUYdAAoJEBrvn3PsoRcmT28QAJNbxjLRPYvkIfizeHoAFRH2
pNfd9458/AECJ6muGAs+tYeDw9uhYMVPnbMLZOwzgPl8HE5NN9XbGjCpwpNzsEK4
a8zb5CsonBh+xBNgbx1CIjCNYYQLd2qmgxMVaH4R7VWS+DgVBjfKq5MnM0vdSNcw
SSzb9dMEjgl1cOZa07CG4GuPwEUIFiCVygjYSrGP2E8qCepKvH+0webIXk7COqZK
SyhTdhS+dsdgGW5Mm8cA8zIVPaWYXMo88kOq2S4fIs5HiWtnVXQ9ljJ4r2Py1SEO
H3u4lMWc7Hu0PUW6b6K+uDQfyJtRNi0diJSswseA37v6BeQW4zYMNfL40AsnG+Fv
MusJFtBqHzXKhAeE/zpwi5QWs/qHvRYlETifIMKMrQldssDJo15ed/M8wNCZRobv
Q7K3XKOt228nUUP2FrZl1I4wGWwkBMpzP89t8HMrTZYV2EFWqE+lu9oXcEjz9k12
64UXiWXU0jRAhMiCAvQUL7fKaOb9TXfGPy+3+bZOAtKM5M582+0d94EObA67SBsm
O4H5vLTwS041x1cndW0NDxDbtM+IAuu2Jorzqzcie3ld7cqsKAyDbSk3i1C7zQzG
hvI6FxIy0n6GA9ciw8RM44Q4zPVxYQ4e/MMby9ko7otmL5HLlOCnOUmJ/JHn+QJG
Z7MDRkKAslLUUEqzgQWb
=HNO6
-----END PGP SIGNATURE-----

Re: [Bitcoin-development] 0 confirmation txs using replace-by-fee and game theory

[Isidor Zeuner]

quote:
[...]
> On 4/24/14, Chris Pacia <ctpacia@gmail.com> wrote:
> > It would work but it's an ugly hack IMO. What do people do if they don't
> > have extra to pay when making a purchase? I have 200 mbtc and want to buy a
> > 200 mbtc phone but I can't because I need 400 mbtc. Sucks for me.
> >
> > I would much prefer the hassle of a green address notary than always having
> > to make sure I have double what I need to make a purchase.
>
> This scheme wouldn't be mandatory. You can still wait for
> confirmations or rely somehow on existing trust instead if that's
> better for you on that situation.
>

Considering hotel or car rental payments where the credit card
processor reserves a higher amount in order to cover risks, it
doesn't seem like anything new or particularly inconvenient that a
payment system may require a larger amount than the final price being
available.

Which brings us to the question: Is it an important characteristic in
a payment system that it is capable of quickly spending your last
penny?

Best regards,

Isidor

Re: [Bitcoin-development] 0 confirmation txs using replace-by-fee and game theory

[Gareth Williams]

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

On 24/04/14 22:07, Chris Pacia wrote:
> It would work but it's an ugly hack IMO. What do people do if they don't
> have extra to pay when making a purchase? I have 200 mbtc and want to
> buy a 200 mbtc phone but I can't because I need 400 mbtc. Sucks for me.

I don't see why it couldn't work with just 200mBTC.
* you sign a 200mBTC TX to me, walk out of my shop with the phone
* you immediately sign & broadcast a double-spend TX with higher fee
* my POS computer (or BitPay's) sees the double spend, immediately
spends the initial TX to fees, and sounds the shoplifting alarm.

You don't get any money back, but you do get an angry shopkeeper chasing
you down the street / calling the police / blacklisting you from the
store. Assuming my POS computer's behaviour was completely automated and
widespread - and therefore predictable on your part - why would you ever
try this?

The number of people irrational enough to try this /knowing it never
works/ is likely to be way lower than the number who just stuff the
phone in their pocket and shoplift the old fashioned way. So I'd be
comfortable without the extra 200mBTC collateral :-)






[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 555 bytes --]

Re: [Bitcoin-development] 0 confirmation txs using replace-by-fee and game theory

[Mike Hearn]

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

>
> You don't get any money back, but you do get an angry shopkeeper chasing
> you down the street / calling the police / blacklisting you from the
> store.
>

If they could do that they'd just take the stolen property back and you
would have failed to spend your money twice. So this is by definition, not
a successful double spend. We are worried about the cases when you could
successfully double spend, and the only thing stopping you is Bitcoin.

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

Re: [Bitcoin-development] 0 confirmation txs using replace-by-fee and game theory

[Gareth Williams]

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


On 25/04/14 20:19, Mike Hearn wrote:
>     You don't get any money back, but you do get an angry shopkeeper chasing
>     you down the street / calling the police / blacklisting you from the
>     store.
> 
> 
> If they could do that they'd just take the stolen property back and you
> would have failed to spend your money twice. So this is by definition,
> not a successful double spend. We are worried about the cases when you
> could successfully double spend, and the only thing stopping you is Bitcoin.

You might not succeed in catching them, but however small the risk of
getting caught is, they're taking that risk for an assured zero gain.
Any rational attacker would therefore not bother.

I think it's a very elegant solution to the typical "broadcast double
spend" attack. Of course it unfortunately does nothing to stop a
dishonest mining pool from secretly working on your double spend for a
fee. But that breaks down to:
* trade first and hope the dishonest pool finds the next block
* the dishonest pool finds and withholds the block while you trade

We can discount the second one entirely - the orphan risk makes it very
expensive to execute, and people are typically accepting zero-conf for
low value items like cups of coffee. For high value items it is probably
reasonable (and hopefully common practice?) to wait for a block.

So we're left with the first situation. As others have noted, given a
dishonest pool with 5% total hashrate, a dedicated attack is out (unless
you want to end up actually buying goods to 20x the value of the attack
in the process.)

That leaves the opportunists, who press the "attempt to take-back 70% of
this transaction" (remember the pool gets their cut) every time they buy
a coffee and very occasionally get lucky. They're the only unsolvable
problem I can see here. It remains to be seen how many such opportunists
we'll end up with, or how much hashrate the dishonest pool can actually
attract.



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 555 bytes --]

Re: [Bitcoin-development] 0 confirmation txs using replace-by-fee and game theory

[Peter Todd]

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

On Thu, Apr 24, 2014 at 12:48:54PM +0200, Jorge Timón wrote:
> Here is a solution to the problem of having 0 confirmation
> transactions

FWIW I'm running an experiment right now to detect how easy it is to
doublespend 0-conf transactions I need to collect more data, but initial
results indicate that transaction propagation is sufficiently unreliable
that double-spending frequently works without miners using
replace-by-fee even when both transactions pay high fees, there is a 60
second delay between first and second, and there's only about four
replace-by-fee nodes on the network.

With replace-by-fee scorched-earth the success rate of such
double-spends would be significantly reduced as the attacker would need
to get lucky with bad propagation not just once, but twice in a row.

> that relies on game
> theory and most miners implementing replace-by-fee and child-pays-for-parent.
> 
> This has been proposed before
> http://sourceforge.net/p/bitcoin/mailman/message/30876033/
> I'm just going to describe the general idea in more detail.

Just to be clear, while that post is mine, original credit for the idea
actually goes to John Dillon as far as I know; I first heard about it
from him in private discussion.

> Replace-by-fee and child-pays-for parent cannot be prohibited by a
> protocol rule.
> I believe all miners will eventually implement these policies because
> it is the more rational way for them to prioritize transactions.
> Finally I hope they do because it would make 0-confirmation
> transactions possible as described in this post.
> So I can't find any reasoning against replace-by-fee unless my example
> is terribly flawed.
> Am I missing something?

A few things:

1) Replace-by-fee doesn't protect against sybil attacks; only
confirmations are solid evidence that a transaction has actually reached
the mining power and your communication channel to that mining power
isn't being blocked. Keep in mind that Bitcoin depends on the existence
of a jam-free network, and very importantly, lets you detect when that
network has failed and you are being jammed. No unconfirmed transaction
scheme can solve this problem in a decentralized network.

2) Replace-by-fee scorched earth does require you to keep private keys
online to sign the replacements. Not a big deal, but it's yet another
reason why you wouldn't want to use it for high-value stuff.

3) It doesn't directly solve finney attacks(1) where the miner mines the
transaction in private. However finney attacks are only relevant if
there is high centralization of hashing power, and all other proposed
mechanisms, e.g. coinbase reallocation, themselves do a lot of harm to
decentralization. (just look at how coinbase reallocation lets large
pools bully smaller miners out of business by blacklisting their blocks)

One interesting thing with regard to finney attacks and replace-by-fee
though is that enforcing hasher visibility of the blocks they are mining
- what getblocktemplate was meant to do voluntarily - lets any hasher
detect a finney attack double-spend and broadcast it. They have a weak
incentive to do so - the scorched earth reply is a high-fee transaction
of course and pre-broadcasting transactions makes blocks propagate
faster - at which point you're back to a public double-spend.  Enforcing
visibility of block contents to hashers is definitely a good thing for
decentralization.

1) https://bitcointalk.org/index.php?topic=3441.msg48384#msg48384

-- 
'peter'[:-1]@petertodd.org
000000000000000093d8af23978adc9e201a1f2e2dc52844f9013a1da3621572

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

Re: [Bitcoin-development] 0 confirmation txs using replace-by-fee and game theory

[Jorge Timón]

On 4/24/14, Peter Todd <pete@petertodd.org> wrote:
> ...
> With replace-by-fee scorched-earth the success rate of such
> double-spends would be significantly reduced as the attacker would need
> to get lucky with bad propagation not just once, but twice in a row.

Interesting.

>> Replace-by-fee and child-pays-for parent cannot be prohibited by a
>> protocol rule.
>> I believe all miners will eventually implement these policies because
>> it is the more rational way for them to prioritize transactions.
>> Finally I hope they do because it would make 0-confirmation
>> transactions possible as described in this post.
>> So I can't find any reasoning against replace-by-fee unless my example
>> is terribly flawed.
>> Am I missing something?
>
> A few things:
>
> 1) Replace-by-fee doesn't protect against sybil attacks; only

No worse than the current situation.

> 2) Replace-by-fee scorched earth does require you to keep private keys
> online to sign the replacements. Not a big deal, but it's yet another
> reason why you wouldn't want to use it for high-value stuff.

High-value transactions should wait for several confirmations.

> 3) It doesn't directly solve finney attacks(1) where the miner mines the
> transaction in private. However finney attacks are only relevant if
> there is high centralization of hashing power, and all other proposed
> mechanisms, e.g. coinbase reallocation, themselves do a lot of harm to
> decentralization. (just look at how coinbase reallocation lets large
> pools bully smaller miners out of business by blacklisting their blocks)

Again, no worse than the current situation. And regular double-spends
attacks are much simpler than finney attacks.

> One interesting thing with regard to finney attacks and replace-by-fee
> though is that enforcing hasher visibility of the blocks they are mining
> - what getblocktemplate was meant to do voluntarily - lets any hasher
> detect a finney attack double-spend and broadcast it. They have a weak
> incentive to do so - the scorched earth reply is a high-fee transaction
> of course and pre-broadcasting transactions makes blocks propagate
> faster - at which point you're back to a public double-spend.  Enforcing
> visibility of block contents to hashers is definitely a good thing for
> decentralization.

Where can I read more about "enforcing hashing visibility of block contents"?
Sounds somewhat similar to p2pool to me but I'm not sure I understand it.