--- Day changed Fri Jun 16 2017
01:17 < andytoshi> so i think doing a multiexp is going to require malloc to build the wnaf tables :/
01:30 < gmaxwell> context? looking at doing a generic multiexp?
01:30 < gmaxwell> how big is the table for one pubkey?
01:31 < andytoshi> yeah, looking at doing a generic multiexp
01:31 < andytoshi> 257 ints for one pubkey i think
01:31 < andytoshi> and these don't need to be ints, they can be chars
01:32 < andytoshi> wait...no, that's not true, one moment
01:32 < gmaxwell> well you can do the multiexp in batches the performance impact from the multiexp has diminishing returns.
01:32 < gmaxwell> so, e.g. if it's only reasonable to put 32 keys worth of table on the stack then just do that.
01:33 < gmaxwell> though if we're doing batches that big we should implement bos-coster. esp with the endomorphism it can be a lot more efficient.
01:35 < andytoshi> ok, i'll look that up
01:36 < gmaxwell> I'll see if I can find my sage implementation
03:06 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has quit [Remote host closed the connection]     
03:06 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has joined #secp256k1     
04:13 < andytoshi> nice, this is waay easier than the window precomp stuff, thanks
04:14 < andytoshi> though i should maybe haul out C Unleashed and remember how to write a heap..
05:05 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Read error: Connection reset by peer]     
05:05 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has quit [Read error: Connection reset by peer]     
05:06 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has joined #secp256k1     
05:06 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1     
05:22 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has quit [Remote host closed the connection]     
05:22 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has joined #secp256k1     
11:27 < indutny> endomorphism really makes wnaf fast
11:27 < sipa> almost sounds like a drug
11:27 < indutny> wnaf is better to support 4-point multiplication+addition
11:28 < indutny> to make verification very very fast
11:28 < indutny> sipa: it is worse
11:28 < indutny> GLV is really fast
11:28 < sipa> it's maybe a 20-30% soeedup
11:28 < sipa> *speedup
11:28 < indutny> this is a lot of secp256k1
11:29 -!- SopaXorzTaker [~SopaXorzT@unaffiliated/sopaxorztaker] has quit [Remote host closed the connection]     
11:30 < indutny> but looks like you added it already https://github.com/bitcoin-core/secp256k1/commit/949bea92624fbd65bfb21d773f1df6a115af71ff
11:30 < sipa> GLV was the reason for writing libsecp256k1
11:31 < indutny> right, so I'm no longer sure what andytoshi was discussing then
11:31 < sipa> the ability to compile without it was only added layer
11:31 < sipa> we don't have multiexp
11:31 < sipa> not for arbitrary number of points
11:31 < sipa> only for a*P + b*G
11:32 < indutny> ah well
11:32 < indutny> ok, I see now
11:36 < gmaxwell> It is also patented.
11:36 < indutny> heh     
11:36 < gmaxwell> also, come on dude, you copied the impl from our codebase previously; we talked about this a long time ago.
11:37 < indutny> I doubt that I copied it from your codebase
11:37 < indutny> but we talked about it indeed
11:37 < gmaxwell> You were asking me how we computed the lambda and beta constants for it a couple years ago, you don't recall?
11:38 < indutny> does it mean that it was copied? :)
11:38 < gmaxwell> and in a plain multiexp its improvement asymptotically goes to nothing as the number of points increase.
11:39 < gmaxwell> indutny: oh sorry, my point was it looked to me like you learned how to do it from us, so I thought it was really weird that you were telling us to use it.
11:39 < indutny> oh well!
11:39 < indutny> this is more like it
11:40 < gmaxwell> (I didn't mean that you copied the code itself or anything like that.)
11:40 < indutny> my memory is failing on me on this, to be honest
11:40 < indutny> but I did `git log` in about 10 minutes since asking :)
11:40 < indutny> it all looked suspicious from the start so I should have done it before talking about it
11:41 < indutny> sorry for this
11:41 < gmaxwell> np     
11:42 < gmaxwell> But as I said, its improvement with a plain wnaf multiexp goes to nothing with more pubkeys... basically the improvement from the endomorphism is that it halves the number of doublings that you do.   But if you are multiexping 64 points, the doublings hardly matter, they're a tiny percentage of the total time.
11:42 < indutny> it is still noticeable for 4 points
11:42 < indutny> like in verification
11:42 < indutny> I wasn't really talking about doing bigger multiexp
11:42 < indutny> didn't realize that that was discussed
11:43 -!- SopaXorzTaker [~SopaXorzT@unaffiliated/sopaxorztaker] has joined #secp256k1     
12:33 -!- SopaXorzTaker [~SopaXorzT@unaffiliated/sopaxorztaker] has quit [Remote host closed the connection]     
13:29 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Remote host closed the connection]     
13:30 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1     
16:25 -!- phantomcircuit_ [~phantomci@192.241.205.97] has joined #secp256k1     
16:26 -!- Netsplit *.net <-> *.split quits: phantomcircuit, [b__b]
16:27 -!- Netsplit over, joins: [b__b]
23:25 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has quit [Remote host closed the connection]     
23:26 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has joined #secp256k1