README.md (8016B)
1 # ppad-secp256k1 2 3 A pure Haskell implementation of [BIP0340][bp340] Schnorr signatures 4 and deterministic [RFC6979][r6979] ECDSA (with [BIP0146][bp146]-style 5 "low-S" signatures) on the elliptic curve secp256k1. 6 7 (See also [ppad-csecp256k1][csecp] for FFI bindings to 8 bitcoin-core/secp256k1.) 9 10 ## Usage 11 12 A sample GHCi session: 13 14 ``` 15 > -- pragmas and b16 import for illustration only; not required 16 > :set -XOverloadedStrings 17 > :set -XBangPatterns 18 > import qualified Data.ByteString.Base16 as B16 19 > 20 > -- import qualified 21 > import qualified Crypto.Curve.Secp256k1 as Secp256k1 22 > 23 > -- secret, public keys 24 > let sec = 0xB7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF 25 :{ 26 ghci| let Just pub = Secp256k1.parse_point . B16.decodeLenient $ 27 ghci| "DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659" 28 ghci| :} 29 > 30 > let msg = "i approve of this message" 31 > 32 > -- create and verify a schnorr signature for the message 33 > let sig0 = Secp256k1.sign_schnorr sec msg mempty 34 > Secp256k1.verify_schnorr msg pub sig0 35 True 36 > 37 > -- create and verify a low-S ECDSA signature for the message 38 > let sig1 = Secp256k1.sign_ecdsa sec msg 39 > Secp256k1.verify_ecdsa msg pub sig1 40 True 41 > 42 > -- for faster signs (especially w/ECDSA) and verifies, use a context 43 > let !tex = Secp256k1.precompute 44 > Secp256k1.verify_schnorr' tex msg pub sig0 45 True 46 ``` 47 48 ## Documentation 49 50 Haddocks (API documentation, etc.) are hosted at 51 [docs.ppad.tech/secp256k1][hadoc]. 52 53 ## Performance 54 55 The aim is best-in-class performance for pure, highly-auditable Haskell 56 code. 57 58 Current benchmark figures on my mid-2020 MacBook Air look like (use 59 `cabal bench` to run the benchmark suite): 60 61 ``` 62 benchmarking schnorr/sign_schnorr' 63 time 2.557 ms (2.534 ms .. 2.596 ms) 64 0.998 R² (0.997 R² .. 0.999 R²) 65 mean 2.579 ms (2.556 ms .. 2.605 ms) 66 std dev 83.75 μs (69.50 μs .. 100.5 μs) 67 68 benchmarking schnorr/verify_schnorr' 69 time 1.429 ms (1.381 ms .. 1.482 ms) 70 0.993 R² (0.987 R² .. 0.998 R²) 71 mean 1.372 ms (1.355 ms .. 1.396 ms) 72 std dev 67.72 μs (50.44 μs .. 110.5 μs) 73 74 benchmarking ecdsa/sign_ecdsa' 75 time 233.7 μs (230.3 μs .. 237.2 μs) 76 0.997 R² (0.996 R² .. 0.998 R²) 77 mean 238.6 μs (234.8 μs .. 243.3 μs) 78 std dev 14.85 μs (12.27 μs .. 19.17 μs) 79 80 benchmarking ecdsa/verify_ecdsa' 81 time 1.460 ms (1.418 ms .. 1.497 ms) 82 0.994 R² (0.989 R² .. 0.997 R²) 83 mean 1.419 ms (1.398 ms .. 1.446 ms) 84 std dev 80.76 μs (66.73 μs .. 104.9 μs) 85 ``` 86 87 In terms of allocations, we get: 88 89 ``` 90 schnorr 91 92 Case Allocated GCs 93 sign_schnorr' 3,273,824 0 94 verify_schnorr' 1,667,360 0 95 96 ecdsa 97 98 Case Allocated GCs 99 sign_ecdsa' 324,672 0 100 verify_ecdsa' 3,796,328 0 101 ``` 102 103 ## Security 104 105 This library aims at the maximum security achievable in a 106 garbage-collected language under an optimizing compiler such as GHC, in 107 which strict constant-timeness can be [challenging to achieve][const]. 108 109 The Schnorr implementation within has been tested against the [official 110 BIP0340 vectors][ut340], and ECDSA has been tested against the relevant 111 [Wycheproof vectors][wyche], so their implementations are likely to be 112 accurate and safe from attacks targeting e.g. faulty nonce generation or 113 malicious inputs for signature parameters. Timing-sensitive operations, 114 e.g. elliptic curve scalar multiplication, have been explicitly written 115 so as to execute *algorithmically* in time constant with respect to 116 secret data, and evidence from benchmarks supports this: 117 118 ``` 119 benchmarking derive_public/sk = 2 120 time 1.703 ms (1.680 ms .. 1.728 ms) 121 0.997 R² (0.995 R² .. 0.999 R²) 122 mean 1.704 ms (1.684 ms .. 1.730 ms) 123 std dev 81.99 μs (67.86 μs .. 98.34 μs) 124 125 benchmarking derive_public/sk = 2 ^ 255 - 19 126 time 1.686 ms (1.654 ms .. 1.730 ms) 127 0.998 R² (0.997 R² .. 0.999 R²) 128 mean 1.658 ms (1.645 ms .. 1.673 ms) 129 std dev 44.75 μs (34.84 μs .. 59.81 μs) 130 131 benchmarking schnorr/sign_schnorr (small secret) 132 time 5.388 ms (5.345 ms .. 5.438 ms) 133 1.000 R² (0.999 R² .. 1.000 R²) 134 mean 5.429 ms (5.410 ms .. 5.449 ms) 135 std dev 58.14 μs (48.93 μs .. 68.69 μs) 136 137 benchmarking schnorr/sign_schnorr (large secret) 138 time 5.364 ms (5.324 ms .. 5.410 ms) 139 0.999 R² (0.999 R² .. 1.000 R²) 140 mean 5.443 ms (5.414 ms .. 5.486 ms) 141 std dev 102.1 μs (74.16 μs .. 146.4 μs) 142 143 benchmarking ecdsa/sign_ecdsa (small secret) 144 time 1.740 ms (1.726 ms .. 1.753 ms) 145 1.000 R² (0.999 R² .. 1.000 R²) 146 mean 1.752 ms (1.744 ms .. 1.761 ms) 147 std dev 32.33 μs (26.12 μs .. 43.34 μs) 148 149 benchmarking ecdsa/sign_ecdsa (large secret) 150 time 1.748 ms (1.731 ms .. 1.766 ms) 151 0.999 R² (0.998 R² .. 0.999 R²) 152 mean 1.756 ms (1.743 ms .. 1.771 ms) 153 std dev 48.99 μs (40.83 μs .. 62.77 μs) 154 ``` 155 156 Due to the use of arbitrary-precision integers, integer division modulo 157 the elliptic curve group order does display persistent substantial 158 timing differences on the order of 2 nanoseconds when the inputs differ 159 dramatically in size (here 2 bits vs 255 bits): 160 161 ``` 162 benchmarking remQ (remainder modulo _CURVE_Q)/remQ 2 163 time 27.44 ns (27.19 ns .. 27.72 ns) 164 1.000 R² (0.999 R² .. 1.000 R²) 165 mean 27.23 ns (27.03 ns .. 27.43 ns) 166 std dev 669.1 ps (539.9 ps .. 860.2 ps) 167 168 benchmarking remQ (remainder modulo _CURVE_Q)/remQ (2 ^ 255 - 19) 169 time 29.11 ns (28.87 ns .. 29.33 ns) 170 0.999 R² (0.999 R² .. 1.000 R²) 171 mean 29.04 ns (28.82 ns .. 29.40 ns) 172 std dev 882.9 ps (647.8 ps .. 1.317 ns) 173 ``` 174 175 This represents the worst-case scenario (real-world private keys will 176 never differ so extraordinarily) and is likely to be well within 177 acceptable limits for all but the most extreme security requirements. 178 But because we don't make "hard" guarantees of constant-time execution, 179 take reasonable security precautions as appropriate. You shouldn't 180 deploy the implementations within in any situation where they could 181 easily be used as an oracle to construct a [timing attack][timea], 182 and you shouldn't give sophisticated malicious actors [access to your 183 computer][flurl]. 184 185 If you discover any vulnerabilities, please disclose them via 186 security@ppad.tech. 187 188 ## Development 189 190 You'll require [Nix][nixos] with [flake][flake] support enabled. Enter a 191 development shell with: 192 193 ``` 194 $ nix develop 195 ``` 196 197 Then do e.g.: 198 199 ``` 200 $ cabal repl ppad-secp256k1 201 ``` 202 203 to get a REPL for the main library. 204 205 [bp340]: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki 206 [ut340]: https://github.com/bitcoin/bips/blob/master/bip-0340/test-vectors.csv 207 [bp146]: https://github.com/bitcoin/bips/blob/master/bip-0146.mediawiki 208 [r6979]: https://www.rfc-editor.org/rfc/rfc6979 209 [nixos]: https://nixos.org/ 210 [flake]: https://nixos.org/manual/nix/unstable/command-ref/new-cli/nix3-flake.html 211 [hadoc]: https://docs.ppad.tech/secp256k1 212 [wyche]: https://github.com/C2SP/wycheproof 213 [timea]: https://en.wikipedia.org/wiki/Timing_attack 214 [flurl]: https://eprint.iacr.org/2014/140.pdf 215 [const]: https://www.chosenplaintext.ca/articles/beginners-guide-constant-time-cryptography.html 216 [csecp]: https://git.ppad.tech/csecp256k1