BLAKE3 is a cryptographic hash function that produces a 256-bit digest by default but also supports extendable output.
pub const Blake3 = structpub const Blake3 = struct {
pub const block_length = 64;
pub const digest_length = 32;
pub const key_length = 32;
pub const Options = struct { key: ?[key_length]u8 = null };
pub const KdfOptions = struct {};
key: [8]u32,
chunk: ChunkState,
cv_stack_len: u8,
cv_stack: [max_depth + 1][8]u32,
/// Construct a new `Blake3` for the hash function, with an optional key
pub fn init(options: Options) Blake3 {
if (options.key) |key| {
const key_words = loadKeyWords(key);
return init_internal(key_words, .{ .keyed_hash = true });
} else {
return init_internal(iv, .{});
}
}
/// Construct a new `Blake3` for the key derivation function. The context
/// string should be hardcoded, globally unique, and application-specific.
pub fn initKdf(context: []const u8, options: KdfOptions) Blake3 {
_ = options;
var context_hasher = init_internal(iv, .{ .derive_key_context = true });
context_hasher.update(context);
var context_key: [key_length]u8 = undefined;
context_hasher.final(&context_key);
const context_key_words = loadKeyWords(context_key);
return init_internal(context_key_words, .{ .derive_key_material = true });
}
pub fn hash(b: []const u8, out: []u8, options: Options) void {
var d = Blake3.init(options);
d.update(b);
d.final(out);
}
pub fn hashParallel(b: []const u8, out: []u8, options: Options, allocator: Allocator, io: Io) error{ OutOfMemory, Canceled }!void {
if (b.len < parallel_threshold) {
return hash(b, out, options);
}
const key_words = if (options.key) |key| loadKeyWords(key) else iv;
const flags: Flags = if (options.key != null) .{ .keyed_hash = true } else .{};
const num_full_chunks = b.len / chunk_length;
const thread_count = Thread.getCpuCount() catch 1;
if (thread_count <= 1 or num_full_chunks == 0) {
return hash(b, out, options);
}
const remaining_bytes = b.len % chunk_length;
const num_leaves = @divCeil(b.len, chunk_length);
const cvs = try allocator.alloc([8]u32, num_leaves);
defer allocator.free(cvs);
// Process chunks in parallel
const num_workers = thread_count;
const chunks_per_worker = (num_full_chunks + num_workers - 1) / num_workers;
var group: Io.Group = .init;
defer group.cancel(io);
for (0..num_workers) |worker_id| {
const start_chunk = worker_id * chunks_per_worker;
if (start_chunk >= num_full_chunks) break;
group.async(io, ChunkBatch.process, .{ChunkBatch{
.input = b,
.start_chunk = start_chunk,
.end_chunk = @min(start_chunk + chunks_per_worker, num_full_chunks),
.cvs = cvs,
.key = key_words,
.flags = flags,
}});
}
try group.await(io);
if (remaining_bytes > 0) {
var chunk_state = ChunkState.init(key_words, flags);
chunk_state.chunk_counter = num_full_chunks;
chunk_state.update(b[num_full_chunks * chunk_length ..]);
const output = chunk_state.output();
cvs[num_full_chunks] = output.chainingValue();
}
// Build Merkle tree in parallel layers using ping-pong buffers
const max_intermediate_size = @divCeil(num_leaves, 2);
const buffer0 = try allocator.alloc([8]u32, max_intermediate_size);
defer allocator.free(buffer0);
const buffer1 = try allocator.alloc([8]u32, max_intermediate_size);
defer allocator.free(buffer1);
var current_level = cvs;
var next_level_buf = buffer0;
var toggle = false;
while (current_level.len > 8) {
const num_parents = current_level.len / 2;
const has_odd = current_level.len % 2 == 1;
const next_level_size = num_parents + @intFromBool(has_odd);
try buildMerkleTreeLayerParallel(
current_level[0 .. num_parents * 2],
next_level_buf[0..num_parents],
key_words,
flags,
io,
);
if (has_odd) {
next_level_buf[num_parents] = current_level[current_level.len - 1];
}
current_level = next_level_buf[0..next_level_size];
next_level_buf = if (toggle) buffer0 else buffer1;
toggle = !toggle;
}
// Finalize remaining small tree sequentially
var hasher = init_internal(key_words, flags);
for (current_level, 0..) |cv, i| hasher.pushCv(cv, i);
hasher.final(out);
}
fn init_internal(key: [8]u32, flags: Flags) Blake3 {
return Blake3{
.key = key,
.chunk = ChunkState.init(key, flags),
.cv_stack_len = 0,
.cv_stack = undefined,
};
}
fn mergeCvStack(self: *Blake3, total_len: u64) void {
const post_merge_stack_len = @as(u8, @intCast(@popCount(total_len)));
while (self.cv_stack_len > post_merge_stack_len) {
const left_cv = self.cv_stack[self.cv_stack_len - 2];
const right_cv = self.cv_stack[self.cv_stack_len - 1];
const output = parentOutputFromCvs(left_cv, right_cv, self.key, self.chunk.flags);
const cv = output.chainingValue();
self.cv_stack[self.cv_stack_len - 2] = cv;
self.cv_stack_len -= 1;
}
}
fn pushCv(self: *Blake3, new_cv: [8]u32, chunk_counter: u64) void {
self.mergeCvStack(chunk_counter);
self.cv_stack[self.cv_stack_len] = new_cv;
self.cv_stack_len += 1;
}
/// Add input to the hash state. This can be called any number of times.
pub fn update(self: *Blake3, input: []const u8) void {
if (input.len == 0) return;
var inp = input;
if (self.chunk.len() > 0) {
const take = @min(chunk_length - self.chunk.len(), inp.len);
self.chunk.update(inp[0..take]);
inp = inp[take..];
if (inp.len > 0) {
const output = self.chunk.output();
const chunk_cv = output.chainingValue();
self.pushCv(chunk_cv, self.chunk.chunk_counter);
self.chunk.reset(self.key, self.chunk.chunk_counter + 1);
} else {
return;
}
}
while (inp.len > chunk_length) {
var subtree_len = roundDownToPowerOf2(inp.len);
const count_so_far = self.chunk.chunk_counter * chunk_length;
while ((subtree_len - 1) & count_so_far != 0) {
subtree_len /= 2;
}
const subtree_chunks = subtree_len / chunk_length;
if (subtree_len <= chunk_length) {
var chunk_state = ChunkState.init(self.key, self.chunk.flags);
chunk_state.chunk_counter = self.chunk.chunk_counter;
chunk_state.update(inp[0..@intCast(subtree_len)]);
const output = chunk_state.output();
const cv = output.chainingValue();
self.pushCv(cv, chunk_state.chunk_counter);
} else {
var cv_pair: [2 * digest_length]u8 = undefined;
compressSubtreeToParentNode(inp[0..@intCast(subtree_len)], self.key, self.chunk.chunk_counter, self.chunk.flags, &cv_pair);
const left_cv = loadCvWords(cv_pair[0..digest_length].*);
const right_cv = loadCvWords(cv_pair[digest_length..][0..digest_length].*);
self.pushCv(left_cv, self.chunk.chunk_counter);
self.pushCv(right_cv, self.chunk.chunk_counter + (subtree_chunks / 2));
}
self.chunk.chunk_counter += subtree_chunks;
inp = inp[@intCast(subtree_len)..];
}
if (inp.len > 0) {
self.chunk.update(inp);
self.mergeCvStack(self.chunk.chunk_counter);
}
}
/// Finalize the hash and write any number of output bytes.
pub fn final(self: *const Blake3, out: []u8) void {
self.finalizeSeek(0, out);
}
/// Finalize the hash and write any number of output bytes, starting at a given seek position.
/// This is an XOF (extendable-output function) extension.
pub fn finalizeSeek(self: *const Blake3, seek: u64, out: []u8) void {
if (out.len == 0) return;
if (self.cv_stack_len == 0) {
const output = self.chunk.output();
output.rootBytes(seek, out);
return;
}
var output: Output = undefined;
var cvs_remaining: usize = undefined;
if (self.chunk.len() > 0) {
cvs_remaining = self.cv_stack_len;
output = self.chunk.output();
} else {
cvs_remaining = self.cv_stack_len - 2;
const left_cv = self.cv_stack[cvs_remaining];
const right_cv = self.cv_stack[cvs_remaining + 1];
output = parentOutputFromCvs(left_cv, right_cv, self.key, self.chunk.flags);
}
while (cvs_remaining > 0) {
cvs_remaining -= 1;
const left_cv = self.cv_stack[cvs_remaining];
const right_cv = output.chainingValue();
output = parentOutputFromCvs(left_cv, right_cv, self.key, self.chunk.flags);
}
output.rootBytes(seek, out);
}
pub fn reset(self: *Blake3) void {
self.chunk.reset(self.key, 0);
self.cv_stack_len = 0;
}
}