--- Log opened Mon Aug 19 00:00:50 2019 02:43 -!- reallll is now known as belcher 10:50 < elichai2> Hi, I'm working on doing a batch ecdsa recover. currently just batching the `ge->gej` operation using `secp256k1_ge_set_all_gej_var`, can you think of any way to do this *without* requiring scratch space? I think I' 10:51 < elichai2> *I think it's needed because I can't know how many `secp256k1_gej` I'll need 10:51 < elichai2> (and we don't have any `secp256k1_gej` in the public API for the user to supply something like that) 10:51 < elichai2> * `gej->ge` 10:55 < andytoshi> ISTR there's a way if you're willing to trash your input points 10:56 < andytoshi> which usually you are, but we have a `const` on it, and there's no other functions that do this 10:57 < andytoshi> actually i think i did this in my context-cleanup PR? like, i thought i removed `secp256k1_ge_set_all_gej_var` and inlined it so that i'd be able to do this? maybe not.. 11:01 < sipa> you still need scratch space 11:02 < sipa> your inputs are N inputs and N sigs, your output is N pubkeys 11:02 < sipa> i don't think you can repurpose any of the input space to store N gejs 11:02 < elichai2> hmm maybe I could somehow use the output array of `secp256k1_pubkey` as a scratch space? 11:03 < sipa> pubkey objects are 64 bytes 11:03 < sipa> gejs are 120 bytes 11:03 < sipa> (at least) 11:04 < sipa> oh plus the infinity flag 11:04 < elichai2> how big can `z` be in reallity? it should be pretty low. is it crazy to use some X bytes on the stack to save the z data? 11:04 < elichai2> but it will be too hacky 11:04 < sipa> Z will be a uniformly random field element in practice 11:05 < sipa> really, just use scratch space 11:05 < sipa> it's the right tool for the job 11:05 < elichai2> oh really? ha. ok, than there's no good solution except scratch space 11:08 < sipa> z3 = x2*z2 - x1*z2^3 11:08 < sipa> in jacobian addition of (x1,y1) with (x2,y2,z2) 11:09 < elichai2> sipa: even with scratch space I need to write a new `secp256k1_ge_set_all_gej_var` that writes into a secp256k1_pubkey not a ge, otherwise i'll need ~twice the scratch space 11:09 < sipa> please don't do that 11:09 < sipa> if you're going to need scratch space anyway, just use it 11:10 < sipa> secp256k1_pubkey is only for communication with the outside world, and shouldn't be used anywhere internally 11:10 < sipa> for the use case of making CMS cheaper, you won't ever have more than 20 keys 11:11 < sipa> memory usage is not a problem 11:11 < elichai2> I can have it as a helper function that wraps around the internals of `secp256k1_ge_set_all_gej_var`. But I get your point. I'll just use the scratch space 11:29 < andytoshi> sipa: the point is that your input and output possibly come from the user so you don't have to worry about how those get allocated 11:29 < andytoshi> so if you're allowed to trash the input you can store some temp values there 11:29 < andytoshi> not the whole gej, just some z multiples 11:29 < andytoshi> we do essentially this during context creation 11:30 < andytoshi> (it may nonetheless be inappropriate for whatever elichai2 is doing, but it is possible) 11:30 < andytoshi> oh, no, maybe i'm wrong https://github.com/bitcoin-core/secp256k1/blob/master/src/ecmult_gen_impl.h#L90 11:31 < andytoshi> oh lol https://github.com/bitcoin-core/secp256k1/blob/master/src/group_impl.h#L136 I was able to repurpose the *output* to avoid the use of temp space 11:31 < elichai2> andytoshi: in theory if I could trash inputs and use outputs for temp data It might be enough to use no scratch space at all but that's violating the current API (all inputs are const) and it's really weird and overcomplicated 11:31 < andytoshi> elichai2: now i'm confused as to what you're trying to do 11:31 < andytoshi> the existing `secp256k1_ge_set_all_gej_var` does not allocate any memory 11:32 < elichai2> andytoshi: have a function that accepts a list of secp256k1_ecdsa_recoverable_signature and a list of messages as inputs. and a list of secp256k1_pubkey as outputs 11:32 < elichai2> so I need scratch to allocate the inputs for `secp256k1_ge_set_all_gej_var` (ges and gejs) 11:33 < andytoshi> oh i see 11:33 < andytoshi> yeah the scratch space is what you want 11:34 < andytoshi> (if i was expecting to have millions of keys or something i might do something ugly and layer-violating to avoid this, but i can't imagine you will) 11:35 < elichai2> is doing `sizeof(*points)` safe for an unintialized `secp256k1_ge *points`? it seems like it shouldn't be safe but maybe sizeof is a special case 11:35 < andytoshi> yes, the sizeof operator does not evaluate its argument 11:35 < andytoshi> so that is not actually a pointer dereference 11:35 < elichai2> ha 11:36 < andytoshi> so it's safe (but bear in mind it will *not* give you an array length!) 11:36 < sipa> you can also write sizeof(secp256k1_ge), but both are legal 11:36 < andytoshi> sizeof(value) is more robust to changes in types, but it's also less idiomatic 11:36 < andytoshi> you also don't need the parens, but that's really unidiomatic :P 11:36 < sipa> https://en.cppreference.com/w/c/language/sizeof 11:37 < sipa> andytoshi: wow, i didn't know that 11:37 < sipa> and it's even on the page i just linked to 11:38 < andytoshi> :P i think i read about it on usenet, but I got told off when i tried to use it in a real project 11:38 < sipa> oh, you do need the parentheses if you're passing a type name 11:38 < sipa> but don't need them when it's a value 11:38 < elichai2> I don't like that it looks like a dereference lol, but it is more robust 11:39 < sipa> elichai2: in any case, the memory needed for an array of N elements of type T is exactly N*sizeof(T) 11:39 < elichai2> yeah, that's what I did 11:39 < elichai2> thanks 12:20 -!- reallll [~belcher@unaffiliated/belcher] has joined #secp256k1 12:24 -!- belcher [~belcher@unaffiliated/belcher] has quit [Ping timeout: 272 seconds] 13:36 < elichai2> nickler: I see that in your batching tests you do a lot of stuff just to pass the compiler anger about trying to pass non const stuff. is there a way to bypass it, It's really frustrating :/ (doing similiar stuff in my code) 13:45 < sipa> elichai2: if you have a non-cons5 object of type X, and a const pointer to it, you can aoways access it using (X*)x 13:48 < sipa> (i don't know the actual code you're referring to) 13:50 < elichai2> sipa: refering to this: https://github.com/bitcoin-core/secp256k1/pull/558/files#diff-4ad2dd2b8b6840915f8f0e99d18e1dc8R657 13:50 < elichai2> constructing a `const unsigned char *const *msg32` is not fun. 13:50 < sipa> cdecl ia your friend 15:35 < elichai2> hmmm right now it seems to only be 2-3 ums increase per signature 15:36 < elichai2> (by increase I actually mean decrese lol, it's 2-3 ums faster) 15:38 < andytoshi> 2-3 µs? 15:39 < andytoshi> by avoiding some memcpys? 15:39 < elichai2> yeah heh altough for the max it can sometimes can be big difference, not sure why `ecdsa_recover: min 54.2us / avg 56.6us / max 68.7us ecdsa_recover_batch: 10: min 50.8us / avg 51.9us / max 53.0us` 15:39 < elichai2> andytoshi: no, by using `secp256k1_ge_set_all_gej_var` 15:40 < sipa> that's 50.8us per key? 15:40 < elichai2> to verify a bunch together 15:40 < elichai2> sipa: yes. still trying to play with it to make sure i'm not missing anything obvious but yeah 15:41 < sipa> that sounds far too slow 15:41 < andytoshi> it should be roughly equal to a sig verification, no 15:41 < andytoshi> ? 15:41 < sipa> oh, of course 15:41 < andytoshi> also a 5µs drop is around what i'd expect for losing a field inversion 15:41 < elichai2> well it also includes parsing and serializing 15:41 < sipa> i'm wrong; that sounds perfectly reasonable 15:42 < sipa> it's still two EC multiplications per key 15:42 < sipa> it should btw output all recoveries, not just one (up to 4 per sig) 15:42 < sipa> which will add an extra slowdown 15:42 < elichai2> yeah, the only low hanging thing is having a condition for if the messages are the same (which I assume is the usual case) then I can optimize a bit 15:43 < sipa> but what this means is that if you have a 1-of-20 multisig, you only do one recovery, not 20 15:43 < sipa> but what this means is that if you have a 1-of-20 multisig, you only do one recovery, not 20 sig verifications 15:45 < elichai2> sipa: hmm we need all four because we don't have the recid? 15:45 < sipa> indeed 15:45 < sipa> we have the actual public keys though 15:46 < elichai2> we could output only two and check the oddness/evenness on the original key 15:46 < sipa> that's not correct 15:47 < sipa> the two recoveries are (m/r)G + (s/r)R and (m/r)G - (s/r)R 15:47 < sipa> they're not each others negations 15:48 < elichai2> right we negate before we add sorry. hmmm 15:48 < sipa> but this is not much of a slowdown i think; you compute the G component and the R component separately (instead of using a multi-mult), and then return their sum and difference 15:48 < elichai2> could this somehow introduce more mellability? 15:48 < sipa> no, because the result has to exactly match one of the provided public keys 15:49 < sipa> the only requirement is that we find all possible keys 15:49 < sipa> and "more malleability"... if the new verification algorithm is in even the slightest way different from the existing one, it's a consensus bug; malleability would be the least of our issues 15:50 < elichai2> yeah of course, but then every signature is valid with 4 different public keys 15:50 < elichai2> or 2 for that matter 15:50 < sipa> it already is. 15:51 < sipa> that's the reason why recovery needs to return all keys 15:51 < elichai2> isn't regular ecdsa valid only for 2 keys? 15:52 < sipa> 2 or 4 15:52 < sipa> (4 only happens in pathologically constructed cases, it's astronomically unlikely otherwise) 15:52 < sipa> only when there are two X coordinates that equal r modulo n 15:54 < sipa> which implies r must be between 0 and p-n (~ 1.27*2^128) 16:00 < elichai2> hmm 16:00 < sipa> that's because for idiotic reasons r in ECDSA is a number modulo the group order rather than a field element 16:01 < sipa> and as the field size is slightly larger than the group order, there can be 2 X coordinates with the same r 16:02 < elichai2> btw, I can add another condition to the api that if the messages list is length 1 then I reuse eG. curious if that can give a bigger increase 16:03 < sipa> that sounds like an optimization for later 16:03 < sipa> it doesn't improve the worst case performance 16:03 < elichai2> yeah 16:07 -!- roconnor [~roconnor@host-184-164-11-222.dyn.295.ca] has joined #secp256k1 16:07 < elichai2> we'll probably lose a precent by not using `secp256k1_ecmult`, but i'll change it to output the whole 4 or just the two quads of (s/r)G? 16:08 < roconnor> elichai2: are you implementing https://github.com/bitcoin/bitcoin/issues/15621 ? 16:08 < elichai2> roconnor: yes 16:09 < sipa> "two quads" ? 16:09 < roconnor> horray! 16:09 < elichai2> sipa: I meant the odd+even 16:09 < elichai2> roconnor: :) 16:09 < sipa> elichai2: i don't know what you mean, but imho it should return lists of 2 or 4 secp256k1_pubkey objects 16:10 < elichai2> roconnor: a bit disappointed in the performance increase so far in my tests, (for raw verifying without taking into account the k checks instead of n (in k-of-n)) 16:11 < elichai2> sipa: ok. so I need to ask for 4X list and i'll return a size. I think i'll commit now and continue tomorrow 16:11 < sipa> elichai2: cool 16:12 < sipa> elichai2: actually 16:12 < elichai2> yeah? 16:12 < sipa> nvm 16:13 < sipa> elichai2: in any case, #15621 predicts that for n-of-n it won't be a performance win 16:16 < roconnor> Indeed I expected key recovery for n-of-n to be slightly slower, and I'd consider only using key recovery for k < n. Of course, these things would need to be benchmarked. 16:22 < elichai2> roconnor: right now it's ~2-3% faster but I gave a recid, i'll try changing it to input all 4 keys and see the performance 16:23 < sipa> if it's faster even for n-of-n multisig, we have the problem that we should replace the normal ECDSA verifier with your code :p 17:20 < elichai2> Is `secp256k1_ecmult(ctx, &pt, &pt, &one, &some);` faster then `secp256k1_ecmult_gen(ctx, &pt, &some)`? (these seem to be the most used ways to compute a*G) 17:23 < sipa> the latter is a lot slower 17:23 < sipa> it's constant time 19:34 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1 19:49 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection] 19:52 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1 20:07 -!- elichai2 [uid212594@gateway/web/irccloud.com/x-uedwuyemjifqeace] has quit [Quit: Connection closed for inactivity] 22:23 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection] 22:26 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1 22:32 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection] 22:40 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1 22:45 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Ping timeout: 264 seconds] --- Log closed Tue Aug 20 00:00:45 2019