OP_PLENTY

OP_PLENTY.py

"""
OP_PLENTY — encode arbitrary byte values as the choice of Tapscript opcode.

CORE CODEC
==========

Each payload byte is split into two nibbles. Each nibble becomes one opcode
whose numeric value is congruent to that nibble modulo 22:

    nibble = opcode % 22

Nibble decoding is therefore stateless. Encoding requires a small state
machine because most nibbles have two representatives:

    low representative   grows or holds the scratch stack
    high representative  shrinks the scratch stack

The encoder chooses between them to keep the logical scratch depth inside
{5, 6, 7}. Both choices decode to the same nibble, so the decoder does not
need to reproduce or understand the depth walk.

The core codec does not require any particular marker or length format.
Framing is a separate, optional layer.


BASIC UNFRAMED FORM
===================

The original form begins with seven stack items:

    51 00 00 00 00 00 00
    OP_1 followed by six OP_0 elements

The OP_1 is a truthy bottom anchor. After the encoded payload, a three-opcode
footer collapses the scratch stack back to that anchor:

    exit depth 5: 6d 6d 61   OP_2DROP OP_2DROP OP_NOP
    exit depth 6: 6d 6d 75   OP_2DROP OP_2DROP OP_DROP
    exit depth 7: 6d 6d 6d   OP_2DROP OP_2DROP OP_2DROP

Because OP_2DROP (0x6d) is absent from the encoding alphabet, it can also act
as an unambiguous body terminator when the decoder already knows where the
encoded script begins.

This unframed form is sufficient when the caller supplies the script boundary
or raw-transaction offset. No length header or magic marker is inherent to the
modulo-22 encoding.


OPTIONAL SELF-FRAMING (V2)
==========================

For txid-only recovery, an optional v2 framing layer can be added:

    seven OP_5 opcodes
    eight encoded length nibbles
    encoded payload
    footer

The seven OP_5 opcodes are both the initial scratch stack and a searchable
magic sequence:

    55 55 55 55 55 55 55

The length is a four-byte big-endian integer containing the number of payload
hex characters, which is twice the payload's byte length:

    encoded_length = 2 * len(payload)

Those eight length nibbles are encoded through exactly the same modulo-22
state machine as the payload. They are not a data push and are not part of
the core alphabet design.

A v2 decoder can therefore:

    1. Search the raw transaction for seven OP_5 bytes.
    2. Fold the next eight opcodes modulo 22 to recover the length.
    3. Decode exactly that many following opcode-nibbles.
    4. Ignore the footer, authorization tail, and remaining transaction bytes.

V2 is optional. It makes the encoding self-locating and length-delimited, but
it is not needed when the script location and payload boundary are already
known.


WORKED CORE EXAMPLE: b"Hi"
===========================

    0x48 -> nibbles (4, 8)
    0x69 -> nibbles (6, 9)

Beginning at depth 7:

    nibble 4, depth 7:
        OP_NUMNOTEQUAL = 0x9e
        158 % 22 = 4
        depth 7 -> 6

    nibble 8, depth 6:
        OP_16 = 0x60
        96 % 22 = 8
        depth 6 -> 7

    nibble 6, depth 7:
        OP_GREATERTHAN = 0xa0
        160 % 22 = 6
        depth 7 -> 6

    nibble 9, depth 6:
        OP_NOP = 0x61
        97 % 22 = 9
        depth remains 6

The core payload body is therefore:

    9e 60 a0 61

Nibble 9 is special: its low representative is OP_NOP, a depth-neutral hold,
rather than a grower. Its high representative is OP_NIP, which shrinks.


THE SAME EXAMPLE WITH OPTIONAL V2 FRAMING
=========================================

The payload contains two bytes, or four hex characters, so its length header
is:

    00000004

The encoded length opcodes are:

    9a 58 9a 58 9a 58 9a 5c

The complete framed data program is:

    seed:
        55 55 55 55 55 55 55

    encoded length:
        9a 58 9a 58 9a 58 9a 5c

    encoded payload:
        9e 60 a0 61

    depth-6 footer:
        6d 6d 75

Combined:

    555555555555559a589a589a589a5c9e60a0616d6d75

Folding the eight length opcodes modulo 22 yields 00000004. Folding the next
four opcodes yields 4869, recovering b"Hi".


AUTHORIZATION TAIL
==================

A complete signed Tapleaf may append:

    OP_DROP <32-byte x-only public key> OP_CHECKSIG

The signature begins below the seven scratch items on the witness stack. The
unframed data program leaves:

    [signature, 1]

The v2 data program leaves:

    [signature, 5]

OP_DROP removes the truthy anchor, and OP_CHECKSIG leaves the final clean,
truthy result.


ALPHABET AND STEERING
=====================

The alphabet contains 28 unique opcodes:

    11 growing representatives
     1 depth-neutral hold
    12 shrinking representatives
     4 depth-neutral unary representatives

The four unary opcodes represent nibbles b through e.

Nibble 9 uses:

    OP_NOP   as its hold representative
    OP_NIP   as its shrinking representative

Nibble a uses OP_OVER only at depth 5. At depths 6 and 7 it uses OP_MAX,
shrinking earlier than the other paired classes and keeping the walk centered.


WHY MODULO 22
=============

Every selected representative must:

    1. Reduce to its represented nibble.
    2. Have the required grow, hold, shrink, or neutral stack behavior.
    3. Avoid disabled, data-dependent-failure, and OP_SUCCESS opcode slots.

Among the safe opcode/action candidates searched for this construction, 22
was the smallest modulus found that supplied all sixteen nibble classes with
the required steering behavior.

Under ordinary BIP342 consensus, OP_SUCCESSx makes a Tapscript succeed
unconditionally. Core standard policy discourages OP_SUCCESSx, and BIP110
makes that rejection mandatory, so the encoding alphabet avoids those slots.


VALUE SAFETY
============

OP_ADD, the shrinking representative for nibble f, is the only selected
opcode that can increase a numeric magnitude. It executes only at depth 7.

Every transition from depth 6 to depth 7 places a small Script number on top
of the stack. Any depth-neutral unary operations performed before OP_ADD do
not increase its magnitude. OP_ADD therefore combines an existing value with
a bounded small value.

For any consensus-sized transaction, the number of possible additions is far
too small to approach the four-byte CScriptNum range.
"""


from enum import IntEnum


class Op(IntEnum):
    OP_1                  = 0x51
    OP_5                  = 0x55
    OP_8                  = 0x58
    OP_9                  = 0x59
    OP_10                 = 0x5a
    OP_11                 = 0x5b
    OP_12                 = 0x5c
    OP_13                 = 0x5d
    OP_14                 = 0x5e
    OP_15                 = 0x5f
    OP_16                 = 0x60
    OP_NOP                = 0x61
    OP_2DROP              = 0x6d
    OP_DROP               = 0x75
    OP_NIP                = 0x77
    OP_OVER               = 0x78
    OP_EQUAL              = 0x87
    OP_NEGATE             = 0x8f
    OP_ABS                = 0x90
    OP_NOT                = 0x91
    OP_0NOTEQUAL          = 0x92
    OP_ADD                = 0x93
    OP_BOOLAND            = 0x9a
    OP_BOOLOR             = 0x9b
    OP_NUMEQUAL           = 0x9c
    OP_NUMNOTEQUAL        = 0x9e
    OP_LESSTHAN           = 0x9f
    OP_GREATERTHAN        = 0xa0
    OP_LESSTHANOREQUAL    = 0xa1
    OP_GREATERTHANOREQUAL = 0xa2
    OP_MAX                = 0xa4


# nibble -> (growing/neutral representative, shrinking representative)
PAIR = {
    0x0: (Op.OP_8,  Op.OP_BOOLAND),
    0x1: (Op.OP_9,  Op.OP_BOOLOR),
    0x2: (Op.OP_10, Op.OP_NUMEQUAL),
    0x3: (Op.OP_11, Op.OP_EQUAL),
    0x4: (Op.OP_12, Op.OP_NUMNOTEQUAL),
    0x5: (Op.OP_13, Op.OP_LESSTHAN),
    0x6: (Op.OP_14, Op.OP_GREATERTHAN),
    0x7: (Op.OP_15, Op.OP_LESSTHANOREQUAL),
    0x8: (Op.OP_16, Op.OP_GREATERTHANOREQUAL),
    0x9: (Op.OP_NOP, Op.OP_NIP),
    0xa: (Op.OP_OVER, Op.OP_MAX),
    0xf: (Op.OP_1, Op.OP_ADD),
}

UNARY = {
    0xb: Op.OP_NEGATE,
    0xc: Op.OP_ABS,
    0xd: Op.OP_NOT,
    0xe: Op.OP_0NOTEQUAL,
}

FOOTER = {
    5: (Op.OP_2DROP, Op.OP_2DROP, Op.OP_NOP),
    6: (Op.OP_2DROP, Op.OP_2DROP, Op.OP_DROP),
    7: (Op.OP_2DROP, Op.OP_2DROP, Op.OP_2DROP),
}

MAGIC = bytes([Op.OP_5]) * 7
LENGTH_NIBBLES = 8


def encode(data: bytes) -> bytes:
    # Store the number of payload hex characters, not bytes. Because one
    # opcode represents one hex character, the decoder can use it directly.
    framed = (2 * len(data)).to_bytes(4, "big") + data

    out = bytearray(MAGIC)
    depth = 7

    for byte in framed:
        for nib in (byte >> 4, byte & 0xf):
            if nib in UNARY:
                op = UNARY[nib]

            elif depth == 7 or (depth == 6 and nib == 0xa):
                op = PAIR[nib][1]
                depth -= 1

            else:
                op = PAIR[nib][0]
                if nib != 0x9:  # OP_NOP is neutral
                    depth += 1

            out.append(op)

    out.extend(FOOTER[depth])
    return bytes(out)


def decode(blob: bytes) -> bytes:
    # blob may be either the bare script or the complete raw transaction.
    start = blob.index(MAGIC) + len(MAGIC)
    encoded = blob[start:]

    # Every encoding opcode satisfies opcode % 22 == represented nibble.
    header = "".join(f"{op % 22:x}" for op in encoded[:LENGTH_NIBBLES])
    hex_length = int(header, 16)

    payload = encoded[LENGTH_NIBBLES:LENGTH_NIBBLES + hex_length]
    payload_hex = "".join(f"{op % 22:x}" for op in payload)

    return bytes.fromhex(payload_hex)


def asm(script: bytes) -> str:
    return " ".join(Op(op).name for op in script)