--- Day changed Tue Nov 19 2019 01:27 -!- jonatack [~jon@2a01:e35:8aba:8220:6627:dad:d967:649d] has quit [Ping timeout: 276 seconds] 02:02 -!- jonatack [~jon@abayonne-654-1-191-177.w92-134.abo.wanadoo.fr] has joined ##taproot-bip-review 02:11 -!- jonatack [~jon@abayonne-654-1-191-177.w92-134.abo.wanadoo.fr] has quit [Ping timeout: 240 seconds] 02:13 -!- jonatack [~jon@109.232.227.138] has joined ##taproot-bip-review 02:51 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has quit [Remote host closed the connection] 02:52 < waxwing> i finished this over the weekend, about what wagner's algorithm/attack is, it occurs to me that the few people that may be interested are likely to be here :) https://joinmarket.me/blog/blog/avoiding-wagnerian-tragedies/ 02:56 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has joined ##taproot-bip-review 03:15 -!- ZmnSCPxj_ [~ZmnSCPxj@180.190.33.230] has joined ##taproot-bip-review 03:28 -!- Chris_Stewart_5 [~chris@unaffiliated/chris-stewart-5/x-3612383] has joined ##taproot-bip-review 03:28 < jonatack> waxwing: ty :) 03:35 -!- jonatack [~jon@109.232.227.138] has quit [Ping timeout: 250 seconds] 03:39 -!- andytoshi [~apoelstra@unaffiliated/andytoshi] has joined ##taproot-bip-review 05:01 -!- HighOnBtc [~Admin@86.121.55.235] has joined ##taproot-bip-review 06:15 -!- pyskell [~pyskell@unaffiliated/pyskell] has joined ##taproot-bip-review 06:19 -!- rottensox [~rottensox@unaffiliated/rottensox] has joined ##taproot-bip-review 07:13 -!- andytoshi [~apoelstra@unaffiliated/andytoshi] has quit [Ping timeout: 245 seconds] 07:59 -!- davterra [~dulyNoded@195.242.213.120] has joined ##taproot-bip-review 08:22 -!- Guest61_ [~textual@91.240.140.128] has joined ##taproot-bip-review 08:25 -!- Guest61 [~textual@91.240.140.128] has quit [Ping timeout: 240 seconds] 08:33 -!- Guest61 [~textual@91.240.140.128] has joined ##taproot-bip-review 08:36 -!- Guest61_ [~textual@91.240.140.128] has quit [Ping timeout: 265 seconds] 08:59 < waxwing> " A product of two numbers is a square when either both or none of the factors are squares." i must be dumb i don't get it .. a product of two not square factors isn't always a square (i.e the "none" case), like 3x7 is not a square even though both factors are not squares. 09:10 < waxwing> i think it's a statement correct modulo p, isn't that it? 09:11 < waxwing> oh and distinguishes when p=3 mod 4 vs 1 mod 4 according to wiki, because of the difference of whether -1 is a square or not. 09:14 < sipa> waxwing: yeah, modulo a prime this is correct 09:14 < sipa> (it's even true when -1 is a square) 09:16 < waxwing> right that specific sentence, true 09:20 < sipa> put otherwise: this follows from the legendre symbol being a completely multiplicative function 09:20 < sipa> maybe we should add "modulo a prime" to that sentence? 09:21 < sipa> i think this became confused when we changed the "quadratic residue" terminology for "square" 09:21 < waxwing> i think so yes. 09:22 < waxwing> yes quadratic residue is particularly unfortunate, but hard to argue with Gauss :) 09:22 < sipa> it's all Square's fault 09:23 < waxwing> lol. reminds me i always say Gaussian not normal because let's face it the former is just cool sounding. 09:24 < sipa> "standard normal" is even worse 09:24 < sipa> how boring a name can you come up with 09:25 < waxwing> i note you correctly say this is a new standard but it might be worth adding a footnote about how it's also widely used in slightly different forms, like what is it EDDSA is basically a Schnorr variant. 09:26 < waxwing> probably there are others but meh it's only a suggestion no need to go overboard. i just have occasionally encountered people thinking this is a new untried piece of cryptography, which is pretty far from accurate really. 09:26 < sipa> yup, worth citing 09:26 < sipa> even the hash(R || P || m) argument order matches eddsa 09:27 < waxwing> oh, right, presumably we will now bikeshed that for the next hour or two :) 09:27 < sipa> i prebikeshedded it with real_or_random already 09:28 < waxwing> yeah i saw that. kinda interesting discussion, maybe i'll link it here 09:29 < waxwing> cancel that i have no idea where i read it, now. 09:39 -!- andrewtoth [~andrewtot@gateway/tor-sasl/andrewtoth] has joined ##taproot-bip-review 10:15 <@aj> waxwing: https://github.com/sipa/bips/pull/62 ? 10:18 < sipa> that's it 10:50 < moneyball> 10 minutes until Q&A! 10:50 < sipa> i'll be 5-10 minutes late 10:52 -!- pyskell [~pyskell@unaffiliated/pyskell] has quit [Quit: Leaving] 10:58 -!- Moller40 [~mr@82.103.130.152] has joined ##taproot-bip-review 11:00 <@aj> #startmeeting 11:00 < lightningbot> Meeting started Tue Nov 19 19:00:22 2019 UTC. The chair is aj. Information about MeetBot at http://wiki.debian.org/MeetBot. 11:00 < lightningbot> Useful Commands: #action #agreed #help #info #idea #link #topic. 11:00 < kabaum> Hi 11:00 < amiti> hi 11:00 < moneyball> hi 11:00 < nickler> hi 11:00 < nothingmuch> hi 11:00 <@aj> hi 11:01 < kabaum> It's only me from group 5 here today, so my questions are not filtered through our pre-Q&A-meeting. 11:01 < fanquake> hi 11:02 < kabaum> Q 1/3: Why isn't implicit Y a reduction in security? I don't get the explanation given in last paragraph of "Implicit Y coordinates" or in footnote 6. Is it so that given a privkey q for a pubkey P with explicit Y, one can easily calculate the privkey p' for the pubkey -P? 11:03 < sipa> kanzure: https://medium.com/blockstream/reducing-bitcoin-transaction-sizes-with-x-only-pubkeys-f86476af05d7 11:03 < sipa> eh, kabaum ^ 11:03 < fjahr> hi 11:04 < sipa> kabaum: also https://bitcoin.stackexchange.com/a/90120/208 11:04 < nickler> kabaum: but basically yes. Inverting the public key is just computing the negation of a 256 bit number (the y coordinate) so that's very easy. 11:04 < kanzure> hi 11:05 -!- pglazman [~pglazman@205.209.24.227] has joined ##taproot-bip-review 11:05 < sipa> nickler: you keep bringing that up as argument, but i don't think that's relevant 11:05 < sipa> even if it cost an EC multiplication to do so, x-only would still not be a reduction in security 11:06 -!- willcl_ark [~quassel@cpc123762-trow7-2-0-cust7.18-1.cable.virginm.net] has quit [Quit: Quit] 11:07 < nickler> still I want to point out that a third party can easily do that, no access to the secret key is required 11:07 < sipa> right 11:08 < kabaum> sipa: Got it. The stackexchange answer helped. 11:08 < nothingmuch> Q: both e and R style signatures seem to be rationalizable appealing to orphan rates, network latency for the former, validation cpu cost for the latter, but it's not clear how to compare these. what is the argument for favoring R and batch verification, especially on a longer time horizon? is it empirical? 11:09 < sipa> kabaum: another way to look at it: the fact that you can negate a public key (which negates the corresponding private key) is indeed going to help an attacker... but it *always* does that, whether public keys are x-only or full x/y 11:09 < kabaum> sipa: thanks. 11:10 < sipa> kabaum: FWIW, secp256k1 has another "efficiently computable endomorphism" (which is what this negation gives you), namely multiplication with a specific constant lambda... which also always helps an attacker 11:10 < nickler> nothingmuch: the argument is that batch verification is a significant speedup. It's empirical in the sense that we've implemented and measured it (that's the graph in the bip) 11:12 < sipa> kabaum: the expected number of EC additions an attacker needs to do with a DLP breaking algorithm is proportional to sqrt(p/m) where p is the largest prime factor of the group order, and m is the number of efficiently computable endomorphism (m=6 for secp256k1, but the efficient negation is part of it) 11:14 < sipa> nothingmuch: the "be made as small as 16 bytes" should probably get a qualifier "in some security models" 11:17 < kabaum> nickler: My next Q is related to nickler's answer. 11:17 < kabaum> Q 2/3: Is the graph "Batch signature verification in libsecp256k1" made using the bip-schnorr scheme or using some other/generic Schnorr scheme? 11:19 < nickler> kabaum: it's the bip-schnorr implementation in libsecp 11:19 -!- willcl_ark [~quassel@cpc123762-trow7-2-0-cust7.18-1.cable.virginm.net] has joined ##taproot-bip-review 11:19 < nickler> this one https://github.com/bitcoin-core/secp256k1/pull/558 11:20 <@aj> nickler: well, it's from a pre-x-only version of that PR, right? 11:20 < sipa> here is a graph that's based on more lowlevel benchmarking: http://bitcoin.sipa.be/speedup-batch.png 11:20 < sipa> which only takes the multi-exp into account and not the other overhead of verifying a signature 11:20 < nickler> aj: right, but it shouldn't make a visible difference 11:21 < nickler> but I should try to reproduce the numbers just to be sure :) 11:22 < nickler> perhaps s/I/someone to reduce systematic bias 11:22 < kabaum> nickler: that'd be interesting. 11:22 < kabaum> Q 3/3: Why is batch verification of u signatures more efficient than verifying them separately? I counted the number of point multiplications and additions. For individual verification I get 2u mult and u add. For batch I get 2u mult and 2u-1 add. Also the amount of hashing seems similar in batch and separate verification. What am I missing? 11:22 < sipa> kabaum: Strauss' algorithm 11:23 < sipa> (and for larger numbers, Pippenger's algorithm) 11:23 < sipa> it turns out that x*A + y*B can actually be computed more efficiently in one go than computing (x*A) and (y*B) separately and adding them up 11:24 -!- Moller40_ [~mr@82.103.130.152] has joined ##taproot-bip-review 11:25 < sipa> kabaum: very broadly, the number of EC additions you need to do to implement n EC multiplications grows with n/log(n), rather than n 11:25 < sipa> (if you only care about their sum) 11:27 < nickler> kabaum: https://cdn.preterhuman.net/texts/cryptography/Hankerson,%20Menezes,%20Vanstone.%20Guide%20to%20elliptic%20curve%20cryptography%20(Springer,%202004)(ISBN%20038795273X)(332s)_CsCr_.pdf section 3.3.3 11:27 < sipa> i can try to give an intuition for that here too, if there are no other questions 11:27 < nickler> "Guide to Elliptic Curve Cryptography" by Hankersen, Menezes, Vanstone 11:27 -!- Moller40 [~mr@82.103.130.152] has quit [Ping timeout: 250 seconds] 11:28 < kabaum> sipe: I'd love that. 11:29 < kabaum> nickler: Strauss isn't mentioned in that document. 11:29 < nothingmuch> i jumped the gun with my question, but it's still outstanding, but an intuition for batch verification seems relevant to it anyway 11:29 < sipa> imagine you're trying to compute 19*P 11:30 < nickler> kabaum: section 3.3.3 11:30 < sipa> one way to do that is to compute 2P = P+P, 4P = 2P+2P, 8P = 4P+4P, 16=8P+8P, and then sum P+2P+16P 11:30 < nickler> they don't call it strauss but shamir's trick 11:30 < sipa> right? 11:30 -!- Moller40_ [~mr@82.103.130.152] has quit [Ping timeout: 240 seconds] 11:31 < kabaum> yes! 11:31 < waxwing> key prefixing means we lose the pubkey recovery property, right? 11:32 < sipa> waxwing: correct 11:32 < waxwing> how do we feel about that. 11:32 < sipa> i think key aggregation is more important that pubkey recovery 11:32 < waxwing> oh i see it's in footnote 3 11:33 < sipa> kabaum: so you're doing 4 doublings (because the largest power of two is 16P), and then 1 addition for every 1-bit in the binary representation of 16 11:34 < sipa> but say you want to compute 19P + 23Q, you're just going to do twice the amount of work now (two times 4 doublings, and an addition for every 1 bit in 19 and 23) 11:34 < sipa> agree? 11:34 < kabaum> Agree! 11:35 < sipa> so that's not a good approach 11:35 <@aj> waxwing: you can do pubkey recovery with partial sigs with the same construction though; claim the complete key is P+-P+G, so you're going for sG=R+H(R,G,m)*G and calculate a partial signature s1,R1 s1*G = R + H(R,G,m)*P and P is recoverable 11:36 -!- Moller40 [~mr@82.103.130.249] has joined ##taproot-bip-review 11:36 < sipa> kabaum: an alternative is working backwards: write 19 as 11001 in binary, and compute it as dbl(dbl(dbl(dbl(P)))+P)+P) 11:36 < sipa> this is the exact same number of additions/doublings 11:37 < sipa> but instead of precomputing all power-of-two's times P first, and then adding them up, you use an "accumulator" that you add P into every time a "1" bit is encountered, and you double for every bit 11:37 < waxwing> aj, hmm interesting, that's confusing, so you're talking about like a multisig scenario? but would that work with musig? 11:37 < sipa> this is actually the same algorithm as https://en.wikipedia.org/wiki/Exponentiation_by_squaring, expect addition/doubling instead of multiply/square 11:38 < kabaum> sipa: did you write 19 backwards in binary? 11:38 < sipa> kabaum, nothingmuch: does this make sense? 11:38 < sipa> no 11:38 <@aj> waxwing: just abusing the api needed for partial sigs to allow for a protocol that wants pubkey recovery 11:38 < sipa> kabaum: maybe it's easier to see if i write it as dbl(dbl(dbl(dbl(0+P)))+P)+P) 11:38 < waxwing> aj, i guess it depends on what situation you want to do pubkey recovery .. the one i was made aware of was people working in a constrained environment wanting to transfer without being explicit about a key. 11:38 < waxwing> constrained as in something like mesh network. 11:39 < sipa> kabaum: oh, i'm confusing myself! 11:40 < sipa> it's dbl(dbl(dbl(dbl(0+P)+P)))+P 11:40 < sipa> the outer bits (11) become the inner part 11:40 < sipa> maybe IRC isn't the best medium for this 11:40 < nothingmuch> sipa: roughly makes sense to me but i doubt i will fully comprehend this here, i'm slow on the uptake and probably need to work it out on paper 11:40 < sipa> nothingmuch: i'm just giving background, i haven't explained it yet :) 11:41 < waxwing> there is a trailing ) on the last bullet point of "Default Signing" 11:41 < kabaum> Oh, it's 0x19, got that. Now I'm way behind you.... Catching up. 11:41 < sipa> kabaum: no, 19 = 16 + 8 + 1 11:41 < sipa> eh, 16 + 2 + 1 11:41 < sipa> i need a whiteboard :) 11:42 < waxwing> cancel that there is not a trailing ) . doh. 11:44 < sipa> kabaum: the number in binary is 10011 * P 11:44 < sipa> start with 0P = 0 11:44 < sipa> you see a 1 bit (the one in front), so you add P, and get 1P 11:44 < sipa> you double, and get 2P 11:44 < nickler> aj: fwiw the libsecp-zkp musig api wouldn't let you do that. Also, not committing to the pubkey allowsa an attacker to tweak the signature to be valid for another bip32 derived key 11:44 < sipa> you see a 0 bit, so don't do anything 11:44 < sipa> you double, and get 4P 11:44 < sipa> you see a 0 bit, so don't do anything 11:44 < sipa> you double, and get 8P 11:45 < sipa> you see a 1 bit, so you add P, and get 9P 11:45 < sipa> you double, and get 18P 11:45 < sipa> you see a 1 bit, so you add P, and get 19P 11:45 < sipa> done. 11:45 -!- rottensox [~rottensox@unaffiliated/rottensox] has quit [Quit: Bye] 11:45 < sipa> does this make sense? 11:46 < waxwing> nickler, yeah i haven't figured it out, as you have, but makes sense that that is not compatible with musig, as it's kind of a related key attack thing. 11:46 <@aj> nickler: that means the api only does musig, not simple pubkey addition (with knowledge of discrete log) right? 11:47 < waxwing> aj, so you're basically arguing for people to still use base bip schnorr but have their own protocols (not in bitcoin itself, per se) that could do that kind of stuff? 11:47 < nothingmuch> sipa: so then to do both, it's just adding Q or P based on whether their respective bits are set into the same accumulator, and doubling once? 11:47 < nickler> well in our musig api you have the concept of a session which keeps your nonce, others nonces and your secret key. If you call partial sig it will use mostly session information 11:47 < sipa> nothingmuch: exactly! 11:47 < sipa> and what did you gain? 11:47 <@aj> waxwing: that it's conceivable yeah, not necessarily a good idea :) 11:47 < waxwing> :) 11:50 < kabaum> sipa: Didn't you just describe normal "adding and doubling" method? 11:50 < sipa> kabaum: yes indeed 11:50 < kabaum> ok, then I follow. 11:51 < sipa> so the next step is what nothingmuch said: if you want to compute say 19P + 25Q, where 19 is 10011 in binary, and 25 is 11001, you can merge the two computations 11:51 < sipa> you start with 0P+0Q = 0 11:51 < sipa> you see a 1 bit in both, so you add P and Q, and 1P+1Q 11:52 < sipa> you double, and get 2P+2Q 11:52 < sipa> you see a 1 bit in 25, so you add Q, and get 2P+3Q 11:52 < sipa> you double, and get 4P+6Q 11:52 < sipa> you see 0 bits in both and do nothing 11:53 < sipa> you double, and get 8P+12Q 11:53 < sipa> you see 1 bit in 19, so you add P, and 9P+12Q 11:53 < sipa> you double, and get 18P+24Q 11:53 < sipa> you see a 1 bit in both, you add P+Q, and get 18P+25Q 11:53 < sipa> *19P+25Q 11:54 < sipa> and in doing so, you've only doubled 4 times, not 8 times 11:56 < waxwing> i see you specify deterministic nonces but a very much simpler form than rfc6979 .. perhaps mention the latter in footnote 10? 11:57 < waxwing> debatable since it's not like rfc6979 was actually part of a bitcoin standard/bip before iirc 11:57 < sipa> we all like 289264 invocation of the SHA256 compression functions to compute a nonce 11:57 -!- Moller40_ [~mr@46.246.1.163] has joined ##taproot-bip-review 11:58 < waxwing> also that bias being small is cool but maybe it would be nice to cite something. i remember 1 bit biases in nonces have been enough in theory before (lattice stuff) 11:58 < sipa> waxwing: they are 11:58 < waxwing> 6979 was kinda hard. but i mean ... Pornin is the man. 11:59 < sipa> it's a 0.0000000000000000000000000000000000000058 bit bias here 11:59 < waxwing> ah right yeah, thought i might have made that error :) 11:59 < sipa> i think we have a comment somewhere that the bias is unobservable 11:59 < waxwing> wait was it really 300K? lol 12:00 < kabaum> sipa: I got it! Thanks! You really made it simple. 12:00 < sipa> waxwing: no, more like 15 12:00 < sipa> waxwing: still, it's actually a nontrivial portion of the signing time 12:00 < waxwing> yeah you have that comment in 10 it's fine. and no need to comment rfc6979 i think. 12:00 < waxwing> i see. makes sense. i know there are some loops you can end up in but they're vanishingly unlikely. 12:01 -!- Moller40 [~mr@82.103.130.249] has quit [Ping timeout: 240 seconds] 12:03 < nothingmuch> sipa: i'd like to reiterate my question about e vs. R based signatures, and the rationale for preferring batch verification over compact signatures, and add to it 12:03 < waxwing> i think you could argue you don't need either the batch verification nor the optimisation sections in the BIP. 12:03 < waxwing> albeit it helps a lot to understand design decisions. 12:03 < nothingmuch> namely, is it fair to say that batch verification is necessarily serial? 12:04 < sipa> nothingmuch: what does that mean? 12:05 < nothingmuch> sipa: can't be computed in parallel 12:05 < sipa> i don't know what that means 12:05 < waxwing> i also don't understand, surely the whole point of batching is to do stuff in parallel 12:05 < nothingmuch> i mean given a batch, that the algorithm to do the whole batch is not concurrent 12:06 < nothingmuch> and can't benefit from multiple cores 12:06 < sipa> nothingmuch: ah, in theory it could, but we don't have an implementation for that 12:06 < sipa> however, you can split up the batch in 4 batches, and verify each on one core easily 12:06 < waxwing> that loses some of the scaling, but then if you had a parallelisable algo, it might too, i guess 12:07 < nothingmuch> i'm trying to better understand the compute vs. network latency tradeoff, the benefit from batching is obvious to me, but i'm not sure how it holds up against bandwidth cost, especially since witness data is discounted 12:07 < nothingmuch> or is the difference in security model the main rationale for preferring R over e, with batching being an extra benefit? 12:08 < nothingmuch> (without witness discount i can see that batch verification should be strictly better for orphan rates, but slightly reduced tx throughput) 12:09 < waxwing> pretty sure it's batching, the 'e' version is usually what's proved in security proofs isn't it. 12:09 < waxwing> oh but shortened .. ok. 12:11 < sipa> so using a 128-bit e value works in some security models for Schnorr, but not all 12:12 < sipa> (depending on which other assumptions on the group/hash are made) 12:12 < sipa> nothingmuch: as for bandwidth, i think the relevant metrics are (a) worst case bandwidth usage and (b) worst case CPU per byte usage 12:13 < sipa> and worst case bandwidth isn't affected by any of these proposals - it's close to 4M of data per block 12:13 < sipa> while batch validation significantly improves CPU per vbyte 12:14 < nothingmuch> that makes sense 12:14 < sipa> specifically, i believe the ROM/DL/forkinglemma proof for Schnorr indeed works with 128-bit hashes... but the generic group + collision resistant hash proof needs 256 bit hashes 12:16 < nothingmuch> we had another question in group 16 yesterday, which i attempted to answer but wanted to verify - is the reason for H(tag)||H(tag) being the prefix so that the compression function can already be applied given that the block size is double the image size? 12:17 < sipa> yes, that's the reason for having a 64-byte prefix 12:17 < sipa> though any other 64-byte prefix could be picked 12:18 < sipa> the reason for doubling the hash of the tag is given in bip-taproot i think 12:20 <@aj> second paragraph of Specification in bip-taproot 12:20 <@aj> any other questions or shall we call it? 12:20 < kabaum> Thank you all so much for your time today! My two suggestions for bip-schnorr are: 1) Specify the specific schnorr scheme used in the graph. 2) Add a footnote mentioning Strauss' algorithm or Shamir's trick as the reason for the efficiency gains of batch verification. 12:21 < waxwing> i think all of that including batch algo itself is kinda out of scope. but i'm conflicted because it's actually pretty cool to have it there :) 12:21 < waxwing> aj, don't let me stop you :) 12:21 < sipa> kabaum: i guess i should point out that Shamir's trick is only one of the ways in which multi-EC-multiplication is faster than single-EC-multiplication 12:22 < kabaum> Oh, shit. There's more. Maybe a followup on next Q&A. 12:23 <@aj> #endmeeting 12:23 < lightningbot> Meeting ended Tue Nov 19 20:23:10 2019 UTC. Information about MeetBot at http://wiki.debian.org/MeetBot . (v 0.1.4) 12:23 < lightningbot> Minutes: http://www.erisian.com.au/meetbot/taproot-bip-review/2019/taproot-bip-review.2019-11-19-19.00.html 12:23 < lightningbot> Minutes (text): http://www.erisian.com.au/meetbot/taproot-bip-review/2019/taproot-bip-review.2019-11-19-19.00.txt 12:23 < lightningbot> Log: http://www.erisian.com.au/meetbot/taproot-bip-review/2019/taproot-bip-review.2019-11-19-19.00.log.html 12:23 < sipa> there is a much cooler algorithm called Pippenger's, which actually gives O(n/log(n)) speed (all Strauss does is get rid of the doubling cost for the 2nd and later multiplications, but never reduces additions) 12:23 < sipa> kabaum: i can explain yet another algorithm called Bos-Coster which is very simple to explain, but isn't faster in practice so we don't use it 12:23 <@aj> can't ask for a better last line than "Oh shit. There's more." ... 12:24 < kabaum> aj: hehe 12:24 < nothingmuch> thank you! 12:24 < sipa> kabaum: interested? 12:25 < kabaum> sipa: If you have the time, please. 12:25 < kabaum> But I'm a bit overloaded. 12:25 < waxwing> i remember it's cool and not too hard to understand. 12:25 < sipa> so you want to compute n1*P1 + n2*P2 + n3*P3 + ..., and assume there are hundreds of terms 12:25 < waxwing> unfortunately i don't actually remember the algorithm, so please :) 12:26 < sipa> you sort them by descending value of n_i 12:26 < sipa> so n1 and n2 are the largest two n values 12:27 < sipa> now observe that n1*P1 + n2*P2 is actually the same as (n1-n2)*P1 + n2*(P1+P2) 12:27 < sipa> (it's subtracting n2*P1 from the first term, and adding it to the second term) 12:27 < sipa> right? 12:28 * waxwing is listening 12:28 < kabaum> You add and subtract n2P1 12:28 < sipa> so you can rewrite your list of EC multiplications to perform 12:29 < sipa> by doing 1 EC addition (the P1+P2) 12:29 < sipa> however, n1 and n2 are you two largest numbers... if they're approximately uniformly distributed, n1-n2 is going to be say 100 times smaller than n1, if you have 100 terms 12:30 < sipa> so you replace the P2 in the n2*P2 term with (P1+P2), delete the n1*P1 term, and re-insert (n1-n2)*P1 into your list... but probably not at the front anymore (as n1-n2 will very likely be a lot smaller than n1) 12:30 < sipa> right? 12:33 < kabaum> I vaguely follow.... now that n2 is probably the biggest value you can rearrange the terms again. 12:34 < sipa> indeed 12:34 < sipa> but the important thing is that we've reduced the multiplication factor of one of the terms by a factor 100, with just one EC multiplication 12:34 < sipa> *one EC addition 12:34 < sipa> and we can keep doing this 12:34 < sipa> with the new top two terms 12:35 < sipa> remember that in a naive EC multiplication algorithms (double and add), we're really only getting rid of 1 bit in the scalars for each EC addition 12:35 < sipa> here we're getting rid of 7 or 8 bits with high likelihood 12:36 < sipa> and the more terms there are, the more bits we get rid of in one go 12:37 < sipa> of course, at some point this must end-- we only have a finite number of bits in those scalars 12:37 < kabaum> That's fantastic. Like magic. When do you stop rearranging procedure? 12:37 < sipa> how does it end? sometimes n1 will equal n2 12:38 < sipa> in which case you just rewrite n*P1 + n*P2 into a single term n*(P1+P2) 12:38 < waxwing> interesting that the worst case would be when the differences between the coefficients were the same as the coefficients themselves. 12:38 < waxwing> iiuc. 12:39 < sipa> so actually the end point of this algorithm is just a single term, always 12:39 < sipa> of the form n*P 12:39 < sipa> where n is the gcd of all input scalars, which with extremely high probability is just 1 12:39 < sipa> in which case you're done and can just return P 12:41 < kabaum> So no multiplicatin at all. 12:42 < sipa> well, multiplication is always just a bunch of additions 12:42 < sipa> the question is how :) 12:43 < kabaum> yes, sure :=) 12:44 < sipa> the reason this algorithm isn't used is because it interacts badly with another optimization we have 12:44 < kabaum> Roughly how many iterations would this take? O(number of terms)? 12:44 < sipa> O(n/log(n)) 12:44 < sipa> or rather, O(n_terms*(1+bits_per_term/log(n_terms))) 12:45 < sipa> so it can't ever beat O(n_terms), but it can reduce the number of additions per term if the number of terms goes up 12:48 < kabaum> sipa: Thank you so much for the lecture! Hope to see you next Q&A! 12:48 < kabaum> Buy all! 12:49 < sipa> https://cryptojedi.org/peter/data/eccss-20130911b.pdf 12:49 -!- pglazman [~pglazman@205.209.24.227] has quit [Quit: My MacBook has gone to sleep. ZZZzzz…] 12:49 < sipa> this slide deck explains a lot of the ideas behind efficient multi-multiplication and more 12:50 < kabaum> Noted! 12:50 -!- Chris_Stewart_5 [~chris@unaffiliated/chris-stewart-5/x-3612383] has quit [Ping timeout: 240 seconds] 12:53 < instagibbs_> thick meeting notes :) 12:53 < instagibbs_> is there a name for the fixed sized signature encoding 12:56 < instagibbs_> bip-schnorr signature encoding I guess :P 13:04 < sipa> "64 byte sigs" 13:04 < sipa> "compact sigs" 13:04 < sipa> "non-braindead sigs" 13:05 < waxwing> was pretty disappointed you didn't use ASN.1 ngl 13:07 < instagibbs_> is secp's ECDSA compact serialization (e,s)? 13:07 < instagibbs_> looks like it's two scalars :) 13:08 < instagibbs_> in other words, it's not "entirely obvious" but the name is going to be BIPXXX 13:09 < sipa> no, it's (r,s) (where r = R.x) 13:09 < sipa> also, ECDSA doesn't have an equivalent for "e" (it has no hashes) 13:09 < instagibbs_> (r,s), right, :) 13:17 -!- midnight [~midnightm@unaffiliated/midnightmagic] has joined ##taproot-bip-review 13:18 < midnight> ahh.. here it is. 13:36 -!- pglazman [~pglazman@205.209.24.227] has joined ##taproot-bip-review 13:38 -!- davterra [~dulyNoded@195.242.213.120] has quit [Read error: Connection reset by peer] 13:38 -!- davterra [~dulyNoded@195.242.213.120] has joined ##taproot-bip-review 13:55 -!- pglazman [~pglazman@205.209.24.227] has quit [Ping timeout: 265 seconds] 13:57 -!- Moller40 [~mr@178.73.220.83] has joined ##taproot-bip-review 13:58 -!- Moller40_ [~mr@46.246.1.163] has quit [Ping timeout: 265 seconds] 14:12 -!- pglazman [~pglazman@205.209.24.227] has joined ##taproot-bip-review 14:46 -!- rottensox [~rottensox@unaffiliated/rottensox] has joined ##taproot-bip-review 15:14 -!- davterra [~dulyNoded@195.242.213.120] has quit [Ping timeout: 240 seconds] 15:15 -!- davterra [~dulyNoded@195.242.213.120] has joined ##taproot-bip-review 15:52 -!- pglazman [~pglazman@205.209.24.227] has quit [Quit: My MacBook has gone to sleep. ZZZzzz…] 16:11 < elichai2> sipa: I just went over the meeting, awesome explanations :) 16:11 < elichai2> I have one question, can any of these algorithms be of use in signing too? I can't see how any of them can be constant time in relation to the secret 16:12 < elichai2> (I'm actually not sure I looked at the signing mult function in libsecp) 16:15 < elichai2> sipa: arghh I disagree on "it has no hashes". You can't do the (e, s) because the whole term need to be devided by the nonce, so you need to have the nonce. But if you do ecdsa "without hashes" then it's broken. (unless you sign on some preknown constant ie opposite of fiat shamir) 16:16 < elichai2> At least that's my understanding (which I might be wrong :) ) 16:18 < sipa> elichai2: i don't understand 16:19 < sipa> ECDSA certainly needs the message to be a hash, if that's what you mean - it's absolutely broken otherwise, but the requirements on that hash are very low (just preimage resistance, i think) 16:19 < sipa> but apart from that, there is no 'challenge' value like schnorr has (which is the 'e' in the (e,s) form, or the hash in the (R,s) form) 16:22 < elichai2> Isn't that just because ecdsa is multiplied by the multiplicative inverse of the nonce? 16:22 < elichai2> Arghh I confused myself 16:23 < sipa> ECDSA effectively uses r=R.x as challenge 16:23 < sipa> so another way of looking at it is that for ECDSA, the (R,s) and (e,s) forms are the same (as you can interpret r both as an encoding of R, or as the challenge itself) 16:27 < elichai2> Looked again at the equations, and even if I remove the division by k I still can't make like (e, s) 16:27 < elichai2> The fact that the nonce is by itself in schnorr helps a lot 16:29 < sipa> the equation is sR = mG + rP, where R is some point whose X coordinate is r 16:30 < sipa> treating ECDSA as "(R, s)": compute r=R.x, and verify the equation 16:30 < elichai2> Oh I see now. The (e,s) is natural because we have e=H(R,m). For ecdsa A. We don't have that naturally. B. we can't get anything useful out of the equation without knowing R 16:30 < elichai2> Am I understanding correctly? 16:30 < sipa> treating ECDSA as "(e, s)" (with e=r), compute R as (mG+rP)/s, then extract R.x and compare it with e 16:31 < sipa> i'm saying the opposite: ECDSA is actually already in (e, s) form (if you call e=R.x) 16:32 < sipa> it's just confused because e is just computed directly from the R point... so it looks like it's encoding R itself 16:32 < elichai2> What will be the security if you split e up? 16:33 < sipa> what do you mean split e up? 16:33 < elichai2> I.e verify like this: e==R.x[:32] 16:33 < elichai2> Or something like that 16:33 < elichai2> Can you make "short ecdsa signatures"? 16:34 < sipa> that's a great question 16:34 < elichai2> * e==R.x[:16] 16:34 < sipa> but it's hard to answer without an accepted security proof 16:34 < sipa> like... as far as provable security goes, under standard assumptions, ECDSA is insecure with either a short or a long 'e' :p 16:35 < elichai2> It's easier to think with hash functions, but shortening a point seems scary lol (in terms of uniformity) 16:35 < elichai2> Lol yeah 16:36 < sipa> ok, let's redefine ECDSA signatures as (e,s) for which H((mG + eP)/s) = e 16:36 < sipa> so replacing "x coordinate of" with a hash function 16:36 < elichai2> Hmm that sounds like you can just use a shorter hash 16:36 < sipa> which is *not* ECDSA, to be clear 16:37 < elichai2> Haven't read Bone's paper on the requirement of hash functions for schnorr sigs so idk what's the proofs there and if they could be applied 16:37 < sipa> http://www.neven.org/papers/schnorr.pdf ? 16:37 < elichai2> Yes 16:37 < sipa> no Bone involved 16:37 < elichai2> Ops no Bone 16:37 < elichai2> Neven == Bone :P 16:37 < sipa> also, do you mean Boneh? 16:38 < elichai2> (for some reason in my mind lol) 16:38 < elichai2> Yes you'll need to excuse me, it's 3am here heh 16:39 < elichai2> That's why https://eprint.iacr.org/2018/483 16:39 < elichai2> Got me confused that this was also Neven+Boneh 16:51 -!- pglazman [~pglazman@205.209.24.227] has joined ##taproot-bip-review 17:02 -!- andrewtoth [~andrewtot@gateway/tor-sasl/andrewtoth] has quit [Remote host closed the connection] 17:02 -!- andrewtoth [~andrewtot@gateway/tor-sasl/andrewtoth] has joined ##taproot-bip-review 17:25 < luke-jr> this channel should be logged :/ 17:25 <@aj> it is logged? 17:26 < harding> http://www.erisian.com.au/taproot-bip-review/ 17:26 -!- mode/##taproot-bip-review [+o harding] by ChanServ 17:27 -!- harding changed the topic of ##taproot-bip-review to: Discussion about the Taproot BIP Reviews. More information: https://github.com/ajtowns/taproot-review; logs: http://www.erisian.com.au/taproot-bip-review/ ; meeting logs: http://www.erisian.com.au/meetbot/taproot-bip-review/2019 17:27 -!- mode/##taproot-bip-review [-o harding] by harding 18:07 -!- pglazman [~pglazman@205.209.24.227] has quit [Quit: My MacBook has gone to sleep. ZZZzzz…] 18:42 -!- pglazman [~pglazman@205.209.24.227] has joined ##taproot-bip-review 19:25 -!- gmaxwell [gmaxwell@wikimedia/KatWalsh/x-0001] has joined ##taproot-bip-review 19:35 < gmaxwell> sipa: https://pdfs.semanticscholar.org/7d54/3246aedff2a9bea4a9a964691126a0f3e050.pdf gives a concrete attack on shortned schnorr signatures, under a very slightly contrived hash function that meets the security requirements normally used in proofs for full length schnorr signatures. Thus proving they are weaker and more fragile, if not showing they are pratically so. 19:35 < gmaxwell> I believe there exists another paper that shows them insecure in a musig-ish sort of setting with an attack like nicker's recent blockstream blogpost. 19:36 < gmaxwell> I vaguely recall there being another attack that I can't find that Adam Back had mentioned previously, so you might want to ask him. 19:38 < gmaxwell> nothingmuch: you mentioned orphaning a number of times but typically signatures are not sent with blocks, but well before them in loose transactions. I think it's unlikely that saving 16 bytes per signature would make a difference in the common case. (and against some attack block specifically constructed to not have prepropagated data, the attacker could stuff with whatever they want). 19:39 -!- pglazman [~pglazman@205.209.24.227] has quit [Quit: My MacBook has gone to sleep. ZZZzzz…] 19:39 < gmaxwell> nothingmuch: also in the long run I expect that on 'a longer time horizon' aggregation would be used, which makes the small offsets in the signature size more irrelevant. 19:41 -!- pglazman [~pglazman@205.209.24.227] has joined ##taproot-bip-review 19:41 < gmaxwell> Also, wrt batching, it's a rather large speedup... and in particular, the taproot check as well as future musig combining for aggregation can be combined into a common batch operation, allowing biger batches in practice for more speeup. 19:44 < gmaxwell> waxwing 19:44 < gmaxwell> waxwing: RFC6979 is awful for complicated political reasons. 19:46 < gmaxwell> waxwing: essentially, it wanted to use an unmodified NIST approved random generation function exactly like it's supposted to be use, with the message/key as the freeform random inputs ... so that FIPS certified stuff could use it while retaining their FIPS certification. 19:47 < gmaxwell> It also has to deal with NIST curves, most (all?) of which have N such that the size is really far from a power of two, and bias is a real concern. 19:49 < gmaxwell> the bip-schnorr recommended nonce procedure is the same (IIRC) as the EdDSA one. 19:49 < gmaxwell> (except for the whole prehashing the secret part, which isn't compatible with ... well.. anything interesting) 19:49 -!- pglazman [~pglazman@205.209.24.227] has quit [Quit: My MacBook has gone to sleep. ZZZzzz…] 19:53 < nothingmuch> gmaxwell: yes, i later realized compact blocks completely moot my point ;-) 19:53 < nothingmuch> s/point/concern/; 19:56 < nothingmuch> i suppose that flawed assumption being interpreted too charitably by nickler and sipa was why i felt i needed to follow up 19:58 < gmaxwell> well bandwith is certantly an issue too, orphaning aside. 19:58 < gmaxwell> There is actually a third design option that wasn't mentioned. Which is esentially use a short schnorr signature but communicate in r,s form. 19:59 -!- shesek [~shesek@unaffiliated/shesek] has joined ##taproot-bip-review 19:59 < gmaxwell> This would give all the batch advantages, but if you really cared about space or bandwidth, you could convert to short e,s form for communication/storage an convert back for checking hashes. 20:00 < gmaxwell> The reason I never promoted that is because I consider the shortned schnorr signature security story, at least at the 256 bit security level, kinda dubious. 20:00 < sipa> * 128 security level 20:00 < gmaxwell> If we were talking about a 448 bit curve or something, then I think a shortned signature might be more interesting. 20:00 -!- pglazman [~pglazman@205.209.24.227] has joined ##taproot-bip-review 20:02 < gmaxwell> also, if you really prefer saving 16 bytes over a factor of 2 validation speed and don't care about less clear security properties... BLS signatures are the obvious thing to use instead of shortned schnorr. 20:06 -!- HighOnBtc [~Admin@86.121.55.235] has quit [Remote host closed the connection] 20:10 < nothingmuch> gmaxwell: i'm having trouble understanding how those are interchangiable after staring at it for a while... is there a name for this variant i could look up? 20:11 < sipa> nothingmuch: interchange what with what? 20:11 < sipa> schnorr with bls? 20:12 < nothingmuch> no, and forms (is r a typo fo R here? or a differently defined scalar?) 20:12 < sipa> nothingmuch: in schnorr? 20:12 < sipa> it's the first paragraph in the bip 20:12 < nothingmuch> sipa: see gmaxwell's remark on third design option, 14 min ago 20:13 < sipa> e = hash(R || P || m) 20:13 < sipa> so you can convert (R, s) into (e, s) by just computing the hash of R||P||m 20:13 < nothingmuch> initially i assumed R,s was meant, but i don't see how you can convert back from e,s to R,s form 20:14 < sipa> and convert (e, s) into (R, s) by computing R = sG - eP 20:14 < nothingmuch> oh, right! i think this is an indication i should have gone to sleep a while aog 20:14 < sipa> haha 20:30 -!- pglazman [~pglazman@205.209.24.227] has quit [Quit: My MacBook has gone to sleep. ZZZzzz…] 22:07 -!- pglazman [~pglazman@c-67-174-198-20.hsd1.ca.comcast.net] has joined ##taproot-bip-review 22:44 -!- kabaum [~kabaum@2001:9b1:efd:9b00::281] has quit [Ping timeout: 250 seconds] 23:00 -!- Moller40 [~mr@178.73.220.83] has quit [Quit: -a- IRC for Android 2.1.55] 23:08 -!- pglazman [~pglazman@c-67-174-198-20.hsd1.ca.comcast.net] has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]