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 Swift implementation, at version 2.5.6. The Scionic tree format is specified in spec/FORMAT.md. The Rust library is the reference for it, and this library is held to the same test vectors, under spec/, byte for byte.
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/proofsizes. The tests hold this table to that program.
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 |
swift run -c release proofsizesScionic 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.
createDag,Dagand the transmission packets of 2.4.x are replaced bybuild,verify,fetch,serveandRemote.
Add the package to the dependencies in your Package.swift, and its library to a target's:
dependencies: [
.package(url: "https://github.com/HORNET-Storage/Scionic-MerkleTree-Swift", from: "2.5.6"),
],
targets: [
.target(name: "MyApp", dependencies: [
.product(name: "ScionicMerkleTree", package: "Scionic-MerkleTree-Swift"),
]),
],The module is named ScionicMerkleTree:
import ScionicMerkleTree| Requirement | |
|---|---|
| Swift | 6.0 or newer |
| Systems | Linux, macOS and Windows, each tested on every push, and iOS, built on every push |
| Dependencies | swift-crypto on Linux and Android. Apple's systems hash with CryptoKit and Windows with CNG |
| Foundation | not used by the library |
Turn a folder into a Scionic Merkle Tree, verify it, read a file out of it, and write the tree back to disk:
import ScionicMerkleTree
// A store keeps chunks and lists by their hashes. This one is in memory.
let store = MemoryStore()
// 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 = try build(store, path: "models/my-model")
print(root) // bafkrei...
// Verify everything the store holds for that root: every list, every chunk.
let summary = try verify(store, root)
print("\(summary.files) files, \(summary.record.top.size) bytes")
// Read one file by its path in the tree.
if let entry = try lookup(store, root, path: "config.json") {
let content = try readFile(store, entry.target)
print("config.json holds \(content.count) bytes")
}
// Write the whole tree back out, to a path that does not exist yet.
try writeToDisk(store, root, to: "restored")A root is written as a CID that begins bafkrei. Root gives it as its text, Root(text:) reads one back, 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 program. This example runs as it stands.
import ScionicMerkleTree
// A publisher builds a tree. Here it is built from bytes in memory.
let publisher = MemoryStore()
let builder = Builder(store: publisher, chunking: .fastCDCv1)
let readme = try builder.file(bytes: Array("# My model\n".utf8))
let weights = try builder.file(bytes: [UInt8](repeating: 7, count: 3 << 20))
let top = try builder.folder([
Entry(name: "README.md", target: readme),
Entry(name: "weights.bin", target: weights),
])
let root = try builder.finish(top: top)
// A responder answers requests from the publisher's store.
let peer = Responder(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 remote = try Remote(peer: peer, root: root)
if let entry = try remote.lookup("weights.bin") {
let middle = MemorySink()
try remote.read(entry.target, offset: 1 << 20, length: 16, to: middle)
print(middle.bytes)
}
// 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()
let summary = try fetch(mirror, root, from: peer)
print(summary.files, "files")Syncing runs over anything that reads and writes bytes: a TCP or QUIC stream, a WebSocket, a pipe. The library takes a connection as a ByteSource and a ByteSink, which a type of yours has: one reads as many bytes as are there, up to so many, and gives zero only at the end, and the other writes bytes whole or throws. One side serves and the other asks.
import ScionicMerkleTree
/// The side that holds the tree. It answers one peer's requests until the
/// peer hangs up.
func serveOnePeer(_ store: any Store, over connection: any ByteSource & ByteSink) throws {
try serve(store, from: connection, to: connection)
}
/// The side that wants the tree. A fetch that was cut off goes on from what
/// the store holds when it is run again.
func fetchTree(_ root: Root, into store: any Store, over connection: any ByteSource & ByteSink) throws {
let peer = StreamPeer(input: connection, output: connection)
_ = try fetch(store, root, from: peer)
}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.
A sink that keeps bytes back, as a buffered one does, has a flush method, and the library calls it where the other side waits for what was written. serve reads its requests through a buffer of its own.
| To do this | Use |
|---|---|
| Build a tree from a folder or a file on disk | build, BuildOptions |
| Build a tree from bytes or streams, entry by entry | Builder |
| Verify a tree that a store holds, and mend damage | verify, VerifyOptions |
| Find a path, read a file, read a range of its bytes | lookup, readFile, readRange, readOpen |
| Write a tree out to disk | writeToDisk, 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 | exportBundle, importBundle |
| List what changed between two trees | diff, Change |
| Bring your own transport | Intake, Request, Frame, the Peer protocol |
| Bring your own storage | the Store protocol |
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 the entryExtra of build 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: ScionicError.corrupt carries its hash. With VerifyOptions(discardDamaged: true) the damaged parts are removed, and the next fetch brings back exactly those. VerifyOptions(rechunk: true) also chunks every file again, and refuses a file that was not chunked the standard way.
// Verifying finds the damage, and the error names what was harmed.
do {
_ = try verify(mirror, root)
} catch ScionicError.corrupt(_, let hash) {
print("the damaged chunk is named:", hash == chunk)
}
// With discardDamaged the damaged parts are removed, and the next fetch
// brings back exactly those.
do {
_ = try verify(mirror, root, options: VerifyOptions(discardDamaged: true))
} catch ScionicError.missing {
print("it is missing now")
}
_ = try fetch(mirror, root, from: Responder(publisher))Bundles and changes. A whole tree can travel as one stream, and two trees in one store can be compared. A file is read and written here through two small types over Foundation's FileHandle:
import Foundation
import ScionicMerkleTree
/// The bytes of a file, in order.
final class FileSource: ByteSource {
let file: FileHandle
init(_ file: FileHandle) {
self.file = file
}
func read(into buffer: UnsafeMutableRawBufferPointer) throws -> Int {
// At the end of the file there is nothing more: zero bytes.
guard let bytes = try file.read(upToCount: buffer.count) else {
return 0
}
return bytes.copyBytes(to: buffer)
}
}
/// Bytes written to a file, in order.
final class FileSink: ByteSink {
let file: FileHandle
init(_ file: FileHandle) {
self.file = file
}
func write(_ bytes: UnsafeRawBufferPointer) throws {
try file.write(contentsOf: Data(bytes))
}
}
let store = MemoryStore()
let older = try build(store, path: "release-1")
let newer = try build(store, path: "release-2")
// What changed, by path. The chunks that both releases share are held once.
for change in try diff(store, old: older, new: newer) {
print(change.path)
}
// The new release as one file: the record, then every list and every
// chunk once.
try Data().write(to: URL(fileURLWithPath: "release-2.bundle"))
let bundle = try FileHandle(forWritingTo: URL(fileURLWithPath: "release-2.bundle"))
try exportBundle(store, newer, to: FileSink(bundle))
try bundle.close()
// Reading it back runs the same checks as a fetch from a peer.
let reading = try FileHandle(forReadingFrom: URL(fileURLWithPath: "release-2.bundle"))
let elsewhere = MemoryStore()
let summary = try importBundle(elsewhere, newer, from: FileSource(reading))
try reading.close()
print(summary.files, "files arrived")Every example in this file is run by the tests, from the files in tests/Examples.
Three programs come with the package. examples/roundtrip 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 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/proofsizes prints the branch sizes in the tables above.
swift run -c release roundtrip <folder> <work-dir>
swift run -c release speed <MiB> [folder]
swift run -c release proofsizesA 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 conforms to the Store protocol:
public protocol Store: AnyObject, Sendable {
/// Keeps `bytes` under `hash`. Keeping what is kept already changes nothing.
/// The bytes are lent for the call only: a store that keeps them keeps a
/// copy.
func put(_ kind: Stored, _ hash: Hash, _ bytes: UnsafeRawBufferPointer) throws
/// What is kept under `hash`, if anything.
func get(_ kind: Stored, _ hash: Hash) throws -> [UInt8]?
/// Lends what is kept under `hash` to `body`, and says whether anything is
/// kept: `body` is called once if it is, and not at all if it is not. The
/// bytes are lent for that call only, and an error from `body` is what this
/// throws.
func lend(_ kind: Stored, _ hash: Hash, to body: (UnsafeRawBufferPointer) throws -> Void) throws -> Bool
/// Reads what is kept under `hash` into `into`, when it is as long as `into`
/// is, and says how long it is: nil when nothing is kept. A thing of another
/// length is not read, and `into` is left as it was.
func readInto(_ kind: Stored, _ hash: Hash, _ into: UnsafeMutableRawBufferPointer) throws -> UInt64?
/// Whether anything is kept under `hash`. Unless a store has its own, this
/// asks how long the thing is, so a store that can say that without reading
/// the bytes is not read.
func has(_ kind: Stored, _ hash: Hash) throws -> Bool
/// How many bytes are kept under `hash`.
func size(_ kind: Stored, _ hash: Hash) throws -> UInt64?
/// Forgets what is kept under `hash`.
func remove(_ kind: Stored, _ hash: Hash) throws
}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 need not have has, size, lend or readInto of its own: unless it has, size reads the whole thing, lend asks get, and readInto asks lend and copies what is lent. A store that can answer without reading the bytes should have has and size, and a store on disk should have size at the least: without it, seeing whether a chunk is there takes a read of the whole chunk. It should have 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 readInto: 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 has a complete store that keeps each thing as a file named by its hash.
Every error the library throws is a ScionicError, unless a store, a source or a sink of yours threw it. What went wrong is told by its case, such as .corrupt, .missing, .hashMismatch, .limitExceeded or .invalidData, and a case's values say more where they apply, as the hash does for a damaged chunk above. An error from a store of yours is handed back as it is, and one from a source or a sink of yours inside .stream, which says what was being read or written.
A source that fails is never taken for one that ended. A file whose source breaks off, or a stream that fails with its last bytes, is an error, and not a shorter file. A source that says it gave more bytes than it was asked for is an error too.
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, Chunking.fastCDCv1 |
| root | Root, the hash of the tree's record: Record |
File in src/ |
What it holds |
|---|---|
Format.swift |
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.swift |
The Classic Merkle Tree of a list: building it, showing a part of it, and checking a part. |
FastCDC.swift |
Content-defined chunking (fastcdc-v1), in memory and as a stream. |
Build.swift |
Building a tree from a folder on disk or from bytes. |
Intake.swift |
The one set of checks for a tree that comes from a peer, comes in a bundle, or sits in a store. |
Read.swift |
Finding a path, reading a file or a range of one, and writing a tree out to disk. |
Diff.swift |
What changed between two trees. |
Wire.swift |
The requests, and the frames that answer them. |
Sync.swift |
Serving a store, fetching a tree, reading parts of a peer's tree, and bundles. |
Store.swift |
The Store protocol, and a store in memory. |
Disk.swift |
Holding a folder open, so that nothing below it is reached through a link. |
SHA256.swift |
SHA-256: CryptoKit on Apple's systems, CNG on Windows, and swift-crypto elsewhere. |
Measured on a Windows 11 laptop with Swift 6.3.1, built with -c release: each figure is the median of the five rounds of the benchmark at the end of this file. The two programs named in the tables print the same figures on any machine.
Into a store in memory (examples/speed) |
|
|---|---|
| Content-defined chunking, one core | 7.2 GiB/s |
| SHA-256 of the chunks, one core | 4.1 GiB/s |
| Building a tree from one file of 1 GiB, every core | 17.9 GiB/s |
| Building a tree from ten files of 256 MiB on disk, every core | 9.4 GiB/s |
| Building a tree from 20,000 files of 4 KiB on disk, every core | 0.17 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) |
|
|---|---|
| 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.2 ms |
| Writing the tree back out as files | 1.3 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 hold the library to the guarantees below with forged bytes (tests/ForgeryTests.swift), which are made by a second, independent copy of the format's rules (tests/Support/Oracle.swift).
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.
- Waiting. A build or a check whose store fails on one of its threads ends with that error, and no thread waits for another that has stopped.
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. - Whatever is held open is let go of, however the work ends: as it should, or with an error of its own or of a store, a source or a sink of yours.
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 a small record in memory for every different chunk, so that each chunk is counted once: some tens of megabytes 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(store, 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(store, threads: 1), which keeps memory for one chunk. - A connection has to hold 2,048 bytes of requests on their way, which every connection over a network does. Between a
StreamPeerandserve, a connection that holds nothing works all the same, and for an answerer of another make there isStreamPeer(input:output:ahead: 0). - On Windows, opening a file so that it cannot be led astray costs more than a plain open. With every core at work it does not show. While a folder is being read on Windows, other programs cannot rename or delete it.
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 the Rust library 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 a library reads the file.spec/fastcdc-vectors/manifest.jsonpins where 11 files are chunked, and what each file hashes to.
The files under spec/ are the Rust library's, copied byte for byte. The tests check the vectors' own hash before they use them.
| Implementation | Version | |
|---|---|---|
| Swift, this repository | 2.5.6 | |
| Rust | 2.5.6 | The reference for the format. |
| Go | 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 Rust or the Go library and one built by this library from the same folder have the same root, and each reads what the others write.
swift build --build-tests
swift test
swift test -c release -Xswiftc -enable-testingCI runs these on Linux, macOS and Windows on every push, runs the tests once more on Swift 6.0, the oldest version the package supports, and builds the library for iOS. The tests also hold this file to the package: its Swift code is taken from files that are compiled and run, and its tables of branch sizes from the program that measures them.
The three pictures of this file are the Go library's, byte for byte: docs/pictures/README.md says where they are drawn.
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.


