⚡📦 CAR Pool & More 🚙💨 A Pragmatic Improvement to Sync Performance github.com/fission-suite/spec/car-pool

The limitation of local knowledge is the fundamental fact about the setting in which we work, and it is a very powerful limitation – Nancy Lynch, A Hundred Impossibility Proofs for Distributed Computing

Some peers are “more peer” than others (especially in an operator context)

BROOKLYN ZELENKA JUSTIN JOHNSON @expede CTO @ Fission @justincjohnson IPFS Engineer @ Fission Won’t have time to cover everything in depth. Come talk to us after, or read the spec ;)

Caveat Trusted, Point-to-Point IPLD Transfer

The Problem Pain In Practice ❤🩹

The Problem Why?

The Problem Why? We 💕 IPLD Fission has deeply nested, cross-linked data that Cannot fit into browser storage Benefits from deduplication Has multiple writers Using mature, universally supported transports would be awesome “Light clients” Speed of light concerns

The Problem Food. Water. Shelter.

The Problem Flakiness in Browsers & CLI & GitHub Actions

The Problem Flakiness in Browsers & CLI & GitHub Actions 🖥

The Problem Are You There? 🤳

The Problem Are You There? 🤳 Keeping nodes reliably connected in production is extremely di cult (browser, server, desktop, mobile) Private networks don’t make sense for our use case ffi (We’d love to share an operator node architecture wish list with any maintainers, though)

The Problem Are You There? 🤳 Keeping nodes reliably connected in production is extremely di cult (browser, server, desktop, mobile) Private networks don’t make sense for our use case (We’d love to share an operator node architecture wish list with any maintainers, though) ffi Up/down over a HTTP Gateway is just LARPing decentralization 🌶

The Problem Are You There? 🤳 Keeping nodes reliably connected in production is extremely di cult (browser, server, desktop, mobile) Private networks don’t make sense for our use case (We’d love to share an operator node architecture wish list with any maintainers, though) Up/down over a HTTP Gateway is just LARPing decentralization 🌶 ffi Native push doesn’t make sense

The Problem Are You There? 🤳 Keeping nodes reliably connected in production is extremely di cult (browser, server, desktop, mobile) Private networks don’t make sense for our use case (We’d love to share an operator node architecture wish list with any maintainers, though) Up/down over a HTTP Gateway is just LARPing decentralization 🌶 Native push doesn’t make sense ffi 🖥

The Problem Are You There? 🤳 Keeping nodes reliably connected in production is extremely di cult (browser, server, desktop, mobile) Private networks don’t make sense for our use case (We’d love to share an operator node architecture wish list with any maintainers, though) Up/down over a HTTP Gateway is just LARPing decentralization 🌶 Native push doesn’t make sense ffi 🖥 💾

The Problem Bitswap Redux

The Problem Bitswap Redux 🎁?

The Problem Bitswap Redux 🎁? 🎁!

The Problem Bitswap Redux 🎁? 👀 🎁!

The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲?

The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲? 🔑🌲!

The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲? 🔑🌲! 👀

The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲? 🔑🌲! 👀 💾 🎟 🖼?

The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲? 🔑🌲! 👀 💾 🎟 🖼? 🎟!

The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲? 🔑🌲! 👀 💾 🎟 🖼? 🎟! 👀

The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲? 🔑🌲! 👀 💾 🎟 🖼? 🎟! 👀 🧸?

The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲? 🔑🌲! 👀 💾 🎟 🖼? 🎟! 👀 🧸? 🧸!

The Problem Bitswap Redux 🗜 🎁? 👀 🎁! 🔑🌲? 🔑🌲! 👀 💾 🎟 🖼? 🎟! 👀 🧸? 🧸!

The Problem Breadth vs Depth

The Problem Breadth vs Depth ✅

The Problem Breadth vs Depth ✅ ❌

The Problem Breadth vs Depth ❌ ✅ ☝

Prior Art On the Shoulders of Giants

Prior Art IPFS Ecosystem

Prior Art IPFS Ecosystem Qri’s DSync GraphSync, Selectors (orthogonal) WNFS(v1) Hashed History Table Merkle Bloom

The Problem Papers 📜

The Problem Papers 📜 To Push or Pull: On Reducing Communication and Synchronization in Graph Computations What’s The Di erence? E cient Set Reconciliation Without Prior Context Synchronizing Namespaces with Invertible Bloom Filters The Hash History Approach for Reconciling Mutual Inconsistency HEX BLOOM: An E cient Method for Authenticity and Integrity Verification in Privacy-preserving Computing ffi ffi ff The Distributed Bloom Filter

CAR Mirror One-to-One

CAR Mirror Strategy

CAR Mirror Strategy Reduce graph scope Send index with request Use heuristics to find deduplication

CAR Mirror

CAR Mirror Balancing Factors

CAR Mirror Balancing Factors Latency Accuracy/Deduplication

CAR Mirror Balancing Factors Latency Equilibrium TL;DR We can a ord to be messy ff Accuracy/Deduplication

CAR Mirror First Reduce Scope

CAR Mirror First Reduce Scope AOT Mutable pointers (IPNS, DNSLink, ENS, di ed CID, etc) ff Previous CAR Mirror sessions

CAR Mirror First Reduce Scope AOT Mutable pointers (IPNS, DNSLink, ENS, di ed CID, etc) Previous CAR Mirror sessions Adaptive Optimization ff Previous CAR Mirror rounds

CAR Mirror First Reduce Scope AOT Mutable pointers (IPNS, DNSLink, ENS, di ed CID, etc) Previous CAR Mirror sessions Adaptive Optimization Previous CAR Mirror rounds No Overlap or Cold Start If the set is small, use random nodes ff “Worst case” looks very similar to Bitswap

CAR Mirror Back of the Napkin

CAR Mirror Back of the Napkin 500k nodes

CAR Mirror Back of the Napkin 500k nodes 46-59 chars + 1 delimiter each ~ average 53 chars each

CAR Mirror Back of the Napkin 500k nodes 46-59 chars + 1 delimiter each ~ average 53 chars each 53 ASCII chars x 500k nodes = 26.5MB

CAR Mirror Back of the Napkin 500k nodes 46-59 chars + 1 delimiter each ~ average 53 chars each 53 ASCII chars x 500k nodes = 26.5MB Gzipped ~ 11.5MB

CAR Mirror Back of the Napkin 500k nodes 46-59 chars + 1 delimiter each ~ average 53 chars each 53 ASCII chars x 500k nodes = 26.5MB Gzipped ~ 11.5MB 🤔 ? r e t t e b o d e w Can

CAR Mirror Bloom Filter Primer

CAR Mirror Context and Heuristics

CAR Mirror Context and Heuristics 500k nodes @ FPP 1/1M = 1.71MB

CAR Mirror Context and Heuristics (Recommend +1 OOM) 500k nodes @ FPP 1/1M = 1.71MB

CAR Mirror Context and Heuristics (Recommend +1 OOM) 500k nodes @ FPP 1/1M = 1.71MB 93% savings! 👍

CAR Mirror Context and Heuristics (Recommend +1 OOM) 500k nodes @ FPP 1/1M = 1.71MB Gzipped ~ 896 KB 93% savings! 👍

CAR Mirror Context and Heuristics (Recommend +1 OOM) 500k nodes @ FPP 1/1M = 1.71MB 93% savings! 👍 Gzipped ~ 896 KB 92% savings! 👍

CAR Mirror Context and Heuristics (Recommend +1 OOM) 500k nodes @ FPP 1/1M = 1.71MB 93% savings! 👍 Gzipped ~ 896 KB 92% savings! 👍 AKA ~ 1 x OOM 🎉 Zero false positives on average

CAR Mirror Stages

CAR Mirror Stages Selection Narrowing Transmission Graph Status Cleanup

CAR Mirror Stages Selection Narrowing Transmission Graph Status Cleanup Next Round

CAR Mirror Over the Wire

CAR Mirror Over the Wire Bloom CID Roots CAR

CAR Mirror Over the Wire Requestor Pull Bloom CID Roots CAR

CAR Mirror Over the Wire Requestor Pull Bloom CID Roots CAR Requestor Push

Meta Pull Previous Round Bloom & Roots 🥺 🦸 📃🌸 Analyze New Roots New Bloom 📀📀📀📀📀 Updated Bloom & Roots Previous Round Hash Set Analyze & Fetch Response CAR Updated Hash Set

Meta Push Previous Round Bloom & Roots 🥺 🦸 Previous Round Hash Set 🥵 📀📀📀📀📀📃 Store & Analyze Request CAR DAG Bloom 🌸 📃 Updated Bloom & Roots Bloom & CID Roots Updated Hash Set

CAR Mirror Straggler Cleanup 🧹 🧹 🧹

CAR Mirror Graph Contraction

CAR Pool Many-to-One

CAR Pool Why

CAR Pool Why Recover multiple providers Stream in true parallel Work sharing Stepping stone to trustless network seeding (more later)

CAR Pool Requestor-Controlled Sharding A-H I-P Q-Z 🦸 🦸 🦸 📱

CAR Pool Invertible Bloom Filter (IBF) Primer

CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0

CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 (Not to scale 📏) 0 0 1 0 1 0 0

CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2

CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2

CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) Counter XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2

CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) Counter XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2 XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3

CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) Counter XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2 XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3 +

CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) Counter XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2 XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3

=

CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) Counter XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2 XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3 XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3

=

CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) Counter XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2 XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3

= XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3

CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) Counter XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2 + = XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3

XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3

CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) Counter XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2 + = XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR

3 🧹Cleanup XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3

CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) Counter XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2 + = XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR

3 🧹Cleanup XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3

CAR Pool Provider Coordinator 🦸 🌸🔁 🤹 📱 🌸🔁 🦸

CAR Pool Linear Network Coding

BONUS: Wild Ideas for Future Research PSI, PSU, NN Compression, XOR-Folding, etc

CAR Pool PSI youtube.com/watch?v=tsCD4i9SpxA

CAR Pool XOR-Folding https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3527984

An Eager Backbone 🦴 Content Addressed Alliance Teaser

🎉 Thank You, IPFS þing 🇮🇸 https://fission.codes ✨ github.com/fission-suite/spec ✨ {brooklyn,justin}@fission.codes @expede & @justincjohnson