1 2019-11-09T00:47:32  *** pinheadmz has joined ##taproot-bip-review
 2 2019-11-09T02:15:44  *** HighOnBtc has quit IRC
 3 2019-11-09T02:29:18  *** nick_freeman has joined ##taproot-bip-review
 4 2019-11-09T02:32:27  *** nick_fre_ has quit IRC
 5 2019-11-09T03:51:12  *** nick_freeman has quit IRC
 6 2019-11-09T04:01:54  *** mryandao has joined ##taproot-bip-review
 7 2019-11-09T05:16:02  *** andytoshi has quit IRC
 8 2019-11-09T05:45:10  *** michaelfolkson has joined ##taproot-bip-review
 9 2019-11-09T06:00:13  *** michaelfolkson has quit IRC
10 2019-11-09T06:13:47  <raj_149> paraphrasing from Bip-Schnorr: implicite Y coordinate are not reduction in security if they are thought of from number of "curve operation to get priv key" perspective, as getting the right Y is just an negation operation in field element.
11 2019-11-09T06:13:47  <raj_149> But this necessarily reduces the total space of valid pubkeys into half. Does that have any security consequences for DLP?
12 2019-11-09T06:13:47  <raj_149> let me know if my question is not clear enough.
13 2019-11-09T06:30:34  <sipa> raj_149: no, it does.not reduce security at all, not even 1 bit
14 2019-11-09T06:30:38  <sipa> https://medium.com/blockstream/reducing-bitcoin-transaction-sizes-with-x-only-pubkeys-f86476af05d7
15 2019-11-09T06:31:22  <sipa> raj_149: the intuition is that the fact that negation of public keys is so cheap to compute, will *already* reduce security... even for full public keys with y coordinate
16 2019-11-09T06:59:46  <raj_149> Okay, thanks for the reference.
17 2019-11-09T07:04:51  <sipa> raj_149: another way to look at it (which is in the bip draft, i think) is this: imagime you had an algorithm X that given an x-only pubkey computed its discrete logarithm
18 2019-11-09T07:05:35  <sipa> you can write an algorithm Y that breaks the DL for full pubkeys, by simply giving it to X, and then depending on whether the sign is right, either return its result directly or negate ot
19 2019-11-09T07:06:00  <sipa> so Y is not slower than X
20 2019-11-09T07:12:38  <raj_149> That does make sense.
21 2019-11-09T07:12:38  <raj_149> In another words, the total privkey space is unchanged.
22 2019-11-09T07:12:39  <raj_149> So assuming DLP is hard, its gonna take same effort to scour privkey for pubkeys with/without the tie breaker. Will that be a valid arguement?
23 2019-11-09T07:13:22  <sipa> raj_149: no, the privkey space is halved
24 2019-11-09T07:13:39  <sipa> but it's removing a half that already didn't add any security
25 2019-11-09T07:18:57  *** r251d has quit IRC
26 2019-11-09T07:19:37  <raj_149> Oh right. privkeys are negated depending on the y of pubkeys.
27 2019-11-09T07:19:37  <raj_149> What do you mean by "didn't add security"?
28 2019-11-09T07:19:38  <raj_149> Isn't the computational hardness depends on the total size of the haystack in which your have to hit the niddle? If you have smaller haystack then it becomes easier to find the niddle.
29 2019-11-09T07:21:06  <sipa> raj_149: the most efficient DLP solver algorithms scale with the square root of largest prime factor of the group size divided by the size of the efficiently computable endomorphism on the group
30 2019-11-09T07:21:34  <sipa> negating a group element is an efficiently computable endomorphism
31 2019-11-09T07:28:49  <raj_149> I guess i need to study more on DLP. It felt counterintuitive at first glance.
32 2019-11-09T07:29:43  <raj_149> Thanks for clarifying. Is the any reference i can study up on this topic??
33 2019-11-09T07:34:31  <sipa> start with pollard's rho for discrete logarithms
34 2019-11-09T09:00:45  *** michaelfolkson has joined ##taproot-bip-review
35 2019-11-09T10:56:57  *** b10c has joined ##taproot-bip-review
36 2019-11-09T11:31:26  *** sergei-t has joined ##taproot-bip-review
37 2019-11-09T12:03:32  <waxwing> where can i check current status on threshold with musig? i have this vague memory that someone said it wasn't currently clear that it could be done ..?
38 2019-11-09T12:10:30  *** sergei-t has left ##taproot-bip-review
39 2019-11-09T12:21:24  *** michaelfolkson has quit IRC
40 2019-11-09T12:26:59  *** jonatack has quit IRC
41 2019-11-09T12:44:48  *** jonatack has joined ##taproot-bip-review
42 2019-11-09T12:50:23  *** jonatack has quit IRC
43 2019-11-09T13:01:50  *** Chris_Stewart_5 has joined ##taproot-bip-review
44 2019-11-09T13:02:43  *** jonatack has joined ##taproot-bip-review
45 2019-11-09T13:50:18  *** b10c has quit IRC
46 2019-11-09T14:07:38  *** Chris_Stewart_5 has quit IRC
47 2019-11-09T14:28:34  *** stacie has joined ##taproot-bip-review
48 2019-11-09T15:05:58  <moneyball> real_or_random and andytoshi likely know the latest status. My understanding is the theory is there but very hard to do in practice so they’re exploring alternative mechanisms that are more practical.
49 2019-11-09T15:08:31  <waxwing> gotcha. presumably the theory being based on shamir style stuff? (polynomials), but it absolutely doesn't surprise me if it's decidedly non trivial. but, we fallback to MAST things, i take it, for the cases where there is not a combinatorial blowup. albeit that has its privacy loss tradeoff.
50 2019-11-09T15:12:49  *** stacie has quit IRC
51 2019-11-09T15:26:23  *** mryandao has quit IRC
52 2019-11-09T15:27:38  *** mryandao has joined ##taproot-bip-review
53 2019-11-09T15:45:20  *** michaelfolkson has joined ##taproot-bip-review
54 2019-11-09T16:04:46  *** michaelfolkson has quit IRC
55 2019-11-09T16:22:14  *** michaelfolkson has joined ##taproot-bip-review
56 2019-11-09T16:34:22  *** HighOnBtc has joined ##taproot-bip-review
57 2019-11-09T16:37:27  <sipa> waxwing: my understanding is that there isn't much specific to musig in the context of threshold signatures
58 2019-11-09T16:38:12  <sipa> as in: if you have a secure threshold scheme it can probably be adapted to work with musig-derived kwys too
59 2019-11-09T16:39:05  <sipa> the question is more what security properties are proven for treshold schemes in general, and it seems the theory is laxking quite a bit... common schemes are only secure with k<k/2 or so
60 2019-11-09T16:49:48  <moneyball> k<n/2 right?
61 2019-11-09T17:03:50  *** hebasto has quit IRC
62 2019-11-09T17:04:08  *** hebasto has joined ##taproot-bip-review
63 2019-11-09T17:07:25  *** hebasto has quit IRC
64 2019-11-09T17:18:00  *** hebasto has joined ##taproot-bip-review
65 2019-11-09T17:22:07  *** michaelfolkson has quit IRC
66 2019-11-09T17:22:54  <kanzure> waxwing: andytoshi had a gist
67 2019-11-09T17:23:27  <kanzure> no.. not a gist. nevermind.
68 2019-11-09T17:39:50  *** michaelfolkson has joined ##taproot-bip-review
69 2019-11-09T17:42:06  *** michaelfolkson has quit IRC
70 2019-11-09T17:42:33  *** jonatack has quit IRC
71 2019-11-09T17:44:06  *** michaelfolkson has joined ##taproot-bip-review
72 2019-11-09T17:46:12  *** michaelfolkson has quit IRC
73 2019-11-09T17:46:59  *** hebasto has quit IRC
74 2019-11-09T17:48:15  *** hebasto has joined ##taproot-bip-review
75 2019-11-09T17:56:02  *** HighOnBtc has quit IRC
76 2019-11-09T18:05:59  *** r251d has joined ##taproot-bip-review
77 2019-11-09T18:23:42  *** andytoshi has joined ##taproot-bip-review
78 2019-11-09T18:31:17  *** yaslama has joined ##taproot-bip-review
79 2019-11-09T19:51:42  *** jonatack has joined ##taproot-bip-review
80 2019-11-09T21:04:37  *** HighOnBtc has joined ##taproot-bip-review
81 2019-11-09T21:18:01  *** b10c has joined ##taproot-bip-review
82 2019-11-09T21:42:54  *** mryandao_ has joined ##taproot-bip-review
83 2019-11-09T21:43:20  *** mryandao has quit IRC
84 2019-11-09T22:04:13  *** alon-e has joined ##taproot-bip-review
85 2019-11-09T23:17:14  *** HighOnBtc has quit IRC
86 2019-11-09T23:19:44  <nickler> waxwing: https://github.com/ElementsProject/secp256k1-zkp/pull/46/files#diff-286bf85b94befb0c9cf796503abf9f45 and https://www.youtube.com/watch?v=Wy5jpgmmqAg
87 2019-11-09T23:50:17  *** b10c has quit IRC
88 2019-11-09T23:51:12  <waxwing> nickler thanks