--- Log opened Tue Mar 30 00:00:10 2021
00:36 -!- nsh [~lol@wikipedia/nsh] has quit [Max SendQ exceeded]
00:45 -!- andytosh1 [~apoelstra@unaffiliated/andytoshi] has joined #secp256k1
00:47 -!- andytoshi [~apoelstra@unaffiliated/andytoshi] has quit [Ping timeout: 260 seconds]
00:47 -!- nsh [~lol@wikipedia/nsh] has joined #secp256k1
01:14 -!- nsh [~lol@wikipedia/nsh] has quit [Remote host closed the connection]
01:19 -!- nsh [~lol@wikipedia/nsh] has joined #secp256k1
04:12 -!- dr-orlovsky [~dr-orlovs@31.14.40.19] has quit [Quit: ZNC 1.8.0 - https://znc.in]
04:18 -!- roconnor [~roconnor@host-184-164-13-101.dyn.295.ca] has joined #secp256k1
04:22 -!- TD-Linux [~Thomas@about/essy/indecisive/TD-Linux] has quit [Ping timeout: 260 seconds]
04:22 -!- TD-Linux [~Thomas@about/essy/indecisive/TD-Linux] has joined #secp256k1
04:42 < roconnor> elichai2: Probably better for secp256k1_start_batch to take a secp256k1_batch* argument rather than do an allocation (which would need a corresponding deallocation).
04:43 < elichai2> hmm so the batch object itself could be on the stack? then I'll need to decide if it's an opaque byte array or not. it will probably just contain 2/3 pointers, an int, and maybe a sha2 context
04:46 < roconnor> I'm a little less excitted by secp256k1_start_batch_size (should return size_t?), but maybe it is okay.
04:47 < roconnor> maybe I don't understand which direction it is computing.
04:48 -!- belcher_ is now known as belcher
04:49 < elichai2> yeah I'm also not sure on that because strauss and pippenger have their own considerations on batch sizes, i'm trying to understand them now
04:50 < elichai2> but the point is to allow something like "I want to batch X operations"
04:51 < elichai2> so that if I have 20 sigs and 15 tweaks, then I can just say `35 ops` and it will batch them without a memory consideration, only an algorithmic one
04:52 < elichai2> but if I have say 500, then now it doesn't make sense to say `500 ops` because that will be a big allocation, i'll maybe say 64 or something. we should come up with *some* API that allows a naive user to juggle those considerations without understanding what's happening too much
04:54 < roconnor> I guess.  There is secp256k1_strauss_max_points which is similar, but it isn't even internally exposed.
04:56 < roconnor> but what you are saying makes sense.
04:58 < roconnor> I was a little concerned with: what if we want to do some sort of double buffering where we kick off a thread to do one batch while filling up the next batch.
04:58 < roconnor> But maybe we want the caller to handle all the threading issues.
04:59 < elichai2> (fyi any recommended reading about pippenger and strauss? I want to understand them and their batch sizes better before attempting this)
04:59 < roconnor> They can divide their signature/tweek data into #cores buckets and run those threads independently.
04:59 < elichai2> ohh threading in libsecp, that will be hard with C89 and not being unix specific
05:00 < elichai2> It's better to leave that for the caller I think. they can have a batch object per core
05:01 < roconnor> I haven't studied pippenger.
05:02 < elichai2> completely unrelated, but about: https://github.com/ElementsProject/secp256k1-zkp/pull/120/files#r602303742 I thought it's possible to do an unstable quicksort with n*log(n) worst case without any heap allocations(everything in-place)
05:04 < roconnor> I'm not immideately sure how to compute the approximate median to be used for the pivot without an allocation.
05:05 < elichai2> I think it's called `pattern defeating quicksort`
05:06 < roconnor> that sounds dubious.
05:06 < roconnor> oh on the box it says it is nlogn
05:08 < elichai2> that's that's how Rust's standard library sort works: https://doc.rust-lang.org/src/core/slice/sort.rs.html#756
05:08 < roconnor> elichai2: pft, the solution they propose is to switch to heapsort when things get bad.
05:08 < roconnor> > Traditionally the solution to this is to randomize the pivot selection of quicksort.
05:09 < roconnor> BTW, This is wrong.
05:09 < roconnor> the traditional solution is to do a linear time computation of the approximate median value and use that as the pivot.
05:09 < roconnor> it is what the original quicksort paper did!
05:11 < elichai2> ha, even wikipedia says: `This same pivot strategy can be used to construct a variant of quicksort (median of medians quicksort) with O(n log n) time`
05:12 < elichai2> and doesn't say anything about randomization
05:12 < roconnor> elichai2: also quicksort requires either an allocation to hold the pivots during recurion, or to use actual recursion and risk blowing the stack.  (I don't know, is ln(SIZE_MAX) recursive calls considered safe?).
05:13 < roconnor> I have a general rule of thumb to never write recursive functions when doing serious C programming.
05:14 < elichai2> specifically in C or generally? (I try to not do recursions, but sometimes in edge cases I do tail recursions)
05:15 < elichai2> The rust implementation uses recursion but limits it to `floor(log2(len)) + 1`, if it gets there they use heapsort
05:16 < roconnor> Well I suppose if I didn't write recursive function in Haskell, I wouldn't get anywhere. :D  But Haskell is a wierd because function calls don't actually push stack frames (instead case expressions / pattern matching does)
05:17 < roconnor> I suppose tail-recursion in lanaguages like Lisp and OCaml would be fine, though quicksort is not tail-recursive.
05:18 < roconnor> I could maybe find it acceptable to write recursive functions in C whose depth is limited to at most ln(SIZE_MAX).
05:19 < elichai2> why ln(SIZE_MAX)?
05:20 < roconnor> It's a nice value for divide an conqure algorithms.  e.g you cannot sort arrays of larger than SIZE_MAX if you cannot pass in their length as an argument. :)
05:20 < roconnor> and it produces reasonable sounding depth limits in practice like 64 or 32.
05:21 < roconnor> It's hard because every function call in C is technically undefined behaviour because it might blow the stack and there is no guarentee there is any stack space at all ever.
05:22 < elichai2> I think the actual limit for arrays is PTRDIFF_MAX not SIZE_MAX (because a lot of stuff offset pointers using signed numbers, at least in LLVM that's the limit)
05:22 < elichai2> lol that's an interesting way of looking at it
05:24 < roconnor> Anyhow, I did write a heapsort for jonas last week. I can paste it if you want to see it.
05:28 < roconnor> Wikipedia says "the variant of quicksort with in-place partitioning and tail recursion uses only O(log n) space. "
05:28 < roconnor> in-place heap sort uses O(1) extra space.
05:29 < roconnor> I guess in practice, quicksort uses O(64) extra space. :)
05:32 < elichai2> haha, yeah, in rust they're just really concentrated on no heap allocations (there's even kind of ~2 standard libraries, 1 (libcore) is 0 OS and heap calls, another is libstd which does OS calls (there's actually a third one in between called liballoc that requires a heap but not an OS))
05:38 < roconnor> In this application, radix sort is also on the table.
05:38 < elichai2> apparently the pippenger that's in libsecp is somewhat novel https://twitter.com/pwuille/status/1020770542146555904
05:39 < roconnor> I'd probably implement that before an nlogn quicksort.
05:40 < elichai2> I don't really know radix sort, doesn't the complexity there relate to the key size? (here 256 bit)
05:41 < roconnor> right, it is O(n*k).  I implemented a radix sort in my simplicity project.
05:42 < roconnor> But my implementation does an allocation.
05:42 < elichai2> oh, btw how's simplicity going?
05:42 < roconnor> However radix it needs allocation in about the same way quicksort does.
05:43 < roconnor> Which means that maybe you could get away with a 64 entry array allocated on the stack (or use recursion).
05:43 < roconnor> I was nervous about using recursion.
05:43 < roconnor> elichai2: Simplicity is coming along.  I've reimplemented half of libsecp256k1 in Simplicity, which is why I'm so familar with it now.
05:43 < elichai2> you really really hate recursion
05:44 < elichai2> why reimplemented and not just used?
05:44 < roconnor> recursion in consensus code in C.
05:44 < elichai2> OoO
05:44 < roconnor> elichai2: Part of the Simplicity project is to have formal specificaitons of the behaviour of the intrinsic operations (jets).
05:45 < elichai2> oh that's why you're now formally verifying every little PR to libsecp
05:45 < roconnor> I achive this formal specification by writing the specification in Simplicity.
05:45 < roconnor> *lol* not quite that far, but I certainly do want to formally verify the fragement of libsecp256k1.
05:46 < roconnor> so that when I implement these jets using libsecp256k1, I can formally prove that the implementation meets its formal specification.
05:46 < roconnor> I'm trying to avoid the issues in EVM where different implemenations are aruging who implemented their intrinsics correctly or not.
05:47 < elichai2> did that really happen? or you mean the security bug from 2-3 months ago?
05:47 < roconnor> I don't know. There was a couple of years ago where there was some sort of fork event due to arguments over the specificaiton of some new operation they added.
05:48 -!- dr-orlovsky [~dr-orlovs@31.14.40.19] has joined #secp256k1
05:51 < roconnor> I think it maybe was this one: https://www.coindesk.com/ethereums-next-blockchain-upgrade-faces-delay-after-testing-failure
05:51 < roconnor> something about not agreeing on the gas requirements for SSTORE.
05:52 < roconnor> maybe the fork was only on testnet.
05:53 < roconnor> Anyhow, if Simplicity has EC operations, and uses jacobian coordinates for speed, then the precise coordinates returned by operations ends up being consensus critical.
05:54 < roconnor> Something that isn't even true of libsecp256k1 itself.
06:08 < elichai2> roconnor: so you use jacoobian inside but if you try to observe it will convert to affine?
06:09 < roconnor> nope. Simplicity doesn't offer any information hiding.  You get the jacobian coordinates.
06:09 < elichai2> oh wow, so you can't use a blinded context?
06:11 < roconnor> Simplicty only operates on public data, so a blinded context isn't useful in the first place.
06:12 < roconnor> Simplicity never operates on secret keys or any secret data of any kind.
06:12 < roconnor> which is why I only need half of libsecp256k1.
07:19 -!- kiltzman [~k1ltzman@195.189.99.96] has joined #secp256k1
07:48 < elichai2> experimental is checked via `enable_experimental`: https://github.com/bitcoin-core/secp256k1/blob/master/configure.ac#L455. but set using `use_experimental`: https://github.com/bitcoin-core/secp256k1/blob/master/configure.ac#L120 how does this work?
08:32 < elichai2> roconnor: what's `inp_g_sc` short for?
08:43 < elichai2> also, about #900, if it's faster/same speed, then I think it's still fine even with my design, it just means my design saves less space (on the other hand it means I can retrofit my design into the current callback design)
08:44 < roconnor> inp_g_sc is a parameter name in ecmult_multi_var.
08:44 < elichai2> yeah, I meant what does it stands for
08:45 < roconnor> input g scalar.
08:45 < roconnor> I guess.
08:45 < roconnor>  * Multi-multiply: R = inp_g_sc * G + sum_i ni * Ai.
08:45 < elichai2> oh because it's the one multiplied by G, ok lol
08:46 < roconnor> oh right
08:46 < elichai2> I guessed the scalar, but didn't click the G and didn't realize inp=input
08:46 < roconnor> intput generator scalar
08:46 < roconnor> I didn't name it, so I don't really know.
08:46 < sipa> yeah, input g scalar i think
08:50 < roconnor> elichai2: I'm pretty happy with your API proposal. I'm just worried about how the implementation will all fit together.  But I'm optimisitc something will work.
08:53 < roconnor> secp256k1_ecmult_multi_var isn't used anywhere other than benchmarks and tests (and maybe -zkp), so indeed it should be able to be changed if we feel the need.
08:55 < elichai2> yeah I'm going over the internals now and then in the next few days i'll try to stub a quick implementation to first see if everything fits. right now it does look like i'll call secp256k1_ecmult_strauss_wnaf/secp256k1_ecmult_pippenger_wnaf directly
09:00 < roconnor> It would certainly make sense to batch sigs/tweeks to something that won't exceed ECMULT_MAX_POINTS_PER_BATCH.
09:01 < roconnor> Not quite sure how that value was was obtained or what it means.
09:03 < nickler> roconnor: I added that limit to be able to test all possible batch sizes
09:15 < roconnor> That feels like an unusual justification for that limit.
09:32 < nickler> Noted. This code is quite complex in its current state, so being able to test edge cases is a pretty good justification (I don't know about "unusual").
09:33 < roconnor> I don't quite get it.  It seems like you are introducing an edge case just to test it.  But whatever.
09:44 < nickler> The idea (iirc) is to replace the edge case n_points <= SIZE_MAX (untestable) with n_points <= ECMULT_MAX_POINTS_PER_BATCH (testable). But whatever.
09:46 < sipa> that makes sense to me
09:51 < sipa> also at such large batch sizes there are only diminishijg returns at best, i think?
09:52 < sipa> iirc we observed performance.even decreasing at some size
09:52 < sipa> don't remember where
09:56 < roconnor> what do you meanby diminishing returns?
09:57 < sipa> where doing a batch of N points takes barely less time to verify than 2 batches of N/2 points
09:57 < sipa> sorry, phone typing
09:58 < roconnor> ah right
09:58 < roconnor> I was thinking of N+1 vs N and 1.
10:01 < sipa> nickler: i wonder if we should redo the batch validation benchmarks/graphs now we have safegcd; the difference between sqrt and inv is a lot bigger now... maybe that means very small batches aren't worth it anymore
10:03 < roconnor> If you do that can you also again estimate the fraction of time spent on decompression vs the rest of batch validation?
10:03 < sipa> iirc we took that into account in previous benchmarks
10:04 < roconnor> nickler: gave me some figures a few weeks ago suggesting that about 40% of the time was spent in decompression for large batches. (IIRC).
10:05 < sipa> we need batch square root :(
10:05 < roconnor> yea, presumably that precentage is going to be going up.
10:06 < roconnor> I never should have told you folks about compressed keys. :)
10:08 < sipa> haha
10:09 < sipa> if we wouldn't have ecdsa compressed pubkeys, i suspect bitcoin would have adopted schnorr signatures much earlier (just to get the compressed key benefit)
10:48 -!- jonatack [jon@gateway/vpn/airvpn/jonatack] has quit [Quit: jonatack]
11:01 -!- jonatack [jon@gateway/vpn/airvpn/jonatack] has joined #secp256k1
14:12 < nickler> sipa: Hm yeah pushed some updated benchmark numbers to the PR and it looks quite different. Will try to find my the code I created the graph with.
14:12 < nickler> safegcd is just too good
15:10 < elichai2> nickler: are you sure these are because of safegcd and not endomorphism?
15:11 < elichai2> (which turned from default off to on in the rebase)
15:21 < nickler> elichai2: indeed, the pre-rebase bench was without endo
15:31 -!- gmaxwell [~procyonid@wikimedia/KatWalsh/x-0001] has joined #secp256k1
15:32 < gmaxwell> Is https://github.com/bitcoin-core/secp256k1/pull/760#issuecomment-810618207 showing a performance regression?  ... safegcd shouldn't have made batch verification slower. :)
15:37 -!- michaelfolkson2 [~michaelfo@2a03:b0c0:1:e0::23d:d001] has joined #secp256k1
15:40 -!- aj_ [aj@cerulean.erisian.com.au] has joined #secp256k1
15:42 -!- wxss [~user@mail.deeplinkmedia.com] has quit [Ping timeout: 265 seconds]
15:43 -!- wxss [~user@mail.deeplinkmedia.com] has joined #secp256k1
15:43 -!- michaelfolkson [~michaelfo@161.35.37.66] has quit [Quit: ZNC 1.8.0 - https://znc.in]
15:43 -!- aj [aj@cerulean.erisian.com.au] has quit [Ping timeout: 240 seconds]
16:01 -!- gmaxwell [~procyonid@wikimedia/KatWalsh/x-0001] has left #secp256k1 []
19:11 -!- aj_ is now known as aj
20:20 -!- belcher_ [~belcher@unaffiliated/belcher] has joined #secp256k1
20:22 -!- belcher [~belcher@unaffiliated/belcher] has quit [Ping timeout: 240 seconds]
22:14 -!- waitman [wago@monkeymeat.coolchatclub.com] has joined #secp256k1
--- Log closed Wed Mar 31 00:00:11 2021