silentpayments: add benchmarks for scanning

diff --git a/src/bench.c b/src/bench.c
index f561ad1..ac2054a 100644
--- a/src/bench.c
+++ b/src/bench.c
@@ -32,6 +32,10 @@ static void help(const char *executable_path, int default_iters) {
     printf("    - ElligatorSwift (optional module)\n");
 #endif
 
+#ifdef ENABLE_MODULE_SILENTPAYMENTS
+    printf("    - Silent payments (optional module)\n");
+#endif
+
     printf("\n");
     printf("The default number of iterations for each benchmark is %d. This can be\n", default_iters);
     printf("customized using the SECP256K1_BENCH_ITERS environment variable.\n");
@@ -39,33 +43,39 @@ static void help(const char *executable_path, int default_iters) {
     printf("Usage: %s [args]\n", executable_path);
     printf("By default, all benchmarks will be run.\n");
     printf("args:\n");
-    printf("    help              : display this help and exit\n");
-    printf("    ecdsa             : all ECDSA algorithms--sign, verify, recovery (if enabled)\n");
-    printf("    ecdsa_sign        : ECDSA siging algorithm\n");
-    printf("    ecdsa_verify      : ECDSA verification algorithm\n");
-    printf("    ec                : all EC public key algorithms (keygen)\n");
-    printf("    ec_keygen         : EC public key generation\n");
+    printf("    help                                 : display this help and exit\n");
+    printf("    ecdsa                                : all ECDSA algorithms--sign, verify, recovery (if enabled)\n");
+    printf("    ecdsa_sign                           : ECDSA siging algorithm\n");
+    printf("    ecdsa_verify                         : ECDSA verification algorithm\n");
+    printf("    ec                                   : all EC public key algorithms (keygen)\n");
+    printf("    ec_keygen                            : EC public key generation\n");
 
 #ifdef ENABLE_MODULE_RECOVERY
-    printf("    ecdsa_recover     : ECDSA public key recovery algorithm\n");
+    printf("    ecdsa_recover                        : ECDSA public key recovery algorithm\n");
 #endif
 
 #ifdef ENABLE_MODULE_ECDH
-    printf("    ecdh              : ECDH key exchange algorithm\n");
+    printf("    ecdh                                 : ECDH key exchange algorithm\n");
 #endif
 
 #ifdef ENABLE_MODULE_SCHNORRSIG
-    printf("    schnorrsig        : all Schnorr signature algorithms (sign, verify)\n");
-    printf("    schnorrsig_sign   : Schnorr sigining algorithm\n");
-    printf("    schnorrsig_verify : Schnorr verification algorithm\n");
+    printf("    schnorrsig                           : all Schnorr signature algorithms (sign, verify)\n");
+    printf("    schnorrsig_sign                      : Schnorr sigining algorithm\n");
+    printf("    schnorrsig_verify                    : Schnorr verification algorithm\n");
 #endif
 
 #ifdef ENABLE_MODULE_ELLSWIFT
-    printf("    ellswift          : all ElligatorSwift benchmarks (encode, decode, keygen, ecdh)\n");
-    printf("    ellswift_encode   : ElligatorSwift encoding\n");
-    printf("    ellswift_decode   : ElligatorSwift decoding\n");
-    printf("    ellswift_keygen   : ElligatorSwift key generation\n");
-    printf("    ellswift_ecdh     : ECDH on ElligatorSwift keys\n");
+    printf("    ellswift                             : all ElligatorSwift benchmarks (encode, decode, keygen, ecdh)\n");
+    printf("    ellswift_encode                      : ElligatorSwift encoding\n");
+    printf("    ellswift_decode                      : ElligatorSwift decoding\n");
+    printf("    ellswift_keygen                      : ElligatorSwift key generation\n");
+    printf("    ellswift_ecdh                        : ECDH on ElligatorSwift keys\n");
+#endif
+
+#ifdef ENABLE_MODULE_SILENTPAYMENTS
+    printf("    silentpayments                       : all Silent payments benchmarks (scan_nomatch, scan_worstcase)\n");
+    printf("    silentpayments_scan_nomatch          : Silent payments scanning common case (no match)\n");
+    printf("    silentpayments_scan_worstcase        : Silent payments scanning worst case (block-sized tx, all match)\n");
 #endif
 
     printf("\n");
@@ -170,6 +180,10 @@ static void bench_keygen_run(void *arg, int iters) {
 # include "modules/ellswift/bench_impl.h"
 #endif
 
+#ifdef ENABLE_MODULE_SILENTPAYMENTS
+# include "modules/silentpayments/bench_impl.h"
+#endif
+
 int main(int argc, char** argv) {
     int i;
     secp256k1_pubkey pubkey;
@@ -182,7 +196,8 @@ int main(int argc, char** argv) {
     char* valid_args[] = {"ecdsa", "verify", "ecdsa_verify", "sign", "ecdsa_sign", "ecdh", "recover",
                          "ecdsa_recover", "schnorrsig", "schnorrsig_verify", "schnorrsig_sign", "ec",
                          "keygen", "ec_keygen", "ellswift", "encode", "ellswift_encode", "decode",
-                         "ellswift_decode", "ellswift_keygen", "ellswift_ecdh"};
+                         "ellswift_decode", "ellswift_keygen", "ellswift_ecdh", "silentpayments",
+                         "silentpayments_scan_nomatch", "silentpayments_scan_worstcase"};
     int invalid_args = have_invalid_args(argc, argv, valid_args, ARRAY_SIZE(valid_args));
 
     int default_iters = 20000;
@@ -240,6 +255,15 @@ int main(int argc, char** argv) {
     }
 #endif
 
+#ifndef ENABLE_MODULE_SILENTPAYMENTS
+    if (have_flag(argc, argv, "silentpayments") || have_flag(argc, argv, "silentpayments_scan_nomatch") ||
+        have_flag(argc, argv, "silentpayments_scan_worstcase")) {
+        fprintf(stderr, "./bench: silentpayments module not enabled.\n");
+        fprintf(stderr, "See README.md for configuration instructions.\n\n");
+        return EXIT_FAILURE;
+    }
+#endif
+
     /* ECDSA benchmark */
     data.ctx = secp256k1_context_create(SECP256K1_CONTEXT_NONE);
 
@@ -284,5 +308,11 @@ int main(int argc, char** argv) {
     run_ellswift_bench(iters, argc, argv);
 #endif
 
+#ifdef ENABLE_MODULE_SILENTPAYMENTS
+    /* SilentPayments benchmarks */
+    run_silentpayments_bench(iters, argc, argv);
+#endif
+
+
     return EXIT_SUCCESS;
 }
diff --git a/src/bench.h b/src/bench.h
index f88277a..948e8db 100644
--- a/src/bench.h
+++ b/src/bench.h
@@ -71,7 +71,7 @@ static void print_number(const int64_t x) {
         buffer[--ptr] = '-';
         g++;
     }
-    printf("%5.*s", g, &buffer[ptr]); /* Prints integer part */
+    printf("%8.*s", g, &buffer[ptr]); /* Prints integer part */
     printf("%-*s", FP_EXP, &buffer[ptr + g]); /* Prints fractional part */
 }
 
@@ -100,7 +100,7 @@ static void run_benchmark(char *name, void (*benchmark)(void*, int), void (*setu
         sum += total;
     }
     /* ',' is used as a column delimiter */
-    printf("%-30s, ", name);
+    printf("%-40s, ", name);
     print_number(min * FP_MULT / iter);
     printf("   , ");
     print_number(((sum * FP_MULT) / count) / iter);
@@ -167,7 +167,7 @@ static void print_output_table_header_row(void) {
     char* min_str = "    Min(us)    "; /* center alignment */
     char* avg_str = "    Avg(us)    ";
     char* max_str = "    Max(us)    ";
-    printf("%-30s,%-15s,%-15s,%-15s\n", bench_str, min_str, avg_str, max_str);
+    printf("%-40s,%-18s,%-18s,%-18s\n", bench_str, min_str, avg_str, max_str);
     printf("\n");
 }
 
diff --git a/src/modules/silentpayments/Makefile.am.include b/src/modules/silentpayments/Makefile.am.include
index 842a33e..d377974 100644
--- a/src/modules/silentpayments/Makefile.am.include
+++ b/src/modules/silentpayments/Makefile.am.include
@@ -1,2 +1,3 @@
 include_HEADERS += include/secp256k1_silentpayments.h
 noinst_HEADERS += src/modules/silentpayments/main_impl.h
+noinst_HEADERS += src/modules/silentpayments/bench_impl.h
diff --git a/src/modules/silentpayments/bench_impl.h b/src/modules/silentpayments/bench_impl.h
new file mode 100644
index 0000000..2bb706c
--- /dev/null
+++ b/src/modules/silentpayments/bench_impl.h
@@ -0,0 +1,217 @@
+/***********************************************************************
+ * Copyright (c) 2024 josibake                                         *
+ * Distributed under the MIT software license, see the accompanying    *
+ * file COPYING or https://www.opensource.org/licenses/mit-license.php.*
+ ***********************************************************************/
+
+#ifndef SECP256K1_MODULE_SILENTPAYMENTS_BENCH_H
+#define SECP256K1_MODULE_SILENTPAYMENTS_BENCH_H
+
+#include "../../../include/secp256k1_silentpayments.h"
+
+#include "../../util.h"
+
+/* maximum non-coinbase taproot outputs per block: largest N for 1-in-N-out P2TR transaction
+ * that has a vsize <= (1_000_000 - 81 - 64) [https://bitcoin.stackexchange.com/a/122952]
+ * (needed for constructing the "worst-case scanning attack", where a single
+ *  tx fills up a full bock of taproot outputs that all go to the same scankey group) */
+#define MAX_P2TR_OUTPUTS_PER_BLOCK 23250
+
+#define SP_BENCH_MAX_INPUTS  1
+#define SP_BENCH_MAX_OUTPUTS MAX_P2TR_OUTPUTS_PER_BLOCK
+
+typedef struct {
+    secp256k1_context *ctx;
+    secp256k1_pubkey spend_pubkey;
+    unsigned char scan_key[32];
+    secp256k1_xonly_pubkey *tx_outputs;
+    secp256k1_xonly_pubkey **tx_outputs_ptrs;
+    secp256k1_xonly_pubkey tx_inputs[SP_BENCH_MAX_INPUTS];
+    const secp256k1_xonly_pubkey *tx_inputs_ptrs[SP_BENCH_MAX_INPUTS];
+    secp256k1_silentpayments_found_output *found_outputs;
+    secp256k1_silentpayments_found_output **found_outputs_ptrs;
+    unsigned char smallest_outpoint[36];
+    unsigned char label[33];
+    unsigned char label_tweak[32];
+    int num_outputs;
+    int num_matches;
+} bench_silentpayments_data;
+
+const unsigned char* label_lookup(const unsigned char* key, const void* cache_ptr) {
+    bench_silentpayments_data *data = (bench_silentpayments_data*)cache_ptr;
+    if (secp256k1_memcmp_var(key, data->label, 33) == 0) {
+        return data->label_tweak;
+    }
+    return NULL;
+}
+
+static void bench_silentpayments_scan_setup(void* arg) {
+    int i;
+    bench_silentpayments_data *data = (bench_silentpayments_data*)arg;
+    const unsigned char smallest_outpoint[36] = {
+        0x16, 0x9e, 0x1e, 0x83, 0xe9, 0x30, 0x85, 0x33, 0x91,
+        0xbc, 0x6f, 0x35, 0xf6, 0x05, 0xc6, 0x75, 0x4c, 0xfe,
+        0xad, 0x57, 0xcf, 0x83, 0x87, 0x63, 0x9d, 0x3b, 0x40,
+        0x96, 0xc5, 0x4f, 0x18, 0xf4, 0x00, 0x00, 0x00, 0x00,
+    };
+    const unsigned char spend_pubkey[33] = {
+        0x02,0xee,0x97,0xdf,0x83,0xb2,0x54,0x6a,
+        0xf5,0xa7,0xd0,0x62,0x15,0xd9,0x8b,0xcb,
+        0x63,0x7f,0xe0,0x5d,0xd0,0xfa,0x37,0x3b,
+        0xd8,0x20,0xe6,0x64,0xd3,0x72,0xde,0x9a,0x01
+    };
+    const unsigned char scan_key[32] = {
+        0xa8,0x90,0x54,0xc9,0x5b,0xe3,0xc3,0x01,
+        0x56,0x65,0x74,0xf2,0xaa,0x93,0xad,0xe0,
+        0x51,0x85,0x09,0x03,0xa6,0x9c,0xbd,0xd1,
+        0xd4,0x7e,0xae,0x26,0x3d,0x7b,0xc0,0x31
+    };
+    unsigned char scalar[32];
+    secp256k1_keypair input_keypair;
+    size_t pubkeylen = 33;
+
+    for (i = 0; i < 32; i++) {
+        scalar[i] = i + 1;
+    }
+    /* Create the first input public key for the full scan from the scalar. */
+    CHECK(secp256k1_keypair_create(data->ctx, &input_keypair, scalar));
+    CHECK(secp256k1_keypair_xonly_pub(data->ctx, &data->tx_inputs[0], NULL, &input_keypair));
+    data->tx_inputs_ptrs[0] = &data->tx_inputs[0];
+    CHECK(secp256k1_ec_pubkey_parse(data->ctx, &data->spend_pubkey, spend_pubkey, pubkeylen));
+    memcpy(data->scan_key, scan_key, 32);
+    memcpy(data->smallest_outpoint, smallest_outpoint, 36);
+
+    /* prepare transaction outputs for the "worst-case scanning attack",
+     * can be used for typical scanning scenarios as well */
+    {
+        secp256k1_silentpayments_recipient *recipients = malloc(sizeof(secp256k1_silentpayments_recipient) * data->num_outputs);
+        const secp256k1_silentpayments_recipient **recipients_ptrs = malloc(sizeof(secp256k1_silentpayments_recipient*) * data->num_outputs);
+        const secp256k1_keypair *keypairs_ptrs[SP_BENCH_MAX_INPUTS];
+        secp256k1_pubkey scan_pubkey, other_scan_pubkey;
+        unsigned char other_scan_seckey[32] = {99};
+        secp256k1_silentpayments_label label;
+        secp256k1_pubkey labeled_spend_pubkey;
+        int index_first_k;
+
+        CHECK(data->num_outputs <= SP_BENCH_MAX_OUTPUTS);
+        CHECK(data->num_matches <= data->num_outputs);
+        index_first_k = data->num_outputs - data->num_matches;
+
+        CHECK(secp256k1_ec_pubkey_create(data->ctx, &scan_pubkey, data->scan_key));
+        CHECK(secp256k1_ec_pubkey_create(data->ctx, &other_scan_pubkey, other_scan_seckey));
+
+        CHECK(secp256k1_silentpayments_recipient_label_create(data->ctx, &label, data->label_tweak, data->scan_key, 0));
+        CHECK(secp256k1_silentpayments_recipient_label_serialize(data->ctx, data->label, &label));
+        CHECK(secp256k1_silentpayments_recipient_create_labeled_spend_pubkey(data->ctx,
+            &labeled_spend_pubkey, &data->spend_pubkey, &label));
+
+        data->tx_outputs = malloc(sizeof(secp256k1_xonly_pubkey) * data->num_outputs);
+        data->tx_outputs_ptrs = malloc(sizeof(secp256k1_xonly_pubkey*) * data->num_outputs);
+        data->found_outputs = malloc(sizeof(secp256k1_silentpayments_found_output) * data->num_outputs);
+        data->found_outputs_ptrs = malloc(sizeof(secp256k1_silentpayments_found_output*) * data->num_outputs);
+
+        keypairs_ptrs[0] = &input_keypair;
+        for (i = 0; i < data->num_outputs; i++) {
+            data->tx_outputs_ptrs[i] = &data->tx_outputs[i];
+            recipients_ptrs[i] = &recipients[i];
+            recipients[i].spend_pubkey = labeled_spend_pubkey;
+            if (i >= index_first_k) {
+                recipients[i].scan_pubkey = scan_pubkey;
+            } else {
+                unsigned char tweak[32] = {0};
+                tweak[31] = 1;
+                /* tweak non-match scan pubkey in order to create single-recipient groups
+                 * (we want to avoid running into the recipient group protocol limit) */
+                CHECK(secp256k1_ec_pubkey_tweak_add(data->ctx, &other_scan_pubkey, tweak));
+                recipients[i].scan_pubkey = other_scan_pubkey;
+            }
+            recipients[i].index = i;
+        }
+        CHECK(secp256k1_silentpayments_sender_create_outputs(data->ctx, data->tx_outputs_ptrs, recipients_ptrs,
+            data->num_outputs, data->smallest_outpoint, keypairs_ptrs, SP_BENCH_MAX_INPUTS, NULL, 0));
+
+        for (i = 0; i < data->num_outputs; i++) {
+            data->found_outputs_ptrs[i] = &data->found_outputs[i];
+        }
+        /* reverse outputs within k group to simulate worst-case */
+        for (i = 0; i < data->num_matches / 2; i++) {
+            int pos = index_first_k + i;
+            secp256k1_xonly_pubkey *tmp = data->tx_outputs_ptrs[pos];
+            data->tx_outputs_ptrs[pos] = data->tx_outputs_ptrs[data->num_outputs - i - 1];
+            data->tx_outputs_ptrs[data->num_outputs - i - 1] = tmp;
+        }
+
+        free(recipients_ptrs);
+        free(recipients);
+    }
+}
+
+static void bench_silentpayments_scan_teardown(void* arg, int iters) {
+    bench_silentpayments_data *data = (bench_silentpayments_data*)arg;
+    (void)iters;
+
+    free(data->tx_outputs);
+    free(data->tx_outputs_ptrs);
+    free(data->found_outputs);
+    free(data->found_outputs_ptrs);
+}
+
+static void bench_silentpayments_scan(void* arg, int iters) {
+    bench_silentpayments_data *data = (bench_silentpayments_data*)arg;
+    secp256k1_silentpayments_prevouts_summary prevouts_summary;
+    uint32_t n_found = 0;
+    int i;
+    const secp256k1_silentpayments_label_lookup label_lookup_fn = label_lookup;
+    const void *label_context = data;
+
+    CHECK(data->num_outputs <= SP_BENCH_MAX_OUTPUTS);
+
+    for (i = 0; i < iters; i++) {
+        CHECK(secp256k1_silentpayments_recipient_prevouts_summary_create(data->ctx, &prevouts_summary,
+            data->smallest_outpoint, data->tx_inputs_ptrs, SP_BENCH_MAX_INPUTS, NULL, 0));
+        CHECK(secp256k1_silentpayments_recipient_scan_outputs(data->ctx,
+            data->found_outputs_ptrs, &n_found,
+            (const secp256k1_xonly_pubkey**)data->tx_outputs_ptrs, data->num_outputs,
+            data->scan_key, &prevouts_summary, &data->spend_pubkey,
+            label_lookup_fn, label_context)
+        );
+        CHECK(n_found == (uint32_t)data->num_matches);
+    }
+}
+
+static void run_silentpayments_bench(int iters, int argc, char** argv) {
+    bench_silentpayments_data data;
+    int d = argc == 1;
+
+    data.ctx = secp256k1_context_create(SECP256K1_CONTEXT_NONE);
+
+    if (d || have_flag(argc, argv, "silentpayments") || have_flag(argc, argv, "silentpayments_scan_nomatch")) {
+        const int num_outputs_bench[] = {2, 5, 10, 100, 1000, 2323, MAX_P2TR_OUTPUTS_PER_BLOCK};
+        size_t o;
+        for (o = 0; o < ARRAY_SIZE(num_outputs_bench); o++) {
+            const int num_outputs = num_outputs_bench[o];
+            char str[64];
+            data.num_outputs = num_outputs;
+            data.num_matches = 0;
+            sprintf(str, "silentpayments_scan_nomatch_N=%i", num_outputs);
+            run_benchmark(str, bench_silentpayments_scan, bench_silentpayments_scan_setup, bench_silentpayments_scan_teardown, &data, 10, num_outputs < 100 ? iters : 1);
+        }
+    }
+
+    if (d || have_flag(argc, argv, "silentpayments") || have_flag(argc, argv, "silentpayments_scan_worstcase")) {
+        size_t k;
+        const int num_matches_bench[] = {10, 100, 1000, 2323};
+        for (k = 0; k < ARRAY_SIZE(num_matches_bench); k++) {
+            const int num_matches = num_matches_bench[k];
+            char str[64];
+            data.num_outputs = MAX_P2TR_OUTPUTS_PER_BLOCK;
+            data.num_matches = num_matches;
+            sprintf(str, "silentpayments_scan_worstcase_K=%i", num_matches);
+            run_benchmark(str, bench_silentpayments_scan, bench_silentpayments_scan_setup, bench_silentpayments_scan_teardown, &data, 3, 1);
+        }
+    }
+
+    secp256k1_context_destroy(data.ctx);
+}
+
+#endif /* SECP256K1_MODULE_SILENTPAYMENTS_BENCH_H */