We've designed a new type of Merkle DAG/Merkle Tree hybrid known as the Scionic Merkle Tree. Scionic Merkle Trees contain small branches like Classic Merkle Trees, the folder storage support of Merkle DAGs, and numbered file chunks, so anyone can sync a file by its hash and request the range of chunk numbers they are missing. LeafSync is the name of the simple protocol used to request a range of a file's chunk numbers in order to retrieve a batch of missing file chunks. Identical chunks, files and folders have identical hashes wherever they appear, so each one is stored once and sent once.
This repository is the Rust implementation, at version 2.5.6. It is the reference for the Scionic tree format, which is specified in spec/FORMAT.md. The Go and Swift libraries are held to it by the shared test vectors under spec/.
Scionic Merkle Trees maintain the advantages of IPFS Merkle DAGs with the slim Merkle Branches of Classic Merkle Trees, while providing LeafSync as a new feature that complements any set reconciliation system (IBLTs, negentropy, et al.). In plant grafting, the "Scion" is the upper part of the plant, chosen for its desirable fruits or flowers; it's grafted onto another plant's base to grow together. In a similar vein, the Scionic Merkle Tree was born from grafting together Merkle Trees and Merkle DAGs. This process emphasizes why we use the term "Scion" for the Scionic Merkle Trees: it symbolizes the digital grafting of these two similar data structures, combining their strengths into one piece of software.
- Scionic Merkle Trees: The Best of Both Worlds
- Scionic Merkle Branch Statistics
- Syncing by File Hash and Chunk Number
- What's New in 2.5.6
- Documentation
Merkle Trees are cryptographic structures used to manage and securely verify large amounts of data. However, there's a significant drawback: they cannot store folders of files.
The number of hashes required for a Merkle proof in a Classic Merkle Tree grows logarithmically with the number of file chunks, meaning the growth rate slows as the tree grows. This pattern makes them very efficient for large datasets.
Merkle DAGs were developed as a solution to incorporate folders of files, addressing a key limitation of Classic Merkle Trees. However, this structure has its own challenge: to securely download a single file chunk, you must download the hash of every other file chunk inside the folder it's stored in. Each parent leaf keeps growing as the folder grows, even though the size of each Merkle chunk should always remain the same.
Scionic Merkle Trees resolve this flaw, because each Scionic parent leaf is itself chunked using a Classic Merkle Tree, ensuring every part of the Scionic Merkle Tree is uniformly small. In the most extreme cases of P2P decentralization, a user could retrieve each Merkle branch from a different source without needing to download the entire parent leaf first.
Like Merkle DAGs, Scionic Merkle Trees can accommodate storing folders of files. An entire directory of files and subfolders can be converted into a Scionic Merkle Tree, and a single file can be a tree on its own.
Files are split into chunks with content-defined chunking (FastCDC): chunk boundaries are derived from the bytes themselves rather than from fixed offsets, so identical content produces identical chunks no matter where it appears. Editing a large file no longer shifts every boundary after the edit: only the chunks around the edit change, and every other chunk is reused.
Chunk sizes are bounded: more than 512 KiB, 2 MiB on average, and 8 MiB at most, with only a file's last chunk allowed to be smaller. No crafted content can produce a flood of tiny chunks or one giant chunk to stall producers, verifiers or transports. The algorithm is frozen as fastcdc-v1 in spec/FORMAT.md and pinned by the vectors in spec/fastcdc-vectors, so every implementation cuts the same bytes at the same places.
A hash covers what a thing is, and never where it sits:
- A chunk's hash is the SHA-256 of its bytes, and nothing else.
- A file's hash covers the ordered list of its chunks. It does not cover the file's name.
- A folder's hash covers its entries: each name with the hash under it. It does not cover the folder's own name.
So the same chunk, the same file and the same folder have the same hash in every tree. A store keeps each of them once, and a sync skips whatever the receiver already holds, whichever tree it first arrived with. A renamed file, a copied folder, and a new version of a large file that changes a few megabytes each cost only what is new.
Within each parent leaf, the list of children is organized as a Classic Merkle Tree rather than one potentially large list of hashes. This holds for a folder with its entries and for a file with its chunks. Large files and large folders lead to very long lists, and chunking the parent leaf with a Classic Merkle Tree avoids that scaling problem.
- A folder's Classic Merkle Tree covers its entries, in the order of their names.
- A file's Classic Merkle Tree covers its chunks, in the order they have in the file. A chunk's number is its place in that tree, so a chunk cannot be shown under a number it does not have.
The top of each tree is its Classic Merkle root. The hash of a folder or of a file covers three things: how many items its list has, its size in bytes, and its Classic Merkle root. That hash is what a parent holds for its child, and what the tree's record holds for the folder or file on top. In the pictures above, every folder and file shows those three in a box, and every link by hash ends at that box.
A large file has far more chunks than most folders have entries: about 500,000 for a file of a terabyte. A file of 512 KiB or less is a single chunk, and its tree is that one leaf.
If a user wants to download a specific file chunk within a Scionic Merkle Tree, they no longer need to download the hash of every other chunk of its file, or the listing of every other file in its folder. Instead, they download a Classic Merkle branch for each parent on the way down from the root. This allows the user to verify that the chunk is part of the tree without the rest of it.
A folder's entries are sorted by name, and every fork of the folder's Merkle tree records the name at which its right half begins. A name can therefore sit in exactly one place. One branch proves that a name is in a folder and what it holds, and the same kind of branch proves that a name is not in the folder. A publisher cannot show one file under a name to a reviewer and a different file under the same name to everyone else.
Comparing the size of a Scionic Merkle Branch to the whole parent leaf that a Merkle DAG has you download. These are bytes on the wire in version 2.5.6, measured by examples/proof_sizes.rs.
One file out of a folder, proven by its name:
| Entries in the folder | The whole folder listing | A Scionic branch | Smaller by |
|---|---|---|---|
| 10 | 610 bytes | 300 bytes | 2x |
| 1,000 | 61 KB | 648 bytes | 94x |
| 10,000 | 610 KB | 880 bytes | 693x |
| 1,000,000 | 61 MB | 1,228 bytes | 50,000x |
One chunk out of a file, proven by its number:
| Chunks in the file | About | The file's whole chunk list | A Scionic branch | Smaller by |
|---|---|---|---|---|
| 10 | 20 MB | 360 bytes | 219 bytes | 2x |
| 1,000 | 2 GB | 36 KB | 459 bytes | 78x |
| 10,000 | 20 GB | 360 KB | 619 bytes | 582x |
| 500,000 | 1 TB | 18 MB | 819 bytes | 22,000x |
cargo run --release --example proof_sizesScionic Merkle Trees incorporate Classic Merkle Trees within their structure, so their branches grow logarithmically: each time a folder or a file doubles in size, a branch through it grows by one step. In stark contrast, a parent leaf in an IPFS Merkle DAG grows linearly, because the hash of every child must be downloaded to check any one of them.
A Scionic Merkle Tree says what is in it. The root names what is on top, a folder lists its entries, and a file lists its chunks. LeafSync is the protocol that fetches from it. A receiver asks for:
- a file by its hash, and its chunks by their numbers: chunks 100 to 200 of this file;
- a range of a file's bytes, for which only the chunks that hold those bytes are sent;
- one name of a folder, or a range of its entries.
A chunk's number is its position in its file's list, and the file's hash covers that list, so nobody can lie about a number. A file's hash is the same in every tree, so the same request means the same thing wherever the file appears.
LeafSync complements any set reconciliation system, such as Negentropy. Each does the part it is suited to:
- Set reconciliation syncs the Merkle roots, and the file hashes that link to each root. Two sides work out which roots, and which files under a root, one of them holds and the other is missing. These are small sets: one hash for a tree and one for a file.
- LeafSync then syncs the chunks of each file. A file's chunks are numbered, so a receiver asks for the ranges of numbers it is missing. Chunk hashes are never reconciled as a set. They are by far the largest set, about 500,000 for a terabyte of files, and set reconciliation costs memory and work for every hash in the set.
This library provides LeafSync. It holds no set reconciliation of its own, and works beside whichever one an application runs. A receiver that has nothing but a root needs none at all: it walks down from the root, skips everything it already holds by its hash, and asks for the rest.
A phone can read one file out of a tree of terabytes and hold almost nothing. Which chunks of a file a peer holds is one bit per chunk: about 60 KB for a file of a terabyte. Different ranges of one file can be requested from different peers at the same time.
Everything is verified on arrival. Every answer is checked against a hash that has already been checked, all the way back to the root, before it is kept or passed on. Nothing is trusted because of who sent it.
Version 2.5.6 is a new tree format, built for deduplication and for trees of a terabyte and more. It does not read trees made by 2.4.x, and the same folder has a different root than it had there.
- Deduplication comes first. A chunk's hash covers its bytes alone and a file's hash covers its chunks alone. Names and chunk numbers moved into the parent. Earlier versions hashed a chunk's number into the chunk and a file's name into the file, so the same bytes had different hashes in different places.
- LeafSync numbers a file's chunks, not a tree's leaves. Earlier versions numbered every leaf of a tree. It now asks for a file by its hash and for its chunks by their numbers within that file, which the file's hash covers. Set reconciliation is left with the small sets: the Merkle roots, and the file hashes that link to them.
- A folder has one place for each name, so one branch proves that a name is in a folder, or that it is not.
- Hardened against forged data. A made-up leaf, a file that comes back short, a chunk that belongs to another file, and a store that is tricked into handing back other bytes are each refused, and each has a test.
- Bounded memory and work. Every request says how long its answer may be, a tree's record says how much the tree holds, and writing a tree out counts what it would create before it creates anything.
- Built for terabytes. Building and verifying use every core, a file is never held in memory whole, a damaged chunk is named by its hash and fetched again on its own, and any byte range of a file can be read without the rest of it.
- Safe on disk. A link is never followed, in building or in writing out, even when one is swapped in while the work is under way.
- A new API.
create_dag,Dagand the transmission packets of 2.4.x are replaced bybuild,verify,fetch,serveandRemote.
The crate is on crates.io:
[dependencies]
scionic-merkletree = "2.5.6"Or run cargo add scionic-merkletree. The API documentation is on docs.rs.
| Requirement | |
|---|---|
| Rust | 1.85 or newer |
| Systems | Linux, macOS and Windows, each tested on every push |
| Dependencies | sha2 and rayon; on Unix rustix, and on Windows windows-sys |
unsafe code |
in one function, on Windows only, which asks the system which file an open file is (src/disk.rs); the crate denies it everywhere else |
Turn a folder into a Scionic Merkle Tree, verify it, read a file out of it, and write the tree back to disk:
use scionic_merkletree::{
build, lookup, read_file_to_vec, verify, write_to_disk, BuildOptions, MemoryStore,
};
fn main() -> scionic_merkletree::Result<()> {
// A store keeps chunks and lists by their hashes. This one is in memory.
let store = MemoryStore::new();
// Build a tree from a folder. The root depends on the folder's contents
// alone: not on where the folder is, what it is called, or how many
// threads built it.
let root = build(&store, "models/my-model", &BuildOptions::new())?;
println!("{root}"); // bafkrei...
// Verify everything the store holds for that root: every list, every chunk.
let summary = verify(&store, &root)?;
println!("{} files, {} bytes", summary.files, summary.record.top().size);
// Read one file by its path in the tree.
if let Some(entry) = lookup(&store, &root, "config.json")? {
let bytes = read_file_to_vec(&store, &entry.target())?;
println!("config.json holds {} bytes", bytes.len());
}
// Write the whole tree back out, to a path that does not exist yet.
write_to_disk(&store, &root, "restored")?;
Ok(())
}A root is written as a CID that begins bafkrei. Root implements Display and FromStr, and only that one spelling of a root is read.
Anything that answers requests is a peer: a connection to another machine, or a store in the same process. This example runs as it stands.
use scionic_merkletree::{
fetch, Builder, Chunking, Entry, ExtraData, MemoryStore, Remote, Responder,
};
fn main() -> scionic_merkletree::Result<()> {
// A publisher builds a tree. Here it is built from bytes in memory.
let publisher = MemoryStore::new();
let mut builder = Builder::new(&publisher, Chunking::FastCdcV1);
let readme = builder.file_from_bytes(b"# My model\n")?;
let weights = builder.file_from_bytes(&vec![7_u8; 3 << 20])?;
let top = builder.folder(vec![
Entry::new("README.md", readme, ExtraData::new())?,
Entry::new("weights.bin", weights, ExtraData::new())?,
])?;
let root = builder.finish(top, ExtraData::new())?;
let mut peer = Responder::new(&publisher);
// Read a part of the tree and keep nothing: find one file by its name,
// then take 16 bytes from the middle of it. Only the chunk that holds
// those bytes is sent, and it is verified against the root.
let mut remote = Remote::open(&mut peer, &root)?;
let entry = remote.lookup("weights.bin")?.expect("the tree has the file");
let mut bytes = Vec::new();
remote.read(&entry.target(), 1 << 20, 16, &mut bytes)?;
assert_eq!(bytes, [7_u8; 16]);
// Or fetch the whole tree into another store. Each part is verified
// before it is kept, and what the store already holds is skipped.
let mirror = MemoryStore::new();
let summary = fetch(&mirror, &root, &mut peer)?;
assert_eq!(summary.files, 2);
Ok(())
}Syncing runs over anything that reads and writes bytes: a TCP or QUIC stream, a WebSocket, a pipe. One side serves and the other asks.
use scionic_merkletree::{fetch, serve, MemoryStore, Root, StreamPeer};
use std::io::{BufReader, BufWriter};
use std::net::{TcpListener, TcpStream};
/// The side that holds the tree answers requests until the peer hangs up.
fn serve_one_peer(store: &MemoryStore) -> Result<(), Box<dyn std::error::Error>> {
let (stream, _) = TcpListener::bind("0.0.0.0:4040")?.accept()?;
let mut input = BufReader::new(stream.try_clone()?);
let mut output = BufWriter::new(stream);
serve(store, &mut input, &mut output)?;
Ok(())
}
/// The side that wants the tree fetches it. A fetch that was cut off goes on
/// from what the store holds when it is run again.
fn fetch_tree(
address: &str,
root: &Root,
store: &MemoryStore,
) -> Result<(), Box<dyn std::error::Error>> {
let stream = TcpStream::connect(address)?;
let input = BufReader::new(stream.try_clone()?);
let mut peer = StreamPeer::new(input, BufWriter::new(stream));
fetch(store, root, &mut peer)?;
Ok(())
}The library verifies everything against the root, so a connection does not have to be trusted for the data to be right. It does not encrypt or authenticate the connection: use TLS or Noise where a transfer should be private.
| To do this | Use |
|---|---|
| Build a tree from a folder or a file on disk | build, build_with, BuildOptions |
| Build a tree from bytes or streams, entry by entry | Builder |
| Verify a tree that a store holds, and mend damage | verify, verify_with, VerifyOptions |
| Find a path, read a file, read a range of its bytes | lookup, read_file, read_range, read_open |
| Write a tree out to disk | write_to_disk, write_to_disk_with, WriteOptions |
| Serve a store to peers | serve, Responder |
| Fetch a whole tree from a peer | fetch |
| Read parts of a peer's tree and keep nothing | Remote |
| Carry a whole tree as one file or stream | export, import |
| List what changed between two trees | diff, Change |
| Bring your own transport | Intake, Request, Frame, the Peer trait |
| Bring your own storage | the Store trait |
Building. Building uses every core unless BuildOptions::workers says otherwise. Several files are chunked at once, and threads that are free help chunk and hash a long one. A file is never held in memory whole: a builder holds up to 16 MiB of it, or up to 64 MiB while other threads help it. BuildOptions::timestamp writes the time into the tree's record, and build_with attaches extra data to each entry, such as a file mode or a media type. A link or a special file in the folder is refused, or left out with Links::Skip. It is never followed.
Verifying and mending. verify checks every list and every chunk that a store holds for a root, on every core. When bytes were harmed where they are kept, the error says which thing it is: Error::Corrupt carries its hash. With VerifyOptions::new().discard_damaged(true) the damaged parts are removed, and the next fetch brings back exactly those. VerifyOptions::rechunk also chunks every file again, and refuses a file that was not chunked the standard way.
Bundles and changes. A whole tree can travel as one stream, and two trees in one store can be compared:
use scionic_merkletree::{build, diff, export, import, BuildOptions, MemoryStore};
use std::fs::File;
fn main() -> Result<(), Box<dyn std::error::Error>> {
let store = MemoryStore::new();
let old = build(&store, "release-1", &BuildOptions::new())?;
let new = build(&store, "release-2", &BuildOptions::new())?;
// What changed, by path. The chunks that both releases share are held once.
for change in diff(&store, &old, &new)? {
println!("{}", change.path());
}
// The new release as one file: the record, then every list and every
// chunk once. Reading it back runs the same checks as a fetch from a peer.
export(&store, &new, &mut File::create("release-2.bundle")?)?;
let elsewhere = MemoryStore::new();
import(&elsewhere, &new, &mut File::open("release-2.bundle")?)?;
Ok(())
}Three examples come with the crate. examples/roundtrip.rs takes a folder the whole way round with a store on disk: it builds the tree, verifies it, fetches it into a second store, reads 4 KiB from 64 places in its largest file, writes it out again, and holds the copy to the same root, timing each step. examples/speed.rs measures chunking, hashing, building and verifying into a store in memory, then fetching the tree into a second store and carrying it to a third as a bundle, and builds a folder of your own when it is given one. examples/proof_sizes.rs prints the branch sizes in the tables above.
cargo run --release --example roundtrip -- <folder> <work-dir>
cargo run --release --example speed -- <MiB> [folder]
cargo run --release --example proof_sizesA store keeps bytes under hashes, and that is all the library asks of one. MemoryStore is a store in memory, for tests and small trees. A database, a folder on disk or an object store implements the Store trait:
pub trait Store: Send + Sync {
/// Keeps `bytes` under `hash`. Keeping what is kept already changes nothing.
fn put(&self, kind: Stored, hash: &Hash, bytes: &[u8]) -> Result<()>;
/// What is kept under `hash`, if anything.
fn get(&self, kind: Stored, hash: &Hash) -> Result<Option<Arc<[u8]>>>;
/// Forgets what is kept under `hash`.
fn remove(&self, kind: Stored, hash: &Hash) -> Result<()>;
// `has`, `size`, `lend` and `read_into` have default implementations. A
// store on disk should have its own `size`, `lend` and `read_into`, as the
// text below says.
}Stored says which of four kinds of thing it is: a chunk, a file's chunk list, a folder's listing, or a tree's record. A store never has to understand what it holds: every byte it hands back is checked again before it is used. A store on disk should have its own size: has asks it, and without it, seeing whether a chunk is there takes a read of the whole chunk. It should have its own lend too: the library reads chunks through it, and a store that reads each one into memory it uses again spares the system finding fresh memory for every chunk. And it should have its own read_into: where the library reads several chunks at once, or reads them to send, it hands the store memory as long as each chunk should be, and a store that looks at how long a thing is before it reads any of it reads the chunk straight there. examples/roundtrip.rs has a complete store that keeps each thing as a file named by its hash.
The API and the specification use the same words as this page. This is where each one is found:
| Here | In the API and in spec/FORMAT.md |
|---|---|
| chunk | ChunkRef, Stored::Chunk |
| a file's chunk list | file list: FileList |
| a folder's listing | folder list: FolderList, made of entries: Entry |
| Merkle branch, Merkle proof | branch: FileBranch, FolderBranch |
| chunking | Chunking::FastCdcV1 |
| root | Root, the hash of the tree's record: Record |
| Module | What it holds |
|---|---|
format |
The bytes of a chunk, a file, a folder, an entry and the record, and the branches that show a part of a list. Reading is strict. |
tree |
The Classic Merkle Tree of a list: building it, showing a part of it, and checking a part. |
fastcdc |
Content-defined chunking (fastcdc-v1), in memory and as a stream. |
build |
Building a tree from a folder on disk or from bytes. |
intake |
The one set of checks for a tree that comes from a peer, comes in a bundle, or sits in a store. |
read |
Finding a path, reading a file or a range of one, and writing a tree out to disk. |
diff |
What changed between two trees. |
wire |
The requests, and the frames that answer them. |
sync |
Serving a store, fetching a tree, reading parts of a peer's tree, and bundles. |
store |
The Store trait, and a store in memory. |
Measured on a Windows 11 laptop with Rust 1.100, built with --release: each figure is the median of the five rounds of the benchmark at the end of this file. The two examples named in the tables print the same figures on any machine.
Into a store in memory (examples/speed.rs) |
|
|---|---|
| Content-defined chunking, one core | 7.0 GiB/s |
| SHA-256 of the chunks, one core | 4.1 GiB/s |
| Building a tree from one file of 1 GiB, every core | 16.7 GiB/s |
| Building a tree from ten files of 256 MiB on disk, every core | 9.3 GiB/s |
| Building a tree from 20,000 files of 4 KiB on disk, every core | 0.15 s |
| Verifying every byte of a tree of 1 GiB, every core | 71 GiB/s |
With a store on disk, a folder of 3.5 GiB (examples/roundtrip.rs) |
|
|---|---|
| Building the tree into the store | 0.7 s |
| Verifying every byte from the store | 0.1 s |
| Fetching the tree into a second store | 0.8 s |
| Reading 4 KiB of a file of 1.5 GiB through a peer, on average over 64 places | 1.1 ms |
| Writing the tree back out as files | 1.2 s |
That folder holds one file of 1 GiB twice. The tree stores it once: 3.5 GiB of files are kept as 2.5 GiB of chunks and 40 KB of lists.
A receiver trusts one thing: the root. The peer that sends a tree, the network in between, and the bytes that sit in a store are all treated as untrusted. The tests under tests/ hold the library to the guarantees below with forged bytes, which are made by a second, independent copy of the format's rules (tests/support/oracle.rs).
What is verified
- No forged content. A made-up child under a folder or a file, a real child's branch offered with another child, a file offered as a folder, a list offered as a chunk, and a file given another file's chunks are all refused.
- No short files. A file never comes back shorter than it is. If a chunk is missing, reading is an error.
- One name, one place. A folder cannot show one name at two places, even if it was put together out of order on purpose.
- Every byte of a branch counts. A branch that differs in any one byte is refused, so no two branches prove the same thing.
- Nothing is kept before it is verified. A frame that nothing asked for is refused and not kept. A list that fails a check is not kept either, and that transfer takes nothing more.
What is bounded
- Memory. A peer cannot make a receiver set aside more memory than the tree it trusts calls for: every request says how long its answer may be.
- Size. A tree's record says how much the tree holds, and taking it in stops as soon as it would hold more.
- Expansion. A small tree that stands for an endless one, by holding one folder under many names, is counted before it is written out, and refused.
- Malformed input is an error, and never a crash or a loop.
What a store can count on
- Damage is found and named. Bytes that were harmed in a store are found when the tree is verified, and named by their hash. They can be removed and fetched again on their own.
- A peer cannot delete your data. Nothing a peer sends makes a store remove bytes that are sound. A list that names a held chunk with a wrong length is refused, and the chunk stays.
What happens on disk
- A link is never followed when a tree is built. That holds for a link that is in the folder, and for one that takes a file's or a folder's place while the folder is being read. Each folder is held open while it is read, and what is in it is opened from the folder itself, never by a path that is looked up again.
- Nothing is written outside the destination. A tree is written only to a new place, and only with names the system can hold as they are. The new folders are held open while they are filled, so a link that takes the place of one is not written through.
- A file is read under its own name. Windows drops a dot or a space from the end of a name when it looks a path up, and takes
NULfor a device wherever it stands, so a filemodel.beside a filemodelwould be read asmodel. Everything below the folder a caller names is opened by a path that Windows takes letter for letter. unsafecode in one place only. On Windows, one function asks the system for an open file's 128-bit number, which the standard library can't (src/disk.rs). Everywhere else the crate deniesunsafecode.
The exact rules are in spec/FORMAT.md, under "What a receiver checks", "Limits", "Building a tree" and "Writing a tree out".
- Verifying or fetching a whole tree keeps about a hundred bytes in memory for every different chunk, so that each chunk is counted once: about 50 MB for a terabyte.
- A list is taken in whole. A file's chunk list is 36 bytes a chunk, about 18 MB for each terabyte of the file, and a folder's listing has to fit in memory.
- A tree is built from a folder as the folder is while it is read. If another program changes files in it meanwhile, the tree can hold a mix of old and new. It cannot be led outside the folder.
- Links, special files and file permissions are not stored. An entry's extra data has room for a caller to record a mode.
- A responder that tells a peer which chunks of a file it holds looks into its store for each of them.
Responder::have(false)switches that off for one that serves strangers. - A responder keeps up to 64 MiB of memory between answers, to read the chunks of the next answer into, on every core. One that serves many peers at once may read with the answering thread alone,
Responder::threads(1), which keeps memory for one chunk. - On Windows, opening a file so that it cannot be led astray costs about 16 millionths of a second for each file. With every core at work it does not show. On one thread, 20,000 files of 4 KiB take 1.0 second to build where a plain open would take 0.7. While a folder is being read on Windows, other programs cannot rename or delete it.
- On systems that are neither Unix nor Windows, a folder is not held open, and a link that is swapped in while a folder is read can be followed.
spec/FORMAT.mdis the format: what every hash covers, what a receiver checks, the bytes of every request and answer, and the limits.spec/vectors/manifest.jsonholds the shared vectors, which this crate makes and every implementation is held to, byte for byte: 7 whole trees with every one of their bytes, 9 branches of them, 8 lookups of a name, 12 requests with their answers, 3 exchanges on a connection, and 76 forged inputs that must be refused.spec/vectors/README.mdsays how another library reads the file.spec/fastcdc-vectors/manifest.jsonpins where 11 files are chunked, and what each file hashes to.
| Implementation | Version | |
|---|---|---|
| Rust, this repository | 2.5.6 | The reference for the format. |
| Go | 2.5.6 | |
| Swift | 2.5.6 |
The three libraries are kept in step: one format, one set of vectors and one version number. A tree built by the Go or the Swift library and one built by this library from the same folder have the same root, and each reads what the others write.
cargo fmt --check
cargo clippy --all-targets --locked -- -D warnings
cargo test --locked
cargo test --locked --releaseCI runs these on Linux, macOS and Windows on every push, and runs the tests once more on Rust 1.85, the oldest version the crate supports. The Rust examples in this file are compiled with the tests, and the one that needs no files is run. AGENTS.md holds the rules for contributors.
Released under the MIT License.
The three libraries, measured one after another on the same machine and the same files. None of them is fastest at everything:
- Swift is fastest at chunking a file, at building its tree in memory, at fetching a tree from one store in memory into another, at building a tree from ten large files, and at building a tree again from the copy written out to disk.
- Rust is fastest at writing a tree as a bundle and reading it back, and at building a tree from 20,000 small files.
- Rust and Swift tie for fastest at building a tree into a store on disk, verifying it from there, fetching it into a second store on disk, reading 4 KiB through a peer, and writing a tree out as files. Go is behind them at each.
- All three tie at hashing, and at verifying a tree in memory.
Each time is the median of five rounds. Lower is faster, and the times of those named fastest are in bold.
| Step | Fastest | Go | Rust | Swift |
|---|---|---|---|---|
| A file of 1 GiB, in memory | ||||
| Content-defined chunking, one core | Swift | 0.166 s | 0.142 s | 0.139 s |
| SHA-256 of its chunks, one core | All three tied | 0.242 s | 0.241 s | 0.242 s |
| Building its tree into a store in memory, every core | Swift | 0.229 s | 0.060 s | 0.056 s |
| Verifying every byte of the tree, every core | All three tied | 0.015 s | 0.014 s | 0.014 s |
| Fetching the tree into a second store, as from a peer | Swift | 0.661 s | 0.154 s | 0.151 s |
| Writing the tree as a bundle, and reading that into a third store | Rust | 0.950 s | 0.426 s | 0.436 s |
| Folders on disk, built into a store in memory | ||||
| Ten files of 256 MiB | Swift | 0.330 s | 0.269 s | 0.265 s |
| 20,000 files of 4 KiB | Rust | 0.158 s | 0.154 s | 0.174 s |
| A folder of 3.5 GiB, with a store on disk | ||||
| Building the tree into the store | Rust and Swift, tied | 1.24 s | 0.73 s | 0.72 s |
| Verifying every byte from the store | Rust and Swift, tied | 0.17 s | 0.13 s | 0.14 s |
| Fetching the tree into a second store | Rust and Swift, tied | 2.70 s | 0.82 s | 0.81 s |
| Reading 4 KiB of a file of 1.5 GiB through a peer, on average over 64 places | Rust and Swift, tied | 1.3 ms | 1.1 ms | 1.2 ms |
| Writing the tree back out as files | Rust and Swift, tied | 2.35 s | 1.24 s | 1.26 s |
| Building a tree from the copy, into a third store | Swift | 1.24 s | 0.87 s | 0.76 s |
Fastest names the library with the lowest time. Where another wasn't slower than it in at least four of the five rounds, the two are named as tied, since the difference between them could be chance.
How much the rounds varied: each library's best and worst of the five
| Step | Go | Rust | Swift |
|---|---|---|---|
| A file of 1 GiB, in memory | |||
| Content-defined chunking, one core | 0.165 s to 0.171 s | 0.139 s to 0.143 s | 0.139 s to 0.141 s |
| SHA-256 of its chunks, one core | 0.238 s to 0.244 s | 0.240 s to 0.245 s | 0.239 s to 0.243 s |
| Building its tree into a store in memory, every core | 0.228 s to 0.232 s | 0.059 s to 0.064 s | 0.055 s to 0.058 s |
| Verifying every byte of the tree, every core | 0.013 s to 0.017 s | 0.013 s to 0.014 s | 0.014 s to 0.015 s |
| Fetching the tree into a second store, as from a peer | 0.660 s to 0.664 s | 0.152 s to 0.157 s | 0.149 s to 0.155 s |
| Writing the tree as a bundle, and reading that into a third store | 0.918 s to 1.113 s | 0.420 s to 0.427 s | 0.433 s to 0.437 s |
| Folders on disk, built into a store in memory | |||
| Ten files of 256 MiB | 0.326 s to 0.337 s | 0.263 s to 0.292 s | 0.264 s to 0.269 s |
| 20,000 files of 4 KiB | 0.150 s to 0.171 s | 0.143 s to 0.158 s | 0.171 s to 0.182 s |
| A folder of 3.5 GiB, with a store on disk | |||
| Building the tree into the store | 1.13 s to 1.56 s | 0.72 s to 0.77 s | 0.67 s to 0.74 s |
| Verifying every byte from the store | 0.14 s to 0.19 s | 0.12 s to 0.15 s | 0.13 s to 0.15 s |
| Fetching the tree into a second store | 2.60 s to 2.80 s | 0.78 s to 0.86 s | 0.77 s to 0.87 s |
| Reading 4 KiB of a file of 1.5 GiB through a peer, on average over 64 places | 1.2 ms to 1.3 ms | 1.1 ms to 1.2 ms | 1.1 ms to 1.2 ms |
| Writing the tree back out as files | 2.31 s to 2.42 s | 1.23 s to 1.29 s | 1.23 s to 1.29 s |
| Building a tree from the copy, into a third store | 1.12 s to 1.54 s | 0.77 s to 0.94 s | 0.70 s to 0.89 s |
How it was measured.
- The machine: one Windows 11 laptop, the same for all three.
- The builds: Go 1.27.3; Rust 1.100.0, with
--release; Swift 6.3.1, with-c release. The libraries were at Go13c91dc, Rust2ca0f1fand Swift72bdc41. - The programs: each library's own
speedandroundtrip, which take the same steps in the same order (What Else It Does says how to run them).speedwas given 1,024 MiB and the folder of ten files, and then 1 MiB and the folder of 20,000 files, of which only the time for the folder is taken.roundtripwas given the folder of 3.5 GiB. - The files: bytes that look random, so that nothing in them compresses, and nothing repeats unless it is there twice on purpose. The folder of 3.5 GiB holds one file of 1 GiB twice, one of 1.5 GiB and one of 2,000 bytes, and its tree keeps 2.5 GiB of chunks. The 20,000 files stand in 100 folders.
speedmakes its file of 1 GiB itself. - The order: in each round, each library ran its programs in turn, and the order of the three changed from round to round, so that none always went first. Before each program the machine rested for 20 seconds, so that one program's heat and writing to the disk would not carry into the next.
- The two folders built into a store in memory are the best of five builds within each program: by then the system holds their files in memory, so the library is measured and not the disk.
What it does not show.
- The steps with a store on disk measure the disk as much as the library. From one round to the next, the same library's time for such a step moved by as much as 1.4 times, which is more than Rust and Swift differ by at any of them. The disk is the laptop's own, which other programs may write to at any time. Even a step in memory had a slow round now and then, which the medians leave out.
- Each library's
roundtripbrings its own store on disk. All three keep each thing as a file named by its hash, write it under another name first, and lend what they read from memory that they use again. Rust's and Swift's can also read a chunk straight into the library's memory, which Go's library doesn't ask for. They are not the same code. - A store in memory keeps a copy of every chunk, and on Windows the fresh memory for each costs more than the copy into it. Fetching and bundling into a store in memory measure that too.
- One machine, one system. Nothing here was measured on Linux or macOS, or on another disk.


