An insertion occurs when, given a chain C with two consecutive
blocks B and B, a block B* created after B′
is such that B , B*, B′ form three consecutive
blocks of a valid chain.
- For an insertion to occur in the Bitcoin blockchain, block B* would need to be a valid child of B:
- a valid block at the corresponding height
- commit to B as its
- B* would also need to be a valid predecessor of B':
prevBlock in block B' would need to match the hash of B*
- Finally, the block B' would need to be a valid block at a height one greater than the one it was previously found at.
These requirements are not just improbable but actually impossible to fulfill. Condition 1. is costly in that it requires expending sufficient work to fulfill the proof-of-work requirement of a valid block. Condition 2. would require finding a block that hashes to an exact value. This means breaking second pre-image resistance of SHA-256 which is considered infeasible. The good news is that if we can break second pre-image resistance, we can also find valid blocks more easily; the assumption that partial pre-images are hard to find are the core assumption of Bitcoin's proof-of-work algorithm. Finally, fulfilling condition 3. is impossible: each block commits to a specific block height in their coinbase transaction as required by BIP34. A block therefore can only be valid at exactly one height in a chain, and inserting another block in front of it invalidates the block.
Looking at the paper, it seems to me that that Definition 8 is chiefly used to prepare Definition 9 (emphasis added.):
Definition 9 (Typical execution). An execution is (ϵ, λ)-typical (or
just typical), for ϵ ∈ (0, 1) and integer λ ≥ 2/f, if, for any set S
of at least λ consecutive rounds, the following hold.
(a) (1 − ϵ)𝔼[X(S)] < X(S) < (1 + ϵ)𝔼[X(S)] and (1 − ϵ)𝔼[Y (S)] < Y (S).
(b) Z(S) < 𝔼[Z(S)] + ϵ𝔼[X(S)].
(c) No insertions, no copies, and no predictions occurred.
I.e. the authors are trying to describe the three defined occurrences as atypical execution.