--- Day changed Tue Feb 06 2018 00:01 < sipa> for 2-of-3 it gets more interesting 00:01 < kallewoof> if you have MuSig, it seems like you can do the same as 2-of-2, no? 00:02 < sipa> how so? 00:03 < kallewoof> I mean, in the 2-of-2 case, presuming B can't make a negating pubkey from A's key, the same should apply for A/B/C in 2-of-3, no? 00:03 < kallewoof> using MuSig 00:04 < sipa> yes, but then what? 00:04 < kallewoof> Is there a problem with that approach? 00:04 < sipa> MuSig on A,B,C would give you a key that all 3 need to sign for 00:04 < sipa> how do you turn it into a 2-of-3 00:04 < kallewoof> Oh 00:05 < kallewoof> Only thing I can think of is to make AB AC BC combinations, but I suspect there's a better solution 00:05 < sipa> oh yes 00:05 < sipa> the point is that there is just a single key 00:05 < sipa> not multiple 00:06 < kallewoof> That does 2-of-3? 00:06 < sipa> yes 00:06 < sipa> if 1-of-2 is possbible, and w- 00:06 < sipa> if 1-of-2 is possbible, and 2-of-2 is possiblez there must be a way to combine those approaches and get 2-of-3 :) 00:07 < kallewoof> Well, your 1-of-2 approach above seems a little dangerous :P 00:07 < sipa> what is dangerous about it? 00:07 < kallewoof> B has A's private key 00:07 < sipa> no 00:07 < sipa> they both have a fresh private key 00:07 < sipa> it's not A's private key 00:07 < sipa> it's A and B's private key 00:08 < sipa> which happens to be generated by A 00:08 < kallewoof> Oh, good point 00:08 < sipa> so A can run away with the money, obviously 00:08 < sipa> but that's not a problem, as A is explicitly authorized to do so 00:08 < sipa> this approach does not work with reused keys 00:09 < kallewoof> So the 1-of-2 is simply a shared private key. And 2-of-2 can be done using MuSig. So you'd somehow have a shared private key and use MuSig to get 2-of-3? 00:10 < sipa> so 00:10 < sipa> you can see 2-of-3 as (A and B) or (B and C) or (C and A) 00:10 < sipa> you have A and B generate keys, call them kA and kB 00:12 < sipa> now both A and B split their keys into two pairs, so 4 pairs in total 00:12 < kallewoof> You can split keys? 00:12 < sipa> kA = kA1B+kA1C 00:12 < sipa> so kA1B is randomly generated, kA1C = kA-kA1b 00:13 < kallewoof> Oh *nod* 00:13 < sipa> and same for kA = kA2C+kA2A 00:13 < sipa> same with B 00:14 < sipa> now A gives kA1B to B, kA1C to C, kA2A to himself, kA2C to C 00:14 < sipa> and B gives kB1B to B, kB1C to C, kB2A to himself, kB2C to C 00:15 < kallewoof> kB2A to A, I think you mean 00:15 < sipa> yup! 00:15 < sipa> now C and A for example both have a share from A and one from B 00:16 < sipa> and those 4 shares together add up to the same as kA+kB 00:17 < kallewoof> I have to write it down on paper I think but that looks like it works. That's pretty cool! 00:17 < sipa> yup, whiteboards/paper help with this stuff 00:17 < sipa> you can also see there are many footguns 00:18 < sipa> like you need make sure no keys cancel out (which requires signatures) 00:18 < kallewoof> Yeah. I initially wondered why you didn't just do MuSig = kA+kB, and share kA with A+B and kB with B+C... but then realized B can then single sign 00:18 < sipa> and you need to make sure that the refipients of shares verify that those shares actually add up the the right key 00:19 < kallewoof> Right 00:19 < sipa> and you need to have ore-established identities to secure the communication channels with 00:19 < sipa> *pre 00:19 < kallewoof> *nods* 00:19 < sipa> but it is extremely powerf 00:20 < sipa> you can extend it to any policy you can write using ands and ors over keys 00:20 < kallewoof> Very cool. Thanks for taking the time to explain 00:21 < sipa> the crazy thing is that the result is just a 1-of-1 sig on chain 00:22 < sipa> nobody knows what the policy was, or that there were multiple parties involved at all 00:22 < sipa> and it's efficient 00:22 < sipa> the downside is that it's not accountable - you don't know which subsets of participants sogned 00:22 < kallewoof> Haha yeah. Mind blowing stuff. Ever since I realized you can add keys I've been thinking about applications. And of course most of them are completely insecure.. 00:23 < gmaxwell> (for clarification sake, any policy that makes sense can be constructed with ands and ors... a circuit that can't be constructed with ands and ors is one where _adding_ an additional approval would make the signature fail... which makes no sense) 00:24 < sipa> "pieter and kalle are allowed to spend the coins, AS LONG AS GREG DOES NOT AGREE" 00:28 < sipa> this sounds like the setup for some crazy hollywood movie about a rich uncle who leaves his inheritance with a will that his nephews can only spend the money on things they disagree about 00:28 * sipa zZzZ 04:34 < kallewoof> /me giggles 10:42 < maaku> kallewoof: missing from sipa's explanation is the mathematical fact (which maybe you already know) that ANY signing requirements can be expressed as a monotone boolean function, and all MBF can be expressed in a form like (A and B and C) or (D and E) or ... 10:42 < maaku> this is called disjunctive normal form 10:43 < maaku> (this should look familiar from sipa's tree signatures) 10:44 < maaku> so this "MuSig one signing set, then key-split shares to the other signers" approach for signing conditions in disjunctive normal form is actually fully general and can represent any signing condition 10:46 < maaku> although there may be computational limits which prevent us from using the fully generalized scheme in all use cases we might care about due to combinatorial explosion ... e.g. a "50 out of 100" threshold in disjunctive normal form has 2^96 different signing sets, even though there's only 100 participants 10:47 < sipa> maaku: i believe the scheme generalizes 10:47 < sipa> you don't actually need it to be disjunctive normal form 10:48 < sipa> it just needs to be written as ands ans ors 10:48 < sipa> for example if it's an and of ors of ands, you repeat the ors-of-ands scheme for each toplevel or, and add the pubkeys together 10:49 < maaku> yes 10:50 < sipa> and you may be able to add in actual thresholds using polynomial interpolation too, as andytoshi thought earlier 10:50 < maaku> that also lets each participant have their own multi-key signing policies that are opaque to the higher level protocol 10:50 < sipa> right 10:52 < maaku> I prefer to explain using disjunctive normal form because it's easy to show how that is fully general. But practicalities make things a lot more complex.. 11:00 -!- hdevalence [~hdevalenc@52.119.117.17] has joined #secp256k1 12:42 -!- king_ [~king@5.157.36.99] has joined #secp256k1 12:46 -!- king_ [~king@5.157.36.99] has quit [Client Quit] 13:23 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Ping timeout: 255 seconds] 13:28 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1 14:09 -!- hdevalence [~hdevalenc@52.119.117.17] has quit [Quit: hdevalence] 14:20 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Remote host closed the connection] 14:21 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1 16:01 < gmaxwell> sipa: I bet co-Z would change the strauss vs pippenger tradeoff point... the coZ speedup will make a bigger difference for batches, since more of the time is in precomputation. 16:22 < gmaxwell> https://eprint.iacr.org/2008/051.pdf points out that the last addition before a (series of) doubling(s) can be done as a combined doubling-addition which is faster than the indivigual operations. There is one of these in every window for both strauss and pippenger. They claim 11m+7s for their unified double and add, the two operarions for us are 15m+8s, and their formula is not specialized for a=0. 16:33 -!- echonaut [~echonaut@46.101.192.134] has quit [Remote host closed the connection] 16:33 -!- echonaut1 [~echonaut@46.101.192.134] has joined #secp256k1 16:34 -!- droark [~droark@c-24-22-123-27.hsd1.or.comcast.net] has quit [Quit: Later.] 16:39 < gmaxwell> This is interesting, ftp://nozdr.ru/biblio/kolxo3/Cs/CsLn/I/Information%20Security%20and%20Cryptology%20-%20ICISC%202004,%207%20conf.(LNCS3506,%20Springer,%202005)(ISBN%203540262261)(501s).pdf#page=148 it shows post-processing methods to reduce the highest significant digit in WNAF representations. sipa and I were discussing that subject the other day. 16:41 < gmaxwell> in particular it notes you could have a simple table with length reduction subsitutions, and just apply it on the highest digits. 16:46 < arubi> TIL about #page= 17:22 -!- droark [~droark@c-24-22-123-27.hsd1.or.comcast.net] has joined #secp256k1 18:36 < gmaxwell> sipa: so going through and subsituting 0s into the wnaf w/ a really dumb postprocess (couldn't be bothered to figured out how to do it efficiently) speeds up 1 point pippenger by 10% 18:46 < gmaxwell> ecmult_8g: min 115us / avg 116us / max 117us 18:46 < gmaxwell> ecmult_8g: min 109us / avg 109us / max 110us 18:46 < gmaxwell> so I guess the speedup probably drops off pretty fast. 18:52 < sipa> is that just exploiting the fact the wnaf is allowed to produce 0s instead of just odd numbers? 19:17 -!- jtimon [~quassel@41.31.134.37.dynamic.jazztel.es] has quit [Ping timeout: 268 seconds] 19:57 < gmaxwell> sipa: yes. 19:57 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Remote host closed the connection] 19:58 < gmaxwell> if a digit is 1 or -1 and the digit before it has opposite sign, I set it to zero and fixup the digit before it. kinda dumb. 19:58 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1 20:21 -!- echonaut1 [~echonaut@46.101.192.134] has quit [Remote host closed the connection] 20:21 -!- echonaut [~echonaut@46.101.192.134] has joined #secp256k1 21:30 -!- echonaut [~echonaut@46.101.192.134] has quit [Remote host closed the connection] 21:30 -!- echonaut [~echonaut@46.101.192.134] has joined #secp256k1 21:35 -!- echonaut [~echonaut@46.101.192.134] has quit [Remote host closed the connection] 21:36 -!- echonaut [~echonaut@46.101.192.134] has joined #secp256k1 21:42 -!- echonaut [~echonaut@46.101.192.134] has quit [Remote host closed the connection] 21:42 -!- echonaut [~echonaut@46.101.192.134] has joined #secp256k1 21:51 -!- echonaut [~echonaut@46.101.192.134] has quit [Remote host closed the connection] 21:51 -!- echonaut [~echonaut@46.101.192.134] has joined #secp256k1 21:53 -!- echonaut [~echonaut@46.101.192.134] has quit [Remote host closed the connection] 21:53 -!- echonaut [~echonaut@46.101.192.134] has joined #secp256k1 21:54 -!- echonaut [~echonaut@46.101.192.134] has quit [Remote host closed the connection] 21:54 -!- echonaut2 [~echonaut@46.101.192.134] has joined #secp256k1 21:56 < gmaxwell> sipa: I'd open a PR but I'm not seeing a way to do it cleanly. 21:56 < gmaxwell> (just being dumb I'm sure) 22:15 -!- echonaut2 [~echonaut@46.101.192.134] has quit [Remote host closed the connection] 22:16 -!- echonaut [~echonaut@46.101.192.134] has joined #secp256k1