Why does the all 0 public key have a known private key in SR25519 and ED25519?(substrate.stackexchange.com) |
Why does the all 0 public key have a known private key in SR25519 and ED25519?(substrate.stackexchange.com) |
There is a much more concise explanation than in the linked post: in Ristretto, the encoding of group elements was constructed so that the encoding of the identity (zero) element of the group is the all-zero byte string. So it’s not surprising that the all-zero byte string has a known private key: it’s the all-zero secret key.
This aspect of the encoding makes it very easy to check whether a provided group element is the identity element, because “zero means zero”.
What the questioner seems to be looking for is a way to generate “burn addresses”, public keys with the property that everyone can be sure that no one else knows the secret key to. This is actually kind of hard: if I just give you a public key, how do you know I didn’t generate it from a secret key I know?
The correct answer to this “nothing-up-my-sleeve” problem is to have a group-valued hash function, which Ristretto provides. Then public keys can be specified as the outputs of the hash function.
In a Pedersen commitment, you have two generators, let’s call them G_value and G_blinding. To commit to a value v, you choose a random blinding factor v_blinding and form the commitment C_v as
C_v = v * G_value + v_blinding * G_blinding
Later, you can publish (v, v_blinding) to open the commitment.
Pedersen commitments are really useful because they’re homomorphic: adding commitments produces a commitment to the sum of the values. So you can use them to do a limited form of computation on hidden data.
Where does the verifiable generation come in? Since G_value and G_blinding are both in the same prime-order group, there exists _some_ value r so that G_value = r * G_blinding. If someone knew this relation r, they could forge commitments, for instance
C_v = (v+1) * G_value + (v_blinding - r) * G_blinding
and claim that C_v is a commitment to the value v+1 instead, because knowledge of the relation r lets them “slide value” between the “basis vectors”.
So Pedersen commitments are only _computationally_ binding: finding r requires solving the discrete logarithm problem, which we assume is hard, as long as the generators G_value and G_blinding were generated through some verifiable procedure.
On the other hand, though, they’re perfectly hiding, since knowing r lets you find a valid blinding factor for _any_ value, so even an infinitely computationally powerful adversary can’t determine which value was used after the fact.
Is this sentence a mistake? A private key is a secret key.
The answer, I believe, is we have no way of doing that so far. The closest thing that exists is "multiparty" or "distributed" generation of an RSA modulus. Roughly, in the two party case of Alice and Bob, this means Alice picks some pair of numbers (P1, Q1) and Bob similarly picks some (P2, Q2). Then, Alice and Bob engage in some secure multiparty computation protocol whereby they obliviously a) check P1+P2 and Q1+Q2 are prime, and b) if so, output N=(P1+P2)(Q1+Q2) to both Alice and Bob.
At the end of the protocol (after repeating enough times that it succeeds), both parties have derived an N whose factorization they don't know.
I don't know much about this area of study, but searching multiparty RSA modulus generation should bring up relevant papers.
Some curves (eg: Ristretto) were designed to alleviate this problem.
[1] https://neilmadden.blog/2020/05/28/whats-the-curve25519-clam...
Curve25519 is a _curve_ that implements a non-prime order _group_. Ristretto255 is a prime-order _group_ that uses Curve25519 as an underlying _curve_.
In other words, Ristretto is a pair of encode/decode functions that map points on _curve25519_ to _ristretto group elements_ and vice versa. It's called "ristretto" because it's a restricted (specific to curve25519) version of Mike Hamburg's Decaf format that "reduces amount of coffee/cofactor by 4" for Edwards curves.
Like if you want to secretly know the private key of 0xDEADBEEF, set your generator to lift(0xDEADBEEF) x (1/$secret). Now the deadbeef pubkey has a DL relative to your generator of $secret.
If you understand this it becomes obvious why it is strange that people seem to be able to know the private key of the all 0 public key. Getting to that point on the curve would either require undoing the multiplication or brute force, both of which are not feasible assuming that ECC is not broken.
Without going to deep: the explanation of this penomenon is that ed25519 uses a different curve model (not Weierstrasser curves) where this logic does not completely apply due to special cases.
Considering that it is highly unlikely that this is a coincidence it is believed that the designers of the secp256k1 curve chose the generator point based on that value. They looked at that point (1/2, P) and then they defined the generator point G as 2*P.
* NOTE: don't try this at home. If you're not clever about this you will lose all your Bitcoins.
Bawolff's concise ELI5 comment helped though.
- If you remember RSA, ECC replaces RSA because it has better performance.
- In ECC, public keys are points on a curve. There's two main types of EC curves:
- A Weierstrass curve looks like a pimple (classical ECC) - you'll see this in older crypto systems.
- An Edwards curve looks like a butthole - more popular these days, as it has less 'exceptional cases' on the curve which don't confirm to normal 'add two points together to get a third point' maths.
- 'Ristretto' turns out to be the ECC-based key derivation algorithm used by Polkadot cryptocurrency: https://wiki.polkadot.network/docs/learn-cryptography or https://ristretto.group/ and is based on Edwards curves.
The second answer (typical for Stack Exchange sites) summarizes it well):
> In the Ristretto group, 0 is a member of the group, while in Secp256k1 it is not.
So here's my advice. If you multiplied too much by zero, you can make it less 0 by dividing a few times by zero. Then maths would be closer to the precise 0 that you were looking for in the first place.
Saving others a click:
> DES has a few specific keys termed "weak keys" and "semi-weak keys". These are keys that cause the encryption mode of DES to act identically to the decryption mode of DES
We used a partial homomorphic encryption system for it, but I’m sure we could’ve used a Pederson commitment if we tweaked how we approached it.
One factor though that the PoC never truly got rid of was a semi-trusted central system. We didn’t need to though, at the time. Would’ve been neat however!
In other words, the joke around coffee takes a 90º turn with Ristretto because our first application was Bulletproofs where you need (among other things) a lot of orthogonal generator points.
When encoding the public key, you give only one coordinate and possibly also a sign bit, and the other person uses the curve equation to solve for the other coordinate. Just like with a Weierstrass curve y^2 = x^3 + ax + b, you can solve for y using only x, plus one bit to say whether to take the positive or negative square root.
Technically, the zero-string encodes the identity element (0,1) for Ristretto, but not for Ed25519 where it's the point (i,0) where i = sqrt(-1). (Not (1,0) as the StackExchange claims, unless I'm very much mistaken. For Ed448 instead I believe it encodes (-1,0).) However the points (i,0) or (-1,0) are basically a rotation of (0,1). So for some protocols it works out that you can use 0 as the private key and it will work anyway.
Part of the point of Ristretto is to eliminate this sort of "gotcha" where certain public keys are equivalent. The way around it is that you pick a certain one of the equivalent points to encode, in a canonical way, and the other options are not valid encodings. This also means you don't need a sign bit: one of the criteria for choosing which rotation is that the sign bit would be zero.
Also: I did not use ChatGPT. Proof: Any native english speaker can tell you that my answers do not come from a native speaker. I don't think ChatGPT can mimic that (yet). English not being your first language can have its virtues.
Hmmm... true true. Simplifications are likely to miss the nuances involved.