fast-noble-hashes

Why hashing shows up in an install

An npm lockfile records the integrity of every tarball as a SHA-512, so anything that installs or verifies packages hashes every tarball. A crypto polyfill, such as the one Nodepod offers to the code it runs, needs createHash, pbkdf2Sync and scrypt as well. @noble/hashes, a JavaScript implementation with no dependencies, can provide all of those. For the 4.4 MB typescript tarball noble takes 30.5 ms to compute the SHA-512 in Node, and fast-noble-hashes takes 5.7 ms.

A hash function is a compression function run over the message one block at a time: 64 bytes at a time for SHA-256, SHA-1 and MD5, 128 for SHA-512. Each block goes through 64 or 80 rounds of rotates, xors and additions. That function is the part that was rewritten. Everything around it, meaning the classes, the buffering, the padding rules and the errors, is noble's.

Why SHA-512 gains the most

JavaScript has no 64-bit integer that an engine handles quickly. Its bitwise operators work on 32 bits, and noble's _u64.js says in its header that BigUint64Array is too slow, so it stores every 64-bit word as two 32-bit numbers, a high half and a low half. A rotate becomes shifts and ors across the pair, and an addition has to recover the carry out of the low half with a division. noble's own comment in sha2.js says the same thing: SHA-512 is slower than SHA-256 in JavaScript because 64-bit operations are slow.

WebAssembly has 64-bit rotate and add as single instructions. The SHA-512 kernel is written the way the algorithm reads, on i64 values, and it runs about 5 times as fast as noble's pairs. That is why the headline numbers are for SHA-512 and SHA-384, which are the same code with a different start value and a shorter output.

Why SHA-256 gains least, and short inputs gain more

SHA-256 is the case where JavaScript is best off. Its words are 32 bits wide, which is what the engine's integer operations are, and the JIT compiles 32-bit rotates well. The WebAssembly version is scalar as well, so in the recorded results it gains 1.7-1.9x in Node and about 2.3x in Chromium. Engines differ here more than for the other hashes, because the JIT is what SHA-256 is competing with, so the sweep above shows what your browser does today. More work on the kernel did not change the recorded figures. A precomputed message schedule ran about 30% slower than keeping the schedule in locals, and wasm-opt -O3 changed nothing. The dead ends are written down.

Short messages gain more because less happens around them. noble's one-shot sha256(message) creates a hash object, with its buffer, on every call. The fast one never creates an instance, and it encodes a string straight into WebAssembly memory. So a 56-character string is 4.0x faster for SHA-256 and 7.0x for MD5 in Node, while a megabyte of SHA-256 is 1.7x. Hashing through .create().update(...).digest() gains less, 1.7-2.3x on a short string, because noble's constructor allocates a buffer for each instance and that stays.

Templates that expand on first use

Unrolled, the 64 rounds of SHA-256 are 8.8 KB of WebAssembly and the 80 rounds of SHA-512 are 11.3 KB. Shipping that costs bytes. Rolling the rounds into a loop costs speed: it ran at 0.79-0.97 of the unrolled speed. Templates avoid both. Each family ships a description of its rounds, a few hundred bytes long, with commands for the parts that change from round to round, and expand() in _fast.js writes out the full module the first time the family is used. The module is compiled synchronously, in the same call.

A build-time assembler, wasm/asm.mjs, writes the templates, and this is how SHA-256's is written in wasm/kernels.mjs:

export const SHA256 = A.cat(
  A.func([[24, T.i32], [1, T.v128]], A.loop, loadBE32(27), load32(8),
    repeat(64, when(16, SCHED256), ROUND256), store32(8), next(64)),
  OUT_BE,
  W_BE,
);

The commands are few:

• repeat writes a body out n times, with the round number j available inside it. That is the 64 rounds of SHA-256 and the 80 of SHA-512.
• when keeps a body only from a given round. The message schedule starts at round 16, and SHA-1 switches its round function every 20 rounds.
• A rotating local: the state variables a to h move one place each round, so a round names them relative to j and expand() picks the local.
• Memory offsets that grow with j, such as the load of round constant j, and the family's own constants, such as its block length.

The template travels as text that bundlers and minifiers leave alone: printable ASCII without " and backslash. The most frequent opcodes and immediates, bytes 0x00-0x54 and 0xfa-0xff, take one character, and the other bytes take two. That compresses almost like the binary does. Base64 came out about 30% larger after compression, and a table of the most frequent bytes was larger even with the table counted.

Each family's template is referenced only by the module that defines its hashers, so a bundle carries only the families its imports reach. Importing sha256 alone brings the common template and SHA-256's, and nothing for SHA-512 or MD5. Once used, a family keeps its instance, 64 KiB of memory that is wiped after every call.

Expanding is not free. In Node, the first sha256() call takes 1.2 ms with fast-noble-hashes and 0.3 ms with noble. The table above breaks the first use of each family into its steps in your browser. Each step takes on the order of 0.1 ms.

State stays noble's

Code that inspects or clones a hash object keeps working. noble's classes keep their state in fields (A to H, buffer, pos, length), and after every call those fields hold what noble's JavaScript would have left in them. To get there, update and digestInto copy the state words into WebAssembly memory, run the compression, copy them back, and write the buffer the way noble's loop does. Each call ends by zeroing the scratch memory, so WebAssembly memory holds no message bytes and no state between calls.

If an object could behave differently from noble's, noble's code runs instead. That covers a subclass, which may override process(), and an instance whose blockLen, outputLen, padOffset or isLE was changed. The result is the same and it is slower.

Type anything below. Both libraries hash it as you type, and the digests are compared with each other and, for SHA-2, with the browser's WebCrypto.

PBKDF2 and scrypt

PBKDF2 runs HMAC once per iteration, and every HMAC is two passes of the hash. noble's loop clones an HMAC object and calls update and digestInto on it for each iteration, then xors the result into the total. In fast-noble-hashes, iterations 2 to c run inside a single WebAssembly function that keeps HMAC's inner and outer states in memory. JavaScript is not called between iterations. Long runs are cut into slices, because the counter in WebAssembly is 32 bits and so that the async version can yield to the event loop as noble's does. In the recorded results that comes to 3.4x for SHA-256 and about 7x for SHA-512 in Node, and 4x and 8x in Chromium: figures that combine the faster hash with the JavaScript work per iteration that no longer happens.

scrypt's cost is ROMix, which fills N blocks of data and then reads them back in an order that depends on the data, running salsa20/8 at each step. The module is 694 bytes. It keeps the 16 words of a block in four SIMD registers, runs each quarter-round on four columns at once with vector adds, shifts and xors, and rotates lanes and swaps two registers so that the row rounds run the same code as the column rounds. The glue permutes the words on the way in and out so they sit in the order the vector rounds need. Each scrypt() call gets a fresh instance whose memory is grown to fit its N, r and p and wiped at the end, so a large N leaves no large memory behind. scrypt runs 2.3x as fast.

How we know the results are noble's

Most of the package is noble's own files, and the design keeps it that way. The five patched modules, in ESM and CommonJS, are noble's files plus the find-and-replace pairs in tools/patches.mjs. A pair must match exactly once or the build fails. test/files.mjs checks that every shipped file is noble's plus those patches and nothing else, and that the rest are noble's byte for byte.

The differential suite, test/diff.mjs, ran 113,334 checks for each of ESM and CommonJS, and 113,120 with a second seed. It compares digests and every instance field after every call, against noble and against node:crypto, and it covers errors, HMAC, HKDF, PBKDF2 and scrypt in sync and async form with progress callbacks, subclasses, tampered instances and the public surface. A separate set of checks, written apart from the package's tests, ran 17,308 checks of the calls a real consumer, Nodepod, makes, such as lockfile integrity of npm tarballs, and found no difference. The same differential check runs in Chromium, Firefox and WebKit, on the main thread and in a worker.

Tests can also be too weak, so npm run mutate plants deliberate bugs in the glue, in _md.js and in the WebAssembly, and the suite must fail on each one. It catches all 41.

What is different

The package needs WebAssembly with SIMD: Node 16.4 or later, Chrome and Edge 91, Firefox 89, Safari 16.4. Without WebAssembly, the SHA-2, SHA-1 and MD5 hashers, and HMAC, HKDF and PBKDF2 over them, and scrypt, throw Error("fast-noble-hashes needs WebAssembly") when first used, though noble's input errors still come first. With WebAssembly but a content security policy that blocks compiling it, or without SIMD, the engine's CompileError is thrown instead. SHA-3, BLAKE, RIPEMD-160, Argon2 and the rest are noble's code and run at noble's speed.

scrypt's memory is WebAssembly memory. 128 * r * (N + p + 1) bytes plus 64 KiB must fit in 4 GiB, which only a raised maxmem can reach, since the default limit is 1 GiB. Past that, or when the memory cannot be allocated, scrypt throws the RangeError of Memory.grow(). The module-private constant tables and scratch arrays are gone, along with the salsa20 functions. None of them was exported, and the exports of every module are noble's. pbkdf2Async and scryptAsync yield every asyncTick milliseconds like noble's, but slice the work differently, so the number of event-loop turns differs. The onProgress values and their order are noble's.

Size is mixed. The bundle these demos load is 17.6 KB (6.4 KB brotli) against 17.1 KB (6.1 KB brotli) for noble. The full set that Nodepod imports (scrypt, sha384, sha512, sha256, sha1, md5, hmac, pbkdf2) comes to 6,197 bytes brotli against 6,237. A single hash import is another matter, because the glue and the common template come with it. For sha256 alone, they add about 1.9 KB brotli where noble's SHA-256 function and its constants are about 0.6 KB.