evalScript through runSeq
ProvedBitcoinMiniscript.evalScript_eq_runSeqevalScript f o st sc is the stack of runSeq from the initial state when the condition stack ends empty, none otherwise.
import Definitions.Def_BitcoinMiniscript import Definitions.Def_BitcoinScript open BitcoinMiniscript BitcoinToLocal BitcoinHtlc BitcoinScript BitcoinSig BitcoinVerify
theorem BitcoinMiniscript.evalScript_eq_runSeq (f : BitcoinScript.Flags) (o : BitcoinScript.Oracle)
(st : List BitcoinScript.Bytes) (sc : BitcoinScript.Script) :
BitcoinScript.evalScript f o st sc =
match BitcoinMiniscript.runSeq f o (BitcoinScript.State.initial st) sc with
| none => none
| some s' => if s'.vfExec.isEmpty then some s'.stack else none := by sorryRead-back
What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)
Read-back: BitcoinMiniscript.evalScript_eq_runSeq
Statement. For any flags , any oracle (arbitrary functions, see below), any initial stack (a list of byte strings, top first) and any script (any list of instructions, not necessarily one produced from Miniscript):
Here and is the main stack of .
Definitions used in the statement, unfolded
Basic data (from the script-interpreter preamble)
Byte strings, stacks, witnesses. A byte string is a finite list of 8-bit bytes (values –); is the empty byte string and the length of . Stacks, witnesses and outputs are finite lists of byte strings written top element first. For such lists, is the list with placed on top of , is concatenation (in all elements of lie above all elements of , the first element of being the top of the stack), and is the number of elements.
Constants.
. For a byte string: ; ; for a string with at least two bytes, . So it is true exactly when some byte other than the last is nonzero, or the last byte is neither nor ; the empty string, all-zero strings, and strings of zero bytes followed by a final are false.
. , .
(script-number encoding of an integer ). . For , let be the little-endian base-256 digits of with no most-significant zero bytes. If the last (most significant) byte of has bit set, the result is followed by one extra byte, if and if ; otherwise the result is with bit of its last byte set if , and itself if . Examples: , , , , .
Flags . A record of three independent booleans , , ; every combination is allowed.
Oracle . A record of completely arbitrary functions, with no property assumed of any of them (they are not required to be the real hash functions or a real signature check, need not produce outputs of any particular length, and need not be injective or collision resistant):
- : byte strings byte strings;
- , an arbitrary function of a signature and a public key ("none" means the script fails);
- : integers booleans.
(both lists top-first), with result none, some(true) or some(false):
- if : some(true);
- if is nonempty and : some(false);
- if and : compute . If none, the result is none. If some(true): the result is some(false) when , and otherwise . If some(false): the result is some(false) when , and otherwise .
The script interpreter (from the script-interpreter preamble)
Instructions and scripts. An instruction is either for a byte string , or for an opcode byte . A script is a finite list of instructions. Opcode bytes used below: OP_1NEGATE , OP_RESERVED , OP_1…OP_16 …, OP_NOP , OP_IF , OP_NOTIF , OP_ELSE , OP_ENDIF , OP_VERIFY , OP_RETURN , OP_TOALTSTACK , OP_FROMALTSTACK , OP_IFDUP , OP_DUP , OP_SWAP , OP_SIZE , OP_EQUAL , OP_EQUALVERIFY , OP_0NOTEQUAL , OP_BOOLAND , OP_BOOLOR , OP_RIPEMD160 , OP_SHA1 , OP_SHA256 , OP_HASH160 , OP_HASH256 , OP_CODESEPARATOR , OP_CHECKSIG , OP_CHECKSIGVERIFY , OP_CHECKMULTISIG , OP_CHECKMULTISIGVERIFY , OP_NOP1 , OP_CHECKLOCKTIMEVERIFY , OP_CHECKSEQUENCEVERIFY , OP_NOP4…OP_NOP10 … (plus the other standard stack/arithmetic opcodes named below).
is the number of instructions in the script with (pushes and opcodes are not counted).
States. A state is a quadruple : the main stack and the alt stack (lists of byte strings, top first), the condition stack (a list of booleans, innermost first) and the operation counter . . means every entry of is true (so it is true for , and false exactly when contains at least one false). The state is executing when .
Decoding numbers. "Decode with limit " fails if ; otherwise it gives the sign–magnitude little-endian value of : if the last byte has bit set, minus the little-endian value of with that bit cleared, else the little-endian value of ( decodes to ). No minimal-encoding requirement is applied anywhere.
— one instruction; result is a new state or failure.
- : fail if . If executing, put on top of the main stack; otherwise leave the state unchanged. Then fail if .
- : (1) if and , fail; if , increase by one (this happens also in non-executed branches). (2) If is one of the fifteen disabled opcodes (
OP_CAT,OP_SUBSTR,OP_LEFT,OP_RIGHT,OP_INVERT,OP_AND,OP_OR,OP_XOR,OP_2MUL,OP_2DIV,OP_MUL,OP_DIV,OP_MOD,OP_LSHIFT,OP_RSHIFT), fail, executing or not. (3) If executing, or , apply (below, with the flag "executing" passed in); fail if it fails, and otherwise fail if the resulting . (4) Otherwise the state is unchanged apart from , and it fails if .
. "Top" is the first stack element, "second" the next; whenever a required element is missing the result is failure.
OP_1NEGATEorOP_1…OP_16: push , i.e. of .OP_NOP,OP_NOP1,OP_NOP4…OP_NOP10,OP_CODESEPARATOR: no change.OP_CHECKLOCKTIMEVERIFY: if is false, no change. Otherwise decode the top with limit (not removing it); fail if that fails, if the value , or if is false; else no change.OP_CHECKSEQUENCEVERIFY: if is false, no change. Otherwise decode the top with limit (not removing it); fail if that fails or ; if bit of is set, no change; otherwise fail if is false, else no change.OP_IF/OP_NOTIF: if , remove the top and put (negated forOP_NOTIF) in front of ; if not , put false in front of and leave the stack alone.OP_ELSE: fail if is empty, else negate its first entry.OP_ENDIF: fail if is empty, else remove its first entry.OP_VERIFY: remove the top; fail if of it is false.OP_RETURN: fail.OP_TOALTSTACK: move the top of the main stack onto the alt stack.OP_FROMALTSTACK: move the top of the alt stack onto the main stack.OP_2DROP,OP_2DUP,OP_3DUP,OP_2OVER,OP_2ROT,OP_2SWAP,OP_DROP,OP_NIP,OP_OVER,OP_ROT,OP_TUCK: the standard rearrangements of the top two to six elements.OP_DUP: duplicate the top.OP_SWAP: exchange top and second.OP_IFDUP: duplicate the top if of it is true, else no change.OP_DEPTH: push .OP_PICK/OP_ROLL: remove the top, decode it (limit ) as , require a nonempty remainder with its length, and copy (PICK) or move (ROLL) its element of index (0 = top) to the top.OP_SIZE: push for the top , which stays.OP_EQUAL/OP_EQUALVERIFY: remove the top and second ;OP_EQUALpushes ;OP_EQUALVERIFYfails unless .OP_1ADD,OP_1SUB,OP_NEGATE,OP_ABS,OP_NOT,OP_0NOTEQUAL: remove the top, decode it with limit as (fail if longer), push of , , , , ( if else ), ( if else ) respectively.OP_ADD,OP_SUB,OP_BOOLAND,OP_BOOLOR,OP_NUMEQUAL,OP_NUMEQUALVERIFY,OP_NUMNOTEQUAL,OP_LESSTHAN,OP_GREATERTHAN,OP_LESSTHANOREQUAL,OP_GREATERTHANOREQUAL,OP_MIN,OP_MAX: remove the top and second , decode from and from with limit (fail if either is longer), and push of the result: , , ( if and else ), ( if or else ), and for , then , ;OP_NUMEQUALVERIFYpushes nothing and fails unless .OP_WITHIN: remove three elements (top), , , decode each with limit , push of the decoded values.OP_RIPEMD160,OP_SHA1,OP_SHA256,OP_HASH160,OP_HASH256: replace the top by , , , , respectively.OP_CHECKSIG/OP_CHECKSIGVERIFY: with the top and the second, let ; fail if is none;OP_CHECKSIGreplaces both by ;OP_CHECKSIGVERIFYremoves both and fails unless is true.OP_CHECKMULTISIG/OP_CHECKMULTISIGVERIFY: remove the top and decode it (limit ) as ; fail if or ; let and fail if ; the next elements (top-first) are the keys (fail if fewer); the following element is decoded (limit ) as , failing if absent, if or ; the next elements (top-first) are the signatures (fail if fewer); let and fail if none; one more element, the dummy, must be present and is removed; fail if is true and the dummy is not ; the counter becomes ;OP_CHECKMULTISIGpushes onto what remains, the VERIFY form pushes nothing and fails unless is true.- Every other byte (including
OP_RESERVED, , and any byte used as an opcode): fail.
: is if its condition stack is empty and failure otherwise; fails if fails and is otherwise.
: if succeeds with final state , the result is "some" of the main stack of ; otherwise it is failure (none). Nothing about the alt stack, the operation counter, or the truth of the top element is checked; the initial stack is not checked against any size limit.
(defined in the Miniscript file): exactly like but without the final check: (whatever its condition stack), and fails if fails and is otherwise.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.