How we can create a trust-free decentralized system for ipfs-search?
Special thanks to Nina for helping out with the research
This post is a follow up to our post on frameworks that can allow for the distribution and decentralization of ipfs-search. Here we will look at technologies that can enable us to create a trust-free decentralized system.
A truly decentralized web needs the network to provide privacy and trust by design. This requires algorithms that allow for trustless management. Zero-knowledge proofs and/or cross-validation enables nodes to verify the existence and validity of exchanges. The challenge is to maintain a distributed consensus, without actually being able to see or make public any of the transaction details, guaranteeing privacy.
Zero-Knowledge proofs
A blockchain is a data structure, a linear transaction log, replicated by rewarding the users of devices that log new transactions.
- A change in any block invalidates every block after it, which means that an adversary can not tamper with historical transactions.
- A user only gets rewarded if they are working on the same chain as everyone else, so each participant has an incentive to go with the consensus. The result is a shared definitive historical record.
But:
- It is not “trustless”, because most of its users are trusting the software, instead of trusting other people.
- Blockchain systems do not make the data in them accurate or the people entering the data trustworthy. But it enables any user to audit its integrity.
- Independent auditing, to download the blockchain from a broadcast node and decrypt the Merkle root from the Linux command line to verify transactions requires at least non-trivial technical skills.
Millionaire’s Problem
In Yao’s Millionaire’s Problem, two millionaires want to find out if they have the same amount of money without disclosing the exact amount. This problem is analogous to a more general problem where there are two numbers a and b and the goal is to determine whether the inequality a ≥ b is true or false without revealing the actual values of a and b. Problems like these can be used in Zero-Knowledge Protocols or Zero-Knowledge Password Proofs (ZKPs). The latter, Zero Knowledge Password Proof, is a way of doing authentication without exchanging passwords. This makes them difficult to steal. The first term, Zero-Knowledge Protocol, has appeared more within blockchain circles.
Zero-Knowledge Protocols
A Zero-Knowledge protocol has to have the following properties:
- Completeness — If the statement is true, it will convince a verifier following the protocol of this fact by an honest prover.
- Soundness — If the statement is false, no cheating prover can convince an honest verifier that it is true, except with some small probability.
- Zero-Knowledge — If the statement is true, no verifier learns anything other than the fact that the statement is true. In other words, knowing the statement (not the secret) is enough to imagine a scenario showing that the prover knows the secret. This is formalized by showing that every verifier has some simulator that, given only the statement to be proved (and no access to the prover), can produce a transcript that “looks like” an interaction between the honest prover and the verifier in question.
Zero-knowledge proofs are probabilistic “proofs” (useful for “good enough” algorithms) rather than deterministic proofs, and techniques exist to decrease the soundness error to negligibly small values.
Resources
- September 2017, the first ZKP was conducted on the Byzantium fork of Ethereum, and perhaps we can adapt it for our purpose.
- The knowledge complexity of interactive proof systems, Shafi Goldwasser, Silvio Micali, Charles Rackoff, February 1989
- How to Explain Zero-Knowledge Protocols to Your Children, Jean-Jacques Quisquater, Louis Guillou, Thomas Berson, 1990
- A Survey of Noninteractive Zero-KnowledgeProof System and Its Applications, Huixin Wu and Feng Wang, May 2014
- A Mind-Bending Cryptographic Trick Promises to Take Blockchains Mainstream, Mike Orcutt, November 2017
Smart contracts
A smart contract is a computer protocol intended to digitally ease, verify, or enforce the negotiation or performance of a contract. Smart contracts allow the performance of credible transactions between disparate, anonymous parties without third parties (central authority, legal system, or external enforcement). These transactions are trackable and irreversible and serve to increase the integrity of the ledger.
Resources
- Research Directions in Blockchain Data Management and Analytics, Hoang Tam Vo, Ashish Kundu, Mukesh Mohania, 2018
Voting
Voting models for consensus have certain security properties. They can be asynchronous Byzantine Fault Tolerant and achieve consensus even when some nodes are malicious and delay some messages. High traffic between nodes is generally needed to get consensus. Hashgraph has come up with a voting mechanism where this would not be necessary.
Resources
I Want Your Vote! (Oh Wait I Already Know It), Paul Madsen, 2017
Gossip about gossip
Gossip about gossip, based on the gossip communication protocol, enables nodes to exchange data with other nodes at internet scale. There are currently three known libraries that install a gossip algorithm to discover nodes in a peer-to-peer network: Apache Gossip, gossip-python and Smudge.
Resources
Apache Gossip (UDP, Java)
gossip-python (TCP)
Smudge (UDP, Go)