--- Log opened Thu Dec 23 00:00:09 2021
06:28 < real_or_random> sipa: could we (in theory) have secp256k1_gej_add_ge_nonuniform with a non-uniform addition law and get away with it for ecmult_gen?  
06:36 < real_or_random> maybe because our ecmult_gen algorithm simply never adds a point to itself (as in the the musig-dn circuit)? I'm not sure. 
06:43 < sipa> You'd need a special case for handling infinity in ecmult_gen, but other than that, I guess it could work?
06:45 < real_or_random> you mean infinity where? as the result or as an intermediate result?
06:49 < sipa> As the final result.
06:50 < sipa> I think the current ecmult_gen code will never reach an intermediary infinity unless the final result is infinity.
06:50 < sipa> And it won't reach doubling unless you can solve the ECDLP.
06:52 < real_or_random> hm yeah I mean the scalar being zero is not hard to handle as a special case
06:53 < sipa> Making it guaranteed to not hit doubling either would be nice.
06:53 < sipa> Especially if it could be combined with multicomb.
06:54 < real_or_random> oh there's multicomb, I always forget about it
06:54 < sipa> I vaguely remember multicomb exploiting some positive/negative symmetry, so perhaps it actually always does that.
06:54 < sipa> But I'd need to swap in the details.
06:57 < real_or_random> our uniform secp256k1_gej_add_ge  has 7 mul and 5 sqr, the best uniform in EFD needs one fewer sqr
06:57 < real_or_random> *best non-uniform
06:57 < sipa> Plus a ton of cmovs etc.
06:58 < real_or_random> right yeah, whether it's really better depends on the "fast" operations too
06:58 < real_or_random> I'll leave a note in the multicomb PR or in a separate issue. probably nothing we consider before multicomb
06:59 < sipa> Which reminds me. It requires rebasing. And documentation.
06:59 < real_or_random> :D
07:00 < sipa> I remember when I first made the change to have signing be actually constant-time, it took 90 us.
07:01 < real_or_random> When I think about it, I feel I should do more high-level stuff (protocols, QA, ...). But then I get nerdsniped by performance improvements
07:01 < sipa> Now it's 23 us on my desktop. I wonder how much of that is CPUs having become faster the past 7 years.
07:01 < real_or_random> hehe
07:02 < real_or_random> but to be honest, you and peter and all the others are anyway more skilled when it comes to performance, so I should really work on the protocols :P
07:08 < real_or_random> by the way, the much lower hanging fruit is sha256 overrides...
07:08 < sipa> Yes.
07:08 < sipa> I also wonder how much of our time in tests is actually SHA256?
07:08 < real_or_random> and offering a better ecdsa nonce function 
07:09 < sipa> The test randomness uses the rfc6979 RNG function...
07:09 < real_or_random> yeah, right, we could replace that one too
07:10 < real_or_random> I'm just not inclined to spend a lot of time optimizing the tests... ^^
07:13 < real_or_random> I guess we should really prioritize the overrides now. in particular now that we have schnorr sigs
07:13 < real_or_random> where SHA256 is computed in libsecp, not in core...
07:21 < sipa> I'm not sure it will actually make a tangible difference.
07:25 < real_or_random> idk, maybe over an entire initial sync? :P yeah, but anyway, we should do it ^^
07:25 < sipa> I believe that non-accelerated SHA256 is around 15 cycles/byte on modern x86_64, or 960 cycles per compression. For signing we do 3 hashes, or 5 compressions, so around 1.3 microseconds.
07:25 < sipa> That's more than I had expected.
07:26 < real_or_random> I pinged elichai2 in https://github.com/bitcoin-core/secp256k1/issues/702
07:26 < sipa> For verification it's only 2 compressions I think.
08:32 < sipa> Switching to a faster RNG for tests is a small but measurable speedup.
08:32 < sipa> I had hoped for more.
09:38 < real_or_random> how much is it?
09:38 < sipa> from ~34.0s to ~32.9s
09:38 < sipa> with iter=64
09:39 < real_or_random> hm, yeah, is it then worth doing it?
09:40 < sipa> that would be a reasonable question if i hadn't already done it :)
09:40 < real_or_random> could also replace it with plain SHA256 then 
09:40 < real_or_random> hm ok yeah ^^
09:40 < sipa> Of course, it's not unreasonable to say it's not worth reviewer time.
09:42 < sipa> I like triple negations and I cannot fail to not tell lies.
09:43 < real_or_random> how will this affect the randomness tests? 
09:43 < sipa> If it's a good RNG (which the paper at least claims...), so it shouldn't affect anything.
09:44 < sipa> Well, non-cryptographic PRNG.
09:44 < real_or_random> ok what was the purpose of the randomness tests? 
09:44 < real_or_random> just check if we're not screwing up horribly?
09:44 < sipa> Yeah, I guess.
09:45 < real_or_random> well ok yeah, but then we move from rfc6769 to testing an internal function. which may be ok 
09:45 < sipa> "Finally, our years-long maintained randomness tests actually have a purpose!"
09:46 < real_or_random> by the way, an idea I recently had is to hash all the "computation" results in the tests and output the result. and then see if it matches across platforms in CI, maybe   adding one run per target
09:46 < real_or_random> seed = commit hash ^^ or similar
09:46 < sipa> we already output one final 16-byte value extracted from the internal RNG.
09:46 < sipa> So if that matches, all inputs should be the same.
09:47 < sipa> We could feed some outputs back into the RNG, I guess?
09:47 < real_or_random> yeah, this is only about the inputs
09:47 < sipa> Right, though some outputs may affect control flow of the test routines.
09:47 < real_or_random> we could feed back outputs, which would be much more interesting
09:48 < real_or_random> well all "outputs" should be deterministic. otherwise I don't consider it an output
09:48 < real_or_random> so this may involve serializing fe elements to make sure they're the same across 32bit/64bit etc
09:49 < real_or_random> but anyway, going through tests.c is a non-trivial amount of work 
09:49 < sipa> yeah
10:39 < real_or_random> we need to stop opening PRs, we can't keep up ^^  *just opened another one*
11:55 < sipa> Reading up on multicomb again, I could believe there is a way to structure it so that it never doubles/cancels.
11:55 < sipa> Maybe I should simulate it exhaustively for a small group.
11:55 < sipa> I probably want demo python code anyway for it.
13:35 -!- lukedashjr [~luke-jr@user/luke-jr] has joined #secp256k1
13:36 -!- luke-jr [~luke-jr@user/luke-jr] has quit [Ping timeout: 268 seconds]
13:37 -!- lukedashjr is now known as luke-jr
13:39 -!- lukedashjr [~luke-jr@user/luke-jr] has joined #secp256k1
13:41 -!- luke-jr [~luke-jr@user/luke-jr] has quit [Ping timeout: 240 seconds]
13:41 -!- lukedashjr is now known as luke-jr
14:02 -!- luke-jr [~luke-jr@user/luke-jr] has quit [Ping timeout: 240 seconds]
14:45 -!- luke-jr [~luke-jr@user/luke-jr] has joined #secp256k1
15:14 -!- luke-jr [~luke-jr@user/luke-jr] has quit [Ping timeout: 260 seconds]
16:14 -!- luke-jr [~luke-jr@user/luke-jr] has joined #secp256k1
16:29 -!- lukedashjr [~luke-jr@user/luke-jr] has joined #secp256k1
16:29 -!- luke-jr [~luke-jr@user/luke-jr] has quit [Ping timeout: 256 seconds]
16:30 -!- lukedashjr is now known as luke-jr
--- Log closed Fri Dec 24 00:00:10 2021