What would be an example for an insertion into the blockchain?

Question

I'm reading the paper The Bitcoin Backbone Protocol: Analysis and Applications. On page 21, definition 8 reads:

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. A copy occurs if the same block exists in two different positions. A prediction occurs when a block extends one which was computed at a later round

The word round seems to be indicating that the network is considered synchronous and time is divided into rounds. My understanding is that an insertion has a negligible probability but what would it look like if it did happen? I could use an example and more explanation for how insertions could happen and under what conditions.

Answer 1

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.

1. 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 prevBlock

2. B* would also need to be a valid predecessor of B':

• The prevBlock in block B' would need to match the hash of B*

3. 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.