--- 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]