--- Log opened Sat Sep 22 00:00:16 2018
00:59 -!- Flyoc5 [~Flyoc@2402:800:6128:5164:6071:1fd9:384a:3b3] has joined #secp256k1
01:05 -!- Flyoc5 [~Flyoc@2402:800:6128:5164:6071:1fd9:384a:3b3] has quit [Ping timeout: 260 seconds]
01:09 -!- GoldenNeko0 [~GoldenNek@host-5-138-94-152.stavropol.ru] has joined #secp256k1
01:11 -!- GoldenNeko0 [~GoldenNek@host-5-138-94-152.stavropol.ru] has quit [Remote host closed the connection]
01:40 -!- lmorchard9 [~lmorchard@110.78.185.212] has joined #secp256k1
01:40 -!- apt4 [~apt@115.73.136.105] has joined #secp256k1
01:42 -!- apt4 [~apt@115.73.136.105] has quit [Remote host closed the connection]
01:47 -!- lmorchard9 [~lmorchard@110.78.185.212] has quit [Ping timeout: 260 seconds]
02:04 -!- zerick5 [~zerick@173.225.246.149] has joined #secp256k1
02:12 -!- zerick5 [~zerick@173.225.246.149] has quit [Ping timeout: 240 seconds]
03:40 -!- lebster29 [~lebster@183.102.48.172] has joined #secp256k1
03:43 -!- lebster29 [~lebster@183.102.48.172] has quit [Remote host closed the connection]
05:15 -!- svliege26 [~svliege@156.218.20.46] has joined #secp256k1
05:15 -!- svliege26 [~svliege@156.218.20.46] has quit [Remote host closed the connection]
06:48 -!- awal24 [~awal@5.34.62.1] has joined #secp256k1
06:49 -!- awal24 [~awal@5.34.62.1] has quit [Remote host closed the connection]
06:54 -!- dastier6 [~dastier@110.77.230.168] has joined #secp256k1
06:55 -!- dastier6 [~dastier@110.77.230.168] has quit [Killed (Sigyn (Spam is off topic on freenode.))]
07:22 -!- darkhorizon16 [~darkhoriz@110.77.171.119] has joined #secp256k1
07:22 -!- darkhorizon16 [~darkhoriz@110.77.171.119] has quit [Remote host closed the connection]
07:48 < andytoshi> roconnor: i don't really want to write a new scratch-space-less precomp. it'd be extremely slow for one because i'd need a ton of field inversions that i couldn't batch (roughly 70ms instead of 20ms by my estimate)
07:49 < andytoshi> but also, there's a meta-problem here that i need this for secp256k1-zkp because it's needed to make borromean signatures on a hardware wallet, but i don't have a good use case for upstream
07:50 < andytoshi> so if i'm producing useless code that doesn't even improve the memory usage of the existing precomp, i don't expect i'll be able to get it in :)
08:02 -!- sharrow23 [~sharrow@190.192.242.195] has joined #secp256k1
08:06 -!- sharrow23 [~sharrow@190.192.242.195] has quit [Remote host closed the connection]
08:23 -!- moondoggy28 [~moondoggy@222.98.8.142] has joined #secp256k1
08:24 -!- moondoggy28 [~moondoggy@222.98.8.142] has quit [Killed (Sigyn (Spam is off topic on freenode.))]
09:04 -!- Lt_Lemming15 [~Lt_Lemmin@190.185.143.210] has joined #secp256k1
09:09 -!- Lt_Lemming15 [~Lt_Lemmin@190.185.143.210] has quit [Ping timeout: 252 seconds]
09:14 -!- benone [~benone@41.236.162.72] has joined #secp256k1
09:19 -!- benone [~benone@41.236.162.72] has quit [Remote host closed the connection]
10:53 -!- dry [~dry@118.176.58.120] has joined #secp256k1
10:57 -!- dry [~dry@118.176.58.120] has quit [Killed (Sigyn (Spam is off topic on freenode.))]
12:25 < andytoshi> i think i've got it. i can change `secp256k1_ecmult_odd_multiples_table` so that on the first pass it stores only `rzr` and `y`, which will fit into a ge_storage, then on the second pass i can use effective-affine trickery to convert this into `x` and `y` ... which will cost one extra fe_mul, fe_neg and fe_add per entry
12:25 < andytoshi> times 16k that's about 500 extra microseconds for precomp on my machine, which i think is a worthwhile tradeoff for eliminating all of the aux memory
13:09 < andytoshi> oh, actually it doesn't even need that. i think this is operation-count-neutral
13:09 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has quit [Remote host closed the connection]
13:10 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has joined #secp256k1
13:35 < gmaxwell> what are you precomping in signing?
13:36 -!- deusexbeer [~deusexbee@080-250-075-036-dynamic-pool-adsl.wbt.ru] has joined #secp256k1
13:37 < andytoshi> gmaxwell: in the borromean proving code, the challenges are computed using secp256k1_ecmult which uses the ecmult_context precomp
13:37 < andytoshi> meanwhile the public keys are computed using secp256k1_ecmult_gen, so actually both precomp tables are used
13:38 < gmaxwell> Ok. so on embedded devices flash is almost always vastly more available than ram, so usuall for a _gen table you just want it static, not computed on the fly.
13:39 < andytoshi> true, so maybe eliminating scratch memory there is not a big deal .. but it wasn't hard to do and it will make the "preallocated slab" API cleaner
13:49 < gmaxwell> yea, I don't see any problem in reducing the memory usage. Just wanting to make sure you're not spinning your wheels on the wrong optimizations.
13:49 < gmaxwell> For ecmult_context you obviously can't make that static.
13:50 < andytoshi> right
13:50 < andytoshi> it's not 100% clear that i _need_ it .. we could use ecmult_const in the borromean proving code in principle. but i think that would get prohibitively slow pretty quickly
13:52 < gmaxwell> I think the approached used in dettman's PR for secp256k1_ecmult uses less memory for a given level of performance.
13:52 < gmaxwell> like half or something like that?
13:52 < andytoshi> which PR?
13:53 < gmaxwell> andytoshi: https://github.com/bitcoin-core/secp256k1/pull/546
13:53 < andytoshi> oh right!
13:54 < gmaxwell> actually it appears to use 32x less memory.
13:54 < gmaxwell> per his table.
13:54 < gmaxwell> (though his figures probably aren't peak memory)
14:07 < andytoshi> that's incredible
14:07 < andytoshi> i'll try to review that tonight once i'm done this
14:07 < andytoshi> (i'm close. i've generated almost all the points correctly now, or at least my sage spot-checks are working, so i'm confident that my algorithm works. i think i have some indexing bug somewhere.)
14:12 < gmaxwell> yea, compared to our current stuff, its not exciting... but on embedded it's a big win.
14:38 < andytoshi> done. hacked in a context_create benchmark and confirmed that the times are identical before and after my changes
14:43 < andytoshi> https://github.com/bitcoin-core/secp256k1/pull/557
14:58 < gmaxwell> Sweet another PR to sit open unmerged for a year
14:59 < gmaxwell> andytoshi: will reiew!
15:00 < gmaxwell> er review.
15:40 < andytoshi> hehehe
15:40 < andytoshi> thanks :)
15:56 -!- LeadGuit17 [~LeadGuit@110.78.148.173] has joined #secp256k1
15:57 -!- LeadGuit17 [~LeadGuit@110.78.148.173] has quit [Killed (Unit193 (Spam is not permitted on freenode.))]
16:04 < gmaxwell> man dettman's change is really a lot more improvement for small tables than I'd thought.
16:51 < andytoshi> i've read the paper and it's really not intuitive to me why this would be such a big improvement
16:51 < andytoshi> it feels like precomputing an arbitrary pile of things and then adding them up :P
16:52 < andytoshi> and i don't see how different piles of the same size could have drastically different performance characteristics
16:53 < TD-Linux> oh that's very nice. makes me want to retry libsecp on cc65
16:56 < gmaxwell> andytoshi: because it can use the entries more, because it can use negations on the interior sums.
16:58 < andytoshi> oh, yeah, i see
16:58 < andytoshi> kinda. we alse used negations in our "odd signed digits" precomp
16:59 < gmaxwell> sure, this can use more of them.  like each table gets reused at multiple scales.
17:00 < gmaxwell> so you effectively don't just get use of each table entry and its negation, but 2x each entry and its negation, 4x each entry and its negation, etc.
17:00 < andytoshi> ah!
17:00 < andytoshi> ok, and if you put the tooth spacing to 1 it'd be kinda like our algorithm
17:01 < andytoshi> and you'd lose that ability
17:01 < gmaxwell> yes. thats how I understand it.
17:01 < andytoshi> thanks. that clicked for me
17:36 < nsh> neat
17:38 < nsh> quite a paper...
17:41 < nsh> "In  essence,  they  compute  a  suitable generator of the lattice containing the logarithms of the desired results, quotiented by the lattice of the logarithms of the inputs."
17:41 < nsh> that sounds awfully clever
17:47 -!- jchia24 [~jchia@177.11.47.246] has joined #secp256k1
17:48 -!- jchia24 [~jchia@177.11.47.246] has quit [Remote host closed the connection]
17:55 -!- havok88 [~havok88@41.235.60.192] has joined #secp256k1
18:01 -!- havok88 [~havok88@41.235.60.192] has quit [Ping timeout: 252 seconds]
18:34 -!- meingtsla15 [~meingtsla@190-207-145-116.dyn.dsl.cantv.net] has joined #secp256k1
18:37 -!- meingtsla15 [~meingtsla@190-207-145-116.dyn.dsl.cantv.net] has quit [Remote host closed the connection]
19:53 -!- hmir [~hmir@187.20.117.169] has joined #secp256k1
19:54 -!- hmir [~hmir@187.20.117.169] has quit [K-Lined]
19:59 -!- vasco-santos16 [~vasco-san@5.166.142.75] has joined #secp256k1
20:02 -!- vasco-santos16 [~vasco-san@5.166.142.75] has quit [Remote host closed the connection]
20:29 -!- WorMzy5 [~WorMzy@210.105.208.120] has joined #secp256k1
20:31 -!- WorMzy5 [~WorMzy@210.105.208.120] has quit [Remote host closed the connection]
20:37 -!- bspar14 [~bspar@190-201-169-113.dyn.dsl.cantv.net] has joined #secp256k1
20:37 -!- bspar14 [~bspar@190-201-169-113.dyn.dsl.cantv.net] has quit [Remote host closed the connection]
23:42 -!- scivola11 [~scivola@cm-84.212.151.142.getinternet.no] has joined #secp256k1
23:43 -!- scivola11 [~scivola@cm-84.212.151.142.getinternet.no] has quit [Remote host closed the connection]
--- Log closed Sun Sep 23 00:00:17 2018