--- Log opened Mon Mar 29 00:00:10 2021
00:56 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has quit [Quit: ZNC - http://znc.sourceforge.net]
00:57 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1
06:00 -!- deusexbeer [~deusexbee@080-250-076-051-dynamic-pool-adsl.wbt.ru] has quit [Quit: Konversation terminated!]
06:00 -!- deusexbeer [~deusexbee@080-250-076-051-dynamic-pool-adsl.wbt.ru] has joined #secp256k1
06:51 < roconnor> I'm starting to think the ecmult_multi_var is slightly too narrow of an interface to be used for batch verification.
06:52 < roconnor> Currently it does a "Multi-multiply: R = inp_g_sc * G + sum_i ni * Ai."
06:52 < roconnor> But what I think we want is one that does "Multi-multiply: R = (sum_i gi) * G + sum_i ni * Ai."
06:53 < roconnor> So that we can stream a series of equations to be batch verfied without needing to add up all the G coefficents in advance.
06:54 < roconnor> Maybe I should write this comment in PR#760
07:09 < elichai2> roconnor: Checking if I understand the current impl and what you're proposing
07:09 < elichai2> currently it's: `Scalar *G + Sum(List of tuples of:(Scalar*Point))`
07:10 < elichai2> and you're proposing: `Sum(List of scalars)*G + Sum(List of tuples of: (Scalar*Point))`
07:11 < elichai2> (can you please mark your github comments code as C by adding C after the ```? (e.g.: ```C //blabla ```), it makes it easier to read :) )
07:13 < roconnor> hey look at that.  That's pretty cool.
07:15 < roconnor> elichai2: my proposed enhanced ecmult_multi_var would have each gi for the List of scalars returned by the callback.
07:16 < roconnor> The wierd split between `secp256k1_batch_verify_gi_callback` and `secp256k1_batch_verify_callback` in my API proposal is only there to satify the current ecmult_multi_var's API shape.
07:17 < nickler> roconnor: why would you need to add up all the G coefficients in advance? Isn't it enough to store the sum of what you've seen so far on the scratch space?
07:17 < roconnor> nickler: that isn't how ecmult_multi_var works.
07:19 < roconnor> you currently cannot call ecmult_multi_var until you've computed a single G coefficent.
07:20 < roconnor> And thus, as it stands, batch verification much add up all the G coefficents prior to calling ecmult_multi_var.
07:24 < nickler> But that doesn't seem to prevent streaming. If you're storing ni, Ai, (sum_i gi), you can call ecmult_mult_var at any time.
07:25 < roconnor> my proposed API doesn't store ni Ai, etc.
07:27 < roconnor> That said, my API proposal is somewhat off-the-cuff, and I may have made some errors.
07:30 < roconnor> But my plan is for secp256k1_ecmult_multi_callback to in turn call secp256k1_batch_verify_callback and tweek those coefficents according to the chacha data...
07:30 < roconnor> ah oops the chacha seed must be derived from all the input data, which means two passes through all the data at the very least.
07:35 < nickler> I still don't understand your original point about gi, but ecmult_multi must be refactored anyway to separate out the scratch space allocations. I should probably close the schnorr PR.
07:35 < roconnor> refactored anyway?
07:36 -!- belcher_ is now known as belcher
07:37 < nickler> regardless of whether there's an issue with ecmult_multi "needing to add up all the G coefficients in advance"
07:38 < roconnor> Right, but what is the stratch space problem?  I'm not aware of it.
07:40 < nickler> Ah, my understanding is that we want to copy group elements and scalars to the scratch space when calling secp256k1_batch_add_* already, not when we do batch verification and call ecmult_multi in the end.
07:45 < roconnor> but ecmult_multi copies um "bunches" of points and scalars into the strach space and operates on bunches at a time.  There isn't enough room to copy *all* the points and scalar into the scratch space.
07:46 < elichai2> nickler: Isn't the scratch space in ecmult_multi_var needed for pippenger and friends?
07:47 < elichai2> Also, Do we even need the callback there? can't we precompute the scalars and pass them directly to the ecmult_mult_var? (ie the `add` function will compute the scalars, feed a sha context etc and then when we actually batch verify we pass them as a ready list)
07:48 < nickler> roconnor: right, this is why you'd do batch verify, remember the result and clear the scratch space any time the scratch space gets full in batch_add_*
07:53 < roconnor> nickler: It is definitely the case that it is stupid to allocate space to copy all the tweaks and sigs into, and allocate approximately the same amout of space for pippenger etc to again make a copy of these points;  However there are two solutions, you can either eliminate the ecmult_multi copy like you propose, or we can eleiminate the batch_verify copy, which is what I'm proposing.
08:00 < roconnor> nickler: what would your new ecmult_multi API look like?
08:00 < roconnor> the one that is scratch-allocation-free.
08:04 < nickler> Hm, there are many details to consider like deciding whether to use strauss/pippenger etc. but I'd think that ecmult_multi would not accept a callback argument and instead assume that the scratch space is already filled with the initial state
08:04 < nickler> (at least points and scalars)
08:05 < nickler> Not sure what the "batch_verify copy" is or how it would be required by the API that elichai suggested
08:06 < nickler> elichai2: the scratch space is needed for pippenger and friends, but one could assume that it already contains the points because they've been placed into the scratch space by the batch_add_* functions.
08:08 < nickler> roconnor: to be clear I'm not sure if this works well or is the best approach. I just assumed this was the idea in the github thread.
08:09 < nickler> elichai2: perhaps you can clarify how you imagine what "// add to batch" would do
08:10 < elichai2> I thought about a few options, and will probably find problems in some of them while trying to implement. the naive way will be to just store the sig/msg/key in the scratch space until hitting the threshold
08:10 < elichai2> the more interesting one IMO is to do the precomputation to get the scalars and points, and maybe even seed a sha2 context and then store those
08:15 < elichai2> but I don't yet know the details of pippenger/strauss well enough to know how it's best to optimize the scratch space, so I can't currently comment on the amount of copies/space required
08:15 < nickler> elichai2: Ah okay then it seems like we're on the same page. I just skipped the naive way because 2x memory would be quite a downside if we compare it to a simple batch_verify_schnorr_and_tweaks function.
08:16 < elichai2> yeah
08:31 < roconnor> elichai2: does your API proposal involve calling (the current) ecmult_mult_var?
08:33 < elichai2> minor changes(like there's not really a point in the n_batches loop there) but yeah
08:35 < elichai2> maybe even the callback won't be necessary, not sure
08:35 < elichai2> but if your proposal can give better cpu/memory perf then sure why not, I don't really understand it though
08:38 < roconnor> I'm confused by "maybe even the callback won't be necessary,". The current ecmult_multi_var has a callback so if your proposal involves using it then you must provide a callback.
08:41 < roconnor> Maybe your proposal would call secp256k1_ecmult_pippenger_batch or secp256k1_ecmult_strauss_wnaf directly?
08:42 < roconnor> that would make more sense than I what I was thinking it was going to do.
08:43 < elichai2> those also currently use the callback. but yes. basically do something similar to what `ecmult_multi_var` but without using it directly
08:44 < elichai2> (sorry that it's not fully thought out, I was mostly concentrating on the external API)
08:45 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has quit [Quit: ZNC - http://znc.sourceforge.net]
08:46 < roconnor> Right, I mean to say "would call  secp256k1_ecmult_pippenger_wnaf ..."
08:46 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1
08:47 < elichai2> now you're getting to the specific parts of the code I know the least :). so I don't currently know exactly how and what
08:48 < roconnor> Okay, let me reconsider your proposed API in this light.
08:51 < roconnor> Somwhat relevent, pr #900 proposes to eliminate the points and scalars allocation from secp256k1_ecmult_strauss_batch, which moves in the opposite direction as elichai2 is discussing.
09:29 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has quit [Quit: ZNC - http://znc.sourceforge.net]
09:30 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1
09:31 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has quit [Remote host closed the connection]
09:48 -!- dongcarl [~dongcarl@unaffiliated/dongcarl] has joined #secp256k1
11:51 -!- jonatack [~jon@88.124.242.136] has quit [Ping timeout: 268 seconds]
11:51 -!- jonatack [jon@gateway/vpn/airvpn/jonatack] has joined #secp256k1
13:09 -!- jonatack [jon@gateway/vpn/airvpn/jonatack] has quit [Quit: jonatack]
14:20 -!- jonatack [jon@gateway/vpn/airvpn/jonatack] has joined #secp256k1
15:02 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1
15:22 -!- deusexbeer [~deusexbee@080-250-076-051-dynamic-pool-adsl.wbt.ru] has quit [Ping timeout: 246 seconds]
15:23 -!- deusexbeer [~deusexbee@080-250-076-051-dynamic-pool-adsl.wbt.ru] has joined #secp256k1
15:30 -!- sanketcell [~sanketcel@ec2-100-24-255-95.compute-1.amazonaws.com] has quit [Ping timeout: 260 seconds]
15:30 -!- sanket1729_ [~sanket172@ec2-100-24-255-95.compute-1.amazonaws.com] has quit [Ping timeout: 265 seconds]
15:36 -!- sanket1729 [~sanket172@ec2-100-24-255-95.compute-1.amazonaws.com] has joined #secp256k1
15:37 -!- sanketcell [~sanketcel@ec2-100-24-255-95.compute-1.amazonaws.com] has joined #secp256k1
15:53 -!- belcher [~belcher@unaffiliated/belcher] has quit [Ping timeout: 260 seconds]
16:01 -!- belcher [~belcher@unaffiliated/belcher] has joined #secp256k1
17:42 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has quit [Quit: ZNC - http://znc.sourceforge.net]
17:47 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1
18:15 -!- BlueMatt [~BlueMatt@unaffiliated/bluematt] has quit [Ping timeout: 245 seconds]
18:18 -!- BlueMatt [~BlueMatt@unaffiliated/bluematt] has joined #secp256k1
18:25 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has quit [Remote host closed the connection]
18:26 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has joined #secp256k1
18:44 -!- deusexbeer [~deusexbee@080-250-076-051-dynamic-pool-adsl.wbt.ru] has quit [Ping timeout: 240 seconds]
19:43 -!- BlueMatt [~BlueMatt@unaffiliated/bluematt] has quit [Ping timeout: 250 seconds]
19:45 -!- BlueMatt [~BlueMatt@unaffiliated/bluematt] has joined #secp256k1
20:19 -!- belcher_ [~belcher@unaffiliated/belcher] has joined #secp256k1
20:23 -!- belcher [~belcher@unaffiliated/belcher] has quit [Ping timeout: 268 seconds]
23:12 -!- sanket1729 [~sanket172@ec2-100-24-255-95.compute-1.amazonaws.com] has quit [Ping timeout: 240 seconds]
23:14 -!- sanketcell [~sanketcel@ec2-100-24-255-95.compute-1.amazonaws.com] has quit [Ping timeout: 268 seconds]
23:15 -!- sanketcell [~sanketcel@ec2-100-24-255-95.compute-1.amazonaws.com] has joined #secp256k1
23:16 -!- sanket1729 [~sanket172@ec2-100-24-255-95.compute-1.amazonaws.com] has joined #secp256k1
23:33 -!- k1ltzman [~k1ltzman@195.189.99.96] has quit [Ping timeout: 240 seconds]
23:46 -!- roconnor [~roconnor@host-45-58-230-226.dyn.295.ca] has quit [Ping timeout: 246 seconds]
--- Log closed Tue Mar 30 00:00:10 2021