OSDI '21 - Bringing Decentralized Search to Decentralized Services

Summary

Mee introduces 'D-Search', a decentralized, verifiable, and private search engine system designed to complement the ecosystem of decentralized services and blockchain apps. Addressing issues like opaque censorship and search bias in centralized systems, D-Search leverages a combination of cloud and blockchain technologies for state availability and verifiability. It employs a witness-based approach for ensuring data integrity and employs privacy-preserving techniques like ORAM to protect user queries. The system demonstrates promising performance with minimal latency and scalable throughput, offering a robust solution for enhancing the decentralization of web applications.

Takeaways

• 🌐 The speaker introduces 'D-Search', a decentralized, verifiable, and private search engine system designed for decentralized services and blockchain applications.
• 🔍 D-Search addresses the reliance of current decentralized applications on centralized search engines, which can lead to opaque censorship and search bias, harming user interests and the principles of decentralization.
• 🛠️ The basic search pipeline involves data storage on blockchain or IPFS, crawling to parse data, indexing to generate an inverted index, and querying using the index to provide search results.
• 🚫 Centralized search engines pose threats such as censorship and bias, which D-Search aims to eliminate by providing a decentralized alternative.
• 💡 The idea behind D-Search is to leverage smart contracts and peer-to-peer networks to construct a search pipeline without the latency issues associated with blockchain transaction confirmation times.
• 🔒 To ensure data integrity and availability in a decentralized environment, D-Search introduces 'Kanban', a global append-only storage system built on public cloud infrastructure.
• 🛑 The system uses 'Decentralized Lambdas' for computing power, which are stateless and commit their state to Kanban to ensure continuity in case of unexpected failures.
• 🔄 D-Search ensures verifiable search through 'Verifiable Kanban' and 'Verifiable Lambda', using root hashes committed to the blockchain and witness data structures for offline verification.
• 🔒 To protect user privacy, D-Search employs techniques such as equalizing message plans to counter network adversaries and using ORAM schemes to protect against execution adversaries.
• 📈 The performance of D-Search is demonstrated through a prototype that serves two systems, showing low latency and scalability, with efficient verification processes.
• 🔑 In summary, D-Search is a decentralized search system that combines cloud and blockchain technologies to provide a scalable, verifiable, and private search solution for existing D-Apps.

Q & A

What is the main proposal of the 'd-search' system?

The 'd-search' system is a decentralized, verifiable, and private search engine designed to address the shortcomings in the current ecosystem of decentralized services and blockchain applications.

Why is there a need for a decentralized search engine in the context of DApps?

There is a need for a decentralized search engine because current DApps typically rely on centralized search solutions, which can lead to opaque censorship and paid listing/search bias, harming the interests of users and violating the principles of decentralization.

How does the 'd-search' system address the issue of state availability in a decentralized environment?

The 'd-search' system decouples state from computation by introducing 'Kanban', a global append-only storage with data integrity built on top of public cloud services, ensuring high availability and data integrity.

What is the role of 'Decentralized Lambdas' in the 'd-search' system?

'Decentralized Lambdas' are stateless workers in the 'd-search' system that perform small tasks from the search pipeline and constantly commit their state to 'Kanban', ensuring scalability and minimizing fault disruptions.

How does the 'd-search' system ensure verifiable search results?

The system ensures verifiable search results by using a combination of verifiable 'Kanban' and verifiable 'Lambdas'. It divides command content into epochs, calculates a root hash for each epoch, and commits it to the blockchain, allowing users to verify the search results using on-chain hashes.

What is the significance of the 'witness' in the 'd-search' system?

A 'witness' in the 'd-search' system is a data structure that mirrors the data flow and records the causality between input and output. It is used to ensure data integrity and to enable offline verification of the search process.

How does the 'd-search' system protect user privacy during searches?

The system protects user privacy by using techniques like equalizing all message plans to counter network adversaries and employing ORAM (Oblivious RAM) schemes to protect against execution adversaries, ensuring that each search triggers a different memory address path.

What are the performance metrics of the 'd-search' system as demonstrated in the prototype?

The 'd-search' prototype showed an end-to-end latency of within 50 milliseconds for a single keyword search, demonstrating a user experience comparable to today's search engines. However, throughput dropped significantly when using all ORAM due to its lack of concurrency support.

How does the 'd-search' system scale horizontally?

The 'd-search' system can scale horizontally by deploying workers across different geographic regions. The system's throughput can increase with the addition of more workers, demonstrating native scalability.

What is the difference between native verification and dedicated verification in the context of the 'd-search' system?

Native verification is where a client independently verifies the search results, which can be time-consuming. In contrast, dedicated verification involves verifiers that check the execution integrity and data integrity on behalf of the user, significantly accelerating the verification process by reusing common witnesses.

How does the 'd-search' system leverage existing cloud and blockchain infrastructures?

The 'd-search' system leverages cloud infrastructure for its 'Kanban' storage, benefiting from the cloud's large, cheap storage with high availability. Blockchain infrastructure is used to provide undeniable proofs for combined content, ensuring the verifiability of common contents.