--- Log opened Fri Dec 11 00:00:44 2020 00:00 < real_or_random> sipa: that's awesome 00:02 < sipa> it's taken me a few days already, but it's a really effective way of review too 00:03 < sipa> lots of things i thought i understood but didn't until i tried to explain them 00:09 < real_or_random> yeah that's not unexpected I guess, but it's always a nice feeling :) 00:11 < sipa> indeed 00:12 < real_or_random> and I totally agree, it makes review more effective. I mean, why should every reader redo the same thoughts 00:13 < real_or_random> (in some sense, we want this to make sure that the reviews are independent... but checking a proof is easier than coming up with it) 00:13 < sipa> even if nobody reads this, i think this was a good use of my time 00:13 < sipa> i definitely understand it a lot better 00:14 < real_or_random> :D 00:14 < aj> sipa: nice! 00:15 < real_or_random> reminds me of this: I attended a seminar about compiler verification at uni. we were looking at the very early works in this space 00:16 < real_or_random> they all took a pair of input code and output code of the compiler, and tried to prove them equivalent. 00:17 < real_or_random> this did not really work out except for basic examples. and this is so clear if you look at it. it totally ignores the knowledge of the compiler 00:18 < real_or_random> i.e., the tool needs to infer what the compiler had in mind. why not ask the compiler to output a proof for why some optimization was justified? 00:18 < sipa> right 00:21 < real_or_random> (It's not a great insight that the one who claims a property should provide a reason. Humans have done this for ever. 00:22 < real_or_random> But I found it amusing that it applies to computer programs too) 00:25 < sipa> also: how the hell did dettman discover that (x * x * (x - 2)) computes the negative of the modular inverse of x, modulo 64? 00:25 < sipa> sorry, (x * (x * x - 2)) 00:26 < real_or_random> wtf 00:26 < sipa> and that that's faster than a lookup table :p 00:50 < aj> https://crypto.stackexchange.com/questions/47493/how-to-determine-the-multiplicative-inverse-modulo-64-or-other-power-of-two ? clever induction from mod 2^n to mod 2^2n? 00:57 < sipa> ooh that looks related 01:00 < sipa> mod 8 it holds that x^2=1 for all odd x 01:00 < sipa> thus mod 64 it holds that x^2 * (2 - x^2) = 1 01:01 < sipa> and thus x*(2-x^2) must be the inverse of x mod 64 01:06 < sipa> with an extra multiplication this works for 4096 03:01 -!- belcher [~belcher@unaffiliated/belcher] has joined #secp256k1 03:48 < roconnor> real_or_random: https://github.com/fmlab-iis/gcc2cryptoline/tree/master/examples/bitcoin 03:49 < real_or_random> oh nice 04:11 < sanket1729> I tried reading about the bounds in safegcd paper. completely over my head. 04:12 < sanket1729> I am super curious as how can sipa reason about all possible numbers 6600 bits because you cannot brute force that 04:13 < aj> sounds like a pieter wuille fact 04:25 < sanket1729> > the number of vertices on these convex hulls seems to only grow linearly with the number of divsteps, which makes this approach tractable. 04:43 -!- dr-orlovsky [~dr-orlovs@31.14.40.19] has joined #secp256k1 05:14 < sanket1729> sipa: Since ceil(724/62) and ceil(741/62) are both 12. Does this mean that the convex hull effort for upper bounds would not translate into practice? Even without that, we would used the same code constants? 05:18 < sanket1729> I think the idea is really cool and definitely worth exploring, I am just double checking my understanding. 07:39 < sanket1729> I about to something that I think worked, but as I typing it realized did not work because it requires secret data dependent memory access. But still if it works otherwise 07:39 < sanket1729> Since all the matrices form a ring, they are commutative, we can only keep track of how many times each branch(among the three conditional for divstep). We also have a precomputed table t[c0][c1][c2] where c0, c1, c2 represent the counts for number of times each branch was taken. 07:39 < sanket1729> Note that this table will have limited rows(loose bound 62^3). That way we can save 4 multiplications and replace them by counter per iteration. 07:53 -!- belcher [~belcher@unaffiliated/belcher] has quit [Ping timeout: 272 seconds] 07:56 -!- reallll [~belcher@unaffiliated/belcher] has joined #secp256k1 08:00 -!- reallll is now known as belcher 08:49 < sipa> sanket1729: matrices are a ring but not a commutative ring 08:50 < sanket1729> oops 08:50 < sipa> sanket1729: and yes, there is no practical gain for 256 bits; i mentioned that in one of my tweets about it 08:53 < sanket1729> wow, I retweeted that thread and did not read the tweet :facepalm 08:56 < sipa> sanket1729: as for the 6600 bit numbers, the key realization is that we only need to know for every iteration count what the largest possible number is 08:56 < sipa> once we have that, we can verify that list against any approximation formula you want 08:59 < sanket1729> I see that's why you have section titled Thresholds in the safegcd writeup. At first, that seemed unrelated to the problem of good upper bound, so I ignored it 09:01 < sipa> regarding the starting delta value 09:01 < sanket1729> yes, i am super curious about it. 09:02 < sipa> it's related to how much we know g is smaller than 2f, i believe 09:02 < sipa> and 1 represents they're equal in magnitude 09:03 < sipa> negative means 2f is smaller 09:03 < sipa> positive means g is smaller 09:03 < sanket1729> yes, that was my understanding too. I think they represent the degree difference you represent both the numbers are polynomials in Z2 09:04 < sanket1729> so, if p = 256 bits and x is 254 bits, my intuition was that we should set delta 2 09:04 < sipa> delta 3, even 09:04 < sipa> but i don't know if this matters in practice 09:04 < sipa> because the variable-time version of the algorithm does multiple divsteps at once 09:05 < sanket1729> is it correct to say that correctness of the algorithm is not on delta at all? Or maybe only on the sign? 09:05 < sanket1729> not dependant 09:06 < sipa> oh it matters; it:s needed to guarantee it terminates, for one 09:07 < sanket1729> but there is no "one right" value for delta. 09:08 < sipa> setting it wrong may definitely increase the number of divsteps needed 09:09 < sipa> sanket1729: i'm going to try simulating to see if setting the initial delta makes a difference 09:10 < sanket1729> okay, that answers my question about initial value of delta. Since, we are anyways doing fixed number of iterations and operations, trying to set a value dependent on bits may not make a difference 09:10 < sanket1729> oh, simulations 09:10 < sanket1729> nice 09:14 < sipa> the primary thing the delta value does is restrict what sequences of transitions are legal 09:14 < sipa> there are 3 possible transitions, but at any point (given delta) only 2 are allowed 09:15 < sipa> that's necessary for the algorithm to cobverge 10:26 -!- jonatack [~jon@213.152.186.40] has quit [Ping timeout: 240 seconds] 10:50 -!- jonatack [~jon@37.170.61.94] has joined #secp256k1 11:03 -!- jonatack [~jon@37.170.61.94] has quit [Read error: Connection reset by peer] 11:26 -!- jonatack [~jon@213.152.161.244] has joined #secp256k1 12:28 -!- belcher [~belcher@unaffiliated/belcher] has quit [Ping timeout: 272 seconds] 12:44 -!- belcher [~belcher@unaffiliated/belcher] has joined #secp256k1 --- Log closed Sat Dec 12 00:00:44 2020