Why are you guys spamming the SDC thread and Slack?
I don't see any spamming in the thread... I posted the 'fix' to SDCs anonymity bug because it concerns SDC, does it not?
What I posted is very relevant to SDC. It's not like I was talking about rainbows and butterflies.
SDC looks to be converging on a reasonable fix, but not a recommended one.
Originally, they took the scalar hash then multiplied it by the private key and then used it for the scalar multiple of the group generator (two different types of "multiply" here but I didn't invent this convention). Math looks like
I = H(K_i)xG
That was the very wrong way.
Now they take an arbitrary point on the curve by hashing the time stamp, trying to map it to a point, then using that point as a generator. This takes advantage of the fact that all curve points on a prime field can be full generators. The new generator is G*
I = H(K_i)xG*
There is a relationship between G and G*, namely one is a multiple of the of the other:
G = aG*
But in this case G* is "unknown log", so G is protected by discrete log hardness.
In general, however, it is not good to try to use a generator to hash scalars to a curve. They already learned this lesson once.
The fact that $G$ = $aG^*$ is but a little lemma whose proof that I found in the margins of my notebook.
I will use the additive notation, since this is what is used for Elliptic Curves, but it's just a convention. Multiplicative notation is just as fine.
Lemma *: Let $K$ be a cyclic group of order $n$. Let $G$ be a generator of $K$, i.e. $<G> = K$. Then, $\forall H \in K \exists a \in \{0, \dots, n-1\}$ such that $aG = H$.
Proof: Assume $K$ is a cyclic group of order $n$ and $G$ generates $K$ and let $H \in K$. By definition of cyclic groups, since $G$ generates $K$, there exists an integer $a \in \{0, \dots, n-1\}$ such that $aG = H$. -- see
https://en.wikipedia.org/wiki/Cyclic_group .
Q.E.D. of Lemma *.
Now, since the elliptic curve that is secp256k1 is a group whose order is a prime, then it is a cyclic group. This is because all groups that have prime order are cyclic -- for a proof, see :
http://planetmath.org/proofthateverygroupofprimeorderiscyclic. For some clarification that secp256k1 has prime order, see :
http://bitcoin.stackexchange.com/questions/38108/order-of-group-of-points-of-secp256k1 and the answer by Akater which references the documents defining standard curves, for instance SECG --
http://www.secg.org/sec2-v2.pdf -- to which secp256k1 belongs.
Therefore, by (*), $G = aG^*$ is true.
I'm a bit lost, are you saying that SDC testnet fix is valid?
The other dev is just clarifying mathematically where I asserted the relationship G = aG*, and showing how it is valid.
That was actually a response to a post on the SDC thread where someone without much math knowledge was questioning what I said.
You can't respond to them in their thread or you will get deleted.
So our other dev decided just to do it here. He proved the relationship holds for all group elements G* over a prime field because G is a generator for the group. Our other dev is a real precise mathy-type who doesn't let anything go in the way of math reasoning.
Oh,
and to answer your question, I said "G is protected by discrete log hardness". So the exploit that de-anoned their chain in the first place is now protected by a cryptographically hard problem. However, I also observed that the way they are doing it (maybe to save CPU cycles) is not advisable in general. I can show a couple of reasons why.
Here's essentially where they pick their generator in their current plan:
uint256 hash = Hash(Params().pszTimestamp, Params().pszTimestamp + strlen(Params().pszTimestamp));
What's this do? It takes the hash of the same time stamp string used for the genesis hash and will use it to map to a generator.
Then this generator is used for every ring signature in the entire block chain.
Now, if, for some reason anyone ever solves
a for
G =
aG*
Then the whole system comes crashing down. Every signature will be deanoned. Period.
You may be thinking that the discrete log problem holds here and you would be right. But, on the most practical level it is a single point of failure. Of lesser potential issue is why did they pick that timestamp? There are zillions of seemingly obvious strings and numbers that could be used to seed the generator. Why not the name of the coin, why not "Satoshi Nakamora", why not "Alan Turing", etc. etc? Admittedly this second potential for nefarious intent is far-fetched, but it exists nonetheless, and is a valid cyptographic concern because it leaves some wiggle room that compromises the "rigidity" of the crypto system.
Our system has neither this single point of failure nor arbitrary parameter.
I'll further add that this seemingly simple solution used by shadowcash undoubtedly occurred to the creators of cryptonote. Why didn't the cryptonote devs use this solution of a generator with "unknown" log? Why would they not want to make their system save CPU cycles and further find the group point in constant time? Why did they use a curve where they could solve the root (or find a residue for the root they found)?
These are rhetorical questions, but very important to ask.
