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

bool	Valid () const

int32_t	NetDiff () const

int32_t	Exec () const

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

Private Attributes
bool	valid
	Whether a canonical satisfaction/dissatisfaction is possible at all. More...

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

int32_t	exec
	How 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 439 of file miniscript.h.

Constructor & Destructor Documentation

◆ SatInfo() [1/2]

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

inlineconstexprnoexcept

Empty script set.

Definition at line 450 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 453 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 492 of file miniscript.h.

◆ Empty()

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

inlinestaticconstexprnoexcept

The empty script.

Definition at line 482 of file miniscript.h.

◆ Exec()

int32_t miniscript::internal::SatInfo::Exec ( ) const

inline

Definition at line 458 of file miniscript.h.

◆ Hash()

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

inlinestaticconstexprnoexcept

A script consisting of a single hash opcode.

Definition at line 486 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 490 of file miniscript.h.

◆ NetDiff()

int32_t miniscript::internal::SatInfo::NetDiff ( ) const

inline

Definition at line 457 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 488 of file miniscript.h.

◆ OP_0NOTEQUAL()

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

inlinestaticconstexprnoexcept

Definition at line 501 of file miniscript.h.

◆ OP_CHECKSIG()

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

inlinestaticconstexprnoexcept

Definition at line 500 of file miniscript.h.

◆ OP_DUP()

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

inlinestaticconstexprnoexcept

Definition at line 495 of file miniscript.h.

◆ OP_EQUAL()

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

inlinestaticconstexprnoexcept

Definition at line 498 of file miniscript.h.

◆ OP_EQUALVERIFY()

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

inlinestaticconstexprnoexcept

Definition at line 497 of file miniscript.h.

◆ OP_IFDUP()

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

inlinestaticconstexprnoexcept

Definition at line 496 of file miniscript.h.

◆ OP_SIZE()

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

inlinestaticconstexprnoexcept

Definition at line 499 of file miniscript.h.

◆ OP_VERIFY()

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

inlinestaticconstexprnoexcept

Definition at line 502 of file miniscript.h.

◆ Push()

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

inlinestaticconstexprnoexcept

A script consisting of a single push opcode.

Definition at line 484 of file miniscript.h.

◆ Valid()

bool miniscript::internal::SatInfo::Valid ( ) const

inline

Definition at line 456 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 471 of file miniscript.h.

◆ operator|

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

friend

Script set union.

Definition at line 461 of file miniscript.h.

Member Data Documentation

◆ exec

int32_t miniscript::internal::SatInfo::exec

private

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

Definition at line 446 of file miniscript.h.

◆ netdiff

int32_t miniscript::internal::SatInfo::netdiff

private

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

Definition at line 444 of file miniscript.h.

◆ valid

bool miniscript::internal::SatInfo::valid

private

Whether a canonical satisfaction/dissatisfaction is possible at all.

Definition at line 442 of file miniscript.h.

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

src/script/miniscript.h

Public Member Functions

Static Public Member Functions

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ SatInfo() [1/2]

◆ SatInfo() [2/2]

Member Function Documentation

◆ BinaryOp()

◆ Empty()

◆ Exec()

◆ Hash()

◆ If()

◆ NetDiff()

◆ Nop()

◆ OP_0NOTEQUAL()

◆ OP_CHECKSIG()

◆ OP_DUP()

◆ OP_EQUAL()

◆ OP_EQUALVERIFY()

◆ OP_IFDUP()

◆ OP_SIZE()

◆ OP_VERIFY()

◆ Push()

◆ Valid()

Friends And Related Function Documentation

◆ operator+

◆ operator|

Member Data Documentation

◆ exec

◆ netdiff

◆ valid