Well, the question becomes how did you find out about the transaction in the first place anyway? The SPV node could be informed about the incoming tx through a payment protocol, and that protocol could provide the node with the merkle branch required. Payment becomes "prove to me a transaction in the block chain exists that only I can spend". If you assume x% of mining power is honest, that proof is just the tx and the merkle path to a block with a sufficient number of confirmations.

Verifying bitmitt.net vs. bitmit.net may or may not be easier than verifying two hex strings are identical, but the former already has a lot of real world research dedicated at solving the problem - the problem exists for regular SSL anyway. By supporting the standard SSL infrastructure we can re-use all that hard work and real world experience, and in addition it means that the risks for a company are the same risks they've already analyzed before with regard to their SSL websites.

Besides, you're friend just isn't going to say "26546d600e1a6a278eba2170559afe415ddcdd88 alpaca socks are really good", they're going to call the vendor by their human name. That's just life and to think otherwise goes against what people actually do. Good engineering takes real-world human behavior into account and finds ways to deal with it even if the behavior isn't ideal.

Yup, you're absolutely right. For the particular case of a valid transaction with non-existent txin's a SPV can't verify the fraud themselves, but other cases like invalid script execution are detectable. On the other hand they must be detected anyway as part of verifying a fraud rebuttal, or otherwise you could give rebut with a transaction with, for instance, invalid signatures but valid txin's. This is annoying because SPV clients don't need script validation machinery at all otherwise; they can only accept confirmed transactions safely so validation can be nothing more than checking the merkle path leads to a block in the best chain. To process fraud challenges and rebuttals they need to have validation code identical to that in validating nodes, including all the difficult to get right edge cases that lead to network splits.

SPV can't check fraud challenges at all other than to assume they are valid unless proven otherwise; it's why I'm calling them challenges rather than alerts. However so long as the network as a whole is connected - a core assumption of Bitcoin - any invalid fraud challenge can be rebutted cheaply by any validating node. (you need access to transactions in the recent past, but that's required for reorganizations anyway) The problem is large numbers of fraud challenges getting issued then just becomes one of anit-DDoS techniques, and I think hashcash for them is pretty reasonable, especially if the hashcash uses the same algorithm as the Bitcoin block hash so it's easy to reason about the value of that hashcash. (you could have used it to mine block after all) If a SPV client for some reason missed the rebuttal, at worst they can rebroadcast the challenge themselves to get someone to rebut it again, and if needed caching rebuttals and an inventory for them can be implemented.

A fraud challenge going un-rebutted can be treated pretty much like any reorganization - invalidate the blocks and return the transactions to the mempool - except that the length of the best chain can now decrease. For an SPV client I don't think this changes much; they don't have visibility to the full mempool anyway, and just see that since the best chain isn't what they thought it was and possibly some transactions they thought were confirmed actually aren't. You'll probably want to give some interval before you accept a challenge as valid, but SPV clients already have to wait awhile for confirmations to pile up anyway. In addition for some applications the SPV client might actually only care that the best chain is valid; they might not actually be doing Bitcoin transactions directly. Timestamping is an example that doesn't even involve any transactions at all.

Regarding rolling upgrades, I don't think that case is really much different from what happens with a rolling upgrade anyway. You do add more cases where the SPV clients need to be upgraded, but no more cases than is true for fully validating clients.

I agree that speccing out every form of fraud will be a long painful slog...

Nice! That's exactly what I'm proposing, and you guys beat me to it by a few weeks.

I should have read the forums more over Christmas...

(cleaned up repost of https://bitcointalk.org/index.php?topic=106449.msg1469608#msg1469608, minus the ideas about merkle hashing within a transaction itself)

It's been pointed out before that SPV clients are susceptible to miners colluding to inflate the currency, essentially by creating blocks whose block header is valid and meets the required PoW, but whose coinbase includes fees for non-existent transactions. In particular SPV clients have no way of preventing a 51% cartel of miners from defrauding them this way as there is no proof of fraud a SPV client can be given other than the whole block chain itself. At the same time the existence of any transaction is easy to prove, just provide the merkle branches in the path from the tx to the merkle root in the block header. What we need is to extend that existence proof to proof of the fees associated with that transaction.

Lets suppose we have an honest block with the following transactions and fees:


We include the sum of each sub-trees total fees in the intermediate nodes in the merkle tree. Thus the first level of hashes would be H(0.0011 | H(txA) | H(txB)), H(0.11 | H(txC) | H(txD)) and the second, and final, level H(0.1111 | H(0.0011 | H(txA) | H(txB)) | H(0.11 | H(txC) | H(txD)))

Now suppose the above block has been created by a dishonest miner, and it included a fraudulent transaction with a hefty fee:


Any honest node can now publish a fraud challenge, consisting the path from faketxA to the block header. The length of this path, and thus the overall fraud notice, scales by O(log2(n)) Of course, if the fraud challenge itself is fake it can be trivially rebutted by simply replying with the actual transaction. (for fraud multiple blocks deep, just publish the first fake tx input)

These fraud challenges can be posted on the P2P network itself and broadcast. For DDoS protection they should be delayed a bit so rebuttals can spread faster than notices. Similarly nodes should keep track of where the challenges came from, so rebuttals can be directed appropriately. In addition challenge rate can be limited if required by hashcash, and if the hashcash uses the same algorithm as mining itself reasoning about the value of the hashcash compared to txfee-based anti-DDoS is simple: it's the same as the profit mining would create for an equal amount of hashing.

The big advantage to this proposal is in the scenario where the maximum block size limit is lifted; scalability studies comparing Bitcoin to, say, Visa, imply block sizes and transaction volume so large that even just the cost of maintaining a full txout set will become prohibitive. In this scenario a 51% cartel of miners has a chance of getting away with undetectable inflation fraud. If proofs of such fraud can be cheaply broadcast around the network, even just a single honest validating nodes, which doesn't have to mine, can resist the attack by causing SPV nodes to simply reject the fraudulent blocks, and, for instance, refuse to accept transactions in those blocks in exchange for non-Bitcoin goods and fiat currency. This would take away the incentive for the attack, leaving the attackers with the well known ability to launch double spend attacks with are both detectable and can be cheaply proven.

Similarly even without a changed hash algorithm fraud challenges can protect SPV clients from large miners creating chains of blocks with entirely fraudulent transactions that don't exist, but are sufficiently deep in the (fraudulent) chain to look confirmed. Note that you do not need a 51% majority to do this; a majority guarantees the attack, but having, say, 25% just makes it probabilistic so you have to wait awhile to get lucky and produce a sufficient number of blocks in a row to defraud SPV nodes trusting some given number of confirmations. With fraud challenges anyone can cheaply warn those nodes that the blocks are fraudulent simply by publishing a merkle path challenge to the fake transaction input.

EDIT: gmaxwell pointed out this relevant conversation on the email list: http://sourceforge.net/mailarchive/message.php?msg_id=29450793

EDIT: etotheipi, never mind, I can't read... (took mixing as talking about divisibility)

I think you need to first ask the question "What does an SPV client need to validate a colored coin?"

The coin in it's present form will be in the txout set, but the history won't be, so the client needs to get a set of merkle transactions - a tx + the merkle branches back to the block header - linking the current txout representing the coin to the transaction that issued the coin in the first place.

But once you have that, why does divisibility matter anyway? Just have a standard to distinguish colored and non-colored txouts in a transaction - odd/even number of satoshi's works fine - and as you walk the transaction history dag back to the issuing transaction compute the percentage of total colored value that each txout leading to you represented. If divisibility is ever a problem in one of the transactions just add some value in the txin that isn't returned in change. Here's a concrete example:

Alice issues her "Alice Mining Bonds" and manages to sell %10 of the initial issue immediately to Bob and another %10 to Charlie: (for simplicity I'll leave off the odd-even satoshi's trick)

Charlie then turns around and sells a quarter of his share to David, and keeps the rest:


Now David has a txout worth 0.0025, and the merkle tx from Charlie and finally the initial issuing tx. He knows that he got 25% of the value of the tx Charlie gave him, and Charlie got %10 of the value of the issuing tx; %25 * %10 = %2.5 of the initial bond issue. This technique makes paying for mining fees easy, doesn't force you to tie up Bitcoins just for bonds, allows whatever divisibility is required, and having the merkle tx's available makes implementing bonds on SPV clients easy anyway.

FWIW I'm planning on having my Fidelity Bonds idea work this way.

Incidentally this also suggests a better hashing algorithm for transactions: hash the transactions themselves as some sort of merkle tree. It'd work really nicely if the intermediate hash values included the sum of the tx values under that node in the tree, so the fact that the tx was accepted into the blockchain was proof of the total txout and txin value, without having to actually have copies of any particular txin or txout. Specifically for a tx looking like this:


The hash of the txin's would be calculated as H(0.6 | (H(H(txinC) | H(0.3 | H(H(txinA) | H(txinB))))), the txouts similarly, and the final tx hash H(txin_root_hash | txout_root_hash | locktime etc). (obviously extend this with HMACs and what-not as required to deal with non-ideal hash functions)

Now for a really big issue transaction the merkle branches within the transaction itself are enough to prove the ratio of your bond vs. the issue as a whole. If the issue was for a few thousand bond-holders this is a big deal.

Also this idea can be extended to the transaction values within a block to make it harder for miners to get away with inflating the number of bitcoins to SPV clients, who now just have to pick random parts of the transaction tree to probabilisticly audit for inflation fraud via detecting non-existent transactions. Similarly SPV clients can just add the the total txin and txout values and check that the change in total number of coins from the previous block header is equal to the current block reward. Fraud due to a non-existent transaction can be broadcast by broadcasting the merkle branch suspected of not actually existing, and the broadcast can be quenched by anyone broadcasting a matching transaction. If any SPV node sees an unquenched fraud notice, they don't mine to extend that block further.

Of course, none of the above is implemented yet, but it can be implemented as a merge-mined soft-fork, the same way all the "hash of the txout set" proposals work.

EDIT: cleaned up the stuff above and posted under it's own topic: https://bitcointalk.org/index.php?topic=137933

Guys, stop worrying about the maximum blocksize. There are lots of ways to do off-chain transactions, here is one idea from Gavin, there is also Ripple and OpenTransactions, as well as more limited ways to do micro-transactions; Mike Hearn is apparently working on this concept. I've even got an idea myself.

On the other hand if we do increase the maximum blocksize we reduce the one incentive miners will always have: transaction fees. This reduces the security of Bitcoin for everyone, and makes it expensive for anyone to participate by mining or running a full node. I know it's kinda arbitrary, but keeping the blocksize at 1MB forever lets Bitcoin act as the "gold standard" of crypto-currencies, and enables a whole ecosystem around Bitcoin. If we do this in the future you'll be able to safely buy a house with Bitcoin, albeit for the equivalent of a few dollars in transaction fees, and also pay for a $1 chocolate bar with Bitcoin, albeit using a off-chain mechanism with a bit less security but a transaction fee of maybe a tenth of a cent.

The math is pretty simple really. Lets suppose we need 25x the current block reward value to keep Bitcoin secure in the future, and the reward is purely paid by fees. 25BTC * $15/BTC * 10 = $9375 USD/block. $9375/1Mib * 500bytes = $4.47 for your "buy a house transaction", yet, that will keep the total block chain size to a level, even with full history, that is at most 55GB/year. Anyone with an interest will be able to download the whole chain, still participate as a full node, and keep Bitcoin secure and inflation free for all of us.

Thanks! Glad to help.

sigh... I didn't want to mention what exactly who I exploited precisely because the network is public.


You sure you understand the attack? You don't need to mine at all to pull it off. Email me if you want further clarification.


No it's not. Because clients validate all transactions in blocks against the same rules whether the tx is in the most recent block, or how ever many blocks back, the rules for confirmation are the rules for subsequent confirmation. The rules for every single node on the network are exactly the same; if they aren't you get a network split.

On the other hand there is no single set of rules that decides if a transaction will get into a block in the first place; that's up to miners and the relay-rules of the network itself and every miner and every node can, and does, have somewhat different rules they operate by. Some miners ignore satoshidice tx's, other miners ignore zero fee tx's; it's all over the place.


I'm not one of the core dev's, so maybe they think otherwise, but I'm pretty sure they'd agree that building API's to allow zero-conf transactions to be accepted "safely" sounds like a world of hurt. It's a moving target for one thing as attacks are discovered, and in addition the best ways of detecting them can't be done unless you have access to many different nodes to do network propagation measurement.

If you want to allow zero-conf tx's to be accepted safely, start a service to do so. Have staff that maintain this service, do constant risk analysis and continual threat detection, and if you have good reason to believe your counter-measures are adequate, offer insurance on transactions using the service. It's not a new idea, but there isn't anyway doing it right now as far as I know, so maybe you can make it work?

Putting this functionality in the satoshi client just leads people to believe the functionality works properly. It'll just lead to more examples of people getting defrauded, and we don't need that.


The API's already let you use Bitcoin safely: just don't accept unconfirmed transactions.


It'd be nice of you to ask the core-devs and other members of the community about when is right to release the full details. In addition, when that time comes, I think it'd also be nice to let me do it.

How easy a security problem is to fix has little to do with how dangerous it is until you fix it.

You know, I actually performed this attack, and quite successfully steal a few Bitcoins worth of a service from a site. I don't know what safeguards the site happened to have, but it's not implausible that I could have made off with thousands. (the site has been fixed)


If they know about the issue.

Bitcoin isn't just big well-run sites you know. It's a huge eco-system with a lot of small players, many we probably don't even know about, and many of those unknowns probably don't follow the forums all that closely. It's also average people running Bitcoin clients, and those clients are vulnerable too. Lots of people use Bitcoin but don't understand the intricacies of how it really works, such as why zero-confirmations is easily orders of magnitude less secure than one-confirmation.

I'll guarantee you that some scammer will try to separate some new user from their Bitcoins using this exploit in a over-the-counter trade on irc or face-to-face: "guess it's just taking awhile to confirm, nah, don't be worried, happens all the time, look I gotta go pick up the kids, can you send me the paypal tx?" Previously we thought the scammer in that scenario at least had have access to a bunch of machines and some luck, but it turns out that's not true. From the point of view of that average guy making a otc trade, yes there has been a fundamental shift: a shift from attacks that are annoying and difficult to pull off consistently to one that works reliably every time.

Those major sites are more than capable of asking a member of the dev team. As for why this was published on the forums, easy: not accepting zero-conf tx's has a fairly low cost; it's perfectly reasonable to tell people, yet again, to stop doing it unless they can afford to be defrauded. Not to mention, it's much safer to make the announcement now, in public, than to hope that while we go off telling big sites in secret no-one else figure it out, or the secret leaks.

It took me a week to apply for my PayPal account back in the day.

You know what turns potential new users off of Bitcoin? Headlines like "Bitcoin hacked! Thousands lose all their Bitcoins!"

If having to wait ten minutes to an hour is what makes you not want to use Bitcoin, how about you wait until we come up with a overlay network on top of Bitcoin with instant transactions? It'll happen eventually; I'm working on one such concept myself.

Risk vs reward. No offense to Hal, but 25% isn't a very big improvement, and signature verification is something that absolutely must work correctly. Get it wrong and people can lose a lot of money very quickly. Why risk it?

Basically we used to think double-spending a zero-confirmation transaction took some effort, and doing so could be detected by the receiver. It turns out that's not true.

Now my advise for a business is pretty simple: ensure that your business logic for how you accept Bitcoins is designed in such a way that you can determine the total amount of zero-confirmation transactions you are accepting at any one time, and limit that amount to a level where you would be OK is every one of them was reversed. Watch them carefully and be willing to stop accepting them at all if problems develop.


This problem is something that affects a wide range of Bitcoin-accepting software; it is not specific to the satoshi implementation. Patching and deploying a fix isn't something that can be done by the Bitcoin developers themselves. Not accepting zero-conf transactions however is something everyone can do.

Yes. This technique is different.

No. I happen to be a member, but I found the problem entirely by myself and have no special role within the foundation. gavinandresen, gmaxwell and other core devs know, but beyond that I do not know who else has been told about the issue other than a highly vulnerable site whom I informed personally.

That's unfortunately not true. Bitcoin-QT is affected.

If you do not accept zero-confirmation transactions this vulnerability does not affect you.

However if you do be advised that a previously unknown coin-stealing attack has been found that allows zero-confirmation transactions to be double-spent with a trivial amount of effort and without having to have access to any mining capacity.

Details will be release as soon as a patch is ready. In the meantime do not accept any transaction without at least one confirmation unless you fully trust the sender not to defraud you.

Mods: please copy this to important announcements.

Sort of. Bitcoin's can be "destroyed" by making them unspendable, but this example is unique in that it is one of two ways that that it causes the total number of Bitcoins in existence, spendable or not, to be less than what it could be. Since this can happen with a block with no other transactions, the Bitcoins are essentially never created in the first place.

The other way is the duplicate transaction bug, where the satoshi client assumed that it was impossible to create two transactions with the same transaction hash. As it turns out that's not true, and thus it's possible to overwrite a transaction, destroying the first one, which means that as measured by the set of unspent transaction outputs, the coins no longer exist. This has happened on the main chain: the coinbase of block 91812 is duplicated by 91842 leaving 50 less BTC spendable. BIP30 fixes this problem, so without an actual hash collision this this will not be possible any more soon.

Edit: Fixed link