Add BIP352 module (take 3) #1698

 *                label_context: pointer to a label context object (NULL if
 *                               labels are not used or context is not needed)

(was changed after #1519 (review))

Thanks, I've updated the comment and added a test case for the (lookup, NULL) argument combination.

I think it should be documented for how long the returned pointer from label_lookup should be valid. I think it is obvious it should be valid until the next call of label_lookup, but it is currently not clear (from the docs) whether it should remain valid until secp256k1_silentpayments_recipient_scan_outputs returns. The current implementation of secp256k1_silentpayments_recipient_scan_outputs does not need this (from looking at the code) and in a safe Rust abstraction for this function (code, does contain some outdated comments) suggested for https://github.com/rust-bitcoin/rust-secp256k1/pull/721 (WIP bindings to this pull request's code) I relied on this not being a requirement (though that can be changed).

Hi @antonilol , thanks for the review and bindings code! Agreed that this should be documented. How about something like:

diff --git a/include/secp256k1_silentpayments.h b/include/secp256k1_silentpayments.h
index 2e71405..11fa596 100644
--- a/include/secp256k1_silentpayments.h
+++ b/include/secp256k1_silentpayments.h
@@ -311,6 +311,11 @@ typedef struct secp256k1_silentpayments_found_output {
  *  the recipient uses labels. This allows for checking if a label exists in
  *  the recipients label cache and retrieving the label tweak during scanning.
  *
+ *  If used, the `label_lookup` function must return a pointer to a 32-byte label
+ *  tweak if the label is found, or NULL otherwise. The returned pointer must remain
+ *  valid until the next call to `label_lookup` or until the function returns,
+ *  whichever comes first. It is not retained beyond that.
+ *
  *  For the labels cache, `secp256k1_silentpayments_recipient_create_label`
  *  can be used.
  *

I think the above is the most precise requirement, but perhaps a simpler alternative would be to require that the returned pointer (and labels cache, if used) be valid until _scan_outputs returns? You mention you rely on this not being the case today, but does this make a material difference if we do require that the returned pointer and labels cache be valid for the lifetime of the _scan_outputs function?

Looks good!

I think the above is the most precise requirement, but perhaps a simpler alternative would be to require that the returned pointer (and labels cache, if used) be valid until _scan_outputs returns? You mention you rely on this not being the case today, but does this make a material difference if we do require that the returned pointer and labels cache be valid for the lifetime of the _scan_outputs function?

This depends on the function signature on the Rust side, I have considered 2 cases. The difference is in what the user has to return from label_lookup.

First, there is the one in the proof of concept binding I mentioned here, the user has to return any byte array of length 32 or nothing (translates to NULL pointer). The C side accepts a pointer so the Rust side stores this byte array on the stack and gives the C side a pointer to that. This place on the stack is reused, so requiring that the pointer lives for longer than until the next call of label_lookup means that previous return values need to be kept and some dynamic allocation would be needed. I see this as the easiest for user to use. As far as I can tell no borrow checker issues can arise from this design.

Second, the user has to return a reference to a byte array of length 32 or nothing. The reference is required to live for as long as the function runs. This is because in Rust it is not (yet) possible to declare the reference is only required to live until the next call of label_lookup. This is simple to implement because it is basically a pointer cast and is compatible with _scan_outputs needing pointers to be valid for the lifetime of the function. This one is harder to use, especially for label_lookups that are not simply looking up in a data structure. Returning a reference to any byte array that is not stored outside the function's stack frame is not allowed and storing it on the fly like the first case here probably requires the user to use unsafe code (needs a data structure that allows adding elements while there exist references to its existing elements because the reference is required to live for as long as the function runs) and has the same need for dynamic allocation like the first case can have.

The validity of the context pointer should be completely up to the users of the C library (I consider the Rust binding to also be a user of the C library).

I will also link this discussion in the Rust bindings pull request.

Thanks for the detailed explanation! As I was thinking through this, it also occurred to me requiring the pointers to be valid for the lifetime of _scan_outputs would require keeping around pointers to every label found, even after they had been used by _scan_outputs. This seems undesirable, e.g., imagine a transaction with ~15k labeled outputs all paying to a single recipient. Your explanation seems to confirm my understanding.

in commit de508a78ac66b93b0ff83b419cc6e149950ecc25: took a look into these TODOs, I think the following patch would tackle them (note that the serialize/parse-roundtrip looks superfluous at first sight, but it is needed to set the "combined" flag in the public data, which is ARG_CHECKEDed for 1 in _recipient_create_shared_secret):

diff --git a/src/ctime_tests.c b/src/ctime_tests.c
index 17964b9..83596a3 100644
--- a/src/ctime_tests.c
+++ b/src/ctime_tests.c
@@ -116,6 +116,8 @@ static void run_tests(secp256k1_context *ctx, unsigned char *key) {
     const secp256k1_xonly_pubkey *xonly_pubkeys[1];
     secp256k1_pubkey plain_pubkey;
     const secp256k1_pubkey *plain_pubkeys[1];
+    unsigned char public_data_ser[33] = { 0 };
+    unsigned char shared_secret[33] = { 0 };
 #endif
 
     for (i = 0; i < 32; i++) {
@@ -338,9 +340,10 @@ static void run_tests(secp256k1_context *ctx, unsigned char *key) {
     ret = secp256k1_silentpayments_recipient_scan_outputs(ctx, found_outputs, &n_found_outputs, tx_outputs, 1, key, &public_data, &recipient.labeled_spend_pubkey, NULL, NULL);
     CHECK(ret == 1);
 
-    /* TODO: this fails */
-    /* CHECK(secp256k1_silentpayments_recipient_create_shared_secret(ctx, shared_secret, key, &public_data)); */
-    /* TODO: test secp256k1_silentpayments_recipient_create_output_pubkey */
+    CHECK(secp256k1_silentpayments_recipient_public_data_serialize(ctx, public_data_ser, &public_data));
+    CHECK(secp256k1_silentpayments_recipient_public_data_parse(ctx, &public_data, public_data_ser));
+    CHECK(secp256k1_silentpayments_recipient_create_shared_secret(ctx, shared_secret, key, &public_data));
+    CHECK(secp256k1_silentpayments_recipient_create_output_pubkey(ctx, &xonly_pubkey, shared_secret, &recipient.labeled_spend_pubkey, 0));
 
 #endif
 }
diff --git a/src/modules/silentpayments/main_impl.h b/src/modules/silentpayments/main_impl.h
index 3fc42f5..7d3ad41 100644
--- a/src/modules/silentpayments/main_impl.h
+++ b/src/modules/silentpayments/main_impl.h
@@ -708,6 +708,7 @@ int secp256k1_silentpayments_recipient_create_shared_secret(const secp256k1_cont
     ret &= secp256k1_scalar_set_b32_seckey(&rsk, recipient_scan_key32);
     ret &= secp256k1_silentpayments_recipient_public_data_load_pubkey(ctx, &A_tweaked_ge, public_data);
     /* If there are any issues with the recipient scan key or public data, return early */
+    secp256k1_declassify(ctx, &ret, sizeof(ret));
     if (!ret) {
         return 0;
     }

Thanks for the patch! I've updated the ctime tests to use this, and also removed the remaining TODOs from the test file (with comments where appropriate).

in commit 896e0af2f883d21ba3540290f176dcaa7f57272d: As for those TODOs, probably the safest option is to return an error if _pubkey_tweak_add indeed fails? Initially I assumed that doing that would introduce a branch that can't be tested in practice, but I think it is: by picking arbitrary shared_secret33 and k values, and calculating recipient_labeled_spend_pubkey as -G^(_create_t_k(shared_secret33, k)) the tweaking should fail with these three values. Will try to come up with some test code later to verify.

Ok, managed to come up with a test that makes the VERIFY_CHECK on the _pubkey_tweak_add return value fail:

<details> <summary>diff</summary>

diff --git a/src/modules/silentpayments/tests_impl.h b/src/modules/silentpayments/tests_impl.h
index a1acab7..2a10791 100644
--- a/src/modules/silentpayments/tests_impl.h
+++ b/src/modules/silentpayments/tests_impl.h
@@ -367,6 +367,23 @@ static void test_recipient_api(void) {
     CHECK_ILLEGAL(CTX, secp256k1_silentpayments_recipient_create_output_pubkey(CTX, &t, NULL, &p, 0));
     CHECK_ILLEGAL(CTX, secp256k1_silentpayments_recipient_create_output_pubkey(CTX, &t, o, NULL, 0));
 
+    /* check the _recipient_create_output_pubkey cornercase where internal tweaking would fail;
+       this is the case if the recipient spend public key is P = -(create_t_k(shared_secret, k))*G */
+    {
+        const unsigned char *shared_secret = o;
+        const uint32_t k = 0;
+        secp256k1_scalar t_k;
+        unsigned char t_k_ser[32];
+        secp256k1_pubkey fake_spend_pubkey;
+        secp256k1_xonly_pubkey output_xonly;
+
+        secp256k1_silentpayments_create_t_k(&t_k, shared_secret, k);
+        secp256k1_scalar_get_b32(t_k_ser, &t_k);
+        CHECK(secp256k1_ec_pubkey_create(CTX, &fake_spend_pubkey, t_k_ser));
+        CHECK(secp256k1_ec_pubkey_negate(CTX, &fake_spend_pubkey));
+        CHECK(secp256k1_silentpayments_create_output_pubkey(CTX, &output_xonly, shared_secret, &fake_spend_pubkey, k) == 0);
+    }
+
     n_f = 0;
     labels_cache.entries_used = 0;
     CHECK(secp256k1_silentpayments_recipient_scan_outputs(CTX, fp, &n_f, tp, 1, ALICE_SECKEY, &pd, &p, &label_lookup, &labels_cache));

</details>

I assume that in practice a user can't be tricked into such a scenario though, as the recipient spend public key is known/generated before the shared secret is.

Awesome! IIRC, the initial hesitance to returning a value was adding an untestable branch in the code. But considering this can be exercised in a test (which indicates its not inconceivable that someone could be tricked into calling this function with a maliciously crafted spend pubkey), I removed the VERIFY_CHECK in favour of returning the value and added your test case. Thanks for working on this!

Updated this to actually calculate the shared secret from the public data object, to make valgrind happy.

Suggestion for the comment to tackle another TODO 🔫 (IIUC, the non-constant timing of group element serialization seems to ultimately be caused by variable-time normalization of field elements):

    /* Need to declassify the pubkey sum because serializing a group element (done in the
       `_calculate_input_hash` call following) is not a constant-time operation */
    secp256k1_declassify(ctx, &A_sum_ge, sizeof(A_sum_ge));

Thanks for digging into this! Added the comment with some slight formatting changes.

only noticing now that in one of my earlier comments I was using multiplicative notation (cryptocamp leaving its marks already I guess 😁)

     * B_spend argument, i.e., B_spend = -(_create_t_k(shared_secret33, k))*G

I was about to ask what this strange "-" symbol in -G^(_create_t_k(shared_secret33, k)) is supposed to mean. :stuck_out_tongue:

Team additive 💪

should also memclear the shared secret here and in the error path a few lines above (admitedly a bit annoying though that this leads to so much code duplication :/)

Done, also slightly reworded the comment. Overall, while slightly annoying, the code duplication doesn't seem too bad to me and I don't see a clever way to DRY it up.

nit: could update the main return values in the example to use EXIT_FAILURE/EXIT_SUCCESS (done for other examples in #1654)

Done

It might make sense to split this benchmark into "labeled" and "unlabeled" variants in order to also get a feeling how overhead the labels scanning causes, with something like e.g.:

<details> <summary>diff</summary>

diff --git a/src/modules/silentpayments/bench_impl.h b/src/modules/silentpayments/bench_impl.h
index 1dd1e5a..366d172 100644
--- a/src/modules/silentpayments/bench_impl.h
+++ b/src/modules/silentpayments/bench_impl.h
@@ -108,7 +108,7 @@ static void bench_silentpayments_output_scan(void* arg, int iters) {
     }
 }
 
-static void bench_silentpayments_full_tx_scan(void* arg, int iters) {
+static void bench_silentpayments_full_tx_scan(void* arg, int iters, int use_labels) {
     int i;
     size_t n_found = 0;
     secp256k1_silentpayments_found_output *found_output_ptrs[2];
@@ -116,6 +116,8 @@ static void bench_silentpayments_full_tx_scan(void* arg, int iters) {
     const secp256k1_xonly_pubkey *tx_input_ptrs[2];
     bench_silentpayments_data *data = (bench_silentpayments_data*)arg;
     secp256k1_silentpayments_recipient_public_data public_data;
+    const secp256k1_silentpayments_label_lookup label_lookup_fn = use_labels ? label_lookup : NULL;
+    const void *label_context = use_labels ? label_cache : NULL;
 
     for (i = 0; i < 2; i++) {
         found_output_ptrs[i] = &data->found_outputs[i];
@@ -135,11 +137,19 @@ static void bench_silentpayments_full_tx_scan(void* arg, int iters) {
             data->scan_key,
             &public_data,
             &data->spend_pubkey,
-            label_lookup, label_cache)
+            label_lookup_fn, label_context)
         );
     }
 }
 
+static void bench_silentpayments_full_tx_scan_unlabeled(void *arg, int iters) {
+    bench_silentpayments_full_tx_scan(arg, iters, 0);
+}
+
+static void bench_silentpayments_full_tx_scan_labeled(void *arg, int iters) {
+    bench_silentpayments_full_tx_scan(arg, iters, 1);
+}
+
 static void run_silentpayments_bench(int iters, int argc, char** argv) {
     bench_silentpayments_data data;
     int d = argc == 1;
@@ -147,7 +157,8 @@ static void run_silentpayments_bench(int iters, int argc, char** argv) {
     /* create a context with no capabilities */
     data.ctx = secp256k1_context_create(SECP256K1_FLAGS_TYPE_CONTEXT);
 
-    if (d || have_flag(argc, argv, "silentpayments")) run_benchmark("silentpayments_full_tx_scan", bench_silentpayments_full_tx_scan, bench_silentpayments_scan_setup, NULL, &data, 10, iters);
+    if (d || have_flag(argc, argv, "silentpayments")) run_benchmark("silentpayments_full_tx_scan_labeled", bench_silentpayments_full_tx_scan_labeled, bench_silentpayments_scan_setup, NULL, &data, 10, iters);
+    if (d || have_flag(argc, argv, "silentpayments")) run_benchmark("silentpayments_full_tx_scan_unlabeled", bench_silentpayments_full_tx_scan_unlabeled, bench_silentpayments_scan_setup, NULL, &data, 10, iters);
     if (d || have_flag(argc, argv, "silentpayments")) run_benchmark("silentpayments_output_scan", bench_silentpayments_output_scan, bench_silentpayments_scan_setup, NULL, &data, 10, iters);
 
     secp256k1_context_destroy(data.ctx);

</details> Results on my machine:

Benchmark                     ,    Min(us)    ,    Avg(us)    ,    Max(us)

silentpayments_full_tx_scan_labeled,    94.6       ,    96.6       ,   101.0
silentpayments_full_tx_scan_unlabeled,    82.7       ,    84.2       ,    85.9
silentpayments_output_scan    ,    85.3       ,    87.5       ,    90.7

Agreed. I added the dummy labels originally to make sure I was reporting worst-case[^1] numbers for the full scan benchmark, and the idea was to add more benchmarks in a follow-up that more accurately benchmark labels. However, I think what you have here is nicer and we can still leave a TODO comment to add a more representative benchmark for scanning with labels.

[^1]: worst case in the sense that all of the scan-with-labels code paths are hit during the benchmark. Its not an actual worst case in that you could have a very large, poorly implemented labels cache which would necessarily slow down scanning

Added your diff with a few minor naming differences and left a TODO comment for filling out the labels benchmark in a follow-up. In particular, I would be interested to see a benchmark that demonstrates that scan time is largely unaffected by label cache size, e.g., scanning with 10 labels vs 100,000 labels shouldn't make a difference. I think this should be a follow-up, however, since it's not strictly necessary and will likely require dedicated review of its own to get things right.

Seems fine to limit the scanning-with-labels benchmark to the cryptography-related parts for now. The planned extended benchmark doesn't even necessarily have to live in the secp repo IMHO, it could as well be in a project using the module (i.e. Bitcoin Core in our case), where a labels cache has to be implemented anyways and we wouldn't have to fake it (which might be non-trivial in C to achieve something representative, as I guess we'd need to implement some hashmap-like data structure a la std::unordered_map?). But no hard feelings on the details of where/how, I agree that seeing such a followup would be very interesting indeed.

Excellent point regarding the hashmap. I'll leave the TODO comment for now, but it might be that the follow-up is simply to remove the comment in favour of, as you suggest, benchmarking this in a more realistic setting like Bitcoin Core.

in 070ea002339bf10603da5dd772795c7ccae3af51, function my_memcmp_var

    return 0;

as this doesn't indicate a process execution status

Ah, good catch!

In eeed5671de059d5812571dc0bfcaee12f10f71e2 silentpayments: sending: it may be worth reminding the reader why there's never more than one secret key per input; BIP352 excludes inputs "with conditional branches or multiple public keys".

Added a reminder, with a prompt to review the BIP for more details.

In eeed5671de059d5812571dc0bfcaee12f10f71e2 silentpayments: sending: the taproot secret keys

Done.

In eeed5671de059d5812571dc0bfcaee12f10f71e2 silentpayments: sending: I still think it would be nice to have a helper for this, but it can be introduced in a later PR.

I don't think this module should include a helper function for this, but we can debate this in a later PR 😉

In eeed5671de059d5812571dc0bfcaee12f10f71e2 silentpayments: sending: from offline conversation my understanding is as follows:

We don't add a tie breaker here (e.g. ->index) because:

1. The protocol doesn't require it
2. It would break the constant time property of heap sort

If so, it would be good to say this in a comment so nobody is a) confused b) tempted later to introduce a footgun.

(the temptation might come from a user of this library who finds that their tests are breaking half of the time because they had an ordering related bug - or just natural programmer desire for deterministic sort )

Following up on this, I misspoke regarding 2). Its not about being constant time (heapsort is $O(n\log{}n)$ time, $O(1)$ space), but rather heapsort is unstable so there isn't a straightforward way to do a stable, e.g., multi-key, sort.

Even if there were a straightforward way, I'd still push back since the protocol is designed to not rely on ordering. Rather, the BIP only specifies grouping by scan key and sorting is just our way of implementing "grouping." I'll flesh out the comment to make this more clear.

Updated the comment to indicate developers cannot and should not rely on deterministic sorting of the recipients.

In eeed5671de059d5812571dc0bfcaee12f10f71e2 silentpayments: sending: anyone have a nice Python / Ruby incantation to derive the midstates of BIP0352/...?

Wrote one in C using secp256k1 itself a while ago, see #1653 (regarding Python, the thread suggests using the https://github.com/cloudtools/sha256 library, but didn't try that yet; with the standard library implementation in hashlib it's unfortunately not possible to access the internal state :/).

I've had this thought a few times in the past. Opened https://github.com/secp256k1lab/secp256k1lab/issues/10 to discuss further, as that seems like the most natural place to me for an example/script to live.

see https://gist.github.com/real-or-random/a4aaae5d04eee9f63e7a2e43d25bc2b1#file-sha256_midstate-py

But I think the "proper"TM way is that josie adds a test that checks if the finalized hash is the same as when recomputed from scratch, see https://github.com/bitcoin-core/secp256k1/blob/e523e4f90e1b1c0fba49cd8a08016e1a8dff9232/src/modules/musig/tests_impl.h#L551-L586. Then the reviewer only needs to review this check.

Agree on the "proper" approach, thanks for the pointer to the musig test. I'll add the same here.

Considering we are using optimised tagged hashes in a majority of the modules, this seemed like a good opportunity to DRY up the code and propose a convention for testing tagged hash midstates: https://github.com/bitcoin-core/secp256k1/pull/1725

In eeed5671de059d5812571dc0bfcaee12f10f71e2 silentpayments: sending: it's worth noting somewhere, maybe in the BIP, that removing (omitting) any output k later will cause the recipient to not find outputs > k

Great point! I'll add a footnote to the BIP.

Done in https://github.com/bitcoin/bips/pull/1908

In eeed5671de059d5812571dc0bfcaee12f10f71e2 silentpayments: sending: "is set to" -> "must be set to ... starting with 0" (since it's checked).

Done. I also took out the first sentence, as it seemed to imply we only need to set the index field in certain situations (the index field must always be set, even if only sending to one silent payment recipient).

In eeed5671de059d5812571dc0bfcaee12f10f71e2 silentpayments: sending: so the last shall be first, and the first last :-)

I think it would be more clear to store recipients[0]->scan_pubkey instead and call it current_scan_pubkey.

Done.

in e0c225c047645ae92db877f661ede385f4f8603d: this comment seems outdated? the cast for tx_output_ptrs is now happening at the scan function below (from non-const to const rather than the other way round)

in e0c225c047645ae92db877f661ede385f4f8603d:

                    ret = secp256k1_xonly_pubkey_serialize(ctx,
                        serialized_xonly,
                        &found_outputs[i].output
                    );
                    assert(ret);

just to evaluate all API call return values for consistency (here and in the light client scanning loop below)

in e0c7a09415de00e94e8a8c8fc3c5154d00cc0739:

 *       outpoint_smallest36: serialized (36-byte) smallest outpoint

(also in the description above)

nit: could maybe consider removing the P_ prefix as we don't use this naming scheme anywhere else in this or other modules (I think I introduced that in the first take of the BIP352 module for some reason)

in commit 32d8077cb7d288c7114dcf8d7b831d7ada590bd0: minimum-diff pedantic nit: this change, as well as all other single-line changes in the same commit below should already be part of an earlier commit

 *             (statistically improbable).

(here and in many other instances)

Turns out I am not as good a typist as I thought I was 😅

Not knowing the answer myself, but I'm wondering now whether internal details like this should be part of the header API documentation (that's slightly related to the questions brought up at #1698 (comment) about the proper detail level of error case documentation), or if it's just sufficient to say that there are two secret key types that are somehow treated differently. Or even just remove the sentence completely (and the "For that reason" part). Maybe it's not a big deal to keep it, but I'd assume the user of the module likely doesn't care (and shouldn't) what exactly is going on under the hood at this detail level. That sentence was already part of the first take at #1471, so all the blame goes to me anyways :sweat_smile:

Good catch, I think keeping the API documentation focused on usage makes sense. In this case, I think we can safely drop line 65 to the end. libsecp256k1 already has different data types for plain keys and taproot keys, which I think is explanation enough for a user as to why we have two different arguments for accepting secret keys in this function.

Seems like this memset is a no-op and the test a repetition of the one four lines above. Was the idea here to run the previous test without damaging the spend pubkey of r[1] first? (would make sense considering that it is saved and restored via tmp)

I believe the lines above were a leftover. The idea, as you mention, was to add coverage for a damaged spend pubkey and a damaged scan pubkey. I removed the old lines in favour of the two test cases using the tmp values.

nitty nit: for easier matching for the reader, could sort these constant descriptions in the same order as they appear in the array definitions below

nit: slightly more specific (as the current wording implies that the actual cache data structure can be created with this module)

 *  For creating the labels cache data (label public key and label tweak),

or just

 *  For creating the labels cache data,

I think "data" should be sufficient, considering the data is better explained in the documentation for the _create_label function.

reviewer-friendliness nit: the P_ prefix removal should be part of an earlier commit already to not create extra diff lines

for consistency, could still VERIFY_CHECK the return values of these two function calls

nit: a regular memset is sufficient here, as this is no stack data (and not secret data either)

equivalent but more explicit (ret can only be 1 at this point)

    return 1;

unrelated nit: noted that there is no CMake-equivalent for that, but it's not for any other generated test vectors either, so probably a topic for a different PR (if at all, I assume test vectors are usually just updated by manual script runs rather than involving the build system)

Would consider this a follow-up as a more general build system improvement.

(if at all, I assume test vectors are usually just updated by manual script runs rather than involving the build system)

The current idea is that you can manually delete the files, and the build system will then regenerate them (and you don't need to worry about how this is done). And yes, that's restricted to autotools, which is fine because it's a developer-only thing. Decoupling this from the build system entirely would also be an option.

Anyway, none of this is related to this PR.

I opened #1723 as a follow-up. Mostly because I think it would be really nice to keep the build systems consistent, and I got curious on what this would look like for CMake.

https://github.com/bitcoin-core/secp256k1/pull/1698/commits/ca2538a8782628437488ca32c49f52957aff5f69 I'd drop this check for consistency. (But nothing bad happens if we keep it.)

• Musig also depends on schnorrsig and thus transitively on extrakeys, but we don't check for this.
• You don't add an equivalent check to CMake

Removed.

https://github.com/bitcoin-core/secp256k1/commit/1a5f53f2cf7d3228b7ed147282ea5bd796957cbf Is there a reason why we require the user to set this instead of setting it ourselves? This would make the API simpler and easier to explain.

I vaguely remember discussing this with you and @jonasnick previously where we were debating back and forth on whether the caller should set this or we should set it internally. The preference was to have the caller set the value as this seemed the least confusing of our options, but I can't recall the reasons why 😅 .

If we keep the index field in the struct, then I do think we should have the caller set it, as it seems even more confusing to have the caller create the recipient structs without fully initialising them. That leaves removing the field entirely from the struct, but I don't think there is a (sane) way to keep track of the original ordering internally so that we can ensure we map the generated outputs back to the original ordering.

So I'd prefer to leave it as-is, but perhaps we can better explain this in the API documentation?

Fwiw, I remember thinking about this idea while reviewing at least once, but always ended up on dropping the suggestion as I found it strange that users would pass in input parameters that can be partly uninitialized (haven't checked, but I assume that none of the existing API functions allow this). Users have to fill in the recipients in a loop anyway, so this should usually need one extra line of code. I agree though that the current solution is not ideal either, so no strong opinion. As a compromise, to not allow uninitialized values, one could require that the index field is always zero (maybe renaming it to something like _internal, to express that the user doesn't have to care what it is used for), and then set it internally, but not sure if that is better.

Okay, yes. My thinking was that I prefer an API in which the user passes a data structure which doesn't even have an index field, but this seems hard in C (or at least, it comes with a bunch of other disadvantages). So yes, let's keep this unless someone has a great idea to get rid of this field without introducing any other overhead. In any case, having the field is safe because we check that the value is set correctly. It's just a minor annoyance for the caller.

API in which the user passes a data structure which doesn't even have an index field, but this seems hard in C (or at least, it comes with a bunch of other disadvantages).

Just wanted to confirm this is where I landed as well, i.e., its annoying to have the field but trying to work around the field is even more annoying.

https://github.com/bitcoin-core/secp256k1/commit/1a5f53f2cf7d3228b7ed147282ea5bd796957cbf some writing improvements. if you take them, please reformat

/** The data from a single recipient address
 *
 *  This struct serves as an input argument to `silentpayments_sender_create_outputs`.
 *
 *  `index` must be set to the position (starting with 0) of this recipient in the
 *  `recipients` array passed to `silentpayments_sender_create_outputs`. It is
 *  used to map the returned generated outputs back to the original recipient.
 *
 *  Note:
 *  The spend public key field is named `labeled_spend_pubkey` to indicate that this
 *  spend public key may have been optionally tweaked with a label by the sender.  
 *  This is purely a documentation convention to differentiate 
 *  between other uses of `spend_pubkey` in this API, where it is meant to refer
 *  to the unlabeled spend public key.
 *  Whether `labeled_spend_pubkey` has actually been tagged is irrelevant
 *  for the sender and
 */

• Would it be nicer for the user if we had spend_pubkey and unlabeled_spend_pubkey or (raw_ or whatever) instead?

I think what you're suggesting makes more sense. As the comment already mentions, from the senders perspective it is always just a spend public key. Using this naming convention, we could simplify the docs here and instead move the explainer to the label API docs, where it is actually important that the user of the API understand the distinction.

Updated to use spend_pubkey and unlabeled_spend_pubkey, which I think is much better than what we had before.

https://github.com/bitcoin-core/secp256k1/commit/1a5f53f2cf7d3228b7ed147282ea5bd796957cbf want to add a test for this property? (this also makes review easier)

I copied this value from https://github.com/bitcoin-core/secp256k1/blob/d599714147b20dda092ec4af44ef4174d584bb7d/src/tests.c#L6031-L6037 , where it is comprehensively tested. Would a comment pointing the reviewer to the edge case test be sufficient? Also happy to duplicate a subset of the edge case test over here if that's preferred.

Ah, I see. Then I suggest copying the line CHECK(secp256k1_ec_seckey_verify(CTX, orderc) == 0); . This saves the reviewer from looking up the group order and doing the comparison manually.

Added!

https://github.com/bitcoin-core/secp256k1/commit/1a5f53f2cf7d3228b7ed147282ea5bd796957cbf nit: inconsistent spacing

Took a moment to look how secret keys and public keys are formatted in the other tests, will update these to match the rest of the library.

https://github.com/bitcoin-core/secp256k1/commit/1a5f53f2cf7d3228b7ed147282ea5bd796957cbf

    CHECK(ret == 1);

this is what the docs promise.

https://github.com/bitcoin-core/secp256k1/commit/2b57d2ad8964e536508fae0b6ab1331396fe0308 nit: I suggest "sending and receiving"

https://github.com/bitcoin-core/secp256k1/commit/1a5f53f2cf7d3228b7ed147282ea5bd796957cbf sorted by what? And do we want to make this guarantee in the API?

"Sorting" is an implementation detail, since sorting is simply the method we are using to "group" the addresses by scan key. Given that, its probably better to remove all references to sorting from the API docs and instead use "grouping" to match the language in the BIP?

What about:

diff --git a/include/secp256k1_silentpayments.h b/include/secp256k1_silentpayments.h
index f547207..108c61c 100644
--- a/include/secp256k1_silentpayments.h
+++ b/include/secp256k1_silentpayments.h
@@ -80,14 +80,15 @@ typedef struct secp256k1_silentpayments_recipient {
  *                            recipients, where each recipient is a scan public
  *                            key, a spend public key, and an index indicating
  *                            its position in the original ordering. The
- *                            recipient array will be sorted in place, but
- *                            generated outputs are saved in the
- *                            `generated_outputs` array to match the ordering
- *                            from the index field. This ensures the caller is
- *                            able to match the generated outputs to the
- *                            correct silent payment addresses. The same
- *                            recipient can be passed multiple times to create
- *                            multiple outputs for the same recipient.
+ *                            recipient array will be grouped by scan public key
+ *                            in place (as specified in BIP0352), but generated
+ *                            outputs are saved in the `generated_outputs` array
+ *                            to match the original ordering (using the index
+ *                            field). This ensures the caller is able to match
+ *                            the generated outputs to the correct silent
+ *                            payment addresses. The same recipient can be
+ *                            passed multiple times to create multiple outputs
+ *                            for the same recipient.
  *              n_recipients: the number of recipients. This is equal to the
  *                            total number of outputs to be generated as each
  *                            recipient may passed multiple times to generate

Pushed a slight variant of this, lmk what you think.

looks good. I think I'll do an entire review pass over the API docs once I've finished looking at the actual code

https://github.com/bitcoin-core/secp256k1/commit/1a5f53f2cf7d3228b7ed147282ea5bd796957cbf related to the other comment in this review: Are you saying here that the user should not rely on int secp256k1_silentpayments_sender_create_outputs sorting the recipients? If yes, this contradicts the API docs. (And the implementation file is the wrong place to make such a statement.)

Looking at this with fresh eyes, I think the need for this comment arose from the fact the API docs were perhaps giving too much information about the sorting implementation and creating confusion.

I think it would be better to remove any mentions of sorting from the API, e.g., #1698 (review), and then remove the "Note: " clarifying comment.

Agreed

Couldn't we also in this case (like on the sending side) construct inputs to the functions that hit this? (Did we discuss this on the BIP? I vaguely remember having thought about this before.)

We did discuss this and decided it was improbable due to t_k_scalar being the output of a hash function, where the allowable hash preimage values can only come from the senders spendable UTXOs.

That being said, you're right that we can create a test case for this by first picking a t_k_scalar value and then choosing a B_spend that is the negation of t_k_scalar. In practice, I don't think this could ever happen since the sender is not in control of B_spend, but you could have a malicious receiver that puts out silent payment addresses with maliciously crafted B_spends. Based on that, I think it's worth adding a test case and handling the error in this function.

Yes, we use VERIFY_CHECK like an assertion, i.e., there should be no API calls that make the asserted condition false. Now, we make an exception for inputs that are "cryptographically hard to find" (i.e., a computationally limited adversary will find them only with negligible probability under hardness assumptions that we accept). This is justified because noone will actually be able to hit the assertion in the real world (unless our assumptions turn out to be wrong).

But I think we should not extend our set of assumptions to things like "the API function is called on inputs created from spendable UTXOs in some existing blockchain" or similar. Or in other words: if you can come up with a test case against the public API that triggers that VERIFY_CHECK, then it should not be a VERIFY_CHECK.

Or in other words: if you can come up with a test case against the public API that triggers that VERIFY_CHECK, then it should not be a VERIFY_CHECK.

Thanks for the explanation, I've always been a bit hazy on when/how to use VERIFY_CHECK appropriately; this cleared it up for me! Will add a test for this and remove the VERIFY_CHECK in my next push.

This could also test with an illegal s, I think.

Updated the tests to cover both the negation case and malformed public keys cases.

The Valgrind bug has been fixed: https://github.com/LouisBrunner/valgrind-macos#135

Amazing! Thanks for digging into that.

I suggest calling this a _transaction_summary. This is more descriptive.

Perhaps then public can be dropped because it's a bit more implied from the name. And this is also implied because the function that creates it doesn't get secret data. I think I slightly tend to drop public then. (My thinking is that, if it was secret data, then secret should totally be an explicit part of the name to warn the user, but it's okay to drop public.) It should still be mentioned in the docs that this is just public data.

• secp256k1_silentpayments_recipient_transaction_summary (my favorite)
• secp256k1_silentpayments_recipient_public_transaction_summary
• secp256k1_silentpayments_recipient_public_tx_summary
• secp256k1_silentpayments_recipient_public_tx_summary

Agree with dropping "public." My only nit with calling this a transaction summary is that it contains data not found in a transaction, i.e., the prevout scriptPubKeys. The prevouts are referenced in a transaction (by outpoint). I think this is important because calling it transaction summary to me implies that I can create this with only the transaction itself (which is not true).

What about _recipient_inputs_summary? , or _prevouts_summary?

Ok, good point! I think then recipient_prevouts_summary is the right name. Technically speaking, what references a prevout is a transaction input, so _recipient_inputs_summary is similarly imprecise (though already much better than transaction_summary).

Renamed to prevout_summary.

Just realised prevouts_summary is probably more correct 😅 Not sure why I didn't make it plural. Can update in a later push to prevouts_summary if we feel that would be better.

Fixed in the latest push; now using prevouts_summary everywhere.

I find this unexpected. What I expect from any data structure that comes with serialize and parse methods is that serializing and re-parsing it doesn't make a functional difference.

The need for boolean indicates that there should perhaps be two different data structures. Or, simpler: declare the serialized thing to be something else. This means that one way to get this cleaner is to split the scan function into two, one that takes recipient_public_data and one that takes serialized public data. But wait, we already have it like that: secp256k1_silentpayments_recipient_create_shared_secret is purely for light clients.

That suggests dropping _recpient_public_data_parse (and perhaps renaming _recipient_public_data_serialize to _recipient_public_data_export).

There's a slight loss of functionality: The docs of _recipient_public_data_create say: "If calling this function for simply aggregating the public transaction data for later use, the caller can save the result with silentpayments_recipient_public_data_serialize". Is this really a use case we'd like to offer? It's not great in terms of performance. It will double the amount of necessary EC mults. Note that the caller could simply store the opaque data structure in memory for later use. Only if the caller wants to write it to permanent storage, then serialization will be necessary.

My thinking is that if this is not an important use case, then we should just drop it. But if we want this use case, then we suggest just that there should be a serialization function that serializes the "uncombined" variant for saving EC mults at the cost of increased storage requirements.

Alternative way: I can see why you want just one data structure. This is simply about lazy evaluation of the EC mult, and whether it has already happened or not is merely an implementation detail and should not make an observable difference to the API caller (except in terms of performance). But then I suggest implementing it like a real lazy evaluation:

• _recipient_public_data_create always creates a public_data object with combined = false
• _recipient_public_data_serialize accepts any public_data object. If combined = false, it performs the EC mult before serializing the resulting public key as a compressed public key. If combined = true, it simply serializes
• _recpient_public_data_parse assumes the input represents a previously serialized public_data object and always deserializes into a public_data object with combined = true (and the input_hash portion zeroed out).
• _recipient_create_shared_secret can also accept both combined = true and combined = false. But if we think that calling _create_shared_secret latter necessarily implies the caller is doing something wrong, then my first suggestion above is probably better.

Agree that having _serialize and _parse methods that do not roundtrip is a bit code smelly.

If calling this function for simply aggregating the public transaction data for later use ... Only if the caller wants to write it to permanent storage, then serialization will be necessary.

The comment in the code is a bit confusing. The only reason a caller would want to "aggregate for later use" is when building a silent payments index, for personal use (e.g., fast wallet rescans), or for serving the data to external light clients.

I much prefer your alternative suggestion, as this seems simpler than having multiple data structures and easier to document. I also think full nodes keeping their own silent payments index for fast wallet rescans and for supporting light clients will be a very common (and important!) use case to support.

Makes sense to me. We should then make sure to document the performance implications of the API calls.

I updated this per your suggestion to make this a proper lazy evaluation. Also documented that calling _serialize can incur an EC mult in some cases. I don't think there are any other performance implications that need documenting, since calling _recipient_create_shared_secret will always involve one EC mult, and sometimes a scalar mult, depending on the value of combined. But a scalar mult seems negligible enough that it shouldn't warrant documenting.

Just a minor typo, yet it causes a sanity check for pubkey serialization to be skipped without warning.

#ifdef VERIFY

Great catch!

What happens if parsing fails and an addend other than expected (maybe invalid) is supplied to secp256k1_gej_add_ge_var?

From what I can tell, nothing. If any single public key fails to parse, we will catch it a few lines down. Arguably, we could return early to avoid doing extra work when a single public key is bad, which seems preferable.

Update to return as soon as a bad pubkey is encountered. This avoids calling _gej_add_ge_var with a bad addend and fails early on the first bad key, instead of wasting the callers time with additional work. Also updated the tests to explicitly test both bad plain pubkeys and bad taproot x-only pubkeys.

From what I can tell, nothing.

Indeed. secp256k1_gej_add_ge_var will compute garbage (garbage in, garbage out), but there won't be any crashes or UB. But when looking deeper, there's an interesting question; see #1736.

nit (in int secp256k1_silentpayments_recipient_create_label):

secp256k1_memclear(m_serialized, sizeof(m_serialized));
secp256k1_sha256_clear(&hash);

Done.

nit: ensure there's room for the increment

        VERIFY_CHECK(k < SIZE_MAX);
        k++;
        

Done.

in 163dc82627e864b202b1e919ee39d69df89f12f8:

 *      labeled_spend_pubkey = recipient_spend_pubkey + label

(as label is already a pubkey, not a scalar)

    /* Calculate labeled_spend_pubkey = recipient_spend_pubkey + label

   /* Leaking these values would break indistinguishability of the transaction, so clear them. */

(here and in 5 other instances, in both the sending and receiving commits)

 *  Out:  prevout_summary: pointer to a silentpayments_recipient_prevout_summary object. If 1 is

 *             prevout_summary: pointer to the public_data object, loaded using
 *                              `_recipient_prevout_summary_parse`

 *  - `_recipient_prevout_summary_parse` assumes the input represents a previously serialized

with the recent change to use lazy evaluation (see #1698 (review) ff.), this comment needs to be updated (the ones for _create and _parse are still correct, I think)

Updated, and also updated the ctime_tests, where we were doing a serialization roundtrip to get the prevouts summary object into a combined = true state.

int secp256k1_silentpayments_recipient_create_labeled_spend_pubkey(const secp256k1_context *ctx, secp256k1_pubkey *labeled_spend_pubkey, const secp256k1_pubkey *unlabeled_spend_pubkey, const secp256k1_pubkey *label) {

to match the parameter name in the API header

int secp256k1_silentpayments_recipient_create_output_pubkey(const secp256k1_context *ctx, secp256k1_xonly_pubkey *output_xonly, const unsigned char *shared_secret33, const secp256k1_pubkey *spend_pubkey, const uint32_t k)

to match the parameter name in the API header

 *      labeled_spend_pubkey = unlabeled_spend_pubkey + label

sorry to dig into the same line once again, missed this in the last review round :sweat_smile: might be worth it to grep for recipient_spend occurences in general, if the plan is to get rid of that terminology completely (and only use {labeled_,unlabeled_,}spend_pubkey)

No worries! I went ahead and updated all instances to use {labeled_,unlabeled_,}spend_pubkey and also update the scan_key32 argument to remove the recipient_ prefix. Much cleaner, imo.

 *  Args:                ctx: pointer to a context object (not secp256k1_context_static)

as the sending function needs the generator point multiplication context (for calculating the pubkey sum from the seckey sum), and this is how we usually denote that in the API header (see also #1737)

seems that this declassify call is a duplicate from the one a few lines above and can be removed

(ctime tests still pass for me locally)

in the _create_label API header:

 *  Args:                ctx: pointer to a context object (not secp256k1_context_static)

compared to the sending function it's a bit less obvious that a static context can't be used, as we don't check that ecmult_gen_ctx is built manually, but call another API function ec_pubkey_create which requires this

in _recipient_scan_outputs:

    return 1;

as the "single point of return" approach isn't followed anymore and any failures return early

    ret = secp256k1_pubkey_load(ctx, &spend_pubkey_ge, spend_pubkey);

(as the previous failure would return early)

should securely erase the shared_secret and t_k_scalar here

And maybe we can find a better name for t_k_scalar. Not sure if it appears in the BIP but it's "BIP-style"

It is "BIP-style," in that its the terminology used in the BIP. I think the most accurate thing to call it would be "output_tweak," since this is the value that is created from the hash of the shared secret (with counter k), and then used as an additive tweak with the spend public key / spend private key.

nit, ret is always zero here:

        return 0;

naming nit: I wonder if we could drop the recipient part of the structure (especially considering that the prevout information actually represents key/input material from the sender side, so it could be even potentially confusing?)

typedef struct secp256k1_silentpayments_prevouts_summary {

I guess either is fine. It's a data structure only used on the recipient side, so having recipient is consistent. On the other hand, it suffices that only function names have the sender and recipient infixes. If you believe it could be confusing in this case, then it may be better to drop it.

I think having the sender and recipient infixes should be sufficient and would prefer to keep the names simple, wherever possible. Its also a good point that including recipient in the struct name is at best redundant and at worst confusing.

         * This can fail if t_k * G is the negation of spend_pubkey, but this happens only

(or alternatively, s/spend_pubkey/spend_seckey/, though that would more abstractly refer to a scalar that is not in the scope of this function)

consistent naming nit: the prevouts_summary struct description above uses prevout_pubkey_sum

potential follow-up deduplication idea: could include the hash -> scalar conversion in this function (including the VERIFY_CHECK and comments), so the two call-sites in sending/receiving don't have to do it

I went ahead and took this suggestion now. I think its much cleaner and makes the call sites of _calculate_input_hash_scalar easier to understand without the the duplicated overflow checking and comment explaining why.

 *  only and not optimized. In a production use case, it is expected that the

Or just "in production"

nit: I see why you use an enum here, but this is advanced C stuff that we could try to avoid in the examples. This is conceptually not an enumeration, so I'd prefer #define.

nit: Why print \n before the message? In the other error outputs, the \n comes after the message.

No reason, good catch!

Could add a comment here to explain the structure of this array, e.g., that the [2] is for scan/spend.

    /*** Sending (Alice) ***/

nit: We shouldn't omit the secp256k1 prefix in user-facing docs.

                 *      secp256k1_silentpayments_recipient_scan_outputs(..., NULL, NULL);

                 *  In this example, since Bob has access to the full transaction

In this "case" could refer to the previous paragraph (no labels used at all)

        printf("Alice created the following outputs for Bob and Carol:\n");

                 *  used, he can pregenerate a large number of labels, e.g.,

prefix

                     * in the transaction. For a full example on signing for a Schnorr signature ouput,

or do you want to call this "taproot" to match the terms above?

I think taproot is better here.

A_sum is still BIP-style

The number of found outputs?

Technically, Carol wouldn't know anything about the transaction, i.e., the total number of inputs, outputs, or found outputs. But I think its more correct to be explicit here and say "found outputs" since we are only using this information to initialize the ser_found_outputs array.

We should clean full_seckey at some point.

 *  The structs and callback function are implemented here as a demonstration

             *     2. Call `secp256k1_silentpayments_recipient_scan_outputs`

formatting nit

 *  Out:    labeled_spend_pubkey: pointer to the resulting labeled spend public key
 *  In:   unlabeled_spend_pubkey: pointer to the recipient's unlabeled spend pubkey
 *                         label: pointer to the recipient's label public key

        return EXIT_FAILURE;

/** An explanation of the prevouts_summary object and its usage:

nit: other functions that access the _prevouts_summary.data array (e.g. _prevouts_summary_{serialize,parse}) don't use this constant and directly access at offset 5 + 64 instead, so for consistency, could either remove it here (my preference) or introduce it in the other functions as well

nit, here and in the _create_shared_secret function: could rename rsk_scalar to something more explicit like scan_key_scalar (even after many review rounds, I tend to repeatedly forget that rsk is short for "recipient scan key")

formatting nit

 *  Out:  prevouts_summary: pointer to a silentpayments_prevouts_summary object. If 1 is
 *                          returned, it is set to a parsed version of input33.
 *  In:            input33: pointer to a serialized silentpayments_prevouts_summary.

s/prevout_pubkey_sum/prevouts_pubkey_sum/

nit: k is initialized to zero and never changes in this benchmark, was the plan to increment it in the loop in order to have changing input data? (didn't check if it leads to significantly different results, I presume it doesn't)

It wasn't the plan, and I'm not sure it makes a difference? FWIW, the scan key in the full tx benchmark is the same on every run, as well. So if we are going to update it so the benchmarks run on different data each iteration, I'd be inclined to update both benchmarks. I'd recommend this as a follow up.