--- Day changed Sat Feb 03 2018
02:06 < andytoshi> gmaxwell: i spent some time explaining BPs to waxwing the other day, perhaps he can comment if my way of building them up makes sense
02:07 < andytoshi> though for the inner product proof i still don't have a great idea of how to do it. my intuitive ideas about it were wrong it turns out, based on my series of broken non-power-of-2 extensions
02:08 < gmaxwell> it seems really surprising to me that the non-power-of-two things are so broken.
02:13 < andytoshi> it surprised me, but i think i was just failing to understand why the discrete log problem was important for the proof soundness
02:13 < andytoshi> like i thought all the safety was contained in this a*x + b/x construction
02:15 < andytoshi> like, the way bootle16 did it was to have higher-degree polynomials and a bunch more points at each step, and i thought the extra points were just there to make verification possible at all
02:17 < gmaxwell> I don't really understand the soundness failure. If the extra points are left out, how do you forge a proof?
02:18 < andytoshi> if you leave the points out in bootle16, it won't cause a soundness failure, it will just make verification impossible
02:18 < andytoshi> but the reason they're there at all is that there are extra generators being pulled in at each step
02:18 < andytoshi> which is necessary for sountdness
03:05 < nsh> andytoshi, got logs of that explaination?
03:05 < nsh> -i     
03:10 < andytoshi> nsh: fraid not, i ran into him in person and there was a lot of physical waving of hands and writing in notepads. perhaps he can scan his notes
03:10 < nsh> ah     
03:10 < nsh> no worries :)
03:11 < andytoshi> essentially, there are these two polynomials defined in such a way that (a) the verifier can construct commitments to them just from public inputs, and (b) a specific coefficient of their product will have some specific structure if the prover is being honest
03:12 < andytoshi> then there is a lot of multiplication by hashes and whatnot to make that "if" an "only if"
03:12 < andytoshi> oh, also there is an efficient inner product argument which gets you from (a) to (b), because said polynomials are very large
03:15 < andytoshi> not large in the sense of high-degree, in the rangeproof they're linear and in the general circuit proof they're cubic. but their coefficients are vectors (or more properly, we're dealing with vectors of polynomials, "vector coefficients" isn't a mathematically nice concept) with a lot of entries
03:15 < andytoshi> one entry per bit in the rangeproof case; one entry per multiplication for the circuit proof
05:42 < waxwing> vector-valued polynomials? :)
05:44 < waxwing> nsh, well i for sure haven't understood that much yet, but one thing that i gleaned from andytoshi 's explanation was the role of 'y' and 'z', they come out of FS, so can't be gamed, and they're used as a linearly independent basis to prevent cheating (like <a_L, a_R . y^n> so you can't cleverly choose components to cancel. as i recall it.
05:45 < waxwing> andytoshi, described it as y^n is the 'multiplication gate basis' and z is the 'constraint basis', in the rangeproof the only constraints are the requirement for each a_L element to be a bit, and the other constraint is the <a_L, 2^n> to be equal to v, so the 'z' is used for that second constraint. something like that.
05:50 < nsh> hmm. ty
06:32 < nickler> Regarding BP syllabus for bulletproof: The best introduction I found for proving knowledge soundness and zero knowledge is the latest edition of Boneh's book, chapter 19 and 20 https://crypto.stanford.edu/~dabo/cryptobook/
06:33 < nickler> I also have an annotated version of the proof of protocol 1, but I haven't found a good way to publish and collaboratively edit it yet.
06:37 < waxwing> nickler, sounds great. thanks for the prod on the book; this time i'll actually read it :)
08:52 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Ping timeout: 255 seconds]     
08:58 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1     
12:03 -!- nickler [~nickler@185.12.46.130] has quit [Ping timeout: 240 seconds]     
12:03 -!- nickler [~nickler@185.12.46.130] has joined #secp256k1     
14:06 -!- nickler [~nickler@185.12.46.130] has quit [Ping timeout: 256 seconds]     
14:07 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Ping timeout: 255 seconds]     
14:07 -!- nickler [~nickler@185.12.46.130] has joined #secp256k1     
14:09 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1     
15:03 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Remote host closed the connection]     
15:03 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1     
15:45 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Remote host closed the connection]     
15:46 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1     
16:46 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Remote host closed the connection]     
16:46 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1     
16:51 < maaku> I wonder if any of the NIST SHA-3 finalists admit better arithmetic circuit sizes than SHA2 for validation. Anyone have some insight into that?
16:52 < sipa> blake is better than sha2, i heard from ebfull
16:54 < maaku> Keccak is notably faster than all other finalists and sha2 in hardware implementations (binary circuits), but I have no intuition as to whether that carries over into zkp arithmetic circuits
16:54 < sipa> sha3 is horrible in pure arithmetic circuits
16:54 < sipa> because it uses no integer arithmetic at all
16:54 < maaku> boo     
16:55 < sipa> so you have to operate on each bit individually all the time
16:55 < sipa> and, xor, or ... are all 1 multiplication per bit
16:55 < sipa> not is free if it's done on individual bits
16:57 < sipa> i heard that sha3's sponge operation is 100k multiplication gates
16:57 < sipa> there is a hash function designed for arithmetic circuits, called MiMC
17:08 < maaku> I'm aware, but I'm cautious of deploying something into production with so little cryptographic review vs. a NIST finalist
17:09 < sipa> yup, exactly
17:09 < sipa> you're aware of jubjub?
17:09 < maaku> no, i'm not
17:10 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Remote host closed the connection]     
17:10 < sipa> it's effectively using a pedersen commitment as a hash function
17:10 < sipa> its collision resistance directly derives from DLP
17:10 < gmaxwell> ITS NOT JUBJUB
17:10 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1     
17:10 < sipa> yes, okay
17:10 < sipa> it's the idea that you can construct an elliptic curve inside your arithmetic circuit's field
17:11 < sipa> and having that available lets you use a pedersen commitment over that elliptic curve as an efficiently-provable hash function
17:12 < gmaxwell> one can use a pedersen commitment as a 'hash' function, though the result doesn't have all the properties that we normally expect from a hashfunction (e.g. because the output is a EC point is is distinguishable from uniform).   Sipa keeps calling this jubjub because the zcash people implemented this approach with a curve they call jubjub.
17:13 < sipa> in any case, this can be done with 8 multiplication gates per 3 inout bits
17:13 < maaku> ah ok. i'm familiar with the EC hash scheme
17:13 < sipa> *input bits
17:13 < gmaxwell> For something like a hash tree you don't need properties like output uniformity.
17:13 < maaku> this would be quite a bit slower than a traditional hash function though, right?
17:14 < maaku> outside of a zkp i mean
17:14 < gmaxwell> outside of th... yes.
17:14 < sipa> yes, many times slower
17:14 < gmaxwell> well with huge precomputation it could be made not too horrible I guess.
17:14 < maaku> "many times" might be acceptable, but it seems like it would more like an order of magnitude at least
17:15 < gmaxwell> sipa: what is the speed of ecmult with G only  vs sha2
17:15 < sipa> "many times" is 200 or so
17:15 < gmaxwell> (in libsecp256k1)
17:15 < maaku> yeah ok
17:15 < sipa> even with precomputation
17:15 < gmaxwell> meh you can make it arbitarily close with exponential memory usage! :P
17:15 < sipa> assuming you have O(1) memory access speed
17:15 < gmaxwell> details.
17:15 < sipa> for arvitrarily large memory
17:15 < sipa> no. physics
17:17 < gmaxwell> Is it really 200... IIRC we only do 16 point adds and 128 doublings, using G precomp sizes in libsecp256k1 now.
17:20 < gmaxwell> I suppose that even with costly enough optimization we're still left with the fact that if the comparison point has sha-ni it's totally blown away again.
17:21 < gmaxwell> sipa: I've never much looked into it, but the efficient multiexp algorithims we use are really special cases of more general algorithims that have N outputs.
17:22 < gmaxwell> So, possibly one could construct something to compute N hashes more efficiently than running the single hash function N times.
17:23 < sipa> 200 is the number I get from using a 100000 cpu cycles for EC multiplication with 256-bit input = 3125 cycles per byte
17:23 < sipa> vs naive software implementation of SHA2 which is 15 cycles per byte
17:23 < sipa> with SHA-NI the gap is many times larger
17:23 < gmaxwell> so for example you have [a,b,c,d]G  you first compute multiplies of G that are commonly used by multiple hashes. then reuse those multiples to compute the hashes.
17:29 < gmaxwell> But I expect its similar with multiexp that precomp and fancy techniques largely chase the same gains, and precomp is usually better when you can do ti.
18:04 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has quit [Ping timeout: 240 seconds]     
18:07 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1     
19:24 -!- maaku [~maaku@173.234.25.100] has quit [Ping timeout: 240 seconds]     
19:29 -!- maaku [~maaku@173.234.25.100] has joined #secp256k1     
22:21 -!- GAit [~GAit@unaffiliated/gait] has joined #secp256k1     
22:25 -!- nsh- [~lol@wikipedia/nsh] has joined #secp256k1