2 releases
0.1.2 | Oct 3, 2024 |
---|---|
0.1.0 | Sep 21, 2024 |
#26 in #on-chain
258 downloads per month
Used in solana-secp256k1-schnorr
49KB
719 lines
Solana Secp256k1
This crate leverages two Solana syscalls—big_mod_exp
(for Fermat's Little Theorem) and secp256k1_recover
—to create compute unit (CU)-efficient implementations of all the mathematical functions required to utilize the Secp256k1 curve for arbitrary on-chain cryptographic operations. Most notably, scalar tweaking and elliptic curve (EC) multiplication now cost just 25,000 CUs, a 200x reduction from their initial ~5,000,000 CU cost. This library supports highly performant versions of:
- Point compression
- Point decompression
- Point addition (ECAdd)
- Public key generation (MulG)
- Point multiplication (ECMul)
- Key tweaking (
ECAdd(P, MulG(scalar))
) - Negate scalar ( P )
- Negate scalar ( N )
- Modular inverse of ( P ) (Modinv ( P ))
- Modular inverse of ( N ) (Modinv ( N ))
Mathematical Explanation
Unlike the Ethereum implementation that applies a Keccak-256 hash and truncates the recovered point into an address, Solana's implementation of ecrecover
returns an uncompressed public key point. Therefore, the mathematical formula for ecrecover
on Solana can be defined as:
$Q = r^{-1}(s \cdot R - z \cdot G)$
where:
Q
is the recovered point.r
is the nonce.R
is a point with the x-coordinate ofr
and the y-coordinate defined by the recovery IDv
.z
is the hash scalar of the message we are "signing" 🙃️️️️️️.G
is the generator point.
The input parameters we can control are ( z ), ( v ), ( r ), and ( s ).
By leveraging this, we can utilize ecrecover
to perform a variety of cryptographic functions. For example:
ECMul (Elliptic Curve Multiplication)
To perform ECMul, we zero out the right-hand side of the equation by setting the hash scalar ( z = 0 ). This simplifies the formula to:
$Q = r^{-1}(s \cdot R)$
If we set ( s = k \cdot r ), we can eliminate the modular inverse, reducing the formula to:
$Q = k \cdot R$
Scalar Tweaking
We can expand upon the ECMul example by utilizing the right-hand side of the equation, ( -zG ). This term represents a MulG
operation, generating a public key point from a scalar value. By negating the input scalar and multiplying by ( r ) to cancel out the modular inverse, we reduce the formula to:
$Q = s \cdot R + z \cdot G$
This enables an efficient implementation of tweaked public keys.
Use Cases
This crate primarily enables efficient on-chain verification of Schnorr signatures and facilitates TapTweaks for on-chain Taproot address generation. This allows Solana not only to verify Bitcoin transactions but also to act as an MPC provider for transaction creation and liquidity management via on-chain Bitcoin wallets. Additionally, this library opens up possibilities for:
- Pedersen commitments
- On-chain ECDSA/Schnorr signing, enabling PDA signers on Bitcoin/Ethereum
- Ring signatures
- Bulletproofs
Disclaimer
While this library will be audited, remember to use it at your own risk.
TODO
- Auditing
- Reimplement point doubling method
- Improve ECAdd performance
- Enhance testing
- Optimize syscalls with
no_std
variants - Remove dependency on
solana-program
- Implement multiple compile targets for more efficient implementations in Rust/WASM
Dependencies
~19–29MB
~486K SLoC