BIP-352: handle invalid privkey / pubkey sums for sending / scanning, add changelog

theStack commented at 1:16 pm on June 14, 2024: contributor

See the discussion in the corresponding secp256k1 PR (https://github.com/bitcoin-core/secp256k1/pull/1519#issuecomment-2142599641, https://github.com/bitcoin-core/secp256k1/pull/1519#issuecomment-2143167510, https://github.com/bitcoin-core/secp256k1/pull/1519#issuecomment-2144837459), where it was recommended to include this corner-case in the BIP by real-or-random:

Indeed, this should be in the BIP, ideally even in the pseudocode. If our code starts to reject “payments”, then better be authorized by the standard.

Note that this PR right now only includes the absolute minimum change; happy to include further changes if demanded (reflect this in the Python implementation, add test case), but not sure what are common rules for BIP amendments and if additional changes are worth it for a corner-case. For an additional test vector, one could take the example tx that has been published on signet: d73f4a19f3973e90af6df62e735bb7b31f3d5ab8e7e26e7950651b436d093313

theStack commented at 1:16 pm on June 14, 2024: contributor

cc @josibake @real-or-random

jonatack added the label Proposed BIP modification on Jun 14, 2024

jonatack added the label Pending acceptance on Jun 14, 2024

in bip-0352.mediawiki:340 in 51e7ffbce8 outdated

336@@ -337,6 +337,7 @@ If each of the checks in ''[[#scanning-silent-payment-eligible-transactions|Scan
337 
338 * Generate the ''input_hash'' with the smallest outpoint lexicographically, using the method described above
339 * Let ''A = A<sub>1</sub> + A<sub>2</sub> + ... + A<sub>n</sub>'', where each ''A<sub>i</sub>'' is the public key of an input from the ''[[#inputs-for-shared-secret-derivation|Inputs For Shared Secret Derivation]]'' list
340+** In case ''A'' is the point at infinity, the transaction is not silent payment eligible, and one should proceed with the next one.

josibake commented at 6:41 pm on June 17, 2024:

From what I understand, the point at infinity is not a valid point on the curve, so it might be better to say something like:

0** If ''A'' is not a valid point, i.e., if the sum of the input public keys results in the point at infinity, fail

real-or-random commented at 8:28 am on June 18, 2024:

Well, the point at infinity is certainly in the group (and thus a possible result of the addition). Whether it’s “on the curve” depends on your definition of curve, and whether it’s a “valid point” probably depends on the context. So I think the original text was slightly better (but I guess either is fine in the end).

josibake commented at 1:33 pm on June 18, 2024:

If “valid” is context specific, then I agree its best to mention the point at infinity specifically. “one should” feels a bit too much like a suggestion to me, perhaps something more like:

0** If ''A'' is the point at infinity, skip the transaction

and then also add a bullet point to the section above, “Scanning silent payment eligible transactions”

theStack commented at 11:13 pm on June 18, 2024:

SGTM, changed as suggested.

josibake commented at 6:44 pm on June 17, 2024: member

Thanks for pointing this out, @theStack ! If you are able to add a test case, that would be great! If not, no worries, I can add one later this week.

real-or-random commented at 8:31 am on June 18, 2024: contributor

but not sure what are common rules for BIP amendments and if additional changes are worth it for a corner-case.

I’m not sure if there are common rules, but I think it’s good practice to update BIPs to clarify such cases. And then if the text is changed, then the Python code should also be changed.

I don’t want to make it too complicated, but it may be a good idea to include a changelog, like we did in BIP327: https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki#change-log (this one looks long because we started versioning even before the BIP was merged into the repo here…)

theStack force-pushed on Jun 18, 2024

theStack commented at 11:13 pm on June 18, 2024: contributor

Thanks for the feedback so far!

Thanks for pointing this out, @theStack ! If you are able to add a test case, that would be great! If not, no worries, I can add one later this week.

Added a receiver test case with input data filled in from https://mempool.space/signet/tx/d73f4a19f3973e90af6df62e735bb7b31f3d5ab8e7e26e7950651b436d093313 and dummy data for key_material and address as those fields are not relevant for the case.

but not sure what are common rules for BIP amendments and if additional changes are worth it for a corner-case.

I’m not sure if there are common rules, but I think it’s good practice to update BIPs to clarify such cases. And then if the text is changed, then the Python code should also be changed.

Agree, done. Note that with the secp256k1 module used here (it’s the one Bitcoin Core used in the test framework before https://github.com/bitcoin/bitcoin/pull/26222 was merged), there seems to be no obvious way to check if a public key corresponds to point at infinity, so it’s checked indirectly if its serialization (.get_bytes()) returns None. I thought that it’s maybe worth it to update the secp256k1 implementation to one that follows best practices and has a nicer API (I think you were working on such a Python module, that’d probably be a good choice?), but that’s of course outside of the scope of this PR.

I don’t want to make it too complicated, but it may be a good idea to include a changelog, like we did in BIP327: https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki#change-log (this one looks long because we started versioning even before the BIP was merged into the repo here…)

Seems reasonable to me, curious to get opinions from the BIP authors about the details (verbosity, concrete versioning used etc.), happy to pick up suggestions.

davidaucoin7377 commented at 11:40 pm on June 18, 2024: none

Test run

bitcoin deleted a comment on Jun 18, 2024

real-or-random commented at 1:39 pm on June 19, 2024: contributor

and then also add a bullet point to the section above, “Scanning silent payment eligible transactions”

nit: I don’t think anyone will misinterpret this, but it’s this is a tiny bit confusing because of the text just above the algorithm:

0If each of the checks in ''[[#scanning-silent-payment-eligible-transactions|Scanning silent payment eligible transactions]]'' passes, the receiving wallet must:

It may be a cleaner not to add the bullet point. The checks in the bullet points seem to be rather syntactical checks, so I think it’s okay to omit this one.

I thought that it’s maybe worth it to update the secp256k1 implementation to one that follows best practices and has a nicer API (I think you were working on such a Python module, that’d probably be a good choice?), but that’s of course outside of the scope of this PR.

Yep, we’ll hopefully have something soon because we also use it in our draft for the DKG BIP, which we want to post to the mailing list in the next weeks.

edit: I think it won’t hurt to add an “if” and a test case also on the sender side. This can also be hit with specifically crafted secret keys, but it’s not entirely crazy that someone else generates secret keys for you (e.g., in some special custodial protocol or secret keys printed on physical coins, etc..)

theStack force-pushed on Jun 19, 2024

theStack commented at 10:50 pm on June 19, 2024: contributor

Removed the bullet point as suggested, and added a corresponding part for the sender side (“if a = 0, fail”). Also added that check in the reference implementation, though that code part is currently unreachable, as the pubkey summing is done first in the course of the input hash calculation, which seems a bit odd/unintuitive (see PR #1622).

5twelve approved

real-or-random approved

real-or-random commented at 7:43 am on June 20, 2024: contributor

ACK https://github.com/bitcoin/bips/pull/1620/commits/630466657557b073549f02c130de7bf5799b1cfa I haven’t checked the test vector but the diff looks good

jonatack requested review from josibake on Jun 20, 2024

jonatack commented at 1:04 pm on June 20, 2024: contributor

Light LGTM ACK

 0$ ./reference.py send_and_receive_test_vectors.json   
 1Simple send: two inputs
 2Simple send: two inputs, order reversed
 3Simple send: two inputs from the same transaction
 4Simple send: two inputs from the same transaction, order reversed
 5Outpoint ordering byte-lexicographically vs. vout-integer
 6Single recipient: multiple UTXOs from the same public key
 7Single recipient: taproot only inputs with even y-values
 8Single recipient: taproot only with mixed even/odd y-values
 9Single recipient: taproot input with even y-value and non-taproot input
10Single recipient: taproot input with odd y-value and non-taproot input
11Multiple outputs: multiple outputs, same recipient
12Multiple outputs: multiple outputs, multiple recipients
13Receiving with labels: label with even parity
14Receiving with labels: label with odd parity
15Receiving with labels: large label integer
16Multiple outputs with labels: un-labeled and labeled address; same recipient
17Multiple outputs with labels: multiple outputs for labeled address; same recipient
18Multiple outputs with labels: un-labeled, labeled, and multiple outputs for labeled address; same recipients
19Single recipient: use silent payments for sender change
20Single recipient: taproot input with NUMS point
21Pubkey extraction from malleated p2pkh
22P2PKH and P2WPKH Uncompressed Keys are skipped
23Skip invalid P2SH inputs
24Recipient ignores unrelated outputs
25No valid inputs, sender generates no outputs
26Input pubkeys sum up to the point at infinity, receiver skips tx
27All tests passed

in bip-0352/reference.py:132 in 6304666575 outdated

126@@ -127,6 +127,10 @@ def create_outputs(input_priv_keys: List[Tuple[ECKey, bool]], input_hash: bytes,
127         negated_keys.append(k)
128 
129     a_sum = sum(negated_keys)
130+    if not a_sum.valid:
131+        # Input privkeys sum is zero -> fail
132+        return []

josibake commented at 1:32 pm on June 21, 2024:

Any reason we can’t reuse the private keys corresponding to the public keys in the recipient test case here?

theStack commented at 2:42 pm on June 21, 2024:

No particular reason. However, I just noticed that my script for generating the example “pubkeys-sum-up-to-point-at-infinity” tx didn’t print the private keys, so I don’t have them anymore 😅 🤦‍♂️ will fix that and run it again to re-create the receiver test-case, and a sender one that matches. Shouldn’t take too long hopefully.

jonatack commented at 7:58 pm on June 22, 2024:

No particular reason. However, I just noticed that my script for generating the example “pubkeys-sum-up-to-point-at-infinity” tx didn’t print the private keys, so I don’t have them anymore 😅 🤦‍♂️ will fix that and run it again to re-create the receiver test-case, and a sender one that matches. Shouldn’t take too long hopefully.

Was this done, e.g. with “data corresponds to the newly generated tx fe788cf6578d547819def43d79e6c8f0153d4885f5a343d12bd03f34507aabd6)” in #1620 (comment)?

(edit, it seems so yes, but feel free to confirm)

theStack commented at 9:44 am on June 26, 2024:

No particular reason. However, I just noticed that my script for generating the example “pubkeys-sum-up-to-point-at-infinity” tx didn’t print the private keys, so I don’t have them anymore 😅 🤦‍♂️ will fix that and run it again to re-create the receiver test-case, and a sender one that matches. Shouldn’t take too long hopefully.

Was this done, e.g. with “data corresponds to the newly generated tx fe788cf6578d547819def43d79e6c8f0153d4885f5a343d12bd03f34507aabd6)” in #1620 (comment)?

(edit, it seems so yes, but feel free to confirm)

Yes, confirming (sorry for the late reply, missed that comment a few days ago).

jonatack commented at 5:24 pm on June 26, 2024:

@theStack thanks!

josibake commented at 1:45 pm on June 21, 2024: member

Looks good! Since we are now checking for a = 0, I think its worth adding a test case for the sender side, as well.

Regarding the changelog, I think this is a great suggestion and especially helpful when adding new test cases. I’d suggest adding one here and just reusing the semantic versioning system from BIP327.

(I realize this is a bit out of scope for this change, but I didn’t see a way to open an issue on the BIPs repo for this discussion)

More generally, seems worth it to formalizing the changelog format and versioning scheme as part of BIP2 (or whichever process BIP makes sense), e.g. something like “BIP should include a change log. If a change log is added it must use MAJOR.MINOR.PATH versioning scheme, where MAJOR is.. " etc.

I see a few BIPs have change logs in various formats, which got me thinking it would be nice to formalize it for consistency and also to avoid each BIP needing to either a) copy the text from another BIP explaining the change log or b) re-invent their own versioning scheme each time.

jonatack commented at 2:12 pm on June 21, 2024: contributor

@josibake 👍 on a changelog, like in BIPS 1, 327, and 340, for instance.

theStack commented at 2:43 pm on June 21, 2024: contributor

@josibake: Makes sense. Will rebase (necessary after #1622, thanks for the quick review and merge!), add a sending test-case and the changelog using semantic versioning system in a bit. Simple suggestion (assuming that we are not interested in the pre-merge history for now):

1.0.0 (2024-05-08): Initial version, merged as BIP-352
1.0.1 (2024-06-xx): Add steps to fail if private key sum is zero (for sender) or public key sum is point at infinity (for receiver), add corresponding test vectors

josibake commented at 4:29 pm on June 21, 2024: member

Simple suggestion

LGTM! I don’t think the pre-merge history is super relevant/useful here. Thanks for picking this up!

jonatack removed the label Pending acceptance on Jun 21, 2024

BIP-352: sending: add step to fail if input privkeys sum a is zero

The test vector data was generated with a Python script
(see https://github.com/theStack/bitcoin/blob/bc15ea8d0f282908b912dbf62bba816ecd82424d/contrib/silentpayments/submit_input_pubkeys_infinity_tx.py),
leading to the following output:

---------------------------------------------------------------------------------------------------------
     Privkey 1: a6df6a0bb448992a301df4258e06a89fe7cf7146f59ac3bd5ff26083acb22ceb
     Privkey 2: 592095f44bb766d5cfe20bda71f9575ed2df6b9fb9addc7e5fdffe0923841456
      Pubkey 1: 02557ef3e55b0a52489b4454c1169e06bdea43687a69c1f190eb50781644ab6975
      Pubkey 2: 03557ef3e55b0a52489b4454c1169e06bdea43687a69c1f190eb50781644ab6975
scriptPubKey 1: 00149d9e24f9fab4e35bf1a6df4b46cb533296ac0792
scriptPubKey 2: 00149860538b5575962776ed0814ae222c7d60c72d7b
     Address 1: tb1qnk0zf706kn34hudxma95dj6nx2t2cpujz7j5t5
     Address 2: tb1qnps98z64wktzwahdpq22ug3v04svwttm7gs8wn
-> Funding tx submitted: 3a286147b25e16ae80aff406f2673c6e565418c40f45c071245cdebc8a94174e

Taproot output address for spending tx: tb1pqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqkgkkf5
-> Spending tx submitted: fe788cf6578d547819def43d79e6c8f0153d4885f5a343d12bd03f34507aabd6
---------------------------------------------------------------------------------------------------------

47033c62dc

BIP-352: scanning: add step to skip tx if input pubkeys sum A is point at infinity

The input data for the test vector is taken from the signet transaction
fe788cf6578d547819def43d79e6c8f0153d4885f5a343d12bd03f34507aabd6
which spends two P2WPKH inputs with negated pubkeys (x, y) and (x, -y)
from the funding transaction 3a286147b25e16ae80aff406f2673c6e565418c40f45c071245cdebc8a94174e
(see also https://github.com/bitcoin-core/secp256k1/pull/1519#issuecomment-2143167510
and the output from the script in the previous commit message).

Co-authored-by: josibake <josibake@protonmail.com>

59cc43d727

theStack force-pushed on Jun 21, 2024

theStack force-pushed on Jun 22, 2024

theStack commented at 0:18 am on June 22, 2024: contributor

Will rebase (necessary after #1622, thanks for the quick review and merge!), add a sending test-case and the changelog using semantic versioning system in a bit.

Done. The commits are now divided up into sending and scanning parts (with test vectors directly included; data corresponds to the newly generated tx fe788cf6578d547819def43d79e6c8f0153d4885f5a343d12bd03f34507aabd6), and a changelog addition mostly copied from BIP327 (without the sentence about MAJOR version zero). Ready for review.

theStack renamed this:
~~BIP-352: scanning: add step to skip tx if input pubkey sum A is point at infinity~~
BIP-352: handle invalid privkey / pubkey sums for sending / scanning, add changelog
on Jun 22, 2024

in bip-0352.mediawiki:493 in 4c0c3d7d77 outdated

488+To help implementers understand updates to this document, we attach a version number that resembles ''semantic versioning'' (<code>MAJOR.MINOR.PATCH</code>).
489+The <code>MAJOR</code> version is incremented if changes to the BIP are introduced that are incompatible with prior versions.
490+The <code>MINOR</code> version is incremented whenever the inputs or the output of an algorithm changes in a backward-compatible way or new backward-compatible functionality is added.
491+The <code>PATCH</code> version is incremented for other changes that are noteworthy (bug fixes, test vectors, important clarifications, etc.).
492+
493+* '''1.0.0''' (2024-05-08):

josibake commented at 11:35 am on June 22, 2024:

nit: In my experience, change logs usually start with the latest version first (which is also how the BIP327 change log is structured). Aside from consistency, I also prefer the latest first because as implementors most people are interested in the most recent changes and not necessarily interest in the chronology of changes

theStack commented at 6:32 pm on June 22, 2024:

Good point, I agree! Done.

jonatack commented at 7:54 pm on June 22, 2024:

Change log LGTM. Verified the dates are when the change was merged.

In another PR, it may (or may not) be worthwhile to update BIP 2 with the change log format description, update the other change logs to it, and link to that BIP 2 section in each BIP rather than duplicating it.

josibake approved

josibake commented at 11:38 am on June 22, 2024: member

ACK https://github.com/bitcoin/bips/pull/1620/commits/4c0c3d7d77113507e32187dac662023e85f9c0d8

Test cases look good, left a nit regarding change log ordering, not blocking.

BIP-352: add change log (SemVer format)

The first paragraph is taken from BIP-327, with the sentence
about MAJOR version zero removed, as it's not relevant here
(we don't track the pre-merge history).

496e4295e7

theStack force-pushed on Jun 22, 2024

jonatack commented at 8:01 pm on June 22, 2024: contributor

ACK 496e4295e76579b75dbafbd8a6c6e49948cc0d8d, only change since BIP author approval in #1620#pullrequestreview-2133754731 was taking feedback on change log order.

jonatack merged this on Jun 22, 2024

jonatack closed this on Jun 22, 2024

theStack deleted the branch on Jun 22, 2024

BIP-352: handle invalid privkey / pubkey sums for sending / scanning, add changelog #1620