Introduction

We describe a protocol which can be used to verify that a commitment has been constructed as expected.

Commitment Schemes

• A commitment scheme is a cryptographic protocol with two roles: a prover and a verifier.
• The prover computes a commitment to a message and sends the commitment to the verifier, binding the prover to that message.
• Examples are cryptographic hashes, Ethereum block headers, and The Graph’s Proof of Indexing.
• A challenge is how the verifier can check the correctness of the committed message without requiring the prover to reveal the entire message.
  • The correctness of a message and commitment depends on the expectations of the verifier, such as how they are used in a high-level protocol.

Bisection Games

• Bisection game is a mechanism designed to efficiently identify and resolve disagreements between different provers in the network, ensuring the integrity and security of the protocols.
• The bisection game identifies the first point of disagreement between the alleged sync committee sequences at the leaves of the provers' Merkle trees.
• The bisection game ensures that the honest prover eventually wins once an adversarial Merkle tree is challenged at sufficient depth.

Proof of Indexing (PoI), a commitment scheme

• PoI is a commitment to data that has been indexed by an indexer.
• Currently, the entire dataset must be revealed in order to verify the correctness of the data.
• Correctness means that the data committed to was sourced from events, traces, or eth_call, optionally processed by Substreams and that the indexer did not exclude any data.

Refereed games

• A protocol with two roles: referee and provers

Commitment Schemes

A commitment scheme is a cryptographic protocol between two parties, a prover and a verifier. The prover computes a commitment to data and sends the commitment to the verifier. The committer's goal is to bind themselves to a message without disclosing it to the verifier. Once a commitment to a message $m$ is made, the committer should be unable to reveal any value other than $m$, which is known as the binding property. Additionally, the commitment should not disclose any information about the message $m$ to the verifier, which is referred to as hiding.