A data structure to help the calculation of stack size limits. More...

#include <miniscript.h>

Public Member Functions
constexpr	SatInfo () noexcept
	Empty script set.

constexpr	SatInfo (int32_t in_netdiff, int32_t in_exec) noexcept
	Script set with a single script in it, with specified netdiff and exec.

Static Public Member Functions
static constexpr SatInfo	Empty () noexcept
	The empty script.

static constexpr SatInfo	Push () noexcept
	A script consisting of a single push opcode.

static constexpr SatInfo	Hash () noexcept
	A script consisting of a single hash opcode.

static constexpr SatInfo	Nop () noexcept
	A script consisting of just a repurposed nop (OP_CHECKLOCKTIMEVERIFY, OP_CHECKSEQUENCEVERIFY).

static constexpr SatInfo	If () noexcept
	A script consisting of just OP_IF or OP_NOTIF.

static constexpr SatInfo	BinaryOp () noexcept
	A script consisting of just a binary operator (OP_BOOLAND, OP_BOOLOR, OP_ADD).

static constexpr SatInfo	OP_DUP () noexcept

static constexpr SatInfo	OP_IFDUP (bool nonzero) noexcept

static constexpr SatInfo	OP_EQUALVERIFY () noexcept

static constexpr SatInfo	OP_EQUAL () noexcept

static constexpr SatInfo	OP_SIZE () noexcept

static constexpr SatInfo	OP_CHECKSIG () noexcept

static constexpr SatInfo	OP_0NOTEQUAL () noexcept

static constexpr SatInfo	OP_VERIFY () noexcept

Public Attributes
const bool	valid
	Whether a canonical satisfaction/dissatisfaction is possible at all.

const int32_t	netdiff
	How much higher the stack size at start of execution can be compared to at the end.

const int32_t	exec
	Mow much higher the stack size can be during execution compared to at the end.

Friends
constexpr friend SatInfo	operator\| (const SatInfo &a, const SatInfo &b) noexcept
	Script set union.

constexpr friend SatInfo	operator+ (const SatInfo &a, const SatInfo &b) noexcept
	Script set concatenation.

Detailed Description

A data structure to help the calculation of stack size limits.

Conceptually, every SatInfo object corresponds to a (possibly empty) set of script execution traces (sequences of opcodes).

SatInfo{} corresponds to the empty set.
SatInfo{n, e} corresponds to a single trace whose net effect is removing n elements from the stack (may be negative for a net increase), and reaches a maximum of e stack elements more than it ends with.
operator| is the union operation: (a | b) corresponds to the union of the traces in a and the traces in b.
operator+ is the concatenation operator: (a + b) corresponds to the set of traces formed by concatenating any trace in a with any trace in b.

Its fields are:

valid is true if the set is non-empty.
netdiff (if valid) is the largest difference between stack size at the beginning and at the end of the script across all traces in the set.
exec (if valid) is the largest difference between stack size anywhere during execution and at the end of the script, across all traces in the set (note that this is not necessarily due to the same trace as the one that resulted in the value for netdiff).

This allows us to build up stack size limits for any script efficiently, by starting from the individual opcodes miniscripts correspond to, using concatenation to construct scripts, and using the union operation to choose between execution branches. Since any top-level script satisfaction ends with a single stack element, we know that for a full script:

netdiff+1 is the maximal initial stack size (relevant for P2WSH stack limits).
exec+1 is the maximal stack size reached during execution (relevant for P2TR stack limits).

Mathematically, SatInfo forms a semiring:

operator| is the semiring addition operator, with identity SatInfo{}, and which is commutative and associative.
operator+ is the semiring multiplication operator, with identity SatInfo{0}, and which is associative.
operator+ is distributive over operator|, so (a + (b | c)) = (a+b | a+c). This means we do not need to actually materialize all possible full execution traces over the whole script (which may be exponential in the length of the script); instead we can use the union operation at the individual subexpression level, and concatenate the result with subexpressions before and after it.
It is not a commutative semiring, because a+b can differ from b+a. For example, "OP_1 OP_DROP" has exec=1, while "OP_DROP OP_1" has exec=0.

Definition at line 417 of file miniscript.h.

Constructor & Destructor Documentation

◆ SatInfo() [1/2]

miniscript::internal::SatInfo::SatInfo ( )

inlineconstexprnoexcept

Empty script set.

Definition at line 426 of file miniscript.h.

◆ SatInfo() [2/2]

miniscript::internal::SatInfo::SatInfo	(	int32_t	in_netdiff,
		int32_t	in_exec )

inlineconstexprnoexcept

Script set with a single script in it, with specified netdiff and exec.

Definition at line 429 of file miniscript.h.

Member Function Documentation

◆ BinaryOp()

static constexpr SatInfo miniscript::internal::SatInfo::BinaryOp ( )

inlinestaticconstexprnoexcept

A script consisting of just a binary operator (OP_BOOLAND, OP_BOOLOR, OP_ADD).

Definition at line 464 of file miniscript.h.

◆ Empty()

static constexpr SatInfo miniscript::internal::SatInfo::Empty ( )

inlinestaticconstexprnoexcept

The empty script.

Definition at line 454 of file miniscript.h.

◆ Hash()

static constexpr SatInfo miniscript::internal::SatInfo::Hash ( )

inlinestaticconstexprnoexcept

A script consisting of a single hash opcode.

Definition at line 458 of file miniscript.h.

◆ If()

static constexpr SatInfo miniscript::internal::SatInfo::If ( )

inlinestaticconstexprnoexcept

A script consisting of just OP_IF or OP_NOTIF.

Note that OP_ELSE and OP_ENDIF have no stack effect.

Definition at line 462 of file miniscript.h.

◆ Nop()

static constexpr SatInfo miniscript::internal::SatInfo::Nop ( )

inlinestaticconstexprnoexcept

A script consisting of just a repurposed nop (OP_CHECKLOCKTIMEVERIFY, OP_CHECKSEQUENCEVERIFY).

Definition at line 460 of file miniscript.h.

◆ OP_0NOTEQUAL()

static constexpr SatInfo miniscript::internal::SatInfo::OP_0NOTEQUAL ( )

inlinestaticconstexprnoexcept

Definition at line 473 of file miniscript.h.

◆ OP_CHECKSIG()

static constexpr SatInfo miniscript::internal::SatInfo::OP_CHECKSIG ( )

inlinestaticconstexprnoexcept

Definition at line 472 of file miniscript.h.

◆ OP_DUP()

static constexpr SatInfo miniscript::internal::SatInfo::OP_DUP ( )

inlinestaticconstexprnoexcept

Definition at line 467 of file miniscript.h.

◆ OP_EQUAL()

static constexpr SatInfo miniscript::internal::SatInfo::OP_EQUAL ( )

inlinestaticconstexprnoexcept

Definition at line 470 of file miniscript.h.

◆ OP_EQUALVERIFY()

static constexpr SatInfo miniscript::internal::SatInfo::OP_EQUALVERIFY ( )

inlinestaticconstexprnoexcept

Definition at line 469 of file miniscript.h.

◆ OP_IFDUP()

static constexpr SatInfo miniscript::internal::SatInfo::OP_IFDUP ( bool nonzero )

inlinestaticconstexprnoexcept

Definition at line 468 of file miniscript.h.

◆ OP_SIZE()

static constexpr SatInfo miniscript::internal::SatInfo::OP_SIZE ( )

inlinestaticconstexprnoexcept

Definition at line 471 of file miniscript.h.

◆ OP_VERIFY()

static constexpr SatInfo miniscript::internal::SatInfo::OP_VERIFY ( )

inlinestaticconstexprnoexcept

Definition at line 474 of file miniscript.h.

◆ Push()

static constexpr SatInfo miniscript::internal::SatInfo::Push ( )

inlinestaticconstexprnoexcept

A script consisting of a single push opcode.

Definition at line 456 of file miniscript.h.

Friends And Related Symbol Documentation

◆ operator+

friend SatInfo operator+	(	const SatInfo &	a,
		const SatInfo &	b )

friend

Script set concatenation.

Definition at line 443 of file miniscript.h.

◆ operator|

friend SatInfo operator\|	(	const SatInfo &	a,
		const SatInfo &	b )

friend

Script set union.

Definition at line 433 of file miniscript.h.

Member Data Documentation

◆ exec

const int32_t miniscript::internal::SatInfo::exec

Mow much higher the stack size can be during execution compared to at the end.

Definition at line 423 of file miniscript.h.

◆ netdiff

const int32_t miniscript::internal::SatInfo::netdiff

How much higher the stack size at start of execution can be compared to at the end.

Definition at line 421 of file miniscript.h.

◆ valid

const bool miniscript::internal::SatInfo::valid

Whether a canonical satisfaction/dissatisfaction is possible at all.

Definition at line 419 of file miniscript.h.

The documentation for this struct was generated from the following file:

src/script/miniscript.h

Public Member Functions

Static Public Member Functions

Public Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ SatInfo() [1/2]

◆ SatInfo() [2/2]

Member Function Documentation

◆ BinaryOp()

◆ Empty()

◆ Hash()

◆ If()

◆ Nop()

◆ OP_0NOTEQUAL()

◆ OP_CHECKSIG()

◆ OP_DUP()

◆ OP_EQUAL()

◆ OP_EQUALVERIFY()

◆ OP_IFDUP()

◆ OP_SIZE()

◆ OP_VERIFY()

◆ Push()

Friends And Related Symbol Documentation

◆ operator+

◆ operator|

Member Data Documentation

◆ exec

◆ netdiff

◆ valid