Attestations and Continuity Proving

Overview

A continuity proof is one of the two key proofs necessary for the Creditcoin Decentralized Oracle to securely move data from one chain to another. A continuity proof certifies that a a block is part of the source chain it originates from, based on attestations and other blocks from that chain.

But why do we need continuity proofs for this? Why can't attestors simply record a consensus about every block that belongs to a given source chain? The answer is on-chain storage! If we wanted to use consensus about every block for later oracle proofs of transactions, then we would need to store a record of every block on our Creditcoin 3 chain. This takes up too much on-chain storage space, especially if we're attempting to support a chain like Solana which produces a very large number of blocks.

Instead we only store attestations to source chain blocks at larger intervals, say every 10 or 100 blocks. Continuity proving allows us to service Oracle queries pertaining to any block, even though we don't store them all. The following is more detail on how a continuity proof is constructed.

Key Terms:

📝 Hash: A cryptographic hash is a mathematical function that takes any input (data of any size) and produces a fixed-size output, known as a hash value.

📝 Merkle Tree: A balanced tree data structure of hashes used to efficiently verify the integrity of large sets of data. With the root of a merkle tree and a small number of hashes from that tree, we can efficiently determine whether any given piece of data belongs to the set it describes.

📝 Root (Merkle Root): A Merkle root is the single cryptographic hash at the top of a Merkle tree, allowing us to rapidly verify the integrity of all the data stored in that tree. With a merkle root and a small number of hashes from the corresponding merkle tree, we can efficiently determine whether any given piece of data belongs to that tree. This property allows us to efficiently determine whether a part of a transaction is contained in the merkle tree for a given block.

let root = eth::starknet_pedersen_mmr(&block);

📝 Digest: Another term for any output from a hash function. In the context of the Creditcoin oracle, a digest usually describes the hash output uniquely identifying a block or attestation. The digest of a block is derived by hashing its block number, merkle root, and previous digest.

let digest = Self::hash_payload(&block_number.into(), &root, &prev_digest);

📝 Previous Digest: The previous digest of a block is just the digest of the block before it. We generate each new block digest using the previous digest.

How Hashing "Chains" Blocks Together

Continuity proving relies on one of the key properties of blockchains. Namely, that the digest of each block is generated using both the contents of that block and the digest of the previous block. Since each block uses part of the previous block, the blocks are said to form a chain. This gives us a very important property:

If the contents of block x are changed, then the digests of blocks x, x+1, ... x+n are all changed as a result. This allows us to cheaply verify whether any part of the chain was changed using only the most recent block.

Generating Attestations

The digest of each attestation is calculated using the following process:

1. Determine which source chain blocks to attest to

This is calculated as:

With an attestation_interval of 10 and the last attestation at block 100, this means we would fetch blocks 101-110.

2. Fetch source chain blocks from source chain RPC nodes.

This process is pretty straightforwards. Either the attestors themselves follow the state of the source chain they are attesting to or else they query an external trusted endpoint of their choice. Note that it should not matter if attestors use an external RPC endpoint as long as a sufficient variety of endpoints is represented among attestors.

3. Construct an attestation fragment

We use the blocks from step 2 to construct an attestation_fragment, which is a chain of blocks bridging from one attestation to the next. As we add blocks to this fragment the digest of each block is calculated as:

let digest = Self::hash_payload(&block_number.into(), &root, &prev_digest);

Because each digest hash integrates the previous one, the digest of the attestation block at the end of our attestation_fragment succinctly summarizes the entire chain. The following visual shows how we calculate block digests bridging from one attestation to the next.

Proving Continuity

When processing specific oracle queries, provers repeat the process of constructing a continuity chain. This time, the chain is constructed to link a "queried" block to the closest attestation after it. By proving such a link, we show that the queried block is actually part of the source chain. In this process the prover would:

1. Get source chain blocks, and use them to construct an attestation fragment.

2. Submit that fragment to the STARK proving process, where the continuity of block digests is checked and a succinct proof that hashing was done faithfully is generated.

3. Submit the resulting STARK proof to the Creditcoin 3 chain, where validators check that the final digest of the continuity proof matches that of the attestation at the same block height on-chain.

The STARK proof only certifies that hashing was done properly on a set of input blocks. It is up to validators to verify that the digest resulting from prover continuity hashing is actually correct.

If a prover decides to maliciously modify a block, perhaps to improperly mint funds, then the digest calculated for that block changes. This digest modification cascades through the chain, eventually reaching the digest of the attestation block. When this digest doesn't match the attestation digest recorded on-chain, continuity is disproven.