--- Log opened Wed Jun 02 00:00:26 2021
01:52 -!- glozow [sid453516@user/glozow] has joined #secp256k1
03:18 -!- belcher_ [~belcher@user/belcher] has quit [Ping timeout: 272 seconds]
03:28 -!- belcher [~belcher@user/belcher] has joined #secp256k1
04:02 -!- belcher [~belcher@user/belcher] has quit [Quit: Leaving]
04:03 < michaelfolkson> Thanks for sharing this gmaxwell, I don't understand some of it, need to revisit endomorphism :)
04:43 -!- belcher [~belcher@user/belcher] has joined #secp256k1
04:57 -!- belcher [~belcher@user/belcher] has quit [Quit: Leaving]
04:57 -!- belcher [~belcher@user/belcher] has joined #secp256k1
05:37 < roconnor> sipa: pippenger doesn't use the g_128 table. ... or I guess you are talking about strauss.
05:39 < roconnor> I mean, strauss is "typically" used for non-batch verification.  I'm not sure eliminating the table is going to be a win for that.  I guess that would need to be tested.
05:39 < roconnor> Then pippenger is used for large batchs.
05:40 < roconnor> and I've been sort of assuming that those are the two main use cases, and that small batches will be rare in practice.
05:47 < roconnor> Maybe I'm wrong, and we will batch verify very small number of signatures within one transaction.
07:37 < sipa> roconnor: yeah, i was only talking about strauss
07:37 < sipa> pippenger is only used for 100+ points or so
07:38 < roconnor> you say "is only used" but I was figuring that is going to be the vast majority of batch cases
07:41 < sipa> eh, this was in the comtext of deciding whether this variant was worth it even for cases with 1 or just a few points
10:06 -!- sipa_cloud [uid502720@id-502720.highgate.irccloud.com] has joined #secp256k1
10:07 < sipa> test
10:12 < real_or_random> sipa: PASS
10:12 < sipa_cloud> 1/1 tests successful
10:12 < sipa_cloud> goodbye
10:12 -!- sipa_cloud [uid502720@id-502720.highgate.irccloud.com] has left #secp256k1 []
10:33 < gmaxwell> roconnor: I don't know about that assumption wrt batching.  E.g. when verifying single transactions, it makes sense to batch across all their inputs, esp if they're all sighash_all.  It would be the easiest form of batching to implement in Bitcoin.
10:34 < roconnor> what's a typical number of inputs? 2 or 3?
10:35 < gmaxwell> Sure, but there are many transactions that have dozens.
10:36 < roconnor> also fun to think about, we could multiply by lambda or lambda^2 depending on which has the "smaller" wnaf.
10:36 < roconnor> ... this though is less than half-baked.
10:36 < roconnor> *thought
10:38 < sipa> or -lambda or -lambda^2
10:38 < gmaxwell> roconnor: I think I checked that at some point and found that the difference is extremely small. The L1 norm of the large window wnaf vectors is quite close to the maximum, so the lesser choice of two different ones doesn't change things much.
10:41 < gmaxwell> (er, should have said L0 norm there)
10:55 < roconnor> sipa: I was picturing some sort of magical optimization where we repeatedly add points then multiply the accumulator by -lambda.
10:55 < roconnor> and everything lines up perfectly.
10:58 < sipa> so while lambda is a cube root of 1, -lambda is a hextic root of 1
10:58 < roconnor> yes. a primitive root even.
11:00 < roconnor> Factor[x^6 - 1] = (x - 1) (x^2 + x + 1) (x + 1) (x^2 - x + 1)
11:07 < gmaxwell> sipa: one thing that occured to me is that fixed window naf would reduce the maximum number of batch endo batches.
11:08 < gmaxwell> (but when I thought about it some, I realized it wouldn't really improve the situation for one point, so I didn't think about it too hard)
11:10 < sipa> that's a good question: how much better is variable-width wnaf than fixed-width?
11:11 < gmaxwell> I had ... assumed ... that they were actually the same in performance, other than fixed width potentially needing an extra offset addition.
11:12 < gmaxwell> (and figured if we ever constructed a double-double operation that was more efficient than two doublings, that it would make sense to move to fixed window)
11:12 < sipa> with variable width wnaf with values ranging {-15, -13, -11, ..., 15}, you have at most 1/6 of coefficients nonzero, and on average 1/7
11:13 < sipa> i don't think fixed with wnaf can be as good
11:13 < sipa> *width
11:31 < gmaxwell> they're both at most 1/6 at least.
11:33 < sipa> and for fixed width the average and worst case have to be equal
11:34 < gmaxwell> ah, does fixed never add a zero? Thats interesting.
11:36 < sipa> well it wouldn't be constant time if it did
11:37 < sipa> hmm, it could be cmoving of course
11:37 < gmaxwell> yeah, there isn't a reason we couldn't add infinities in constant time.
11:38 < sipa> yeah, it's only cmoving the table search and negation
11:38 < sipa> but the added point is always ->infinity=0
11:38 -!- roconnor_ [~roconnor@host-45-58-218-136.dyn.295.ca] has joined #secp256k1
11:39 < gmaxwell> In any case, 1/7 and 1/6 aren't that differen't. Thats a difference that could plausably be oovercome by an optimized 32P operation. :P
11:40 < roconnor_> batch verfication doesn't need to be constant time?
11:41 -!- roconnor [~roconnor@host-184-164-3-109.dyn.295.ca] has quit [Ping timeout: 252 seconds]
11:42 < sipa> no
11:43 < gmaxwell> Pippenger uses the fixed window NAF because the efficiency of the odd-multiples comb depends on bunching up all the additions at the same places.
11:44 < gmaxwell> The fact that pippenger is essentially constant time might someday make it easier to vectorize, but there isn't any need for it to be constant time.
11:45 < sipa> gmaxwell: yes, but i'm not sure the difference is enough to weight up against the (also very small) cost of computing fewer beta multiplies
11:45 < gmaxwell> sipa: I expect it is for a big enough batch, but by that point its not using strauss anymore.
11:52 -!- roconnor_ is now known as roconnor
12:30 < real_or_random> I can't follow everything here but it's great to see that this very active discussion ^^ I can imagine we'll have a nice algorithm in the end
12:31 < roconnor> I can imagine we have 27 nice algorithms in the end each optimial for one or two batch sizes.
12:31 < real_or_random> indeed...
12:32 < sipa> hahaha
12:34 < real_or_random> Bu the way, I said may sound like a strange comment from the side line but I think i should  try not to get involved further. Three a pretty good number of brains (in particular yours) and we also need people working on higher layers ^^
12:35 < real_or_random> *what I said
21:32 -!- belcher_ [~belcher@user/belcher] has joined #secp256k1
21:36 -!- belcher [~belcher@user/belcher] has quit [Ping timeout: 245 seconds]
23:57 -!- kaushik [uid502722@id-502722.charlton.irccloud.com] has joined #secp256k1
--- Log closed Thu Jun 03 00:00:28 2021