--- Day changed Thu Sep 03 2015 10:11 -!- nullbyte [~NSA@193.138.219.233] has quit [Ping timeout: 244 seconds] 10:13 -!- nullbyte [NSA@gateway/vpn/mullvad/x-mpdkurhgumpbhnfe] has joined #secp256k1 11:22 < andytoshi> sipa: has the script in #302 changed from when we looked at it here a couple days ago? 11:22 < andytoshi> aside from the big new comment 11:23 < andytoshi> also, is there a PR to fix the ./bench_sign bug since the new recovery code? 11:37 < gmaxwell> I can open one. Sorry, expected someone else to do it. One sec. 11:54 -!- nullbyte [NSA@gateway/vpn/mullvad/x-mpdkurhgumpbhnfe] has quit [Ping timeout: 255 seconds] 11:55 -!- nullbyte [NSA@gateway/vpn/mullvad/x-fisjkgfcvwgzwyly] has joined #secp256k1 12:03 < gmaxwell> andytoshi: #304 btw. 12:04 < gmaxwell> cfields: would it be possible to get clang format to produce almost exactly the existing style (and perhaps enforce some of the style, like no unbraced if/for/etc.) ? If so it might be good pre-release to do so. 12:09 -!- nullbyte [NSA@gateway/vpn/mullvad/x-fisjkgfcvwgzwyly] has quit [Ping timeout: 265 seconds] 12:11 -!- nullbyte [NSA@gateway/vpn/mullvad/x-dndfbsndwoczsyvx] has joined #secp256k1 12:21 < sipa> andytoshi: it changed significantly 12:22 < sipa> uses a different basis 12:22 < sipa> has no more explicit add/double formula 12:22 < sipa> detects when a formula returns Z=0 inside its assumption domain 12:22 < sipa> is faster 12:22 < sipa> and gives beyter diagnostics 12:23 < sipa> i have an unsubmitted change that speeds it up more by adding simplification of ezpressions 12:23 < sipa> gmaxwell: clang format sounds good 12:25 -!- nullbyte [NSA@gateway/vpn/mullvad/x-dndfbsndwoczsyvx] has quit [Ping timeout: 260 seconds] 12:25 < sipa> but the current code runs in a few seconds here 12:25 < sipa> though i tested with some changes to the group laws to break it in some cases, and runtime went up to 2 minutes or so to find the errors 12:26 -!- nullbyte [NSA@gateway/vpn/mullvad/x-ejxokjabtjbckkox] has joined #secp256k1 12:27 < gmaxwell> sipa: do you think the suggestion of also adding an exhaustive test with a mock field? 12:27 < sipa> gmaxwell: would be possible to do separately, but not with the current code (it fails for finite fields,/due to some type of factorization not being implememted) 12:28 < sipa> i'll try to implement that 12:28 < gmaxwell> sipa: I just mean e.g. something that calls the group law functions and passes in finite field objects and exaustively verfies the law. E.g. try all pairs of projective points and make sure they produce the same affine results. 12:29 < andytoshi> sipa: ok, cool, i'll reread the whole thing :) 12:29 < andytoshi> gmaxwell: running the 512-config test matrix on #304 (including running benchmarks!) 12:30 < gmaxwell> I guess the way the branches are factored would mess that up. 12:33 < sipa> gmaxwell: the input domain is 6 dimensions, so the field size would need a p^6 that is not too large 12:35 < gmaxwell> Yes, though not all values are on the curve, so the actual space is more like field^4/2 or so. 12:35 < gmaxwell> and 43^4 is not so huge. 12:41 < sipa> oh, right! 12:41 < sipa> that's a bit ugly, as i wanted to avoid an explicit curve formula 12:44 < sipa> the switch to boost multiindex 12:45 < sipa> 43^6 may still be doable 12:45 < sipa> it's a few billion 12:45 < sipa> ooh 12:46 < sipa> but perhaps i can do early testing 12:46 < sipa> iterating over ax,ay,bx,by and you can already apply tue curve equation 12:47 < sipa> that would be pretty fast 13:17 < gmaxwell> 43 is the smallest field which is 7%12 and where y^2=x^3+7 has prime order. (uh perhaps I should check the order to see if its not insanely small.. :) ) 13:21 < andytoshi> i count 30 points that satisfy that equation 13:21 < andytoshi> i guess, plus infinity that's 31 13:27 < gmaxwell> andytoshi: yes but there are many more projective points. 13:28 < andytoshi> 42 times that number so 1806 finite points, then 43^2 - 1 = 1848 infinite ones? 13:28 < gmaxwell> 127 was another field size that worked. There are a bunch of them. If we get the count small enough it might be reasonable to try with a couple field sizes. 13:29 < andytoshi> well, we treat all infinities the same tho so it doesn't matter how many there algebraically are 13:30 < gmaxwell> is it really 42 times? 13:30 < andytoshi> i think, yeah, for all the 42 nonzero z values you do (x, y) -> (z^2x, z^3y, z) 13:33 < andytoshi> btw there are 127 affine points mod 127, so 16002 finite projective ones 13:34 < andytoshi> and i'm computing this in the python REPL `len([(x, y) for (x, y) in product(xrange(0, p), xrange(0, p)) if (y ** 2) % p == (x ** 3 + 7) % p])` with p = 127 13:34 < andytoshi> and `from itertools import product` 13:35 < gmaxwell> andytoshi: I would have expected (z^2,z^3) to not be unique for all z in Z/43Z. 13:36 < andytoshi> that's ok, z is unique, and z is a coordinate 13:36 < andytoshi> so the points are distinct 13:37 < gmaxwell> okay, I see, interestingly I think thats a stronger promise than we actually need from the group law, but fine to test it. 13:38 < gmaxwell> actually the projection randomization says we do need to test it. OKAY. 13:40 < andytoshi> oh, for p = 43 i meant 30*42 = 1260 finite points 13:40 < andytoshi> which btw matches `len([(x, y, z) for (x, y, z) in product(xrange(0, p), xrange(0, p), xrange(0, p)) if ((y ** 2) % p == (x ** 3 + 7 * z ** 6) % p) and z != 0])` 13:41 < andytoshi> and for p = 127 i meant 126 * 126 = 15876 13:48 < sipa> well, there are other algebraic things to do that can simplify things 13:48 < sipa> for example, if we can prove that the affine cx/cy coordinates do not depend on the input Az,bZ, you can avoid the whole Z coordinate, and set it to one 13:49 < sipa> but then again, if you're trusting the algebraic proof, there would be no need to do an exhaustive search either 13:49 < sipa> so i would argue that the exhaustive search is there for the case the algebra.is.wrong, and you shouldn't rely on it for simplification 13:50 < sipa> and ideally, just iterate all 43^6 combinations, evaluate for all branches whether its assumptions are true, check the result, and check that exactly one branch gives valid result for every input 13:50 < sipa> or even, at most one 13:52 < andytoshi> for each 6-tuple, at most one branch has its assumptions satisfied, and that branch gives a valid result? 13:53 < andytoshi> i'm not sure that having multiple branches match is a problem, but i don't expect it'll happen so i guess we ought to know about it 13:54 < sipa> it means your branch assumptions are badly chosen 13:55 < sipa> you don't write code that uses data from both the then and else branch 13:55 < sipa> but yes, at most one has satisfied assumptions, and that branch gives the right result 13:56 < andytoshi> oh i see, if both match then the tests do not match the code 13:56 < andytoshi> because the code can only ever take one branch 13:56 < sipa> i think we probably want a branch-independent assumption set to, so you can even enforce "when the branch-independent assumotions are satisfies, there is exactly one branch that matches, and that branch gives the right result" 13:57 < andytoshi> yeah, the curve equation should be such an assumption 13:57 < sipa> that would be exhaustively checkable 13:57 < sipa> no, the curve equation is a formula assumption, not an implementation assumption :) 13:57 < andytoshi> oh, ok :) 13:57 < sipa> the "add" checker will enforce that, because if it isn't satisfied, there is not even anything to check 13:58 < sipa> but for example the z=1 condition for affine adders is such a branch-independent assumption 13:58 < andytoshi> gotcha 13:59 < sipa> there distinction between formula assumptions and imolementation assumptions is already in the code now 13:59 < andytoshi> kk i am just reading it now 13:59 < sipa> because there is a pretty printer for the "added assumptions" that an implementation adds on top of the formula assumptions 14:02 < gmaxwell> sipa: 43^6 is an awful lot, I generally agree, but I don't think it compromises it to take the most trivial simplifications. Even though there may still be algebra risk, if its disjoint algebra risk, thats not big deal. But ... I suppose its not even worth discussing e.g. if 43^6 just takes less than time than the discussion to run. :) 14:05 < andytoshi> fwiw i think we should at least put the 1260 finite points into an hardcoded array and iterate over that, vs the 79507 possible triples 14:05 < andytoshi> but agree with "possibly not worth discussing" :) 14:06 < gmaxwell> well, 43^6 is ~= 2^32, I was not expecting that to finish in sage in remotely reasonable time. 14:08 < gmaxwell> 43^4*4 (X,sign,Z,X,sign,Z) would probably be okay. 14:11 < andytoshi> yeah, that's only 14 mil, even if you have to do a sqrt on every iteration that's fine 14:11 < andytoshi> less than a half hour anyway :) 14:12 < andytoshi> oh, sqrt mod 43 you can do by table lookup (ditto for inversion) 14:13 < andytoshi> so i'd swag 14mil iterations is under a minute 14:18 -!- andytoshi [~andytoshi@unaffiliated/andytoshi] has quit [Quit: WeeChat 1.1.1] 14:18 -!- andytoshi [~andytoshi@wpsoftware.net] has joined #secp256k1 14:18 -!- andytoshi [~andytoshi@wpsoftware.net] has quit [Changing host] 14:18 -!- andytoshi [~andytoshi@unaffiliated/andytoshi] has joined #secp256k1 14:20 < andytoshi> hehe, i ran sipa's sage script with B multiplied by various powers of six and the results are unchanged (i.e. the effective affine isomorphism works) 14:20 < andytoshi> err, various things to the sixth power 17:11 < gmaxwell> crap, I had comments on the sage comments and now I don't. 17:11 < gmaxwell> andytoshi: I think you could extend it to test that too. 17:13 < sipa> hmm, weird, i have a case where adding two points results in a point with the same X as one of the inputs 17:13 < sipa> oh, i guess we should check the cofactor of the curve 17:14 < sipa> i don't think this should be possible 17:15 < sipa> oh, yes it should be 17:15 < gmaxwell> that would mean that a + b = -a or -b 17:15 < sipa> which is the case when 2a == -b 17:16 < gmaxwell> probably a good case to test concretely too. 17:16 < sipa> so, my code fails for this 17:16 < gmaxwell> Which code fails for this? 17:17 < sipa> the colinearity test reduces to 0==0 if two x coordinates are identical 17:17 < gmaxwell> ah, that. 17:17 < sipa> so it is insensitive to errors for such additions 17:18 < gmaxwell> Perhaps an additional test for an isomorphic addition would help? like veryify a+1 + b-1 = a + b? 17:20 < sipa> i actually do 3 collinearity tests, with permuted inputs 17:20 < sipa> i think one of them will always be sensitive 17:22 < sipa> if the three points are (a,b,-a), it means (a,b,a) should be collinear... which is trivially true 17:23 < sipa> so there is no need for a sensitive test even 17:23 < sipa> ah, but you still need the "if x coords are equal, y coords are equal or opposite" 17:23 < sipa> yes, i think the permutation works 17:24 < sipa> the formula does divisions by two x coord differences, if those are a-b and b-a, both are nonzero 17:35 < sipa> ok, iterating over all additions of valid points in Z43 takes 21s :) 17:35 < sipa> (by first building a set of valid affine points, and then iterating all combinations of those with 2 non-zero z coords) 17:37 < sipa> in Z31, it seems that there are points for which A+A == A 17:40 < gmaxwell> yea, because it has a cofactor of.. 3? I guess? 17:40 < gmaxwell> and you have a 3-torsion 17:54 < sipa> 5 minutes to verify everything in Z67 (78 points on curve) 18:00 < sipa> similar for the 66 points in Z79 18:08 < gmaxwell> Sweet. 21:08 < cfields> gmaxwell: can probably get pretty close to the same format, i'd think 21:08 < cfields> i notice clang3.7 just added a bunch of new options to clang-format 21:20 < gmaxwell> TD-Linux: ^ I wonder if that was smarters work? 21:21 < TD-Linux> I don't think he upstreamed anything... he was never able to correctly get it to format daala's code 21:24 < gmaxwell> TD-Linux: I know he had proposed some patches upstream. 22:31 -!- nullbyte [NSA@gateway/vpn/mullvad/x-ejxokjabtjbckkox] has quit [Ping timeout: 250 seconds] 22:33 -!- nullbyte [NSA@gateway/vpn/mullvad/x-ltbtdakhauffhhfz] has joined #secp256k1 22:38 -!- nullbyte [NSA@gateway/vpn/mullvad/x-ltbtdakhauffhhfz] has quit [Read error: Connection reset by peer] 22:42 -!- nullbyte [NSA@gateway/vpn/mullvad/x-osqhtogxmctquags] has joined #secp256k1 23:04 -!- nullbyte [NSA@gateway/vpn/mullvad/x-osqhtogxmctquags] has quit [Ping timeout: 244 seconds] 23:06 -!- nullbyte [NSA@gateway/vpn/mullvad/x-azpbogjcrdsegsbn] has joined #secp256k1 23:13 -!- nullbyte [NSA@gateway/vpn/mullvad/x-azpbogjcrdsegsbn] has quit [Ping timeout: 252 seconds] 23:15 -!- nullbyte [~NSA@193.138.219.233] has joined #secp256k1 23:53 < gmaxwell> sipa: so you could test your algebraic test like this 23:54 < gmaxwell> sipa: get the parse tree for the candidate function. Randomly change it. See if the algebraic verification passes. 23:54 < gmaxwell> If it does, use the exhaustive verification. 23:54 < gmaxwell> and we leave this running my my desktop until something interesting happens.