zig/blake3_tree.zig

Página generada desde conduit@conduit-0.1.0-f7J_7zg5DwCsHBHItwdOz9ZVq8cvH7ceFsk7-m3-T61t (zig/root.zig). No se edita a mano: bun run docs:gen la regenera y bun run docs:check falla si difiere.

BLAKE3 as a verifiable tree (spec/wire-v2.md §2–§3.6): chaining values of aligned subtrees, parent nodes, the root, the pre-order outboard over 16 KiB groups, group proofs, verified ranges (slices) in streaming, and the BEP 52 SHA-256 tree derived on demand in the same read that verifies each group against BLAKE3.

The identity it computes is plain BLAKE3 (b3sum): the tree is BLAKE3's own, left-complete over 1 KiB b3-chunks; a 16 KiB group is an aligned subtree of it, and so is any power-of-two upload chunk ≥ 16 KiB.

Why not std.crypto.hash.Blake3: it does not expose a subtree's chaining value at an offset, parent nodes or the non-root output (its ChunkState and Output are private). The compression core below — compress, the SIMD hash-many over several b3-chunks and the subtree reduction — is copied verbatim from Zig's std (lib/std/crypto/blake3.zig, 0.17.0-dev.1893, MIT licence, © Zig contributors), without the thread-parallel part; the tree API after it is conduit's. Every root is checked against std.crypto.hash.Blake3 and the official BLAKE3 vectors in the tests.

Generic primitive (styx dec-0103: two consumers, conduit and the download verification of styx dec-0129): ADR 0002 places it in zkit (zkit.blake3_tree); it lives here, dependency-free, until zkit publishes it and conduit re-pins.

Untrusted input (styx dec-0117): verification never hands out a byte before its group matched; every length and offset is overflow-checked; nothing here allocates except outboardAlloc; memory is O(log n) per verifier. Freestanding-clean (wasm32).

blake3_tree.CvCopiar enlace

const · línea 855

pub const Cv = [digest_length]u8

A chaining value (or a root): 8 words, little-endian.

blake3_tree.b3_chunk_lenCopiar enlace

const · línea 857

pub const b3_chunk_len: u64 = chunk_length

BLAKE3's own chunk ("b3-chunk").

blake3_tree.group_sizeCopiar enlace

const · línea 859

pub const group_size: u64 = 16 * 1024

Verification granularity: 16 b3-chunks (iroh-blobs chunk group, BEP 52 block).

blake3_tree.chunks_per_groupCopiar enlace

const · línea 860

pub const chunks_per_group: u64 = group_size / chunk_length

Sin ///.

blake3_tree.pair_lenCopiar enlace

const · línea 862

pub const pair_len = 2 * digest_length

One outboard entry: CV(left) ‖ CV(right).

blake3_tree.max_stackCopiar enlace

const · línea 866

pub const max_stack = 64

Entries of a merge or verification stack. A tree over n leaves keeps at most popcount(n) + 1 (merge) or height + 1 (walk) entries; n < 2^54 groups for any u64 size, so 64 is never reached.

blake3_tree.NodeCopiar enlace

type · línea 871

pub const Node = struct

The last compression of a node, before choosing its chaining value (no ROOT flag) or the root (with it). A file's root is the root() of its top node; every other node is only ever used through cv().

blake3_tree.Node.cvCopiar enlace

fn · línea 874

pub fn cv(n: *const Node) Cv

Sin ///.

blake3_tree.Node.rootCopiar enlace

fn · línea 878

pub fn root(n: *const Node) Cv

Sin ///.

blake3_tree.subtreeNodeCopiar enlace

fn · línea 889

pub fn subtreeNode(input: []const u8, chunk_counter: u64) Node

Top node of the subtree over input whose first byte is b3-chunk chunk_counter. A chaining value of the file's tree only when the range is one of its subtrees (spec §2: aligned power-of-two, or the last one); the caller guarantees that (SubtreeHasher checks it).

blake3_tree.parentNodeCopiar enlace

fn · línea 902

pub fn parentNode(left: Cv, right: Cv) Node

Parent node over two child chaining values.

blake3_tree.hashCopiar enlace

fn · línea 907

pub fn hash(input: []const u8) Cv

B3(input): the plain BLAKE3 hash, what b3sum prints.

blake3_tree.groupCountCopiar enlace

fn · línea 912

pub fn groupCount(size: u64) u64

Groups of a file of size bytes; an empty file has one empty group.

blake3_tree.outboardLenCopiar enlace

fn · línea 917

pub fn outboardLen(size: u64) u64

Bytes of the outboard of a file of size bytes: 64 per group but one.

blake3_tree.MergerCopiar enlace

type · línea 939

pub const Merger = struct

Merges consecutive equal-size subtrees (the last may be shorter) into the left-complete tree BLAKE3 builds above them — the same lazy merge as the reference implementation: the stack keeps one entry per set bit of the count, and the newest entry is never merged until another one arrives, so the top node can still be finalized as the root.

blake3_tree.Merger.pushCvCopiar enlace

fn · línea 947

pub fn pushCv(m: *Merger, cv: Cv) void

Sin ///.

blake3_tree.Merger.pushNodeCopiar enlace

fn · línea 960

pub fn pushNode(m: *Merger, node: Node) void

Sin ///.

blake3_tree.Merger.finalCopiar enlace

fn · línea 967

pub fn final(m: *const Merger) ?Node

Top node of everything pushed; null when nothing was, or when a single leaf was pushed by pushCv (its node is not known).

blake3_tree.combineCopiar enlace

fn · línea 983

pub fn combine(cvs: []const Cv) ?Node

Top node of the tree over the chaining values of consecutive equal power-of-two subtrees (upload chunks, groups); the last may be shorter. null for fewer than two: a single subtree's top node is its own.

blake3_tree.SubtreeHasherCopiar enlace

type · línea 996

pub const SubtreeHasher = struct

Streaming hash of one aligned subtree (an upload chunk at its offset, spec §3.5): the bytes arrive in pieces of any size, each full 16 KiB group is hashed once (SIMD across its b3-chunks) and folded; final returns the top node, whose cv() is the chunk's Conduit-Chunk-Cv and whose root() is the file root when the subtree is the whole file. Nothing is read twice and nothing is kept but one partial group and the merge stack.

blake3_tree.SubtreeHasher.InitErrorCopiar enlace

const · línea 1008

pub const InitError = error{NotASubtree}

Sin ///.

blake3_tree.SubtreeHasher.initCopiar enlace

fn · línea 1014

pub fn init(offset: u64, len: u64) InitError!SubtreeHasher

offset and len of the subtree in the file. offset must be a multiple of 16 KiB and, for more than one group, of the subtree's power-of-two span. Whether a short range is the file's last one is the caller's knowledge (wire_v2.chunkRange).

blake3_tree.SubtreeHasher.updateCopiar enlace

fn · línea 1026

pub fn update(h: *SubtreeHasher, bytes: []const u8) error{TooLong}!void

Sin ///.

blake3_tree.SubtreeHasher.finalCopiar enlace

fn · línea 1058

pub fn final(h: *SubtreeHasher) error{Short}!Node

Top node of the subtree. error.Short if fewer bytes than len came.

blake3_tree.outboardFromGroupCvsCopiar enlace

fn · línea 1073

pub fn outboardFromGroupCvs(cvs: []const Cv, out: []u8) error{InvalidLength}!void

Pre-order outboard from the group chaining values of a file (cvs.len groups). out.len must be (cvs.len - 1) · 64.

blake3_tree.groupCvsCopiar enlace

fn · línea 1095

pub fn groupCvs(data: []const u8, out: []Cv) error{InvalidLength}!void

Group chaining values of data (one per group, the empty file has one). out.len must be groupCount(data.len).

blake3_tree.outboardAllocCopiar enlace

fn · línea 1106

pub fn outboardAlloc(gpa: mem.Allocator, data: []const u8) error{OutOfMemory}![]u8

Outboard of data, allocated (outboardLen(data.len) bytes).

blake3_tree.VerifyErrorCopiar enlace

const · línea 1123

pub const VerifyError = error{ /// A parent pair or a group did not hash to what its parent (or the root) says. Mismatch, /// More bytes than the walk needs, or a length that does not fit. TooLong, // …

Sin ///.

blake3_tree.SliceVerifierCopiar enlace

type · línea 1207

pub const SliceVerifier = struct

Streaming verifier of a slice of [start, start+len) (spec §3.4): feed it the slice bytes as they arrive, in pieces of any size; it writes to out exactly the bytes of the range, each only after its 16 KiB group matched the tree under root. Memory: one group plus the walk stack.

blake3_tree.SliceVerifier.InitErrorCopiar enlace

const · línea 1216

pub const InitError = error{InvalidRange}

Sin ///.

blake3_tree.SliceVerifier.ErrorCopiar enlace

const · línea 1217

pub const Error = VerifyError || Writer.Error

Sin ///.

blake3_tree.SliceVerifier.initCopiar enlace

fn · línea 1219

pub fn init(root: Cv, size: u64, start: u64, len: u64) InitError!SliceVerifier

Sin ///.

blake3_tree.SliceVerifier.writeCopiar enlace

fn · línea 1241

pub fn write(v: *SliceVerifier, bytes: []const u8, out: *Writer) Error!void

Sin ///.

blake3_tree.SliceVerifier.finishCopiar enlace

fn · línea 1268

pub fn finish(v: *const SliceVerifier) VerifyError!void

The slice ended: everything it promised must have arrived.

blake3_tree.encodeSliceCopiar enlace

fn · línea 1277

pub fn encodeSlice(data: []const u8, outboard: []const u8, start: u64, len: u64, out: *Writer) (Writer.Error || error{ InvalidRange, InvalidLength })!void

Slice of [start, start+len) of data, from data and its outboard (spec §3.4): the parent pairs of every node that overlaps the range, in pre-order, and the bytes of every overlapping group.

blake3_tree.SideCopiar enlace

type · línea 1301

pub const Side = enum

Sin ///.

blake3_tree.SiblingCopiar enlace

type · línea 1302

pub const Sibling = struct

Sin ///.

blake3_tree.proofFromGroupCvsCopiar enlace

fn · línea 1306

pub fn proofFromGroupCvs(cvs: []const Cv, index: u64, out: []Sibling) error{InvalidLength}!usize

Sibling CVs of group index on its path to the root, bottom-up, from the group CVs of the file. Returns how many were written to out.

blake3_tree.verifyGroupCopiar enlace

fn · línea 1335

pub fn verifyGroup(root: Cv, size: u64, index: u64, group: []const u8, siblings: []const Cv) bool

Verifies group (the bytes of group index) against root with its siblings bottom-up. The sides are recomputed from size and index, never taken from the proof.

blake3_tree.Bep52Copiar enlace

type · línea 1373

pub const Bep52 = struct

SHA-256 Merkle tree of BitTorrent v2 (pieces root): leaves are the SHA-256 of each 16 KiB block, the leaf layer is padded with zero hashes to a power of two. Streaming, O(log n) memory.

blake3_tree.Bep52.pushLeafCopiar enlace

fn · línea 1380

pub fn pushLeaf(b: *Bep52, leaf: [32]u8) void

Sin ///.

blake3_tree.Bep52.finalCopiar enlace

fn · línea 1398

pub fn final(b: *const Bep52) ?[32]u8

Root; null for no leaves (an empty file has no BEP 52 root).

blake3_tree.Bep52PassCopiar enlace

type · línea 1429

pub const Bep52Pass = struct

One pass that derives the BEP 52 tree of a file from its bytes while verifying each group against the BLAKE3 tree (root + outboard), so a corrupted byte is never sealed into a torrent: the host reads each group once and hands it to group in order; BLAKE3 and SHA-256 run over the same buffer. Optional leaves_out keeps the 32-byte leaf hashes (the "second outboard"). No allocation.

blake3_tree.Bep52Pass.InitErrorCopiar enlace

const · línea 1439

pub const InitError = error{ InvalidLength, Empty }

Sin ///.

blake3_tree.Bep52Pass.initCopiar enlace

fn · línea 1441

pub fn init(root: Cv, size: u64, outboard: []const u8, leaves_out: ?[][32]u8) InitError!Bep52Pass

Sin ///.

blake3_tree.Bep52Pass.groupCopiar enlace

fn · línea 1450

pub fn group(p: *Bep52Pass, bytes: []const u8) VerifyError!void

Bytes of the next group (index = groups handed so far).

blake3_tree.Bep52Pass.finalCopiar enlace

fn · línea 1473

pub fn final(p: *const Bep52Pass) VerifyError![32]u8

Sin ///.

wire_v2.CvCopiar enlace

const · línea 855

pub const Cv = [digest_length]u8

A chaining value (or a root): 8 words, little-endian.

wire_v2.group_sizeCopiar enlace

const · línea 859

pub const group_size: u64 = 16 * 1024

Verification granularity: 16 b3-chunks (iroh-blobs chunk group, BEP 52 block).