--- Day changed Fri Feb 09 2018 02:07 -!- jtimon [~quassel@41.31.134.37.dynamic.jazztel.es] has joined #secp256k1 04:47 < andytoshi> the ECDH module might change, it's flagged experimental mainly because of that 04:48 < andytoshi> but the change will likely be to a more flexible form where you can specify the hash function 05:42 -!- eragmus [sid136308@gateway/web/irccloud.com/x-kvnyvehjxcosgqrs] has quit [] 05:42 -!- eragmus [sid136308@gateway/web/irccloud.com/x-ehywxaykfciongys] has joined #secp256k1 10:07 < droark> Gotcha. Thanks. I noticed the hash thing while going through some of the GitHub issues. 10:44 < maaku> you should maybe reconsider the word 'experimental'. we've had customers get anxious that our product requires compiling secp256k1 with the --enable-experimental flag 10:45 < maaku> when in fact all it's doing is enabling APIs that are not normally exposed because they are still an active area of development, not that the underlying feature being implemented is itself experimental 11:21 -!- jtimon [~quassel@41.31.134.37.dynamic.jazztel.es] has quit [Ping timeout: 248 seconds] 12:02 < andytoshi> unstable might be a better word, yes, and might be less appealing to the people we want to discourage 12:02 < andytoshi> "this will cause you more work" rather than "this will enable cool shit that nobody else has yet" 12:13 -!- gmaxwell [~gmaxwell@wikimedia/KatWalsh/x-0001] has joined #secp256k1 12:20 -!- mlz [~IRCIdent@unaffiliated/molly] has joined #secp256k1 12:29 < gmaxwell> andytoshi: https://bitcointalk.org/index.php?topic=2816944.msg29913441#msg29913441 am I on drugs, wrt the scheme I give in the "You can attempt" paragraph? If not, why the heck is no one using that? e.g. tor's rendezvous stuff now uses a complicated consensus protocol for picking a random value (which controls where HS's rendezvous end up) which responds to hold-up by sticking with the last random 12:29 < gmaxwell> value. 12:35 < gmaxwell> Oh this is cute, https://lists.torproject.org/pipermail/tor-dev/2014-January/006053.html sipa, andytoshi might remember before that I had an idea for a pairing crypto based threshold key hardening scheme. Where basically some threshold of signers produced a blind BLS signature of some hashed password of yours, as a password cracking rate limiting mechenism. 12:36 < gmaxwell> This implements a similar scheme in plain discrete log, but it doen't appear obviously blindable. 12:38 < gmaxwell> The idea is that the signers have some shared secret X, each of the signers has a share of X, X' they take the message they want to sign and hash it to a curve point, R. Each computes x' * R and publishes a discrete log equivilence between their share pubkey and the multiplied R. 12:38 < gmaxwell> Combination of the multiplied Rs is the determinstic signed value. 12:40 < gmaxwell> I wonder why tor didn't use that, it seems simpler to implement and much more secure than what they did implement. 12:40 < andytoshi> gmaxwell: the "use a delay function on the blockhash" idea? very clever, i think you never see it in the wild because nobody has delay functions in their mental toolbox 12:41 < gmaxwell> Nah, the use of secret sharing to prevent holdup. 12:42 < gmaxwell> The delay function thing I think people don't use due to the lack of cheap to verify determinstic delay functions. 12:43 < andytoshi> ohh nice! 12:43 < andytoshi> that's pretty clever, i think people also forget that verifiable secret sharing is a thing 12:45 < andytoshi> it also makes something of a difficult tradeoff between ability to conspire and ability to holdup 12:47 < gmaxwell> I think a 2 of 3 scheme is strictly better than the normal e.g. 3 of 3... even if 2 of the 3 conspire, all they can do is holdup if they don't like the result. 12:48 < andytoshi> they can reconstruct the other's secret and bias the randomness 12:50 < gmaxwell> hm. My proposal is first a,b,c publish commitments: aG bG and cG ... they do this before any sharing starts. 12:50 < gmaxwell> They can't open these commitments to anything else. 12:50 < andytoshi> sipa: what does libsnark mean by constraints? when i run the `test_sha256_gadget` binary that comes with it, it says 27280 constraints .. which is much lower than the 50k+ constraints that is in your sha2 circuit 12:50 < gmaxwell> Then they start sharing, at that point conspiring parties could abort the protocol when they realize they won't like the result. 12:50 < andytoshi> gmaxwell: ohh i see 12:51 < sipa> andytoshi: what input does the gadget have? 12:51 < andytoshi> i guess they could progressively reveal lower and lower thresholds, and the limit is 1-of-n when everyone reveals their secrets 12:51 < gmaxwell> requires an extra round that way. 12:51 < sipa> we have 28400 gates 12:51 < sipa> for one compression function run 12:52 < sipa> sorry, 25400 gates 12:53 < andytoshi> lemme see, i've gotta chase through their source code 12:53 < gmaxwell> andytoshi: interesting idea there. the original step of just the commitments is a n of n... then you walk back to 1 of n ... damn thats neat, I don't think I've seen anything like that before. 12:54 < sipa> andytoshi: the 50000 mult gates was from an earlier run where i gave it a 56-byte input to full SHA256, resulting in two compression runs 12:54 < andytoshi> right it's only 32k gates 12:54 < andytoshi> but it's 51k constraints 12:54 < sipa> i fixed it just before you did the benchmark to a 64-byte input without padding 12:55 < gmaxwell> That might just be due to QSPs getting xor for free. 12:55 < gmaxwell> maybe 12:56 < sipa> right 13:01 < andytoshi> it looks like they're doing xor with A + B - 2AB 13:01 < sipa> so are we 13:01 < sipa> strange 13:01 < sipa> gmaxwell said they're treating bits differently from ints 13:01 < sipa> and in the bits model, xor is just addition mod 2 13:02 < sipa> are you sure they're treating all xors as a+b-2ab? 13:02 < andytoshi> https://github.com/scipr-lab/libsnark/blob/master/libsnark/gadgetlib1/gadgets/hashes/sha256/sha256_aux.tcc#L80-L95 is what i'm looking at .. still tracing through al the code paths 13:02 < andytoshi> no i'm not sure 13:02 < sipa> or just xors on ints 13:02 < andytoshi> they use a lot of `small_sigma_gadget` and `big_sigma_gadget` in sha2 13:02 < andytoshi> which looks like it's 32 xor gadgets, which looks liek A + B - 2AB 13:03 < sipa> wait, that's the libsnark sha2 code? 13:03 < andytoshi> yes 13:03 < sipa> not the jsnark one? 13:03 < andytoshi> correct 13:03 < andytoshi> i don't have java on my system 13:04 < sipa> i think the pinocchio output of jsnark is in my zkstuff repo 13:04 < andytoshi> i don't know how to use pinocchio output .. or how to get that output from one of these gadget objects 13:04 < andytoshi> i just want to run some benchmarks and libsnark is making me understand the whole library.. 13:05 < sipa> okay 13:15 < andytoshi> in jsnark it seems like xor is doing a mult too https://github.com/akosba/jsnark/blob/3d56f6edad92d64dfd35d7de66570c57f6bc611c/JsnarkCircuitBuilder/src/circuit/operations/primitive/XorBasicOp.java 13:15 < andytoshi> i mean, it says `numMulGates = 1` .. but there is nothing in that code that resembles an xor 13:15 < andytoshi> is "xor" a basic op in the pinnochio output? 13:19 < sipa> yes 13:20 < sipa> i'm talking to ebfull about this 13:20 < andytoshi> kk thanks 14:35 < andytoshi> i think the problem may be that libsnark is using constraints in the sense of https://eprint.iacr.org/2013/507.pdf appendix E "system of rank-1 quadratic equations" vs our constraints which are linear 14:35 < andytoshi> i'm trying to figure out how these quadratic equations behave.. 14:36 < gmaxwell> andytoshi: in the original pinocchio paper, they show that they can use span programs instead of arithmetic programs on binary circuits, which is analogous to be able to use a lower degree equation for the range proofs. 14:37 < gmaxwell> They describ decomposing a circuit into a arithmetic part and a binary part, and using range proofs on the wires between them. 14:39 < andytoshi> oh thanks, i think "rank-1 constraint system" is the same as QAP, and the pinocchio paper has an explanation of how to turn a circuit into a QAP 14:39 < andytoshi> i think the QAP/QSP trick is different from what we do with rangeproofs, we exploit the fact that we have no variable output wires to get a lower degree 14:40 < andytoshi> maybe we can steal the QSP trick as well 14:41 < gmaxwell> I didn't see a way that it could get us smaller proofs, it looked it it would make them larger... though maybe faster to verify. 14:41 < andytoshi> i don't understand how you're mapping between QAPs and QSPs and "strong" QAPs and QSPs and the bootle language.. 14:44 < andytoshi> ugh the r1cs is actually yet another language 14:44 < andytoshi> and pinocchio seems to be distinct from all of them 14:45 < sipa> ebfull told me they're not splitting the problem in a binary and an arithmetic part 14:45 < andytoshi> yes, i don't see any code that does that in either jsnark or libsnark 14:46 < andytoshi> what is a "root" for a multiplication gate? 14:47 < sipa> interesting: you can XOR 2^n bits together with just n multiplication gates. 14:47 < sipa> just sum them, and binary decompose the output 14:49 < sipa> unfortunately, SHA2 only ever XORs at most 3 values together, and this is only beneficial at 4 14:50 < andytoshi> that's a neat trick tho 14:50 < gmaxwell> there are also other tricks like multiplying N values by a small constant by packing them into a single field element with enough space between them that they can't stomp on each other. 14:52 < gmaxwell> e.g. if you're going to muliply x,y,z which are 32 bits at by q={0,1,2,3} you can (x<<72 + y<<36 + z)*q and unpack. 14:59 < andytoshi> is there an efficient way to unpack though? 15:01 < sipa> nope, 1 multiplication per bit that is potentially nonzero 15:06 < gmaxwell> no but if were going to unpack anyways to do boolean things next, the unpack is free. 15:07 < andytoshi> ah good point 16:00 -!- jtimon [~quassel@41.31.134.37.dynamic.jazztel.es] has joined #secp256k1 21:39 -!- jtimon [~quassel@41.31.134.37.dynamic.jazztel.es] has quit [Ping timeout: 240 seconds] 21:54 < gmaxwell> If someone wants to deal with wrong people on the internet, https://en.wikipedia.org/wiki/Blind_signature#Blind_ECDSA_signatures[4] 21:55 < gmaxwell> someone just stuck a "blind ECDSA" in this WP article that isn't. 21:56 < gmaxwell> it's a schnorr signature, and the artcle claims the construction is secure with such strong assumptions that it makes no mention of the very real parallel signature attack.