--- Log opened Thu Oct 16 00:00:10 2025
00:16 -!- tromp [~textual@2001:1c00:3487:1b00:d983:2af2:5deb:9bbb] has quit [Quit: My iMac has gone to sleep. ZZZzzz…]
01:59 -!- jerryf [~jerryf@user/jerryf] has quit [Remote host closed the connection]
01:59 -!- jerryf [~jerryf@user/jerryf] has joined #secp256k1
02:28 < josie> nickler: thanks for confirming the malicious transaction worst case! in the BIP we specify that each output should be removed from the list once it is "found"
02:29 < josie> the idea behind this was to mitigate the worst case scenario. we dont actually do this in the current version of the PR, but it might be worth reconsidering
02:30 < josie> ill respond more on the PR regarding requiring the outputs be sorted by k, but tldr; ruben and i discussed this early days and felt it was too much complexity for "normal" usage to guard against what his hopefully a rare occurance 
02:31 < josie> another thing to consider is in order to create this malicious tx with 23255 outputs, if we assume dust is something like 320 sats, the attacker would have to send you 7.4M sats
02:32 < josie> or in the event they are sending a non-standard zero output amounts tx (or below dust limit), this is a pretty easy attack to detect and the scanner could just skip it 
02:50 -!- tromp [~textual@2001:1c00:3487:1b00:d983:2af2:5deb:9bbb] has joined #secp256k1
04:36 -!- tromp [~textual@2001:1c00:3487:1b00:d983:2af2:5deb:9bbb] has quit [Quit: My iMac has gone to sleep. ZZZzzz…]
05:20 -!- jerryf [~jerryf@user/jerryf] has quit [Remote host closed the connection]
05:21 -!- jerryf [~jerryf@user/jerryf] has joined #secp256k1
05:32 -!- jerryf [~jerryf@user/jerryf] has quit [Remote host closed the connection]
05:32 -!- jerryf [~jerryf@user/jerryf] has joined #secp256k1
05:53 -!- jerryf [~jerryf@user/jerryf] has quit [Remote host closed the connection]
05:53 -!- jerryf [~jerryf@user/jerryf] has joined #secp256k1
06:01 -!- tromp [~textual@2001:1c00:3487:1b00:d983:2af2:5deb:9bbb] has joined #secp256k1
06:21 -!- jonatack [~jonatack@user/jonatack] has joined #secp256k1
06:37 -!- jerryf [~jerryf@user/jerryf] has quit [Remote host closed the connection]
06:37 -!- jerryf [~jerryf@user/jerryf] has joined #secp256k1
06:46 < nickler> josie: Would removing the output really help? I think in the worst case you still need to scan through all of the rest. For example, the k = 0 output could be the last output, the k = 1 the second to last output, and so on. Then the inner loop still runs n_tx_outputs + (n_tx_outputs - 1) + ... + 1 times.
07:25 < bitcoin-git> [secp256k1] hebasto opened pull request #1760: cmake: Split test cases to improve parallelism (master...251016-ctest-opt) https://github.com/bitcoin-core/secp256k1/pull/1760
07:35 < josie> nickler: it doesnt really help (not in the way sorting by k would), but if its easy enough for an implementation to remove each found output before doing the next round, it makes it slightly less worse
07:53 < nickler> I don't see how removing the found output would make it less worse (even slightly).
07:55 < josie> back of the napkin, i think on average removing each found output reduces the pathelogical case by half on average? 
07:55 < josie> but i might be missing something 
07:56 < josie> whoops, s/on average removing each/removing each/
07:58 < nickler> If the attacker creates a transaction such that the scanner always removes the last element of the list you end up with the equation I mentioned above, which is in O(n^2).
07:58 < nickler> You could randomize the list (and remove the found output), which I think would reduce the constants, but not change the asymptotics.
08:01 < josie> nickler: great point, in my head i was always thinking of this where each output is for the scanner, but it didnt quite click that the ordering of k also makes this worse
08:01 < josie> randomising can help, but the randomising operation is also not free
08:12 -!- tromp [~textual@2001:1c00:3487:1b00:d983:2af2:5deb:9bbb] has quit [Quit: My iMac has gone to sleep. ZZZzzz…]
08:34 -!- tromp [~textual@2001:1c00:3487:1b00:d983:2af2:5deb:9bbb] has joined #secp256k1
10:26 < bitcoin-git> [secp256k1] hebasto closed pull request #1755: ci: Remove "x86_64: macOS Ventura, Valgrind" job (master...251003-ci-macos13) https://github.com/bitcoin-core/secp256k1/pull/1755
10:43 -!- tromp [~textual@2001:1c00:3487:1b00:d983:2af2:5deb:9bbb] has quit [Quit: My iMac has gone to sleep. ZZZzzz…]
11:42 -!- BlueMatt [~BlueMatt@ircb.bluematt.me] has quit [Quit: Quit]
11:42 -!- BlueMatt [~BlueMatt@ircb.bluematt.me] has joined #secp256k1
12:27 -!- jerryf [~jerryf@user/jerryf] has quit [Remote host closed the connection]
12:28 -!- jerryf [~jerryf@user/jerryf] has joined #secp256k1
14:50 -!- tromp [~textual@2001:1c00:3487:1b00:d983:2af2:5deb:9bbb] has joined #secp256k1
16:03 -!- tromp [~textual@2001:1c00:3487:1b00:d983:2af2:5deb:9bbb] has quit [Quit: My iMac has gone to sleep. ZZZzzz…]