# Verifiable Indexed Databases With IPLD Prolly Trees --- ### How existing DBs work - Centralized ingestion - Trust in servers ```graphviz digraph Servers { rankdir=LR bgcolor="#11111" fontname="system-ui" fontcolor="#F2F2F2" pad=0.5 node [ shape=rect style="filled,rounded" fillcolor="#6e2de5" fontcolor="#F2F2F2" fontname="System-UI" width=2 ] edge [ color="#2de56e" fontcolor="#F2F2F2" ] data1 [label="Data"] data2 [label="Data"] data3 [label="Data"] leader [label="Leader\n(trusted)"] replica1 [label="Replica\n(trusted)"] replica2 [label="Replica\n(trusted)"] reader [label="Reader"] data1 -> leader data2 -> leader data3 -> leader leader -> replica1 leader -> replica2 replica1 -> reader replica2 -> reader } ``` --- # Merkle Trees  --- ## Prolly Trees - Merkle Tree - Key-value store - Determenistic chunking - ~O(log n) for reads - Efficient merges - Verifiability --- ## Example Slice  --- ## Merkle Path  --- ### Provable Data - Search for records - Attach CID of parent node - Store records/leaf/proof in a CAR file --- ### Verifiable Query Result Format ```json { "results": [ cid1, cid2, ... ], "proofs": [ [cid1, parentCid1], [parentCid1, rootCid], [cid2, parentCid2], [parentCid2, rootCid], ] } ``` --- ## Verification - Get record CID - Fetch record data - Get parent from proof - Verify record is in parent - Iterate up to root --- ## Structure ``` /{collection}/d/{primary key} => record CID /{collection}/i/{index fields}/{index key}{primary key} => primary KEY ``` --- ### Index Key Creation ``` index = ["type", "createdAt"] record = { type: "example", createdAt: 2023, id: "D34DB33F", etc: "whatever" } indexKey = cbor(["example", uint32(2023), "D34DB33F"]) ``` --- ## Why Index? - Fewer lookups (faster, less bandwidth) - Efficient streaming sorting - Handle larger datasets --- # Use cases - Verify data was part of a training set - Verify that log data hasn't been tampered - Search through datasets closer to the edge - Determenistically merge datasets