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

#include <miniscript.h>

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

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

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

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

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

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

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

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

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

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

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

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

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

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 422 of file miniscript.h.

Constructor & Destructor Documentation

◆ SatInfo() [1/2]

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

inlineconstexprnoexcept

Empty script set.

Definition at line 431 of file miniscript.h.

◆ SatInfo() [2/2]

constexpr 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 434 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 469 of file miniscript.h.

◆ Empty()

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

inlinestaticconstexprnoexcept

The empty script.

Definition at line 459 of file miniscript.h.

◆ Hash()

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

inlinestaticconstexprnoexcept

A script consisting of a single hash opcode.

Definition at line 463 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 467 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 465 of file miniscript.h.

◆ OP_0NOTEQUAL()

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

inlinestaticconstexprnoexcept

Definition at line 478 of file miniscript.h.

◆ OP_CHECKSIG()

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

inlinestaticconstexprnoexcept

Definition at line 477 of file miniscript.h.

◆ OP_DUP()

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

inlinestaticconstexprnoexcept

Definition at line 472 of file miniscript.h.

◆ OP_EQUAL()

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

inlinestaticconstexprnoexcept

Definition at line 475 of file miniscript.h.

◆ OP_EQUALVERIFY()

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

inlinestaticconstexprnoexcept

Definition at line 474 of file miniscript.h.

◆ OP_IFDUP()

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

inlinestaticconstexprnoexcept

Definition at line 473 of file miniscript.h.

◆ OP_SIZE()

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

inlinestaticconstexprnoexcept

Definition at line 476 of file miniscript.h.

◆ OP_VERIFY()

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

inlinestaticconstexprnoexcept

Definition at line 479 of file miniscript.h.

◆ Push()

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

inlinestaticconstexprnoexcept

A script consisting of a single push opcode.

Definition at line 461 of file miniscript.h.

Friends And Related Function Documentation

◆ operator+

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

friend

Script set concatenation.

Definition at line 448 of file miniscript.h.

◆ operator|

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

friend

Script set union.

Definition at line 438 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 428 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 426 of file miniscript.h.

◆ valid

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

Whether a canonical satisfaction/dissatisfaction is possible at all.

Definition at line 424 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 Function Documentation

◆ operator+

◆ operator|

Member Data Documentation

◆ exec

◆ netdiff

◆ valid