--- Day changed Sat Nov 28 2015 00:25 -!- wump is now known as wumpus 02:36 -!- Guest36383 [uid115429@gateway/web/irccloud.com/x-yjhlfmaugpqhkuob] has quit [Quit: Connection closed for inactivity] 02:57 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.] 02:57 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #secp256k1 03:54 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.] 04:55 -!- Guest36383 [uid115429@gateway/web/irccloud.com/x-ebpvpqbxoxebkzki] has joined #secp256k1 05:05 -!- Guest36383 is now known as btcdrak 05:06 -!- btcdrak is now known as Guest8622 05:06 -!- Guest8622 [uid115429@gateway/web/irccloud.com/x-ebpvpqbxoxebkzki] has quit [Quit: Updating details, brb] 05:06 -!- btcdrak_ [uid115429@gateway/web/irccloud.com/x-kptbjlqnhftmioth] has joined #secp256k1 05:07 -!- btcdrak_ [uid115429@gateway/web/irccloud.com/x-kptbjlqnhftmioth] has quit [Client Quit] 05:09 -!- btcdrak_ [uid115429@gateway/web/irccloud.com/x-tibhgopyxerhuahf] has joined #secp256k1 05:10 -!- btcdrak_ [uid115429@gateway/web/irccloud.com/x-tibhgopyxerhuahf] has quit [Client Quit] 05:10 -!- btcdrak [uid115429@gateway/web/irccloud.com/x-imneqdqceqwudrgv] has joined #secp256k1 06:52 -!- maaku [~quassel@botbot.xen.prgmr.com] has joined #secp256k1 06:53 -!- maaku is now known as Guest9487 06:53 -!- Guest9487 is now known as maaku 10:14 -!- jtimon [~quassel@74.29.134.37.dynamic.jazztel.es] has quit [Ping timeout: 240 seconds] 11:01 -!- jtimon [~quassel@74.29.134.37.dynamic.jazztel.es] has joined #secp256k1 11:47 < sipa> andytoshi: i'm confused by your confusion! 11:48 < sipa> andytoshi: do you agree that (x=0 or y=0) does not conflict with (x!=0) and does not conflict with (y!=0), but does conflict wiht (x!=0 and y!=0) 11:50 < andytoshi> sipa: yes 11:50 < andytoshi> sipa: is the list of `nonzero` an OR list? 11:51 < andytoshi> s/nonzero/zero 11:51 < sipa> no, they're AND lists 11:51 < sipa> but you encode (x=0 or y=0) as xy=0 11:51 < andytoshi> understood 11:52 < andytoshi> ok, let me thingk.. 11:52 < sipa> so zero={xy} does not conflict with nonzero={x} and not with nonzero={y}, but it does conflict with nonzero={x,y} 11:53 < andytoshi> ok, i think i was confusing "multiply them all together means OR" with something to do with zero divisors (hence my example) 11:54 < sipa> for the zero list, multiplying things together is OR 11:54 < sipa> but for the nonzero list, multiplying things together is AND 11:54 < andytoshi> heh, yeah, that makes sense 11:54 < sipa> which is why we can do things like multiply the different nonzero terms, and simply, and factorize them 11:55 < sipa> you can't do that for the zero list; instead, you create an ideal there 11:55 < andytoshi> understood 11:55 < andytoshi> i guess, my confusion is that you multiply together all the nonzero things and check if they're in the zero ideal... 11:55 < sipa> maybe this warrants some global comment about the semantics of lists 11:56 < andytoshi> ...which in the absense of zero divisors means you're checking whether *any* are zero... 11:56 < andytoshi> ...but immediately above that, you explicitly check each one 11:56 < sipa> right 11:56 < sipa> but it's possible that the product of two factors which are not in the zero ideal, is in the zero ideal 11:56 < andytoshi> because they're zero divisors? 11:57 < andytoshi> well, "zero divisors" in the ring modded out by the ideal 11:57 < sipa> yes, i think so 11:57 < sipa> not in the ring itself, but by modding out the ideal, yes 11:57 < andytoshi> yup 11:57 < sipa> that's exactly what you're testing for 11:57 < andytoshi> ok, so that's my confusion 11:57 < andytoshi> i'm not sure why we're testing for that 11:58 < andytoshi> and it's not commented anywhere that you're testing for that 11:58 < sipa> there's a very specific example in the comments now 11:58 < andytoshi> kk one moment 11:58 < sipa> testing for (x=0 or y=0) will result in {x*y} being in the zero ideal, but not {x} or {y} 11:59 < andytoshi> oh i see 11:59 < andytoshi> so when you construct the zero ideal, you are encoding OR conditions into the zero divisors 12:00 < andytoshi> and you do this waay out at `check_symbolic_execution` or whatever the high-level function is 12:00 < andytoshi> i understand now, i thought that zero divisors would be "accidental" 12:01 < andytoshi> OK. so that said, can you drop the item-by-item checking of nonzero elements? that is, is checking the product is not in the zero ideal sufficient? 12:01 < sipa> i think i added that as a performance optimization 12:01 < sipa> as almost always, that's enough 12:02 < sipa> you only need the expensive multiply + simplify when there actually are zero divisors, i guess 12:02 < andytoshi> that makes sense 12:03 < sipa> added a comment that it's an optimization 12:03 < andytoshi> ok, so i think adding a comment above `def conflicts` which explains how boolean conditions are encoded in the two lists 12:03 < andytoshi> excellent thx 12:04 < andytoshi> i was both overthinking and being stupid here, but i probably won't be the last :) 12:11 < andytoshi> i added a couple comments on github trying to clarify what my confusion was 12:12 < sipa> pushed again 12:16 < andytoshi> sipa: you added the comment at the top of the constraints class? 12:17 < sipa> yes 12:17 < andytoshi> ok, almost sufficient :) 12:18 < andytoshi> "We don't do this for performance reasons, though." should be "we first check every key individually, for performance reasons. If that passes we do the multiply-check, in case for example `a*b` is in the zero ideal but neither `a` nor `b` is. This would happen if the caller wanted to encode the condition "a = 0 OR b = 0". 12:19 < sipa> I think it's a stretch to say that the callers wants to encode that, ever. they're just formulas 12:20 < andytoshi> ok, replace the last sentence with "(This corresponds to the constraint "a = 0 OR b = 0".)" 12:21 < andytoshi> to be clear that if it happens, it's something meaningful 12:21 < andytoshi> and checking for it is the correct thing to do 12:23 < sipa> that's already explained in the conflicts comments 12:24 < sipa> added more comments 12:24 < andytoshi> oh, you say "For example, if we 12:25 < andytoshi> + # know that either x or y is zero, x*y would be in the zero set" 12:25 < andytoshi> can you add ", or and vice-versa" to that 12:25 < andytoshi> sorry :) 12:25 < sipa> what vice-versa? 12:26 < andytoshi> if x or y is zero, x*y will be in the ideal; if x*y is in the ideal then x = 0 or y = 0 12:27 < sipa> reformulated that comment a bit 12:30 < andytoshi> awesome thanks 12:30 < andytoshi> i'm happy now :) 12:31 < andytoshi> ACK group_prover.sage 12:31 < sipa> I trust the rest will be more straightforward :) 12:31 < andytoshi> (i expect the other files i'll pass without comments) 12:31 < andytoshi> yeah :) 12:56 < andytoshi> LOL at the code for checking gej_add_ge 12:57 < andytoshi> i'm really glad that you did this 13:15 < sipa> andytoshi: meaning "i'm glad this is being done" or "i'm glad i didn't write this" 13:16 < andytoshi> both 13:17 < sipa> haha 13:17 < andytoshi> i guess i never really comprehended how nasty that function had become 13:18 < sipa> likewise 13:18 < sipa> and after writing the python code for it, i was so glad that we now have validation for all of its branches 13:23 < andytoshi> heh, silly python, constraints() != constraints() 13:24 < sipa> try java 13:24 < sipa> with its even siller constraints().equals(constraints()) 13:33 < andytoshi> you check if assumeLaw + assumeAssert + assumeBranch conflict, and ignore the branch if so. i added a check to print 'Hey!' if assumeLaw+assumeAssert, or assumeBranch, causes conflicts (so one or the other conflicts by itself) and i'm etting a lot of hits 13:34 < andytoshi> in add_ge_old you have this explicit `conflict_a` `conflict_b` thing that i don't quite understand 13:35 < andytoshi> i guess you mean "no such branch" 13:35 < sipa> right, it's a very ugly way to return "this can't happen" 13:36 < andytoshi> ok, im cool with that one at least 13:36 < andytoshi> the others i haven't checked what's going on yet 13:41 < andytoshi> sipa: how come Az, Ai are capitalized but ax, ay are not? 13:41 < sipa> capitalized = jacobian 13:41 < andytoshi> kk thanks 14:03 -!- jtimon [~quassel@74.29.134.37.dynamic.jazztel.es] has quit [Ping timeout: 240 seconds] 14:06 < andytoshi> ok, of the 16 branches in gej_add_ge, 4 are never checked (assumeBranch conflicts with itself); in gej_add_ge_old 1 of 4 branches is never checked 14:06 < andytoshi> i've confirmed that all 5 of these oddities are correct 14:06 < sipa> yay 14:06 < andytoshi> now i've got a bunch of "assumeLaw + assumeAssert conflict" errors which might actually be mistakes, unsure 14:07 < andytoshi> they only trigger in gej_add_ge and gej_add_ge_old fwiw 14:07 < sipa> well gej_add_ge has an assumeAssert that b is finite; any law that deals with infinite b is going to conflict 14:09 < andytoshi> :) that covers every single gej_add_ge case, thanks 14:10 < andytoshi> ah, and gej_add_ge_old 14:10 < andytoshi> cool, so all those are legit 14:10 < andytoshi> i've confirmed that you're actually checking every single branch 14:10 < sipa> you're very thorough :) 14:11 < andytoshi> heh, well, i haven't checked that your algebra corresponds to what's in the C code 14:12 < andytoshi> and i'm not planning to .. i'm assuming that if you made a transcription error either the sage would fail or the unit tests would 14:12 < gmaxwell> that new sidechannel attack paper are is causing people to claim that libsecp256k1 is broken. :( 14:13 < sipa> well correct them damnit :) 14:14 < andytoshi> eprint 1141? it only mentions our library once. the abstract explicitly says openssl 14:18 < andytoshi> gmaxwell: where are you seeing these claims? i tried going on reddit and my screen was filled with all caps "replace by fee breaks zeroconf, bitcoin is useless now" 14:18 < andytoshi> and i'm not inclined to read past that 14:22 < gmaxwell> andytoshi: https://www.reddit.com/r/ethereum/comments/3uhd5g/secure_your_x86_nodes_sidechannel_attack_unravels/cxg45wp?context=4 the less infuriating one 14:23 < gmaxwell> the obviously intentionally shilly one: https://www.reddit.com/r/btc/comments/3umoo4/dangerous_homebrew_cryptography_in_blockstream/ 14:25 < andytoshi> thanks gmaxwell 14:27 < andytoshi> i think it's safe to totally ignore anything with the phrase "blockstream core" :) 14:27 < andytoshi> the other one i'll keep an eye on 15:00 < andytoshi> sipa: are you going to change #322 to commit to the verifciation key? 15:01 < sipa> yes 15:02 < andytoshi> cool 15:02 < andytoshi> so i should not review it yet? 15:02 < sipa> i'll do the commitment in a separate commit 15:03 < andytoshi> kk 15:03 < sipa> i like committing to commitments in different commits, so we can commit while we commit 15:03 < andytoshi> as long as you commit to doing so 15:03 < sipa> oh, i will not change #322, but i will #359 15:04 < andytoshi> ah ok 15:33 < gmaxwell> sipa: any objection to renaming secp256k1_ecmult to secp256k1_ecmult_var? 15:34 < gmaxwell> maybe after some pending patches are merged? 15:38 < sipa> gmaxwell: no objection, and i think there are several other functions that need such a var suffix 15:46 < gmaxwell> should we do now or after other merges? 15:47 < gmaxwell> I was going to get gcc to output a call graph and make everything internal _var that calls something _var and see how far that gets me. 15:47 < sipa> what others are you thinking of? i don't mind rebasing things of mine 15:48 < sipa> there are some exceptions to that rule 15:48 < sipa> where a var function is called with a compile-time known value for its var argument 15:48 < sipa> but please, go ahead 15:49 < sipa> variable shifts in the endomorphism scalar split iirc 15:51 < andytoshi> i think the endomorphism split is the only example 15:51 < andytoshi> ecmult_const used to have one and gmaxwell told me to split the _var function into a const part 15:51 < andytoshi> (it was gej_double_var when i was sure the input was nonzero) 17:45 -!- jtimon [~quassel@74.29.134.37.dynamic.jazztel.es] has joined #secp256k1 18:41 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #secp256k1 23:19 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Read error: Connection reset by peer] 23:19 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #secp256k1