Closed kclowes closed 2 years ago
👋 @ChihChengLiang! I tagged you because Piper said you know the math behind this really well. If you could please take a look to make sure these changes make sense, that would be great!
I think two bugs are introduced with this PR, below I put the rationale.
TLDR
(Note: I use the term point at infinity, quite loosely below and it should instead be distinguished point since before this PR, those points were not the points at infinity)
Assumptions
1) The points at infinity, act as the identity element in the group. This means that given a point P, P + POINT_AT_INFINITY = P
2) Previously, the code checked for the point at infinity by checking the second component of the Jacobian Point to be 0
Evidence for second assumption
See:
If you check the jacobian_add method (2nd link), where we are adding two points p
and q
, the code checks the second component of p
using if not p[1]
and on this condition, it returns q
. According to the first assumption I made, this is only true, if p
is the point identity element. So that if statement is a way of checking for the point at infinity / identity element.
a
with the scalar n
, the code first checks the second component of a
using if a[1] == 0
, if this is the case then it returns the identity point. This code is essentially saying, if the point is the identity point/ point at infinity, just return it because doing a scalar multiplication with the identity point/point at infinity always returns the identity point. So both if statements check the second component of the jacobian point, and if it is zero, it says "this is the point at infinity/identity point" judging by what it does on those conditions.
Pre PR
Before the PR was merged, since the points at infinity were represented using either (0,0,0) or (0,0,1), the check above would work.
Note this check implicitly assumes that any point whose second component is 0, is the identity point, I haven't checked any further into assumption, I just assumed it held true.
Bug
If you agree with the above rationale, then I think the first bug was introduced because you now represent the point at infinity using the constant (1,1,0) .
See here: https://github.com/kclowes/eth-keys/blob/ecrecover-point-at-infinity/eth_keys/constants.py#L20
But the logic to check for the point at infinity is still to check for the second component, which is not zero using that constant.
The second bug is because using the representation that you chose, the points at infinity is now a set of points (t^2, t^3, 0) where t !=0. This is in the stack overflow post accompanied with this PR above. This means that the if point == POINT_AT_INFINITY
check would not be enough, since it is only checking for one particular representation of the point at infinity, when t = 1, but AFAICT there are no guarantees that this will be the representation that you will get after doing a sequence of point arithmetics.
Testing for bug
Something like the below code
result = POINT_AT_INFINITY
for i in range(0,100):
result = jacobian_add(result, POINT_AT_INFINITY)
assert result == POINT_AT_INFINITY
P
and check that the result is P
, where P
is not the point at infinity.If I understand your changes, then the two tests should fail.
Suggestion
The code was failing because the ecdsa recover was not checking for the points at infinity IIUC. If we assume that the library is correct in just checking for the second component, then you would only need to check this too in the ecdsa_recover method. You could also explicitly check for the two internal representations being used.
I'd probably add a method called is_identity(p: Tuple[int, int, int]) -> bool
that conveys the fact that you are checking for the identity point and abstracts away the implementation details.
@kclowes Sorry I didn't finish my review in time. I think @kevaundray summarized the issue thoroughly.
Thanks for the review @kevaundray! I think I fixed the bugs you pointed out, but would appreciate if you could take another look.
If we assume that the library is correct in just checking for the second component, then you would only need to check this too in the ecdsa_recover method. You could also explicitly check for the two internal representations being used.
Is there a way that seems more correct? If the y-coordinate of point Q from here is 0, does that always correspond to an identity point?
@carver - would appreciate another look as well when you have a few!
What was wrong?
ecdsa_recover
returned a public address even if the Jacobian transformation returned an invalid point (the point at infinity). This behavior was inconsistent with other clients. See: https://github.com/ethereum/tests/issues/941#Once this is merged and released, we'll need to update
eth-account
andpy-evm
.How was it fixed?
Replaced points in the Jacobian files that were meant to represent the points at infinity with the more commonly used representations. And now the
ecdsa_recovery
method checks to see ifQ
is a point at infinity and raises an error to be more consistent with Geth's ecrecover.I went back and forth deciding whether to tack on an
is_infinity
flag to the point at infinity representation, but ultimately decided to go with the simple solution for now. I'm open to adding anis_infinity
flag though if anyone else feels strongly.Cute Animal Picture