tests: silentpayments: cover labeled output beyond the first label batch #1943

secp256k1_silentpayments_check_label_batch maps a candidate index within a batch back to a tx output index via j_start + i / 2. In the first batch j_start == 0, so an incorrect mapping is indistinguishable from the correct one. The only existing test with labeled outputs past the first batch is the K_max test vector, which only checks the number of found outputs. For example, this mutant survives the current tests:

diff --git a/src/modules/silentpayments/main_impl.h b/src/modules/silentpayments/main_impl.h
index 0ea3ee1..533be40 100644
--- a/src/modules/silentpayments/main_impl.h
+++ b/src/modules/silentpayments/main_impl.h
@@ -589,7 +589,7 @@ static int secp256k1_silentpayments_check_label_batch(
         *label_tweak = label_lookup(label33, label_context);
         if (*label_tweak != NULL) {
             *label_ge = label_candidates_ge[i];
-            return (int)(j_start + i / 2);
+            return (int)((j_start + i) / 2);
         }
     }
     return -1;

This PR adds test_recipient_scan_label_batch_index. It puts LABEL_BATCH_SIZE non-matching outputs before a labeled output, so the match lands in the second batch.

Nice finding, Concept ACK

None of the existing tests put a labeled output past the first batch

There is one BIP-352 test vector where 2323 tx outputs are labeled matches and findings in higher batches (j_start > 0) occur, so an incorrect tx output index calculation with the mutant patch in the PR description is at least already exercised. But it unfortunately remains undetected, as the checking is not very thorough for this one, only the number of found outputs is verified and nothing else. Maybe we could do something like "if there are N matches, ensure that those are all with different output x-only pubkeys". This would have caught this issue I think, as with the mutant patch several matches map to the same tx outputs. Ideas welcome (could be in a different PR though).

I opened PR #1950 and confirmed that the suggested new check on test vectors of silent payments does capture the mutant described here.

Is this PR still necessary? This one checks for exacts outputs and is more explicit about testing the even and the odd candidate slots because it scans with p and -p.

Is this PR still necessary? This one checks for exacts outputs and is more explicit about testing the even and the odd candidate slots because it scans with p and -p.

I think it makes sense to keep this PR as well, explicitly verifying outputs and exercising both y-parities are useful additions. I didn't try, but I suppose it would be possible to come up with a mutant patch that's caught by this PR, but not by #1950.

Tested on 0f03931.

I think this is still very much needed on top of #1950. The check added in #1950 only asserts pairwise uniqueness across found outputs in the 2323 vector (full_check = 0), which doesn't check against expected ground-truth pubkeys or labels. If a transaction has filler outputs and only a single match in higher batches (exactly what this test sets up with LABEL_BATCH_SIZE fillers), the uniqueness check is trivially satisfied and wouldn't catch an incorrect index mapping to a filler.

On top of that, explicitly exercising both even and odd candidate slots (p and -p) past batch 0 is great to have.

One minor suggestion: in test_recipient_scan_label_precedes_direct_match, f[0].label is also verified against the cache via secp256k1_silentpayments_recipient_label_serialize. Adding that check here would also ensure label_ge itself is verified for both parities beyond batch 0.

One minor suggestion: in test_recipient_scan_label_precedes_direct_match, f[0].label is also verified against the cache via secp256k1_silentpayments_recipient_label_serialize. Adding that check here would also ensure label_ge itself is verified for both parities beyond batch 0.

label_ge is read from the current batch's candidate array at the in-batch position i, so it's the same code path for every batch and parities. Only the returned index depends on j_start:

*label_ge = label_candidates_ge[i];
return (int)(j_start + i / 2);

I'll keep this test focused on the output index mapping.

The labeled output is the only one in the second batch, so i / 2 is always 0 there and a wrong offset within a later batch goes unnoticed. This mutant survives on master and with this PR:

-            return (int)(j_start + i / 2);
+            return (int)(j_start + (j_start > 0 ? n_batch - 1 - i / 2 : i / 2));

With 2 * LABEL_BATCH_SIZE outputs and the labeled one at LABEL_BATCH_SIZE + 3, the test catches both this mutant and the one in the description.

Thanks for the review! Force-pushed 0c3c70d5f70d09bddf3e9ed5247d382ebe8d577e updating the test so it covers every position mapping across multiple label batches, which kills the mutant suggested in #1943 (comment).

Note that a test can't feasibly kill every possible mutant: one can always be crafted to misbehave only on input sizes beyond those tested, and exhaustively covering all output counts and positions is impractical. This test targets the realistic mapping errors instead.

ACK 0c3c70d5f70d09bddf3e9ed5247d382ebe8d577e

I checked that the new test kills the mutant I reported and the one in the description.

The range-diff from 0f03931 changes only test_recipient_scan_label_batch_index. It now puts the labeled output at every position among 2 * LABEL_BATCH_SIZE + 1 outputs. It scans with p and -p at each position.

Results on this head:

• unmodified: the new test and the silentpayments module pass.
• my mutant (j_start + (j_start > 0 ? n_batch - 1 - i / 2 : i / 2)): the new test fails at tests_impl.h:744. With 0f03931's test, the same mutant still passes.
• the description's mutant ((j_start + i) / 2): the new test fails at the same check.

I agree that no single test can kill every mutant. Covering every position across three batches catches both mutants above.

Tested ACK 0c3c70d on Windows. Confirmed the test catches the mutant.

ACK 0c3c70d5f70d09bddf3e9ed5247d382ebe8d577e

Rough follow-up idea: we could deduplicate some of the SP test code regarding the output_tweak constant (which now appears already three times) and the corresponding label cache and _prevouts_summary setup.