Docs: Remove need for libsecp256k1 dependency in example low-S code

[deanmlittle]

Problem

Current secp256k1 low-S code example asserts that you must add the dependency of libsecp256k1 to your Solana program to validate low S. This is not true. There is a much cheaper, simpler solution that is commonly used in both Bitcoin and Ethereum which is to simply pre-calculate curve order N/2 and do a simple integer comparison.

Sources: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/cryptography/ECDSA.sol#L137

https://github.com/bitcoin-core/secp256k1/blob/master/include/secp256k1.h#L611

Summary of Changes

• Changed code example in docs to reflect an efficient method of detecting high S values in secp256k1 ecdsa signatures without the added dependency of libsecp256k1

Fixes #

[deanmlittle]

Is there anything I could do here to better explain what's going so we can merge this? It doesn't affect any actual code as it is documentation-only, and offers a significant cost reduction by removing a very expensive dependency with a much simpler solution that is commonly used on many other chains. I think it is worth merging.

[seanyoung]

The change looks superficially good but it needs to be correct advice. Where does the example code even come from? Also, it would be great to have @samkim-crypto review on this.

[deanmlittle]

The change looks superficially good but it needs to be correct advice. Where does the example code even come from? Also, it would be great to have @samkim-crypto review on this.

I wrote the example code myself. It is tested and working. I also posted an example of how OpenZeppelin, a collection of some of the most trusted open source contracts in the EVM ecosystem, accomplish the same thing in Solidity:

https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/cryptography/ECDSA.sol#L137

As you can see, it's just a simple u256 integer comparison. It does not require any EC maths or anything like that. We're doing a modular integer comparison here instead of adding the dependency of an external type like u256 or BigInteger, but it's fundamentally the same idea.

As a long-term Bitcoin developer, I would argue this is quite a well-known convention to anyone in Bitcoin and Ethereum with a functional understanding of ECDSA. I hope we could encourage its use on Solana to make S malleability mitigation more efficient.

[seanyoung]

I agree the change does look nice. It would be nice to have a cryptographers view on it (hence @samkim-crypto is in the reviewers).

Also it would be nice to have some actual code rather than a commented out piece, so it can have a test case. If this is subtlety wrong then it could spell disaster.

[deanmlittle]

I agree the change does look nice. It would be nice to have a cryptographers view on it (hence @samkim-crypto is in the reviewers).

Also it would be nice to have some actual code rather than a commented out piece, so it can have a test case. If this is subtlety wrong then it could spell disaster.

gm. if you would like a test written in the actual sdk, that could be arranged too:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=7734d12a03c9d5d1d89bde1519d6d716

[willhickey]

This repository is no longer in use. Please re-open this pull request in the agave repo: https://github.com/anza-xyz/agave