Skip to main content

Crate scionic_merkletree

Crate scionic_merkletree 

Source
Expand description

Scionic Merkle trees.

A tree holds a folder of files, or one file, under one root hash. A file is a list of chunks, a folder is a list of names, and the root covers all of it. Identical chunks, files and folders have identical hashes wherever they are, so a store keeps each of them once. A sender can show a part of a tree without the rest: one name in a folder, one chunk of a file, or a stretch of a file’s bytes.

spec/FORMAT.md in this repository says exactly what each hash covers.

Modules§

tree
The classic tree over a list.

Structs§

Accepted
What became of a frame that an intake accepted.
BuildOptions
How a tree is built from disk.
Builder
Builds a tree part by part: files from their bytes, folders from their entries, and at the end the record.
ChunkRef
One item of a file’s list: a chunk’s hash, and how many bytes it holds.
Entries
A branch of a folder’s entries, as a peer showed it and as it was checked.
Entry
One entry of a folder: a name, the file or folder under it, and extra data.
ExtraData
A small set of named values, kept beside a name in a folder or in a tree’s record. It holds at most 32 values. A value’s name is 1 to 64 bytes, and a value is at most 1,024 bytes.
FileBranch
A branch of a file’s list, with the nodes that stand for the rest of it.
FileList
A file: the list of its chunks, in the file’s order.
FolderBranch
A branch of a folder’s list, with the nodes that stand for the rest of it. A branch of an empty folder shows nothing, and carries nothing.
FolderList
A folder: the list of its entries, sorted by name, with no name twice.
Hash
A SHA-256 hash: of a chunk’s bytes, or of the bytes that describe a file, a folder or a tree.
HaveMap
Which chunks of a file a peer holds: one bit a chunk, in the file’s order. A peer says this about itself, and nothing proves it.
Intake
Takes one tree into a store, checking every part as it arrives.
MemoryStore
A store in memory.
OpenFile
A file’s list with its tree kept, for showing many parts of it, and for finding the chunks that hold a stretch of bytes.
OpenFolder
A folder’s list with its tree kept, for showing many parts of it.
Record
A tree’s record: the file or folder on top, the tree’s totals, and its extra data. The hash of the record is the tree’s root.
Remote
Reads parts of one tree straight from a peer, with nothing kept.
Responder
Answers requests from a store.
Root
The root of a tree: the hash of its record. It is what a tree is known by.
StreamPeer
A peer at the other end of a connection, where serve answers.
Summary
A tree that is whole and checked.
Target
A file or a folder as the thing above it names it: its kind, its hash, and how many bytes of file content it holds.
Totals
What a tree says about itself as a whole: how much a store has to keep for it. Each counts a thing once, however often the tree uses it.
VerifyOptions
How a held tree is checked, beyond what is always checked.
WriteOptions
How far writing a tree out may go.

Enums§

Arrived
What a frame turned out to be, once its hash was worked out.
Change
One difference between an old tree and a new one.
Chunking
How a tree’s files are split into chunks.
Error
Frame
A frame, read.
Kind
Whether an entry is a file or a folder.
Links
What a builder does with a link or a special file that it finds in a folder. Neither is stored in a tree, and a link is never followed: it could lead out of the folder that is being built.
Refusal
Why a peer does not answer.
Request
What a receiver asks a peer for.
Stored
The kinds of thing a store keeps.

Constants§

BUNDLE_MAGIC
What starts a bundle: a tree written out as one stream of frames.
CHUNKING_FASTCDC_V1
How a tree says that its files were chunked by content.
CHUNKING_KEY
The extra value of a record that says how the tree’s files were chunked.
DEFAULT_MAX_CHANGES
The most changes that diff lists.
DEFAULT_MAX_WRITTEN_ENTRIES
The most files and folders that write_to_disk makes unless it is told otherwise.
FASTCDC_GEAR_SEED_PREFIX
Frozen derivation seed for the gear table below:
FASTCDC_LOOSE_MASK
Selects the top 19 bits (boundary ⇔ h < 2^45). Used for positions at or after FASTCDC_TARGET_SIZE. The loose mask is a subset of the strict.
FASTCDC_MAX_SIZE
Forced-cut ceiling. It exists to bound worst-case chunk size (record framing, transport batching), not as a size anyone chooses: with normalized chunking a forced cut is rare, degenerate-content territory.
FASTCDC_MIN_SIZE
Cut-point skipping floor: no boundary test runs inside the first FASTCDC_MIN_SIZE bytes of a chunk, and those bytes are not hashed at all. Interior chunks are therefore at least FASTCDC_MIN_SIZE + 1 bytes; only a final tail chunk may be smaller.
FASTCDC_STRICT_MASK
Selects the top 23 bits of the rolling hash (boundary ⇔ h < 2^41). Used for positions before FASTCDC_TARGET_SIZE.
FASTCDC_TARGET_SIZE
Normalization switch: the strict mask judges positions before it, the loose mask after it, squeezing the chunk-size distribution toward the target.
FRAME_CHUNK
A chunk’s bytes.
FRAME_FILE_BRANCH
A branch of a file’s list, with the nodes that stand for the rest.
FRAME_FILE_LIST
A file’s whole list.
FRAME_FOLDER_BRANCH
A branch of a folder’s list, with the nodes that stand for the rest.
FRAME_FOLDER_LIST
A folder’s whole list.
FRAME_HAVE
Which chunks of a file a peer holds.
FRAME_RECORD
A tree’s record. The frame is the record itself, whose first byte this is.
FRAME_REFUSED
The peer does not answer, and why.
LIST_ITEM_BYTES
How many bytes one item of a file’s list takes: a hash and a length.
MAX_CARRIED_NODES
The most nodes a branch may carry: 40 on each side of what it shows.
MAX_CHUNK_BYTES
The most bytes a chunk may hold: 8 MiB.
MAX_ENTRY_BYTES
The most bytes a folder’s entry may take: its fixed part, the longest name, and extra data that is as full as it can be.
MAX_EXTRA_BYTES
The most bytes a set of extra data may take: how many values it has, and 32 values that are as long as they can be.
MAX_EXTRA_NAME_BYTES
The most bytes the name of an extra value may hold.
MAX_EXTRA_VALUES
The most values a set of extra data may hold.
MAX_EXTRA_VALUE_BYTES
The most bytes an extra value may hold.
MAX_FOLDER_DEPTH
The most folders that may sit inside one another, the top one counted.
MAX_NAME_BYTES
The most bytes a name may hold.
MAX_RECORD_BYTES
The most bytes a record may take: its fixed part, and extra data that is as full as it can be.
MAX_REQUEST_BYTES
The most bytes a request may take. The longest one asks for a name in a folder: its first byte, the folder’s hash, and the longest name with its length.
REQUESTS_AHEAD_BYTES
How many bytes of requests a StreamPeer sends ahead of their answers. It is small on purpose. The other end answers one request before it reads the next, so requests that are sent ahead wait in the connection, and a connection that could not hold them would leave both ends waiting for each other. Every connection holds this much.
TIMESTAMP_KEY
The extra value of a record that says when the tree was built.

Traits§

Peer
Something that answers requests: a connection to another machine, or a Responder in this one.
Store
A place that keeps bytes under hashes.

Functions§

build
Builds the tree of the folder or the file at path into store, and gives its root.
build_with
Builds a tree as build does, and asks entry_extra for the extra data of every entry.
check_name
Checks a name: 1 to 255 bytes, no /, no zero byte, and not . or ...
chunk_frame
The frame for a chunk’s bytes.
diff
The differences between two trees that a store holds, sorted by path. Both trees must have a folder on top, or be the same tree.
diff_within
The differences between two trees, as diff gives them, where more than most changes are an error.
export
Writes a whole tree to out as one stream: the bundle’s first bytes, the record, and then every list and every chunk once, each after what names it. import reads it back.
fetch
Takes the whole tree with this root from a peer into a store.
file_branch_frame
file_hash
The hash of a file with count chunks and size bytes, whose list’s tree has list on top.
file_list_frame
The frame for a file’s whole list.
file_of
The list of a file’s chunks.
folder_branch_frame
folder_hash
The hash of a folder with count entries and size bytes of file content, whose list’s tree has list on top.
folder_list_frame
The frame for a folder’s whole list.
folder_of
The entries of a folder.
have_frame
import
Reads a bundle that export wrote, and takes the tree with this root from it into a store. Every frame goes through the same checks as a frame from a peer, and the tree must be whole when the stream ends. A frame for something the store holds already is passed over. A frame that nothing in the tree names is an error.
lookup
What is at path in a tree: names with / between them, as in weights/model.safetensors. Nothing is there when a name on the way is missing, or is a file. A path that leads through more folders than a tree may have is an error.
read_file
Writes all of a file’s bytes to out.
read_file_to_vec
A file’s bytes, in memory.
read_frame
Reads one frame from a stream, or nothing when the stream has ended. A frame longer than limit is refused before any of it is read, and a stream that ends inside a frame is an error.
read_open
Writes length bytes of a file whose list is open, from byte offset, to out. It does what read_range does, and finds the chunks without a pass over the list.
read_range
Writes length bytes of a file, from byte offset, to out.
record_of
The record of the tree with this root.
refused_frame
serve
Answers the requests that come in on a connection, until it ends.
unwritable
Why this system cannot hold a name as it is, if it cannot.
unwritable_on_windows
Why Windows cannot hold a name as it is, if it cannot.
verify
Checks a whole tree that a store holds: every list, every chunk’s bytes, the depth of its folders and the totals in its record. It is the same set of checks that a tree goes through when it is taken in.
verify_with
Checks a whole tree that a store holds, with more checks switched on.
write_frame
Writes one frame to a stream: its length as four bytes, then the frame.
write_to_disk
Writes a tree out to disk: its top folder as the new folder dest, or its top file as the new file dest.
write_to_disk_with
Writes a tree out to disk as write_to_disk does, within other limits.

Type Aliases§

EntryExtra
Gives the extra data for one entry: its path on disk, its name, and whether it is a file or a folder.
Result