Basic satisfactions

The following table shows all valid satisfactions and dissatisfactions for every Miniscript, using satisfactions and dissatisfactions of its subexpressions. Multiple possibilities are separated by semicolons. Some options are not actually necessary to produce correct witnesses, and are called non-canonical options. They are listed for completeness, but marked in [grey] below.

The correctness properties in the previous section are based on the availability of satisfactions and dissatisfactions listed above. The requirements include a "d" for every subexpression whose dissatisfaction may be needed in building a satisfaction for the parent expression. The "d" properties themselves rely on the "d" properties of subexpressions. An interesting property is that in a well-typed Miniscript, dissatisfying a non-"d" subexpression always causes the overall script to fail, propagating the failure upwards to a point where it either causes the script to abort, or reach the top level.

A conservative simplification is made here, ignoring the existence of always-true expressions like 1. This makes the typing rules incorrect in the following cases:

• or_b(X,1) and or_b(1,X) are complete when X is dissatisfiable ("d"). In that case, the condition is equivalent to 1 and is always met, and a satisfaction of the form "dsat(X)" exists.
• or_b(1,1) is complete, as it is equivalent to 1 and "" is a valid satisfaction.
• and_b(X,1) and and_b(1,X) are dissatisfiable ("d") when X is.
• andor(1,1,Z) is complete, as it is equivalent to 1 and "" is a valid satisfaction.
• andor(1,Y,0) is complete when Y is; it also has the same type as Y, despite 0 always being a "B". This is also dissatisfiable when Y is.
• The 1s items listed above can be replaced with any other always-true expression.

Malleability

While following the table above to construct satisfactions is sufficient for meeting the completeness and soundness properties, it does not guarantee non-malleability.

Malleability is the ability for a third party (not a participant in the script) to modify an existing satisfaction into another valid satisfaction. Since Segwit, malleating a transaction no longer breaks the validity of unconfirmed descendant transactions. However, unintentional malleability may still have a number of much weaker undesirable effects. If a witness can be stuffed with additional data, the transaction's feerate will go down, potentially to the point where its ability to propagate and get confirmed is impacted. Additionally, malleability can be exploited to add roundtrips to BIP152 block propagation, by trying to get different miners to mine different versions of the same transaction. Finally, malleability may interfere with the usage of hash locks as a mechanism for publishing preimages.

Because of these reasons, Miniscript is actually designed to permit non-malleable signing. As this guarantee is restricted in non-obvious ways, let's first state the assumptions:

• The attacker does not have access to any of the private keys of public keys that participate in the Script. Participants with private keys inherently have the ability to produce different satisfactions by creating multiple signatures. While it is also interesting to study the impact rogue participants can have, we treat it as a distinct problem.
• The attacker only has access to hash preimages that honest users have access to as well. This is a reasonable assumption because hash preimages are revealed once globally, and then available to everyone. On the other hand, making the assumption that attackers may have access to more preimages than honest users makes a large portion of scripts impossible to satisfy in a non-malleable way.
• The attacker gets to see exactly one satisfying witness of any transaction. If he sees multiple, it becomes possible for the attacker to mix and match different satisfactions. This is very hard to reason about.
• We restrict this analysis to scripts where no public key is repeated. If signatures constructed for one part of the script can be bound to other checks in the same script, a variant of the mixing from the previous point becomes available that is equally hard to reason about. Furthermore this situation can be avoided by using separate keys.

Malleable satisfactions or dissatisfactions appear whenever options are available to attackers distinct from the one taken by honest users. This can happen for multiple reasons:

1. Two or more options for a satisfaction or dissatisfaction are listed in the table above which are both available to attackers directly. Regardless of which option is used in the honest solution, the attacker can change the solution to the other one.
2. Two or more options for a satisfaction or dissatisfaction are listed in the table above, only one of which is available to attackers, but the honest solution uses another one. In that case, the attacker can modify the solution to pick the one available to him.
3. The honest users pick a solution that contains a satisfaction which can be turned into a dissatisfaction without invalidating the overall witness. Those are called overcomplete solutions.

Non-malleable satisfaction algorithm

Because we assume attackers never have access to private keys, we can treat any solution that includes a signature as one that is unavailable to attackers. For others, the worst case is that the attacker has access to every solution the honest users have, but no others: for preimages this is an explicit assumption, while timelock availability is determined by the nLockTime and nSequence fields in the transaction. As long as the overall satisfaction includes at least one signature, those values are fixed, and timelock availability is identical for attackers and honest users.

In order to produce non-malleable satisfactions we make use of a function that returns the optimal satisfaction and dissatisfaction for a given expression (if any exist), or a special DONTUSE value, together with an optional HASSIG marker that tracks whether the solution contains at least one signature. To implement the function:

• Invoke the function recursively for all subexpressions, obtaining all their satisfactions/dissatisfactions.
• Iterate over all the valid satisfactions/dissatisfactions in the table above (including the non-canonical ones), taking into account:
  • The dissatisfactions for sha256, ripemd160, hash256, and hash160 are always malleable (reason 1), so instead use DONTUSE there.
  • The non-canonical options for and_b, or_b, and thresh are always overcomplete (reason 3), so instead use DONTUSE there as well (with HASSIG flag if the original non-canonical solution had one).
  • The satisfactions for pk_k, pk_h, and multi can be marked HASSIG.
  • When constructing solutions by combining results for subexpressions, the result is DONTUSE if any of the constituent results is DONTUSE. Furthermore, the result gets the HASSIG tag if any of the constituents do.
• If among all valid solutions (including DONTUSE ones) more than one does not have the HASSIG marker, return DONTUSE, as this is malleable because of reason 1.
• If instead exactly one does not have the HASSIG marker, return that solution because of reason 2.
• If all valid solutions have the HASSIG marker, but all of them are DONTUSE, return DONTUSE-HASSIG. The HASSIG marker is important because while this represents a choice between multiple options that would cause malleability if used, they are not available to the attacker, and we may be able to avoid them entirely still.
• Otherwise, all not-DONTUSE options are valid, so return the smallest one (in terms of witness size).

The above can be used to show that no non-canonical solutions listed in the satisfaction table can occur inside non-malleable satisfactions.

• Some of the non-canonical options (the or_b, and_b, and thresh ones) are overcomplete, and thus can clearly not appear in non-malleable satisfactions.
• The fact that non-"d" expressions cannot be dissatisfied in valid witnesses rules out the usage of the non-canonical and_v dissatisfaction.
• "d" expressions are defined to be unconditionally dissatisfiable, which implies that for those a non-HASSIG dissatisfaction must exist. Non-HASSIG solutions must be preferred over HASSIG ones (reason 2), and when multiple non-HASSIG ones exist, none can be used (reason 1). This lets us rule out the other non-canonical options in the table:
  • j:X is always "d", its non-HASSIG dissatisfaction "0" always exists, and thus rules out any usage of "dsat(X)".
  • If andor(X,Y,Z) is "d", a non-HASSIG dissatisfaction "dsat(Z) dsat(X)" must exist, and thus rules out any usage of "dsat(Y) sat(X)".
  • If and_b(X,Y) is "d", a non-HASSIG dissatisfaction "dsat(Y) dsat(X)" must exist, and thus rules out any usage of "dsat(Y) sat(X)" and "sat(Y) dsat(X)". Those are also overcomplete.
  • thresh(k,...) is always "d", a non-HASSIG dissatisfaction with just dissatisfactions must exist due to typing rules, and thus rules out usage of the other dissatisfactions. They are also overcomplete.

Guaranteeing non-malleability

Now we have an algorithm that can find the optimal non-malleable satisfaction for any Miniscript, if it exists. But can we statically prove that such a solution always exists? In order to do that, we add additional properties to the type system:

• "s" Signed: satisfying this expression always requires a signature (predicting whether all satisfactions will be HASSIG).
• "f" Forced: dissatisfying this expression always requires a signature (predicting whether all dissatisfactions will be HASSIG).
• "e" Expressive: this requires a unique unconditional dissatisfaction to exist, and forces all conditional dissatisfactions (if any) to require a signature.

The following table lists these additional properties, and the requirements for non-malleability.

Using the malleability type properties it is possible to determine statically whether a script can be nonmalleably satisfied under all circumstances. In many cases it is reasonable to only accept such guaranteed-nonmalleable scripts, as unexpected behavior can occur when using other scripts.

For example, when running the non-malleable satisfaction algorithm above, adding available preimages, or increasing the nLockTime/nSequence values actually may make it fail where it succeeded before. This is because a larger set of met conditions may mean an existing satisfaction goes from nonmalleable to malleable. Restricting things to scripts that are guaranteed to be satisfiable in a non-malleable way avoids this problem.

When analysing Miniscripts for resource limits, restricting yourself to just non-malleable solutions (or even non-malleable scripts) also leads to tighter bounds, as all non-canonical satisfactions and dissatisfactions can be left out of consideration.