<h2>Malleability in the context of Miniscript</h2>
<p>Malleability is the possibility for a third party to turn a valid satisfaction into another valid satisfaction. That is, to change the witness in the input of a transaction without making the transaction invalid.</p>
<p>There are various shortcomings to malleable witnesses. Witnesses add to the size of the transaction, so if a witness can be malleated such as to inflate the size of a transaction it could hinder its confirmation by reducing its feerate. Note this may &quot;just&quot; be a simple nuisance for regular usage of onchain transactions, but this could have more serious consequences for contracts that rely on the timely confirmation of a transaction.<br />
In addition, using malleable satisfactions can have negative external effects on the network modified witness can affect <a href="https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki" rel="nofollow noreferrer">BIP152</a> block propagation (which is based on the <code>wtxid</code> for Segwit transactions).</p>
<p>Malleability is discussed in more details <a href="https://bitcoin.sipa.be/miniscript/" rel="nofollow noreferrer">here</a>.</p>
<h2>Malleability static analysis in Miniscript</h2>
<p>Malleability appears whenever two valid satisfaction for a fragment are available to a third party. Note that a fragment's satisfaction may contain a dissatisfaction of a sub-fragment.</p>
<p>There are 3 ways that malleability may be introduced:</p>
<ol>
<li><strong>Two valid solutions are directly available to the third party.</strong> For instance let's say the third party knows the preimage to SHA256 hashes <code>H1</code> and <code>H2</code> and a script like <code>and_v(v:or_i(sha256(H1),sha256(H2)),pk(A))</code> is used.</li>
<li><strong>A single valid solution is directly available to the third party, but a participant in the Script uses another one.</strong> For instance let's say the third party knows the preimage to SHA256 hash <code>H1</code> but not to SHA256 hash <code>H2</code> and a script like <code>and_v(v:or_i(sha256(H1),sha256(H2)),pk(A))</code> is used. If the participant satisfies this script by providing the preimage for <code>H2</code>, the third-party can replace the satisfaction by one providing the preimage for <code>H1</code>.</li>
<li><strong>The participant provides a witness containing a satisfaction for a certain sub-fragment that can be turned into a dissatisfaction.</strong> For instance let's say the third party knows nothing, but <code>or_b(pk(A),a:pk(B))</code> is used and a participant spends by providing both a signature for keys A and B. A third party can turn the signature for either A or B to the empty vector without invalidating the witness.</li>
</ol>
<p>In order to make sure malleability may not be inadvertently introduced when spending from a Miniscript, new properties are introduced in the type system based on a set of general assumptions about what material may be available to a third party.<br />
It is assumed:</p>
<ul>
<li>they don't have access to <em>any</em> private key in the script;</li>
<li>they don't have access to more hash preimages than those revealed in the initial witness;</li>
<li>they only get to see a single witness produced by participants (otherwise they can mix-and-match);</li>
<li>no public keys are repeated in the script (otherwise a signature for a fragment may be &quot;replayed&quot; for satisfying another fragment).</li>
</ul>
<p>The properties are:</p>
<ul>
<li>whether satisfying this fragment requires a signature (that is, the satisfaction is not available to a third party);</li>
<li>whether dissatisfying this fragment requires a signature (same but for dissatisfaction);</li>
<li>whether a single dissatisfaction that does not require a signature exists, and others, if there is any, require a signature (that is, the fragment may be safely dissatisfied).</li>
</ul>
<h2>Non-malleable satisfaction algorithm and your example</h2>
<p>Malleability is checked at creation time, and a Miniscript that does not contain at least one non-malleable satisfaction per spending path will be marked as unsafe (/insane). Note this does not rule out the existence of malleable satisfactions in addition to non-malleable ones. The satisfier needs to take care to only use satisfactions that are non malleable.</p>
<p>Your interpretation of the algorithm is correct. The non-malleable satisfier will refuse to use the satisfaction for <code>or_b</code> that satisfies both branches, even if it has the required material. However it will use any of the two non-malleable satisfactions available.</p>
<blockquote>
<p>That said, could you explain to me what would be the problem if OP_0 OP_0 &lt;sig(key)&gt; was used instead of OP_0 OP_1 &lt;sig(key)&gt;?</p>
</blockquote>
<p>It would allow a third party to change a valid witness into another one, see the section above for rationale.</p>
<blockquote>
<p>Or does perhaps there mean all or_b sats should be marked as DONTUSE?</p>
</blockquote>
<p>No, otherwise there would be no point in having an <code>or_b</code> fragment. :) Only all non-canonical satisfactions of <code>or_b</code> need to be marked as <code>DONTUSE</code>.</p>
<h2>Related notes</h2>
<p>Also note that malleability analysis assumes common standardness rules, such as <code>MINIMALIF</code>. So a miner could still malleate some witnesses even if they are treated as non-malleable by Miniscript.</p>

CC BY-SA 4.0
2022-12-07T15:52:03.630Z
Thanks Antoine. I kind of follow the general reasoning but then fail to understand how it applies to the particular example I provided. I guess I'm still not fully understanding it. What **exactly** could do an attacker if he saw `OP_0 OP_0 <sig(key)>` in the mempool (I guess this is the idea) that could not do if he saw `OP_0 OP_1 <sig(key)>`? The attacker can convert one into the other. Why is one then considered malleable and not the other? Also the attacker could convert both solutions to a dissatisfaction by replacing them with OP_1 OP_1 <sig> for example.
landabaso
CC BY-SA 4.0
2022-12-07T15:56:54.363Z
First note that your Miniscript here is malleable in any case, so it's not a surprise it may be malleated in various ways. Both the satisfactions in your comment are malleable. What an attacker can do if you use that is add more roundtrips to compact blocks or transaction relay on the network. Converting a top-level satisfaction to a dissatisfaction by definition makes the transaction invalid, so it isn't a concern. :)
Antoine Poinsot
CC BY-SA 4.0
2022-12-07T16:09:17.603Z
Makes sense! My feeling was solutions were malleable in various ways. I could not get why `OP_0 OP_1 <sig(key)>` was not malleable. I was applying the "Non-malleable satisfaction algorithm" assuming the miniscript was sane. I had put the miniscript into the tool at: https://bitcoin.sipa.be/miniscript/, which provided a valid Bitcoin script and I assumed that this meant it was sane.
landabaso
CC BY-SA 4.0
2022-12-07T15:07:30.910Z
2022-12-07T15:38:14.973Z
2022-12-07T15:38:14.973Z
Antoine Poinsot
<p>I'm having some trouble understanding malleability in miniscript. Specifically I cannot get why some solutions can be used instead of other.</p>
<p>I think using an example may help.</p>
<p>Say, for instance, this miniscript:</p>
<p><code>and_v(v:pk(key),or_b(l:after(100),al:after(200)))</code>, which produces:</p>
<pre><code>&lt;key&gt; OP_CHECKSIGVERIFY OP_IF
  0
OP_ELSE
  &lt;64&gt; OP_CHECKLOCKTIMEVERIFY
OP_ENDIF
OP_TOALTSTACK OP_IF
  0
OP_ELSE
  &lt;c800&gt; OP_CHECKLOCKTIMEVERIFY
OP_ENDIF
OP_FROMALTSTACK OP_BOOLOR
</code></pre>
<p>These are some witnesses that would solve the script above:</p>
<pre class="lang-javascript prettyprint-override"><code>      { script: 'OP_0 OP_0 &lt;sig(key)&gt;', nLockTime: 200 },
      { script: 'OP_1 OP_0 &lt;sig(key)&gt;', nLockTime: 100 },
      { script: 'OP_0 OP_1 &lt;sig(key)&gt;', nLockTime: 200 }
</code></pre>
<p>However, the &quot;<a href="https://bitcoin.sipa.be/miniscript/" rel="nofollow noreferrer">Non-malleable satisfaction algorithm</a>&quot; would mark solution <code>OP_0 OP_0 &lt;sig(key)&gt;</code> as <code>DONTUSE</code> (if I'm not mistaken; see more below) and, thus, this solution should not be used.</p>
<p>This is because <code>OP_0 OP_0 &lt;sig(key)&gt;</code> is produced using a branch where a non-canonical satisfaction for <code>or_b</code> is used and the algorithm says:</p>
<blockquote>
<p>The non-canonical options for and_b, or_b, and thresh are always overcomplete (reason 3), so instead use <code>DONTUSE</code> <strong>there</strong></p>
</blockquote>
<p>BTW, I am making the assumption that <strong>there</strong> in the quote above means that the <code>DONTUSE</code> marker must set only on that particular non-canonical sat of <code>or_b</code>: <code>[sat(Z) sat(X)]</code> (and not to the rest of canonical siblings: <code>dsat(Z) sat(X); sat(Z) dsat(X);</code>). I'm not sure about this interpretation.</p>
<p>That said, could you explain to me what would be the problem if <code>OP_0 OP_0 &lt;sig(key)&gt;</code> was used instead of <code>OP_0 OP_1 &lt;sig(key)&gt;</code>?</p>
<p>What advantage would it give attackers? Both are interchangeable.</p>
<p>Or does perhaps <strong>there</strong> mean all <code>or_b</code> sats should be marked as <code>DONTUSE</code>?</p>

<transaction-malleability><miniscript>
When is a Miniscript solution malleable?
landabaso
# When is a Miniscript solution malleable?

(Asked by: username_0 on 2022-12-07)

I'm having some trouble understanding malleability in miniscript. Specifically I cannot get why some solutions can be used instead of other.

I think using an example may help.

Say, for instance, this miniscript:

`and_v(v:pk(key),or_b(l:after(100),al:after(200)))`, which produces:

```
<key> OP_CHECKSIGVERIFY OP_IF
  0
OP_ELSE
  <64> OP_CHECKLOCKTIMEVERIFY
OP_ENDIF
OP_TOALTSTACK OP_IF
  0
OP_ELSE
  <c800> OP_CHECKLOCKTIMEVERIFY
OP_ENDIF
OP_FROMALTSTACK OP_BOOLOR

```

These are some witnesses that would solve the script above:

```javascript
      { script: 'OP_0 OP_0 <sig(key)>', nLockTime: 200 },
      { script: 'OP_1 OP_0 <sig(key)>', nLockTime: 100 },
      { script: 'OP_0 OP_1 <sig(key)>', nLockTime: 200 }

```

However, the "[Non-malleable satisfaction algorithm](https://bitcoin.sipa.be/miniscript/)" would mark solution `OP_0 OP_0 <sig(key)>` as `DONTUSE` (if I'm not mistaken; see more below) and, thus, this solution should not be used.

This is because `OP_0 OP_0 <sig(key)>` is produced using a branch where a non-canonical satisfaction for `or_b` is used and the algorithm says:

> The non-canonical options for and\_b, or\_b, and thresh are always overcomplete (reason 3), so instead use `DONTUSE` **there**

BTW, I am making the assumption that **there** in the quote above means that the `DONTUSE` marker must set only on that particular non-canonical sat of `or_b`: `[sat(Z) sat(X)]` (and not to the rest of canonical siblings: `dsat(Z) sat(X); sat(Z) dsat(X);`). I'm not sure about this interpretation.

That said, could you explain to me what would be the problem if `OP_0 OP_0 <sig(key)>` was used instead of `OP_0 OP_1 <sig(key)>`?

What advantage would it give attackers? Both are interchangeable.

Or does perhaps **there** mean all `or_b` sats should be marked as `DONTUSE`?

**Tags:** transaction-malleability, miniscript


---

## 1 answers

### Answer by username_1 on 2022-12-07. Score: 6 | Accepted answer

## Malleability in the context of Miniscript

Malleability is the possibility for a third party to turn a valid satisfaction into another valid satisfaction. That is, to change the witness in the input of a transaction without making the transaction invalid.

There are various shortcomings to malleable witnesses. Witnesses add to the size of the transaction, so if a witness can be malleated such as to inflate the size of a transaction it could hinder its confirmation by reducing its feerate. Note this may "just" be a simple nuisance for regular usage of onchain transactions, but this could have more serious consequences for contracts that rely on the timely confirmation of a transaction.  
In addition, using malleable satisfactions can have negative external effects on the network modified witness can affect [BIP152](https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki) block propagation (which is based on the `wtxid` for Segwit transactions).

Malleability is discussed in more details [here](https://bitcoin.sipa.be/miniscript/).

## Malleability static analysis in Miniscript

Malleability appears whenever two valid satisfaction for a fragment are available to a third party. Note that a fragment's satisfaction may contain a dissatisfaction of a sub-fragment.

There are 3 ways that malleability may be introduced:

1. **Two valid solutions are directly available to the third party.** For instance let's say the third party knows the preimage to SHA256 hashes `H1` and `H2` and a script like `and_v(v:or_i(sha256(H1),sha256(H2)),pk(A))` is used.
2. **A single valid solution is directly available to the third party, but a participant in the Script uses another one.** For instance let's say the third party knows the preimage to SHA256 hash `H1` but not to SHA256 hash `H2` and a script like `and_v(v:or_i(sha256(H1),sha256(H2)),pk(A))` is used. If the participant satisfies this script by providing the preimage for `H2`, the third-party can replace the satisfaction by one providing the preimage for `H1`.
3. **The participant provides a witness containing a satisfaction for a certain sub-fragment that can be turned into a dissatisfaction.** For instance let's say the third party knows nothing, but `or_b(pk(A),a:pk(B))` is used and a participant spends by providing both a signature for keys A and B. A third party can turn the signature for either A or B to the empty vector without invalidating the witness.

In order to make sure malleability may not be inadvertently introduced when spending from a Miniscript, new properties are introduced in the type system based on a set of general assumptions about what material may be available to a third party.  
It is assumed:

* they don't have access to *any* private key in the script;
* they don't have access to more hash preimages than those revealed in the initial witness;
* they only get to see a single witness produced by participants (otherwise they can mix-and-match);
* no public keys are repeated in the script (otherwise a signature for a fragment may be "replayed" for satisfying another fragment).

The properties are:

* whether satisfying this fragment requires a signature (that is, the satisfaction is not available to a third party);
* whether dissatisfying this fragment requires a signature (same but for dissatisfaction);
* whether a single dissatisfaction that does not require a signature exists, and others, if there is any, require a signature (that is, the fragment may be safely dissatisfied).

## Non-malleable satisfaction algorithm and your example

Malleability is checked at creation time, and a Miniscript that does not contain at least one non-malleable satisfaction per spending path will be marked as unsafe (/insane). Note this does not rule out the existence of malleable satisfactions in addition to non-malleable ones. The satisfier needs to take care to only use satisfactions that are non malleable.

Your interpretation of the algorithm is correct. The non-malleable satisfier will refuse to use the satisfaction for `or_b` that satisfies both branches, even if it has the required material. However it will use any of the two non-malleable satisfactions available.

> That said, could you explain to me what would be the problem if OP\_0 OP\_0 <sig(key)> was used instead of OP\_0 OP\_1 <sig(key)>?

It would allow a third party to change a valid witness into another one, see the section above for rationale.

> Or does perhaps there mean all or\_b sats should be marked as DONTUSE?

No, otherwise there would be no point in having an `or_b` fragment. :) Only all non-canonical satisfactions of `or_b` need to be marked as `DONTUSE`.

## Related notes

Also note that malleability analysis assumes common standardness rules, such as `MINIMALIF`. So a miner could still malleate some witnesses even if they are treated as non-malleable by Miniscript.

> **Comments:**
> **username_0**: Thanks username_1. I kind of follow the general reasoning but then fail to understand how it applies to the particular example I provided. I guess I'm still not fully understanding it. What **exactly** could do an attacker if he saw `OP_0 OP_0 <sig(key)>` in the mempool (I guess this is the idea) that could not do if he saw `OP_0 OP_1 <sig(key)>`? The attacker can convert one into the other. Why is one then considered malleable and not the other? Also the attacker could convert both solutions to a dissatisfaction by replacing them with OP_1 OP_1 <sig> for example.  
> **username_1**: First note that your Miniscript here is malleable in any case, so it's not a surprise it may be malleated in various ways. Both the satisfactions in your comment are malleable. What an attacker can do if you use that is add more roundtrips to compact blocks or transaction relay on the network. Converting a top-level satisfaction to a dissatisfaction by definition makes the transaction invalid, so it isn't a concern. :)  
> **username_0**: Makes sense! My feeling was solutions were malleable in various ways. I could not get why `OP_0 OP_1 <sig(key)>` was not malleable. I was applying the "Non-malleable satisfaction algorithm" assuming the miniscript was sane. I had put the miniscript into the tool at: https://bitcoin.sipa.be/miniscript/, which provided a valid Bitcoin script and I assumed that this meant it was sane.  

---

