README.md (6558B)
1 # ppad-fixed 2 3 [](https://hackage.haskell.org/package/ppad-fixed) 4  5 [](https://docs.ppad.tech/fixed) 6 7 A pure high-performance implementation of large fixed-width integers 8 and supporting constant-time operations, including Montgomery-form 9 arithmetic on domains related to the the elliptic curve secp256k1. 10 11 ## Usage 12 13 A sample GHCi session: 14 15 ``` 16 > -- import qualified 17 > import qualified Numeric.Montgomery.Secp256k1.Curve as C 18 > 19 > let one = 1 :: C.Montgomery 20 > one 21 1 22 > putStrLn (C.render one) 23 (4294968273, 0, 0, 0) 24 > 25 > let two = one + one 26 > putStrLn (C.render two) 27 (8589936546, 0, 0, 0) 28 > 29 > let big = 2 ^ (128 :: Int) :: C.Montgomery 30 > big 31 340282366920938463463374607431768211456 32 > putStrLn (C.render big) 33 (0, 0, 4294968273, 0) 34 > 35 > let inv = C.inv big 36 > inv 37 85349562743316995932995116683053049354367560536510302240860302699983992117553 38 > putStrLn (C.render inv) 39 (0, 0, 1, 0) 40 > 41 > inv * big 42 1 43 ``` 44 45 ## Performance 46 47 The aim is best-in-class performance for pure Haskell code. 48 49 Current benchmark figures on my M4 Silicon MacBook Air look like: 50 51 ``` 52 benchmarking add/curve: M(1) + M(2 ^ 255 - 19) 53 time 5.399 ns (5.359 ns .. 5.442 ns) 54 1.000 R² (1.000 R² .. 1.000 R²) 55 mean 5.389 ns (5.371 ns .. 5.426 ns) 56 std dev 82.34 ps (54.62 ps .. 128.7 ps) 57 variance introduced by outliers: 21% (moderately inflated) 58 59 benchmarking sub/curve: M(2 ^ 255 - 1) - M(2 ^ 255 - 19) 60 time 5.226 ns (5.217 ns .. 5.241 ns) 61 1.000 R² (1.000 R² .. 1.000 R²) 62 mean 5.249 ns (5.230 ns .. 5.287 ns) 63 std dev 84.60 ps (54.00 ps .. 126.7 ps) 64 variance introduced by outliers: 23% (moderately inflated) 65 66 benchmarking mul/curve: M(2) * M(2 ^ 255 - 19) 67 time 14.78 ns (14.75 ns .. 14.81 ns) 68 1.000 R² (1.000 R² .. 1.000 R²) 69 mean 14.82 ns (14.79 ns .. 14.85 ns) 70 std dev 99.51 ps (84.22 ps .. 118.2 ps) 71 72 benchmarking sqr/curve: M(2 ^ 255 - 19) ^ 2 73 time 14.23 ns (14.20 ns .. 14.27 ns) 74 1.000 R² (1.000 R² .. 1.000 R²) 75 mean 14.26 ns (14.23 ns .. 14.29 ns) 76 std dev 114.3 ps (84.98 ps .. 181.1 ps) 77 78 benchmarking inv/curve: M(2 ^ 255 - 19) ^ -1 79 time 6.936 μs (6.911 μs .. 6.959 μs) 80 1.000 R² (1.000 R² .. 1.000 R²) 81 mean 6.898 μs (6.885 μs .. 6.911 μs) 82 std dev 44.83 ns (35.58 ns .. 56.92 ns) 83 84 benchmarking exp/curve: M(2 ^ 255 - 19) ^ (2 ^ 255 - 19) 85 time 5.200 μs (5.194 μs .. 5.205 μs) 86 1.000 R² (1.000 R² .. 1.000 R²) 87 mean 5.192 μs (5.188 μs .. 5.197 μs) 88 std dev 15.58 ns (11.38 ns .. 20.86 ns) 89 90 benchmarking sqrt/curve: sqrt M(2 ^ 255 - 19) 91 time 6.882 μs (6.876 μs .. 6.890 μs) 92 1.000 R² (1.000 R² .. 1.000 R²) 93 mean 6.893 μs (6.870 μs .. 6.902 μs) 94 std dev 47.48 ns (25.79 ns .. 100.5 ns) 95 ``` 96 97 The library can be used either via a boxed or unboxed API. Functions in 98 the unboxed API, suffixed by magic hashes, do not allocate. Functions in 99 the boxed API allocate only for top-level data constructors used when 100 boxing results -- any internal arithmetic is entirely unboxed. 101 102 For example, a boxed 'Wide' word, defined as: 103 104 ``` haskell 105 data Wide = Wide !(# Limb, Limb #) 106 ``` 107 108 will allocate precisely three machine words -- one for the constructor, 109 and one for each 'Limb' (so, 24 bytes on a 64-bit machine). A 'Wider' 110 word, defined as: 111 112 ``` haskell 113 data Wider = Wider !(# Limb, Limb, Limb, Limb #) 114 ``` 115 116 will allocate five machine words (40 bytes) in turn. 117 118 Thus, the allocation benchmark story for 256-bit Montgomery arithmetic 119 using the boxed API looks like: 120 121 ``` 122 add 123 124 Case Allocated GCs 125 curve: M(1) + M(2) 40 0 126 curve: M(1) + M(2 ^ 255 - 19) 40 0 127 128 sub 129 130 Case Allocated GCs 131 curve: M(2 ^ 255 - 1) - M(1) 40 0 132 curve: M(2 ^ 255 - 1) - M(2 ^ 255 - 19) 40 0 133 134 mul 135 136 Case Allocated GCs 137 curve: M(2) * M(2) 40 0 138 curve: M(2) * M(2 ^ 255 - 19) 40 0 139 140 sqr 141 142 Case Allocated GCs 143 curve: M(2) ^ 2 40 0 144 curve: M(2 ^ 255 - 19) ^ 2 40 0 145 146 inv 147 148 Case Allocated GCs 149 curve: M(2) ^ -1 40 0 150 curve: M(2 ^ 255 - 19) ^ -1 40 0 151 152 exp 153 154 Case Allocated GCs 155 curve: M(2) ^ 2 40 0 156 curve: M(2) ^ (2 ^ 255 - 19) 40 0 157 158 sqrt 159 160 Case Allocated GCs 161 curve: sqrt M(2) 56 0 162 curve: sqrt M(2 ^ 255 - 19) 56 0 163 ``` 164 165 Note that 'sqrt' for example allocates 16 additional bytes as it returns 166 a value of type 'Maybe Montgomery', which involves using either a Just 167 or Nothing constructor (the analogous function in the unboxed API, 168 'sqrt#', avoids allocation by returning an unboxed sum). 169 170 You can compile with GHC's LLVM backend and filter on specific 171 benchmarks via e.g.: 172 173 ``` 174 $ cabal bench ppad-fixed:benchmark:fixed-bench \ 175 --ghc-options="-fllvm -O2" \ 176 --benchmark-options="--match prefix inv" 177 ``` 178 179 ## Security 180 181 This library aims at the maximum security achievable in a 182 garbage-collected language under an optimizing compiler such as GHC, in 183 which strict constant-timeness can be challenging to achieve. 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-fixed 201 ``` 202 203 to get a REPL for the main library. 204 205 ## Attribution 206 207 This library is more or less a Haskell translation of (parts of) the 208 Rust [crypto-bigint](https://github.com/RustCrypto/crypto-bigint) 209 library, having initially started as a port of the golang 210 [uint256](https://github.com/holiman/uint256) library. 211 212 [nixos]: https://nixos.org/ 213 [flake]: https://nixos.org/manual/nix/unstable/command-ref/new-cli/nix3-flake.html