Graph Protocol Graph Day | 2022, 1 Jul 2022

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Graph Day 2022 - Verifiable Information & a Groundbreaking SNARK with Zac Burns of Edge & Node

Description

How do you combat disinformation using web3 technology? In his Graph Day 2022 talk, Edge & Node Research Lead Zac Burns discusses the importance of verifiable information in web3 protocols, and the importance of scaling in a way that is efficient without sacrificing security.

Burns also announced Shellproofs, a novel SNARK that could reduce the cost of resolving millions of state channels by 10,000x upon deployment to The Graph Network. The SNARK was developed in collaboration with Edge & Node, Semiotic Labs, and The Graph Foundation, and a paper detailing the SNARK construction will be published for peer review.

Watch more Graph Day 2022 talks, panels, and announcements here: https://www.youtube.com/playlist?list=PLTqyKgxaGF3SWt8ipQw-Ul9HQvmxulbUu

Time Stamps:

0:00 Introduction
1:45 (Dis)Information
2:27 web3
3:30 Snarks
7:40 Scalar
10:33 Shellproofs
12:25 Verifiable queries
14:35 Shellproofs for Verifiable queries

Keep up with The Graph on social media!

Twitter: https://twitter.com/graphprotocol?s=20
Instagram: https://instagram.com/graphprotocol
LinkedIn: https://www.linkedin.com/company/thegraph
GitHub: https://github.com/graphprotocol
Website: https://thegraph.com

A

What is the value of information we? We live in the information age. Why is that important information is valuable when it reduces uncertainty from important decisions. The familiar pattern goes like this. You spend something for information to make a better decision to achieve an outcome that you care about.

A

So, for example, you might spend time researching local meetups to decide which one to attend, expecting friendship and fun, or maybe you read accountability reports of non-profits to decide where to volunteer, expecting that your contribution will one day enable a discovery that will occur. Your children of a disease thanks to low-cost information, abundance and tools like the graph we can afford to power our days with information to live, happier, healthier and more meaningful lives, but bad actors would seek to weaponize our dependence on information.

A

If you want to control people, the easiest way is to control their flow of information. We see this happening at an alarming scale. Entities offer supposedly free information in exchange for influencing or controlling your behavior.

A

When you perform a search- and you get an ad, that's an attempt to control your behavior through selective information, and this problem goes far beyond ads and even into disinformation corporations fund research to support preset conclusions, bots post on social media, to sway public opinion on crucial issues and governments capture the news to spread propaganda.

A

There's a pernicious war for your mind, waged with disinformation to get you to make choices that benefit someone else at your unwitting expense.

A

This crisis of our time is the backdrop for web3. Our vision for web3 is to build efficient institutions on a solid foundation of incentives and verifiable information.

A

So we turn to snarks as a way to provide verifiability. What are snarks to put it succinctly, a snark is a general-purpose tool for producing proofs of correct computation. Okay, what does that mean without snarks? You can ask questions like given the latest data anchored on blockchain by the national centers for environmental prediction.

A

What country will likely have the least rainfall next year? And you you get the response. Egypt trust me, but in the context of a global society, trust me is increasingly unsatisfying with snarks. We can replace trust with mathematics.

A

The response can be. It is egypt, and here is a mathematical proof that my answer is truthful.

A

Snarks are a wonder kind technology. So why don't? We see ubiquitous use of snarks delivering on their promises, and the answer is that all snarks today, both theoretical and in production, have significant shortcomings.

A

What those shortcomings are we'll get into in a moment, but suffice it to say that these shortcomings are what prevented us from using any existing snark as our foundation for web3.

A

Taking the long view we decided to do something about it, and today I am thrilled to unveil an experimental snark that could forever change how snarks are built. We call it shell proofs.

A

This work is the culmination of three years of research and development that started with jackson blazenski and has grown to become a collaboration between edge and node semiotic and the graf foundation.

A

I want to share what makes shell proofs unique and why it's a giant leap forward for this base, but before I do, we need to take a step back and take a look at some of the options that exist today and really to understand the the context of shell. Proof's promise proof systems today fall into one of two camps and the first camp are systems that rely on something called a trusted. Setup groth, 16 and plonks are snarks that are in this camp. This trusted setup infers that you can't easily check the math.

A

Instead, you have to rely on the integrity of a ceremony performed by a committee, and if you happen to be a committee member who, aided in the trusted setup well, congratulations because you can trust the snark, but for the rest of us there's no way to audit the process after the fact. Maybe we can get on and get in on the next round and we just aren't comfortable with these trust requirements.

A

So we rejected this entire category and focused exclusively on transparent proof, transparent proofs like bulletproofs and starks, carry no trust baggage, transparent proofs are built upon open and auditable mathematics, but unfortunately, by taking this route, we are left with some less than ideal options. If you choose something like bulletproof, you get long verifier times and if you choose something like starks, then you get very large proof sizes and the problem is that blockchain is a resource-constrained environment.

A

Slow, verifiers and large proof sizes have a measurable impact on the cost of using these systems.

A

So it seemed that we're left with the difficult choice of either compromising our values by going back to an option in the trusted setup camp or by choosing one of these and taking an enormous hit to efficiency for our on-chain verifier.

A

What would be great is if we had a snark that was transparent and efficient to verify on chain and that's what shell proofs is.

A

If our security proof wraps up as expected, then we will have a best in-class, prover and verifier, and a world record proof size among transparent snarks.

A

The proof size is notable because we believe that proof size is the most important factor contributing to the overall efficiency of blockchain applications to demonstrate the versatility of shell proofs. I want to share two potential applications within the graph protocol.

A

These applications are very different, but each is a perfect, perfect fit for shelf proofs in its own way.

A

The first application that will speak to the scaling of institutions and the second is going to be on combating disinformation.

A

The first application is dispute resolution and scalar, so we designed the graph to support a fee for every query.

A

When we were looking to build the graph network and see in the growth of traffic on the hosted service, it was clear that we needed a state channel solution that could support billions of queries per day in the near term and support growth for years to come.

A

The seemingly obvious candidate technology for this problem is state channels stage handles are a standard design pattern for moving high bandwidth communication off chain for private parties in a way that can be settled on chain when those parties are finished.

A

Unfortunately, no existing state channel solution came within several orders of magnitude of the tremendous scale of the graph network, so we built scalar the first state channel system that was reliable, low, latency, high throughput and massively parallel, but the dirty secret of all state channels is that if cooperation breaks down and the on-chain dispute processes need to occur, things can get expensive fast.

A

So let's say that an indexer has a million state channels, concurrently open at a time that number seems big, especially before scalar, but it's not that large. In the context of a high performance, low, latency fault, tolerant, distributed system, each scalar state channel requires only about 100 bytes of call data to be submitted on channel dispute requiring a tiny amount of gas, but it would nonetheless require a few hundreds of megabytes to settle a million state channels, despite scalar being one of the most efficient available options for settling disputes.

A

So rather than dumping all of that data on chain. We can use shell proofs to prove that we have the data reducing its size by more than 10 000 times, translating directly into cost savings.

A

A number like 10 000 can seem kind of abstract, so here's a bar chart to show you.

A

What a ten thousand times reduction in size looks like on the right. We have a bar for the value. One and um oh sorry on the right is ten thousand on the left is a bar for the value one, so you can't actually see the bar on the left, because it's less than a pixel tall, and assuming that this is an hd screen, you know 1080p means 1080 pixels tall.

A

We would need 10 of these screens stacked on top of each other and have the graph stretch floor through the ceiling and well into the sky before the bar on the left would occupy a single pixel on this screen. That is what a 10 000 times reduction in size looks like.

A

Let's revisit the properties of shelters.

A

Let's revisit the properties of shell proofs and see why we need shell proofs to be both efficient and trust minimized for scalar. So let's talk about prover efficiency. When we dispute millions of state channels, we need to prove that each is cryptographically signed. Each channel is only collected once and the total value. That's locked in these channels adds up to the correct amount.

A

That's a significant workload that needs to be proven cost effectively under time pressure if an indexer can't collect fees until generating a proof, they're not going to be happy using approver that say crashes, because it runs out of ram because you had too many state channels open and the trust minimization of shell proofs is also essential for scalar. Only by having a snark without a trusted ceremony. Can we credibly state that shell proofs inherits the security properties of the base chain.

A

An efficient verifier is also necessary for scalar. The technical term, for this is verifier succinctness in the context of scalar. Verifier succinctness means that the on-chain smart contract requires very little gas.

A

We set world record lows in this area to lower costs for indexers, which ultimately have to be passed on to consumers and also with verifier succinctness we're showing how to be a good citizen of ethereum and web3 by not crowding out other use cases that are competing for transaction space. Lowering costs for everyone, so the the second of many potential applications for shelf proofs within the graph that I want to share today is verifiable queries.

A

Getting back to the the thing that we talked about when I, when I came up here, you know people rely on the integrity of information queried from the graph to power, their decisions daily. So how do they know that an indexer is not lying today the graph uses cryptoeconomic incentives to prevent fraud, and the way this works is that when you, when you query using the graph, you can cross-check the results against other indexers and if two of them disagree, then you know one is line and you can file a dispute on chain.

A

This process is effective, but imperfect, um and and after actually after you file it on chain, then the that goes to in front of arbitration and and we have to settle that using a human process um using governance. Basically, so here's some some downsides to this approach. First, you know arbitration being a human process, makes it costly to scale.

A

Second, cross-checking relies on redundancy and that reduces the overall network capacity, and finally, incentives do not provide a 100 percent guarantee that liars are deterred or caught, and that means that we can, we can minimize fraud, but never entirely eliminate it.

A

What we would like to do is replace those incentives with mathematics.

A

If we can prove that a response is correct, we can remove the human element, the redundancy and the incentives, and that is precisely what verifiable queries using shell proofs aims to do.

A

A shell proof, verifiable query would start with a commitment to data and construct an argument showing that the response is a faithful execution of your query. The method is analogous to block hashes and merkle proofs and ethereum. If you happen to be familiar with that, we didn't use merkle, proofs or other standard methods for proofs, because the graphs api is expressive and powerful using graphql. You can sort and filter data, follow relations, retrieve collections of entities and their properties, and so without shell proofs.

A

The proof system would would buckle under the weight of all of this expressivity.

A

Let's revisit again why shell proofs must be both efficient and trust minimized, although it's still efficiency and trust minimization that we care about. The reasons are different in this context than when we considered scalar for verifiable queries. Both prover efficiency and verifier succinctness are working toward providing an excellent user experience.

A

A web user typically has very little patience for a page that takes a while to load, so the ultimate goal is to have an efficient prover that would serve each query with low latency, a small proof that can be sent over the wire quickly and a fast verifier that can run in the browser.

A

Verifiable queries also requires trust minimization, so that no privileged group of actors can even have the opportunity to lie about a query result and influence people's behavior.

A

That was a lot to unpack. We just went over two immediate potential use cases for shell proofs within the graph protocol. Both use cases benefit from the completeness of a snark that is efficient enough to scale to large blockchain applications, while also being trust minimized.

A

We think that many more use cases would benefit from shell proofs and we'll be investigating those soon and once we finish peer review of our pre-release, we'll publish multiple research papers on shell proofs and the fundamental breakthroughs that made shell proofs possible.

A

I want to thank my colleagues at edge and node semiotic and the graph foundation who worked unrelentingly in stealth mode, to bring you shell proofs, and thank you for coming on this journey with me to understand. What's so neat about it and where we go from here.

A