Making 0-conf TXs relatively safe "again"

[TalkingAntColony]

OK, I'll try.

Buyer B wants to buy an item with value 0.1 BTC from Merchant M. B has 20.4 BTC in total. These are stored in two transactions outputs B0, B1, both of the buyer.

B0: Transaction Output with 0.4 BTC, private key known to B
B1: Transaction Output with 20 BTC, private key known to B

Now, to buy the item, the buyer sends two transactions Tx2 and Tx3 to the merchant.  The merchant has address <addrM>

Tx2:
  Input B0
  Outputs
    1: 0.1 BTC to <addrM>
    2: 0.3 BTC to <addrB> (another address of B)

Tx3:
  Input B1
  Outputs:
    1: 0.1 BTC to <addrM>
    2: 9.9 BTC to <addrB>
       *only valid with two spends of B0*
 
the transaction Tx3 is special (this would need an extension of the scripting language). In order to use it, one needs to provide two *different* spendings of B0.

The merchant M gets both these transactions, waits 10 seconds, and then gives the item to B. If later another transaction of B0 shows up before transaction Tx2 is in a block, he can broadcast Tx3; and it will be worthwile for a miner to use it (note that it has 10BTC fee included).

There is nothing stopping Tx3 from being broadcast and accepted by the network (assuming input B1 is from standard Tx), so the merchant could extort the buyer under threat of prematurely broadcasting. Scripts are only evaluated when someone tries to spend outputs. Tx3 coins would be sent to an address that is unspendable unless the script conditions were met (presumably, proof of a dbl spend). There is also nothing stopping the buyer from dbl spending B1, making the "safety" Tx invalid.

I am unconvinced there is a way to do what this thread is proposing that isn't exploitable. The proposers have the burden of proof to show otherwise. For instance, you cannot wave your hand and say there is a non-exploitable way to make a Tx valid only when a dbl spend attempt occurs. That is a major change to Tx scripting and will require technical details on your part.

[phelix]

[...]
the transaction Tx3 is special (this would need an extension of the scripting language). In order to use it, one needs to provide two *different* spendings of B0.
[...]

There is nothing stopping Tx3 from being broadcast and accepted by the network [...]

As he said it is a special TX.

The problem with this approach is that the deposit can be spent to another address in the same block as the double spend.

bump:

What about this box of Pandora: Nodes could delay relaying of blocks including potential double spends (txs replacing txs the node knows about). 

This would give miners an incentive to use the first / most popular tx with a certain prev output.

[tholenst]

There is nothing stopping Tx3 from being broadcast and accepted by the network (assuming input B1 is from standard Tx) [...] I am unconvinced there is a way to do what this thread is proposing that isn't exploitable. The proposers have the burden of proof to show otherwise.

I agree that there is work needed there. It is, however, clear that one could in principle add an instruction to the scripting language which does exactly this. However, this would not be a good solution, and so work is needed to make the approach practical.

The problem with this approach is that the deposit can be spent to another address in the same block as the double spend.

No, that's no problem: usually miners will not do this as they can earn more by using Tx3 (or else, the guy who double spends still pays the miner a lot of fees).

Nodes could delay relaying of blocks including potential double spends (txs replacing txs the node knows about).  

This would give miners an incentive to use the first / most popular tx with a certain prev output.

Do nodes currently not transmit tx's which are double spends, i.e., only keep the first one?

[phelix]

The problem with this approach is that the deposit can be spent to another address in the same block as the double spend.

No, that's no problem: usually miners will not do this as they can earn more by using Tx3 (or else, the guy who double spends still pays the miner a lot of fees).

The problem TalkingAntColony pointed out is that of specialized "double spend miners". These build reputation and make money by helping the double spender. In the long run they can make more money by helping the double spender and not use TX3 but by mining the double spend and moving the deposit.

Sometimes (~1%) the double spend miner's blocks get orphaned, though, which means the TXs from the block become public and other miners will mine TX3.

Nodes could delay relaying of blocks including potential double spends (txs replacing txs the node knows about). 

This would give miners an incentive to use the first / most popular tx with a certain prev output.

Do nodes currently not transmit tx's which are double spends, i.e., only keep the first one?

Yes. Invalid TXs will be silently ignored by the standard client. There were discussions about broadcasting double spend warnings along with the two conflicting TXs but there is only little benefit for a careful merchant.

[TalkingAntColony]

[...]
the transaction Tx3 is special (this would need an extension of the scripting language). In order to use it, one needs to provide two *different* spendings of B0.
[...]

There is nothing stopping Tx3 from being broadcast and accepted by the network [...]

As he said it is a special TX. [...]

I feel like this is a grey area with the proposal. You cannot simply assume there exists a feasible extension to scripting which would allow the network to verify that a double spend occurred.

Also, what happens when the payer double-spends to another merchant using this proposal's mechanism? Who's Tx3 would be valid?

[tholenst]

Nodes could delay relaying of blocks including potential double spends (txs replacing txs the node knows about). 

I would guess that major miners already are, or will, at some point, communicate directly among each other. After all, you don't want to miss a block.

It is not clear to me if one could not have a convention to under which miners might ignore certain blocks though.

I feel like this is a grey area with the proposal. You cannot simply assume there exists a feasible extension to scripting which would allow the network to verify that a double spend occurred.

I agree there is work need, but it is clear that there is a way of doing an extension which does what I want: simply introduce an opcode which does exactly what you want (i.e., don't even run the scripts; instead, check whether they have exactly the form required, and if so accept everything). Of course, this would be a bad way of doing it.

I think the main question here is: how can one make the scripting language flexible enough to allow this kind of mechanism?

Also, what happens when the payer double-spends to another merchant using this proposal's mechanism? Who's Tx3 would be valid?

Whichever is mined. Note that the miner will probably take the one giving him more fee.

[phelix]

Nodes could delay relaying of blocks including potential double spends (txs replacing txs the node knows about). 

I would guess that major miners already are, or will, at some point, communicate directly among each other. After all, you don't want to miss a block.

It is not clear to me if one could not have a convention to under which miners might ignore certain blocks though.

This was the idea that lead me to start this thread:
https://bitcointalk.org/index.php?topic=163751 Mining Codex

I would expect the large miners to be well connected, too. Will this still be possible with the new protocols? Will there be mining supernodes with several thousand miners connected to share blocks as fast as possible? Might well be possible.

[cunicula]

Bitcoin is a consensus-building network.  There cannot be a reliable zero-confirmation system using the Bitcoin network alone, because it can't build consensus that quickly.  The whole point of it is that your confidence in the transaction can grow exponentially as a function of work done (#confirmations), but if it has zero work then there is no confidence in it.  At the end of the day, it's that simple -- you can't be confident until your transaction is buried in proof-of-work, which means it must have confirmations.  

That's not to say that there will never be hope for zero-confirmation transactions:  it just means that they will never be (and never were) suitable for zero-trust exchanges without external services.  There are some cool things you can do with locktime and alternate sighash codes, but they all build off already-confirmed transactions -- they require seeding a contract with an already-confirmed tx!   Third-parties may provide mechanisms to help people transaction instantly, and they may take a fee for it.  But you won't get there with the network rules alone.

We need to get away from this wishful thinking that we can somehow adapt this proof-of-work system to work with transactions that have no proof-of-work.  There's still use for them, just not zero-trust transactions (i.e. if my coworker sends me money to cover the lunch tab, I can be confident with the zero-conf, because I can go to his cubicle and punch him later if he double spends, etc -- this is not a zero-trust situation.).  

Like you say, with the existing rule set zero-conf requires trust. As it stands "commitments not to double spend" can themselves be double spent. So they aren't credible.

An altchain could bend the rules and create a simple fix for this. We need "general purpose seeding contracts". These "seeding contracts" would be deposits supporting zero-conf txns to arbitrary payees. The Buyer is the sole party to a "general purpose seeding contract." Buyers precommit to zero-conf payments long in advance, but designate the payee and the amount at the time of sale. The "general purpose seeding contract" enters the blockchain long before the sale occurs, so it is credible. Payees could safely accept anonymous zero-conf payments issued from such contracts.

How could this work?

Suppose there is a new address type. Inputs originating from this address type obey the following txn rules:
1) 4/5 of inputs must be sent to the signing public key (I.e. you can only transfer 20% of any input to a new public key)
2) txn outputs are never spendable until 10 blocks have passed. Provided 3 does not occur, inputs become spendable after 10 blocks.
3) if the signing public key appears twice within a ten block interval, a contract violation is detected. The miner of the second txn receives 1/5 of the inputs as a txn fee. The other inputs are destroyed (i.e. the payee(s) receive nothing at all).

There are just two possible outcomes.
1) Payee receives their money. Buyer does not lose any money.
2) Payee receives nothing. Miner receives buyers payment. Buyer loses at least 4x the value of the payment.

Rational buyers never chose outcome 2, so payment are assured even with 0 confirms. It seems bad that the payee doesn't get paid in outcome 2, but this is unavoidable. You can never know who the legitimate payee is, so all you can do is take money hostage and destroy it.

[Edit: Thieves could try to spend at 6 or more different zero-conf accepting merchants simultaneously, but I bet this is much too difficult and risky to be practical.  If not, you could increase the escrow requirement (e.g. 10-fold instead of 5-fold, so at least 11 simultaneous purchases must occur before theft is profitable).]

[phelix]

[...]

Like you say, with the existing rule set zero-conf requires trust. As it stands "commitments not to double spend" can themselves be double spent. So they aren't credible.

An altchain could bend the rules and create a simple fix for this. We need "general purpose seeding contracts". These "seeding contracts" would be deposits supporting zero-conf txns to arbitrary payees. The Buyer is the sole party to a "general purpose seeding contract." Buyers precommit to zero-conf payments long in advance, but designate the payee and the amount at the time of sale. The "general purpose seeding contract" enters the blockchain long before the sale occurs, so it is credible. Payees could safely accept anonymous zero-conf payments issued from such contracts.

How could this work?

Suppose there is a new address type. Inputs originating from this address type obey the following txn rules:
1) 4/5 of inputs must be sent to the signing public key (I.e. you can only transfer 20% of any input to a new public key)
2) txn outputs are never spendable until 10 blocks have passed. Provided 3 does not occur, inputs become spendable after 10 blocks.
3) if the signing public key appears twice within a ten block interval, a contract violation is detected. The miner of the second txn receives 1/5 of the inputs as a txn fee. The other inputs are destroyed (i.e. the payee(s) receive nothing at all).

There are just two possible outcomes.
1) Payee receives their money. Buyer does not lose any money.
2) Payee receives nothing. Miner receives buyers payment. Buyer loses at least 4x the value of the payment.

Rational buyers never chose outcome 2, so payment are assured even with 0 confirms. It seems bad that the payee doesn't get paid in outcome 2, but this is unavoidable. You can never know who the legitimate payee is, so all you can do is take money hostage and destroy it.

Darn, the last two nights I pondered about something I thought was all new and now you are faster than me with this post.  

Anyway, the key seems to be a possibility to impede double spends even after they are in a block because only then they have to be public. See my less sophisticated but also simpler suggestion below.

[Edit: Thieves could try to spend at 6 or more different zero-conf accepting merchants simultaneously, but I bet this is much too difficult and risky to be practical.  If not, you could increase the escrow requirement (e.g. 10-fold instead of 5-fold, so at least 11 simultaneous purchases must occur before theft is profitable).]

If a merchant waits for 10 seconds after receiving the TX and then broadcasts it to plenty of nodes this can not happen.

[phelix]

Simpler version of cunicula's suggestion. It spans unabridged's original solution across blocks.

You can only know about a double spend for sure once the TX is in a released block. This means an effective zero confirmation double spend circumvention is only possible if it still works after a TX is in the blockchain.

double spend destructor
If a miner can come up with a new signed TX including an input already used as input in the previous block he can claim the input as an additional transaction fee.
The TX in the previous block becomes invalid!
Transactions that only changed the transaction fee must be excluded.

There are just two possible outcomes:
1) Merchant receives their money. Buyer payed merchant.
2) Merchant receives nothing. Miner receives payment. Buyer payed miner.
There is no penalty for the buyer but also no incentive. I think that should be enough.

This change makes single confirmation TXs less secure than now but removes the incentive to double spend. With the current system I don't see a use case for single confirmation TXs other than preventing double spends anyway. TXs with two or more confirmations are as secure as today.

A problem is that it is necessary to make 100% sure never to broadcast modified TXs (with the exception of increased fees).

[TalkingAntColony]

That is a risky method due to invalidating a Tx already in a block. Consider if a dbl-spender mines his own block with a Tx that dbl-spends coins, invalidating a zero-conf Tx he sent a Merchant A. He then immediately pays Merchant B from the dbl-spent coin who accepts zero-conf Tx (presumably because of their trust in this proposal). If he pays Merchant B before he hears about Merchant A's invalidated Tx, then Merchant B will have their zero-conf Tx invalidated and the dbl-spender gets away with effectively dbl-spending coins (got same coins accepted by two merchants).

This also sets up the possibility for extortion, where a buyer threatens to dbl-spend coins (making the merchant lose the coins) unless the merchant does something.

[phelix]

That is a risky method due to invalidating a Tx already in a block. Consider if a dbl-spender mines his own block with a Tx that dbl-spends coins, invalidating a zero-conf Tx he sent a Merchant A. He then immediately pays Merchant B from the dbl-spent coin who accepts zero-conf Tx (presumably because of their trust in this proposal). If he pays Merchant B before he hears about Merchant A's invalidated Tx, then Merchant B will have their zero-conf Tx invalidated and the dbl-spender gets away with effectively dbl-spending coins (got same coins accepted by two merchants).

No, that can not happen if merchant B does a proper job. Merchants always have to wait and listen for a couple of seconds for previous TX and then broadcast the TX afterwards. Merchant B could even sell the double spending TX to a miner without giving away the goods.

This also sets up the possibility for extortion, where a buyer threatens to dbl-spend coins (making the merchant lose the coins) unless the merchant does something.

I don't think extortion is a problem at all for the targeted kinds of goods.

[TalkingAntColony]

The Tx that Merchant A receives may or may not be heard about by Merchant B. It is unwise IMO to make a security feature rely on the assumption that all nodes will know about all unconfirmed Tx. Then, then the buyer mines his own block sending the coins back to himself. Merchant B will accept zero-conf Tx building off that block if he doesn't know about the Tx from Merchant A. The buyer could peer directly with Merchant B so Merchant B is likely to see the new block faster than Merchant A. This gives the buyer more time for his zero-conf Tx to be accepted by Merchant B. Merchant A must "be on the ball" to quickly realize the dbl-spend and make sure all other nodes know this. Naturally or purposefully occurring 1-2 block blockchain forks may make this proposal unreliable as well.

Also, what if there are buyers who always dbl-spend coins, so that merchants will be discouraged from accepting zero-conf Tx using this method? There is no additional cost to buyers who dbl-spend in this scheme anyway.

[phelix]

The Tx that Merchant A receives may or may not be heard about by Merchant B. It is unwise IMO to make a security feature rely on the assumption that all nodes will know about all unconfirmed Tx.

Merchant A of course rebroadcasts the tx himself to make double spends less likely to succeed. As long as no block was found this is a similar situation to what we have now. Once the first tx is in a block, well, the merchant really should make sure he gets that. I have no info on this but I would expect network permeation to be very high.

It is not a security feature but a "safe enough" feature. This means it does not have to be perfect but just 98% or so, way better than what we have now.

Then, then the buyer mines his own block sending the coins back to himself. Merchant B will accept zero-conf Tx building off that block if he doesn't know about the Tx from Merchant A.

? The sending coins back tx conflicts with the tx to Merchant B so he will never accept it if he has seen the block. Also note that as soon as the block with the malicious "sending coins back" becomes public it is certain a miner will claim the payment - because the first tx is public, too.

The buyer could peer directly with Merchant B so Merchant B is likely to see the new block faster than Merchant A.

Are you talking about a Finney attack? The risk of orphaning the new block would be much too high.

This gives the buyer more time for his zero-conf Tx to be accepted by Merchant B. Merchant A must "be on the ball" to quickly realize the dbl-spend and make sure all other nodes know this.

see above

Naturally or purposefully occurring 1-2 block blockchain forks may make this proposal unreliable as well.

These are so rare they do not matter and do not hurt this proposal in any way.

Also, what if there are buyers who always dbl-spend coins, so that merchants will be discouraged from accepting zero-conf Tx using this method? There is no additional cost to buyers who dbl-spend in this scheme anyway.

This is exactly what will happen with the current system. "double spending destruction" removes the incentive to do it so I doubt a lot of people would go through the (maybe very small) trouble. Also most people still have a conscience without financial gains. Cunicula's suggestion even addresses this with a penalty.

[kjj]

I think that schemes like this are doomed to failure.

Right now, a bitcoin transaction has very simple rules.  There are really only two:

A transaction is valid if it satisfies the conditions specified in the inputs it redeems.
A transaction output can only be redeemed once.

That's really all there is to it.  A powerful and useful system defined by just two simple rules.  The pinnacle of engineering and beauty, nothing left to take away.

Now, our computers are really dumb, so things that we take for granted, we have to explain to them in great detail.  So, the software isn't as beautiful as the idea it represents.  We have to tell the computer that you can't have a negative output to balance out a too-large output, and things like that.

Assume that we devise some way to allow the network to take action against double spends.  There are horrifying technical challenges in that task, but we are going to assume that condition, so we don't have to worry about solving them.  Any such scheme is going to destroy the beauty of the system.  There won't be two simple rules that you can explain to literally anyone in 5 minutes, there are going to be three.  And the third one is going to be ugly.  It is going to start out with "Except when..."

The first rule is math.  The second rule is time.  Both of these are necessary, in that you can't have a system like this without math and time.  The third rule will be the mob.  The third rule will be the one that we added to make some particular group of people happy.  The third rule will be the foot in the door for the fourth rule, to make some other group happy.  And then the fifth.  Next thing you know, we'll have a group of people meeting on an island to add a rule that will solve the world's problems.

Fortunately, I think that people see this.  Even if we could distill the problem down to "just a bit of code", it would destroy the beauty of the system.  The software could take the hit, lot of it is already ugly.  But it would be fatal to the idea that the software represents.

[TalkingAntColony]

I'm not convinced my exploit has been resolved, but it may be a misunderstanding of the proposal here. Either way, you haven't convinced me this proposal is sound, and the burden of proof is on the ones claiming they have found a way to make zero-conf Tx safe. If you are really serious about this idea, program it into an altcoin or testnet and get people to run attacks against it. If you are successful, you might create a valuable altcoin or be responsible for a critical fork to bitcoin. At this point however I'm done examining this proposal which is difficult to discern without code.

[cunicula]

@phelix

http://www.reddit.com/r/CryptoCurrency/comments/1evxuk/how_toalt_coin_with_secure_zeroconf_txns/
FYI, I posted here for other eyeballs.

There is nothing wrong with my proposal or your modification. Mine is more secure, yours is more convenient. It's just a trade-off.

The bitcoin community is extremely opposed to hard-forks, so don't be discouraged by the lack of enthusiasm. Major changes are only practical in the altcoin community, so consider promoting radical new ideas there.

[phelix]

I think that schemes like this are doomed to failure.

Right now, a bitcoin transaction has very simple rules.  There are really only two:

A transaction is valid if it satisfies the conditions specified in the inputs it redeems.
A transaction output can only be redeemed once.

That's really all there is to it.  A powerful and useful system defined by just two simple rules.  The pinnacle of engineering and beauty, nothing left to take away.

Now, our computers are really dumb, so things that we take for granted, we have to explain to them in great detail.  So, the software isn't as beautiful as the idea it represents.  We have to tell the computer that you can't have a negative output to balance out a too-large output, and things like that.

Assume that we devise some way to allow the network to take action against double spends.  There are horrifying technical challenges in that task, but we are going to assume that condition, so we don't have to worry about solving them.  Any such scheme is going to destroy the beauty of the system.  There won't be two simple rules that you can explain to literally anyone in 5 minutes, there are going to be three.  And the third one is going to be ugly.  It is going to start out with "Except when..."

The first rule is math.  The second rule is time.  Both of these are necessary, in that you can't have a system like this without math and time.  The third rule will be the mob.  The third rule will be the one that we added to make some particular group of people happy.  The third rule will be the foot in the door for the fourth rule, to make some other group happy.  And then the fifth.  Next thing you know, we'll have a group of people meeting on an island to add a rule that will solve the world's problems.

Fortunately, I think that people see this.  Even if we could distill the problem down to "just a bit of code", it would destroy the beauty of the system.  The software could take the hit, lot of it is already ugly.  But it would be fatal to the idea that the software represents.

I like your romantic view of Bitcoin and aesthetics sure are important. Simple solutions that work well is where brilliance of mind shines. If we can improve the system by making some small changes, though, I think we should still to do it. Maybe it will even bring us to an improved simple solution.

I'm not convinced my exploit has been resolved, but it may be a misunderstanding of the proposal here. Either way, you haven't convinced me this proposal is sound, and the burden of proof is on the ones claiming they have found a way to make zero-conf Tx safe. If you are really serious about this idea, program it into an altcoin or testnet and get people to run attacks against it. If you are successful, you might create a valuable altcoin or be responsible for a critical fork to bitcoin. At this point however I'm done examining this proposal which is difficult to discern without code.

Thank you for input. I think the concept in the basic version is simple enough to make thought experiments with it. I invite you and others to make more of these about it.

@phelix

http://www.reddit.com/r/CryptoCurrency/comments/1evxuk/how_toalt_coin_with_secure_zeroconf_txns/
FYI, I posted here for other eyeballs.

There is nothing wrong with my proposal or your modification. Mine is more secure, yours is more convenient. It's just a trade-off.

That's how I see it, too.

The bitcoin community is extremely opposed to hard-forks, so don't be discouraged by the lack of enthusiasm. Major changes are only practical in the altcoin community, so consider promoting radical new ideas there.

Yup, by now there is so much money and politics involved with Bitcoin that a change like this can only be implemented once there is a successful altcoin testing the change. Maybe it even needs to rise to a level of popularity that makes Bitcoin devs uncomfortable before it will be seriously considered.

[phelix]

With the simple variant there still seems to be an incentive for the miner of the second block to do tx replacement. Maybe that was what TalkingAntColony tried to tell me above.

Cunicula's version does not have this problem. Could be that it is necessary to destroy coins.