Core Lightning implementation of BOLT #11 invoices - part 3

A BOLT #11 invoice breaks down into 4 parts, as shown below

   HRP      separator     data       checksum
    |           |          |             |
lnbcrt100n      1      pj47g4...      r8rsyy

where:

• HRP stands for Human Readable Part, lnbcrt means it is an invoice for the regtest chain of 10000msat (100n),

• 1 is the separator (last 1 in the string)

• then we have the data part and finally

• the checksum (6 characters) as defined by BIP 173.

Let's run some code!

In Core Lightning, unit tests are standalone programs that can be run individually. They are defined by run-*.c files in test/ subdirectories.

We are going to run lightning:common/test/run-bolt11.c test.

First we compile Core Lightning:

◉ tony@tony:~/clnlive/lightning:[git»(HEAD detached at v23.11)]
$ ./configure --disable-rust
...
◉ tony@tony:~/clnlive/lightning:[git»(HEAD detached at v23.11)]
$ make -j4

Then we run the test like this:

◉ tony@tony:~/clnlive/lightning:[git»(HEAD detached at v23.11)]
$ ./common/test/run-bolt11

As the test passed successfully, we got no output.

Now let's modify run-bolt11.c file and make it fail.

To do this, at line 731, we change b11->timestamp value from 1496314658 to 1496314600 and we recompile:

◉ tony@tony:~/clnlive/lightning:[git»(HEAD detached at v23.11)]
$ make -j4

Then we see the test failing:

◉ tony@tony:~/clnlive/lightning:[git»(HEAD detached at v23.11)]
$ ./common/test/run-bolt11
run-bolt11: common/test/run-bolt11.c:60: test_b11: Assertion `b11->timestamp == expect_b11->timestamp' failed.
Aborted (core dumped)

If we want to try things in Core Lightning which don't need lightningd to be running, we can add a file starting by run- in a test/ subdirectory, compile it and run it.

This is what we're going to do in order to try bech32_decode function.

Let's create the new file common/test/run-bech32.c which prints foo:

#include "config.h"
#include "../amount.c"
#include "../bech32.c"
#include "../bech32_util.c"
#include "../bolt11.c"
#include "../features.c"
#include "../node_id.c"
#include "../hash_u5.c"
#include "../memleak.c"
#include "../wire/fromwire.c"
#include "../wire/towire.c"
#include <ccan/err/err.h>
#include <common/setup.h>

int main(int argc, char *argv[])
{
        common_setup(argv[0]);

        printf("foo");

        common_shutdown();
}

Thanks Eduardo for mentioning common_setup and common_shutdown functions used in the tests.

We compile it and run it:

◉ tony@tony:~/clnlive/lightning:[git»(HEAD detached at v23.11)]
$ make -j4
◉ tony@tony:~/clnlive/lightning:[git»(HEAD detached at v23.11)]
$ ./common/test/run-bech32
foo

The function that we want to try is bech32_encode and we see that is used in bolt11_encode_ that way:

char *bolt11_encode_(/* ... */)
{
        u5 *data = tal_arr(tmpctx, u5, 0);
        char *hrp, *output;

        /* ... */

        output = tal_arr(ctx, char, strlen(hrp) + tal_count(data) + 8);
        if (!bech32_encode(output, hrp, data, tal_count(data), (size_t)-1,
                           BECH32_ENCODING_BECH32))
                output = tal_free(output);

        return output;
}

We extract the part we are interested in, transform it a little bit such that we encode into a bech32 string the HRP lnbcrt100n with the data part {0, 1, 0} corresponding to {q, p, q} (bech32 characters). Now, the main function of common/test/run-bech32.c is:

/* ... */

int main(int argc, char *argv[])
{
        u5 data[3] = {0, 1, 0};
        char *output;

        common_setup(argv[0]);

        output = tal_arr(tmpctx, char, 10 + 3 + 8);
        bech32_encode(output, "lnbcrt100n", data, 3, (size_t)-1,
                      BECH32_ENCODING_BECH32);

        printf("%s\n", output);

        common_shutdown();
}

Note that (10 + 3 + 8) in tal_arr corresponds to:

• 10: the length of HRP lnbcrt100n,

• 3: the length of data

• 8: 6 for the length of the checksum + 1 for the separator 1 + 1 for the null character terminating the string output.

We compile and run it like this:

◉ tony@tony:~/clnlive/lightning:[git»(HEAD detached at v23.11)]
$ make -j4
◉ tony@tony:~/clnlive/lightning:[git»(HEAD detached at v23.11)]
$ ./common/test/run-bech32
lnbcrt100n1qpq8tr9cv

If we want to decode output string we encoded with bech32_encode we can use bech32_decode_alloc function as follow:

/* ... */

int main(int argc, char *argv[])
{
        /* ... */

        const char *hrp;
        const u5 *data_decoded;
        size_t data_len = 3;

        bech32_decode_alloc(tmpctx, &hrp, &data_decoded, &data_len, output);

        printf("hrp: %s\n", hrp);
        printf("data_decoded: ");
        for (size_t i = 0; i < 3; ++i) {
          printf("%d ", data_decoded[i]);
        }
        printf("\n");

        common_shutdown();
}

Let's compile and run it:

◉ tony@tony:~/work/repos/lightning:[git»(HEAD detached at v23.11)]
$ ./common/test/run-bech32
lnbcrt100n1qpq8tr9cv
hrp: lnbcrt100n
data_decoded: 0 1 0

bech32_encoding in lightning:common/bech32.h

/** Supported encodings. */
typedef enum {
    BECH32_ENCODING_NONE,
    BECH32_ENCODING_BECH32,
    BECH32_ENCODING_BECH32M
} bech32_encoding;

bech32_encode in lightning:common/bech32.h

/** Encode a Bech32 or Bech32m string
 *
 *  Out: output:  Pointer to a buffer of size strlen(hrp) + data_len + 8 that
 *                will be updated to contain the null-terminated Bech32 string.
 *  In: hrp :     Pointer to the null-terminated human readable part.
 *      data :    Pointer to an array of 5-bit values.
 *      data_len: Length of the data array.
 *      max_output_len: Maximum valid length of output (90 for segwit usage).
 *      enc:      Which encoding to use (BECH32_ENCODING_BECH32{,M}).
 *  Returns 1 if successful.
 */
int bech32_encode(
    char *output,
    const char *hrp,
    const uint8_t *data,
    size_t data_len,
    size_t max_output_len,
    bech32_encoding enc
);

bech32_charset in lightning:common/bech32.c

const char bech32_charset[] = "qpzry9x8gf2tvdw0s3jn54khce6mua7l";

bech32_charset_rev in lightning:common/bech32.c

const int8_t bech32_charset_rev[128] = {
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    15, -1, 10, 17, 21, 20, 26, 30,  7,  5, -1, -1, -1, -1, -1, -1,
    -1, 29, -1, 24, 13, 25,  9,  8, 23, -1, 18, 22, 31, 27, 19, -1,
     1,  0,  3, 16, 11, 28, 12, 14,  6,  4,  2, -1, -1, -1, -1, -1,
    -1, 29, -1, 24, 13, 25,  9,  8, 23, -1, 18, 22, 31, 27, 19, -1,
     1,  0,  3, 16, 11, 28, 12, 14,  6,  4,  2, -1, -1, -1, -1, -1
};

bech32_encode in lightning:common/bech32.c

int bech32_encode(char *output, const char *hrp, const uint8_t *data, size_t data_len, size_t max_output_len, bech32_encoding enc) {
    uint32_t chk = 1;
    size_t i = 0;
    while (hrp[i] != 0) {
        int ch = hrp[i];
        if (ch < 33 || ch > 126) {
            return 0;
        }

        if (ch >= 'A' && ch <= 'Z') return 0;
        chk = bech32_polymod_step(chk) ^ (ch >> 5);
        ++i;
    }
    if (i + 7 + data_len > max_output_len) return 0;
    chk = bech32_polymod_step(chk);
    while (*hrp != 0) {
        chk = bech32_polymod_step(chk) ^ (*hrp & 0x1f);
        *(output++) = *(hrp++);
    }
    *(output++) = '1';
    for (i = 0; i < data_len; ++i) {
        if (*data >> 5) return 0;
        chk = bech32_polymod_step(chk) ^ (*data);
        *(output++) = bech32_charset[*(data++)];
    }
    for (i = 0; i < 6; ++i) {
        chk = bech32_polymod_step(chk);
    }
    chk ^= bech32_final_constant(enc);
    for (i = 0; i < 6; ++i) {
        *(output++) = bech32_charset[(chk >> ((5 - i) * 5)) & 0x1f];
    }
    *output = 0;
    return 1;
}

bech32_decode in lightning:common/bech32.c

bech32_encoding bech32_decode(char* hrp, uint8_t *data, size_t *data_len, const char *input, size_t max_input_len) {
    uint32_t chk = 1;
    size_t i;
    size_t input_len = strlen(input);
    size_t hrp_len;
    int have_lower = 0, have_upper = 0;
    if (input_len < 8 || input_len > max_input_len) {
        return BECH32_ENCODING_NONE;
    }
    *data_len = 0;
    while (*data_len < input_len && input[(input_len - 1) - *data_len] != '1') {
        ++(*data_len);
    }
    hrp_len = input_len - (1 + *data_len);
    if (1 + *data_len >= input_len || *data_len < 6) {
        return BECH32_ENCODING_NONE;
    }
    *(data_len) -= 6;
    for (i = 0; i < hrp_len; ++i) {
        int ch = input[i];
        if (ch < 33 || ch > 126) {
            return BECH32_ENCODING_NONE;
        }
        if (ch >= 'a' && ch <= 'z') {
            have_lower = 1;
        } else if (ch >= 'A' && ch <= 'Z') {
            have_upper = 1;
            ch = (ch - 'A') + 'a';
        }
        hrp[i] = ch;
        chk = bech32_polymod_step(chk) ^ (ch >> 5);
    }
    hrp[i] = 0;
    chk = bech32_polymod_step(chk);
    for (i = 0; i < hrp_len; ++i) {
        chk = bech32_polymod_step(chk) ^ (input[i] & 0x1f);
    }
    ++i;
    while (i < input_len) {
        int v = (input[i] & 0x80) ? -1 : bech32_charset_rev[(int)input[i]];
        if (input[i] >= 'a' && input[i] <= 'z') have_lower = 1;
        if (input[i] >= 'A' && input[i] <= 'Z') have_upper = 1;
        if (v == -1) {
            return BECH32_ENCODING_NONE;
        }
        chk = bech32_polymod_step(chk) ^ v;
        if (i + 6 < input_len) {
            data[i - (1 + hrp_len)] = v;
        }
        ++i;
    }
    if (have_lower && have_upper) {
        return BECH32_ENCODING_NONE;
    }
    if (chk == bech32_final_constant(BECH32_ENCODING_BECH32)) {
        return BECH32_ENCODING_BECH32;
    } else if (chk == bech32_final_constant(BECH32_ENCODING_BECH32M)) {
        return BECH32_ENCODING_BECH32M;
    } else {
        return BECH32_ENCODING_NONE;
    }
}

bolt11_encode_ in lightning:common/bolt11.c

/* Encodes, even if it's nonsense. */
char *bolt11_encode_(const tal_t *ctx,
                     const struct bolt11 *b11, bool n_field,
                     bool (*sign)(const u5 *u5bytes,
                                  const u8 *hrpu8,
                                  secp256k1_ecdsa_recoverable_signature *rsig,
                                  void *arg),
                     void *arg)
{
        u5 *data = tal_arr(tmpctx, u5, 0);
        char *hrp, *output;
        u64 amount;
        struct bolt11_field *extra;
        secp256k1_ecdsa_recoverable_signature rsig;
        u8 sig_and_recid[65];
        u8 *hrpu8;
        int recid;

        /* BOLT #11:
         *
         * A writer:
         * - MUST encode `prefix` using the currency required for successful payment.
         * - if a specific minimum `amount` is required for successful payment:
         *   - MUST include that `amount`.
         * - MUST encode `amount` as a positive decimal integer with no leading 0s.
         * - If the `p` multiplier is used the last decimal of `amount` MUST be `0`.
         * - SHOULD use the shortest representation possible, by using the largest multiplier or omitting the multiplier.
         */
        if (b11->msat) {
                char postfix;
                u64 msat = b11->msat->millisatoshis; /* Raw: best-multiplier calc */
                if (msat % MSAT_PER_BTC == 0) {
                        postfix = '\0';
                        amount = msat / MSAT_PER_BTC;
                } else {
                        size_t i;
                        for (i = 0; i < ARRAY_SIZE(multipliers)-1; i++) {
                                if (!(msat * 10 % multipliers[i].m10))
                                        break;
                        }
                        postfix = multipliers[i].letter;
                        amount = msat * 10 / multipliers[i].m10;
                }
                hrp = tal_fmt(tmpctx, "ln%s%"PRIu64"%c",
                              b11->chain->lightning_hrp, amount, postfix);
        } else
                hrp = tal_fmt(tmpctx, "ln%s", b11->chain->lightning_hrp);

        /* BOLT #11:
         *
         * 1. `timestamp`: seconds-since-1970 (35 bits, big-endian)
         * 1. zero or more tagged parts
         * 1. `signature`: Bitcoin-style signature of above (520 bits)
         */
        push_varlen_uint(&data, b11->timestamp, 35);

        /* This is a hack to match the test vectors, *some* of which
         * order differently! */
        if (!dev_bolt11_old_order) {
                if (b11->payment_secret)
                        encode_s(&data, b11->payment_secret);
        }

        /* BOLT #11:
         *
         * if a writer offers more than one of any field type,
         * it... MUST specify the most-preferred field first, followed
         * by less-preferred fields, in order.
         */
        /* Thus we do built-in fields, then extras last. */
        encode_p(&data, &b11->payment_hash);

        /* BOLT #11:
         * A writer:
         *...
         *    - MUST include either exactly one `d` or exactly one `h` field.
         */
        /* We sometimes keep description around (to put in db), so prefer hash */
        if (b11->description_hash)
                encode_h(&data, b11->description_hash);
        else if (b11->description)
                encode_d(&data, b11->description);

        if (b11->metadata)
                encode_m(&data, b11->metadata);

        if (n_field)
                encode_n(&data, &b11->receiver_id);

        if (dev_bolt11_old_order) {
                if (b11->payment_secret)
                        encode_s(&data, b11->payment_secret);
        }

        if (b11->expiry != DEFAULT_X)
                encode_x(&data, b11->expiry);

        /* BOLT #11:
         *   - SHOULD include one `c` field (`min_final_cltv_expiry_delta`).
         *...
         * A reader:
         *...
         *   - if the `c` field (`min_final_cltv_expiry_delta`) is not provided:
         *     - MUST use an expiry delta of at least 18 when making the payment
         */
        if (b11->min_final_cltv_expiry != 18)
                encode_c(&data, b11->min_final_cltv_expiry);

        for (size_t i = 0; i < tal_count(b11->fallbacks); i++)
                encode_f(&data, b11->fallbacks[i]);

        for (size_t i = 0; i < tal_count(b11->routes); i++)
                encode_r(&data, b11->routes[i]);

        maybe_encode_9(&data, b11->features, b11->metadata != NULL);

        list_for_each(&b11->extra_fields, extra, list)
                if (!encode_extra(&data, extra))
                        return NULL;

        /* FIXME: towire_ should check this? */
        if (tal_count(data) > 65535)
                return NULL;

        /* Need exact length here */
        hrpu8 = tal_dup_arr(tmpctx, u8, (const u8 *)hrp, strlen(hrp), 0);
        if (!sign(data, hrpu8, &rsig, arg))
                return NULL;

        secp256k1_ecdsa_recoverable_signature_serialize_compact(
                secp256k1_ctx,
                sig_and_recid,
                &recid,
                &rsig);
        sig_and_recid[64] = recid;

        bech32_push_bits(&data, sig_and_recid, sizeof(sig_and_recid) * CHAR_BIT);

        output = tal_arr(ctx, char, strlen(hrp) + tal_count(data) + 8);
        if (!bech32_encode(output, hrp, data, tal_count(data), (size_t)-1,
                           BECH32_ENCODING_BECH32))
                output = tal_free(output);

        return output;
}

bech32_decode_alloc in lightning:common/bolt11.c

static bool bech32_decode_alloc(const tal_t *ctx,
                                const char **hrp_ret,
                                const u5 **data_ret,
                                size_t *data_len,
                                const char *str)
{
        char *hrp = tal_arr(ctx, char, strlen(str) - 6);
        u5 *data = tal_arr(ctx, u5, strlen(str) - 8);

        if (bech32_decode(hrp, data, data_len, str, (size_t)-1)
            != BECH32_ENCODING_BECH32) {
                tal_free(hrp);
                tal_free(data);
                return false;
        }

        /* We needed temporaries because these are const */
        *hrp_ret = hrp;
        *data_ret = data;
        return true;
}

u5 in lightning:common/hash_u5.h

/* Type to annotate a 5 bit value. */
typedef unsigned char u5;

tmpctx in lightning:common/utils.c

const tal_t *tmpctx;

common_setup in lightning:common/setup.c

void common_setup(const char *argv0)
{
        int wally_ret;

        setup_locale();
        err_set_progname(argv0);

        /* We rely on libsodium for some of the crypto stuff, so we'd better
         * not start if it cannot do its job correctly. */
        if (sodium_init() == -1)
                errx(1, "Could not initialize libsodium. Maybe not enough entropy"
                     " available ?");

        /* We set up Wally, the bitcoin wallet lib */
        wally_ret = wally_init(0);
        if (wally_ret != WALLY_OK)
                errx(1, "Error initializing libwally: %i", wally_ret);
        wally_ret = wally_set_operations(&wally_tal_ops);
        if (wally_ret != WALLY_OK)
                errx(1, "Error setting libwally operations: %i", wally_ret);
        secp256k1_ctx = wally_get_secp_context();

        /* Make htable* use tal for the tables themselves. */
        htable_set_allocator(htable_tal, htable_tal_free);

        setup_tmpctx();
}

common_shutdown in lightning:common/setup.c

void common_shutdown(void)
{
        const char *p = taken_any();
        if (p)
                errx(1, "outstanding taken(): %s", p);
        take_cleanup();
        tal_free(tmpctx);
        wally_cleanup(0);
        tal_free(wally_tal_ctx);
        autodata_cleanup();
}

setup_tmpctx in lightning:common/utils.c

/* Initial creation of tmpctx. */
void setup_tmpctx(void)
{
        tmpctx = tal_arr_label(NULL, char, 0, "tmpctx");
}

#include "config.h"
#include "../amount.c"
#include "../bech32.c"
#include "../bech32_util.c"
#include "../bolt11.c"
#include "../features.c"
#include "../node_id.c"
#include "../hash_u5.c"
#include "../memleak.c"
#include "../wire/fromwire.c"
#include "../wire/towire.c"
#include <ccan/err/err.h>
#include <common/setup.h>

int main(int argc, char *argv[])
{
        u5 data[3] = {0, 1, 0};
        char *output;

        common_setup(argv[0]);

        output = tal_arr(tmpctx, char, 10 + 3 + 8);
        bech32_encode(output, "lnbcrt100n", data, 3, (size_t)-1,
                BECH32_ENCODING_BECH32);

        printf("%s\n", output);

        const char *hrp;
        const u5 *data_decode;
        size_t data_len = 3;

        bech32_decode_alloc(tmpctx, &hrp, &data_decode, &data_len, output);

        printf("hrp: %s\n", hrp);
        printf("data_decode: ");
        for (size_t i = 0; i < 3; ++i) {
          printf("%d ", data_decode[i]);
        }
        printf("\n");

        common_shutdown();
}