--- Log opened Thu Jan 16 00:00:07 2020
00:14 -!- cfields [~cfields@unaffiliated/cfields] has quit [Remote host closed the connection]
00:15 -!- cfields [~cfields@unaffiliated/cfields] has joined #secp256k1
01:51 -!- belcher [~belcher@unaffiliated/belcher] has joined #secp256k1
02:09 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has quit [Quit: jonatack]
02:20 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has joined #secp256k1
02:54 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has quit [Ping timeout: 245 seconds]
04:10 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has quit [Remote host closed the connection]
04:11 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has joined #secp256k1
04:14 -!- jonatack [~jon@37.173.53.30] has joined #secp256k1
05:17 -!- jonatack [~jon@37.173.53.30] has quit [Ping timeout: 258 seconds]
06:46 -!- benma [~benma@178.197.224.136] has joined #secp256k1
06:46 -!- benma [~benma@178.197.224.136] has quit [Changing host]
06:46 -!- benma [~benma@unaffiliated/benma] has joined #secp256k1
06:47 < benma> hi everyone, just a quick question:
06:47 < benma> static void secp256k1_fe_normalize(secp256k1_fe *r);
06:47 < benma> what does this function do exactly? the docstring is not descriptive enough
06:50 < sipa> benma: it normalizes a field element :)
06:50 < sipa> that means bring it to a canonical representation
06:50 < sipa> and bring its magnitude (a measure for how denormalized it is...) to 1
06:51 < sipa> the denormalization here refers to how much the field elements exceed their usual size
06:51 < sipa> on 64 bit platforms eg field elenents are represented as 5 52-bit integers
06:51 < sipa> they're denormalized when their top 12 bits are nonzero
06:54 < benma> i see, thanks!
06:55 < benma> what's the purpose of having a canonical representation? byte-wise comparison?
06:55 < sipa> and serialization
06:56 < sipa> normalization (at leazt the strongest form) also reduces numbers between 2^256 - 2^32 - 977 (= field size p) and 2^256 by subtracting p
06:57 < benma> the type `secp256k1_fe *r` already implies it is smaller than p, or not?
06:59 < benma> actually I am asking because I am reading those lines: https://github.com/bitcoin-core/secp256k1/blob/074ab582ddb9085611cba8a0495828dadb645345/src/ecdsa_impl.h#L234-L237
07:01 < benma> is the normalization step needed there? shouldn't it be reduced modulo n instead before being loaded into the scalar `computed_r`?
07:02 < sipa> benma: field elements nominally represent integers between 0 and p-1
07:02 < sipa> but they're not necessarily as such
07:04 < sipa> benma: normalization is effectively reducing modulo n, and bringing to canonical representation
07:06 < elichai2> benma: as an optimization `secp256k1_fe` technically can go over the field size. what normalization does is take it to be between 0 and p-1 and makes it use the right amount of uint32/64 such that it can then serialize it into *32 bytes*
07:06 < sipa> it's not called that way as field elements are not integers, they're elememts of Z/Zp
07:06 < benma> "normalization is effectively reducing modulo n," => did you mean modulo p?
07:06 < sipa> yes, p
07:06 < sipa> they're just internally represented as integers in base 2^52
07:07 < benma> so where in those lines is "modulo n" taking place? https://github.com/bitcoin-core/secp256k1/blob/074ab582ddb9085611cba8a0495828dadb645345/src/ecdsa_impl.h#L231-L237
07:07 < elichai2> (an example of the optimization is that ie if you have a = p-1 and you do a+=3 then there's no need to reduce modulo because you might soon do a-=4 or something like that)
07:07 < sipa> benma: in the normalization
07:07 < elichai2> benma: it's modulo p not n :)
07:08 < benma> am i mixing up my groups/fieldS? in ecdsa verification, one is comparing (modulo n), where n is the group order?
07:09 < sipa> field elements (secp256k1_fe) are modulo p
07:09 < elichai2> well `r` is the Y coordinate of R(nonce point), so it's a field (modulo p - the field size) not a scalar(modulo n - the group order)
07:09 < elichai2> *the X coordinate
07:10 < benma> looking at https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
07:10 < benma> 5. Calculate r = x1 (mod n)
07:12 < benma> with `n` defined as "integer order of G", so group order
07:12 < benma> is there a mismatch in terminology or in implementation?
07:14 < elichai2> hmm it appears that when signed you reduce r mod n, even though r is a fe
07:14 < benma> yeah, just trying to understand if i am reading the code wrong or where the source of my confusion is ;)
07:14 < benma> maybe practically speaking, the values are not gonna be between `n` and `p`, so even the wrong reduction has no practical impact?
07:14 < elichai2> you can see the code here: https://github.com/bitcoin-core/secp256k1/blob/master/src/ecdsa_impl.h#L284:L289 `b is r as a field element, and then it's copied into r as a scalar`
07:16 < elichai2> lines 291, 292 require that r wasn't between n and p. I'm not sure though how that requirement is a thing and why
07:17 < benma> looks to me like technically speaking it should be reduced modulo n, but in practice the probability is near 0 for this to happen, so why bother?
07:17 < benma> sipa: is that a correct assesment?
07:20 < elichai2> quick calc shows the stats of hitting between the field and the order is 3.73...*10^-39 or 1/2^127.65 but I it's not a random variable so is that the right way to look at it? are there any properties at play here?
07:21 < benma> actually the function calling this loops until it works: https://github.com/bitcoin-core/secp256k1/blob/master/src/secp256k1.c#L476
07:21 < benma> that is the signing part, but in the verification lines the question remains: https://github.com/bitcoin-core/secp256k1/blob/master/src/ecdsa_impl.h#L231-L238
07:22 < elichai2> well obviously the verification remains if that a requirement of signing
07:22 < elichai2> the loop just means it chooses a different nonce which now makes some sense
07:23 < elichai2> I still don't get *why* it needs to be mod n but it makes sense to loop  if it's not
07:23 < benma> true, wonder where "    /* These two conditions should be checked before calling */" is done :P
07:24 < benma> VERIFY_CHECK is also disabled unless in tests
07:25 < elichai2> how could they be checked? that requires multiplying by G
07:26 < elichai2> I also wonder if we know the DLG of a point with field elements between p and n, i'll assume not unless again there's some deep properties at play here
07:32 < elichai2> benma: I thought we agreed it does do "modulo n" in signing and verification
07:35 < benma> no, that was modulo p?
07:35 < elichai2> see https://github.com/bitcoin-core/secp256k1/blob/master/src/ecdsa_impl.h#L284:L289 again. it serializes `sigr` and then put it into a scalar which is mod n
07:36 < benma> are you saying that `secp256k1_scalar_set_b32` automatically reduces modulo n?
07:36 < elichai2> not directly, but when it's in a scalar it means all operations on it are mod n
07:36 < elichai2> so kind of yes
07:37 < elichai2> wait, it automatically reduce. yes.
07:37 < elichai2> it will right 1 into the `overflow` variable if it was above n
07:38 < benma> the docstrings really need to be improved ;) current one is "/** Set a scalar from a big endian byte array. */"
07:39 < benma> but if it reduces it's clear,yes
07:39 < elichai2> the docstring generally aren't very helpful to someone who isn't familiar with the library
07:39 < elichai2> IMHO
07:40 < elichai2> took me a lot of time to understand the meaning and purpose of every function here
07:43 < benma> thanks for clarifiyng, now it makes a lot more sense!
07:49 < elichai2> glad to be of help
07:54 < benma> added https://github.com/bitcoin-core/secp256k1/pull/713 to help clarify it for the next person
08:01 < sipa> benma: the conversion to scalar will reduce mod n
08:01 < sipa> as scalars are defined as elements of Z/Zn
08:01 < benma> nice!
08:03 < benma> then i think i'll turn commitment_ge.x into a scalar and use `secp256k1_scalar_set_b32` over `memcmp` here: https://github.com/bitcoin-core/secp256k1/pull/669/files#diff-b3ef116529fa0f4b8dbfabca7ba7b82eR64
08:04 < benma> s/secp256k1_scalar_set_b32/secp256k1_scalar_eq
08:52 -!- benma [~benma@unaffiliated/benma] has quit [Remote host closed the connection]
09:49 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has quit [Ping timeout: 260 seconds]
09:59 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1
10:58 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has joined #secp256k1
17:26 -!- belcher [~belcher@unaffiliated/belcher] has quit [Quit: Leaving]
19:55 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1
21:48 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection]
23:13 -!- ariard_ [~ariard@167.99.46.220] has joined #secp256k1
23:18 -!- Netsplit *.net <-> *.split quits: Madars, ariard, ensign
--- Log closed Fri Jan 17 00:00:09 2020