--- 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.