Silent Payments (BIP352) module – discussion about scope and interface #1427

1. 
   theStack commented at 2:02 am on October 1, 2023: contributor

   At the last CoreDev meeting the idea of creating a libsecp Silent Payments (BIP352) module for handling the low-level parts was brought up. I’ve spent some time recently studying the BIP and it’s current implementation (https://github.com/bitcoin/bips/pull/1458, see also tracking issue https://github.com/bitcoin/bitcoin/issues/28536) and thought about what parts would make sense to put into this new module. A good amount of code is ready to use, but before opening a concrete PR, I’d like to discuss the related questions

   • What is the exact scope of a potential libsecp256k1 silent payments module? and
   • What should a sane interface look like?

   Note that when I talk about the caller side I’m not only thinking about Bitcoin Core (though this would obviously be the first one taking use of it); one of the benefits of providing a module would be to help other implementations with the hard low-level math parts about Silent Payments, i.e. the interface should definitely have the goal to be easy and intuitive to use.

   I’m listing some basic ingredients from the Silent Payments protocol and my thoughts about scope/interface to each of them:

   1. calculate the outpoints hash (both sender and receiver sides)

   (see https://github.com/josibake/bips/blob/silent-payments-bip/bip-0352.mediawiki#user-content-Outpoints_hash)

   This step includes sorting a given list of serialized 36-bytes outpoints (=32-bytes txid, 4-bytes vout) and then applying a SHA256 hash to the concatenated result. Should a SP module living in libsecp256k1 land be involved in any of this at all? Three variants are possible:

   1. both sorting and hashing is done by the SP module
   2. sorting is done by the caller, hashing is done by the SP module
   3. both sorting and hashing has to be done by the caller

   For the sake of simplicity, I’m leaning towards variant 3) here. Though it would be ideal if users wouldn’t need to take care of any intermediate computations needed for the protocol at all (not even hashing), it seems a bit odd to pass in specific transaction-internal data to an ECC-focused library. Looking at other libsecp modules, we primarily work with “curve-relevant” inputs like scalars and group elements (and their serializations), and I feel that handling more than that is out of scope and would be better suited for a different, higher-level library. Invoking a sorting algorithm in libsecp256k1 also just feels kind of odd (though technically easily possible, as qsort(3) is part of the standard library for C89).

   Note that the libsecp256k1 implementation of SHA256 is also not optimized and hence slower than the implementation in Bitcoin Core on common architectures.

   2. calculate the sum tweak of input private keys (sender side)

   (see https://github.com/josibake/bips/blob/silent-payments-bip/bip-0352.mediawiki#user-content-Creating_outputs)

   This definitely sounds like something a SP module should take care of. It seems trivial to provide an interface for this part, and one would think that a simple function taking a single list of private keys (i.e. a pointer plus a counter in C world) would do it. The extra challenge here though is that for private keys that are used for taproot outputs, we need to negate them if they’d result in points with an odd y coordinate (to enforce even y parity for the scanning side which only sees an x-only-pubkey, see also https://github.com/josibake/bips/blob/silent-payments-bip/bip-0352.mediawiki#cite_note-why_negate_taproot_private_keys_15). So some of the keys need special treatment. How do we cope with that w.r.t. to an interface that is not too confusing for the user?

   1. Pass two different lists, ones for private keys belonging to pre-taproot outputs and one for keys that result in taproot outputs? (or, create a silentpayments_privkey struct that has an extra flag which indicates if even y parity has to be enforced and use that?)
   2. Provide a helper function like secp256k1_silentpayments_privkey_enforce_even_y_parity that has to be applied on all private keys resulting in BIP341 outputs, before those private keys are passed to the summing function?

   Both approaches don’t sound ideal to me, to be honest, the first one is probably the lesser evil.

   3. calculate the sum tweak of input public keys (receiver side)

   (see https://github.com/josibake/bips/blob/silent-payments-bip/bip-0352.mediawiki#user-content-Scanning)

   In contrast to private keys which are always just 32-bytes long for our purposes, public keys come in different sizes (33, 65 and 32 bytes) and formats (“full”, x-only). The question arises how a user would pass in those different types in a single function call. Should we

   1. Pass in two lists, one of the type secp256k1_pubkey, another one of the type secp256k1_xonly_pubkey? (The user would need to call the corresponding parse functions before, obviously)
   2. Provide a function that let’s the user convert xonly-pubkeys to pubkeys first (in this context, this should be simple by just prepending a 0x02 byte, IIUC) and then only take a single list of secp256k1_pubkey elements?
   3. Something else?

   4. calculate the shared secret using unhashed ECDH (both sides)

   This seems obvious to put into the library, users shouldn’t have the need define a “not-a-hash”-hash-functions to pass onto secp256k1_ecdh manually :)

   ---

   I have to admit after digging deeper it seems that providing an easy interface seems to be a bit more challening than I thought to, especially considering that this can lead to ugly glue code to translate between C++ and C worlds.

   Any thoughts? Happy to hear any input, even an opinion like “please, keep stuff like this stuff completely out of libsecp” is helpful if it is well-founded.

2. theStack cross-referenced this on Oct 1, 2023 from issue BIP352 tracking issue by josibake
3. 
   josibake commented at 5:31 pm on October 2, 2023: member

   Thanks @theStack for starting this discussion! Will have more comments once I finish reading the full issue, but wanted to quickly comment on the outpoint sorting/hashing:

   Per https://github.com/bitcoin/bips/pull/1458#discussion_r1337755627, requiring a sort could make things difficult for HWW. The suggestion from the comment was to instead do something like hash256(outpoint1) + hash256(outpoint2) + ..., which gives us a permutation-invariant hash. I still need to benchmark to see how much slower this makes the scanning, but if the difference is negligible I’d prefer going with this over the sorted hash.

4. 
   jonasnick commented at 1:12 pm on October 11, 2023: contributor

   I haven’t really thought holistically about how a silent payment module would look like, but here are some direct answers without taking the full context into account.

   1. calculate the outpoints hash (both sender and receiver sides)

   I think it’s ok to do outpoint hashing outside of the module. As you point out, callers can hash faster (as long as we don’t have #702). And the consequences of not hashing (correctly) are limited (as opposed to ECDSA, for example).

   As for sorting, the MuSig2 module (currently only in -zkp) adds an in-place, iterative O(n*log(n)) heapsort function that could potentially be used in the module. The reason we did this is that there’s no guarantee that qsort is fast for maliciously crafted inputs.

   2. calculate the sum tweak of input private keys (sender side)

   Passing “two different lists” sounds workable to me. To avoid having to recompute the points corresponding to the secret keys in the xonly list, they should not be passed as byte arrays but as part of keypairs.

   0secp256k1_spay_receiver_pubkey(..., unsigned char *plain_seckeys, secp256k1_keypair *xonly_keypairs, ...)
   

   It is arguably difficult to explain how this function is supposed to be called, but this complexity seems inherent in having the caller designate pubkeys used in taproot (and potentially future segwit versions that do xonly).

   If I understand the algorithm correctly, the libsecp function would return an array of tweaked pubkeys, one for each Bm and change output.

   3. calculate the sum tweak of input public keys (receiver side)

   Passing two lists seems like an okay approach. Conversion functions may just lead to additional confusion. Without them, we maintain this relatively straightforward model:

   0xonly pubkey encoding -> use xonly_parse -> use in functions that accept xonly_pubkeys
   1compressed pubkey encoding -> use ec_pubkey_parse -> use in functions that accept ec_pubkeys
   

5. real-or-random added the label feature on Nov 13, 2023

Contributors
theStack josibake jonasnick

Labels
feature