README.md (5092B)
1 # ppad-fixed 2 3 A pure (**pre-release**, under construction, 4 not-yet-guaranteed-constant-time) high-performance implementation 5 of large fixed-width integers and supporting operations, including 6 Montgomery-form arithmetic on domains related to the the elliptic curve 7 secp256k1. 8 9 ## Usage 10 11 A sample GHCi session: 12 13 ``` 14 > -- import qualified 15 > import qualified Numeric.Montgomery.Secp256k1.Curve as C 16 > 17 > let one = 1 :: C.Montgomery 18 > one 19 1 20 > putStrLn (C.render one) 21 (4294968273, 0, 0, 0) 22 > 23 > let two = one + one 24 > putStrLn (C.render two) 25 (8589936546, 0, 0, 0) 26 > 27 > let big = 2 ^ (128 :: Int) :: C.Montgomery 28 > big 29 340282366920938463463374607431768211456 30 > putStrLn (C.render big) 31 (0, 0, 4294968273, 0) 32 > 33 > let inv = C.inv big 34 > inv 35 85349562743316995932995116683053049354367560536510302240860302699983992117553 36 > putStrLn (C.render inv) 37 (0, 0, 1, 0) 38 > 39 > inv * big 40 1 41 ``` 42 43 ## Performance 44 45 The aim is best-in-class performance for pure Haskell code. 46 47 Current benchmark figures on my M4 Silicon MacBook Air look like: 48 49 ``` 50 benchmarking add/curve: M(1) + M(2 ^ 255 - 19) 51 time 6.890 ns (6.882 ns .. 6.906 ns) 52 1.000 R² (1.000 R² .. 1.000 R²) 53 mean 6.889 ns (6.885 ns .. 6.897 ns) 54 std dev 16.73 ps (8.753 ps .. 30.75 ps) 55 56 benchmarking sub/curve: M(2 ^ 255 - 1) - M(2 ^ 255 - 19) 57 time 6.876 ns (6.872 ns .. 6.883 ns) 58 1.000 R² (1.000 R² .. 1.000 R²) 59 mean 6.877 ns (6.874 ns .. 6.881 ns) 60 std dev 11.60 ps (7.865 ps .. 18.34 ps) 61 62 benchmarking mul/curve: M(2) * M(2 ^ 255 - 19) 63 time 14.78 ns (14.75 ns .. 14.81 ns) 64 1.000 R² (1.000 R² .. 1.000 R²) 65 mean 14.82 ns (14.79 ns .. 14.85 ns) 66 std dev 99.51 ps (84.22 ps .. 118.2 ps) 67 68 benchmarking sqr/curve: M(2 ^ 255 - 19) ^ 2 69 time 14.23 ns (14.20 ns .. 14.27 ns) 70 1.000 R² (1.000 R² .. 1.000 R²) 71 mean 14.26 ns (14.23 ns .. 14.29 ns) 72 std dev 114.3 ps (84.98 ps .. 181.1 ps) 73 74 benchmarking inv/curve: M(2 ^ 255 - 19) ^ -1 75 time 7.004 μs (6.988 μs .. 7.030 μs) 76 1.000 R² (1.000 R² .. 1.000 R²) 77 mean 7.027 μs (7.013 μs .. 7.047 μs) 78 std dev 57.73 ns (50.57 ns .. 74.05 ns) 79 ``` 80 81 The library can be used either via a boxed or unboxed API. Unboxed 82 functions, suffixed by magic hashes, do not allocate. Boxed functions 83 allocate only for top-level data constructors used when boxing results 84 -- any internal arithmetic is entirely unboxed. 85 86 For example, a boxed 'Wide' word, defined as: 87 88 ``` haskell 89 data Wide = Wide !(# Limb, Limb #) 90 ``` 91 92 will allocate precisely three machine words -- one for the constructor, 93 and one for each 'Limb' (so, 24 bytes on a 64-bit machine). A 'Wider' 94 word, defined as: 95 96 ``` haskell 97 data Wider = Wider !(# Limb, Limb, Limb, Limb #) 98 ``` 99 100 will allocate five machine words (40 bytes) in turn. 101 102 Thus, the allocation benchmark story for 256-bit Montgomery arithmetic 103 using the boxed API looks like: 104 105 ``` 106 add 107 108 Case Allocated GCs 109 curve: M(1) + M(2) 40 0 110 curve: M(1) + M(2 ^ 255 - 19) 40 0 111 112 sub 113 114 Case Allocated GCs 115 curve: M(2 ^ 255 - 1) - M(1) 40 0 116 curve: M(2 ^ 255 - 1) - M(2 ^ 255 - 19) 40 0 117 118 mul 119 120 Case Allocated GCs 121 curve: M(2) * M(2) 40 0 122 curve: M(2) * M(2 ^ 255 - 19) 40 0 123 124 sqr 125 126 Case Allocated GCs 127 curve: M(2) ^ 2 40 0 128 curve: M(2 ^ 255 - 19) ^ 2 40 0 129 130 inv 131 132 Case Allocated GCs 133 curve: M(2) ^ -1 40 0 134 curve: M(2 ^ 255 - 19) ^ -1 40 0 135 ``` 136 137 Note that you can compile with GHC's LLVM backend and filter on specific 138 benchmarks via e.g.: 139 140 ``` 141 $ cabal bench ppad-fixed:benchmark:fixed-bench \ 142 --ghc-options="-fllvm -O2" \ 143 --benchmark-options="--match prefix inv" 144 ``` 145 146 ## Security 147 148 This library aims at the maximum security achievable in a 149 garbage-collected language under an optimizing compiler such as GHC, in 150 which strict constant-timeness can be challenging to achieve. 151 152 If you discover any vulnerabilities, please disclose them via 153 security@ppad.tech. 154 155 ## Development 156 157 You'll require [Nix][nixos] with [flake][flake] support enabled. Enter a 158 development shell with: 159 160 ``` 161 $ nix develop 162 ``` 163 164 Then do e.g.: 165 166 ``` 167 $ cabal repl ppad-fixed 168 ``` 169 170 to get a REPL for the main library. 171 172 ## Attribution 173 174 This library is more or less a Haskell translation of (parts of) the 175 Rust [crypto-bigint](https://github.com/RustCrypto/crypto-bigint) 176 library, having initially started as a port of the golang 177 [uint256](https://github.com/holiman/uint256) library. 178 179 [nixos]: https://nixos.org/ 180 [flake]: https://nixos.org/manual/nix/unstable/command-ref/new-cli/nix3-flake.html