Add silentpayments (BIP352) module #1471

This PR adds a new Silent Payments (BIP352) module to secp256k1. The following routines are provided ($a_i$ are input private keys, $A_i$ are input public keys, $b$ and $B$ denote recipient privkeys/pubkeys that would be encoded in silent payment addresses, $d$ and $P$ the keypair for the actual transaction taproot x-only output):

| Receiver | _create_tweaked_pubkey | $A_{sum}, inputhash$ | $A_{tweaked} = inputhash * A_{sum}$ | Both | _create_shared_secret | $Pub$, $sec$<br>(Sender: $B_{scan}, a_{sum}$<br>Receiver: $A_{sum}, b_{scan}$<br>Lightclient: $A_{tweaked}, b_{scan}$) | $SS = (inputhash * sec) * Pub$ (ECDH) | | Receiver | _create_label_tweak | $b_{scan}, m$ | $labeltweak = hash_L(b_{scan} || m)$<br>$label = labeltweak * G$ | | Receiver | _create_address_spend_pubkey | $B_{spend}, label$ | $B_m = B_{spend} + label$ | | Sender | _sender_create_output_pubkey | $SS, B_m, k$ | $P_{xonly} = B_m + hash_S(SS || k) * G$ | | Receiver | _receiver_scan_output | $SS, B_m, k, tx_{output}$ | $t_k = hash_S(SS || k)$<br>$P_{xonly} = B_m + t_k * G$ [not returned]<br>$directmatch = P_{xonly} == tx_{output}$<br>if $directmatch == 0$:<br>$\quad label1 = tx_{output} - P$<br>$\quad label2 = -tx_{output} - P$ | Receiver | _create_output_seckey | $b_{spend}, t_k, (labeltweak)$ | $d = (b_{spend} + labeltweak) + t_k$ |

where

• $hash_I$ denotes a SHA256 tagged hash with tag "BIP0352/Inputs"
• $hash_L$ denotes a SHA256 tagged hash with tag "BIP0352/Label"
• $hash_S$ denotes a SHA256 tagged hash with tag "BIP0352/SharedSecret"

For ending up with output key material used for sending to / scanning for / spending from, both sides would follow the chain of tweak_data -> shared_secret -> output key. The public tweak data can be useful for faster scanning of output transactions by storing them in an index, see e.g. Bitcoin Core PR https://github.com/bitcoin/bitcoin/pull/28241. Private tweak data is arguably less useful, so in theory one could collapse the tweak data and shared secret creation functions into a single one, but IMHO it's nicer if the API is symmetric.

As discussed in #1427 (comment), the approach of passing in two separate key pairs for taproot and non-taproot inputs is followed here. This may seem a bit confusing at first, but has the advantage that the caller doesn't have to deal with enforcing even y-parity for key material manually (e.g. negating private keys of taproot outputs if they would end up in an odd point), which seems error-prone.

The last commit contains the BIP352 test vectors, converted to C code with a Python script. An earlier version of the tests, directly written in Python (by calling in to the secp256k1 shared library using ctypes) can still be found here: https://github.com/theStack/secp256k1/tree/silentpayments-module-demo_old5

Thanks for starting this! Will review. Just wanted to comment that I've made a round of edits to the BIP and it is now updated with the new hashing method (along with the tests).

The PR assumes that the outpoint hash is provided by the caller, but this could change in the future if its calculation involves elliptic-curve operations that would be a good fit for being done within the module as well.

The hash is calculated as hash(outpoint_L || A_sum). Since it commits to the sum of input public keys used, seems like it might make sense to move it into the module? Otherwise, we'd have to do something like calculate the sum of the public keys, return that to the caller so that they can calculate an input hash and then send it back to us.

Thanks for starting this! Will review. Just wanted to comment that I've made a round of edits to the BIP and it is now updated with the new hashing method (along with the tests).

👍

The PR assumes that the outpoint hash is provided by the caller, but this could change in the future if its calculation involves elliptic-curve operations that would be a good fit for being done within the module as well.

The hash is calculated as hash(outpointL || Asum). Since it commits to the sum of input public keys used, seems like it might make sense to move it into the module?

Yes, I agree. A naive solution based on the current PR state would be to provide another function for calculating the input hash and leave the others as they are, but then we would need to pass the input pubkeys and calculate the pubkey sum twice (once for the input hash, and once for the pubkey tweak data), which should be avoided. I guess we want to introduce a function for calculating $A_{sum}$ to reuse that result. Will try to figure out an interface. Suggestions would be greatly appreciated :)

but then we would need to pass the input pubkeys and calculate the pubkey sum twice

(I need to actually review your implementation, but..) I don't think we need to do it twice? On the sender side, you pass in the private keys, add those up (call it priv_key_sum) and then you can generate the pubkey sum from the private keys (e.g. priv_key_sum.GetPubKey(). On the receiving side, you pass in the pubkeys, sum them, use them in the hash and then use them in the shared secret derivation.

but then we would need to pass the input pubkeys and calculate the pubkey sum twice

(I need to actually review your implementation, but..) I don't think we need to do it twice? On the sender side, you pass in the private keys, add those up (call it priv_key_sum) and then you can generate the pubkey sum from the private keys (e.g. priv_key_sum.GetPubKey(). On the receiving side, you pass in the pubkeys, sum them, use them in the hash and then use them in the shared secret derivation.

Oh indeed, I missed that after calculating the sum of private keys, summing up the pubkeys is not necessary anymore.

So if I'm not overlooking something, the interface change should be as simple as replacing the "outpointhash" parameter in the tweak functions with an "outpoint_L" parameter. Will tackle that in a bit.

I've force-pushed with a version that is now up to date with the latest state of the BIP, and updated the PR description accordingly. Labels support is also included, and all the test vectors from the BIP pass. The tests are still run from a Python script that directly interacts with the shared library via ctypes, I'll hopefully have something ready soon to create the actual tests in tests_impl.h from that automatically. The code was changed in many places to operate internal data types and functions in the routines (e.g. secp256k1_ge instead of secp256k1_pubkey, secp256k1_scalar instead of uchar-pointers to 32-byte chunks), which seems to make more sense and have less overhead.

(The previous version of the PR is still available here: https://github.com/theStack/secp256k1/tree/silentpayments-module-demo_old)

Looks great! Did a quick pass, mostly spelling and wording nits.

Another thought I had (need to actually re-review more carefully to confirm) is we might be able to minimize the de-serializations of keys (moving from bytes -> point). From my understanding, this is one of the "expensive" operations as it involves calculating the y value. This would mean either combining things into larger routines, or having the functions return points instead of serialized pubkeys. Curious what you think @theStack

@josibake: Thanks for the initial review, very much appreciated!

Another thought I had (need to actually re-review more carefully to confirm) is we might be able to minimize the de-serializations of keys (moving from bytes -> point). From my understanding, this is one of the "expensive" operations as it involves calculating the y value. This would mean either combining things into larger routines, or having the functions return points instead of serialized pubkeys. Curious what you think @theStack

Good point, that's also something I've been asking myself. I think the expensive part of calculating the y-value only applies for loading secp256k1_xonly_pubkey objects though (not for regular secp256k1_pubkeys), and since those are not used for any intermediate results, it (hopefully) shouldn't be too bad. Directly using the group element type is not possible I think, as that datatype (secp265k1_ge) is internal and not exposed by the API. Would be great to get input from experienced long-term contributors in that subject. // EDIT: oh, you probably meant the raw 33-byte results of the shared secret creation and public tweak data. Maybe those should be changed to secp256k1_pubkey instead.

Force-pushed with the following changes:

• parameter naming: s/outpoint_lowest/outpoint_smallest/, s/tweak_data32/private_tweak_data32/, s/tweak_data33/public_tweak_data/ (the data type for the last one was changed, see below)
• API description: s/for each input/for each silent payment eligible input/
• changed the result type of the public tweak data routine to secp256k1_pubkey to avoid expensive deserialization after in the shared secret creation routine (in light of comment #1471#pullrequestreview-1846116671); AFAICT, this was the only deserialization of public keys that happened for intermediate results?
• removed unnecessary parity handling of x-only-pubkeys, as they always have an even y (https://github.com/bitcoin-core/secp256k1/pull/1471#discussion_r1467904182) and adapted the API description accordingly
• added explicit checks for invalid sum results in the tweak creation routines (zero for the private keys sum, point of infinity for public keys sum) with an open TODO whether we want to have a special return code in this case. IIUC, for the public keys sum case, this case could occur during scanning if someone crafted a transaction where the input pubkeys cancel each other out (trivially reachable with two pubkeys P and -P). It might make sense to have a return code signalling "ignore this tx, it's not suitable for silent payments" to differentiate it from an actual error that happened.

EDIT: oh, you probably meant the raw 33-byte results of the shared secret creation and public tweak data. Maybe those should be changed to secp256k1_pubkey instead.

Yep! Sorry, my original comment wasn't very clear. But to be precise, what I'm referring to is anytime we have to de-serialize a public key encoding into a point (be it compressed or x-only), we need to calculate a sqrt to get the y-value, which is the "expensive" part. So if we only de-serialize once (taking the inputs from the user) and then for the rest of the process use points (i.e. (x, y) pairs) until the final step where we return the generated x-only pubkeys to the user, this should save us some work!

At a quick glance, it looks like you addressed this in your most recent push!

It might make sense to have a return code signalling "ignore this tx, it's not suitable for silent payments" to differentiate it from an actual error that happened.

Thinking about this a bit more, the errors that can happen are:

1. De-serialization errors: I pass some bytes that cannot be de-serialized into a valid public key
2. Hash returns something greater than the curve order: extremely unlikely to ever happen
3. Pubkey / private key sum is point at infinity / 0: extremely unlikely or malicious

I think in all cases the expected user behavior is to move on. For the sender, if they run into any of these errors they would need to pick a different set of inputs (i.e. make a new transaction). For the receiver, their only recourse is to skip the transaction.

I'm not sure what the added value to the user is here if we return different error codes.

It might make sense to have a return code signalling "ignore this tx, it's not suitable for silent payments" to differentiate it from an actual error that happened.

Thinking about this a bit more, the errors that can happen are:

1. De-serialization errors: I pass some bytes that cannot be de-serialized into a valid public key
2. Hash returns something greater than the curve order: extremely unlikely to ever happen
3. Pubkey / private key sum is point at infinity / 0: extremely unlikely or malicious

Leaving 2. aside (from what I understand, it's fine to just ignore those unlikely hash-not-within-curve-order cases), I think the difference between 1. and 3. is that the first suggests that the user is using the API in a wrong way (i.e. shouldn't ever happen in a correct implementation), while 3. can be triggered externally for the pubkey sum case, see below.

I think in all cases the expected user behavior is to move on. For the sender, if they run into any of these errors they would need to pick a different set of inputs (i.e. make a new transaction). For the receiver, their only recourse is to skip the transaction.

I'm not sure what the added value to the user is here if we return different error codes.

Yeah, I tend to agree. The rationale behind introducing those TODOs was to consider differentiating between the cases "invalid input data is passed", indicating that the user did something wrong (case 1 above) and "the individual input data passed is fine, but we still can't continue" (case 3 above). Since the transactions appearing in the mempool / block chain are not in the control of the user, such a "point of infinity" case could be triggered externally in the course of scanning for silent payments.

In Bitcoin Core, at some places we call secp256k1 functions with an additional assert(ret), as we are confident that the input data passed is fine and the function always succeeds, e.g. several times in CKey::SignCompact: https://github.com/bitcoin/bitcoin/blob/5fbcc8f0560cce36abafb8467339276b7c0d62b6/src/key.cpp#L255

In case of the pubkey tweak data creation routine, that would be a mistake as an external transaction could make a node crash in the course of e.g. the silent payment index creation. I guess we can avoid this though by just properly documenting in the API that the return code 0 also could mean "tx is not eligible for silent payments"? Maybe I'm overthinking here and users would hopefully always check for return values for more complex routines.

"invalid input data is passed", indicating that the user did something wrong (case 1 above) and "the individual input data passed is fine, but we still can't continue" (case 3 above)

This is a good point. In theory, a user could recover from case 1, which at that point I'd agree we need two error codes: one to indicate that the user needs to do something different with the current transaction in order to proceed, and another to indicated the can't do anything with the current transaction and it needs to be skipped.

In practice, I don't think case 1 is likely to happen often since the inputs already exist in validated transactions, it's just a matter of correctly extracting them. That being said, I am slightly leaning towards two error codes but I'd also prefer to be consistent with the other modules if we need a tie breaker. I'm curious if there is a general pattern in the library that we can take inspiration from.

Changed the tweak data creation interfaces to take lists of pointers to seckeys/pubkeys (instead of expecting the data to come in concatenated form), as suggested in the discussion #1471 (review). Took me a bit to figure out how to properly create the array of pointers with ctypes in the secp256k1 glue module for the Python test-suite, but now everything passes again.

Working on using this branch in #28122 and had some thoughts regarding labels

Force-pushed with interface changes in the tweak data and shared secret creation routines, following the latest suggestion in #1471 (review) / #1471 (review). The tweak data creation routines now return both the key sums and input hash, without doing any tweaks yet, in order to avoid extra point multiplication for the full node receiver case (see discussion #1471 (review)). Also, there is now only one shared secret creation routine left, with the parameters named public_component, private_component and input_hash. I tried documenting in the API description on what has to be passed depending on the scenario; unsure if this is sufficient yet, maybe there is a better, more clear way of presenting the expected parameters to the user (e.g. summarizing it in a table).

One open question is if we really need a dedicated routine to calculate A_tweaked = input_hash * A_sum (for light clients / silent payment indexes...). That routine would essentially be a copy of secp256k1_ec_pubkey_tweak_mul. Is it okay for the user to demand calling this routine, if it's properly documented, or do we still want do have a dedicated routine secp256k1_silentpayments_create_tweaked_pubkey that does the same, making it clear in the API what has to be passed?

Thanks for your review comments regarding labels and your POC branch @josibake, I will look at this closer in a bit.

One open question is if we really need a dedicated routine to calculate A_tweaked = input_hash * A_sum (for light clients / silent payment indexes...). That routine would essentially be a copy of secp256k1_ec_pubkey_tweak_mul. Is it okay for the user to demand calling this routine, if it's properly documented, or do we still want do have a dedicated routine secp256k1_silentpayments_create_tweaked_pubkey that does the same, making it clear in the API what has to be passed?

I have a slight preference for wrapping secp256k1_ec_pubkey_tweak_mul in a dedicated secp256k1_silentpayments_created_tweaked_pubkeys routine. This way, you can do everything you need to do with just the silent payments module and don't really need to worry about the rest of libsecp256k1. In general, I think the goal for libsecp256k1 is to further restrict the API and stop exposing routines for low level operations, so always wrapping in our own silent payments specific routines seems better.

I've rewritten #28122 to use this module here: https://github.com/josibake/bitcoin/tree/implement-bip352-secp256k1-module. So far, so good! I'll take a fresh look here tomorrow with some feedback, and then update #28122 once I've cleaned up the branch a bit and we are ready to move this PR out of draft. @theStack can you remind me what your criteria for considering this PR "not a draft" were?

I've rewritten #28122 to use this module here: https://github.com/josibake/bitcoin/tree/implement-bip352-secp256k1-module. So far, so good! I'll take a fresh look here tomorrow with some feedback, and then update #28122 once I've cleaned up the branch a bit and we are ready to move this PR out of draft. @theStack can you remind me what your criteria for considering this PR "not a draft" were?

Nice, only skimmed over the branch so far but it's good to see the module in full action. As for the out-of-draft criteria, I think we are pretty close, in my view the only two points missing are:

• add another routine for creating $A_{tweaked}$, as needed for light clients / indexes (trivial, as it's basically a wrapper around secp256k1_ec_pubkey_tweak_mul), #1471 (comment)
• having more test coverage in plain C, I think every routine should at least be called once (ideally all test vectors are converted to C code by the Python script, like e.g. done for MuSig2: https://github.com/jonasnick/secp256k1/blob/musig2-module/tools/test_vectors_musig2_generate.py)

@josibake: I've add the missing _create_tweaked_pubkey function to the API. As far as I'm aware, a user would have all the necessary routines now that are needed for a full silent payments implementation, without the need to do any manual ECC calculations (see also the summary table with formulas in the PR description). If there are no further objections, I'll move the PR out of draft within the next days, after increasing the test coverage a bit more.

@josibake: I've add the missing _create_tweaked_pubkey function to the API. As far as I'm aware, a user would have all the necessary routines now that are needed for a full silent payments implementation, without the need to do any manual ECC calculations (see also the summary table with formulas in the PR description). If there are no further objections, I'll move the PR out of draft within the next days, after increasing the test coverage a bit more.

Looks great! I've updated #28122 to use this branch. I think we can take this out of draft whenever you're ready. While I'm sure the API will change with further review, this seems like a pretty solid starting point!

What is the input k in _sender_create_output_pubkey?

I find the label stuff fairly confusing, both in the BIP and in the description here. But no concrete suggestion on how to improve that...

What is the input k in _sender_create_output_pubkey?

k is a counter used by the receiver to create multiple outputs for the sender. Using the variable k here to match the notation in the BIP (see BIP352#creating-outputs)

Force-pushed with changes regarding tests and CI. The demo-only python test runner script has now been replaced by one that converts the BIP352 test vector data in JSON format to C code (./src/modules/silentpayments/vectors.h), that is in turn included and evaluated in the main test file (./src/modules/silentpayments/tests_impl.h). The last test vector is skipped in the generation script, as is it doesn't contain any silent payment eligible inputs; since the tweak data creation APIs require that at least one input is passed, a user would detect that and not call into secp256k1-silentpayments in such a case in the first place.

Looks great! I've updated #28122 to use this branch. I think we can take this out of draft whenever you're ready. While I'm sure the API will change with further review, this seems like a pretty solid starting point!

Agree. I think there is still a long list of things that could/should be added (some manual tests e.g. for edge-cases, constant-time tests, benchmarks, examples, a proper doc/silentpayments.md document... anything else?), so the PR still feels early, but hopefully good enough as starting point. CI just showed green (enabled for silentpayments in the latest commit), so will move out of draft now.

Happy to also take suggestions regarding ease-of-review. Should I squash the implementation commits? Personally I tend to prefer a higher number of small review chunks rather than the other way round, but I also understand that too many commits can trigger a "the PR is too big to even look into" sensation for potential reviewers.

I know I just said the API looks good, but here's a bunch of API feedback :see_no_evil:

I ended up abusing this function [secp256k1_silentpayments_create_output_seckey]

Yeah, this is basically scalar_add, with some high-level docs.

This is something we need to think about. A goal of the library is to provide safe high-level APIs. I guess we often assume that this is equivalent to avoiding access to low-level operations in the API. But as this functions shows, it's not equivalent. This function is part of a high-level API, but it happens to expose a simple low-level operation... Now, there's nothing wrong with this per se, but people will abuse this for all kinds of things.

And let's be honest. If you need a scalar_add, and the library gives you a (disguised) scalar_add, it's just pragmatic to use it. The API docs won't prevent anyone from doing so. Is it their responsibility? Probably yes.

I think the entire module, as proposed, is a bit unusual for libsecp256k1 because it only wraps some ECC operations of a higher-level protocol (as explained in the header). This design makes sense, but it's different from what we usually have in libsecp256k1.

You could say that BIP340 signatures are also just some ECC parts of a higher-level protocol "Bitcoin", but the difference is that they implement a common interface of a signature scheme, what people call a cryptographic primitive (like public-key encryption, key exchange, hashing, etc.). But this here is merely the "cryptographic core of silent payments", and it's tightly coupled to it.

Again, there's per se nothing wrong with a more low-level module, but I think we'll need to spend some thoughts on how we make it fit the library best. Sometimes the potential for abuse can be reduced by having opaque data types that you can only pass from API function to API function. We do something similar in the proposed musig2 API for example. I think this would be closest to the current spirit of the library.

Another design pattern is to have "stage" functions that perform all the different computation that should be done at a specific stage of the protocol. This doesn't seem elegant, but it prevents mistakes where the caller combines the API functions wrongly, e.g., calls them in the wrong order.

Off-topic ramblings about the library:

So if we expose the silentpayments_create_output_seckey function, we might as well go ahead and expose scalar_add and possibly some more scalar and group functions as part of a mid-level, or "hazmat API" as it's called in some libraries (ignoring for a moment that this is work and raises more questions). We anyway have ec_pubkey_combine left as a relic. Then the caller at least won't have to abuse the silent payment API.

And if we had hazmat API, then one could alternatively simply build some libsilentpayments around it, and other applications could do the same. This would certainly help some applications. But it's not obvious that this is the ideal solution. There are multiple related but different questions, e.g., in should stuff be a module, in which repo should it live, who should maintain it, how should it be linked, etc... (And lol, please don't be discouraged by my comments here. I see value in this as a libsecp256k1 module, it's just that the PR makes me think about the bigger picture again...)

Thanks for chiming in @real-or-random , this is exactly the kind of review we are looking for at this stage! As much as possible, we'd like to keep this module in the spirit of the library. I'll take a look at the Musig2 API for inspiration and also spend some more time thinking about the "stages" concept. That feels somewhat closer to what we have now.

And if we had hazmat API, then one could alternatively simply build some libsilentpayments around it

This also makes a lot of sense to me as an approach. For example, I've been chatting with the developers of rust-silentpayments about how their library might evolve if there is a libsecp256k1 silentpayments module. Seems like having a rust silent payments library that consumes a "hazmat" secp256k1 API could be a reasonable solution?

And lol, please don't be discouraged by my comments here

The only thing that discourages me is no comments at all :smile:

Thanks for the valuable feedback @real-or-random, glad that the interface discussion is in full swing! After thinking about it for a while, I sympathize with the "libsilentpayments" idea more and more.

So if we expose the silentpayments_create_output_seckey function, we might as well go ahead and expose scalar_add and possibly some more scalar and group functions as part of a mid-level, or "hazmat API" as it's called in some libraries (ignoring for a moment that this is work and raises more questions). We anyway have ec_pubkey_combine left as a relic. Then the caller at least won't have to abuse the silent payment API.

Doesn't secp256k1 already have a good amount of exposed routines that potentially fall into the "hazmat API" category, especially w.r.t. the tweaking routines? For example, even without a silent payments module, one could say that the disguised scalar_add you mentioned is right now available as secp256k1_ec_seckey_tweak_add (that's btw the exact routine called within secp256k1_silentpayments_create_output_seckey, so it's currently more like an alias/wrapper around an already exposed function and hence wouldn't enable something new to the user that's not possible yet). Or would the idea be to go one step further and then also expose the internal scalar/ge(j) data types to such a hazmat API, in order to avoid unnecessary conversions between public and internal data types (and avoid error checks) that potentially hurt performance?

To my understanding, secp256k1 as of now provides all the necessary routines for a full BIP352 implementation (Bitcoin Core PR https://github.com/bitcoin/bitcoin/pull/28122 followed that approach before it used this module). The two main reasons for a secp256k1 module (or library using secp256k1, if the libsilentpayments approach is followed) would be AFAICT 1) efficiency and 2) hiding cryptographic complexity from the user.

It's kind of embarrassing to only come up with this doubts weeks after starting this implementation, but I only realize now that the potential of point 1) to warrant a module was actually never verified. Assuming we would have a libsilentpayments C library that uses secp256k1 as it is now (i.e. even without any extra hazmat API). Would that even be significantly slower than using a dedicated optimized silent payments module using low-level scalar/ge(j) primitives? Without having numbers, I'd assume that the most expensive operations are by far always the involved point multiplications (e.g. the shared secret creation via ECDH), and for those having a hazmat API wouldn't change much. @josibake: Do you think it makes sense to benchmark the Bitcoin Core PR #28122 before and after it uses this module to compare what the gains are? Happy to investigate this a bit further, if the old version (based on w0xlt's work, AFAIR) is still available somewhere. Trying Sjor's branch for building the index would probably also be interesting to run once with the "pure secp256k1" and once with the "secp256k1-silentpayments" module approach. Even if my simplified performance assumptions above are completely wrong (I wouldn't be surprised if they are :D), I think it would be good to have some benchmark numbers anyway.

@real-or-random spent some time digesting your comment and wanted to summarize some thoughts:

I think the entire module, as proposed, is a bit unusual for libsecp256k1 because it only wraps some ECC operations of a higher-level protocol (as explained in the header). This design makes sense, but it's different from what we usually have in libsecp256k1.

In hindsight, I think BIP352 could (should) have been three BIPS:

• BIP-silent-payments-non-interactive-multikey-ecdh (SPNIMKECDH)
• BIP-silent-payments-v0 (the part that defines which inputs to use)
• BIP-silent-payments-address-encoding

This way, if we need change how the inputs are chosen in the future, we'd write a small BIP-silent-payments-v1, and nothing about the SPNIMKECDH part would need to change. Conceptually, when talking about a libsecp256k1 module I'm only talking about SPNIMKECDH (i.e. we wouldn't expect a libsecp256k1module to filter transaction inputs to the silent-payments-v0 eligible inputs before performing the SPNIMKECDH protocol). If we start from this assumption and forget about the labels part of silent payments for a second, we could build a high-level API like so:

Sender

typedef struct {
    secp256k1_pubkey recipient_scan_pubkey,
    secp256k1_pubkey recipient_spend_pubkey,
    size_t n_desired_outputs
} secp256k1_silentpayments_recipient;

/**
 * Takes plain and taproot seckeys as inputs, and a list of the desired recipients
 * and returns a list of generated xonly outputs.
 * In this example, a recipient is a scan/spend pubkey pair along with an int to indicate
 * how many outputs should be created for this particular recipient
 * /
int secp256k1_silentpayments_sender_create_outputs(
    const secp256k1_context *ctx,
    secp256k1_xonly_pubkeys **outputs,
    const unsigned char * const *plain_seckeys,
    size_t n_plain_seckeys,
    const unsigned char * const *taproot_seckeys,
    size_t n_taproot_seckeys,
    const secp256k1_silentpayments_recipient * const *recipients,
    size_t n_recipients,
    const unsigned char *outpoint_smallest36
)

Receiver

typedef struct {
    secp256k1_xonly_pubkey pubkey,
    unsigned char output_tweak[32],
} secp256k1_silentpayments_output;

/**
 * Takes tx input pubkeys, the receivers spend pubkey and scan private key, and tx outputs as inputs
 * and returns a list of found outputs, where the found output consists of the xonly pubkey and the tweak data
 * needed to spend it
 * /
int secp256k1_silentpayments_receiver_scan_outputs(
    const secp256k1_context *ctx,
    secp256k1_silentpayments_output **found_outputs,
    const secp256k1_pubkey **input_pubkeys,
    size_t n_input_pubkeys,
    const secp256k1_pubkey *receiver_spend_pubkey,
    const unsigned char *receiver_scan_seckey,
    const secp256k1_xonly_pubkey * const *tx_outputs,
    size_t n_tx_outputs
)
/** 
 * Takes tx input pubkeys and the smallest outpoint and returns a pubkey
 * that can be stored and distributed to clients who need to scan but dont have
 * access to block data/tx data (index for wallet rescanning, light clients, etc).
 * /
int secp256k1_silentpayments_receiver_create_index_data(
    const secp256k1_context *ctx,
    secp256k1_pubkey *A_sum_tweaked,
    const secp256k1_pubkey **input_pubkeys,
    size_t n_input_pubkeys,
    const unsigned char *outpoint_smallest36
)
/**
 * takes the index data (A_sum*input_hash), tx outputs, receivers spend pubkey and scan priv key
 * and returns found outputs. Intended for light clients/wallet rescanning.
 * /
int secp256k1_silentpayments_scan_from_index_data(
    const secp256k1_context *ctx,
    secp256k1_silentpayments_outputs **found_outputs,
    const secp256k1_pubkey *receiver_spend_pubkey,
    const unsigned char *receiver_scan_seckey,
    const secp256k1_pubkey *A_sum_tweaked,
    const secp256k1_xonly_pubkey *tx_outputs,
)
/** 
 * produces a signature for a silent payments taproot output
 * this function is just a wrapper function around schnorrsign which first
 * tweaks the receivers spend key with the tweak data found during scanning.
 * this way, we avoid needing to expose any `scalar_add` functions to the caller.
 * /
int secp256k1_silentpayments_sign32(
    const secp256k1_context *ctx,
    unsigned char *sig64,
    const unsigned char *msg32,
    const secp256k1_keypair *keypair,
    const unsigned char *aux_rand32
    const unsigned char *tweak32
)

This is more of an example than a proposal to demonstrate a few simple function calls and not exposing things that could be abused or used unsafely. The main question here is "would something like this fit as a module for libsecp256k1," considering its not really a generic cryptographic primitive but also not quite the a full silent payments v0 implementation in that the sender and receiver still need to filter the inputs. If the answer is yes, I think we can start from here and figure out how to add labels in sane way (I have a few ideas for labels, both with opaque data types or stages). If the answer is no, then I think looking into other approaches, like a hazmat API is better.

I also spent some time thinking about whether or not this could be a more generic "non-interactive-multikey-ecdh" module that is used by a libsilentpayments or something, but this didn't seem super promising. Mainly because it wasn't clear that the hashing with a counter k would be generically useful, and without that we'd need to return an unhashed ECDH result. Also similar questions about whether the spend and scan key are generically useful or silent payments specific. Furthermore, we'd still need to do low-level operations even after the ECDH step (adding the spend pubkey, scanning with labels, etc), so it felt like just kicking the can down the road a bit.

<hr/> [@theStack](/bitcoin-core-secp256k1/contributor/thestack/)

To my understanding, secp256k1 as of now provides all the necessary routines for a full BIP352 implementation (Bitcoin Core PR https://github.com/bitcoin/bitcoin/pull/28122 followed that approach before it used this module). The two main reasons for a secp256k1 module (or library using secp256k1, if the libsilentpayments approach is followed) would be AFAICT 1) efficiency and 2) hiding cryptographic complexity from the user.

I think this was more an example of "could" rather than "should." From my understanding, bitcoin core is also a bit of a "privileged" user of secp256k1 and the goal of a module would be something generally useful for wallets outside of bitcoin core. Regarding efficiency, I'd be very surprised if this approach is less efficient than what we were originally doing in core, although IIRC bitcoin core is faster when it comes to hashing? The main advantages of doing it all here w.r.t efficiency is not need to serialize/deserialize all the time from compressed keys to group elements. Regarding benchmarking, I do still have the old version not using this module, if you want to compare with that! Would be nice to see some numbers!

@theStack I started refactoring the API based on #1471 (comment). I've only completed the sender side, but will continue working on the receiver side.

The main changes are:

1. Provide a single function for the sender: this means the sender doesn't need to worry about grouping addresses and ensuring they pick the right values for k
   • Requires heapsort (from the musig2 PR)
   • Removes the create_private_tweak_data routine
2. Remove the tweaked_pubkey routine (for light clients): instead, if the caller does not pass a pointer for input_hash, then include input_hash with the returned A_sum

The branch is still a bit rough so some of the comments / commit messages are likely correct. Mostly just looking for conceptual feedback and curious if you have any objections to this approach. The branch is https://github.com/josibake/secp256k1/tree/bip352-api-refactor . I've tried to keep the edits in the relevant commits so that if the changes make sense we can easily incorporate them into your branch.

@theStack I started refactoring the API based on #1471 (comment). I've only completed the sender side, but will continue working on the receiver side.

The branch is still a bit rough so some of the comments / commit messages are likely correct. Mostly just looking for conceptual feedback and curious if you have any objections to this approach. The branch is https://github.com/josibake/secp256k1/tree/bip352-api-refactor . I've tried to keep the edits in the relevant commits so that if the changes make sense we can easily incorporate them into your branch.

Thanks for pushing. A single-function API for sending that takes care of everything (even the scan-pubkey grouping, sort ftw!) seems a good idea to me. What's currently a problem, I think, is that the user doesn't have a way to determine which of the created outputs belong to which recipient. E.g. if the recipients are passed in in the order $(B1_{scan}, B1_{spend})$ and $(B2_{scan}, B2_{spend})$, the outputs could be created in the (unexpected) order $output_{B2}, output_{B1}$, if $B2_{scan}$ is lexographically smaller than $B1_{scan}$.

One solution for this might be to extend the recipient structure by the resulting x-only output key and let the function fill that out, i.e. passing the recipients as in/out-parameter?

A single-function API for sending that takes care of everything (even the scan-pubkey grouping, sort ftw!) seems a good idea to me.

yeah, the more I thought about it, we are already requiring the user to pass all of the keys at once so it didn't seem like we are gaining anything with separate function calls. In the future, it might make sense to have functions to enable sending where the sender does not have access to all of the private keys at once, but that will require a lot more thought and seems out of scope for now.

the user doesn't have a way to determine which of the created outputs belong to which recipient

Good catch, I overlooked this! I took your suggestion of extending the recipient struct and updated the branch. This has the added benefit of simplifying the function signature (i.e. no longer need to pass arguments for outputs and n_outputs).

Thinking about the receiver API a bit more, I realized we can't assume the receiver has access to the tx_outputs when scanning. For example, if the client is using BIP158 block filters, they would generate the scriptPubKey and then check if it is in the filter before downloading the block, or in the case of an electrum style client, they might generate the taproot output and then call the electrum backend to see if the scriptPubKey exists in the UTXO set.

Given this, what do you think about using a callback function for checking if the generated output exists / checking if the label exists? It seems libsecp256k1 does use this pattern already in the case of the ECDH module where the caller can provide their own hash function and using callbacks could allow for a much simpler, easy to use API but I'm not what the cost in performance would be or if this would work with language bindings (e.g. a javascript library using libsecp256k1). Curious to hear your thoughts.

the user doesn't have a way to determine which of the created outputs belong to which recipient

Good catch, I overlooked this! I took your suggestion of extending the recipient struct and updated the branch. This has the added benefit of simplifying the function signature (i.e. no longer need to pass arguments for outputs and n_outputs).

Ah indeed, smaller function signature is a nice benefit, especially since the number of parameters was quite high already. :+1:

As for the current version: I didn't think about this when I made the suggestion, but now having the generated outputs as pointers within the _silentpayments_recipient struct is a bit of tedious/weird interface for users, as they would have to allocate memory also for those (first, for the array of pointers, and then also for the _xonly_pubkey objects as well!), in addition to the struct itself. Do you think it's an acceptable choice if we just drop n_outputs from the struct and store the output directly as instance, i.e.

typedef struct {
    secp256k1_pubkey scan_pubkey;
    secp256k1_pubkey spend_pubkey;
    secp256k1_xonly_pubkey generated_output;
} secp256k1_silentpayments_recipient;

This should make things much easier imho, as the user only has to allocate memory for a single struct instance per recipient. It should also make the implementation slightly simpler (one loop less). I'm assuming here that creating multiple outputs to the same SP address is rather the exception than the rule. Even if it is used more often, I think repeatedly filling out the same scan/spend keypairs is not a problem for wallets.

Thinking about the receiver API a bit more, I realized we can't assume the receiver has access to the tx_outputs when scanning. For example, if the client is using BIP158 block filters, they would generate the scriptPubKey and then check if it is in the filter before downloading the block, or in the case of an electrum style client, they might generate the taproot output and then call the electrum backend to see if the scriptPubKey exists in the UTXO set.

Oh, wasn't aware of that. The two examples you state here are only applicable for the non-label case though, right (not even the change address label)? To my understanding, when scanning for labels, we always need all outputs of a tx. Is it thinkable to have two scanning interfaces, one for the simple non-label case where simply the output is returned, and one for labels, where all outputs are passed and the labels scanning is done?

Given this, what do you think about using a callback function for checking if the generated output exists / checking if the label exists? It seems libsecp256k1 does use this pattern already in the case of the ECDH module where the caller can provide their own hash function and using callbacks could allow for a much simpler, easy to use API but I'm not what the cost in performance would be or if this would work with language bindings (e.g. a javascript library using libsecp256k1). Curious to hear your thoughts.

Interesting idea, I'd intuitively assume it's neither a huge for problem for performance nor for other language bindings, but would have to check deeper.

Do you think it's an acceptable choice if we just drop n_outputs from the struct and store the output directly as instance

This is much simpler. Also agree that cases where a sender is creating multiple outputs for the same recipient will likely be rare, and even in those instances it might still make sense to pass the same address multiple times (e.g. to easily match up the generated address back to the requested amount). This ended up being a bit tedious due to the fact that the generated outputs depend on the order of the recipients, but rather than hack around it here, I updated the test vectors to include all possible output sets.

Oh, wasn't aware of that. The two examples you state here are only applicable for the non-label case though, right (not even the change address label)? To my understanding, when scanning for labels, we always need all outputs of a tx.

Correct, you do need the tx outputs to scan for labels using the (more efficient) subtraction technique. Worth mentioning you can scan for labels without the tx outputs (e.g. the change label) by just adding the label to each output, but this is really inefficient as the number of labels grows.

one for the simple non-label case where simply the output is returned, and one for labels, where all outputs are passed and the labels scanning is done?

I think this makes sense. I'd imagine light clients will not support labels, whereas full nodes will, so it seems reasonable to provide two interfaces.

Still mulling over the callbacks idea, will try to have a concrete proposal over the next few days. I've updated the branch in the meanwhile with the sending changes.

@josibake I had a quick look at the API in your branch, a few minor comments:

• The In/Out parameter secp256k1_silentpayments_recipient seems a bit strange. Why not just group by index? secp256k1_silentpayments_recipient could just contain the scan and spend pks, and the i-th generated output would correspond to the i-th provided secp256k1_silentpayments_recipient?
• Instead of taking a const unsigned char * const *taproot_seckeys argument and multiplying each seckey with base point G to see if it needs to be negated, you could accept an array of secp256k1_xonly_keypair, which holds both the seckey and the pubkey. Often the caller will already have the pubkey and would, if the function wouldn't accept xonly_keypair, do a costly recomputation of the public key unnecessarily. If the caller doesn't have an xonly_keypair, they can just create one.
• I can imagine that others disagree, but I wouldn't add another sign32 function if the spend key can just be tweaked via some keypair_tweak function and then given to the regular schnorrsig_sign32 function. Then this would be the same workflow for a silent payments derived key to sign via schnorrsig_custom. And a similar workflow for the musig module (where tweaking happens via secp256k1_musig_pubkey_tweak_add.

Thanks for the review, @jonasnick !

* The In/Out parameter `secp256k1_silentpayments_recipient` seems a bit strange. Why not just group by index? `secp256k1_silentpayments_recipient` could just contain the scan and spend pks, and the i-th generated output would correspond to the i-th provided `secp256k1_silentpayments_recipient`?

IIUC, this means bringing back the out param taproot_outputs and n_taproot_outputs (or just reuse n_recipients), correct? We could use the index in the taproot_outputs array to match to the recipient (this is because the heapsort does the sort in place, so the recipient order after sorting would match the order in the taproot_outputs array, right?). This seems more complex for the caller in that the need to initialize the taproot output array and match up the indices and I don't see any clear advantage, but perhaps I'm missing something? Also fine to go with the proposed change even if the reason is just that this is a more common pattern

* Instead of taking a `const unsigned char * const *taproot_seckeys` argument and multiplying each seckey with base point G to see if it needs to be negated, you could accept an array of `secp256k1_xonly_keypair`, which holds both the seckey and the pubkey. Often the caller will already have the pubkey and would, if the function wouldn't accept `xonly_keypair`, do a costly recomputation of the public key unnecessarily. If the caller doesn't have an `xonly_keypair`, they can just create one.

Great point, this was on my list of things to change but I forgot to include it!

* I can imagine that others disagree, but I wouldn't add another `sign32` function if the spend key can just be tweaked via some `keypair_tweak` function and then given to the regular `schnorrsig_sign32` function. Then this would be the same workflow for a silent payments derived key to sign via `schnorrsig_custom`. And a similar workflow for the musig module (where tweaking happens via `secp256k1_musig_pubkey_tweak_add`.

I agree. The silent payments protocol doesn't really have anything to do with signing because once the spend key is tweaked, it is just a regular taproot output. My initial thinking was not wanting to expose any low level tweaking functions in the module, but based on the recent IRC discussion regarding a hazmat API, this seems less of a concern.

We could use the index in the taproot_outputs array to match to the recipient (this is because the heapsort does the sort in place, so the recipient order after sorting would match the order in the taproot_outputs array, right?). @josibake I missed that the function sorts internally. I had only looked at the API, but the BIP clearly states "Group receiver silent payment addresses by B_scan". So it seems like the purpose of sorting is to make sure that any two tuples (B_scan, B_m), (B_scan', B_m') with B_scan = B_scan' are next to each other in the array. Isn't that something that can be ensured by the caller? I suppose one problem is that if the caller doesn't do that correctly, the resulting outputs are garbage and are either burned or require some manual procedure to recover.

So I guess an alternative would be:

1. Change the API as I had suggested (remove generated_output from recipient, change recipient to be an input-only parameter, and add taproot_outputs and n_taproot_outputs as output parameters).
2. Check that the recipients array is sorted to make sure that grouping was done correctly. If it wasn't, return 0.

Just thinking aloud. I don't think this is clearly better than having an In/Out argument as you had designed it.

EDIT: Actually, I think there's a case to be made that the caller organizing the recipient array correctly before calling the function (i.e., my suggested alternative) is cleaner than having the caller scan through the output of the function to find the correct scanning key and the corresponding generated_outputs.

So it seems like the purpose of sorting is to make sure that any two tuples (B_scan, B_m), (B_scan', B_m') with B_scan = B_scan' are next to each other in the array.

Yep! This is because the counter k is incremented over a single B_scan for each value of B_m (included repeated values of B_m. As you mentioned, if the sender does not do this grouping correctly the recipient will be unable to find the outputs, so I think we will always need the sorting step. My thinking was if we are going to do the sorting regardless, it seemed better to abstract the grouping step away from the caller completely.

1. Change the API as I had suggested (remove generated_output from recipient, change recipient to be an input-only parameter, and add taproot_outputs and n_taproot_outputs as output parameters).
2. Sort inside the function to make sure that grouping was done correctly. If it wasn't, return 0.

IIUC, heapsort is unstable which means if the caller groups and passes in the tuples [(B_scan, B_m), (B_scan, B_m')...], we might end up reordering them to [(B_scan, B_m'), (B_scan, B_m) ...]. If the caller meant to send 1 BTC to (B_scan, B_m) and 2 BTC to (B_scan, B_m'), it seems there's a risk the values might get switched using the index approach. So I think we'd have to also reconsider how we are verifying the grouping (e.g. use a different sorting algorithm) if we wanted to go with the approach you're suggesting.

@theStack I pushed a refactor of the recipient API to https://github.com/josibake/secp256k1/tree/bip352-api-refactor, let me know what you think. Most notably, it allows for the receiver to scan the transaction in a single call (vs scanning each output individually and managing values of k). This simplifies things for the receiver and I think gets us a bit more speed by reducing some overhead related to serializing/deserializing pubkeys.

I also removed the _seckey function: using the label_lookup callback, I am able to get the label tweak and apply it directly while scanning, so the end result is one single sp_tweak. Given that, it seems we can just use the _ec_seckey_add function directly before signing.

For clients that do not have access to the transaction outputs (e.g. a BIP158 client), they are able to scan using the create_public_tweak_data, create_shared_secret, and create_output functions. They would do so by creating an output, checking if it exists in the UTXO set, and proceeding to create the next output if a match is found. Once they have all of the outputs, they can get the necessary transaction data via their preferred source (e.g. downloading the whole block, downloading the transaction, downloading the outpoints, etc). Another option would be to create a single output, check if it exits in a block, download the full block if it does and continue scanning with the _receiver_scan_outputs function since they would now have all of the transaction outputs.

@jonasnick (since you've been looking at the API), one thing that's kinda gross about this approach is the found_objects struct. I couldn't really think of a better way to do this since we don't know how many found_objects there will be before scanning and I wanted to avoid having the scanner go over each output individually (the old approach). Curious if you have any ideas on how we could improve this.

@josibake

My thinking was if we are going to do the sorting regardless, it seemed better to abstract the grouping step away from the caller completely.

It's not abstracted away completely though because, as far as I understand, the caller needs to search through the In/Out recipients array to find the right (B_scan, B_m) tuple.

Anyway, my suggestion is flawed because it would actually require the caller to sort instead of just grouping the inputs recipients correctly.

@jonasnick (since you've been looking at the API), one thing that's kinda gross about this approach is the found_objects struct.

You mean found_outputs? Unfortunately I don't have an idea right now for a cleaner approach.

Speaking of the API, what's the reason for exposing create_shared_secret to the user instead of just calling it internally in sender_create_outputs and receiver_scan_outputs?

the caller needs to search through the In/Out recipients array to find the right (B_scan, B_m) tuple.

You mean to match up the original sp1qxxx: amount address to the correct generated output? Good point, which is where being able to use the index from the original array would be nice. Will give this some thought. When I say "abstracted" from the caller, I was more referring to the caller not needing to worry about ordering the recipients in any particular way before calling the function.

Speaking of the API, what's the reason for exposing create_shared_secret to the user instead of just calling it internally in sender_create_outputs and receiver_scan_outputs?

For the sender, no reason. create_shared_secret and create_output_pubkey are called internally in sender_create_outputs. For the receiver, there are three clients:

• Index: indexes transactions for wallet rescanning and for serving light clients (uses create_public_tweak_data)
• Fullnode: scans the transaction using receiver_scan_outputs or is doing a wallet rescan using the index data
  • A Fullnode might also be scanning for multiple scan secret keys, which is why it made sense to me to separate create_shared_secret from receiver_scan_outputs. This would allow a node to first do the ECDH step (creating multiple shared secrets) and then scan the transaction with each generated shared secret. You could also have the scan seckeys not on the scanning application and instead in an HSM or some separate application
• Light clients: likely does not have access to the transaction, so generates an output using create_output_pubkey and checks if it exists in the UTXO set
  • In this model, it makes sense to separate create_shared_secret and create_output_pubkey, since create shared secret is a fairly expensive operation, so we'd want a light client to be able to reuse the shared_secret when creating multiple outputs

That being said, open to suggestions on how we could lock down the API even further!

@theStack I pushed a refactor of the recipient API to https://github.com/josibake/secp256k1/tree/bip352-api-refactor, let me know what you think.

Thanks, looks good at a first glance, will go deeper in a bit. One thing I wondered: if an output is found with a direct match, what is the label field in secp256k1_silentpayments_found_output set to? Do we need some flag to differ between "found via direct match" and "found via label" (assuming we don't want to set label to point of infinity, which seems hacky)? Currently, it seems that label is not set at all, I assume the idea is to set it within the if-branch that follows the label_lookup callback invocation.

I agree that the way the result is returned via found_outputs is a bit cumbersome. One alternative approach could be to also pass an in-out parameter here with a list of struct instances that contains both the tx-output to scan for and the found results (label + tweak), together with a boolean flag found, e.g. something like:

typedef struct {
    /* input (in-param part) */
    secp256k1_xonly_pubkey tx_output;

    /* result part (out-param part), only relevant if found is set to 1 */
    int found;
    secp256k1_pubkey label;
    unsigned char tweak[32];
} secp256k1_silentpayments_scanned_output;

That would save the user the headache of allocating memory twice and lead to an interface with less parameters (e.g. the n_found_outputs out-param is not strictly needed anymore, as it's implicit the by the number of instances that have found set to 1). On the other hand, having to iterate through the whole in-out structure array again to collect the found results is admiteddly also quite ugly and presumably slow for transactions with lots of x-only outputs, so absolutely not sure. Just wanted to drop the idea, as it kind of picks up the same interface idea used for the sender side API. Curious on what you think.

// EDIT: the "too slow" problem could be mitigated by having an out-param that returns if any output was found at all. If it is set to zero, the caller doesn't have to bother with inspecting the result and can just continue scanning the next tx.

From an organizational point of view, do you think it makes sense to open a new PR for the refactored branch soon? This PR's description doesn't match the new high-level module approach anymore and with soon reaching >100 comments, it also will start to suffer from the typical github UI problems soon. Would also be nice being able to directly leave code review comments for refactored API. The drawback is that we'd lose some of the previous discussion (or, at least it's harder to find).

Currently, it seems that label is not set at all, I assume the idea is to set it within the if-branch that follows the label_lookup callback invocation

Oops! That was an oversight. It would only be set if the output found contained a label, not set in the case of a direct match. The idea was to make it easy for the caller to match up the output to the correct label, but something else I considered is making that the responsibility of the callback function.

From an organizational point of view, do you think it makes sense to open a new PR for the refactored branch soon

I’ll defer to the libsecp maintainers on what they prefer. For me, I don’t mind merging the branch into this PR and updating the description, but I’m also happy to open an entirely new PR. Whichever is easiest!

Will read the rest of your comment more carefully and respond later.

One alternative approach could be to also pass an in-out parameter here with a list of struct instances that contains both the tx-output to scan for and the found results (label + tweak), together with a boolean flag found

I think this makes more sense than what I have now. Currently, the caller already needs to allocate found_outputs to be the same size as tx_outputs (in the event every output is a payment to the recipient). Seems easy enough to have them iterate through the list again after scanning is finished and grab all the outputs for them (by checking the boolean). They would have the scriptPubKey, the tweak, and the label if used all in one place.

@jonasnick

EDIT: Actually, I think there's a case to be made that the caller organizing the recipient array correctly before calling the function (i.e., my suggested alternative) is cleaner than having the caller scan through the output of the function to find the correct scanning key and the corresponding generated_outputs.

I'm starting to agree, my only concern is I'd still want the sending function to verify that the addresses are in the correct groupings and fail otherwise. Sorting seemed like the easiest way to do this, but another idea is something like the following:

    if (n_recipients < 2) return true;
    for (i = 1; i < n_recipeints; i++) {
        if (secp256k1_ec_pubkey_cmp(ctx, recipients[i-1].scan_pubkey, recipients[i].scan_pubkey) != 0) {
            for (j = i + 1; j < size; j++) {
                if (secp256k1_ec_pubkey_cmp(ctx, recipients[i-1].scan_pubkey, recipients[j].scan_pubkey) == 0) {
                    return 0;
                }
            }
        }
    }
    return 1;

Essentially, anytime there is a scan key change, check the remainder of the list to see if the last seen scan key shows up again. This wouldn't change ordering of the list, but the downside is that the check is O(n^2) in the worst case. But in the context of recipient addresses we kinda know the upper bound in that you can't really request more outputs than you can fit in a single transaction (roughly 9k outputs, see https://bitcoin.stackexchange.com/questions/116958/what-is-the-maximum-number-of-taproot-transactions-that-can-be-mined-in-a-single), so maybe O(n^2) is okay? In the context of a signing device, probably not, but just spitballing some ideas.

@josibake

You mean to match up the original sp1qxxx: amount address to the correct generated output?

Yes.

This wouldn't change ordering of the list, but the downside is that the check is O(n^2) in the worst case.

I would try to avoid adding a function with O(n^2) complexity.

Here's yet another alternative, which adds an index field to the recipient list, sorts the recipients inside the sender_create_outputs but returns the generated_output at the "right" position:

/* In param */
typedef struct {
    secp256k1_pubkey scan_pubkey;
    secp256k1_pubkey spend_pubkey;
    size_t idx;
} secp256k1_silentpayments_recipient;

int secp256k1_silentpayments_sender_create_outputs(secp256k1_xonly_pubkey *generated_output, secp256k1_silentpayments_recipient **recipients) {
  /* sort based on (scan_pubkey, spend_pubkey) */
  recipients = sort(recipients)
  for rec in recipient {
    generated_output[rec->idx] = create_output(...)
  }
}

This modifies the recipient array which may still be annoying for the caller. Of course, the caller can just copy the array to avoid that. Or we could sort it back based on the idx field, but that seems to be overkill. Would the Bitcoin Core implementation require the order of the recipient array unmodified?

The caller would be responsible for setting idx to the right value, but this could be easily checked in sender_create_outputs. @josibake @theStack

From an organizational point of view, do you think it makes sense to open a new PR for the refactored branch soon? I’ll defer to the libsecp maintainers on what they prefer.

I have a slight preference for opening a new PR since josi's branch is more a rewrite than a refactor and a lot of the discussion in this PR doesn't apply.

@josibake

For the receiver, there are three clients:

This would allow a node to first do the ECDH step (creating multiple shared secrets) and then scan the transaction with each generated shared secret.

I don't see advantage of this. Wouldn't it be an equal amount of work to scan the transaction with each scan secret key and generate the shared secret internally?

You could also have the scan seckeys not on the scanning application and instead in an HSM or some separate application

If you can run create_shared_secret on the HSM, why couldn't you run receiver_scan_outputs?

In this model, it makes sense to separate create_shared_secret and create_output_pubkey

I see. Or have create_output_pubkeys function that derives the shared_secret and creates one or more pubkeys.

Wouldn't it be an equal amount of work to scan the transaction with each scan secret key and generate the shared secret internally?

I misspoke, it’s not the shared secret part, but the summing of the input public keys that would duplicated work when scanning with multiple scan keys. So it seems we could have a receiver_scan_outputs function that takes the summed input pubkeys as an input, a scan secret key, and an optional smallest_outpoint (null if the input hash is already included with the summed input pubkeys) and have the share secret be created internally.

Regarding an HSM, I suppose there’s nothing stopping it from taking everything it needs to scan the transaction since the data needed will always be less than the maximum transaction size.

Or have create_output_pubkeys function that derives the shared_secret and creates one or more pubkeys.

I think for this to work the client would need to know the total number of outputs in the transaction to avoid needing to redo ECDH in the event they don’t generate enough pubkeys the first time. However, if we assume the client knows the total number of outputs, we could make this function more closely match the receiver_scan_outputs function by using a output_lookup callback (instead of a label lookup). This way we could completely remove create_shared_secret from the API

(apologies for any typos, doing this on a phone)

I have a slight preference for opening a new PR since josi's branch is more a rewrite than a refactor and a lot of the discussion in this PR doesn't apply.

I've opened #1519 as a new PR, which attempts to incorporate all of the outstanding feedback here and includes a few new ideas.

I've opened #1519 as a new PR, which attempts to incorporate all of the outstanding feedback here and includes a few new ideas.

Let's close this one then.