--- Day changed Tue Nov 21 2017
00:49 < gmaxwell> this was linked on HN today, on a glance it seems to be mostly things I know about, but looks like some that would be interesting to read https://members.loria.fr/PZimmermann/mca/mca-cup-0.5.9.pdf
03:54 -!- jtimon [~quassel@164.31.134.37.dynamic.jazztel.es] has quit [Ping timeout: 248 seconds]     
04:49 -!- SopaXorzTaker [~SopaXorzT@unaffiliated/sopaxorztaker] has joined #secp256k1     
08:44 -!- jtimon [~quassel@164.31.134.37.dynamic.jazztel.es] has joined #secp256k1     
09:44 -!- hdevalence [~hdevalenc@199-188-193-243.PUBLIC.monkeybrains.net] has joined #secp256k1     
11:05 -!- MrBusiness [~ArcMrBism@2602:306:8325:a300:7820:deca:40bd:c850] has quit [Ping timeout: 240 seconds]     
11:22 -!- SopaXorzTaker [~SopaXorzT@unaffiliated/sopaxorztaker] has quit [Remote host closed the connection]     
13:16 -!- instagibbs [~instagibb@pool-100-15-116-35.washdc.fios.verizon.net] has joined #secp256k1     
13:31 -!- jtimon [~quassel@164.31.134.37.dynamic.jazztel.es] has quit [Ping timeout: 240 seconds]     
14:02 -!- jtimon [~quassel@164.31.134.37.dynamic.jazztel.es] has joined #secp256k1     
14:39 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Ping timeout: 248 seconds]     
14:53 -!- MrBusiness [~ArcMrBism@2602:306:8325:a300:9c21:c44b:240c:ed3] has joined #secp256k1     
15:11 < andytoshi> 1512us to verify a 32-bit bulletproof, vs 150us = 4800us. so 3.17x speedup at 32 bits .... for 64-bits it's 2997us, so 3.2x. (and amusingly a 60% speedup even when comparing a 64-bit bulletproof to a 32-bit rangeproof)
15:12 < andytoshi> this is on the same computer that had better numbers yesterday, presumably because youtube is playing, so as always take these with a grain of salt
15:12 < sipa> \o/     
15:12 < andytoshi> and i still have a few speedups i think i can get
15:13 < sipa> still, a dozen seconds of CPU time to verify a full block of outputs...
15:13 < andytoshi> for example i'm doing two separate scalar inversions, that can be made into one at the expense of some layer violation .. and there are a couple {1, x, x^2, ..., x^63} ladders that i compute backward which i think i can reverse by some rearranging of code
15:15 < andytoshi> https://github.com/apoelstra/secp256k1-mw/tree/bulletproofs if you want to try ... i still haven't written a public wrappen so the benchmark file is reaching into internals, i'll fix that now (might result in a slowdown but i don't think so)
15:15 < sipa> unlikely, at that scale
15:18 < andytoshi> i apologize for how messed up the scalar-computation algorithm is right now, i'll also clean that up to be less insane
15:20 < andytoshi> i wish pedersen commitments were in the generator module rather than the rangeproof module, right now you need both to compile the bulletproofs module
15:20 < gmaxwell> How many commitments does it need to generate?
15:20 < gmaxwell> er generators rather.
15:21 < andytoshi> gmaxwell: right now i'm using 128 fixed generators
15:21 < andytoshi> but in general you need 2N for a N-bit proof
15:22 < gmaxwell> yea, 128 isn't many-- 8192 bytes, so perhaps we could make a bulletproofs generator generator module, and just have 128 of them staticly defined, with an optional fallback to call the generator module to make more or something.
15:23 < andytoshi> yeah, that'd be easy to do. will revisit it when i write the aggregation code
15:23 < gmaxwell> I'm happy it's faster!  though as I sepected it's basically in the same order or magnitude, I was kind of expecting up to 2x slower...
15:23 < gmaxwell> oh right we'll need a lot more for aggregation.
15:24 < andytoshi> yeah, we probably want the ability to maintain a giant cache of generators
15:24 < sipa> soon we'll be talking about kilogenerators and megagenerators
15:24 < andytoshi> lol     
15:25 < sipa> "unfortunately, time travel isn't possible, as we'll need 1.21 gigagen"
15:25 < andytoshi> if we ever had a use for this in a trusted-verifier model we could make all the generators be known (to the verifier) multiples of each other
15:25 < andytoshi> which would make verification screaming fast, the multexp would become a scalar equation
15:25 < andytoshi> essentially
15:27 < gmaxwell> interesting observation. ... thats relevant for the ZKCP sort of usecase...
15:27 < sipa> but the verifier would need to transmit 2*N points to the prover
15:27 < andytoshi> true
15:28 < sipa> and there's no more compact way to do so
15:28 < sipa> so probably only useful when there are many proofs between the prover and verifier
15:28 < andytoshi> yeah
15:28 < gmaxwell> andytoshi: did you end up dropping the optimizations which had potential incompatibilities with arbritary arithmetic circuits?
15:29 < andytoshi> gmaxwell: yes, those did not work out. the things that i did are designed to be compatible with arbitrary circuits
15:30 < andytoshi> though benedikt and i are unsure how much gain they'll get us as ultimately you still have to process the whole circuit so maybe my multiexp-minimization will be overwhelmed by that time
15:32 < gmaxwell> generally time spend manipulating points will dwarf any amount of scalar arithmetic... the only time I've ever seen that fall down is the heap and scalar operations in your boscoster code with really large inputs.
15:32 < andytoshi> oh dammit, i forgot part of the verification equation, that's going to cost us another 5-10% in perf
15:32 < gmaxwell> hah     
15:33 < andytoshi> i should say, i forgot the fixed part of the verification equation, it will add another 5 points to our multiexp regardless of aggregate size
15:33 < andytoshi> and actually, 141 -> 146 points is probably less than a 5% hit
15:33 < sipa> more like 3.5%
15:34 < andytoshi> heh, yeah, even ignoring the advantage that pippenger gets us
15:34 < andytoshi> oh lol, i'm not even using pippenger actually, i'm still working on the strauss code
15:34 < sipa> 146/l(146) / (141/l(141))
15:34 < sipa> 1.02822076835525465753
15:34 < gmaxwell> So interesting question of how much speed can you get by puncturing the thing, e.g. 48 bit rangeproof but keeping the same dimensions in the inner product proof, to avoid having to come up with some weird 3,2 breakdown. 64 bits is excessive for bitcoin, 32 bits is too little to avoid a privacy tradeoff.
15:35 < sipa> 32-bit = up to $350000
15:35 < andytoshi> i haven't explored it yet, but i was hoping that i could do a 48-bit rangeproof as a 64-bit proof where 16 of the 'generators' are actually the identity, so their terms just drop off
15:36 < gmaxwell> 32-bits = doesn't cover A LOT of transaction activity with full precision though; even though it is a lot of money, while 48 bits would cover every txn ever made.
15:36 < sipa> could you get an advantage by instead of using x*(x-1) = 0, use x*x = 0
15:36 < sipa> ?     
15:36 < andytoshi> naively doing that would let somebody put crap in the high bits
15:36 < andytoshi> sipa: ooh, good question
15:37 < andytoshi> pretty sure not, the issue is how much stuff you put into the inner product argument
15:37 < gmaxwell> I wonder what the largest TX out ever created was.  I know there was a ~425k one.
15:38 < andytoshi> so i think we need to ignore the rangeproof and just think about how to extend the inner-product argument to non powers of 2
15:38 < gmaxwell> so that alone would be 46 bits.
15:55 < andytoshi> i think we want to switch x and x^-1 in the inner-product proof, it would make the code a bit simpler
17:13 -!- hdevalence [~hdevalenc@199-188-193-243.PUBLIC.monkeybrains.net] has quit [Quit: hdevalence]     
19:21 -!- jtimon [~quassel@164.31.134.37.dynamic.jazztel.es] has quit [Ping timeout: 248 seconds]     
21:36 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1     
22:57 -!- maaku [~maaku@173.234.25.100] has quit [Quit: ZNC - http://znc.in]     
23:04 -!- maaku [~maaku@173.234.25.100] has joined #secp256k1