--- Log opened Mon Jun 21 00:00:44 2021 01:45 -!- luke-jr [~luke-jr@user/luke-jr] has quit [Quit: ZNC - http://znc.sourceforge.net] 01:46 -!- luke-jr [~luke-jr@user/luke-jr] has joined #secp256k1 02:07 -!- belcher_ is now known as belcher 02:58 < real_or_random> gmaxwell: makes sense 07:07 -!- kittywhiskers [~kittywhis@user/kittywhiskers] has quit [Quit: kittywhiskers] 08:06 -!- luke-jr [~luke-jr@user/luke-jr] has quit [Quit: ZNC - http://znc.sourceforge.net] 08:08 -!- luke-jr [~luke-jr@user/luke-jr] has joined #secp256k1 09:01 -!- jessepos_ [~jesse@2601:647:0:89:6de9:9aa6:8bb7:1691] has quit [Quit: Textual IRC Client: www.textualapp.com] 09:02 -!- jesseposner [~jesse@2601:647:0:89:6de9:9aa6:8bb7:1691] has joined #secp256k1 10:13 < BlueMatt> mmmm, those optimizations in the past few months are nice sending a few lightning payments back and forth from 8,963,014 ns/iter (+/- 1,257,844) to 6,683,291 ns/iter (+/- 1,158,284) 10:18 < gmaxwell> wow, 34% ... signing must be on a latency critical path? 10:19 < gmaxwell> You can make signing a fair amount faster using some existing other PRs, and you can also make it infinity less latent with a small amount of coding. 10:21 < BlueMatt> its basically 100% sign + verify 10:21 < sipa> with precomputed nonces signing could be reduced to a fraction of the time, though it is footgunny 10:22 < BlueMatt> like, a generates signature(s), sends to b, b verifies them and generates its own, then responds with new signatures then...... 10:22 < BlueMatt> eh, its less critical then it sounds (despite being *the* thing a lightning node does), its a super synthetic benchmark, really, cause you normally pause a bit before forwarding things. 10:26 < BlueMatt> sipa: by "precomputed nonces signing" do you mean having a precomputed nonce like hashing it and not doing the fancy hashing rfc that hashes too many times, or do you mean like just using a random value? 10:26 < BlueMatt> or is there some special nonce construction that makes signing faster? 10:27 < gmaxwell> BlueMatt: if you don't mind using random numbers for nonces (not rfc1918) you can compute the nonces in advance and signing will take less than 1 microsecond. All the time in signing is computation on the nonce value alone. 10:28 < BlueMatt> how much of that gain can you also get by just replacing rfc1918 by a simpler hmac? 10:28 < BlueMatt> (iirc its somewhat needlessly complicated and hashes more than it strictly needs to?) 10:28 < sipa> a few % 10:29 < sipa> rfc6979 is gratuitously slow 10:29 < sipa> but it's still only a few % compared to the time to compute the R point 10:29 < gmaxwell> (well really less that 0.05 microseconds) 10:29 < BlueMatt> ah, ok 10:30 < BlueMatt> yea, I dunno if I'm gonna do the work to construct Rs and store them in the context for later use :p 10:30 < gmaxwell> yeah you can replace 6979 with a faster thing and get a few speedup. There is also a PR that speeds up signing a bit. 10:30 < sipa> in particular https://github.com/bitcoin-core/secp256k1/pull/693 should speed up signing 10:31 < BlueMatt> cool. well I'll wait for it to land, I just mostly wanted to provide an interesting datapoint on the real-world speedup in a real-world-but-super-secp-bound benchmark :) 10:31 < gmaxwell> But if you precompute random rs and store R,1/k in a table and have code that will not allow you to reuse nonces (e.g. guarentees it deletes them as it uses them), then you can make signing run basically as fast as memcpy. :P 10:31 < gmaxwell> BlueMatt: well it's probably the case that in rust you could make this construct safe, while in other languages it would be more fragile. 10:32 < BlueMatt> right, it would be some amount of effort, but, yes, you could use the language features to make it safe without relying on a mutex. 10:32 < gmaxwell> BlueMatt: beyond latency this construct would also just be faster in total. 10:32 < BlueMatt> by creating multiple R,1/k's at once? 10:32 < gmaxwell> (because you can generate nonces faster in batches... though that speedup would be less significant now post safegcd) 10:32 < BlueMatt> right 10:33 < sipa> is this ecdsa or schnorr? 10:33 < BlueMatt> ecdsa, for now 10:33 < BlueMatt> post-taproot will be schnorr :) 10:33 < gmaxwell> BlueMatt: yeah because there are three modular inverses (two field, one scalar) which can be batched. 10:34 < sipa> 3? 10:34 < sipa> i thought there was once inverse in each signing operation 10:34 < sipa> *one 10:34 < gmaxwell> sipa: r has to be converted to affine. 10:35 < sipa> that's still only 1 field inverse and 1 scalar inverse? 10:35 < gmaxwell> oh right you don't need r.y. It's 1 field and 1 scalar. 10:40 < gmaxwell> BlueMatt: might be interesting to run a realistic benchmark (e.g. with a network delay) which has all the verify operations rigged to take normal time but pass, and all the signing operations just spit out a static signature. 10:41 < BlueMatt> gmaxwell: I think the bigger reason why its not realistic is that lightning nodes generally batch commitment updates, so instead of just having everything be sig-time-bound its more like 1 second + bunch of signatures. the constant would likely dominate up to a rather large number of payments 10:41 < BlueMatt> (oh, and each update requires at least one fsync, soooooooo) 10:43 < BlueMatt> of course "at scale" you could imagine a very consistent flow of payment forwards such that you are concerned about the total throughput of secp operations, and its actually not even a crazy number, if you imagine a server-grade nvme (where fsync is ~free) and people doing shit like the podcast streaming payments stuff. 10:44 < BlueMatt> the numbers above, iirc, are two nodes with A sending B a payment and then B claiming said payment, then B sending A a payment and A claiming said payment. 10:44 < BlueMatt> (without fsyncs) 10:44 < BlueMatt> so, speeding up the secp parts *is* on the table in the future, but its not critical with today's payment flows 10:47 < gmaxwell> yeah before you comments above I assumed fsync and network latency were so large that secp256k1 performance was irrelevant. 10:53 < BlueMatt> true today, but you could imagine a "big" routing node with ram-backed nvme and such where it matters. 10:53 < BlueMatt> at least in the future, maybe not today 11:04 < roconnor> I haven't finished jonas's video, but does the Schnorr proof need the hash to be 256 bit? Maybe the answer is different between the ROM proof and the AGM proof. 11:09 < sipa> roconnor: http://neven.org/papers/schnorr.pdf section 7 11:11 < roconnor> so it would indeed be faster to set compute R from a short 128-bit scalar. 11:11 < roconnor> (pre-compute R) 11:12 < roconnor> well pre-compute or compute R. 11:12 < sipa> perhaps some of those results are outdated, but it suggests that with the traditional ROM proof for Schnorr you need 384-bit groups and 128-bit hashes for 128-bit security, but with their GGM proof you only need 256-bit groups and 256-bit hashes 11:15 < sipa> roconnor: R from a short 128-bit scalar? that sounds vulnerable to lattice attacks 11:15 < gmaxwell> oh dear no you absolutely cannot use an R shortened in any way. 11:16 < roconnor> not a short R a short generator for R. ... but okay I mixed up my hashing. 11:16 < gmaxwell> There is a shortned schnorr that shortens H but it's vulnerable under a different attack model than is normally considered, one the attacker knows the private key and tries to make a single signature that works for two messages. 11:16 < sipa> unsure what you mean by short generator; but if you mean an R for which 0 <= DL(R) < 2**128, that's absolutely broken 11:17 < roconnor> okay, yes that was my intended question, even though I said it all wrong. 11:18 < sipa> in non-EC schnorr it was common to use the (e,s) variant, because sending the hash e is smaller than sending a multiplicative group element (which needs to be many times larger than the hash for its security model) 11:25 < roconnor> sounds like shrinking the hash would have made schnorr signatures faster to verify, but not faster to batch-verify. 11:28 < sipa> right 12:55 -!- luke-jr [~luke-jr@user/luke-jr] has quit [Quit: ZNC - http://znc.sourceforge.net] 12:57 -!- luke-jr [~luke-jr@user/luke-jr] has joined #secp256k1 13:12 < gmaxwell> BlueMatt: if you do come to the conclusion that low latency signing would speed lightning up a lot, I'd be glad to help you with it. I had an implementation somewhere, I just don't really consider it publishable because it's hard to make safe enough, esp without an application that really needs it. 13:13 < BlueMatt> yea, I'll let you know. I kinda doubt its gonna be a "this year" kinda thing, but it definitely may end up being the case eventually 13:13 < gmaxwell> (though it would be pretty nice if the secp256k1 nonce function api supported the right interface, so it would just be a custom nonce function. 13:13 < gmaxwell> ) 13:30 < sipa> with Schnorr signatures you can pretty easily do it as a hack on top, that just "malleates" an existing signature into beibg for another message 13:31 < sipa> create a random messsge, sign it, then at real signing time add (e1-e1)*privkey 13:32 < gmaxwell> I dunno that this is any better. :P 13:33 < sipa> for ecdsa you can'g do that, as you need k^-1 13:34 < sipa> yeah, not actually recommending this! 13:36 < gmaxwell> I'd just wright a seperate fastsign module, but dealing with portably preventing reuse is hard. Ideally you'd want to do the same kind of things done for CSPRNG states for preventing copying/fork. And you'd want access to an RNG inside it. 13:36 < gmaxwell> write lol 13:36 < sipa> ... wringht? 13:36 < sipa> wright? 13:36 < sipa> haha, jinx 13:43 < real_or_random> I think we should really offer a builtin function which is faster than RFC6979 13:43 < real_or_random> maybe similar to the one in BIP340 13:43 < gmaxwell> Or just use BIP340 if you care about speed. :P 13:44 < real_or_random> yeah sure 13:44 < sipa> as long as it's not *exactly* bip340 13:45 < sipa> (different algo is fine) 13:45 < real_or_random> it's faster in the long term but you'll have an initial latency of 5 months if you start using BIP340 now :P 13:45 < gmaxwell> Well that is another reason to offer one explicitly too-- to reduce the odds someone uses the bip340 one. 13:46 < real_or_random> gmaxwell: indeed but the interface is different at least 13:46 < real_or_random> because the BIP340 takes a pubkey 13:46 < sipa> indeed 13:46 < real_or_random> I remember I suggested unifying the interface but it seemed difficult. (maybe it's a bad idea even then) 13:48 < gmaxwell> well bad idea for this example. 13:49 < gmaxwell> If the interface was low latency compatible it would return kinv and R.x rather than k. 17:07 -!- belcher_ [~belcher@user/belcher] has joined #secp256k1 17:10 -!- belcher [~belcher@user/belcher] has quit [Ping timeout: 258 seconds] --- Log closed Tue Jun 22 00:00:45 2021