/* wc_lms_impl.c
 *
 * Copyright (C) 2006-2024 wolfSSL Inc.
 *
 * This file is part of wolfSSL.
 *
 * wolfSSL is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * wolfSSL is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
 */

/* Implementation based on:
 *   RFC 8554: Leighton-Micali Hash-Based Signatures
 *   https://datatracker.ietf.org/doc/html/rfc8554
 * Implementation by Sean Parkinson.
 */

/* Possible LMS options:
 *
 * WC_LMS_FULL_HASH                                      Default: OFF
 *   Performs a full hash instead of assuming internals.
 *   Enable when using hardware SHA-256.
 * WOLFSSL_LMS_VERIFY_ONLY                               Default: OFF
 *   Only compiles in verification code.
 * WOLFSSL_WC_LMS_SMALL                                  Default: OFF
 *   Implementation is smaller code size with slow signing.
 *   Enable when memory is limited.
 */

#include <wolfssl/wolfcrypt/wc_lms.h>
#include <wolfssl/wolfcrypt/error-crypt.h>

#ifdef NO_INLINE
    #include <wolfssl/wolfcrypt/misc.h>
#else
    #define WOLFSSL_MISC_INCLUDED
    #include <wolfcrypt/src/misc.c>
#endif

#if defined(WOLFSSL_HAVE_LMS) && defined(WOLFSSL_WC_LMS)

/* Length of R in bytes. */
#define LMS_R_LEN           4
/* Length of D in bytes. */
#define LMS_D_LEN           2
/* Length of checksum in bytes. */
#define LMS_CKSM_LEN        2

/* Predefined values used in hashes to make them unique. */
/* Fixed value for calculating x. */
#define LMS_D_FIXED         0xff
/* D value when computing public key. */
#define LMS_D_PBLC          0x8080
/* D value when computing message. */
#define LMS_D_MESG          0x8181
/* D value when computing leaf node. */
#define LMS_D_LEAF          0x8282
/* D value when computing interior node. */
#define LMS_D_INTR          0x8383
/* D value when computing C, randomizer value. */
#define LMS_D_C             0xfffd
/* D value when computing child SEED for private key. */
#define LMS_D_CHILD_SEED    0xfffe
/* D value when computing child I for private key. */
#define LMS_D_CHILD_I       0xffff

/* Length of data to hash when computing seed:
 *   16 + 4 + 2 + 32 = 54 */
#define LMS_SEED_HASH_LEN  \
    (LMS_I_LEN + LMS_R_LEN + LMS_D_LEN + LMS_MAX_NODE_LEN)

/* Length of data to hash when computing a node:
 *   16 + 4 + 2 + 32 + 32 = 86 */
#define LMS_NODE_HASH_LEN   \
    (LMS_I_LEN + LMS_R_LEN + LMS_D_LEN + 2 * LMS_MAX_NODE_LEN)

/* Length of data to hash when computing most results:
 *   16 + 4 + 2 + 1 + 32 = 55 */
#define LMS_HASH_BUFFER_LEN \
    (LMS_I_LEN + LMS_Q_LEN + LMS_P_LEN + LMS_W_LEN + LMS_MAX_NODE_LEN)

/* Length of data to hash when computing Q:
 *   16 + 4 + 2 + 32 = 54 */
#define LMS_Q_BUFFER_LEN    \
    (LMS_I_LEN + LMS_Q_LEN + LMS_P_LEN + LMS_MAX_NODE_LEN)

/* Length of preliminary data to hash when computing K:
 *   16 + 4 + 2 = 22 */
#define LMS_K_PRE_LEN       (LMS_I_LEN + LMS_Q_LEN + LMS_P_LEN)

/* Length of preliminary data to hash when computing message hash:
 *   16 + 4 + 2 = 22 */
#define LMS_MSG_PRE_LEN     (LMS_I_LEN + LMS_Q_LEN + LMS_P_LEN)


#ifdef WC_LMS_DEBUG_PRINT_DATA
/* Print data when dubgging implementation.
 *
 * @param [in] name  String to print before data.
 * @param [in] data  Array of bytes.
 * @param [in] len   Length of data in array.
 */
static void print_data(const char* name, const byte* data, int len)
{
    int i;

    fprintf(stderr, "%6s: ", name);
    for (i = 0; i < len; i++) {
        fprintf(stderr, "%02x", data[i]);
    }
    fprintf(stderr, "\n");
}
#endif

/***************************************
 * Index APIs
 **************************************/

#ifndef WOLFSSL_LMS_VERIFY_ONLY
/* Zero index.
 *
 * @param [out] a    Byte array. Big-endian encoding.
 * @param [in]  len  Length of array in bytes.
 */
static WC_INLINE void wc_lms_idx_zero(unsigned char* a, int len)
{
    XMEMSET(a, 0, len);
}

/* Increment big-endian value.
 *
 * @param [in, out] a    Byte array. Big-endian encoding.
 * @param [in]      len  Length of array in bytes.
 */
static WC_INLINE void wc_lms_idx_inc(unsigned char* a, int len)
{
    int i;

    /* Starting at least-significant byte up to most. */
    for (i = len - 1; i >= 0; i--) {
        /* Add one/carry to byte. */
        if ((++a[i]) != 0) {
            /* No more carry. */
            break;
        }
    }
}
#endif /* !WOLFSSL_LMS_VERIFY_ONLY */

/***************************************
 * Hash APIs
 **************************************/

/* Set hash data and length into SHA-256 digest.
 *
 * @param [in, out] state  SHA-256 digest object.
 * @param [in]      data   Data to add to hash.
 * @param [in]      len    Number of bytes in data. Must be less than a block.
 */
#define LMS_SHA256_SET_DATA(sha256, data, len)  \
do {                                            \
    XMEMCPY((sha256)->buffer, (data), (len));   \
    (sha256)->buffLen = (len);                  \
    (sha256)->loLen = (len);                    \
} while (0)

/* Add hash data and length into SHA-256 digest.
 *
 * @param [in, out] state  SHA-256 digest object.
 * @param [in]      data   Data to add to hash.
 * @param [in]      len    Number of bytes in data. Must be less than a block.
 */
#define LMS_SHA256_ADD_DATA(sha256, data, len)                              \
do {                                                                        \
    XMEMCPY((byte*)(sha256)->buffer + (sha256)->buffLen, (data), (len));    \
    (sha256)->buffLen += (len);                                             \
    (sha256)->loLen += (len);                                               \
} while (0)

/* Set the length of 54 bytes in buffer as per SHA-256 final operation.
 *
 * @param [in, out] buffer  Hash data buffer to add length to.
 */
#define LMS_SHA256_SET_LEN_54(buffer)   \
do {                                    \
    (buffer)[54] = 0x80;                \
    (buffer)[55] = 0x00;                \
    (buffer)[56] = 0x00;                \
    (buffer)[57] = 0x00;                \
    (buffer)[58] = 0x00;                \
    (buffer)[59] = 0x00;                \
    (buffer)[60] = 0x00;                \
    (buffer)[61] = 0x00;                \
    (buffer)[62] = 0x01;                \
    (buffer)[63] = 0xb0;                \
} while (0)

/* Set the length of 55 bytes in buffer as per SHA-256 final operation.
 *
 * @param [in, out] buffer  Hash data buffer to add length to.
 */
#define LMS_SHA256_SET_LEN_55(buffer)   \
do {                                    \
    (buffer)[55] = 0x80;                \
    (buffer)[56] = 0x00;                \
    (buffer)[57] = 0x00;                \
    (buffer)[58] = 0x00;                \
    (buffer)[59] = 0x00;                \
    (buffer)[60] = 0x00;                \
    (buffer)[61] = 0x00;                \
    (buffer)[62] = 0x01;                \
    (buffer)[63] = 0xb8;                \
} while (0)

#ifndef WC_LMS_FULL_HASH
/* Hash one full block of data and compute result.
 *
 * @param [in]  sha256  SHA-256 hash object.
 * @param [in]  data    Data to hash.
 * @param [out] hash    Hash output.
 * @return  0 on success.
 */
static WC_INLINE int wc_lms_hash_block(wc_Sha256* sha256, const byte* data,
    byte* hash)
{
    /* Hash the block and reset SHA-256 state. */
    return wc_Sha256HashBlock(sha256, data, hash);
}
#endif /* !WC_LMS_FULL_HASH */

/* Hash data and compute result.
 *
 * @param [in]  sha256  SHA-256 hash object.
 * @param [in]  data    Data to hash.
 * @param [in]  len     Length of data to hash.
 * @param [out] hash    Hash output.
 * @return  0 on success.
 */
static WC_INLINE int wc_lms_hash(wc_Sha256* sha256, byte* data, word32 len,
    byte* hash)
{
    int ret;

#ifndef WC_LMS_FULL_HASH
    if (len < WC_SHA256_BLOCK_SIZE) {
        /* Store data into SHA-256 object's buffer. */
        LMS_SHA256_SET_DATA(sha256, data, len);
        ret = wc_Sha256Final(sha256, hash);
    }
    else if (len < WC_SHA256_BLOCK_SIZE + WC_SHA256_PAD_SIZE) {
        ret = wc_Sha256HashBlock(sha256, data, NULL);
        if (ret == 0) {
            byte* buffer = (byte*)sha256->buffer;
            int rem = len - WC_SHA256_BLOCK_SIZE;

            XMEMCPY(buffer, data + WC_SHA256_BLOCK_SIZE, rem);
            buffer[rem++] = 0x80;
            XMEMSET(buffer + rem, 0, WC_SHA256_BLOCK_SIZE - 2 - rem);
            buffer[WC_SHA256_BLOCK_SIZE - 2] = (byte)(len >> 5);
            buffer[WC_SHA256_BLOCK_SIZE - 1] = (byte)(len << 3);
            ret = wc_Sha256HashBlock(sha256, buffer, hash);
        }
    }
    else {
        ret = wc_Sha256Update(sha256, data, len);
        if (ret == 0) {
            ret = wc_Sha256Final(sha256, hash);
        }
    }
#else
    ret = wc_Sha256Update(sha256, data, len);
    if (ret == 0) {
        ret = wc_Sha256Final(sha256, hash);
    }
#endif /* !WC_LMS_FULL_HASH */

    return ret;
}

/* Update hash with first data.
 *
 * Sets the data directly into SHA-256's buffer if valid.
 *
 * @param [in]  sha256  SHA-256 hash object.
 * @param [in]  data    Data to hash.
 * @param [in]  len     Length of data to hash.
 * @return  0 on success.
 */
static WC_INLINE int wc_lms_hash_first(wc_Sha256* sha256, const byte* data,
    word32 len)
{
    int ret = 0;

#ifndef WC_LMS_FULL_HASH
    if (len < WC_SHA256_BLOCK_SIZE) {
        /* Store data into SHA-256 object's buffer. */
        LMS_SHA256_SET_DATA(sha256, data, len);
    }
    else
#endif /* !WC_LMS_FULL_HASH */
    {
        ret = wc_Sha256Update(sha256, data, len);
    }

    return ret;
}

/* Update hash with further data.
 *
 * Adds the data directly into SHA-256's buffer if valid.
 *
 * @param [in]  sha256  SHA-256 hash object.
 * @param [in]  data    Data to hash.
 * @param [in]  len     Length of data to hash.
 * @return  0 on success.
 */
static WC_INLINE int wc_lms_hash_update(wc_Sha256* sha256, const byte* data,
    word32 len)
{
    int ret = 0;

#ifndef WC_LMS_FULL_HASH
    if (sha256->buffLen + len < WC_SHA256_BLOCK_SIZE) {
        /* Add data to SHA-256 object's buffer. */
        LMS_SHA256_ADD_DATA(sha256, data, len);
    }
    else if (sha256->buffLen + len < 2 * WC_SHA256_BLOCK_SIZE) {
        byte* buffer = (byte*)sha256->buffer;

        XMEMCPY(buffer + sha256->buffLen, data,
            WC_SHA256_BLOCK_SIZE - sha256->buffLen);
        ret = wc_Sha256HashBlock(sha256, buffer, NULL);
        if (ret == 0) {
            int rem = len - (WC_SHA256_BLOCK_SIZE - sha256->buffLen);
            XMEMCPY(buffer, data + WC_SHA256_BLOCK_SIZE - sha256->buffLen, rem);
            sha256->buffLen = rem;
            sha256->loLen += len;
        }
    }
    else {
        ret = wc_Sha256Update(sha256, data, len);
    }
#else
    ret = wc_Sha256Update(sha256, data, len);
#endif /* !WC_LMS_FULL_HASH */

    return ret;
}

/* Finalize hash.
 *
 * @param [in]  sha256  SHA-256 hash object.
 * @param [out] hash    Hash output.
 * @return  0 on success.
 */
static WC_INLINE int wc_lms_hash_final(wc_Sha256* sha256, byte* hash)
{
#ifndef WC_LMS_FULL_HASH
    int ret = 0;
    byte* buffer = (byte*)sha256->buffer;

    buffer[sha256->buffLen++] = 0x80;
    if (sha256->buffLen > WC_SHA256_PAD_SIZE) {
        XMEMSET(buffer + sha256->buffLen, 0,
            WC_SHA256_BLOCK_SIZE - sha256->buffLen);
        ret = wc_Sha256HashBlock(sha256, buffer, NULL);
        sha256->buffLen = 0;
    }
    if (ret == 0) {
        XMEMSET(buffer + sha256->buffLen, 0,
            WC_SHA256_BLOCK_SIZE - 8 - sha256->buffLen);
        sha256->hiLen = (sha256->hiLen << 3) + (sha256->loLen >> 29);
        sha256->loLen = sha256->loLen << 3;
    #ifdef LITTLE_ENDIAN_ORDER
        sha256->buffer[14] = ByteReverseWord32(sha256->hiLen);
        sha256->buffer[15] = ByteReverseWord32(sha256->loLen);
    #else
        sha256->buffer[14] = sha256->hiLen;
        sha256->buffer[15] = sha256->loLen;
    #endif
        ret = wc_Sha256HashBlock(sha256, buffer, hash);
        sha256->buffLen = 0;
        sha256->hiLen = 0;
        sha256->loLen = 0;
    }

    return ret;
#else
    return wc_Sha256Final(sha256, hash);
#endif
}

/***************************************
 * LM-OTS APIs
 **************************************/

/* Expand Q to and array of Winternitz width bits values plus checksum.
 *
 * Supported Winternitz widths: 8, 4, 2, 1.
 *
 * Algorithm 2: Checksum Calculation
 *   sum = 0
 *   for ( i = 0; i < (n*8/w); i = i + 1 ) {
 *     sum = sum + (2^w - 1) - coef(S, i, w)
 *   }
 *   return (sum << ls)
 * Section 3.1.3: Strings of w-Bit Elements
 *   coef(S, i, w) = (2^w - 1) AND
 *                   ( byte(S, floor(i * w / 8)) >>
 *                     (8 - (w * (i % (8 / w)) + w)) )
 * Combine coefficient expansion with checksum calculation.
 *
 * @param [in]  q   Q array of bytes.
 * @param [in]  n   Number of bytes in Q.
 * @param [in]  w   Winternitz width in bits.
 * @param [in]  ls  Left shift of checksum.
 * @param [out] qe  Expanded Q with checksum.
 * @return  0 on success.
 * @return  BAD_FUNC_ARG when Winternitz width is not supported.
 */
static WC_INLINE int wc_lmots_q_expand(byte* q, word8 n, word8 w, word8 ls,
    byte* qe)
{
    int ret = 0;
    word16 sum;
    unsigned int i;

#ifndef WOLFSSL_WC_LMS_SMALL
    switch (w) {
        /* Winternitz width of 8. */
        case 8:
            /* No expansion required, just copy. */
            XMEMCPY(qe, q, n);
            /* Start sum with all 2^w - 1s and subtract from that. */
            sum = 0xff * n;
            /* For each byte of the hash. */
            for (i = 0; i < n; i++) {
                /* Subtract coefficient from sum. */
                sum -= q[i];
            }
            /* Put coefficients of checksum on the end. */
            qe[n + 0] = (word8)(sum >> 8);
            qe[n + 1] = (word8)(sum     );
            break;
        /* Winternitz width of 4. */
        case 4:
            sum = 2 * 0xf * n;
            /* For each byte of the hash. */
            for (i = 0; i < n; i++) {
                /* Get coefficient. */
                qe[0] = (q[i] >> 4)      ;
                qe[1] = (q[i]     ) & 0xf;
                /* Subtract coefficients from sum. */
                sum -= qe[0];
                sum -= qe[1];
                /* Move to next coefficients. */
                qe += 2;
            }
            /* Put coefficients of checksum on the end. */
            qe[0] = (word8)((sum >> 8) & 0xf);
            qe[1] = (word8)((sum >> 4) & 0xf);
            qe[2] = (word8)((sum     ) & 0xf);
            break;
        /* Winternitz width of 2. */
        case 2:
            sum = 4 * 0x3 * n;
            /* For each byte of the hash. */
            for (i = 0; i < n; i++) {
                /* Get coefficients. */
                qe[0] = (q[i] >> 4)      ;
                qe[0] = (q[i] >> 6)      ;
                qe[1] = (q[i] >> 4) & 0x3;
                qe[2] = (q[i] >> 2) & 0x3;
                qe[3] = (q[i]     ) & 0x3;
                /* Subtract coefficients from sum. */
                sum -= qe[0];
                sum -= qe[1];
                sum -= qe[2];
                sum -= qe[3];
                /* Move to next coefficients. */
                qe += 4;
            }
            /* Put coefficients of checksum on the end. */
            qe[0] = (word8)((sum >>  8) & 0x3);
            qe[1] = (word8)((sum >>  6) & 0x3);
            qe[2] = (word8)((sum >>  4) & 0x3);
            qe[3] = (word8)((sum >>  2) & 0x3);
            qe[4] = (word8)((sum      ) & 0x3);
            break;
        /* Winternitz width of 1. */
        case 1:
            sum = 8 * 0x01 * n;
            /* For each byte of the hash. */
            for (i = 0; i < n; i++) {
                /* Get coefficients. */
                qe[0] = (q[i] >> 4)      ;
                qe[0] = (q[i] >> 7)      ;
                qe[1] = (q[i] >> 6) & 0x1;
                qe[2] = (q[i] >> 5) & 0x1;
                qe[3] = (q[i] >> 4) & 0x1;
                qe[4] = (q[i] >> 3) & 0x1;
                qe[5] = (q[i] >> 2) & 0x1;
                qe[6] = (q[i] >> 1) & 0x1;
                qe[7] = (q[i]     ) & 0x1;
                /* Subtract coefficients from sum. */
                sum -= qe[0];
                sum -= qe[1];
                sum -= qe[2];
                sum -= qe[3];
                sum -= qe[4];
                sum -= qe[5];
                sum -= qe[6];
                sum -= qe[7];
                /* Move to next coefficients. */
                qe += 8;
            }
            /* Put coefficients of checksum on the end. */
            qe[0] = (word8)((sum >>  8)      );
            qe[1] = (word8)((sum >>  7) & 0x1);
            qe[2] = (word8)((sum >>  6) & 0x1);
            qe[3] = (word8)((sum >>  5) & 0x1);
            qe[4] = (word8)((sum >>  4) & 0x1);
            qe[5] = (word8)((sum >>  3) & 0x1);
            qe[6] = (word8)((sum >>  2) & 0x1);
            qe[7] = (word8)((sum >>  1) & 0x1);
            qe[8] = (word8)((sum      ) & 0x1);
            break;
        default:
            ret = BAD_FUNC_ARG;
            break;
    }

    (void)ls;
#else
    int j;

    if ((w != 8) && (w != 4) && (w != 2) && (w != 1)) {
        ret = BAD_FUNC_ARG;
    }

    if (ret == 0) {
        /* Start sum with all 2^w - 1s and subtract from that. */
        sum = ((1 << w) - 1) * ((n * 8) / w);
        /* For each byte of the hash. */
        for (i = 0; i < n; i++) {
            /* Get next byte. */
            byte a = *(q++);
            /* For each width bits of byte. */
            for (j = 8 - w; j >= 0; j -= w) {
                /* Get coefficient. */
                *qe = a >> (8 - w);
                /* Subtract coefficient from sum. */
                sum -= *qe;
                /* Move to next coefficient. */
                qe++;
                /* Remove width bits. */
                a <<= w;
            }
        }
        /* Shift sum up as required to pack it on the end of hash. */
        sum <<= ls;
        /* For each width buts of checksum. */
        for (j = 16 - w; j >= ls; j--) {
            /* Get coefficient. */
            *(qe++) = sum >> (16 - w);
            /* Remove width bits. */
            sum <<= w;
        }
    }
#endif /* !WOLFSSL_WC_LMS_SMALL */

    return ret;
}

/* Calculate the hash for the message.
 *
 * Algorithm 3: Generating a One-Time Signature From a Private Key and a
 * Message
 *   ...
 *   5. Compute the array y as follows:
 *      Q = H(I || u32str(q) || u16str(D_MESG) || C || message)
 * Algorithm 4b: Computing a Public Key Candidate Kc from a Signature,
 * Message, Signature Typecode pubtype, and Identifiers I, q
 *   ...
 *   3. Compute the string Kc as follows:
 *      Q = H(I || u32str(q) || u16str(D_MESG) || C || message)
 *
 * @param [in, out]  state  LMS state.
 * @param [in]       msg    Message to hash.
 * @param [in]       msgSz  Length of message in bytes.
 * @param [in]       c      C or randomizer value.
 * @param [out]      q      Computed Q value.
 * @return  0 on success.
 */
static int wc_lmots_msg_hash(LmsState* state, const byte* msg, word32 msgSz,
    const byte* c, byte* q)
{
    int ret;
    byte* buffer = state->buffer;
    byte* ip = buffer + LMS_I_LEN + LMS_Q_LEN;

    /* I || u32str(q) || u16str(D_MESG) */
    c16toa(LMS_D_MESG, ip);
    /* H(I || u32str(q) || u16str(D_MESG) || ...) */
    ret = wc_lms_hash_first(&state->hash, buffer, LMS_MSG_PRE_LEN);
    if (ret == 0) {
        /* H(... || C || ...) */
        ret = wc_lms_hash_update(&state->hash, c, LMS_MAX_NODE_LEN);
    }
    if (ret == 0) {
        /* H(... || message) */
        ret = wc_lms_hash_update(&state->hash, msg, msgSz);
    }
    if (ret == 0) {
        /* Q = H(...) */
        ret = wc_lms_hash_final(&state->hash, q);
    }

    return ret;
}

#ifndef WOLFSSL_LMS_VERIFY_ONLY
/* Compute array y, intermediates of public key calculation, for signature.
 *
 * Verification will perform the remaining iterations of hashing.
 *
 * Algorithm 3: Generating a One-Time Signature From a Private Key and a
 * Message
 *   ...
 *   5. Compute the array y as follows:
 *      Q = H(I || u32str(q) || u16str(D_MESG) || C || message)
 *      for ( i = 0; i < p; i = i + 1 ) {
 *        a = coef(Q || Cksm(Q), i, w)
 *        tmp = x[i]
 *        for ( j = 0; j < a; j = j + 1 ) {
 *          tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
 *        }
 *        y[i] = tmp
 *      }
 * x[i] can be calculated on the fly using psueodo key generation in Appendix A.
 * Appendix A, The elements of the LM-OTS private keys are computed as:
 *   x_q[i] = H(I || u32str(q) || u16str(i) || u8str(0xff) || SEED).
 *
 * @param [in, out]  state  LMS state.
 * @param [in]       seed   Seed to hash.
 * @param [in]       msg    Message to sign.
 * @param [in]       msgSZ  Length of message in bytes.
 * @param [in]       c      C or randomizer value to hash.
 * @param [out]      y      Calculated intermediate hashes.
 * @return  0 on success.
 */
static int wc_lmots_compute_y_from_seed(LmsState* state, const byte* seed,
    const byte* msg, word32 msgSz, const byte* c, byte* y)
{
    const LmsParams* params = state->params;
    int ret = 0;
    word16 i;
    byte q[LMS_MAX_NODE_LEN + LMS_CKSM_LEN];
#ifdef WOLFSSL_SMALL_STACK
    byte* a = state->a;
#else
    byte a[LMS_MAX_P];
#endif /* WOLFSSL_SMALL_STACK */
    byte* buffer = state->buffer;
    byte* ip = buffer + LMS_I_LEN + LMS_Q_LEN;
    byte* jp = ip + LMS_P_LEN;
    byte* tmp = jp + LMS_W_LEN;

    /* Q = H(I || u32str(q) || u16str(D_MESG) || C || message) */
    ret = wc_lmots_msg_hash(state, msg, msgSz, c, q);
    if (ret == 0) {
        /* Calculate checksum list all coefficients. */
        ret = wc_lmots_q_expand(q, LMS_MAX_NODE_LEN, params->width, params->ls,
             a);
    }
    #ifndef WC_LMS_FULL_HASH
    if (ret == 0) {
        /* Put in padding for final block. */
        LMS_SHA256_SET_LEN_55(buffer);
    }
    #endif /* !WC_LMS_FULL_HASH */

    /* Compute y for each coefficient. */
    for (i = 0; (ret == 0) && (i < params->p); i++) {
        unsigned int j;

        /* tmp = x[i]
         *     = H(I || u32str(q) || u16str(i) || u8str(0xff) || SEED). */
        c16toa(i, ip);
        *jp = LMS_D_FIXED;
        XMEMCPY(tmp, seed, LMS_SEED_LEN);
    #ifndef WC_LMS_FULL_HASH
        ret = wc_lms_hash_block(&state->hash, buffer, tmp);
    #else
        ret = wc_lms_hash(&state->hash, buffer, LMS_HASH_BUFFER_LEN, tmp);
    #endif /* !WC_LMS_FULL_HASH */

        /* Apply the hash function coefficient number of times. */
        for (j = 0; (ret == 0) && (j < a[i]); j++) {
            /* I || u32str(q) || u16str(i) || u8str(j) || tmp */
            *jp = j;
            /* tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) */
        #ifndef WC_LMS_FULL_HASH
            ret = wc_lms_hash_block(&state->hash, buffer, tmp);
        #else
            ret = wc_lms_hash(&state->hash, buffer, LMS_HASH_BUFFER_LEN, tmp);
        #endif /* !WC_LMS_FULL_HASH */
        }

        if (ret == 0) {
            /* y[i] = tmp */
            XMEMCPY(y, tmp, LMS_MAX_NODE_LEN);
            y += LMS_MAX_NODE_LEN;
        }
    }

    return ret;
}
#endif /* !WOLFSSL_LMS_VERIFY_ONLY */

/* Compute public key candidate K from signature.
 *
 * Signing performed the first coefficient number of iterations of hashing.
 *
 * Algorithm 4b: Computing a Public Key Candidate Kc from a Signature,
 * Message, Signature Typecode pubtype, and Identifiers I, q
 *   ...
 *   3. Compute the string Kc as follows:
 *      Q = H(I || u32str(q) || u16str(D_MESG) || C || message)
 *      for ( i = 0; i < p; i = i + 1 ) {
 *        a = coef(Q || Cksm(Q), i, w)
 *        tmp = y[i]
 *        for ( j = a; j < 2^w - 1; j = j + 1 ) {
 *          tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
 *        }
 *        z[i] = tmp
 *      }
 *      Kc = H(I || u32str(q) || u16str(D_PBLC) ||
 *                                    z[0] || z[1] || ... || z[p-1])
 *   4, Return Kc.
 *
 * @param [in, out] state  LMS state.
 * @param [in]      msg    Message to compute Kc for.
 * @param [in]      msgSz  Length of message in bytes.
 * @param [in]      c      C or randomizer value from signature.
 * @param [in]      sig_y  Part of signature containing array y.
 * @param [out]     kc     Kc or public key candidate K.
 * @return  0 on success.
 */
static int wc_lmots_compute_kc_from_sig(LmsState* state, const byte* msg,
    word32 msgSz, const byte* c, const byte* sig_y, byte* kc)
{
    const LmsParams* params = state->params;
    int ret;
    word16 i;
    byte q[LMS_MAX_NODE_LEN + LMS_CKSM_LEN];
#ifdef WOLFSSL_SMALL_STACK
    byte* a = state->a;
#else
    byte a[LMS_MAX_P];
#endif /* WOLFSSL_SMALL_STACK */
    byte* buffer = state->buffer;
    byte* ip = buffer + LMS_I_LEN + LMS_Q_LEN;
    byte* jp = ip + LMS_P_LEN;
    byte* tmp = jp + LMS_W_LEN;
    unsigned int max = ((unsigned int)1 << params->width) - 1;

    /* I || u32str(q) || u16str(D_PBLC). */
    c16toa(LMS_D_PBLC, ip);
    /* H(I || u32str(q) || u16str(D_PBLC) || ...). */
    ret = wc_lms_hash_first(&state->hash_k, buffer, LMS_K_PRE_LEN);
    if (ret == 0) {
        /* Q = H(I || u32str(q) || u16str(D_MESG) || C || message) */
        ret = wc_lmots_msg_hash(state, msg, msgSz, c, q);
    }
    if (ret == 0) {
        /* Calculate checksum list all coefficients. */
        ret = wc_lmots_q_expand(q, LMS_MAX_NODE_LEN, params->width, params->ls,
            a);
    }
    #ifndef WC_LMS_FULL_HASH
    if (ret == 0) {
        /* Put in padding for final block. */
        LMS_SHA256_SET_LEN_55(buffer);
    }
    #endif /* !WC_LMS_FULL_HASH */

    /* Compute z for each coefficient. */
    for (i = 0; (ret == 0) && (i < params->p); i++) {
        unsigned int j;

        /* I || u32(str) || u16str(i) || ... */
        c16toa(i, ip);

        /* tmp = y[i].
         * I || u32(str) || u16str(i) || ... || tmp */
        XMEMCPY(tmp, sig_y, LMS_MAX_NODE_LEN);
        sig_y += LMS_MAX_NODE_LEN;

        /* Finish iterations of hash from coefficient to max. */
        for (j = a[i]; (ret == 0) && (j < max); j++) {
            /* I || u32str(q) || u16str(i) || u8str(j) || tmp */
            *jp = (word8)j;
            /* tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) */
        #ifndef WC_LMS_FULL_HASH
            ret = wc_lms_hash_block(&state->hash, buffer, tmp);
        #else
            ret = wc_lms_hash(&state->hash, buffer, LMS_HASH_BUFFER_LEN, tmp);
        #endif /* !WC_LMS_FULL_HASH */
        }

        if (ret == 0) {
            /* H(... || z[i] || ...) (for calculating Kc). */
            ret = wc_lms_hash_update(&state->hash_k, tmp, LMS_MAX_NODE_LEN);
        }
    }

    if (ret == 0) {
        /* Kc = H(...) */
        ret = wc_lms_hash_final(&state->hash_k, kc);
    }

    return ret;
}

#ifndef WOLFSSL_LMS_VERIFY_ONLY
/* Generate LM-OTS public key.
 *
 * Caller set: state->buffer = I || u32str(q)
 *
 * Algorithm 1: Generating a One-Time Signature Public Key From a Private Key
 *   ...
 *   4. Compute the string K as follows:
 *      for ( i = 0; i < p; i = i + 1 ) {
 *        tmp = x[i]
 *        for ( j = 0; j < 2^w - 1; j = j + 1 ) {
 *          tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
 *        }
 *        y[i] = tmp
 *      }
 *      K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1])
 *   ...
 * x[i] can be calculated on the fly using psueodo key generation in Appendix A.
 * Appendix A, The elements of the LM-OTS private keys are computed as:
 *   x_q[i] = H(I || u32str(q) || u16str(i) || u8str(0xff) || SEED).
 *
 * @param [in, out]  state   LMS state.
 * @param [in]       seed    Seed to hash.
 * @param [out]      k       K, the public key hash, or OTS_PUB_HASH
 */
static int wc_lmots_make_public_hash(LmsState* state, const byte* seed, byte* k)
{
    const LmsParams* params = state->params;
    int ret;
    word16 i;
    byte* buffer = state->buffer;
    byte* ip = buffer + LMS_I_LEN + LMS_Q_LEN;
    byte* jp = ip + LMS_P_LEN;
    byte* tmp = jp + LMS_W_LEN;
    unsigned int max = ((unsigned int)1 << params->width) - 1;

    /* I || u32str(q) || u16str(D_PBLC). */
    c16toa(LMS_D_PBLC, ip);
    /* K = H(I || u32str(q) || u16str(D_PBLC) || ...) */
    ret = wc_lms_hash_first(&state->hash_k, buffer, LMS_K_PRE_LEN);

#ifndef WC_LMS_FULL_HASH
    /* Put in padding for final block. */
    LMS_SHA256_SET_LEN_55(buffer);
#endif /* !WC_LMS_FULL_HASH */

    for (i = 0; (ret == 0) && (i < params->p); i++) {
        unsigned int j;

        /* tmp = x[i]
         *     = H(I || u32str(q) || u16str(i) || u8str(0xff) || SEED). */
        c16toa(i, ip);
        *jp = LMS_D_FIXED;
        XMEMCPY(tmp, seed, LMS_SEED_LEN);
    #ifndef WC_LMS_FULL_HASH
        ret = wc_lms_hash_block(&state->hash, buffer, tmp);
    #else
        ret = wc_lms_hash(&state->hash, buffer, LMS_HASH_BUFFER_LEN, tmp);
    #endif /* !WC_LMS_FULL_HASH */
        /* Do all iterations to calculate y. */
        for (j = 0; (ret == 0) && (j < max); j++) {
            /* I || u32str(q) || u16str(i) || u8str(j) || tmp */
            *jp = (word8)j;
            /* tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) */
        #ifndef WC_LMS_FULL_HASH
            ret = wc_lms_hash_block(&state->hash, buffer, tmp);
        #else
            ret = wc_lms_hash(&state->hash, buffer, LMS_HASH_BUFFER_LEN, tmp);
        #endif /* !WC_LMS_FULL_HASH */
        }
        if (ret == 0) {
            /* K = H(... || y[i] || ...) */
            ret = wc_lms_hash_update(&state->hash_k, tmp, LMS_MAX_NODE_LEN);
        }
    }
    if (ret == 0) {
        /* K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1]) */
        ret = wc_lms_hash_final(&state->hash_k, k);
    }

    return ret;
}

/* Encode the LM-OTS public key.
 *
 * Encoded into public key and signature if more than one level.
 * T[1] is already in place. Putting in: type, ostype and I.
 *
 * Section 4.3:
 *   u32str(type) || u32str(otstype) || I || T[1]
 *
 * @param [in]  params  LMS parameters.
 * @param [in]  priv    LMS private ley.
 * @param [out] pub     LMS public key.
 */
static void wc_lmots_public_key_encode(const LmsParams* params,
    const byte* priv, byte* pub)
{
    const byte* priv_i = priv + LMS_Q_LEN + LMS_SEED_LEN;

    /* u32str(type) || ... || T(1) */
    c32toa(params->lmsType, pub);
    pub += 4;
    /* u32str(type) || u32str(otstype) || ... || T(1) */
    c32toa(params->lmOtsType, pub);
    pub += 4;
    /* u32str(type) || u32str(otstype) || I || T(1) */
    XMEMCPY(pub, priv_i, LMS_I_LEN);
}
#endif /* !WOLFSSL_LMS_VERIFY_ONLY */

/* Check the public key matches the parameters.
 *
 * @param [in] params  LMS parameters.
 * @param [in] pub     Public key.
 * @return  0 on success.
 * @return  PUBLIC_KEY_E when LMS or LM-OTS type doesn't match.
 */
static int wc_lmots_public_key_check(const LmsParams* params, const byte* pub)
{
    int ret = 0;
    word32 type;

    /* Get message hash and height type. */
    ato32(pub, &type);
    pub += 4;
    /* Compare with parameters. */
    if (type != params->lmsType) {
        ret = PUBLIC_KEY_E;
    }
    if (ret == 0) {
        /* Get node hash and Winternitz width type. */
        ato32(pub, &type);
        /* Compare with parameters. */
        if (type != params->lmOtsType) {
            ret = PUBLIC_KEY_E;
        }
    }

    return ret;
}

/* Calculate public key candidate K from signature.
 *
 * Algorithm 4b: Computing a Public Key Candidate Kc from a Signature,
 * Message, Signature Typecode pubtype, and Identifiers I, q
 *   ...
 *   2. Parse sigtype, C, and y from the signature as follows:
 *      a. sigtype = strTou32(first 4 bytes of signature)
 *      b. If sigtype is not equal to pubtype, return INVALID.
 *      ...
 *      d. C = next n bytes of signature
 *      e.   y[0] = next n bytes of signature
 *           y[1] = next n bytes of signature
 *           ...
 *         y[p-1] = next n bytes of signature
 *   3. Compute the string Kc as follows:
 *   ...
 *
 * @param [in, out] state  LMS state.
 * @param [in]      pub    LMS public key.
 * @param [in]      msg    Message/next private key to verify.
 * @param [in]      msgSz  Length of message in bytes.
 * @param [in]      sig    Signature including type, C and y[0..p-1].
 * @param [out]     kc     Public key candidate Kc.
 */
static int wc_lmots_calc_kc(LmsState* state, const byte* pub, const byte* msg,
    word32 msgSz, const byte* sig, byte* kc)
{
    int ret = 0;

    /* Check signature type. */
    if (XMEMCMP(pub, sig, LMS_TYPE_LEN) != 0) {
        ret = SIG_TYPE_E;
    }
    if (ret == 0) {
        /* Get C or randomizer value from signature. */
        const byte* c = sig + LMS_TYPE_LEN;
        /* Get array y from signature. */
        const byte* y = c + LMS_MAX_NODE_LEN;

        /* Compute the public key candidate Kc from the signature. */
        ret = wc_lmots_compute_kc_from_sig(state, msg, msgSz, c, y, kc);
    }

    return ret;
}

#ifndef WOLFSSL_LMS_VERIFY_ONLY
/* Generate LM-OTS private key.
 *
 * Algorithm 5: Computing an LMS Private Key
 * But use Appendix A to generate x on the fly.
 *   PRIV = SEED | I
 *
 * @param [in]  rng     Random number generator.
 * @param [out] priv    Private key data.
 */
static int wc_lmots_make_private_key(WC_RNG* rng, byte* priv)
{
    return wc_RNG_GenerateBlock(rng, priv, LMS_SEED_LEN + LMS_I_LEN);
}

/* Generate LM-OTS signature.
 *
 * Algorithm 3: Generating a One-Time Signature From a Private Key and a
 * Message
 *   ...
 *   4. Set C to a uniformly random n-byte string
 *   5. Compute the array y as follows:
 *      ...
 *   6. Return u32str(type) || C || y[0] || ... || y[p-1]
 *
 * @param [in, out] state  LMS state.
 * @param [in]      seed   Private key seed.
 * @param [in]      msg    Message to be signed.
 * @param [in]      msgSz  Length of message in bytes.
 * @param [out]     sig    Signature buffer.
 * @return  0 on success.
 */
static int wc_lmots_sign(LmsState* state, const byte* seed, const byte* msg,
    word32 msgSz, byte* sig)
{
    int ret;
    byte* buffer = state->buffer;
    byte* ip = buffer + LMS_I_LEN + LMS_Q_LEN;
    byte* jp = ip + LMS_P_LEN;
    byte* tmp = jp + LMS_W_LEN;
    byte* sig_c = sig;

    /* I || u32str(q) || u16str(0xFFFD) || ... */
    c16toa(LMS_D_C, ip);
    /* I || u32str(q) || u16str(0xFFFD) || u8str(0xFF) || ... */
    *jp = LMS_D_FIXED;
    /* I || u32str(q) || u16str(0xFFFD) || u8str(0xFF) || SEED */
    XMEMCPY(tmp, seed, LMS_SEED_LEN);
    /* C = H(I || u32str(q) || u16str(0xFFFD) || u8str(0xFF) || SEED)
     * sig = u32str(type) || C || ... */
#ifndef WC_LMS_FULL_HASH
    /* Put in padding for final block. */
    LMS_SHA256_SET_LEN_55(buffer);
    ret = wc_lms_hash_block(&state->hash, buffer, sig_c);
#else
    ret = wc_lms_hash(&state->hash, buffer, LMS_HASH_BUFFER_LEN, sig_c);
#endif /* !WC_LMS_FULL_HASH */

    if (ret == 0) {
        byte* sig_y = sig_c + LMS_MAX_NODE_LEN;

        /* Compute array y.
         * sig = u32str(type) || C || y[0] || ... || y[p-1] */
        ret = wc_lmots_compute_y_from_seed(state, seed, msg, msgSz, sig_c,
            sig_y);
    }

    return ret;
}
#endif /* WOLFSSL_LMS_VERIFY_ONLY */

/***************************************
 * LMS APIs
 **************************************/

#ifndef WOLFSSL_LMS_VERIFY_ONLY
#ifndef WOLFSSL_WC_LMS_SMALL
/* Load the LMS private state from data.
 *
 * @param [in]  params     LMS parameters.
 * @param [out] state      Private key state.
 * @param [in]  priv_data  Private key data.
 */
static void wc_lms_priv_state_load(const LmsParams* params, LmsPrivState* state,
    byte* priv_data)
{
    /* Authentication path data. */
    state->auth_path = priv_data;
    priv_data += params->height * LMS_MAX_NODE_LEN;

    /* Stack of nodes. */
    state->stack.stack = priv_data;
    priv_data += (params->height + 1) * LMS_MAX_NODE_LEN;
    ato32(priv_data, &state->stack.offset);
    priv_data += 4;

    /* Cached root nodes. */
    state->root = priv_data;
    priv_data += LMS_ROOT_CACHE_LEN(params->rootLevels);

    /* Cached leaf nodes. */
    state->leaf.cache = priv_data;
    priv_data += LMS_LEAF_CACHE_LEN(params->cacheBits);
    ato32(priv_data, &state->leaf.idx);
    priv_data += 4;
    ato32(priv_data, &state->leaf.offset);
    /* priv_data += 4; */
}

/* Store the LMS private state into data.
 *
 * @param [in]      params     LMS parameters.
 * @param [in]      state      Private key state.
 * @param [in, out] priv_data  Private key data.
 */
static void wc_lms_priv_state_store(const LmsParams* params,
    LmsPrivState* state, byte* priv_data)
{
    /* Authentication path data. */
    priv_data += params->height * LMS_MAX_NODE_LEN;

    /* Stack of nodes. */
    priv_data += (params->height + 1) * LMS_MAX_NODE_LEN;
    c32toa(state->stack.offset, priv_data);
    priv_data += 4;

    /* Cached root nodes. */
    priv_data += LMS_ROOT_CACHE_LEN(params->rootLevels);

    /* Cached leaf nodes. */
    priv_data += LMS_LEAF_CACHE_LEN(params->cacheBits);
    c32toa(state->leaf.idx, priv_data);
    priv_data += 4;
    c32toa(state->leaf.offset, priv_data);
    /* priv_data += 4; */
}

#ifndef WOLFSSL_LMS_NO_SIGN_SMOOTHING
/* Copy LMS private key state.
 *
 * @param [in]  params  LMS parameters.
 * @param [out] dst     LMS private state destination.
 * @param [in]  src     LMS private state source.
 */
static void wc_lms_priv_state_copy(const LmsParams* params,
    LmsPrivState* dst, const LmsPrivState* src)
{
    XMEMCPY(dst->auth_path, src->auth_path, LMS_PRIV_STATE_LEN(params->height,
        params->rootLevels, params->cacheBits));
    dst->stack.offset = src->stack.offset;
    dst->leaf.idx = src->leaf.idx;
    dst->leaf.offset = src->leaf.offset;
}
#endif /* !WOLFSSL_LMS_NO_SIGN_SMOOTHING */
#endif /* !WOLFSSL_WC_LMS_SMALL */

/* Calculate the leaf node hash.
 *
 * Assumes buffer already contains : I
 *
 * Appendix C.
 *   ...
 *     temp = H(I || u32str(r)|| u16str(D_LEAF) || OTS_PUB_HASH[i])
 *   ...
 * Section 5.3. LMS Public Key
 *                                        ... where we denote the public
 *   key final hash value (namely, the K value computed in Algorithm 1)
 *   associated with the i-th LM-OTS private key as OTS_PUB_HASH[i], ...
 * Algorithm 1: Generating a One-Time Signature Public Key From a
 * Private Key
 *   ...
 *   K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1])
 *   ...
 * Therefore:
 *   OTS_PUB_HASH[i] = H(I || u32str(i) || u16str(D_PBLC) ||
 *                       y[0] || ... || y[p-1])
 *
 * @param [in, out] state  LMS state.
 * @param [in]      seed   Private seed to generate x.
 * @param [in]      i      Index of leaf.
 * @param [in]      r      Leaf hash index.
 * @param [out]     leaf   Leaf node hash.
 */
static int wc_lms_leaf_hash(LmsState* state, const byte* seed, word32 i,
    word32 r, byte* leaf)
{
    int ret;
    byte* buffer = state->buffer;
    byte* rp = buffer + LMS_I_LEN;
    byte* dp = rp + LMS_R_LEN;
    byte* ots_pub_hash = dp + LMS_D_LEN;

    /* I || u32str(i) || ... */
    c32toa(i, rp);
    /* OTS_PUB_HASH[i] = H(I || u32str(i) || u16str(D_PBLC) ||
     *                     y[0] || ... || y[p-1])
     */
    ret = wc_lmots_make_public_hash(state, seed, ots_pub_hash);
    if (ret == 0) {
        /* I || u32str(r) || ... || OTS_PUB_HASH[i] */
        c32toa(r, rp);
        /* I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[i] */
        c16toa(LMS_D_LEAF, dp);
        /* temp = H(I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[i]) */
    #ifndef WC_LMS_FULL_HASH
        /* Put in padding for final block. */
        LMS_SHA256_SET_LEN_54(buffer);
        ret = wc_lms_hash_block(&state->hash, buffer, leaf);
    #else
        ret = wc_lms_hash(&state->hash, buffer, LMS_SEED_HASH_LEN, leaf);
    #endif /* !WC_LMS_FULL_HASH */
    }

    return ret;
}

/* Calculate interior node hash.
 *
 * Appendix C. n Iterative Algorithm for Computing an LMS Public Key
 * Generating an LMS Public Key from an LMS Private Key
 *   ...
 *   left_side = pop(data stack);
 *   temp = H(I || u32str(r) || u16str(D_INTR) || left_side || temp)
 *   ...
 * Popping the stack is done in the caller.
 *
 * @param [in, out] state  LMS state.
 * @param [in]      sp     Stack pointer to left nodes.
 * @param [in]      r      Node hash index.
 * @param [out]     node   Interior node hash.
 */
static int wc_lms_interior_hash(LmsState* state, byte* sp, word32 r,
    byte* node)
{
    byte* buffer = state->buffer;
    byte* rp = buffer + LMS_I_LEN;
    byte* left = rp + LMS_R_LEN + LMS_D_LEN;

    /* I || u32str(r) || u16str(D_INTR) || ... || temp */
    c32toa(r, rp);
    /* left_side = pop(data stack)
     * I || u32str(r) || u16str(D_INTR) || left_side || temp */
    XMEMCPY(left, sp, LMS_MAX_NODE_LEN);
    /* temp = H(I || u32str(r) || u16str(D_INTR) || left_side || temp) */
    return wc_lms_hash(&state->hash, buffer, LMS_NODE_HASH_LEN, node);
}

#ifdef WOLFSSL_WC_LMS_SMALL
/* Computes hash of the Merkle tree and gets the authentication path for q.
 *
 * Appendix C: An Iterative Algorithm for Computing an LMS Public Key
 *    for ( i = 0; i < 2^h; i = i + 1 ) {
 *      r = i + num_lmots_keys;
 *      temp = H(I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[i])
 *      j = i;
 *      while (j % 2 == 1) {
 *        r = (r - 1)/2;
 *        j = (j-1) / 2;
 *        left_side = pop(data stack);
 *        temp = H(I || u32str(r) || u16str(D_INTR) || left_side || temp)
 *      }
 *      push temp onto the data stack
 *   }
 *   public_key = pop(data stack)
 *
 * @param [in, out] state      LMS state.
 * @param [in]      id         Unique tree identifier, I.
 * @param [in]      seed       Private seed to generate x.
 * @param [in]      max        Count of leaf nodes to calculate. Must be greater
 *                             than q. Must be a power of 2.
 * @param [in]      q          Index for authentication path.
 * @param [out]     auth_path  Authentication path for index.
 * @param [out]     pub        LMS public key.
 * @param [out]     stack_d    Where to store stack data.
 * @return  0 on success.
 */
static int wc_lms_treehash(LmsState* state, const byte* id, const byte* seed,
    word32 q, byte* auth_path, byte* pub)
{
    int ret = 0;
    const LmsParams* params = state->params;
    byte* buffer = state->buffer;
    byte* rp = buffer + LMS_I_LEN;
    byte* dp = rp + LMS_R_LEN;
    byte* left = dp + LMS_D_LEN;
    byte* temp = left + LMS_MAX_NODE_LEN;
#ifdef WOLFSSL_SMALL_STACK
    byte* stack = NULL;
#else
    byte stack[(LMS_MAX_HEIGHT + 1) * LMS_MAX_NODE_LEN];
#endif /* WOLFSSL_SMALL_STACK */
    byte* sp;
    word32 i;

    /* I || ... */
    XMEMCPY(buffer, id, LMS_I_LEN);

#ifdef WOLFSSL_SMALL_STACK
    /* Allocate stack of left side hashes. */
    stack = XMALLOC((params->height + 1) * LMS_MAX_NODE_LEN, NULL,
        DYNAMIC_TYPE_TMP_BUFFER);
    if (stack == NULL) {
        ret = MEMORY_E;
    }
#endif /* WOLFSSL_SMALL_STACK */
    sp = stack;

    /* Compute all nodes requested. */
    for (i = 0; (ret == 0) && (i < ((word32)1 << params->height)); i++) {
        word32 j = i;
        word16 h = 0;
        /* r = i + num_lmots_keys */
        word32 r = i + ((word32)1 << (params->height));

        /* Calculate leaf node hash. */
        ret = wc_lms_leaf_hash(state, seed, i, r, temp);

        /* Store the node if on the authentication path. */
        if ((ret == 0) && (auth_path != NULL) && ((q ^ 0x1) == i)) {
            XMEMCPY(auth_path, temp, LMS_MAX_NODE_LEN);
        }

        /* I || ... || u16str(D_INTR) || ... || temp */
        c16toa(LMS_D_INTR, dp);
        /* Calculate parent node is we have both left and right. */
        while ((ret == 0) && ((j & 0x1) == 1)) {
            /* Get parent node index. r and j are odd. */
            r >>= 1;
            j >>= 1;
            h++;

            /* Calculate interior node hash.
             * temp = H(I || u32str(r) || u16str(D_INTR) || left_side || temp)
             */
            sp -= LMS_MAX_NODE_LEN;
            ret = wc_lms_interior_hash(state, sp, r, temp);

            /* Copy out node to authentication path if on path. */
            if ((ret == 0) && (auth_path != NULL) && ((q >> h) ^ 0x1) == j) {
                XMEMCPY(auth_path + h * LMS_MAX_NODE_LEN, temp,
                    LMS_MAX_NODE_LEN);
            }
        }
        /* Push temp onto the data stack. */
        XMEMCPY(sp, temp, LMS_MAX_NODE_LEN);
        sp += LMS_MAX_NODE_LEN;
    }

    if ((ret == 0) && (pub != NULL)) {
        /* Public key, root node, is top of data stack. */
        XMEMCPY(pub, stack, LMS_MAX_NODE_LEN);
    }
#ifdef WOLFSSL_SMALL_STACK
    XFREE(stack, NULL, DYNAMIC_TYPE_TMP_BUFFER);
#endif /* WOLFSSL_SMALL_STACK */
    return ret;
}

/* Compute the LMS public key - root node of tree.
 *
 * @param [in, out] state  LMS state.
 * @param [in]      id     Unique tree identifier, I.
 * @param [in]      seed   Private seed to generate x.
 * @param [out]     pub    LMS public key.
 * @return  0 on success.
 */
static int wc_lms_make_public_key(LmsState* state, const byte* id,
    const byte* seed, byte* pub)
{
    return wc_lms_treehash(state, id, seed, 0, NULL, pub);
}

/* Calculate the authentication path.
 *
 * @param [in, out] state  LMS state.
 * @param [in]      id     Public random: I.
 * @param [in]      seed   Private random: SEED.
 * @param [in]      q      Index of leaf.
 * @param [out]     sig    Signature buffer to place authentication path into.
 * @param [out]     root   Root node of tree.
 * @return  0 on success.
 */
static int wc_lms_auth_path(LmsState* state, const byte* id, const byte* seed,
    word32 q, byte* sig, byte* root)
{
    return wc_lms_treehash(state, id, seed, q, sig, root);
}
#else
/* Computes hash of the Merkle tree and gets the authentication path for q.
 *
 * Appendix C: An Iterative Algorithm for Computing an LMS Public Key
 *    for ( i = 0; i < 2^h; i = i + 1 ) {
 *      r = i + num_lmots_keys;
 *      temp = H(I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[i])
 *      j = i;
 *      while (j % 2 == 1) {
 *        r = (r - 1)/2;
 *        j = (j-1) / 2;
 *        left_side = pop(data stack);
 *        temp = H(I || u32str(r) || u16str(D_INTR) || left_side || temp)
 *      }
 *      push temp onto the data stack
 *   }
 *   public_key = pop(data stack)
 *
 * @param [in, out] state      LMS state.
 * @param [in, out] privState  LMS state of the private key.
 * @param [in]      id         Unique tree identifier, I.
 * @param [in]      seed       Private seed to generate x.
 * @param [in]      q          Index for authentication path.
 * @return  0 on success.
 */
static int wc_lms_treehash_init(LmsState* state, LmsPrivState* privState,
    const byte* id, const byte* seed, word32 q)
{
    int ret = 0;
    const LmsParams* params = state->params;
    byte* buffer = state->buffer;
    byte* auth_path = privState->auth_path;
    byte* root = privState->root;
    HssLeafCache* leaf = &privState->leaf;
    byte* rp = buffer + LMS_I_LEN;
    byte* dp = rp + LMS_R_LEN;
    byte* left = dp + LMS_D_LEN;
    byte* temp = left + LMS_MAX_NODE_LEN;
#ifdef WOLFSSL_SMALL_STACK
    byte* stack = NULL;
#else
    byte stack[(LMS_MAX_HEIGHT + 1) * LMS_MAX_NODE_LEN];
#endif /* WOLFSSL_SMALL_STACK */
    word32 spi = 0;
    word32 i;
    word32 max_h = (word32)1 << params->height;
    word32 max_cb = (word32)1 << params->cacheBits;

    privState->stack.offset = 0;
    /* Reset the cached stack. */
    leaf->offset = 0;
    leaf->idx = q;
    if ((q + max_cb) > max_h) {
        leaf->idx = max_h - max_cb;
    }

    /* I || ... */
    XMEMCPY(buffer, id, LMS_I_LEN);

#ifdef WOLFSSL_SMALL_STACK
    /* Allocate stack of left side hashes. */
    stack = XMALLOC((params->height + 1) * LMS_MAX_NODE_LEN, NULL,
        DYNAMIC_TYPE_TMP_BUFFER);
    if (stack == NULL) {
        ret = MEMORY_E;
    }
#endif /* WOLFSSL_SMALL_STACK */

    /* Compute all nodes requested. */
    for (i = 0; (ret == 0) && (i < max_h); i++) {
        word32 j = i;
        word16 h = 0;
        /* r = i + num_lmots_keys */
        word32 r = i + max_h;

        /* Calculate leaf node hash. */
        ret = wc_lms_leaf_hash(state, seed, i, r, temp);

        /* Cache leaf node if in range. */
        if ((ret == 0) && (i >= leaf->idx) && (i < leaf->idx + max_cb)) {
            XMEMCPY(leaf->cache + i * LMS_MAX_NODE_LEN, temp, LMS_MAX_NODE_LEN);
        }

        /* Store the node if on the authentication path. */
        if ((ret == 0) && (auth_path != NULL) && ((q ^ 0x1) == i)) {
            XMEMCPY(auth_path, temp, LMS_MAX_NODE_LEN);
        }

        /* I || ... || u16str(D_INTR) || ... || temp */
        c16toa(LMS_D_INTR, dp);
        /* Calculate parent node is we have both left and right. */
        while ((ret == 0) && ((j & 0x1) == 1)) {
            /* Get parent node index. r and j are odd. */
            r >>= 1;
            j >>= 1;
            h++;

            /* Calculate interior node hash.
             * temp = H(I || u32str(r) || u16str(D_INTR) || left_side || temp)
             */
            spi -= LMS_MAX_NODE_LEN;
            ret = wc_lms_interior_hash(state, stack + spi, r, temp);

            /* Copy out top root nodes. */
            if ((h > params->height - params->rootLevels) &&
                    ((i >> (h-1)) != ((i + 1) >> (h - 1)))) {
                int off = (1 << (params->height - h)) + (i >> h) - 1;
                XMEMCPY(root + off * LMS_MAX_NODE_LEN, temp, LMS_MAX_NODE_LEN);
            }

            /* Copy out node to authentication path if on path. */
            if ((ret == 0) && (auth_path != NULL) && ((q >> h) ^ 0x1) == j) {
                XMEMCPY(auth_path + h * LMS_MAX_NODE_LEN, temp,
                    LMS_MAX_NODE_LEN);
            }
        }
        /* Push temp onto the data stack. */
        XMEMCPY(stack + spi, temp, LMS_MAX_NODE_LEN);
        spi += LMS_MAX_NODE_LEN;

        if (i == q - 1) {
            XMEMCPY(privState->stack.stack, stack, spi);
            privState->stack.offset = spi;
        }
    }

#ifdef WOLFSSL_SMALL_STACK
    XFREE(stack, NULL, DYNAMIC_TYPE_TMP_BUFFER);
#endif /* WOLFSSL_SMALL_STACK */
    return ret;
}

/* Computes hash of the Merkle tree and gets the authentication path for q.
 *
 * Appendix C: An Iterative Algorithm for Computing an LMS Public Key
 *    for ( i = 0; i < 2^h; i = i + 1 ) {
 *      r = i + num_lmots_keys;
 *      temp = H(I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[i])
 *      j = i;
 *      while (j % 2 == 1) {
 *        r = (r - 1)/2;
 *        j = (j-1) / 2;
 *        left_side = pop(data stack);
 *        temp = H(I || u32str(r) || u16str(D_INTR) || left_side || temp)
 *      }
 *      push temp onto the data stack
 *   }
 *   public_key = pop(data stack)
 *
 * @param [in, out] state       LMS state.
 * @param [in, out] privState   LMS state of the private key.
 * @param [in]      id          Unique tree identifier, I.
 * @param [in]      seed        Private seed to generate x.
 * @param [in]      min_idx     Minimum leaf index to process.
 * @param [in]      max_idx     Maximum leaf index to process.
 * @param [in]      q           Index for authentication path.
 * @param [in]      useRoot     Whether to use nodes from root cache.
 * @return  0 on success.
 */
static int wc_lms_treehash_update(LmsState* state, LmsPrivState* privState,
    const byte* id, const byte* seed, word32 min_idx, word32 max_idx, word32 q,
    int useRoot)
{
    int ret = 0;
    const LmsParams* params = state->params;
    byte* buffer = state->buffer;
    byte* auth_path = privState->auth_path;
    LmsStack* stackCache = &privState->stack;
    HssLeafCache* leaf = &privState->leaf;
    byte* rp = buffer + LMS_I_LEN;
    byte* dp = rp + LMS_R_LEN;
    byte* left = dp + LMS_D_LEN;
    byte* temp = left + LMS_MAX_NODE_LEN;
#ifdef WOLFSSL_SMALL_STACK
    byte* stack = NULL;
#else
    byte stack[(LMS_MAX_HEIGHT + 1) * LMS_MAX_NODE_LEN];
#endif /* WOLFSSL_SMALL_STACK */
    byte* sp;
    word32 max_cb = (word32)1 << params->cacheBits;
    word32 i;

    /* I || ... */
    XMEMCPY(buffer, id, LMS_I_LEN);

#ifdef WOLFSSL_SMALL_STACK
    /* Allocate stack of left side hashes. */
    stack = XMALLOC((params->height + 1) * LMS_MAX_NODE_LEN, NULL,
        DYNAMIC_TYPE_TMP_BUFFER);
    if (stack == NULL) {
        ret = MEMORY_E;
    }
#endif /* WOLFSSL_SMALL_STACK */

    /* Public key, root node, is top of data stack. */
    XMEMCPY(stack, stackCache->stack, params->height * LMS_MAX_NODE_LEN);
    sp = stack + stackCache->offset;

    /* Compute all nodes requested. */
    for (i = min_idx; (ret == 0) && (i <= max_idx); i++) {
        word32 j = i;
        word16 h = 0;
        /* r = i + num_lmots_keys */
        word32 r = i + ((word32)1 << (params->height));

        if ((i >= leaf->idx) && (i < leaf->idx + max_cb)) {
            /* Calculate offset of node in cache. */
            word32 off = ((i - (leaf->idx + max_cb) + leaf->offset) % max_cb) *
                LMS_MAX_NODE_LEN;
            /* Copy cached node into working buffer. */
            XMEMCPY(temp, leaf->cache + off, LMS_MAX_NODE_LEN);
            /* I || u32str(i) || ... */
            c32toa(i, rp);
        }
        else {
            /* Calculate leaf node hash. */
            ret = wc_lms_leaf_hash(state, seed, i, r, temp);

            /* Check if this is at the end of the cache and not beyond q plus
             * the number of leaf nodes. */
            if ((i == leaf->idx + max_cb) && (i < (q + max_cb))) {
                /* Copy working node into cache over old first node. */
                XMEMCPY(leaf->cache + leaf->offset * LMS_MAX_NODE_LEN, temp,
                    LMS_MAX_NODE_LEN);
                /* Increase start index as first node replaced. */
                leaf->idx++;
                /* Update offset of first leaf node. */
                leaf->offset = (leaf->offset + 1) & (max_cb - 1);
            }
        }

        /* Store the node if on the authentication path. */
        if ((ret == 0) && ((q ^ 0x1) == i)) {
            XMEMCPY(auth_path, temp, LMS_MAX_NODE_LEN);
        }

        /* I || ... || u16str(D_INTR) || ... || temp */
        c16toa(LMS_D_INTR, dp);
        /* Calculate parent node if we have both left and right. */
        while ((ret == 0) && ((j & 0x1) == 1)) {
            /* Get parent node index. r and j are odd. */
            r >>= 1;
            j >>= 1;
            h++;

            sp -= LMS_MAX_NODE_LEN;
            if (useRoot && (h > params->height - params->rootLevels) &&
                    (h <= params->height)) {
                /* Calculate offset of cached root node. */
                word32 off = ((word32)1U << (params->height - h)) +
                    (i >> h) - 1;
                XMEMCPY(temp, privState->root + (off * LMS_MAX_NODE_LEN),
                    LMS_MAX_NODE_LEN);
            }
            else {
                /* Calculate interior node hash.
                 * temp = H(I || u32str(r) || u16str(D_INTR) || left_side ||
                 *          temp)
                 */
                ret = wc_lms_interior_hash(state, sp, r, temp);
            }

            /* Copy out top root nodes. */
            if ((ret == 0) && (q == 0) && (!useRoot) &&
                    (h > params->height - params->rootLevels) &&
                    ((i >> (h-1)) != ((i + 1) >> (h - 1)))) {
                int off = (1 << (params->height - h)) + (i >> h) - 1;
                XMEMCPY(privState->root + off * LMS_MAX_NODE_LEN, temp,
                    LMS_MAX_NODE_LEN);
            }

            /* Copy out node to authentication path if on path. */
            if ((ret == 0) && (((q >> h) ^ 0x1) == j)) {
                XMEMCPY(auth_path + h * LMS_MAX_NODE_LEN, temp,
                    LMS_MAX_NODE_LEN);
            }
        }
        if (ret == 0) {
            /* Push temp onto the data stack. */
            XMEMCPY(sp, temp, LMS_MAX_NODE_LEN);
            sp += LMS_MAX_NODE_LEN;

            /* Save stack after updating first node. */
            if (i == min_idx) {
                /* Copy stack back. */
                stackCache->offset = (word32)((size_t)sp - (size_t)stack);
                XMEMCPY(stackCache->stack, stack, stackCache->offset);
            }
        }
    }

    if (!useRoot) {
        /* Copy stack back. */
        XMEMCPY(stackCache->stack, stack, params->height * LMS_MAX_NODE_LEN);
        stackCache->offset = (word32)((size_t)sp - (size_t)stack);
    }

#ifdef WOLFSSL_SMALL_STACK
    XFREE(stack, NULL, DYNAMIC_TYPE_TMP_BUFFER);
#endif /* WOLFSSL_SMALL_STACK */
    return ret;
}
#endif /* WOLFSSL_WC_LMS_SMALL */

/* Sign message using LMS.
 *
 * Appendix D. Method for Deriving Authentication Path for a Signature.
 * Generating an LMS Signature
 *   ...
 *   3. Create the LM-OTS signature for the message:
 *      ots_signature = lmots_sign(message, LMS_PRIV[q])
 *   4. Compute the array path as follows:
 *      ...
 *   5. S = u32str(q) || ots_signature || u32str(type) ||
 *                           path[0] || path[1] || ... || path[h-1]
 *   ...
 * path[] added by caller as it can come from cache.
 *
 * @param [in, out] state  LMS state.
 * @param [in]      priv   LMS private key.
 * @param [in]      msg    Message/public key to sign.
 * @param [in]      msgSz  Length of message in bytes.
 * @param [out]     sig    LMS signature.
 * @return  0 on success.
 */
static int wc_lms_sign(LmsState* state, const byte* priv, const byte* msg,
    word32 msgSz, byte* sig)
{
    int ret;
    const LmsParams* params = state->params;
    byte* buffer = state->buffer;
    byte* s = sig;
    const byte* priv_q = priv;
    const byte* priv_seed = priv_q + LMS_Q_LEN;
    const byte* priv_i = priv_seed + LMS_SEED_LEN;

    /* Setup for hashing: I || Q */
    XMEMCPY(buffer, priv_i, LMS_I_LEN);
    XMEMCPY(buffer + LMS_I_LEN, priv_q, LMS_Q_LEN);

    /* Copy q from private key.
     * S = u32str(q) || ... */
    XMEMCPY(s, priv_q, LMS_Q_LEN);
    s += LMS_Q_LEN;

    /* ots_signature = sig = u32str(type) || ... */
    c32toa(state->params->lmOtsType, s);
    s += LMS_TYPE_LEN;
    /* Sign this level.
     * S = u32str(q) || ots_signature || ... */
    ret = wc_lmots_sign(state, priv_seed, msg, msgSz, s);
    if (ret == 0) {
        /* Skip over ots_signature. */
        s += LMS_MAX_NODE_LEN + params->p * LMS_MAX_NODE_LEN;
        /* S = u32str(q) || ots_signature || u32str(type) || ... */
        c32toa(params->lmsType, s);
    }

    return ret;
}

#if !defined(WOLFSSL_WC_LMS_SMALL) && !defined(WOLFSSL_LMS_NO_SIG_CACHE)
/* Copy in the cached signature data.
 *
 * @param [in]  params    LMS parameters.
 * @param [in]  y         y cache.
 * @param [in]  priv      Private key data.
 * @param [out] sig       Signature data.
 */
static void wc_lms_sig_copy(const LmsParams* params, const byte* y,
    const byte* priv, byte* sig)
{
    /* Put in q. */
    XMEMCPY(sig, priv, LMS_Q_LEN);
    sig += LMS_Q_LEN;
    /* S = u32str(q) || ... */
    c32toa(params->lmOtsType, sig);
    sig += LMS_TYPE_LEN;
    /* S = u32str(q) || ots_signature || ... */
    XMEMCPY(sig, y, LMS_MAX_NODE_LEN + params->p * LMS_MAX_NODE_LEN);
    sig += LMS_MAX_NODE_LEN + params->p * LMS_MAX_NODE_LEN;
    /* S = u32str(q) || ots_signature || u32str(type) || ... */
    c32toa(params->lmsType, sig);
}
#endif /* !WOLFSSL_WC_LMS_SMALL && !WOLFSSL_LMS_NO_SIG_CACHE */
#endif /* !WOLFSSL_LMS_VERIFY_ONLY */

/* Compute the root node of the LMS tree.
 *
 * Algorithm 6a: Computing an LMS Public Key Candidate from a Signature,
 * Message, Identifier, and Algorithm Typecodes
 *   ...
 *   4. Compute the candidate LMS root value Tc as follows:
 *      node_num = 2^h + q
 *      tmp = H(I || u32str(node_num) || u16str(D_LEAF) || Kc)
 *      i = 0
 *      while (node_num > 1) {
 *        if (node_num is odd):
 *          tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||path[i]||tmp)
 *        else:
 *          tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||tmp||path[i])
 *        node_num = node_num/2
 *        i = i + 1
 *      }
 *      Tc = tmp
 *   5. Return Tc.
 *
 * @param [in, out]  state  LMS state.
 * @param [in]       q      Index of node.
 * @param [in]       kc     K candidate.
 * @param [in]       path   Authentication path from signature.
 * @param [out]      tc     T candidate.
 * @return  0 on success.
 */
static int wc_lms_compute_root(LmsState* state, word32 q, const byte* kc,
    const byte* path, byte* tc)
{
    int ret;
    const LmsParams* params = state->params;
    byte* buffer = state->buffer;
    byte* rp = buffer + LMS_I_LEN;
    byte* ip = rp + LMS_Q_LEN;
    byte* node = ip + LMS_P_LEN;
    byte* b[2][2] = { { node,                    node + LMS_MAX_NODE_LEN },
                      { node + LMS_MAX_NODE_LEN, node                    } };
    /* node_num = 2^h + q */
    word32 r = (1 << params->height) + q;

    /* tmp = H(I || u32str(node_num) || u16str(D_LEAF) || Kc) */
    c32toa(r, rp);
    c16toa(LMS_D_LEAF, ip);
    XMEMCPY(node, kc, LMS_MAX_NODE_LEN);
    /* Put tmp into offset required for first iteration. */
#ifndef WC_LMS_FULL_HASH
    /* Put in padding for final block. */
    LMS_SHA256_SET_LEN_54(buffer);
    ret = wc_lms_hash_block(&state->hash, buffer, b[r & 1][0]);
#else
    ret = wc_lms_hash(&state->hash, buffer, LMS_SEED_HASH_LEN, b[r & 1][0]);
#endif /* !WC_LMS_FULL_HASH */

    if (ret == 0) {
        int i;

        /* I||...||u16str(D_INT)||... */
        c16toa(LMS_D_INTR, ip);

        /* Do all but last height. */
        for (i = 0; (ret == 0) && (i < params->height - 1); i++) {
            /* Put path into offset required. */
            XMEMCPY(b[r & 1][1], path, LMS_MAX_NODE_LEN);
            path += LMS_MAX_NODE_LEN;

            /* node_num = node_num / 2 */
            r >>= 1;
            /*  H(...||u32str(node_num/2)||..) */
            c32toa(r, rp);
            /* tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||path[i]||tmp) or
             * tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||tmp||path[i])
             * Put tmp result into offset required for next iteration. */
            ret = wc_lms_hash(&state->hash, buffer, LMS_NODE_HASH_LEN,
                b[r & 1][0]);
        }
        if (ret == 0) {
            /* Last height. */
            /* Put path into offset required. */
            XMEMCPY(b[r & 1][1], path, LMS_MAX_NODE_LEN);
            /* node_num = node_num / 2 */
            r >>= 1;
            /*  H(...||u32str(node_num/2)||..) */
            c32toa(r, rp);
            /* tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||path[i]||tmp) or
             * tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||tmp||path[i])
             * Put tmp result into Tc.*/
            ret = wc_lms_hash(&state->hash, buffer, LMS_NODE_HASH_LEN, tc);
        }
    }

    return ret;
}

/* LMS verify message using public key and signature.
 *
 * Algorithm 6a: Computing an LMS Public Key Candidate from a Signature,
 * Message, Identifier, and Algorithm Typecodes
 *   ...
 *   2. Parse sigtype, q, lmots_signature, and path from the signature
 *      as follows:
 *      a. q = strTou32(first 4 bytes of signature)
 *      ...
 *      e. lmots_signature = bytes 4 through 7 + n * (p + 1)
 *         of signature
 *      ...
 *      j. Set path as follows:
 *           path[0] = next m bytes of signature
 *           path[1] = next m bytes of signature
 *              ...
 *         path[h-1] = next m bytes of signature
 *   3. Kc = candidate public key computed by applying Algorithm 4b
 *      to the signature lmots_signature, the message, and the
 *      identifiers I, q
 *   4. Compute the candidate LMS root value Tc as follows:
 *      ...
 *   5. Return Tc
 * Algorithm 6: LMS Signature Verification
 *   ...
 *   3. Compute the LMS Public Key Candidate Tc from the signature,
 *      message, identifier, pubtype, and ots_typecode, using
 *      Algorithm 6a.
 *   4. If Tc is equal to T[1], return VALID; otherwise, return INVALID.
 *
 * @param [in, out] state  LMS state.
 * @param [in]      pub    LMS public key.
 * @param [in]      msg    Message/public key to verify.
 * @param [in]      msgSz  Length of message in bytes.
 * @param [in]      sig    LMS signature.
 */
static int wc_lms_verify(LmsState* state, const byte* pub, const byte* msg,
    word32 msgSz, const byte* sig)
{
    int ret;
    const LmsParams* params = state->params;
    byte* buffer = state->buffer;
    const byte* pub_i = pub + LMS_TYPE_LEN + LMS_TYPE_LEN;
    const byte* pub_k = pub_i + LMS_I_LEN;
    const byte* sig_q = sig;
    byte tc[LMS_MAX_NODE_LEN];
    byte* kc = tc;

    /* Algorithm 6. Step 3. */
    /* Check the public key LMS type matches parameters. */
    ret = wc_lmots_public_key_check(params, pub);
    if (ret == 0) {
        /* Algorithm 6a. Step 2.e. */
        const byte* sig_lmots = sig + LMS_Q_LEN;

        /* Setup buffer with I || Q. */
        XMEMCPY(buffer, pub_i, LMS_I_LEN);
        XMEMCPY(buffer + LMS_I_LEN, sig_q, LMS_Q_LEN);

        /* Algorithm 6a. Step 3. */
        ret = wc_lmots_calc_kc(state, pub + LMS_TYPE_LEN, msg, msgSz,
            sig_lmots, kc);
    }
    if (ret == 0) {
        /* Algorithm 6a. Step 2.j. */
        const byte* sig_path = sig + LMS_Q_LEN + LMS_TYPE_LEN +
            LMS_MAX_NODE_LEN + params->p * LMS_MAX_NODE_LEN + LMS_TYPE_LEN;
        word32 q;

        /* Algorithm 6a. Step 2.a. */
        ato32(sig_q, &q);

        /* Algorithm 6a. Steps 4-5. */
        ret = wc_lms_compute_root(state, q, kc, sig_path, tc);
    }
    /* Algorithm 6. Step 4. */
    if ((ret == 0) && (XMEMCMP(pub_k, tc, LMS_MAX_NODE_LEN) != 0)) {
        ret = SIG_VERIFY_E;
    }

    return ret;
}

/***************************************
 * HSS APIs
 **************************************/

#ifndef WOLFSSL_LMS_VERIFY_ONLY
/* Derive the seed and i for child.
 *
 * @param [in, out] state   LMS state.
 * @param [in]      id      Parent's I.
 * @param [in]      seed    Parent's SEED.
 * @param [in]      q       Parent's q.
 * @param [out]     seed_i  Derived SEED and I.
 * @return  0 on success.
 */
static int wc_hss_derive_seed_i(LmsState* state, const byte* id,
    const byte* seed, const byte* q, byte* seed_i)
{
    int ret = 0;
    byte buffer[WC_SHA256_BLOCK_SIZE];
    byte* idp = buffer;
    byte* qp = idp + LMS_I_LEN;
    byte* ip = qp + LMS_Q_LEN;
    byte* jp = ip + LMS_P_LEN;
    byte* tmp = jp + LMS_W_LEN;

    /* parent's I || ... */
    XMEMCPY(idp, id, LMS_I_LEN);
    /* parent's I || q || ... */
    XMEMCPY(qp, q, LMS_Q_LEN);
    /* parent's I || q || D_CHILD_SEED || ... */
    c16toa(LMS_D_CHILD_SEED, ip);
    /* parent's I || q || D_CHILD_SEED || D_FIXED || ... */
    *jp = LMS_D_FIXED;
    /* parent's I || q || D_CHILD_SEED || D_FIXED || parent's SEED */
    XMEMCPY(tmp, seed, LMS_SEED_LEN);
    /* SEED = H(parent's I || q || D_CHILD_SEED || D_FIXED || parent's SEED) */
#ifndef WC_LMS_FULL_HASH
    /* Put in padding for final block. */
    LMS_SHA256_SET_LEN_55(buffer);
    ret = wc_lms_hash_block(&state->hash, buffer, seed_i);
#else
    ret = wc_lms_hash(&state->hash, buffer, LMS_HASH_BUFFER_LEN, seed_i);
#endif /* !WC_LMS_FULL_HASH */

    if (ret == 0) {
        seed_i += LMS_SEED_LEN;
        /* parent's I || q || D_CHILD_I || D_FIXED || parent's SEED */
        c16toa(LMS_D_CHILD_I, ip);
        /* I = H(parent's I || q || D_CHILD_I || D_FIXED || parent's SEED) */
    #ifndef WC_LMS_FULL_HASH
        ret = wc_lms_hash_block(&state->hash, buffer, tmp);
    #else
        ret = wc_lms_hash(&state->hash, buffer, LMS_HASH_BUFFER_LEN, tmp);
    #endif /* !WC_LMS_FULL_HASH */
        /* Copy part of hash as new I into private key. */
        XMEMCPY(seed_i, tmp, LMS_I_LEN);
    }

    return ret;
}

/* Get q, index, of leaf at the specified level. */
#define LMS_Q_AT_LEVEL(q, ls, l, h)                                 \
    (w64GetLow32(w64ShiftRight((q), (((ls) - 1 - (l)) * (h)))) &    \
     (((word32)1 << (h)) - 1))

/* Expand the seed and I for further levels and set q for each level.
 *
 * @param [in, out] state     LMS state.
 * @param [in, out] priv      Private key for use in signing.
 * @param [in]      priv_raw  Private key read.
 * @param [in]      inc       Whether this is an incremental expansion.
 * @return  0 on success.
 */
static int wc_hss_expand_private_key(LmsState* state, byte* priv,
    const byte* priv_raw, int inc)
{
    const LmsParams* params = state->params;
    int ret = 0;
    w64wrapper q;
    w64wrapper qm1;
    word32 q32;
    byte* priv_q;
    byte* priv_seed_i;
    int i;

    /* Get the 64-bit q value from the raw private key. */
    ato64(priv_raw, &q);
    /* Step over q and parameter set. */
    priv_raw += HSS_Q_LEN + HSS_PRIV_KEY_PARAM_SET_LEN;

    /* Get q of highest level. */
    q32 = LMS_Q_AT_LEVEL(q, params->levels, 0, params->height);
    /* Set q of highest tree. */
    c32toa(q32, priv);

    /* Incremental expansion needs q-1. */
    if (inc) {
        /* Calculate q-1 for comparison. */
        qm1 = q;
        w64Decrement(&qm1);
    }
    else {
        /* Copy out SEED and I into private key. */
        XMEMCPY(priv + LMS_Q_LEN, priv_raw, LMS_SEED_I_LEN);
    }

    /* Compute SEED and I for rest of levels. */
    for (i = 1; (ret == 0) && (i < params->levels); i++) {
        /* Don't skip calculating SEED and I. */
        int skip = 0;

        /* Incremental means q, SEED and I already present if q unchanged. */
        if (inc) {
            /* Calculate previous levels q for previous 64-bit q value. */
            word32 qm1_32 = LMS_Q_AT_LEVEL(qm1, params->levels, i - 1,
                params->height);
            /* Same q at previous level means no need to re-compute. */
            if (q32 == qm1_32) {
                /* Do skip calculating SEED and I. */
                skip = 1;
            }
        }

        /* Get pointers into private q to write q and seed + I. */
        priv_q = priv;
        priv += LMS_Q_LEN;
        priv_seed_i = priv;
        priv += LMS_SEED_I_LEN;

        /* Get q for level from 64-bit composite. */
        q32 = w64GetLow32(w64ShiftRight(q, (params->levels - 1 - i) *
            params->height)) & (((word32)1 << params->height) - 1);
        /* Set q of tree. */
        c32toa(q32, priv);

        if (!skip) {
            /* Derive SEED and I into private key. */
            ret = wc_hss_derive_seed_i(state, priv_seed_i + LMS_SEED_LEN,
                priv_seed_i, priv_q, priv + LMS_Q_LEN);
        }
    }

    return ret;
}

#ifndef WOLFSSL_WC_LMS_SMALL
#ifndef WOLFSSL_LMS_NO_SIGN_SMOOTHING
/* Initialize the next subtree.
 *
 * @param [in] state      LMS state.
 * @param [in] privState  LMS private state.
 * @param [in] curr       Current private key.
 * @param [in] priv       Next private key.
 * @param [in] q          q for this level.
 * @return  0 on success.
 */
static int wc_lms_next_subtree_init(LmsState* state, LmsPrivState* privState,
    byte* curr, byte* priv, word32 q)
{
    int ret;
    const LmsParams* params = state->params;
    byte* priv_q;
    byte* priv_seed;
    byte* priv_i;
    word32 pq;

    priv_q = priv;
    priv += LMS_Q_LEN;
    priv_seed = curr + LMS_Q_LEN;
    priv += LMS_SEED_LEN;
    priv_i = curr + LMS_Q_LEN + LMS_SEED_LEN;
    priv += LMS_I_LEN;

    ato32(curr, &pq);
    pq = (pq + 1) & ((1 << params->height) - 1);
    c32toa(pq, priv_q);

    privState->stack.offset = 0;
    privState->leaf.idx = (word32)-(1 << params->cacheBits);
    privState->leaf.offset = 0;

    /* Derive SEED and I for next tree. */
    ret = wc_hss_derive_seed_i(state, priv_i, priv_seed, priv_q,
        priv + LMS_Q_LEN);
    if (ret == 0) {
        /* Update treehash for first leaf. */
        ret = wc_lms_treehash_update(state, privState,
            priv + LMS_Q_LEN + LMS_SEED_LEN, priv + LMS_Q_LEN, 0, q, 0, 0);
    }

    return ret;
}

/* Increment count on next subtree.
 *
 * @param [in] state     LMS state.
 * @param [in] priv_key  HSS private key.
 * @param [in] q64       64-bit q for all levels.
 * @return  0 on success.
 */
static int wc_hss_next_subtree_inc(LmsState* state, HssPrivKey* priv_key,
    w64wrapper q64)
{
    int ret = 0;
    const LmsParams* params = state->params;
    byte* curr = priv_key->priv;
    byte* priv = priv_key->next_priv;
    int i;
    w64wrapper p64 = q64;
    byte tmp_priv[LMS_PRIV_LEN];
    int use_tmp = 0;
    int lastQMax = 0;
    w64wrapper p64_hi;
    w64wrapper q64_hi;

    /* Get previous index. */
    w64Decrement(&p64);
    /* Get index of previous and current parent. */
    p64_hi = w64ShiftRight(p64, (params->levels - 1) * params->height);
    q64_hi = w64ShiftRight(q64, (params->levels - 1) * params->height);
    for (i = 1; (ret == 0) && (i < params->levels); i++) {
        word32 qc;
        w64wrapper cp64_hi;
        w64wrapper cq64_hi;

        /* Get index of previous and current child. */
        cp64_hi = w64ShiftRight(p64, (params->levels - i - 1) * params->height);
        cq64_hi = w64ShiftRight(q64, (params->levels - i - 1) * params->height);
        /* Get the q for the child. */
        ato32(curr + LMS_PRIV_LEN, &qc);

        /* Compare index of parent node with previous value. */
        if (w64LT(p64_hi, q64_hi)) {
            wc_lms_priv_state_copy(params, &priv_key->state[i],
                &priv_key->next_state[i-1]);
            ret = wc_lms_next_subtree_init(state, &priv_key->next_state[i - 1],
                use_tmp ? tmp_priv : curr, priv, 0);
            use_tmp = 0;
        }
        /* Check whether the child is in a new subtree. */
        else if ((qc == ((word32)1 << params->height) - 1) &&
                w64LT(cp64_hi, cq64_hi)) {
            XMEMSET(tmp_priv, 0, LMS_Q_LEN);
            /* Check whether the node at the previous level is also in a new
             * subtree. */
            if (lastQMax) {
                /* Calculate new SEED and I based on new subtree. */
                ret = wc_hss_derive_seed_i(state,
                    priv + LMS_Q_LEN + LMS_SEED_LEN, priv + LMS_Q_LEN, tmp_priv,
                    tmp_priv + LMS_Q_LEN);
            }
            else {
                /* Calculate new SEED and I based on parent. */
                ret = wc_hss_derive_seed_i(state,
                    curr + LMS_Q_LEN + LMS_SEED_LEN, curr + LMS_Q_LEN, priv,
                    tmp_priv + LMS_Q_LEN);
            }
            /* Values not stored so note that they are in temporary. */
            use_tmp = 1;

            /* Set the the q. */
            XMEMCPY(tmp_priv, curr + LMS_PRIV_LEN, LMS_Q_LEN);
        }

        lastQMax = (qc == ((word32)1 << params->height) - 1);
        curr += LMS_PRIV_LEN;
        priv += LMS_PRIV_LEN;
        p64_hi = cp64_hi;
        q64_hi = cq64_hi;
    }

    return ret;
}

/* Initialize the next subtree for each level bar the highest.
 *
 * @param [in, out] state     LMS state.
 * @param [out]     priv_key  Private key data.
 * @return  0 on success.
 */
static int wc_hss_next_subtrees_init(LmsState* state, HssPrivKey* priv_key)
{
    int ret = 0;
    const LmsParams* params = state->params;
    byte* curr = priv_key->priv;
    byte* priv = priv_key->next_priv;
    int i;

    XMEMCPY(priv, curr, LMS_PRIV_LEN);
    wc_lms_idx_inc(priv, LMS_Q_LEN);

    for (i = 1; (ret == 0) && (i < params->levels); i++) {
        word32 q;

        ato32(curr + LMS_PRIV_LEN, &q);
        ret = wc_lms_next_subtree_init(state, &priv_key->next_state[i - 1],
            curr, priv, q);

        curr += LMS_PRIV_LEN;
        priv += LMS_PRIV_LEN;
    }

    return ret;
}
#endif

/* Update the authentication path and caches.
 *
 * @param [in, out] state     LMS state.
 * @param [in, out] priv_key  Private key information.
 * @param [in]      levels    Number of level to start at.
 * @param [out]     pub_root  Public root.
 * @return  0 on success.
 */
static int wc_hss_init_auth_path(LmsState* state, HssPrivKey* priv_key,
    byte* pub_root)
{
    int ret = 0;
    int levels = state->params->levels;
    byte* priv = priv_key->priv + LMS_PRIV_LEN * (levels - 1);
    int l;

    for (l = levels - 1; (ret == 0) && (l >= 0); l--) {
        word32 q;
        const byte* priv_q = priv;
        const byte* priv_seed = priv_q + LMS_Q_LEN;
        const byte* priv_i = priv_seed + LMS_SEED_LEN;

        /* Get current q for tree at level. */
        ato32(priv_q, &q);
        /* Set cache start to a value that indicates no numbers available. */
        ret = wc_lms_treehash_init(state, &priv_key->state[l], priv_i,
             priv_seed, q);

        /* Move onto next level's data. */
        priv -= LMS_PRIV_LEN;
    }

    if ((ret == 0) && (pub_root != NULL)) {
        XMEMCPY(pub_root, priv_key->state[0].root, LMS_MAX_NODE_LEN);
    }

    return ret;
}

/* Calculate the corresponding authentication path index at that height.
 *
 * @param [in] i  Leaf node index.
 * @param [in] h  Height to calculate for.
 * @return  Index on authentication path.
 */
#define LMS_AUTH_PATH_IDX(i, h)                                 \
    (((i) ^ ((word32)1U << (h))) | (((word32)1U << (h)) - 1))

/* Update the authentication path.
 *
 * @param [in, out] state     LMS state.
 * @param [in, out] priv_key  Private key information.
 * @param [in]      levels    Number of level to start at.
 * @return  0 on success.
 */
static int wc_hss_update_auth_path(LmsState* state, HssPrivKey* priv_key,
    byte* priv_raw, int levels)
{
    const LmsParams* params = state->params;
    int ret = 0;
    byte* priv = priv_key->priv + LMS_PRIV_LEN * (levels - 1);
    int i;
#ifndef WOLFSSL_LMS_NO_SIGN_SMOOTHING
    w64wrapper q64;
#endif

    (void)priv_raw;
#ifndef WOLFSSL_LMS_NO_SIGN_SMOOTHING
    ato64(priv_raw, &q64);
#endif

    for (i = levels - 1; (ret == 0) && (i >= 0); i--) {
        word32 q;
        const byte* priv_q = priv;
        const byte* priv_seed = priv_q + LMS_Q_LEN;
        const byte* priv_i = priv_seed + LMS_SEED_LEN;
        LmsPrivState* privState = &priv_key->state[i];

        /* Get q for tree at level. */
        ato32(priv_q, &q);
    #ifndef WOLFSSL_LMS_NO_SIGN_SMOOTHING

        if ((levels > 1) && (i == levels - 1) && (q == 0)) {
            /* New sub-tree. */
            ret = wc_hss_next_subtree_inc(state, priv_key, q64);
        }
        if ((ret == 0) && (q != 0))
    #else
        if (q == 0) {
            /* New sub-tree. */
            ret = wc_lms_treehash_init(state, privState, priv_i, priv_seed, 0);
        }
        else
    #endif
        {
            word32 maxq = q - 1;
            int h;
            int maxh = params->height;

            /* Check each index at each height needed for the auth path. */
            for (h = 0; (h < maxh) && (h <= maxh - params->rootLevels); h++) {
                /* Calculate the index for current q and q-1. */
                word32 qa = LMS_AUTH_PATH_IDX(q, h);
                word32 qm1a = LMS_AUTH_PATH_IDX(q - 1, h);
                /* If different then needs to be computed so keep highest. */
                if ((qa != qm1a) && (qa > maxq)) {
                    maxq = qa;
                }
            }
            for (; h < maxh; h++) {
                /* Calculate the index for current q and q-1. */
                word32 qa = LMS_AUTH_PATH_IDX(q, h);
                word32 qm1a = LMS_AUTH_PATH_IDX(q - 1, h);
                /* If different then copy in cached hash. */
                if ((qa != qm1a) && (qa > maxq)) {
                    int off = (1 << (params->height - h)) + (qa >> h) - 1;
                    XMEMCPY(privState->auth_path + h * LMS_MAX_NODE_LEN,
                        privState->root + off * LMS_MAX_NODE_LEN,
                        LMS_MAX_NODE_LEN);
                }
            }
            /* Update the treehash and calculate the extra indices for
             * authentication path. */
            ret = wc_lms_treehash_update(state, privState, priv_i, priv_seed,
                q - 1, maxq, q, 1);
        #ifndef WOLFSSL_LMS_NO_SIGN_SMOOTHING
            if ((ret == 0) && (i > 0)) {
                w64wrapper tmp64 = w64ShiftRight(q64,
                    (levels - i) * params->height);
                w64Increment(&tmp64);
                tmp64 = w64ShiftLeft(tmp64, 64 - (i * params->height));
                if (!w64IsZero(tmp64)) {
                    priv_seed = priv_key->next_priv + i * LMS_PRIV_LEN +
                        LMS_Q_LEN;
                    priv_i = priv_seed + LMS_SEED_LEN;
                    privState = &priv_key->next_state[i - 1];

                    ret = wc_lms_treehash_update(state, privState, priv_i,
                        priv_seed, q, q, 0, 0);
                }
            }
        #endif
            break;
        }

        /* Move onto next level's data. */
        priv -= LMS_PRIV_LEN;
    }

    return ret;
}

#if !defined(WOLFSSL_LMS_NO_SIG_CACHE) && (LMS_MAX_LEVELS > 1)
/* Pre-sign for current q so that it isn't needed in signing.
 *
 * @param [in, out] state     LMS state.
 * @param [in, out] priv_key  Private key.
 */
static int wc_hss_presign(LmsState* state, HssPrivKey* priv_key)
{
    int ret = 0;
    const LmsParams* params = state->params;
    byte* buffer = state->buffer;
    byte pub[LMS_PUBKEY_LEN];
    byte* root = pub + LMS_PUBKEY_LEN - LMS_MAX_NODE_LEN;
    byte* priv = priv_key->priv;
    int i;

    for (i = params->levels - 2; i >= 0; i--) {
        const byte* p = priv + i * (LMS_Q_LEN + LMS_SEED_LEN + LMS_I_LEN);
        const byte* priv_q = p;
        const byte* priv_seed = priv_q + LMS_Q_LEN;
        const byte* priv_i = priv_seed + LMS_SEED_LEN;

        /* ... || T(1) */
        XMEMCPY(root, priv_key->state[i + 1].root, LMS_MAX_NODE_LEN);
        /* u32str(type) || u32str(otstype) || I || T(1) */
        p = priv + (i + 1) * (LMS_Q_LEN + LMS_SEED_LEN + LMS_I_LEN);
        wc_lmots_public_key_encode(params, p, pub);

        /* Setup for hashing: I || Q || ... */
        XMEMCPY(buffer, priv_i, LMS_I_LEN);
        XMEMCPY(buffer + LMS_I_LEN, priv_q, LMS_Q_LEN);

        /* LM-OTS Sign this level. */
        ret = wc_lmots_sign(state, priv_seed, pub, LMS_PUBKEY_LEN,
            priv_key->y + i * LMS_PRIV_Y_TREE_LEN(params->p));
    }

    return ret;
}
#endif /* !WOLFSSL_LMS_NO_SIG_CACHE && LMS_MAX_LEVELS > 1 */
#endif /* !WOLFSSL_WC_LMS_SMALL */

/* Load the private key data into HSS private key structure.
 *
 * @param [in]      params     LMS parameters.
 * @param [in, out] key        HSS private key.
 * @param [in]      priv_data  Private key data.
 */
static void wc_hss_priv_data_load(const LmsParams* params, HssPrivKey* key,
    byte* priv_data)
{
#ifndef WOLFSSL_WC_LMS_SMALL
    int l;
#endif

    /* Expanded private keys. */
    key->priv = priv_data;
    priv_data += LMS_PRIV_KEY_LEN(params->levels);

#ifndef WOLFSSL_WC_LMS_SMALL
    for (l = 0; l < params->levels; l++) {
        /* Caches for subtree. */
        wc_lms_priv_state_load(params, &key->state[l], priv_data);
        priv_data += LMS_PRIV_STATE_LEN(params->height, params->rootLevels,
            params->cacheBits);
    }

#ifndef WOLFSSL_LMS_NO_SIGN_SMOOTHING
    /* Next subtree's expanded private keys. */
    key->next_priv = priv_data;
    priv_data += LMS_PRIV_KEY_LEN(params->levels);
    for (l = 0; l < params->levels - 1; l++) {
        /* Next subtree's caches. */
        wc_lms_priv_state_load(params, &key->next_state[l], priv_data);
        priv_data += LMS_PRIV_STATE_LEN(params->height, params->rootLevels,
            params->cacheBits);
    }
#endif /* WOLFSSL_LMS_NO_SIGN_SMOOTHING */

#ifndef WOLFSSL_LMS_NO_SIG_CACHE
    /* Signature cache. */
    key->y = priv_data;
#endif /* WOLFSSL_LMS_NO_SIG_CACHE */
#endif /* WOLFSSL_WC_LMS_SMALL */
}

#ifndef WOLFSSL_WC_LMS_SMALL
/* Store the private key data from HSS private key structure.
 *
 * @param [in]      params     LMS parameters.
 * @param [in]      key        HSS private key.
 * @param [in, out] priv_data  Private key data.
 */
static void wc_hss_priv_data_store(const LmsParams* params, HssPrivKey* key,
    byte* priv_data)
{
    int l;

    (void)key;

    /* Expanded private keys. */
    priv_data += LMS_PRIV_KEY_LEN(params->levels);

    for (l = 0; l < params->levels; l++) {
        /* Caches for subtrees. */
        wc_lms_priv_state_store(params, &key->state[l], priv_data);
        priv_data += LMS_PRIV_STATE_LEN(params->height, params->rootLevels,
            params->cacheBits);
    }
#ifndef WOLFSSL_LMS_NO_SIGN_SMOOTHING
    /* Next subtree's expanded private keys. */
    priv_data += LMS_PRIV_KEY_LEN(params->levels);
    for (l = 0; l < params->levels - 1; l++) {
        /* Next subtree's caches. */
        wc_lms_priv_state_store(params, &key->next_state[l], priv_data);
        priv_data += LMS_PRIV_STATE_LEN(params->height, params->rootLevels,
            params->cacheBits);
    }
#endif /* WOLFSSL_LMS_NO_SIGN_SMOOTHING */

#ifndef WOLFSSL_LMS_NO_SIG_CACHE
    /* Signature cache. */
#endif /* WOLFSSL_LMS_NO_SIG_CACHE */
}
#endif /* WOLFSSL_WC_LMS_SMALL */

/* Expand private key for each level and calculating auth path..
 *
 * @param [in, out] state      LMS state.
 * @param [in]      priv_raw   Raw private key bytes.
 * @param [out]     priv_key   Private key data.
 * @param [out]     priv_data  Private key data.
 * @param [out]     pub_root   Public key root node.
 * @return  0 on success.
 */
int wc_hss_reload_key(LmsState* state, const byte* priv_raw,
    HssPrivKey* priv_key, byte* priv_data, byte* pub_root)
{
    int ret;

    (void)pub_root;

    wc_hss_priv_data_load(state->params, priv_key, priv_data);
#ifndef WOLFSSL_WC_LMS_SMALL
    priv_key->inited = 0;
#endif

    /* Expand the raw private key into the private key data. */
    ret = wc_hss_expand_private_key(state, priv_key->priv, priv_raw, 0);
#ifndef WOLFSSL_WC_LMS_SMALL
    if ((ret == 0) && (!priv_key->inited)) {
        /* Initialize the authentication paths and caches for all trees. */
        ret = wc_hss_init_auth_path(state, priv_key, pub_root);
    #ifndef WOLFSSL_LMS_NO_SIGN_SMOOTHING
        if (ret == 0) {
            ret = wc_hss_next_subtrees_init(state, priv_key);
        }
    #endif
    #if !defined(WOLFSSL_LMS_NO_SIG_CACHE) && (LMS_MAX_LEVELS > 1)
        if (ret == 0) {
            /* Calculate signatures for trees not at bottom. */
            ret = wc_hss_presign(state, priv_key);
        }
    #endif /* !WOLFSSL_LMS_NO_SIG_CACHE */
        /* Set initialized flag. */
        priv_key->inited = (ret == 0);
    }
#endif /* WOLFSSL_WC_LMS_SMALL */

    return ret;
}

/* Make an HSS key pair.
 *
 * @param [in, out] state      LMS state.
 * @param [in]      rng        Random number generator.
 * @param [out]     priv_raw   Private key to write.
 * @param [out]     priv_key   Private key.
 * @param [out]     priv_data  Private key data.
 * @param [out]     pub        Public key.
 * @return  0 on success.
 */
int wc_hss_make_key(LmsState* state, WC_RNG* rng, byte* priv_raw,
    HssPrivKey* priv_key, byte* priv_data, byte* pub)
{
    const LmsParams* params = state->params;
    int ret = 0;
    int i;
    byte* p = priv_raw;
    byte* pub_root = pub + LMS_L_LEN + LMS_TYPE_LEN + LMS_TYPE_LEN + LMS_I_LEN;

    /* The 64-bit q starts at 0 - set into raw private key. */
    wc_lms_idx_zero(p, HSS_Q_LEN);
    p += HSS_Q_LEN;

    /* Set the LMS and LM-OTS types for each level. */
    for (i = 0; i < params->levels; i++) {
        p[i] = (params->lmsType << 4) + params->lmOtsType;
    }
    /* Set rest of levels to an invalid value. */
    for (; i < HSS_MAX_LEVELS; i++) {
        p[i] = 0xff;
    }
    p += HSS_PRIV_KEY_PARAM_SET_LEN;

    /* Make the private key. */
    ret = wc_lmots_make_private_key(rng, p);

    if (ret == 0) {
        /* Set the levels into the public key data. */
        c32toa(params->levels, pub);
        pub += LMS_L_LEN;

        ret = wc_hss_reload_key(state, priv_raw, priv_key, priv_data, pub_root);
    }
    #ifdef WOLFSSL_WC_LMS_SMALL
    if (ret == 0) {
        byte* priv_seed = priv_key->priv + LMS_Q_LEN;
        byte* priv_i = priv_seed + LMS_SEED_LEN;

        /* Compute the root of the highest tree to get the root for public key.
         */
        ret = wc_lms_make_public_key(state, priv_i, priv_seed, pub_root);
    }
    #endif /* !WOLFSSL_WC_LMS_SMALL */
    if (ret == 0) {
        /* Encode the public key with remaining fields from the private key. */
        wc_lmots_public_key_encode(params, priv_key->priv, pub);
    }

    return ret;
}

#ifdef WOLFSSL_WC_LMS_SMALL
/* Sign message using HSS.
 *
 * Algorithm 8: Generating an HSS signature
 *   1. If the message-signing key prv[L-1] is exhausted, regenerate
 *      that key pair, together with any parent key pairs that might
 *      be necessary.
 *      If the root key pair is exhausted, then the HSS key pair is
 *      exhausted and MUST NOT generate any more signatures.
 *      d = L
 *      while (prv[d-1].q == 2^(prv[d-1].h)) {
 *        d = d - 1
 *        if (d == 0)
 *          return FAILURE
 *      }
 *      while (d < L) {
 *        create lms key pair pub[d], prv[d]
 *        sig[d-1] = lms_signature( pub[d], prv[d-1] )
 *        d = d + 1
 *      }
 *   2. Sign the message.
 *      sig[L-1] = lms_signature( msg, prv[L-1] )
 *   3. Create the list of signed public keys.
 *      i = 0;
 *      while (i < L-1) {
 *        signed_pub_key[i] = sig[i] || pub[i+1]
 *        i = i + 1
 *      }
 *   4. Return u32str(L-1) || signed_pub_key[0] || ...
 *                               || signed_pub_key[L-2] || sig[L-1]
 *
 * @param [in, out] state     LMS state.
 * @param [in, out] priv_raw  Raw private key bytes.
 * @param [in, out] priv_key  Private key data.
 * @param [in]      msg       Message to sign.
 * @param [in]      msgSz     Length of message in bytes.
 * @param [out]     sig       Signature of message.
 * @return  0 on success.
 */
int wc_hss_sign(LmsState* state, byte* priv_raw, HssPrivKey* priv_key,
    byte* priv_data, const byte* msg, word32 msgSz, byte* sig)
{
    const LmsParams* params = state->params;
    int ret = 0;
    byte* priv = priv_key->priv;

    (void)priv_data;

    /* Step 1. Part 2: Check for total key exhaustion. */
    if (!wc_hss_sigsleft(params, priv_raw)) {
        ret = KEY_EXHAUSTED_E;
    }

    if (ret == 0) {
        /* Expand the raw private key into the private key data. */
        ret = wc_hss_expand_private_key(state, priv, priv_raw, 0);
    }
    if (ret == 0) {
        int i;
        w64wrapper q;
        w64wrapper qm1;

        /* Get 64-bit q from raw private key. */
        ato64(priv_raw, &q);
        /* Calculate q-1 for comparison. */
        qm1 = q;
        w64Decrement(&qm1);

        /* Set number of signed public keys. */
        c32toa(params->levels - 1, sig);
        sig += params->sig_len;

        /* Build from bottom up. */
        for (i = params->levels - 1; (ret == 0) && (i >= 0); i--) {
            byte* p = priv + i * (LMS_Q_LEN + LMS_SEED_LEN + LMS_I_LEN);
            byte* root = NULL;

            /* Move to start of next signature at this level. */
            sig -= LMS_SIG_LEN(params->height, params->p);
            if (i != 0) {
                /* Put root node into signature at this index. */
                root = sig - LMS_MAX_NODE_LEN;
            }

            /* Sign using LMS for this level. */
            ret = wc_lms_sign(state, p, msg, msgSz, sig);
            if (ret == 0) {
                byte* s = sig + LMS_Q_LEN + LMS_TYPE_LEN + LMS_MAX_NODE_LEN +
                    params->p * LMS_MAX_NODE_LEN + LMS_TYPE_LEN;
                byte* priv_q = p;
                byte* priv_seed = priv_q + LMS_Q_LEN;
                byte* priv_i = priv_seed + LMS_SEED_LEN;
                word32 q32;

                /* Get Q from private key as a number. */
                ato32(priv_q, &q32);
                /* Calculate authentication path. */
                ret = wc_lms_auth_path(state, priv_i, priv_seed, q32, s, root);
            }
            if ((ret == 0) && (i != 0)) {
                /* Create public data for this level if there is another. */
                sig -= LMS_PUBKEY_LEN;
                msg = sig;
                msgSz = LMS_PUBKEY_LEN;
                wc_lmots_public_key_encode(params, p, sig);
            }
        }
    }
    if (ret == 0) {
        /* Increment index of leaf node to sign with in raw data. */
        wc_lms_idx_inc(priv_raw, HSS_Q_LEN);
    }

    return ret;
}
#else
/* Build signature for HSS signed message.
 *
 * Algorithm 8: Generating an HSS signature
 *   1. ...
 *      while (prv[d-1].q == 2^(prv[d-1].h)) {
 *        d = d - 1
 *        if (d == 0)
 *          return FAILURE
 *      }
 *      while (d < L) {
 *        create lms key pair pub[d], prv[d]
 *        sig[d-1] = lms_signature( pub[d], prv[d-1] )
 *        d = d + 1
 *      }
 *   2. Sign the message.
 *      sig[L-1] = lms_signature( msg, prv[L-1] )
 *   3. Create the list of signed public keys.
 *      i = 0;
 *      while (i < L-1) {
 *        signed_pub_key[i] = sig[i] || pub[i+1]
 *        i = i + 1
 *      }
 *   4. Return u32str(L-1) || signed_pub_key[0] || ...
 *                               || signed_pub_key[L-2] || sig[L-1]
 *
 * @param [in, out] state      LMS state.
 * @param [in, out] priv_raw   Raw private key bytes.
 * @param [in, out] priv_key   Private key data.
 * @param [in]      msg        Message to sign.
 * @param [in]      msgSz      Length of message in bytes.
 * @param [out]     sig        Signature of message.
 * @return  0 on success.
 */
static int wc_hss_sign_build_sig(LmsState* state, byte* priv_raw,
    HssPrivKey* priv_key, const byte* msg, word32 msgSz, byte* sig)
{
    const LmsParams* params = state->params;
    int ret = 0;
    int i;
    w64wrapper q;
    w64wrapper qm1;
    byte* priv = priv_key->priv;

    /* Get 64-bit q from raw private key. */
    ato64(priv_raw, &q);
    /* Calculate q-1 for comparison. */
    qm1 = q;
    w64Decrement(&qm1);

    /* Set number of signed public keys. */
    c32toa(params->levels - 1, sig);
    sig += params->sig_len;

    /* Build from bottom up. */
    for (i = params->levels - 1; (ret == 0) && (i >= 0); i--) {
        byte* p = priv + i * (LMS_Q_LEN + LMS_SEED_LEN + LMS_I_LEN);
        byte* root = NULL;
    #ifndef WOLFSSL_LMS_NO_SIG_CACHE
        int store_p = 0;
        word32 q_32 = LMS_Q_AT_LEVEL(q, params->levels, i,
            params->height);
        word32 qm1_32 = LMS_Q_AT_LEVEL(qm1, params->levels, i,
            params->height);
    #endif /* !WOLFSSL_LMS_NO_SIG_CACHE */

        /* Move to start of next signature at this level. */
        sig -= LMS_SIG_LEN(params->height, params->p);
        if (i != 0) {
            /* Put root node into signature at this index. */
            root = sig - LMS_MAX_NODE_LEN;
        }

    #ifndef WOLFSSL_LMS_NO_SIG_CACHE
        /* Check if we have a cached version of C and the p hashes that we
         * can reuse. */
        if ((i < params->levels - 1) && (q_32 == qm1_32)) {
            wc_lms_sig_copy(params, priv_key->y +
                i * LMS_PRIV_Y_TREE_LEN(params->p), p, sig);
        }
        else
    #endif /* !WOLFSSL_LMS_NO_SIG_CACHE */
        {
            /* Sign using LMS for this level. */
            ret = wc_lms_sign(state, p, msg, msgSz, sig);
        #ifndef WOLFSSL_LMS_NO_SIG_CACHE
            store_p = (i < params->levels - 1);
        #endif /* !WOLFSSL_LMS_NO_SIG_CACHE */
        }
        if (ret == 0) {
            byte* s = sig + LMS_Q_LEN + LMS_TYPE_LEN;

        #ifndef WOLFSSL_LMS_NO_SIG_CACHE
            /* Check if we computed new C and p hashes. */
            if (store_p) {
                /* Cache the C and p hashes. */
                XMEMCPY(priv_key->y + i * LMS_PRIV_Y_TREE_LEN(params->p), s,
                    LMS_PRIV_Y_TREE_LEN(params->p));
            }
        #endif /* !WOLFSSL_LMS_NO_SIG_CACHE */
            s += LMS_MAX_NODE_LEN + params->p * LMS_MAX_NODE_LEN +
                LMS_TYPE_LEN;

            /* Copy the authentication path out of the private key. */
            XMEMCPY(s, priv_key->state[i].auth_path,
                params->height * LMS_MAX_NODE_LEN);
            /* Copy the root node into signature unless at top. */
            if (i != 0) {
                XMEMCPY(root, priv_key->state[i].root, LMS_MAX_NODE_LEN);
            }
        }
        if ((ret == 0) && (i != 0)) {
            /* Create public data for this level if there is another. */
            sig -= LMS_PUBKEY_LEN;
            msg = sig;
            msgSz = LMS_PUBKEY_LEN;
            wc_lmots_public_key_encode(params, p, sig);
        }
    }

    return ret;
}

/* Sign message using HSS.
 *
 * Algorithm 8: Generating an HSS signature
 *   1. If the message-signing key prv[L-1] is exhausted, regenerate
 *      that key pair, together with any parent key pairs that might
 *      be necessary.
 *      If the root key pair is exhausted, then the HSS key pair is
 *      exhausted and MUST NOT generate any more signatures.
 *      d = L
 *      while (prv[d-1].q == 2^(prv[d-1].h)) {
 *        d = d - 1
 *        if (d == 0)
 *          return FAILURE
 *      }
 *      while (d < L) {
 *        create lms key pair pub[d], prv[d]
 *        sig[d-1] = lms_signature( pub[d], prv[d-1] )
 *        d = d + 1
 *      }
 *   2. Sign the message.
 *      sig[L-1] = lms_signature( msg, prv[L-1] )
 *   3. Create the list of signed public keys.
 *      i = 0;
 *      while (i < L-1) {
 *        signed_pub_key[i] = sig[i] || pub[i+1]
 *        i = i + 1
 *      }
 *   4. Return u32str(L-1) || signed_pub_key[0] || ...
 *                               || signed_pub_key[L-2] || sig[L-1]
 *
 * @param [in, out] state      LMS state.
 * @param [in, out] priv_raw   Raw private key bytes.
 * @param [in, out] priv_key   Private key data.
 * @param [in, out] priv_data  Private key data.
 * @param [in]      msg        Message to sign.
 * @param [in]      msgSz      Length of message in bytes.
 * @param [out]     sig        Signature of message.
 * @return  0 on success.
 */
int wc_hss_sign(LmsState* state, byte* priv_raw, HssPrivKey* priv_key,
    byte* priv_data, const byte* msg, word32 msgSz, byte* sig)
{
    const LmsParams* params = state->params;
    int ret = 0;

    /* Validate fixed parameters for static code analyzers. */
    if ((params->rootLevels == 0) || (params->rootLevels > params->height)) {
        ret = BAD_FUNC_ARG;
    }

    /* Step 1. Part 2: Check for total key exhaustion. */
    if ((ret == 0) && (!wc_hss_sigsleft(params, priv_raw))) {
        ret = KEY_EXHAUSTED_E;
    }

    if ((ret == 0) && (!priv_key->inited)) {
        /* Initialize the authentication paths and caches for all trees. */
        ret = wc_hss_init_auth_path(state, priv_key, NULL);
    #if !defined(WOLFSSL_LMS_NO_SIG_CACHE) && (LMS_MAX_LEVELS > 1)
        if (ret == 0) {
            ret = wc_hss_presign(state, priv_key);
        }
    #endif /* !WOLFSSL_LMS_NO_SIG_CACHE */
        /* Set initialized flag. */
        priv_key->inited = (ret == 0);
    }
    if (ret == 0) {
        ret = wc_hss_sign_build_sig(state, priv_raw, priv_key, msg, msgSz, sig);
    }
    if (ret == 0) {
        /* Increment index of leaf node to sign with in raw data. */
        wc_lms_idx_inc(priv_raw, HSS_Q_LEN);
    }
    /* Check we will produce another signature. */
    if ((ret == 0) && wc_hss_sigsleft(params, priv_raw)) {
        /* Update the expanded private key data. */
        ret = wc_hss_expand_private_key(state, priv_key->priv, priv_raw, 1);
        if (ret == 0) {
            /* Update authentication path and caches for all trees. */
            ret = wc_hss_update_auth_path(state, priv_key, priv_raw,
                params->levels);
        }
    }
    if (ret == 0) {
        /* Store the updated private key data. */
        wc_hss_priv_data_store(state->params, priv_key, priv_data);
    }

    return ret;
}
#endif

/* Check whether key is exhausted.
 *
 * First 8 bytes of raw key is the index.
 * Check index is less than count of leaf nodes.
 *
 * @param [in] params    LMS parameters.
 * @param [in] priv_raw  HSS raw private key.
 * @return  1 when signature possible.
 * @return  0 when private key exhausted.
 */
int wc_hss_sigsleft(const LmsParams* params, const byte* priv_raw)
{
    w64wrapper q;
    w64wrapper cnt;

    /* Get current q - next leaf index to sign with. */
    ato64(priv_raw, &q);
    /* 1 << total_height = total leaf nodes. */
    cnt = w64ShiftLeft(w64From32(0, 1), params->levels * params->height);
    /* Check q is less than total leaf node count. */
    return w64LT(q, cnt);
}
#endif /* !WOLFSSL_LMS_VERIFY_ONLY */

/* Verify message using HSS.
 *
 * Section 6.3. Signature Verification
 *  1. Nspk = strTou32(first four bytes of S)
 *  2. if Nspk+1 is not equal to the number of levels L in pub:
 *  3.   return INVALID
 *  4. key = pub
 *  5. for (i = 0; i < Nspk; i = i + 1) {
 *  6.   sig = siglist[i]
 *  7.   msg = publist[i]
 *  8.   if (lms_verify(msg, key, sig) != VALID):
 *  9.     return INVALID
 * 10.   key = msg
 * 11. }
 * 12. return lms_verify(message, key, siglist[Nspk])
 *
 * @param [in, out] state  LMS state.
 * @param [in]      pub    HSS public key.
 * @param [in]      msg    Message to rifyn.
 * @param [in]      msgSz  Length of message in bytes.
 * @param [in]      sig    Signature of message.
 * @return  0 on success.
 * @return  SIG_VERFIY_E on failure.
 */
int wc_hss_verify(LmsState* state, const byte* pub, const byte* msg,
    word32 msgSz, const byte* sig)
{
    const LmsParams* params = state->params;
    int ret = 0;
    word32 nspk;
    const byte* key = pub + LMS_L_LEN;
    word32 levels;

    /* Get number of levels from public key. */
    ato32(pub, &levels);
    /* Line 1: Get number of signed public keys from signature. */
    ato32(sig, &nspk);
    /* Line 6 (First iteration): Move to start of next signature. */
    sig += LMS_L_LEN;

    /* Line 2: Verify that pub and signature match in levels. */
    if (nspk + 1 != levels) {
        /* Line 3: Return invalid signature. */
        ret = SIG_VERIFY_E;
    }
    if (ret == 0) {
        word32 i;

        /* Line 5: For all but last LMS signature. */
        for (i = 0; (ret == 0) && (i < nspk); i++) {
            /* Line 7: Get start of public key in signature. */
            const byte* pubList = sig + LMS_Q_LEN + LMS_TYPE_LEN +
                LMS_MAX_NODE_LEN + params->p * LMS_MAX_NODE_LEN + LMS_TYPE_LEN +
                params->height * LMS_MAX_NODE_LEN;
            /* Line 8: Verify the LMS signature with public key as message. */
            ret = wc_lms_verify(state, key, pubList, LMS_PUBKEY_LEN, sig);
            /* Line 10: Next key is from signature. */
            key = pubList;
            /* Line 6: Move to start of next signature. */
            sig = pubList + LMS_PUBKEY_LEN;
        }
    }
    if (ret == 0) {
        /* Line 12: Verify bottom tree with real message. */
        ret = wc_lms_verify(state, key, msg, msgSz, sig);
    }

    return ret;
}

#endif /* WOLFSSL_HAVE_LMS && WOLFSSL_WC_LMS */

