Topic: Two Bitcoins at the Price of One (Read 13463 times)

Transactions don't have a proper validity window.  They do include a "not valid before" field, which is almost always set to zero.  This means either "around the first moon landing", or "early 2009", depending on your point of view.  But they do not include a "not valid after" field.

The protocol does not define what a node does with transactions that aren't valid.  This includes transactions that are waiting to become valid, as well as transactions that are invalid because they attempt to redeem an invalid input, for whatever reason.

Since the protocol does not define it, each client is allowed to retain or discard transactions as the authors see fit.  I may be wrong here, but I believe that the client which is currently the most popular discards transactions more-or-less at random if a new one comes in that would exceed the size of the buffer set aside for such things.

After how much time two 0-confirmation double spend transactions are deleted ? Or are they persistent for ever waiting to be picked up?

And until that time arrives, there is a third party service launching that offers to provide a protection service for 0/unconfirmed payments:
 - http://bitcoinmagazine.net/zipconf-the-other-side-of-instant

So the obvious solution is for the "new merchant" to connect to a trusted intermediary.  There is no reason all Bitcoin nodes need to be anonymous.  Some could be strongly signed.

Imagine I started a service today called "Tangible Cryptography Trusted Fast Transactions" (TCTFT).   I sign contracts with major pools to
a) guarantee my node (or more likely global network of nodes) will ALWAYS have a connection slot to the pool
b) Pool will respond to API requests where I check if a tx is in the memory pool
c) Once pool puts a tx in memory pool it signs an assurity contract that it will NEVER replace that tx from memory pool.

Obviously pools will want compensation so I offer a flat fee monthly (say 10 BTC per TH/s of proven hashing power) plus 1 bitcent per tx validated tx that is included in a block the pool signs.  None of this would be in tx fees.  It would be private payments between a trusted intermediary and the pools.  To ensure merchants I can be trusted I incorporate, offer a contract with SLA, and post a $100,000 surety bond.

When a merchant gets a 0-confirm tx it sends details to me (via an API).  I send it to each pool and the pool confirms once it is in the memory pool.  Remember pools are under contract with penalties to never remove tx from memory pool once they confirm it.  Based on merchant's desired security level I notify merchant once "enough" of the pools have included that tx in their memory pool.   Merchant pays me per API request.

So hypothetically Starbucks gets a bitcoin payment.  It's POS terminal forwards a request of TX ID to my server who then forwards it to the pools.  One by one each pool reports the tx is part of the memory pool.  If attacker tx got to pool first pool would report double spend.  Assumming no pool reports double spend once 60% of global hashing power reports the tx in their memory pool I notify the merchant.  Elapsed time is on the order of 5-10 seconds.  Merchant POS terminal shows "confirmed" and customer leaves with coffee.

Now does the amount of real "fast tx" commerce today support such a network?  No but it wouldn't be very difficult to support.  Merchants get fast tx, pools get a secondary source of revenue, customers get lower prices (less fraud passthrough), and Bitcoin is seen as stronger and safer than other payment methods.  A win all around.

Of course it is possible through the use of "fast tx" brokers.  A broker pays a service fee to each pool to be one of their x connections.  Broker acts as a middle man providing secure API for multiple merchants.   A broker is necessary to handle "assurity contracts' anyways. Decentralization can still be achieved by having multiple brokers.

Multiple merchants (paying fees) ---> "fast tx" broker ----> multiple pools (compensated via broker possibly as a flat monthly rate).

The rest of your posts seem to assume merchant will fall back on accepting tx from insecure peers. Solution is merchant never falls back to accepting tx from insecure peers.


Centralization (to some degree) will always exist.  A broker could easily handle 20+ pools (and private large scale mining farms).  If top 20 pools combined had 75% of hashing power Bitcoin would be more not less decentralized.

That depends on a great many variables beyond the control of the attacker, or even the vendor.  But the length of time that the vendor's node has been in existence has a significant effect upon how deep that node is.  Yet, the first step is to locate said node.  This first step is no small feat unto itself, even if no special steps have been taken to hide the node.  The second step is to 'isolate' said node from major nodes; and not just mining pools.  There do exist nodes that have been deliberately modified to allow unlimited connections & do not mine, for the purpose of creating 'supernodes' intended to improve the network latency.  An attacker would have to isolate these nodes as well, which is something that is also unlikely to go unnoticed for very long.  Also, an attacker would have to know if the vendor's node uses Tor or any VPN to connect to one or more peers.  If such an attacker can do all of these things, then the attacker can do a complete finney attack to remove all doubt of failure.  However, in a practical sense, to do these forms of attacks it would basicly have to be an inside job, for the attacker would have to have at least network access to the vendors node, which in a practical sense means physical access to that node.  A corner vendor shop might keep his node running on his POS computer, accessible to a cashier with ill intent, but there is no way that Wal-Mart would.  This is the kind of attack that would work once or twice before word got out about how it's done and business associations sent out alerts to members to do things differently.  IMHO, this kind of attack, and pretty much every version of a finney attack that I have heard thus far, are only theoretical and not a practical attack vector because 1) the nature of the network makes identifying any particular node very difficult and it's connected peers moreso and 2) it's a class of theoretical attack vectors that are well known among the developer community here.  Black swans never fly in from a watched direction.  The very fact that these types of attacks have been openly discussed on this forum contributes to the future difficulty of their success, since developers of vendor POS nodes are likely to consider these known attack vectors in their node designs.

As to the statement that my ego has been affected, I personally don't have any skills in this area; but I do understand how the system works & find it somewhat offensive when someone with a low post count comes into this forum with the belief that he understands it generally and thus can make generalizations based upon whatever prior computer science experience he may have.  Granted, the network topology isn't unique, but nor is it transparent.  There are a great many things that can be done to make a node nearly invisible to an outside observer.

It was already pointed out that Step #2 or point 1) is not feasible. Mining pool can handle only 100 (or on this order) connections. This limits number of "fast transaction" vendors to just 100.

Step #1 or point 2) is easy to implement and somewhat effective. However, with a bit of analysis of time from injecting TX to vendor's response you can find a node very close to the vendor.

To combat measures in point 3) and 4) attacker needs quite substantial resources. However, noting outside of reach for a government or mid-size criminal organisation.

Point 5) is quite hard to implement, especially that direct connections to miners are a bit hard to achieve. Also currently we experience heavy concentration of hashing power in pools. Such concentration is not required by BitCoin network to work. If you have everyone mining solo or in small pools, you cannot connect to all of them.

Yes, and they seem to have ignored the basic recommendation where step #1 is start the node using -nolisten and step #2, have the node explicitly connect to well known nodes (e.g., pool miners).  
The problem should then essentially be marginalized to irrelevance, though there is more that can be done, as is described here:

First of all, let's leave our egos out of this. Bad guys do not care about this and white hats care even less.

The problem is: there seems to be a market need for "fast transactions" which in BitCoin case mean 0-confirmation transactions. One way out of this is to declare that BitCoin is not a tool for this. It was not designed for 0-confirmation transactions and anyone trying it is pushing square pegs into round holes.

Another way is to explore what can be done to make 0-confirmation transactions safer. When an idea is proposed, one has to explore what can be done to exploit it.

In this case authors made an observation that vast majority of nodes in BitCoin network are honest. Basing on this observation they propose an alert system. What you/us proposed is a modified usage of the system (not modification of the system itself). The problem is that such modifications change the playing field. After such change there will be a possible gain from running a large network of zombie nodes. This in turn will invalidate the observation on which these propositions are based.

With regard to any penalty for abuse of BitCoin network, legal or otherwise, it relies on existence of some external entity or coalition of entities to carry out such vengeance. This is exactly what BitCoin was trying to avoid: no central bank, no government, no police to crack down on cheaters, no courts to arbitrate. If we have a force to punish offenders than we can just print fiat money! How simple!

PS: With respect to adding new nodes at the edges. The vendor node is likely to be a new node as well. The point is to isolate vendor node from mining nodes.

Adding nodes to the existing netowrk isn't the same as destroying nodes.  The network exists, any nodes that you could add to it would attach at the network's edges.  Adding 100K new nodes to the networ would, at worst, slow down the network for those persistant nodes that were already connected before your botnet arrived.  If you don't believe it, try it.  But setting up a lab experiment like these guys did, that favors you, doesn't count.   I dare you to do it on the live network.  If you can 1) find my personal node & 2) manage to slow my propagation rate down to an unworkable delay then I will concede defeat and shout your superiority in all manner while also lobbying for your sainthood in my free time.

A bit of warning, though.  You're going to have to do it using your own funds & without being noticed by the bitcoin watchdogs.  Some of these guys have some real talent, and they won't take kindly to your 'proof'.  You must destroy the network without getting caught for it to count, and it has to last for at least 10 minutes.  If you do get caught by the watchdogs, which is highly likely, you can 1) expect that you will discover that you are wanted for a stautory rape charge in some East Coast state that you've never been to and 2) that's just what the script kiddies will do.  Before they are done, you will discover that your own smartphone hates you; and has sent gay porn to every person currently in your contact list as well as your entire high school graduating class & every person that you have ever dated.

I just thought that I should be upfront about the possible consequeces of failure.

Small-world networks (peer to peer networks) start falling apart when 90% of nodes are destroyed. (I will have to look for reference.) In the same spirit if you add to network 10 times more non-functioning nodes the network will fragment.

Nodes that you can trust to interact with you honestly, based upon history of connection and/or the known ownership of said node, such as connecting to one or more of the major pools or one or more of the fallback nodes that have been running since the dawn of bitcoin.  Still don't need to trust that they are forever honorable, because you have so many connections.  Basicly you are simply not allowing new connections to nodes for which you have no history with.

No matter how many nodes you create, you cannot prevent valid transactions from propagating trough the honest nodes.  This is why the normal client uses so many connections, to protect against the posibility of a 'finney attack' which is what you just described.  It only takes one honest node to completely route around your blockade.  And that is for low value POS transactions only.  Anything of any significant value, and sellers are going to demand either personal data or at least 6 confirmations.  Try and buy a new car for less time than an hour, by either cash or credit.

Speak for yourself -- that title is slightly more accurate, but still misleading.

Sort of defeats the whole purpose of bitcoin.

If you trust your peers, why bother with all this mining/blockchain/cryptography garbage?

So how about this:

1) Only connect to nodes you trust (like major pools).
2) Don't allow incoming connections
3) Modify the bitcoind not not forward your tx to your peers.
4) Modify the bitcoind to halt tx if double spend is detected.
5) Write an API which lets you know what % of hashing power has your tx in their memory pool.

Then you can see which pools have notifies you of the tx and decline tx if double spend is detected.

So hypothetically:
Lets call tx A the payment to me, and tx B the double spend back to attacker.
My merchant node connects to the top 10 pools (roughly 80% of hashing power).
Since those pools will relay tx to me I can determine which pools have seen my tx, which have seen the double spend, and which have seen neither (yet).

If attacker sends only tx B to major pools then I will never see tx A (because it loses all races) and will almost instantly see tx B.

If attacker only sends tx A to major pools then he has a less than 20% chance of getting the double spend (actually less because unless all other miners are malicious my tx will win at least some of those races)

If attacker sends tx A to some of major pools and tx B to some of major pools I will see both hit my node.  At which point I keep attacker's funds (on the % of tx which clear) and decline the tx on grounds of attempted fraud using the cryptographically signed double spend as proof.  This creates a unique cost to attacker not present in CC fraud.  Attacker risks losing funds on a failed double spend.  

If the above method is combined with "assurity contracts" with major pools the merchant has even higher confidence (pool agrees to not replace tx it has "insured").

If the above method is combined with a "network listener" which is a node with hundreds of connections to random nodes globally which looks continually for double spends then even attempted (but likely doomed to failure anyways) double spends can be proactively detected before they even get to the merchant's processing node.


None of this prevents Finney attacks due to the fact that "tx B" is unknown but having even 1% of network hashing power is prohibitively expensive (~$1M today and likely to climb over time).  Finney attacks are also time bound and that can be exploited to make them uneconomical for small tx.  The attacker needs to delay broadcasting the block long enough to complete the tx and during that delay the chance of another node finding a block is ~0.16% per second.   This produces an expected cost to the attacker of 8.3 bitcents per second (current block reward value)
.  
Safe delay time = (purchase price / 0.083 BTC) in seconds (or ~ 1 minute for every 5.0 BTC in value)

Example:
Selling a 1 BTC game code. That has a time value of e time value of 12 seconds block delay is ~1 BTC.  So wait 20 seconds and THEN release the code.  Lets look at the long run effect of that.
20s * 0.16777% = ~3%.
97% of time attacker "wins" 1 BTC
3% of the time attacker loses 50 BTC block reward.
0.97* 1 + 0.03 *(-50) = -0.5 BTC.  The attacker has a negative expectation.  He is gambling and you are the house (w/ a 50% house advantage).

I went to sleep (it is night here in kangaroo land) but a thought did not let me sleep. I think I can answer question which I have formulated.

The reason why it would not work, and why solution proposed in the paper will not work, is that attacker (or attackers) can make 100 000 cheap/light/zombie nodes which they control. Such nodes would not propagate alerts, or would only propagate selected alerts. It will boil down to resources available to honest and corrupt participants. And in this game proof of work is not available.

It is hard to estimate how many nodes are now in the network. However, my guestimate is that there are 16000 mining computers (Eligius has 622 distinct addresses and makes 4% of total hashing power). Hence, I guess that number of BitCoin daemon nodes is of similar order. While reports of networks of zombie computers with 100 000 participants are not uncommon.

Currently, no one creates such horde of corrupt zombie nodes, because there is no gain from it. This also explains why transactions propagate so quickly (~3s). In a network of 10 000 nodes, where each node is connected to 20 other nodes, everyone is just 4-5 hoops away.

Excellent idea.

Its funny, if they had marketed the paper as "bitcoin 0-confirm is safe for brick-and-mortar -- just wait 10 seconds" we'd all be thanking them.  Because one of the biggest concerns with the idea of deploying bitcoin massively as cell-phone based cash for small transactions is the 10 minute confirm time.  But I don't care about the "spin" the result is what's most important so thanks guys for doing this research!