bnb-chain / tss-lib

Threshold Signature Scheme, for ECDSA and EDDSA
MIT License
790 stars 271 forks source link

Fix a bug of addition law of elliptic curve groups #81

Closed cychuang0924 closed 9 months ago

cychuang0924 commented 4 years ago

I notice that the origin addition law has a bug. https://github.com/binance-chain/tss-lib/blob/883f207b38f0357d7a8c7fa957301c7a6f9b0848/crypto/ecpoint.go#L50

For example: Let N be the order of an elliptic curve group and G is a generator of the elliptic curve group. Then if you try to use "Add" to compute 2G+(N-2)G, then the output is an error.

This phenomenon will cause the following implementation which has possible failure. https://github.com/binance-chain/tss-lib/blob/883f207b38f0357d7a8c7fa957301c7a6f9b0848/ecdsa/keygen/round_3.go#L135

If you meet the case 2G+(N-2)G, then culprits is not empty. However, the case 2G+ (N-2)G
should be handled.

Following your nice codes, we recommend that

  1. Denote X()=nil and Y()=nil to be identity element in the elliptic curve group (i.e. aG+(nil, nil) = aG, for any a in [0,N-1]), which also implies that this point X()=nil and Y()=nil is on the curve. You can imaginary this point intercepting the elliptic curve at infinity.

  2. Add function should handle some special cases. After this modification, this "Add" can sum any two elements in elliptic curve groups including the following cases:

If you don't like my coding style, then you can rewrite it.

Well, some functions maybe also need to modify. For examples:

"FlattenECPoints", UnFlattenECPoints and so on.....

Thank you for your patience.

ZhAnGeek commented 9 months ago

@cychuang0924 Hi, thanks for submit fixes, could you fix the tests so we could merge?