Merkle Tree Ladder Mode (MTL) Signatures

           SPHINCS+-MTL              Security     NIST
           Instantiation            Parameter n   Level
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-128s-simple |      16      |   1   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-128s-robust |      16      |   1   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-128f-simple |      16      |   1   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-128f-robust |      16      |   1   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-192s-simple |      24      |   3   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-192s-robust |      24      |   3   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-192f-simple |      24      |   3   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-192f-robust |      24      |   3   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-256s-simple |      32      |   5   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-256s-robust |      32      |   5   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-256f-simple |      32      |   5   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-256f-robust |      32      |   5   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-128s-simple  |      16      |   1   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-128s-robust  |      16      |   1   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-128f-simple  |      16      |   1   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-128f-robust  |      16      |   1   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-192s-simple  |      24      |   3   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-192s-robust  |      24      |   3   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-192f-simple  |      24      |   3   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-192f-robust  |      24      |   3   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-256s-simple  |      32      |   5   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-256s-robust  |      32      |   5   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-256f-simple  |      32      |   5   |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-256f-robust  |      32      |   5   |
+--------------------------------+----------------------+

-------------------------- mtl.py --------------------------------
"""
This is a collection of the algorithms defined in the Merkle Tree
  Ladder Mode (MTL) Signatures specification. Helping functions
  (like rand, lsb, msb, bit_width) are also provided to ensure
  the algorithms work.
"""

import spx
from math import sqrt
from hashlib import sha256
from secrets import token_bytes
import sys
import hmac
import time

#################################################################
# Definitions of helping functions used in algorithms
#################################################################

# Input: Node Id
# Output: Number of 1 bits in a number
def bit_width(index):
    return bin(index).count("1")

# Input: Node Id
# Output: Least significant bit position
def lsb(index):
    return int(index & -index).bit_length()

# Input: Node Id
# Output: Most significant bit position
def msb(index):
    return index.bit_length()

# Input: Byte string to pad
# Output: Padded string that uses the len value for the pad
def block_pad(value):
    block_size=32
    padding_size = (block_size - len(value) % block_size)
    padding_value = chr(padding_size)
    pad = value + bytes((padding_value * padding_size), 'utf-8')

    return pad

#################################################################
# MTL Data Structures
#################################################################
################################################################
# Data Structure 1: MTL Ladder Declaration
################################################################

class MTL_LADDER:
    def __init__(self, flags, sid, rungs=[]):
        self.flags = flags
        self.sid = sid
        self.rung_count = len(rungs)
        self.rungs = rungs

    def bytes(self):
        buffer  = self.flags.to_bytes(2,'big')
        buffer += self.sid[:8]
        buffer += self.rung_count.to_bytes(2,'big')
        for rung in self.rungs:
            buffer += rung.bytes()
        return buffer

################################################################
# Data Structure 2: MTL Ladder Rung Declaration
################################################################

class RUNG:
    def __init__(self, left_index, right_index, hash):
        self.left_index = left_index
        self.right_index = right_index
        self.hash = hash

    def bytes(self):
        buffer  = self.left_index.to_bytes(4,'big')
        buffer += self.right_index.to_bytes(4,'big')
        buffer += self.hash
        return buffer

################################################################
# Data Structure 3: MTL Authentication Path Declaration
################################################################

class MTL_AUTH_PATH:
    def __init__(self, flags, leaf_index, sid, sibling_hash,
                 rung_left, rung_right):
        self.flags = flags
        self.sid = sid
        self.leaf_index = leaf_index
        self.rung_left = rung_left
        self.rung_right = rung_right
        self.sibling_hash_count = len(sibling_hash)
        self.sibling_hash = sibling_hash

    def bytes(self):
        buffer  = self.flags.to_bytes(2,'big')
        sid_value = self.sid
        if(len(sid_value) < 8):
            sid_value += b'\x00' * (8 - len(sid_value))
        buffer += sid_value[:8]
        buffer += self.leaf_index.to_bytes(4,'big')
        buffer += self.rung_left.to_bytes(4,'big')
        buffer += self.rung_right.to_bytes(4,'big')
        buffer += self.sibling_hash_count.to_bytes(2,'big')
        buffer += b''.join(self.sibling_hash)

        return buffer

##################################################################
# Data Structure 4: MTL Node Set Declaration.
##################################################################

class MTLNS:
    def __init__(self, seed, sid):
        self.seed = seed
        self.sid = sid
        self.count = 0
        self.hashes = {}

##################################################################
# Data Structure 5: Full MTL Mode Signature Declaration
##################################################################

class MTL_SIG:
    def __init__(self, R_mtl, auth, ladder, sig):
        self.R_mtl = R_mtl
        self.auth = auth
        self.ladder = ladder
        self.siglen = len(sig)
        self.sig = sig

    def bytes(self):
        buffer  = self.R_mtl
        buffer += self.auth.bytes()
        buffer += self.ladder.bytes()
        buffer += self.siglen.to_bytes(4,'big')
        buffer += self.sig
        return buffer

##################################################################
# Data Structure 6: Condensed MTL Mode Signature Declaration
##################################################################

class MTL_CONDENSED_SIG:
    def __init__(self, R_mtl, auth):
        self.R_mtl = R_mtl
        self.auth = auth

    def bytes(self):
        buffer  = self.R_mtl
        buffer += self.auth.bytes()

        return buffer


#################################################################
# MTL Algorithms
#################################################################
##################################################################
# Algorithm 1: Hashing a Data Value to Produce a Leaf Node.
##################################################################
# Input: seed, seed value for the node set (associated with
#     public key)
# Input: sid, series identifier for the node set
# Input: leaf_index of the leaf node hash value
#     being computed
# Input: data_value corresponding to the leaf node
# Output: leaf_hash, leaf node hash value

def hash_leaf(seed, sid, leaf_index, data_value):
    dataADRS = spx.ADRS()
    dataADRS.setType(spx.ADRS.MTL_DATA)
    dataADRS.setSID(sid)
    dataADRS.setLeafIndex(leaf_index)

    leaf_hash = spx.F(seed, dataADRS.bytes(), data_value)

    return leaf_hash

##################################################################
# Algorithm 2: Hashing Two Child Nodes to Produce an Internal Node.
##################################################################
# Input: seed, seed value for the node set (associated with
#     public key)
# Input: sid, series identifier for the node set
# Input: left_index, left part of the internal node index pair
# Input: right_index, right part of the internal node index pair
# Input: left_hash, left child hash value
# Input: right_hash, right child hash value
# Output: internal_hash, internal node hash value

def hash_int(seed, sid, left_index, right_index,
             left_hash, right_hash):
    mtlnsADRS = spx.ADRS()
    mtlnsADRS.setType(spx.ADRS.MTL_TREE)
    mtlnsADRS.setSID(sid)
    mtlnsADRS.setLeftRightIndexes(left_index, right_index)

    internal_hash = spx.H(seed, mtlnsADRS.bytes(),
                          left_hash, right_hash)

    return internal_hash

##################################################################
# Algorithm 3: Initializing a MTL Node Set.
##################################################################
# Input: seed, seed value for this node set (associated with
#     public key)
# Input: sid, series identifier for this node set
# Output: node_set, new MTL node set object

def mtl_initns(seed, sid):
    node_set = MTLNS(seed, sid)
    return node_set

##################################################################
# Algorithm 4: Appending a Data Value to a MTL Node Set.
##################################################################
# Input: data_value to append to the node set
# Input: node_set, MTL node set object (updated in place)
# Output: leaf_index assigned to the data value

def mtl_append(data_value, node_set):
    leaf_index = node_set.count
    node_set.count = leaf_index + 1

    seed = node_set.seed
    sid = node_set.sid

    # Compute and store the leaf node hash value
    node_set.hashes[leaf_index,leaf_index] = hash_leaf(seed, sid,
                leaf_index, data_value)

    # Compute and store additional internal node hash values
    for i in range(1,lsb(leaf_index+1)):
        left_index = leaf_index - 2**i + 1
        mid_index = leaf_index - 2**(i-1) + 1
        node_set.hashes[left_index, leaf_index] = hash_int(seed,
                sid, left_index, leaf_index,
                node_set.hashes[left_index, mid_index - 1],
                node_set.hashes[mid_index, leaf_index])

    return leaf_index

##################################################################
# Algorithm 5: Computing an Authentication Path for a Data Value.
##################################################################
# Input: leaf_index, leaf node index of the data value to
#     authenticate
# Input: node_set, MTL node set object encompassing the specified
#     leaf node
# Output: auth_path, authentication path from the leaf node to the
#     associated rung

def mtl_authpath(leaf_index, node_set):
    left_index = 0
    sibling_hashes  = []
    flags = 0

    # Check that the leaf is part of this node set
    if(leaf_index < 0) or (leaf_index >= node_set.count):
        return None # Leaf is outside of node set

    # Find the rung index pair covering the leaf index
    for i in range(msb(node_set.count),-1,-1):
        if node_set.count & (1 << i):
            right_index = left_index + 2**i - 1
            if leaf_index <= right_index:
                break
            left_index = right_index + 1

    # Concatenate the sibling nodes from the leaf to the rung
    for i in range(0, bit_width(right_index-left_index)):
        if leaf_index & (1<<i):
            sibling_left = (~(2**i-1) & leaf_index) - 2**i
        else:
            sibling_left = (~(2**i-1) & leaf_index) + 2**i
        sibling_right = sibling_left + 2**i -1
        sibling_hashes.append(node_set.hashes[sibling_left,
                                              sibling_right])

    auth_path =  MTL_AUTH_PATH(flags, leaf_index, node_set.sid,
                         sibling_hashes, left_index, right_index)
    return auth_path

##################################################################
# Algorithm 6: Computing a Merkle Tree Ladder for a Node Set.
##################################################################
# Input: node_set, MTL node set object
# Output: ladder, Merkle tree ladder for this node set

def mtl_ladder(node_set):
    left_index = 0
    rungs = []
    flags = 0

    # Concatenate the rungs in the node set
    for i in range(msb(node_set.count),-1,-1):
        if node_set.count & (1 << i):
            right_index = left_index + 2**i - 1
            rungs.append(RUNG(left_index, right_index,
                         node_set.hashes[left_index,right_index]))
            left_index = right_index + 1

    ladder = MTL_LADDER(flags, node_set.sid, rungs)
    return ladder

##################################################################
# Algorithm 7: Selecting a Ladder Rung.
##################################################################
# Input: auth_path, authentication path from the leaf node to
#     a rung in the ladder
# Input: ladder, Merkle tree ladder to authenticate relative to
# Output: assoc_rung, the rung in the ladder associated with the
#     authentication path or None

def mtl_rung(auth_path, ladder):

    # Check that authentication path and ladder have
    #     same SID
    if(auth_path.sid != ladder.sid):
        return None

    leaf_index = auth_path.leaf_index
    sibling_hash_count = auth_path.sibling_hash_count

    # Check that auth path is a binary rung strategy path
    left_index = leaf_index & ~(2**sibling_hash_count-1)
    right_index = left_index + (2**sibling_hash_count-1)
    if((auth_path.rung_left != left_index) or
       (auth_path.rung_right != right_index)):
        return None

    # Find associated rung with lowest degree, if present
    assoc_rung = None
    # Minimum degree is updated after first rung is found
    min_degree = -1

    for rung in ladder.rungs:
        # Check if rung index pair would be encountered in
        #     evaluating authentication path for leaf node
        left_index = rung.left_index
        right_index = rung.right_index
        if((left_index <= leaf_index) and
           (right_index >= leaf_index)):
            degree = lsb(right_index-left_index+1)-1
            if(((degree <= lsb(left_index)-1) or
                (lsb(left_index) == 0)) and
               (right_index-left_index+1 == 2**degree) and
               (degree <= sibling_hash_count)):
                if((assoc_rung == None) or
                   (degree < min_degree)):
                    assoc_rung = rung
                    min_degree = degree

    return assoc_rung


##################################################################
# Algorithm 8: Verifying an Authentication Path.
##################################################################
# Input: seed value for this operation (associated with
#     public key)
# Input: data_value to authenticate
# Input: auth_path, (presumed) authentication path from
#     corresponding leaf node to rung of ladder covering leaf node
# Input: assoc_rung, Merkle tree rung to authenticate relative to
# Output: result, a Boolean indicating whether the data value is
#     successfully authenticated

def mtl_verify(seed, data_value, auth_path, assoc_rung):

    sid = auth_path.sid
    leaf_index = auth_path.leaf_index
    sibling_hash_count = auth_path.sibling_hash_count

    # Recompute leaf node hash value
    target_hash = hash_leaf(seed, sid, leaf_index, data_value)

    # Compare leaf node hash value to associated rung hash value
    #     if index pairs match
    if ((leaf_index == assoc_rung.left_index) and
        (leaf_index == assoc_rung.right_index)):
        return target_hash == assoc_rung.hash

    # Recompute internal node hash values and compare to associated
    #     rung hash value if index pairs match
    for i in range(1, sibling_hash_count+1):
        left_index  = leaf_index & ~(2**i-1)
        right_index = left_index + 2**i -1
        mid_index   = left_index + 2**(i-1)

        sibling_hash = auth_path.sibling_hash[i-1]
        if leaf_index < mid_index:
            target_hash = hash_int(seed, sid, left_index,
                                   right_index, target_hash,
                                   sibling_hash)
        else:
            target_hash = hash_int(seed, sid, left_index,
                                   right_index, sibling_hash,
                                   target_hash)

        # Break if associated rung reached
        if((left_index == assoc_rung.left_index) and
           (right_index == assoc_rung.right_index)):
            return target_hash == assoc_rung.hash

    return False

-------------------------- spx.py --------------------------------
"""
This is a stub implementation of SPHINCS+ underlying
  signature functions to demonstrate how MTL mode
  with underlying SPHINCS+ signatures would work.
  These classes and functions should be replaced
  with actual implementations.
"""

from hashlib import sha256
from secrets import token_bytes
import sys
import hmac
import time

# Property that come from the underlying schemes
#    Use non-deterministic hashing
RANDOMIZE = False
#    Number of bytes in the hashing function
n = 32

# Define this so that the algorithm code is easy to read.
# Since this overrides the default rand, it should be
#     replaced in the code for any real experimentation
#     to avoid any conflicts
def rand(n):
    return token_bytes(n)

##################################################
#  SPX Placeholder Functions: Created for the test
#      code. To be replaced by actual underlying
#      SPHINCS+ or other scheme implementations
##################################################
class SPX_SK:
    def __init__(self, seed, prf, pk_seed, pk_root):
        self.seed = seed
        self.prf = prf
        self.pk_seed = pk_seed
        self.pk_root = pk_root

class SPX_PK:
    def __init__(self, seed, root):
        self.seed = seed
        self.root = root

# This function doesn't compute the root but uses random data
# TODO: Replace the code in this stub with the actual calls
#     to use SPHINCS+
def spx_keygen():
    PK = SPX_PK(rand(n),rand(n))
    SK = SPX_SK(rand(n),rand(n),PK.seed, PK.root)

    return SPXKEY(SK,PK)

# Signing doesn't actually use a SPHINCS+ signature, but instead
#     hashes the data for compactness
# TODO: Replace the code in this stub with the actual calls
#     to use SPHINCS+
def spx_sign(M, SK):
    data_value = sha256()
    data_value.update(M)
    return data_value.digest()

# Signing doesn't actually verify a SPHINCS+ signature, but instead
#     hashes the data for compactness
# TODO: Replace the code in this stub with the actual calls
#     to use SPHINCS+
def spx_verify(M, sig, PK):
    m = sha256()
    m.update(M)
    digest = m.digest()

    return digest == sig

# Stub for the prf function
# TODO: Replace the code in this stub with the actual calls
#     to use SPHINCS+
def prf_msg(prf, opt, message):
    m = opt + message
    return hmac.new(prf, m, sha256).digest()

# Stub for the F function
# TODO: Replace the code in this stub with the actual calls
#     to use SPHINCS+
def F(seed, dataADRS, data_value):
    m = sha256()
    m.update(block_pad(seed[:32]))
    m.update(dataADRS)
    m.update(data_value)

    return m.digest()

# Stub for the H function
# TODO: Replace the code in this stub with the actual calls
#     to use SPHINCS+
def H(seed, mtlnsADRS, left_hash, right_hash):
    m = sha256()
    m.update(block_pad(seed[:32]))
    m.update(mtlnsADRS)
    m.update(left_hash)
    m.update(right_hash)

    return m.digest()

# Stub for the hash message
# TODO: Replace the code in this stub with the actual calls
#     to use SPHINCS+
def h_mtl_msg(R, pkseed, pkroot, message):

    m = sha256()
    m.update(R)
    m.update(pkseed)
    m.update(pkroot)
    m.update(message)
    msg = m.digest()

    # Should be MGF1-SHA-256 - TODO
    h = sha256()
    h.update(R)
    h.update(pkseed)
    h.update(msg)
    return h.digest()


class SKMTL:
    def __init__(self, sk, mtlns):
        self.sk = sk
        self.mtlns = mtlns

class SPXKEY:
    def __init__(self, sk, pk):
        self.sk = sk
        self.pk = pk

class SPXMTLLADDER:
    def __init__(self, ladder, sig):
        self.ladder = ladder
        self.sig = sig

    def bytes(self):
        return self.ladder.bytes() + self.sig

class ADRS:
    MTL_MSG = 16
    MTL_DATA = 17
    MTL_TREE = 18
    MTL_LADDER = 19

    layer_addr = b'\x00\x00\x00\x00'
    tree_addr = b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
    addr_type = b'\x00\x00\x00\x00'
    addr1 = b'\x00\x00\x00\x00'
    addr2 = b'\x00\x00\x00\x00'
    addr3 = b'\x00\x00\x00\x00'

    def setType(self, atype):
        self.addr_type = atype.to_bytes(4, 'big')

    def setMessageId(self, msgid):
        self.addr3 = msgid.to_bytes(4, 'big')

    def setLeafIndex(self, leaf_index):
        self.addr2 = leaf_index.to_bytes(4, 'big')
        self.addr3 = leaf_index.to_bytes(4, 'big')

    def setLeftRightIndexes(self, left_index, right_index):
        self.addr2 = left_index.to_bytes(4, 'big')
        self.addr3 = right_index.to_bytes(4, 'big')

    def setSID(self, sid):
        if(len(sid) < 8):
            sid += b'\x00' * (8 - len(sid))
        self.tree_addr = sid[:8]

    def bytes(self):
        return b''.join([self.layer_addr,self.tree_addr,
                self.addr_type,self.addr1,self.addr2,self.addr3])

# Input: Byte string to pad
# Output: Padded string that uses the len value for the pad
def block_pad(value):
    block_size=32
    padding_size = (block_size - len(value) % block_size)
    padding_value = chr(padding_size)
    pad = value + bytes((padding_value * padding_size), 'utf-8')

    return pad

------------------------- mtl_test.py -------------------------------
"""
pytest harness for verifying the MTL algorithms with an underlying
  SPHINCS+ signature API.
"""

import mtl
import spx
from textwrap import wrap
from secrets import token_bytes
from hashlib import sha256
import hmac

SID = b'0123456789012345'
good_msg = "Test Message".encode('utf-8')
bad_msg  = "Invalid Message".encode('utf-8')

# Define this so that the algorithm code is easy to read.
# Since this overrides the default rand, it should be
#     replaced in the code for any real experimentation
#     to avoid any conflicts
def rand(n):
    return token_bytes(n)

#################################################################
# Functions to print data structures to see what is happening
#################################################################
def print_node_set(node_set):
    max_width = 0
    print("=== MTL Node Set =======================")
    for left_index, right_index in node_set.hashes:
        if max_width < (right_index-left_index):
            max_width = right_index-left_index
    for left_index, right_index in node_set.hashes:
        print(f"({left_index},{right_index})")
        print(f" {node_set.hashes[(left_index, right_index)].hex()}")

def print_ladder(ladder):
    print("=== MTL Ladder =======================")
    for rung in ladder.rungs:
        print(f"({rung.left_index},{rung.right_index})")
        print(f"    {rung.hash.hex()}")

def print_signature(sig):
    print("=== MTL Signature =======================")
    for segment in wrap(sig.bytes().hex(), 64):
        print(f"{segment}")


#################################################################
# Consolidated functions
#################################################################
##################################################################
# SPHINCS+-MTLi Key Pair Generation
##################################################################
# Output: SPXKEY, a key object with the SPHINCS+ secret key and
#                 MTL node set along with the SPHINCS+ Public Key

def spx_mtl_keygen():
    # Generate SPHINCS+ key pair
    spxkey = spx.spx_keygen()
    # Form series identifier consisting of all 0s and initialize
    #     MTL node set with this series identifier
    sid = b'\x00' * 8
    node_set = mtl.mtl_initns(spxkey.pk.seed, sid)

    # Form and return SPHINCS+ key pair
    return spx.SPXKEY(spx.SKMTL(spxkey.sk, node_set), spxkey.pk)

#################################################################
# SPHINCS+-MTLi Message Series Append
#################################################################
# Input: M, message to be signed
# Input: SK_mtl, SPHINCS+-MTLi private key that contains a SPHINCS+
#     private key SK (including SK.seed, SK.prf, PK.seed, PK.root)
#     and a MTL node set node_set (updated in place)
# # Output: MTL record index (mtl_leaf_index, randomizer_mtl)
def spx_mtl_append(M, SK_mtl):
    leaf_index = SK_mtl.mtlns.count
    mtlADRS = spx.ADRS()
    mtlADRS.setType(spx.ADRS.MTL_MSG)
    mtlADRS.setSID(SK_mtl.mtlns.sid)
    mtlADRS.setMessageId(leaf_index)

    # Choose the public seed as input to the randomized message
    #     digest operation for deterministic hashing, or generate a
    #     random value for randomized hashing
    opt = SK_mtl.sk.pk_seed
    if spx.RANDOMIZE:
        opt = rand(n)

    randomizer_mtl = spx.prf_msg(SK_mtl.sk.prf, opt,
                                 mtlADRS.bytes() + M)
    data_value = spx.h_mtl_msg(randomizer_mtl,
                               SK_mtl.sk.pk_seed,
                               SK_mtl.sk.pk_root, M)

    # Add the M hash to the mtl node set
    mtl_leaf_index = mtl.mtl_append(data_value, SK_mtl.mtlns)

    return mtl_leaf_index, randomizer_mtl

##################################################################
# SPHINCS+-MTLi Signature Generation
##################################################################
# Input: M, message to be signed
# Input: SK_mtl, SPHINCS+-MTLi private key that contains a SPHINCS+
#     private key SK (including SK.seed, SK.prf, PK.seed, PK.root)
#     and a MTL node set node_set (updated in place)
# Output: sig_spx_mtl, SPHINCS+-MTL signature = (randomizer_mtl,
#     auth_path, ladder, sig_spx)

def spx_mtl_sign(M, SK_mtl):
    # Add the message to the MTL node set
    mtl_leaf_index, randomizer_mtl = spx_mtl_append(M, SK_mtl)

    auth_path = mtl.mtl_authpath(mtl_leaf_index, SK_mtl.mtlns)
    ladder = mtl.mtl_ladder(SK_mtl.mtlns)

    # Sign the ladder with the MTL tree address
    sepADRS = spx.ADRS()
    sepADRS.setType(spx.ADRS.MTL_LADDER)
    sepADRS.setSID(SK_mtl.mtlns.sid)

    signature = spx.spx_sign(sepADRS.bytes() + ladder.bytes(),
                             SK_mtl.sk)

    sig_spx_mtl = mtl.MTL_SIG(randomizer_mtl, auth_path,
                            ladder, signature)
    return sig_spx_mtl

##################################################################
# SPHINCS+-MTL Signature Verification
##################################################################
# Input: M, Message to verify
# Input: signature, Signature to use for verification
# Input: PK that corresponds to the secret key from the signed
#     message
# Output: Boolean if signature verifies correctly

def spx_mtl_verify(M, signature, PK):
    data_value = spx.h_mtl_msg(signature.R_mtl, PK.seed, PK.root, M)
    sepADRS = spx.ADRS()
    sepADRS.setSID(signature.auth.sid)
    sepADRS.setType(spx.ADRS.MTL_LADDER)

    # Verify the SPHINCS+ signature on the ladder
    if(spx.spx_verify(sepADRS.bytes() + signature.ladder.bytes(),
                  signature.sig, PK)):
        # Verify the MTL authentication path
        ladder_rung = mtl.mtl_rung(signature.auth, signature.ladder)
        if(mtl.mtl_verify(PK.seed, data_value, signature.auth,
                      ladder_rung)):
            return True
    return False

#################################################################
# Test Functions
#################################################################
##################################################################
# Test 1: Sign and verify a single message
##################################################################
def test_sign_message():
    # Generate a key set for MTL plus the stubbed SPHINCS+
    spxkey = spx_mtl_keygen()

    # Sign the message using MTL and the underyling secret key
    sig = spx_mtl_sign(good_msg,spxkey.sk)

    # Verify the message signature
    assert(spx_mtl_verify(good_msg,sig,spxkey.pk))
    # Check that a different message doesn't work
    assert(not spx_mtl_verify(bad_msg,sig,spxkey.pk))

    # Show the resulting data structures (requires pytest -s)
    print(f"\n>>> Message ID {sig.auth.leaf_index}")
    print_node_set(spxkey.sk.mtlns)
    print_ladder(sig.ladder)
    print_signature(sig)

##################################################################
# Test 2: Sign and verify multiple messages, one at a time
##################################################################
def test_sign_messages_incremental():
    # Setup how many messages should be tested
    test_message_count = 15

    # Generate a key set for MTL plus the stubbed SPHINCS+
    spxkey = spx_mtl_keygen()

    # Test Signing Multiple Messages
    for node in range(0,test_message_count):
        # Create the message to sign
        message = f"Test Message {node}".encode('utf-8')

        # Sign the message w/MTL and the underyling secret key
        sig = spx_mtl_sign(message,spxkey.sk)

        # Verify the message signature
        assert(spx_mtl_verify(message,sig,spxkey.pk))
        # Check for fail with different message
        assert(not spx_mtl_verify(bad_msg,sig,spxkey.pk))

    # Show the resulting data structures (requires pytest -s)
    print(f"\n>>> Message ID {sig.auth.leaf_index}")
    print_node_set(spxkey.sk.mtlns)
    print_ladder(sig.ladder)
    print_signature(sig)

##################################################################
# Test 3: Sign and verify multiple messages as a batch
#         Only performs underlying signature one time
##################################################################
def test_sign_verify_multi_record_batch():
    # Setup how many messages should be tested
    test_message_count = 1024

    # Not using non-deterministic hashing for this test
    signatures = {}
    mtl_leaf_list = []

    # Generate a key set for MTL plus the stubbed SPHINCS+
    spxkey = spx_mtl_keygen()
    # Initalize a new node set - the node set must be
    #    kept separately since
    node_set = mtl.mtl_initns(SID, spxkey.pk.seed)

    # Add messages to the MTL node set
    for node in range(0,test_message_count):
        # Create the message to sign
        message = f"Test Message {node}".encode('utf-8')
        # Add the message to the MTL node set
        mtl_leaf_list.append(spx_mtl_append(message, spxkey.sk))

    # Fetch the ladder that represents all the batch messages
    ladder = mtl.mtl_ladder(spxkey.sk.mtlns)

    # Sign the ladder with the MTL tree address
    sep_addr = spx.ADRS()
    sep_addr.setType(spx.ADRS.MTL_LADDER)
    sep_addr.setSID(spxkey.sk.mtlns.sid)
    signature = spx.spx_sign(sep_addr.bytes() + ladder.bytes(),
                             spxkey.sk.sk)

    # Get the authentication path for each message
    for leaf in mtl_leaf_list:
        leaf_index, rtml = leaf
        message = f"Test Message {leaf_index}".encode('utf-8')
        auth_path = mtl.mtl_authpath(leaf_index, spxkey.sk.mtlns)

        # Save the signatures for later to be verified
        signatures[message] = mtl.MTL_SIG(rtml, auth_path, ladder,
                                          signature)

    # Verify the authentication path for each message
    for sig_set in signatures:
        # Verify the message signature
        assert(spx_mtl_verify(sig_set, signatures[sig_set],
               spxkey.pk))
        # Check for fail with different message
        assert(not spx_mtl_verify(bad_msg, signatures[sig_set],
               spxkey.pk))

##################################################################
# Test 4: Sign a message set and condense the last signature
##################################################################
def test_condense_incremental_signature():
    # Setup how many messages should be tested
    test_message_count = 1024

    # Generate a key set for MTL plus the stubbed SPHINCS+
    spxkey = spx_mtl_keygen()

    # Create a set of records
    for node in range(0,test_message_count):
        # Create the message to sign
        message = f"Test Message {node}".encode('utf-8')
        # Sign the message w/MTL and the underyling secret key
        sig = spx_mtl_sign(message,spxkey.sk)

    # Get the condensed signature for the last message
    mtl_auth_condensed = mtl.MTL_CONDENSED_SIG(sig.R_mtl, sig.auth)
    # Fetch the ladder for the condensed signature
    mtl_spx_ladder = spx.SPXMTLLADDER(sig.ladder, sig.sig)

    # Print out the resulting signature information and the lengths
    print(f"\n ===== Full Signature (len {len(sig.bytes())})" +
          f" w/fake underlying signature ============")
    for segment in wrap(sig.bytes().hex(), 64):
        print(f"   {segment}")
    print("   Note: Underlying signature is a stub (SHA256 hash).")
    print("    Remove 32 bytes and add signature bytes to compare")


    print(f"\n ===== Condensed Path " +
          f"(len {len(mtl_auth_condensed.bytes())})" +
          f" ========================================")
    for segment in wrap(mtl_auth_condensed.bytes().hex(), 64):
        print(f"   {segment}")

    print(f"\n =====  Signed Ladder " +
          f"(len {len(mtl_spx_ladder.bytes())})" +
          f"  w/fake underlying signature =============")
    for segment in wrap(mtl_spx_ladder.bytes().hex(), 64):
        print(f"   {segment}")
    print("   Note: Underlying signature is a stub (SHA256 hash).")
    print("    Remove 32 bytes and add signature bytes to compare")

##################################################################
# Test 5: Sign a message set, condense and then reconstitute
#         the last signature
##################################################################
def test_reconstitute_incremental_signature():
    # Setup how many messages should be tested
    test_message_count = 1024

    # Generate a key set for MTL plus the stubbed SPHINCS+
    spxkey = spx_mtl_keygen()

    # Create a set of records
    for node in range(0,test_message_count):
        # Create the message to sign
        message = f"Test Message {node}".encode('utf-8')
        # Sign the message w/MTL and the underyling secret key
        sig = spx_mtl_sign(message,spxkey.sk)

    # Get the condensed signature for the last message
    mtl_auth_condensed = mtl.MTL_CONDENSED_SIG(sig.R_mtl, sig.auth)
    # Fetch the ladder for the condensed signature
    mtl_spx_ladder = spx.SPXMTLLADDER(sig.ladder, sig.sig)

    # Reconstitute the last message with the auth path and ladder
    # Note: Assuming the handle points to the condensed ladder.
    #     In a real scenario the handle should be used to ensure
    #     an appropriate ladder is used.
    reconstituted_sig = mtl.MTL_SIG(mtl_auth_condensed.R_mtl,
        mtl_auth_condensed.auth, mtl_spx_ladder.ladder,
        mtl_spx_ladder.sig)

     # Verify the message signature
    assert(spx_mtl_verify(message,reconstituted_sig,spxkey.pk))
    # Check for fail with different message
    assert(not spx_mtl_verify(bad_msg,reconstituted_sig,spxkey.pk))

    print(f"\n ===== Reconstituted Signature (len " +
         f"{len(reconstituted_sig.bytes())})" +
         f" w/fake underlying signature ====")
    for segment in wrap(reconstituted_sig.bytes().hex(), 64):
        print(f"   {segment}")
    print("   Note: Underlying signature is a stub (SHA256 hash).")
    print("    Remove 32 bytes and add signature bytes to compare")

>>> Message ID 0
=== MTL Node Set =======================
(0,0)
    af7d4a1bea359d3a578a846ec2bf0e69c34f8833d7332ae32e0b82997baa90b8
=== MTL Ladder =======================
(0,0)
    af7d4a1bea359d3a578a846ec2bf0e69c34f8833d7332ae32e0b82997baa90b8
=== MTL Signature =======================
260f918fc224f074761e4c4adeb7d8bdf4b26cd6d6ebc9e500d5a824e338b189
0000000000000000000000000000000000000000000000000000000000000000
000000010000000000000000af7d4a1bea359d3a578a846ec2bf0e69c34f8833
d7332ae32e0b82997baa90b800000020148f0a787c2128f51630c1247acf528a
bc0ad11d9f9976cb7cd2e4e34ac11dd8


>>> Message ID 14
=== MTL Node Set =======================
(0,0)
    90885ec41541d80b9d2321a89ba22aaac24bfd83983629e4f6321e6fd73971a8
(1,1)
    6bb46cc9a692ec32d85d3056fda670f047dac054278c47fa58a9d85f3a8c3ab6
(0,1)
    ab79f7f0b68baef5bd2a88adda4986d37dea0dc623c467052d54bfda15dcdd50
(2,2)
    08cc36404c05451bb359c19274f3490cf699fa3821f6fa1d22d2391e781dbc5d
(3,3)
    dfa0847ab4f3fe5cf8c90accd345aaa1b39f7a805ef7151ee3f60a2dcb39deb4
(2,3)
    ccca3f26e19bfe8ff8ca0ecdd387ad77d4b7550bca47be2c6ce7cf311b14b6bb
(0,3)
    b0b956ccdf9376abb65c2de4adb32b2002685a76470d6f837bf9acf3e67a16cf
(4,4)
    e9a7f5152c904579d13961f224e5079f750ce5b854cf1864c17c4de19a2fb7f0
(5,5)
    c90fff55c43f55087d0509d81a7bf235ed172c49760b3aef0e77723e88277ca8
(4,5)
    402b3fd5c8d9f508823b9ae595cfa4fb484b634bff00907e84c836c325618071
(6,6)
    e921e204e4859007641025ad493f5155b21a8143aca65a2167c150cf502d5061
(7,7)
    a555767ca23936b57a399fe60870118f634b59f72f342f5a926f7e8fb24ed18f
(6,7)
    070a5fb7cc11819459cf42cb856083bbb89b1323cdada7c0a1fe6923fd8d2ddd
(4,7)
    b1eef8a3a285a5a53ba5c3338839f645407bdd2a199e8db4d5064fc0ab005f38
(0,7)
    f6c4315a7824ffc2fdbb2734a701782e4ae4b3cc51bd985cf8e38e6bd6cf1f71
(8,8)
    76a4e1eb3a6704f89482edd395a3cb6b518b9c135c0f3e2dd33e15ec03a15195
(9,9)
    65dd60329127f06362b8ac19f07973dd672f06cfdca7cd08634e44ee2bfbe12f
(8,9)
    38d7fa56eff168a91d358bf4a7b7192ee0f0fe6f77914020b8e876224a73efef
(10,10)
    1db3087f33ee86aeaa9458e3b3e85b17e7b08b05ffecac5b5a7ad85d4c902d0f
(11,11)
    54c82d5529593ee9bc571d15b47c05e500bfe74be787996115bbf61008f8480d
(10,11)
    9bd9256c9053aebd96c69b8b1daaa31a02897ad9457da92572b1c3ffa153a975
(8,11)
    ac3d9b008bccd126d1d833dc22091bfc614d376576152b9c7bbb7f53428dc0d5
(12,12)
    793669679a28408866d8e8620162510674526fda5a50b2eb3a7e73ee19c6e291
(13,13)
    4050397b554c2e555144c01d3e6422e162b4beb5c548cb31225da0830475fec1
(12,13)
    377d3e97b80914460eaa1c5b6a5e6d071a5e614dd0e2fd1b88e56f083c699526
(14,14)
    ca30a9a18dd8bc1aab3beebd74832299ea9ec1218cefa75c91b70a4c06b05f01
=== MTL Ladder =======================
(0,7)
    f6c4315a7824ffc2fdbb2734a701782e4ae4b3cc51bd985cf8e38e6bd6cf1f71
(8,11)
    ac3d9b008bccd126d1d833dc22091bfc614d376576152b9c7bbb7f53428dc0d5
(12,13)
    377d3e97b80914460eaa1c5b6a5e6d071a5e614dd0e2fd1b88e56f083c699526
(14,14)
    ca30a9a18dd8bc1aab3beebd74832299ea9ec1218cefa75c91b70a4c06b05f01
=== MTL Signature =======================
4dc2df90700edb3469b94aa71507fd6b83594354ac5805e076f499d0000d83e2
000000000000000000000000000e0000000e0000000e00000000000000000000
000000040000000000000007f6c4315a7824ffc2fdbb2734a701782e4ae4b3cc
51bd985cf8e38e6bd6cf1f71000000080000000bac3d9b008bccd126d1d833dc
22091bfc614d376576152b9c7bbb7f53428dc0d50000000c0000000d377d3e97
b80914460eaa1c5b6a5e6d071a5e614dd0e2fd1b88e56f083c6995260000000e
0000000eca30a9a18dd8bc1aab3beebd74832299ea9ec1218cefa75c91b70a4c
06b05f01000000204fc750e0d79cf1542e976c7db95989fbf7976c21be19a112
c25d0a547a6046bb

 ===== Full Signature (len 464) ============
   c23e1d84cd9fcb405b961ffc7112f201518a3ea0a385ecacb1e811b4f918481a
   00000000000000000000000003ff00000000000003ff000ae18407c19db0027c
   8687d7a3fa25aaca51bf9c5c5ae4a44642faaf4f063221ccab1048b35ae4ef70
   dac11079f310ead2be2eee39580d98b269df783581af32a17db4ea8c07dd3e07
   b9d4d7adf8dcdabbc3578e71730fa7fe472339be0d51db404511dff928b57f6e
   08874141978ba02a5ad8b05db062824f61f3d7dd14abd326cdc286ec29664e8d
   adf930762a2f15bae0d00fedf6384c3971fa315c96476e4dbbddfb399e9ebade
   2cc88c139b6e6fa12284134231ec0e17bb5d661d066a3b07a3f6446b62dd9e52
   2268dfd550b80016ea2c50a6b079f823cd71b02dcd41797008f78ed5dcbfcc9f
   20d0e0effc903cc5e5f1d47075f86a67c0636757fff963bf83303f05ff5e41b8
   4e53d32a078f51632725ccb3ba61b99040e8946761f011aeb3596b7f392e4900
   3ce8d007ac703307b1190c3c675599bd854b7c294f41943f0000000000000000
   0000000100000000000003ff39e43cfdb78daa9ccc38c7d8342167eb9e8fa968
   0a639050c2bc65a07996796900000020cb00605933efc08b05a60970293a609f
   440a9b81fd73bdd5e783e3da758a575e
   Note: Underlying signature is a stub (SHA256 hash).
         Remove 32 bytes and add signature bytes to compare

 ===== Condensed Path (len 376) =============
   c23e1d84cd9fcb405b961ffc7112f201518a3ea0a385ecacb1e811b4f918481a
   00000000000000000000000003ff00000000000003ff000ae18407c19db0027c
   8687d7a3fa25aaca51bf9c5c5ae4a44642faaf4f063221ccab1048b35ae4ef70
   dac11079f310ead2be2eee39580d98b269df783581af32a17db4ea8c07dd3e07
   b9d4d7adf8dcdabbc3578e71730fa7fe472339be0d51db404511dff928b57f6e
   08874141978ba02a5ad8b05db062824f61f3d7dd14abd326cdc286ec29664e8d
   adf930762a2f15bae0d00fedf6384c3971fa315c96476e4dbbddfb399e9ebade
   2cc88c139b6e6fa12284134231ec0e17bb5d661d066a3b07a3f6446b62dd9e52
   2268dfd550b80016ea2c50a6b079f823cd71b02dcd41797008f78ed5dcbfcc9f
   20d0e0effc903cc5e5f1d47075f86a67c0636757fff963bf83303f05ff5e41b8
   4e53d32a078f51632725ccb3ba61b99040e8946761f011aeb3596b7f392e4900
   3ce8d007ac703307b1190c3c675599bd854b7c294f41943f

 =====  Signed Ladder (len 84) =============
   00000000000000000000000100000000000003ff39e43cfdb78daa9ccc38c7d8
   342167eb9e8fa9680a639050c2bc65a079967969cb00605933efc08b05a60970
   293a609f440a9b81fd73bdd5e783e3da758a575e
   Note: Underlying signature is a stub (SHA256 hash).
         Remove 32 bytes and add signature bytes to compare

 ===== Reconstituted Signature (len 464) ===
   e47de2877319c902f73f8bd2a4bd8f168d9b579e48d768c24a3cd2d70d131db4
   00000000000000000000000003ff00000000000003ff000a0e482b126bd6318f
   677d22a28d366be44cbe6dd8709c1b9a0adcb01c7ad7e02d06e084b109aaccb0
   3cdd305c47040c0e299cdcf5f61a4dc28b4aa7ad2b6523e14605d72bcde7afba
   f16841b0ac2588204c1a373adfd91bc239fbf3f2219d8775aa67b5bf74f7bb13
   e764a8fcc8b4e30eba9da0c8db26d2e06403e8a4d00573ae33c434a3015e60a6
   4cce4bbce4d07cfdaf7a3be4198d9635b2f3d4126d2290d9fce69f62d3f10129
   269e922de914406276aca04e3f2df949b1f36e14c4a6373a8c137bbd9476dd2e
   702c34762e2a105bc260a8842f223dd5c338e01eb013c433139f758cee854e30
   07f4b8498a7c528a213c67feeec36cc63101d4d7cb5de3fe8ef774706196437b
   12131b105bb39947a03d82895f6908497d9acb797aba2459cd65f27c49f3bd43
   a50bbd2b732b1fdd6fbaacd9578c54ba9fe6a1207aaaf4ca0000000000000000
   0000000100000000000003ffc54f80e04cbed078c0ca20e89c868cc8f69219ab
   d96a8e0ab6fcdb6643df7aac000000204ed3fd35aa080e5e35e8c25f112fc3b7
   a4660b8f6d7087a69471d775d5e5c4ef
   Note: Underlying signature is a stub (SHA256 hash).
         Remove 32 bytes and add signature bytes to compare