README.md (5552B)
1 # ppad-fixed 2 3 A pure (**pre-release**, under construction, not-yet-constant-time) 4 implementation of large fixed-width integers and supporting operations. 5 6 ## Usage 7 8 A sample GHCi session: 9 10 ``` 11 > -- import qualified 12 > import Data.Word.Extended as W 13 > 14 > -- use 'to_word256' to convert variable-length integers to Word256 15 > let u = W.to_word256 0xFFFFFFFFFF 16 > :t u 17 u :: W.Word256 18 > 19 > -- compare values 20 > let v = W.to_word256 0xFFFFFF 21 > u `W.lt` v 22 False 23 > 24 > -- bitwise operations 25 > u `W.or` v -- == u 26 1099511627775 27 > u `W.and` v -- == v 28 16777215 29 > 30 > -- arithmetic operations 31 > (u `add` v) `sub` (u `add` v) 32 0 33 > u `mul` u `mul` u `mul` u `mul` u `mul` u `mul` u 34 115779721307862780478962831313825936498328052285500565196053117862789708251135 35 > 36 > u `div` v 37 65536 38 > 39 > -- modular reduction 40 > u `mod` v 41 65535 42 ``` 43 44 ## Performance 45 46 The aim is best-in-class performance for pure, highly-auditable Haskell 47 code. Most operations beat out their variable-length Integer variants, 48 *but*, we have yet to reach parity with the all-important division and 49 modulo operations. 50 51 Current benchmark figures on my mid-2020 MacBook Air look like (use 52 `cabal bench` to run the benchmark suite): 53 54 ``` 55 benchmarking addition & subtraction/add 56 time 11.20 ns (11.11 ns .. 11.30 ns) 57 0.999 R² (0.999 R² .. 1.000 R²) 58 mean 11.47 ns (11.32 ns .. 11.75 ns) 59 std dev 679.6 ps (380.7 ps .. 1.038 ns) 60 variance introduced by outliers: 80% (severely inflated) 61 62 benchmarking addition & subtraction/add (baseline) 63 time 25.09 ns (24.36 ns .. 26.00 ns) 64 0.991 R² (0.981 R² .. 0.998 R²) 65 mean 24.81 ns (24.27 ns .. 25.85 ns) 66 std dev 2.408 ns (1.289 ns .. 4.439 ns) 67 variance introduced by outliers: 91% (severely inflated) 68 69 benchmarking addition & subtraction/sub 70 time 11.51 ns (11.42 ns .. 11.63 ns) 71 0.999 R² (0.999 R² .. 1.000 R²) 72 mean 11.66 ns (11.54 ns .. 11.81 ns) 73 std dev 475.9 ps (350.7 ps .. 642.7 ps) 74 variance introduced by outliers: 65% (severely inflated) 75 76 benchmarking addition & subtraction/sub (baseline) 77 time 31.93 ns (31.71 ns .. 32.13 ns) 78 1.000 R² (0.999 R² .. 1.000 R²) 79 mean 31.65 ns (31.39 ns .. 31.89 ns) 80 std dev 841.0 ps (710.8 ps .. 1.002 ns) 81 variance introduced by outliers: 42% (moderately inflated) 82 83 benchmarking multiplication/mul 84 time 29.41 ns (29.06 ns .. 29.84 ns) 85 0.995 R² (0.988 R² .. 0.999 R²) 86 mean 30.50 ns (29.58 ns .. 33.10 ns) 87 std dev 4.628 ns (1.452 ns .. 9.437 ns) 88 variance introduced by outliers: 96% (severely inflated) 89 90 benchmarking multiplication/mul (baseline) 91 time 46.08 ns (45.71 ns .. 46.43 ns) 92 0.999 R² (0.999 R² .. 1.000 R²) 93 mean 46.12 ns (45.65 ns .. 46.56 ns) 94 std dev 1.564 ns (1.218 ns .. 2.063 ns) 95 variance introduced by outliers: 54% (severely inflated) 96 97 benchmarking division/div 98 time 81.94 ns (81.11 ns .. 82.84 ns) 99 0.999 R² (0.999 R² .. 1.000 R²) 100 mean 81.97 ns (81.43 ns .. 82.89 ns) 101 std dev 2.422 ns (1.696 ns .. 3.578 ns) 102 variance introduced by outliers: 46% (moderately inflated) 103 104 benchmarking division/div (baseline) 105 time 72.08 ns (71.26 ns .. 72.89 ns) 106 0.999 R² (0.999 R² .. 0.999 R²) 107 mean 72.35 ns (71.52 ns .. 73.15 ns) 108 std dev 2.566 ns (2.203 ns .. 3.044 ns) 109 variance introduced by outliers: 55% (severely inflated) 110 111 benchmarking division/mod 112 time 106.6 ns (105.7 ns .. 107.5 ns) 113 0.999 R² (0.999 R² .. 0.999 R²) 114 mean 107.9 ns (106.5 ns .. 109.2 ns) 115 std dev 4.520 ns (3.705 ns .. 6.013 ns) 116 variance introduced by outliers: 63% (severely inflated) 117 118 benchmarking division/mod (baseline) 119 time 77.94 ns (76.87 ns .. 79.02 ns) 120 0.998 R² (0.998 R² .. 0.999 R²) 121 mean 78.50 ns (77.49 ns .. 79.74 ns) 122 std dev 3.694 ns (2.729 ns .. 5.235 ns) 123 variance introduced by outliers: 68% (severely inflated) 124 ``` 125 126 Note that you can compile with GHC's LLVM backend and filter on specific 127 benchmarks via e.g.: 128 129 ``` 130 $ cabal bench ppad-fixed:benchmark:fixed-bench \ 131 --ghc-options="-fllvm -O2" \ 132 --benchmark-options="--match prefix inv" 133 ``` 134 135 ## Security 136 137 This library aims at the maximum security achievable in a 138 garbage-collected language under an optimizing compiler such as GHC, in 139 which strict constant-timeness can be challenging to achieve. 140 141 If you discover any vulnerabilities, please disclose them via 142 security@ppad.tech. 143 144 ## Development 145 146 You'll require [Nix][nixos] with [flake][flake] support enabled. Enter a 147 development shell with: 148 149 ``` 150 $ nix develop 151 ``` 152 153 Then do e.g.: 154 155 ``` 156 $ cabal repl ppad-fixed 157 ``` 158 159 to get a REPL for the main library. 160 161 ## Attribution 162 163 This library is more or less a Haskell translation of the golang 164 [uint256](https://github.com/holiman/uint256) library. 165 166 [nixos]: https://nixos.org/ 167 [flake]: https://nixos.org/manual/nix/unstable/command-ref/new-cli/nix3-flake.html