--- Day changed Wed Jul 12 2017 05:40 -!- zmanian_____ [sid113594@gateway/web/irccloud.com/x-fhmhjufidorjuble] has joined #secp256k1 05:40 -!- CodeShark_ [sid126576@gateway/web/irccloud.com/x-egokdoxawwwlvfxt] has joined #secp256k1 05:41 -!- TD--Linux [~Thomas@kyoko.thomasdaede.com] has joined #secp256k1 05:41 -!- CodeShark [sid126576@gateway/web/irccloud.com/x-eugwmiyfnvabvufe] has quit [Ping timeout: 246 seconds] 05:41 -!- zmanian____ [sid113594@gateway/web/irccloud.com/x-owkwsesbxlhehixs] has quit [Ping timeout: 246 seconds] 05:41 -!- TD-Linux [~Thomas@about/essy/indecisive/TD-Linux] has quit [Ping timeout: 246 seconds] 05:41 -!- CodeShark_ is now known as CodeShark 09:52 -!- TD--Linux is now known as TD-Linux 09:52 -!- TD-Linux [~Thomas@kyoko.thomasdaede.com] has quit [Changing host] 09:52 -!- TD-Linux [~Thomas@about/essy/indecisive/TD-Linux] has joined #secp256k1 10:50 -!- jtimon [~quassel@102.30.134.37.dynamic.jazztel.es] has joined #secp256k1 12:27 -!- adiabat [~adiabat@45.63.20.152] has joined #secp256k1 12:29 < adiabat> Hi, not sure if right place to ask but I'm trying to implement secp256k1 schnorr sigs and am getting intermittent problems 12:29 < adiabat> signatures verify correctly 99.6% of the time 12:30 < adiabat> it's deterministic, but given random messages, random pubkeys, random k values... it mostly works. 12:30 < sipa> are you using libsecp256k1? 12:30 < adiabat> but about 0.4% of the time the signature doesn't verify; that is s*G != R - eA 12:30 < adiabat> no I wrote my own stuff in go 12:31 < adiabat> so maybe not appropriate for this channel but 12:31 < adiabat> wondering if anyone knew like "aah, 0.4%, that's probably ____" 12:31 < adiabat> but the code I'm using is derived from libsecp 12:31 < sipa> that's probably a serialization issue, where the first byte is a 0? 12:31 < sipa> (which happens 1/256 of the time) 12:32 < waxwing> damn you beat me sipa :) 12:32 < adiabat> oh... ! 12:32 < adiabat> didn't even see that 12:32 < sipa> also, we've stopped considering schnorr sign in libsecp256k1 12:32 < adiabat> hmmm I will look at that, good call 12:32 < adiabat> I know, you took it out :) 12:33 < sipa> we're now looking into Bellare-Neven multisignatures, see #461 12:33 < adiabat> several students at MIT were like "can sipa put schnorr sigs back in? can you ask him??" 12:33 < adiabat> oh cool, will look 12:33 < adiabat> wasn't aware of that 12:33 < sipa> for a single signer, they're effectively schnorr signatures 12:34 < gmaxwell> also the Y sign tiebreak we used before wasn't great, and is fundimentally more expensive than the quadratic residue test we suggest now. 12:34 < gmaxwell> The earlier multisig code with it was also vulnerable to wagner's attack. 12:34 < adiabat> the Y-sign thing was what was causing my code to fail 50% of the time yesterday :) 12:35 < adiabat> well, 50.39% I thing 12:35 < adiabat> *think 12:35 < sipa> the verification equation for a signature (R,s) and message m for keys P1,P2,...,Pn is R == s*G + H(1||L||R||m)*P1 + H(2||L||R||m)*P2 + ... + H(n||L||R||m)*Pn, where L = H(P1||P2||...||Pn) 12:35 < adiabat> huh so similar, just you put the index in at the beginning 12:35 < sipa> with a single signer that reduces to R == s*G + H(1||H(P)||R||m)*P1 12:37 < adiabat> the P1, P2... in L is sorted cannonically, similar to the previous "combo commitment" right? 12:38 < sipa> that is very similar, but not equivalent, to the multisig scheme we were proposing before, which had R == s*G + H(1||L)*H(C||R||m)*P1 + ... + H(n||L)*H(C||R||m)*P2, where L = H(P1||...||Pn), and C = H(1||L)*P1 + ... + H(n||L)*Pn 12:39 < adiabat> (writing it on paper to see difference) 12:39 < sipa> adiabat: it's not sorted, so the keys are position dependent 12:40 < gmaxwell> adiabat: use of the sign as the tiebreak is not great because it breaks our inversion-free-verification optimization (which we use for ECDSA); since you need to put R back in affine coordinates to check the sign. We propose now requiring R to be chosen so that R.y is a quadratic residue. (see the thread on curves list; "libsecp256k1's novel(?) ECDSA verification optimization") 12:41 < adiabat> gmaxwell: will read up on this... what proportion of R.ys are? as in how many to try? 12:41 < sipa> adiabat: for every valid R.x, there are two R.y values 12:41 < adiabat> this Bellare-Neven multisig does seem simpler 12:42 < adiabat> sipa: right; previously R.y had to be even 12:42 < sipa> adiabat: one of those R.y's is a quadratic residue, one is not 12:42 < sipa> also, one is odd and one is even 12:42 < sipa> also, one is high and one is low 12:42 < sipa> so there are 3 possible tie breaks 12:43 < adiabat> oh ok so it's the same subtract N fix 12:43 < sipa> adiabat: to see the similarity, notice that C (the combined public key) is in fact just a specially-constructed commitment to the list of public keys, just like L 12:44 < sipa> so our scheme is equivalent is commitment structure (but not in features) to R == s*G + H(1||L)*H(L||R||m)*P1 + ..., rather than H(1||L||R||m)*P1 in BNms 12:44 < adiabat> yeah H(1||L)*H(C||R||m) does seem redundant 12:44 < sipa> well it's needed to make the result look like a signature with a single key 12:44 < adiabat> also why not put everyting into one hash instead of multiplying the two scalars 12:44 < sipa> that's a feature that BNms does not have 12:44 < sipa> the verifier needs to know all signer keys 12:45 < sipa> rather than being able to verify with some aggregate key 12:45 < gmaxwell> sipa: to be specific, BNM has it to the extent any schnorr signature has it: you can do it externally and obliviously to the verifier; but you must solve the delinearization problem somehow. 12:45 < adiabat> that seems like a downside though... but maybe not in practice 12:46 < adiabat> right; in the 1 of 1 case, you can construct your own multisignature scheme that looks like 1 key 12:46 < sipa> gmaxwell: ok, more specific: there is no combined aggregated key known before signing 12:47 < gmaxwell> it's not an actual difference with what we proposed before; other than we proposed using exactly the same delinearization scheme in the keys-combine and aggregate case; and BNM uses a delinearization approach which isn't compatible with combined keys. 12:47 < adiabat> 1 of 1 is s*G + H(1||L||R||m)*P ... but L is just P 12:47 < sipa> right 12:47 < gmaxwell> You can still do your own thing on top.. exactly. 12:47 < gmaxwell> So it's no worse off. 12:47 < sipa> exactly... we could even say that the 1 and the hash around P is dropped when the list of keys is size 1 12:47 < gmaxwell> But we get a aggregate scheme for the many keys case with a good security proof (better than ours; which was a bit weak). 12:47 < sipa> or not, who cares 12:48 < adiabat> do the 1, 2, 3s actually help against birthday attacks? well I suppose I should read the paper 12:48 < gmaxwell> yea, zomg "number 1, doom". 12:50 < sipa> adiabat: without the 1,2,3, the multiplier for each key is the same 12:59 < andytoshi> amusingly my initial code (maybe the current code too) starts counting from 0 and it serializes 0 as a null string, so the single-signer case is even closer to an ordinary sig 13:00 < andytoshi> i think the commitment structure is H(idx || H(L||R||m)) and in the single-signer case L is just the single pubkey, so you wind up with a double-hash but otherwise nothing funny looking 13:01 < sipa> ah, Schnorr with double-SHA256 as hash function! 13:02 < gmaxwell> fun aside: with sha-ni I believe sha256 is now the fastest cryptographic hash anyone would consider using. 13:02 < waxwing> andytoshi: https://twitter.com/geekfun0/status/885172784938209280 13:03 < gmaxwell> andytoshi: yes, counting at zero seems obvious, though one would want to avoid collisions from absurd delimiting errors. 13:03 < gmaxwell> so I think a zero length zero might not be kosher. 13:03 < sipa> gmaxwell: the length is implied by the length of the input to the outside hash 13:04 < andytoshi> so, L and R and m always have fixed lengths (m is actually a 32-byte hash already) 13:04 < gmaxwell> ah, true, okay then 13:04 < gmaxwell> well m having a fixed length is technically suboptimal. 13:04 < andytoshi> i agree this made me hesitant but i'm pretty sure it's ok 13:04 -!- jtimon [~quassel@102.30.134.37.dynamic.jazztel.es] has quit [Ping timeout: 240 seconds] 13:04 < gmaxwell> but I don't think we're going to do something differently there for bitcoin. 13:16 -!- neha [~narula@tbilisi.csail.mit.edu] has joined #secp256k1 13:40 < adiabat> sipa: fixed serialization / padding error in my code, thanks! 13:58 < sipa> haha 14:00 -!- jtimon [~quassel@102.30.134.37.dynamic.jazztel.es] has joined #secp256k1 15:30 -!- echonaut [~echonaut@46.101.192.134] has quit [Remote host closed the connection] 15:32 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has quit [Excess Flood] 15:32 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1 15:32 -!- echonaut [~echonaut@46.101.192.134] has joined #secp256k1 18:19 -!- jtimon [~quassel@102.30.134.37.dynamic.jazztel.es] has quit [Remote host closed the connection] 19:34 -!- jtimon [~quassel@102.30.134.37.dynamic.jazztel.es] has joined #secp256k1 20:28 -!- neha [~narula@tbilisi.csail.mit.edu] has quit [Ping timeout: 240 seconds] 20:42 -!- jtimon [~quassel@102.30.134.37.dynamic.jazztel.es] has quit [Remote host closed the connection]