5

Section 11 presents calculations of the probability of double spending, P(z, q), given an attacker relative hash rate q and a block count z.

Calculations

P(z, q) can only be understood by knowing exactly what z represents. From the Calculations section:

The recipient waits until the transaction has been added to a block and z blocks have been linked after it. He doesn't know the exact amount of progress the attacker has made, but assuming the honest blocks took the average expected time per block, the attacker's potential progress will be a Poisson distribution with expected value... [my emphasis]

Clearly, the transaction has one confirmation. The transaction "has been added to a block" and zero blocks have been linked after it. In other words, the transaction is hosted by the tip of the active chain.

Nevertheless, the probability of this transaction being double-spent is 100%, regardless of the attacker's hash power. In fact, the probability is 100% even with no active attacker.

This contradiction is reinforced by the equation Satoshi gives:

enter image description here

When z = 0, P = 1.0.

What am I missing?

There is at least one answer to this question that claims that z=0 means that the transaction is unconfirmed. That's inconsistent with the paragraph I quoted.

There appears to be an error somewhere in the Calculations section leading to a contradiction. I'm looking for an answer that either points the error out, or explains what I'm misinterpreting.

EDIT

One response offers the suggestion that Satoshi may have been talking about a Finney attack. In other words, the attacker has already pre-mined a block before attempting the double spend. Assuming the attacker can propagate blocks faster than the network, there would be a 100% chance of success. In this scenario, the attacker and network are tied at z=0, and given faster block propagation, the advantage goes to the attacker.

However, the Calculations section explicitly disallows a Finney attack. In particular, the attacker has mined no blocks prior to the attack:

The receiver generates a new key pair and gives the public key to the sender shortly before signing. This prevents the sender from preparing a chain of blocks ahead of time by working on it continuously until he is lucky enough to get far enough ahead, then executing the transaction at that moment. Once the transaction is sent, the dishonest sender starts working in secret on a parallel chain containing an alternate version of his transaction.

I believe at least part of the problem is mathematical. Specifically, Satoshi gives the value of λ as:

enter image description here

When z=0, λ=0.

Referring back to Satoshi's original derivation of double-spending probability P(z, q):

enter image description here

λ=0 means that every term is zero, independent of hash rate. In other words, the attacker can never double spend.

This contradicts the "rearranged" form of the equation, which gives a probability of 100% as noted above.

I'm no math specialist, but from what I can tell, the two forms of P(z, q) that Satoshi gives are not equivalent for z=0. In fact, they give the opposite answer:

  • in one case, the attacker always fails, P(z, q) = 0
  • in the other case, the attacker succeeds with 100% probability, P(z, q) = 1.

Either way, the attacker's relative hash rate doesn't factor into the analysis when z=0.

I realize that other treatments of this problem have appeared. For now, I'm just interested in fixing the apparent problem with the white paper's analysis for z=0.

Is this possible, and if so, how can I do that?

3
+25

One way to interpret this is that there is, indeed, a mistake.

A more charitable interpretation is that there are two unstated assumptions:

  1. The attacker is performing a Finney-like attack - that is, he has already pre-mined a block before even attempting the transaction. So while z=0 means the honest network has 1 block, so does the attacker.

  2. The attacker wins propagation races. So if there is a leaf attacker block with the double-spending transaction, and a same-height leaf honest block with the original transaction, the attacker's transaction will be accepted.

Together, these give a 100% chance of success for the attacker if there is only 1 confirmation.

In my own paper on the subject, I have explicitly stated the assumption that the attacker already has one block (while removing a different simplifying assumption).

  • This makes sense, thanks. In that case, shouldn't the probability of the attacker already having mined the block be factored in? In other words, an attacker with low relative hash rate will not very often be in a position to start the attack in the first place. – Rich Apodaca May 31 '18 at 18:40
  • 1
    @RichApodaca: The probability that the attacker has already mined a block is 100%, given that he has already mined a block. That is, a low-hashrate miner will not have a lot of opportunities to perform an attack - but he will not even attempt to purchase from the merchant until he has an opportunity, and when he does, it will be when he has found a block. So the attack will definitely succeed if the merchant doesn't wait for confirmations. – Meni Rosenfeld May 31 '18 at 18:45
  • 1
    @RichApodaca: The attacker will also need to complete the purchase itself immediately, before the block he has just found is orphaned, just like in the Finney attack. It is something of a stretch, which is why arguing that Satoshi was simply careless with his calculations is just as reasonable. – Meni Rosenfeld May 31 '18 at 18:48
  • The Calculations section explicitly rules out a Finney attack: "Once the transaction is sent, the dishonest sender starts working in secret on a parallel chain containing an alternate version of his transaction." In other words, the attack begins with no blocks mined by the attacker. – Rich Apodaca Jun 3 '18 at 19:19
2

Does z = 0 mean that a transaction hasn't yet been confirmed, or that it has been confirmed but its block hasn't yet been extended?

Z = 0 means that the transaction has not yet been confirmed. The probability is 1 because, under the assumptions made for these calculations, unconfirmed transactions can always be considered insecure and double spendable by the attacker regardless of their hashrate.

  • z=0 clearly means that the transaction has one confirmation: "The recipient waits until the transaction has been added to a block and z blocks have been linked after it." In other words, the transaction has been added to the tip of the active chain. – Rich Apodaca May 31 '18 at 15:13
  • @RichApodaca z=0 clearly represents the point where the race starts (honest chain vs attacker chain). If you want to be pedantic about it, assume that both chains have one block each (same height). – Mike D May 31 '18 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.