<blockquote>
<p>An <em>insertion</em> occurs when, given a chain <em><strong>C</strong></em> with two consecutive
blocks <em><strong>B</strong></em> and <em><strong>B</strong></em>, a block <em><strong>B*</strong></em> created after <em><strong>B′</strong></em>
is such that <em><strong>B</strong></em> , <em><strong>B*</strong></em>, <em><strong>B′</strong></em> form three consecutive
blocks of a valid chain.</p>
</blockquote>
<ol>
<li>For an insertion to occur in the Bitcoin blockchain, block <em><strong>B*</strong></em> would need to be a valid child of <em><strong>B</strong></em>:</li>
</ol>
<ul>
<li>a valid block at the corresponding height</li>
<li>commit to <em><strong>B</strong></em> as its <code>prevBlock</code></li>
</ul>
<ol start="2">
<li><em><strong>B*</strong></em> would also need to be a valid predecessor of <em><strong>B'</strong></em>:</li>
</ol>
<ul>
<li>The <code>prevBlock</code> in block <em><strong>B'</strong></em> would need to match the hash of <em><strong>B*</strong></em></li>
</ul>
<ol start="3">
<li>Finally, the block <em><strong>B'</strong></em> would need to be a valid block at a height one greater than the one it was previously found at.</li>
</ol>
<p>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 <a href="https://en.wikipedia.org/wiki/Cryptographic_hash_function#Properties" rel="nofollow noreferrer"><em>second pre-image resistance</em></a> 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 <a href="https://github.com/bitcoin/bips/blob/master/bip-0034.mediawiki" rel="nofollow noreferrer">BIP34</a>. 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.</p>
<p>Looking at the paper, it seems to me that that Definition 8 is chiefly used to prepare Definition 9 (emphasis added.):</p>
<blockquote>
<p>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.</p>
<p>(a) (1 − ϵ)[X(S)] &lt; X(S) &lt; (1 + ϵ)[X(S)] and (1 − ϵ)[Y (S)] &lt; Y (S).<br />
(b) Z(S) &lt; [Z(S)] + ϵ[X(S)].<br />
<strong>(c) No insertions, no copies, and no predictions occurred.</strong></p>
</blockquote>
<p>I.e. the authors are trying to describe the three defined occurrences as atypical execution.</p>

CC BY-SA 4.0
2020-08-11T17:05:06.967Z
2020-08-11T17:05:06.967Z
Murch
<p>I'm reading the paper <a href="https://eprint.iacr.org/2014/765.pdf" rel="nofollow noreferrer">The Bitcoin Backbone Protocol:
Analysis and Applications</a>. On page 21, definition 8 reads:</p>
<blockquote>
<p>An <em>insertion</em> occurs when, given a chain <em><strong>C</strong></em> with two consecutive
blocks <em><strong>B</strong></em> and <em><strong>B</strong></em>, a block <em><strong>B*</strong></em> created after <em><strong>B′</strong></em>
is such that <em><strong>B</strong></em> , <em><strong>B*</strong></em>, <em><strong>B′</strong></em> form three consecutive
blocks of a valid chain. A <em>copy</em> occurs if the same block exists in
two different positions. A <em>prediction</em> occurs when a block extends
one which was computed at a later round</p>
</blockquote>
<p>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.</p>

CC BY-SA 4.0
2020-08-11T17:07:02.500Z
Hi @mike, I've edited your question to include the context you had provided in the comments. Please see whether my edit left the gist of your question intact, otherwise please feel free to rollback or edit as you wish.
Murch
<blockchain><hash><academic-research><height>
What would be an example for an insertion into the blockchain?
mike
# What would be an example for an insertion into the blockchain?

(Asked by: username_0 on 2020-08-02)

I'm reading the paper [The Bitcoin Backbone Protocol:
Analysis and Applications](https://eprint.iacr.org/2014/765.pdf). 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.

**Tags:** blockchain, hash, academic-research, height

> **Comments:**
> **username_1**: Hi @username_0, I've edited your question to include the context you had provided in the comments. Please see whether my edit left the gist of your question intact, otherwise please feel free to rollback or edit as you wish.  

---

## 1 answers

### Answer by username_1 on 2020-08-11. Score: 0 | Accepted answer

> 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*](https://en.wikipedia.org/wiki/Cryptographic_hash_function#Properties) 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](https://github.com/bitcoin/bips/blob/master/bip-0034.mediawiki). 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.


---

