Public Keys
Public keys are nothing more or less than a point on Elliptic Curve, represented by (x, y), uncompressed public keys are represented in HEX format as 0 4 x y, 04 is to represent that it is uncompressed, in totality it is of 520 bits, not much for a single Public Key but adds a lot of data when you add several hundred transactions per block, or tens of thousands of transactions per day.
Compressed Public Keys
In bitcoin blockchain compressed public keys are represented by 0 2 x if y is even, else 0 3 x.
Wait but why odd, even, why not negative and positive? y has 2 similar values with opposite signs for each x according to the elliptic curve, right ?
When I imagine secp256k1's elliptic curve y^2 = x^3 + 7, I see a smooth curve perfect in my head and I bet so do you, hence the above question makes sense, but the curve is actually defined in a finite field of some prime P, y^2 = (x^3 + 7) % P, a more formal way to put this is, secp256k1 is defined over the field Zp such that P = 2256 - 232 - 29 - 28 - 27 - 26 - 24 - 1.
food for thought, what do you think about the symmetricity of the image on right? is it symmetric about x axis ? what about y axis ? what about a line passing parallel to x half way up y? read more about finite fields and what do they actually do.
Yeah I know the truth is ugly, the continuity is destroyed once in a finite field, we will dig in deep into why and what of finite field in some other blog, for now take it for granted, it is just modulo P.
Once in a finite field for every x, there will be two solutions, f(x) and P-f(x), and if one is odd other will be even and vice versa, so now you know, try to think why both will have different parities as an exercise.
Now since we are using compressed public keys, we will use them to derive uncompressed ones, which is the y, question arises how to decompress a public key, or how to find y when x is given.
we have y^2 = (x^3 + 7) % P, we need to find the square root of (x^3 + 7) % P, first we need to find whether there exists solution or not, by euler's criterian x^3+7 has a square root mod P iff (x^3 + 7)^(P - 1) / 2 % P = 1, if this condition is satisfied we have solution.
By tonelli-Shanks algorithm, which is used in modular arithmetic to solve for r in a congruence of the form r^2 = n(mod P), where P is a prime, for primes such that for P % 4 == 3, (P + 1) % 4 == 0, by fermat's little theorem r^P = r % P, r^(P + 1) = r^2 % P, r^(1/2) % P = r^(P + 1) / 4, since we know that (P+1) % 4 == 0, (P + 1) / 4 is integer.
So r^(1/2) % P has one solution r^(P + 1) / 4 and other as P - r^(P + 1) / 4.
So there you have it, when given 0 2 x find both values of y and choose the even y, and that of 0 3 x is odd y.
This compression technique allows us to store only the x coordinate of the public key point, omitting the y coordinate and reducing the size of the key and the space required to store it by 256 bits. An almost 50% reduction in size in every transaction adds up to a lot of data saved over time!