secp256k1

Pure Haskell Schnorr, ECDSA on the elliptic curve secp256k1 (docs.ppad.tech/secp256k1).
git clone git://git.ppad.tech/secp256k1.git
Log | Files | Refs | README | LICENSE

README.md (8960B)


      1 # secp256k1
      2 
      3 [![](https://img.shields.io/hackage/v/ppad-secp256k1?color=blue)](https://hackage.haskell.org/package/ppad-secp256k1)
      4 ![](https://img.shields.io/badge/license-MIT-brightgreen)
      5 [![](https://img.shields.io/badge/haddock-secp256k1-lightblue)](https://docs.ppad.tech/secp256k1)
      6 
      7 A pure Haskell implementation of [BIP0340][bp340] Schnorr signatures,
      8 deterministic [RFC6979][r6979] ECDSA (with [BIP0146][bp146]-style
      9 "low-S" signatures), ECDH, and various primitives on the elliptic curve
     10 secp256k1.
     11 
     12 (See also [ppad-csecp256k1][csecp] for FFI bindings to
     13 bitcoin-core/secp256k1.)
     14 
     15 ## Usage
     16 
     17 A sample GHCi session:
     18 
     19 ```
     20   > -- pragmas and b16 import for illustration only; not required
     21   > :set -XOverloadedStrings
     22   > :set -XBangPatterns
     23   > import qualified Data.ByteString.Base16 as B16
     24   >
     25   > -- import qualified
     26   > import qualified Crypto.Curve.Secp256k1 as Secp256k1
     27   >
     28   > -- secret, public keys
     29   > let sec = 0xB7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF
     30   :{
     31   ghci| let Just pub = Secp256k1.parse_point . B16.decodeLenient $
     32   ghci|       "DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659"
     33   ghci| :}
     34   >
     35   > let msg = "i approve of this message"
     36   >
     37   > -- create and verify a schnorr signature for the message
     38   > let sig0 = Secp256k1.sign_schnorr sec msg mempty
     39   > Secp256k1.verify_schnorr msg pub sig0
     40   True
     41   >
     42   > -- create and verify a low-S ECDSA signature for the message
     43   > let sig1 = Secp256k1.sign_ecdsa sec msg
     44   > Secp256k1.verify_ecdsa msg pub sig1
     45   True
     46   >
     47   > -- for faster signs (especially w/ECDSA) and verifies, use a context
     48   > let !tex = Secp256k1.precompute
     49   > Secp256k1.verify_schnorr' tex msg pub sig0
     50   True
     51 ```
     52 
     53 ## Documentation
     54 
     55 Haddocks (API documentation, etc.) are hosted at
     56 [docs.ppad.tech/secp256k1][hadoc].
     57 
     58 ## Performance
     59 
     60 The aim is best-in-class performance for pure, highly-auditable Haskell
     61 code.
     62 
     63 Current benchmark figures on a relatively-beefy NixOS VPS look like
     64 (use `cabal bench` to run the benchmark suite):
     65 
     66 ```
     67   benchmarking schnorr/sign_schnorr'
     68   time                 2.584 ms   (2.491 ms .. 2.646 ms)
     69                        0.994 R²   (0.991 R² .. 0.997 R²)
     70   mean                 2.459 ms   (2.426 ms .. 2.492 ms)
     71   std dev              114.5 μs   (95.32 μs .. 142.8 μs)
     72 
     73   benchmarking schnorr/verify_schnorr'
     74   time                 1.283 ms   (1.263 ms .. 1.301 ms)
     75                        0.999 R²   (0.998 R² .. 0.999 R²)
     76   mean                 1.273 ms   (1.260 ms .. 1.284 ms)
     77   std dev              41.56 μs   (31.12 μs .. 54.35 μs)
     78 
     79   benchmarking ecdsa/sign_ecdsa'
     80   time                 222.6 μs   (219.9 μs .. 224.9 μs)
     81                        0.999 R²   (0.999 R² .. 1.000 R²)
     82   mean                 219.1 μs   (217.8 μs .. 220.5 μs)
     83   std dev              4.523 μs   (3.525 μs .. 6.158 μs)
     84 
     85   benchmarking ecdsa/verify_ecdsa'
     86   time                 1.267 ms   (1.260 ms .. 1.276 ms)
     87                        1.000 R²   (1.000 R² .. 1.000 R²)
     88   mean                 1.278 ms   (1.273 ms .. 1.286 ms)
     89   std dev              21.32 μs   (15.43 μs .. 30.82 μs)
     90 ```
     91 
     92 In terms of allocations, we get:
     93 
     94 ```
     95 schnorr
     96 
     97   Case                   Allocated  GCs
     98   sign_schnorr'          3,273,824    0
     99   verify_schnorr'        1,667,360    0
    100 
    101 ecdsa
    102 
    103   Case                 Allocated  GCs
    104   sign_ecdsa'            324,672    0
    105   verify_ecdsa'        3,796,328    0
    106 
    107 ecdh
    108 
    109   Case          Allocated  GCs
    110   ecdh (small)  2,141,736    0
    111   ecdh (large)  2,145,464    0
    112 ```
    113 
    114 ## Security
    115 
    116 This library aims at the maximum security achievable in a
    117 garbage-collected language under an optimizing compiler such as GHC, in
    118 which strict constant-timeness can be [challenging to achieve][const].
    119 
    120 The Schnorr implementation within has been tested against the [official
    121 BIP0340 vectors][ut340], and ECDSA and ECDH have been tested against
    122 the relevant [Wycheproof vectors][wyche], so their implementations
    123 are likely to be accurate and safe from attacks targeting e.g. faulty
    124 nonce generation or malicious inputs for signature or public key
    125 parameters. Timing-sensitive operations, e.g. elliptic curve scalar
    126 multiplication, have been explicitly written so as to execute
    127 *algorithmically* in time constant with respect to secret data, and
    128 evidence from benchmarks supports this:
    129 
    130 ```
    131   benchmarking derive_pub/sk = 2
    132   time                 1.513 ms   (1.468 ms .. 1.565 ms)
    133                        0.994 R²   (0.991 R² .. 0.997 R²)
    134   mean                 1.579 ms   (1.557 ms .. 1.600 ms)
    135   std dev              74.25 μs   (60.33 μs .. 93.80 μs)
    136 
    137   benchmarking derive_pub/sk = 2 ^ 255 - 19
    138   time                 1.571 ms   (1.530 ms .. 1.599 ms)
    139                        0.997 R²   (0.995 R² .. 0.998 R²)
    140   mean                 1.574 ms   (1.553 ms .. 1.589 ms)
    141   std dev              57.72 μs   (45.29 μs .. 71.48 μs)
    142 
    143   benchmarking schnorr/sign_schnorr' (small)
    144   time                 2.436 ms   (2.357 ms .. 2.516 ms)
    145                        0.995 R²   (0.994 R² .. 0.998 R²)
    146   mean                 2.563 ms   (2.532 ms .. 2.588 ms)
    147   std dev              95.87 μs   (71.98 μs .. 127.2 μs)
    148 
    149   benchmarking schnorr/sign_schnorr' (large)
    150   time                 2.470 ms   (2.372 ms .. 2.543 ms)
    151                        0.993 R²   (0.989 R² .. 0.997 R²)
    152   mean                 2.407 ms   (2.374 ms .. 2.443 ms)
    153   std dev              123.7 μs   (110.7 μs .. 144.9 μs)
    154 
    155   benchmarking ecdsa/sign_ecdsa' (small)
    156   time                 206.9 μs   (202.7 μs .. 211.8 μs)
    157                        0.997 R²   (0.996 R² .. 0.999 R²)
    158   mean                 213.8 μs   (211.5 μs .. 215.9 μs)
    159   std dev              7.476 μs   (5.572 μs .. 9.698 μs)
    160 
    161   benchmarking ecdsa/sign_ecdsa' (large)
    162   time                 216.7 μs   (211.6 μs .. 221.7 μs)
    163                        0.997 R²   (0.995 R² .. 0.999 R²)
    164   mean                 221.8 μs   (219.5 μs .. 224.1 μs)
    165   std dev              7.673 μs   (6.124 μs .. 10.69 μs)
    166 
    167   benchmarking ecdh/ecdh (small)
    168   time                 1.623 ms   (1.605 ms .. 1.639 ms)
    169                        0.999 R²   (0.998 R² .. 1.000 R²)
    170   mean                 1.617 ms   (1.603 ms .. 1.624 ms)
    171   std dev              32.52 μs   (20.66 μs .. 55.97 μs)
    172 
    173   benchmarking ecdh/ecdh (large)
    174   time                 1.623 ms   (1.580 ms .. 1.661 ms)
    175                        0.996 R²   (0.992 R² .. 0.998 R²)
    176   mean                 1.625 ms   (1.606 ms .. 1.641 ms)
    177   std dev              58.38 μs   (44.31 μs .. 78.23 μs)
    178 ```
    179 
    180 Due to the use of arbitrary-precision integers, integer division modulo
    181 the elliptic curve group order does display persistent substantial
    182 timing differences on the order of 2 nanoseconds when the inputs differ
    183 dramatically in size (here 2 bits vs 255 bits):
    184 
    185 ```
    186   benchmarking remQ (remainder modulo _CURVE_Q)/remQ 2
    187   time                 27.44 ns   (27.19 ns .. 27.72 ns)
    188                        1.000 R²   (0.999 R² .. 1.000 R²)
    189   mean                 27.23 ns   (27.03 ns .. 27.43 ns)
    190   std dev              669.1 ps   (539.9 ps .. 860.2 ps)
    191 
    192   benchmarking remQ (remainder modulo _CURVE_Q)/remQ (2 ^ 255 - 19)
    193   time                 29.11 ns   (28.87 ns .. 29.33 ns)
    194                        0.999 R²   (0.999 R² .. 1.000 R²)
    195   mean                 29.04 ns   (28.82 ns .. 29.40 ns)
    196   std dev              882.9 ps   (647.8 ps .. 1.317 ns)
    197 ```
    198 
    199 This represents the worst-case scenario (real-world private keys will
    200 never differ so extraordinarily) and is likely to be well within
    201 acceptable limits for all but the most extreme security requirements.
    202 But because we don't make "hard" guarantees of constant-time execution,
    203 take reasonable security precautions as appropriate. You shouldn't
    204 deploy the implementations within in any situation where they could
    205 easily be used as an oracle to construct a [timing attack][timea],
    206 and you shouldn't give sophisticated malicious actors [access to your
    207 computer][flurl].
    208 
    209 If you discover any vulnerabilities, please disclose them via
    210 security@ppad.tech.
    211 
    212 ## Development
    213 
    214 You'll require [Nix][nixos] with [flake][flake] support enabled. Enter a
    215 development shell with:
    216 
    217 ```
    218 $ nix develop
    219 ```
    220 
    221 Then do e.g.:
    222 
    223 ```
    224 $ cabal repl ppad-secp256k1
    225 ```
    226 
    227 to get a REPL for the main library.
    228 
    229 [bp340]: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
    230 [ut340]: https://github.com/bitcoin/bips/blob/master/bip-0340/test-vectors.csv
    231 [bp146]: https://github.com/bitcoin/bips/blob/master/bip-0146.mediawiki
    232 [r6979]: https://www.rfc-editor.org/rfc/rfc6979
    233 [nixos]: https://nixos.org/
    234 [flake]: https://nixos.org/manual/nix/unstable/command-ref/new-cli/nix3-flake.html
    235 [hadoc]: https://docs.ppad.tech/secp256k1
    236 [wyche]: https://github.com/C2SP/wycheproof
    237 [timea]: https://en.wikipedia.org/wiki/Timing_attack
    238 [flurl]: https://eprint.iacr.org/2014/140.pdf
    239 [const]: https://www.chosenplaintext.ca/articles/beginners-guide-constant-time-cryptography.html
    240 [csecp]: https://git.ppad.tech/csecp256k1