I don't think it's feasible. You don't just walk into a store and buy plut rent this kind of hashrate, it still requires a lot of preparation. GPUs will soon be obsolete and ASICs are Application Specific, a provider of SHA-256 ASICs is a hash market. And I still think if it becomes possible we lose anyway, since the security will be only linear in the number of confirmations. A fuller treatment of this is under the scope of more accurate economic modeling.

Great.

Well, first it's worth pointing out exactly how much effort was involved. I have spent about 12 hours working on this paper. It is this low because the paper is something of a "v Pravde net izvestiy, v Izvestiyakh net pravdy". There is really nothing new in sections 1-5. 1-2 are just common knowledge (added for context), 3-5 (which are what I really wanted to write) are just drilling down the analysis in Satoshi's paper. The only differences are:

1. Instead of a Poisson distribution, I used a more accurate negative binomial distribution.
2. I assumed the attacker needs to be 1 block ahead to win, but also that he pre-mines a block a la Finney; these two cancel out. Also, there is some ambiguity about how Satoshi counts the confirmations.

Writing when you know what you want to write doesn't take that much time. (It does require a specific state of mind which is not always available.) Half the time was spent figuring out how to properly align the blockchain diagrams.

Section 6 is mostly novel and required some research, but it's not meant to be authoritative, more of a starting point for additional analysis. I included it because the paper wouldn't be complete without it.

My primary motivations for writing this were:

1. I hate misinformation and myths. When I see important mistakes constantly being repeated I want to do something about it. It might end up saving me time by sparing the need to correct the mistakes every time.
2. It can signal my skills and commitment to Bitcoin, which may help expand my business opportunities (aka indirect monetization).
3. While it is hard work, some of it can also be fun (the math part, not the figuring out xy-pic part).

Altruism plays variable roles in different things I do, but I can't honestly say it had more than a minor influence on this in particular. So all in all #1 is why I wanted to do this, #2 is why I could justify allocating time to it, and #3 is a perk.

That's the one. I haven't spent time thinking about it in a while, AFAIR it's not completely fleshed out yet, but I think these ideas are the key to preventing a majority attack that rejects all transactions.

Yes. (It's 2.5 min so 7.5 min).

1. Yes, because it's more accepted. If we switched to a new currency every year because of some alleged trivial benefit, we would miss the point.
2. Decreasing the average block time has the obvious benefit of reducing time for confirmations. But it has equally obvious disadvantages:
a. There is more forking, meaning an attacker has more effective hashrate. I've ignored inadvertent forking completely in the paper, but it starts being a problem if we go wild with reducing the time constant.
b. There are more blocks, and hence more block headers. For a full node this is negligible but for an SPV (aka lightweight) client this makes a world of difference, especially if it is to be run on weak mobile devices.
So some tradeoff needs to be chosen. It can be argued that 2.5 min is better than 10 min, but it's far from clear-cut.
3. It doesn't really matter ultimately. If you can afford to wait more than a few seconds, you can usually afford to wait an hour. If not, I believe the gap can be bridged with Trustless, instant, off-the-chain Bitcoin payments.
4. Because Litecoin might be more prone to botnets.

Interesting, need to think about this.

This is indeed what a DAG is and I think we're thinking about the same proposal. I might try linking to it sometime.

This seems equivalent to cementing, see above.

Yes, for a given amount of average waiting time. In practice you'll start with the level of security you want, from it deduce the number of confirmations, and this will determine the average wait time; in Litecoin it will be shorter than in Bitcoin.

Thank you.

I'm not currently associated with any university, but I originate from the Weizmann Institute of Science, so if I push this forward it may be done in collaboration with them. My thesis advisor is a member of a group that is interested in Bitcoin.

I've never published any papers so I don't know what the procedure would be, and for now I'm sticking to myself and maybe ArXiv.

If the attacker has some minimal hashrate, he can double spend quite easily with the Finney attack.

If not and the attack is based purely on propagation, I should point out that there is already a paper on this subject, Two Bitcoins at the Price of One? Double-Spending Attacks on Fast Payments in Bitcoin. I haven't studied it in depth.

I agree with your analysis, but would like to add that the client can be modified to respond to queries "Do you know of a transaction that conflicts with T1?". This way, if a peer hears about T1 and then T2, he will not forward T2 to the merchant, but he may respond that he is aware of it, giving the merchant another chance at detecting a possible double-spend.

I think these questions can be answered with some modeling assumptions (and this may have been done in the linked paper). If more is required I'm open to solicitations for further research.

Thank you again for your generosity. I should point out though that (assuming this is relevant) more pledges would be needed for me to undertake entirely new research at this point.


This is out of the scope of the devs, it's a core protocol issue. I think defending against casual double-spenders is certainly feasible. The real problem is with well-funded entities trying to harm Bitcoin with majority attacks.

There are some proposals for alternative systems (e.g. proof of stake), but they are fairly controversial. I think the solution to DoS attacks is a DAG system as was described once by Maged.

Since making more payments before finalizing the list is very messy, and Nefario says he'll have more accounts for me, I'll give about a week before moving forward.

There's an alpha Armory-based CC client with most of the needed functionality, I expect I'll be able to issue a CC version in about 2 months.

Update: It's not really related, but I've finally received some coins from GLBSE. It's a Hanukkah miracle! I don't yet know for sure what portion this is of my entire deposit.

It is. 6 confirmations is equivalent to 6 confirmations and 60 confirmations is equivalent to 60 confirmations. The probability of success is uniquely determined by the number of confirmations and the attacker's percentage of the total hashrate. With these two fixed, it does not at all matter what are the difficulty, the total hashrate, the average time between blocks, or the actual time it took to find those confirmations.

Frankly, I don't see why I have to repeat myself. I have stated my result, provided a derivation for it, and clarified it in previous comments. If you disagree, you should either point out a flaw in my argument, or provide a derivation for an alternative result which we can then discuss.

Yes (which means once a block is found its timestamp cannot be changed), but there is some wiggle room. Also, a new node joining the network has no idea whether blocks which are given to him were actually found at the time specified by their timestamp.

Right, but I want to reduce middleman risk if possible, and I expect that getting my desired position with options will entail very high friction.

Assuming the same number of confirmations, there is the same variance in the number of blocks found by the attacker.

Assuming the same wait time, a reduced difficulty means more blocks found on average. For Poisson-distributed variables, the variance is equal to the mean, so the standard deviation is equal to the square root of the mean. With a larger mean, the relative standard deviation is lower.

Yes. But this is dwarfed by the fact that with a lower difficulty, you can increase the number of confirmations with the same wait time and greatly reduce the probability of success (which is the main factor in the economics of the attack).

The attacker can mine away and only start the attack when he finds a block. This is easy to do even with a low hashrate. If you are familiar with the Finney attack, it is a special case of this where the number of confirmations is 0, and hence the probability of success is 100%, with any hashrate.

He could do that, and a fuller treatment of this is under the scope of the economic discussion. However, there is a big gap in the effectiveness of pre-mining one vs. two. Pre-mining 1 block is a "sure thing" as the attacker counts on finding a block anyway, so he may as well postpone the attack until he does. But after he finds the first block, waiting to get more blocks just puts him at risk that the honest network will regain the lead. If this happens he loses the reward of the block he found. He is in a hashrate disadvantage so he's better off pressing his head start.

If the only attack cost is the lost block reward, then he should pre-mine just one block because the risk of losing the reward is the same and this gives him a better chance to benefit from it. If, however, the main cost is the illiquidity of the goods purchased, he should indeed make multiple attempts to pre-mine several blocks, and call the thing off with every failure.

Right. (When the number of confirmations is equal.)


Another way to look at this: If the attacker does not have majority, he will find on average less blocks than the honest network. If the average thing always happened, he would always fail. Variance in the number of blocks works to his advantage, because he has a chance to be lucky and get more than the average number of blocks, enough to beat the network. Assuming a fixed (#blocks * avg. time), the smaller the avg. time, the more individual items are being tracked, and so (as is the case with these Poisson processes) the lower the relative variance, and the lower the chance to luck out. This is similar to how mining pools reduce variance by basing the reward on tracking the number of abundant shares, rather than the number of rare blocks.

I don't know. It's pretty old.

Thank you.

This is indeed what they argue, and this is wrong.

I understand the distinction and not trying to set up a strawman, it's just too wordy. Their actual argument as stated above really is a myth.

The key observation is that the process is entirely non-temporal. It's a series of discrete turns where each party has a chance to move a step ahead. The probability of success relies on the properties of this Markov chain, and there is no place where the time constant can have an effect. Of course, if we were talking about the time it takes to complete the attack, things would be different.

Yes, and hence reflect the average amount of work an attacker would need to do to overturn them. But not the probability of success, when the actual number of blocks (and the hashrate) is invariant.

I've been meaning to write a post discussing a framework for various levels of synchronization, where each can be cemented but overturned by the next. For a few months now, haven't gotten around to it yet.

I tend to agree, but let's see where this is going.

Bumping for being still/again relevant. Amount was updated to 500 BTC for now, smaller amounts will also be considered.

The way I see it, there are 3 major differences between Jesse's and Andrew's versions of Jesse's words:
1. Porn vs. CP.
2. Mostly vs. only.
3. Gambling vs. no mention of it.

#1 is important because all 3 uses Jesse mentioned are merely controversial, while CP is universally shocking.
#2 is important because, while the word "only" is of course not to be understood literally, there is a difference between "any other use is unheard of" and "the bulk of activity is these, leaving plenty of room for more legitimate activities".
#3 is important because the inclusion of gambling tilts the scale towards the possible truth of the statement.

It was fairly clear from Andrew's story, and Jesse confirmed, that some humorous effect was intended, which also should be taken into account. The statement may or may not be true, and I wouldn't be happy about it being true, but it's a reasonable way to lampshade Bitcoin's negative portrayal in popular media. It's not the first thing I would say about Bitcoin, but to each his own methods .

Why bother? The article isn't very good, and apparently it is primarily a translation of one from Le Monde.

It has several mistakes, the biggest one being that "Bitcoin has become a PSP", which itself was copied from an even worse article (entirely based on this mistake) in TheMarker, which I also considered important until now.

I offered a correction to the TheMarker paper, but they censored it. Let's see how my comments in Ha'aretz fare (they belong to the same group).

I call this practice "cementing" and it has some problems, similar to what we would have if there was no blockchain at all. The basic idea is that a node could be stuck on "the wrong version" after being isolated and fed bad data from an attacker, and would have no way to recover even after being exposed to the honest network.

There are some ways to work with that but it's far from simple.

Yes, it does. I am explicitly discussing hashrate-based attacks with the vanilla protocol, disregarding additional layers of protection such as hardcoded checkpoints and proof of stake.

With the current schedule of checkpoints, it is not practical to consider waiting for a checkpoint to accept payment.

In Satoshi's original whitepaper, he concludes with discussing double-spending attacks and their probabilities of success. This section does not get the attention it deserves, unfortunately, leading to several widespread myths:

Myth. Double-spending requires having more than half of the network hashrate.

Myth. Waiting for confirmations offers meaningful protection against an attacker with majority hashrate.

Myth. There is something special about 6 confirmations, and/or it grants absolute protection.

Myth. The important factor is the amount of time spent waiting for confirmations, rather than the number of blocks. (Still a myth if instead of actual time you look at #blocks * average time per block).

In Analysis of hashrate-based double-spending, I elucidate and build on Satoshi's work in this area. I explain the basics of double-spending and derive the probability for its success. I provide various graphs and charts for this probability. I also give a simplified model for the economics of double-spending.

Some of the key conclusions are:

• Hashrate-based double-spending boils down to a race between an attacker and the honest network. In every turn one of them moves a discrete step forward, each with a probability determined by their relative hashrate. A successful attempt means managing to catch up with the honest network, a failure means falling so far behind there is no longer a chance of catching up.
• Successful double-spending is possible with any attacker hashrate. There is no need for a majority to carry out this attack.
• Waiting for more confirmations exponentially decreases the probability of double-spending success. The decay rate depends on the attacker's relative hashrate.
• The probability of success depends on the number of confirmations and not on the amount of time waited. An alternative network with a shorter time between blocks can thus obtain more security with a given amount of wait time.
• The time constant might be relevant, if we assume that the attacker cannot sustain his hashrate for a prolonged period of time. In this case, even majority hashrate does not guarantee success, as the attack could take more time than available. However, it does not seem likely that an attacker would go through the trouble of obtaining enormous computational resources and only maintain them for a time short enough to make this consideration relevant.
• No amount of confirmations will reduce the success rate to 0.
• If the attacker controls more hashrate than the honest network, no amount of confirmations will reduce the success rate below 100%.
• There is nothing special about the default, often-cited figure of 6 confirmations. It was chosen based on the assumption that an attacker is unlikely to amass more than 10% of the hashrate, and that a negligible risk of less than 0.1% is acceptable. Both these figures are arbitrary, however; 6 confirmations are overkill for casual attackers, and at the same time powerless against more dedicated attackers with much more than 10% hashrate.
• In practice, the probabilities of success are less relevant directly, than as a major factor in determining the economics of an attack.
• Economic modeling is complicated, and some additional factors come into play. The time between blocks can affect the economics, and even with majority hashrate an attack might not be economical despite the guaranteed success. However, by the time the latter factor becomes relevant, the security is anyway weak beyond redemption.

50 BTC more received, 0.01 BTC per bond sent (counts as $0.12).

PS. To all whom it may concern, 17mE6CjNxCKn51yAQuVx3ERq1qT5uYyRLr is an address in my Bitcoin-qt wallet and the main address I use to receive payments from Alberto. I send funds from Bitcoin-qt (not necessarily the same coins) to my blockchain.info address 14ubeus6MbjWqy13x2uFPS6XFUyE92ty96 to be used with sendmany.

This is a myth, and a dangerous one at that.

It is fine if Mtgox wants to be safer than strictly necessary. But if they believe that 6 confirmations are somehow special and magically safe, and fail to incorporate it in a complete risk management solution, it can have disastrous consequences.

Optimally, the system will credit increasing amounts based on the number of confirmations. For example, someone deposits some amount X of bitcoins. After 1 confirmation 10 BTC will be credited. After 2 confirmations, 30. 3: 100. 4: 300. 5: 1000. 6: 3000. 7: 10000. And so on, until the entire deposit is credited. This system also needs to properly handle multiple simultaneous deposits.

While simple and efficient, it can be understood if Mtgox wishes to avoid confusing themselves and the customers, and properly handling the number of confirmations can be "outsourced" to smpake-style services.

Right, and the scale can be set up so that the expense is always greater than what they can get away with.

I agree with the spirit of this, but the numbers are way off. The success rate is not simply q^(n+1).
The correct numbers for 20% are: 1:40%, 2:20.8%, 3:11.6%, 4:6.67%.

As we speak I am finishing a paper analyzing double-spending success probabilities in more detail, including more accurate formulas and tables. I will link to it here when done.

Edit: Said paper is available here, and this is the thread for discussing it.

Right, both the bondholders and myself are victims of the GLBSE mess, in different ways. We all signed up to deal with the fallout of a problem with GLBSE, even if we hoped it wouldn't happen, or that it wouldn't be this bad.

I'm using a time tracking software I wrote to keep a record of what I do every minute of every day. I haven't gotten yet to the part of displaying the total per time period, if I ever do it will be interesting to see how much time I've spent on this since GLBSE shut down.