Prover Contract

What makes the Prover contract interesting is the ability to prove that something happened on a specific chain. The Prover takes as input the proof data that contain a merkle path to the block where the transaction/receipt originated and a merkle path to the transaction/receipt. Also, the height of the known block to the light client contract needs to be provided. This block needs to be ahead or on the block of the transaction that we are proving. With all of this the prover can calculate the expected block merkle root and compare it to the one stored in the light client block.

Proof for a certain receipt can be fetched by making an RPC call (EXPERIMENTAL_light_client_proof) to the Archival node. Together with the block height from the light client contract which needs to be higher than the block height of the block where the transaction/receipt happened, everything that needs to be provided to the Prover is ready.

Structure used by Prover with its substructures:

pub struct FullOutcomeProof {
    /// Proof of execution outcome
    pub outcome_proof: ExecutionOutcomeWithIdAndProof,
    /// Proof of shard execution outcome root
    pub outcome_root_proof: MerklePath,
    /// A light weight representation of block that contains the outcome root
    pub block_header_lite: BlockHeaderLight,
    /// Proof of the existence of the block in the block merkle tree,
    /// which consists of blocks up to the light client head
    pub block_proof: MerklePath,
}

pub struct BlockHeaderLight {
    pub prev_block_hash: Hash,
    pub inner_rest_hash: Hash,
    pub inner_lite: BlockHeaderInnerLite,
}

pub struct ExecutionOutcomeWithIdAndProof {
    /// Proof of the execution outcome
    pub proof: MerklePath,
    /// Block hash of the block that contains the outcome root
    pub block_hash: Hash,
    pub outcome_with_id: ExecutionOutcomeWithId,
}

pub struct ExecutionOutcomeWithId {
    /// The transaction hash or the receipt ID.
    pub id: Hash,
    /// The actual outcome
    pub outcome: ExecutionOutcome,
}

pub struct ExecutionOutcome {
    /// Logs from this transaction or receipt.
    pub logs: Vec<Vec<u8>>,
    /// Receipt IDs generated by this transaction or receipt.
    pub receipt_ids: Vec<Hash>,
    /// The amount of the gas burnt by the given transaction or receipt. 
    pub gas_burnt: u64,     
    /// The total number of the tokens burnt by the given transaction or receipt.
    pub tokens_burnt: u128, 
    /// The transaction or receipt id that produced this outcome.
    pub executor_id: String, 
    /// Execution status. Contains the result in case of successful execution.
    pub status: ExecutionStatus, 
}

To verify proof is correct we use two steps:

1. Execution Outcome Root Verification

If the outcome root of the transaction or receipt is included in block B, then outcome_proof includes the block hash of B, as well as the merkle proof of the execution outcome in its given shard. The outcome root in B can be reconstructed by

shard_outcome_root = compute_root(sha256(execution_outcome.hash()), outcome_proof.proof);
block_outcome_root = compute_root(sha256(shard_outcome_root.hash()), outcome_root_proof);

This outcome root must match the outcome root in block_header_lite.inner_lite.

2. Block Merkle Root Verification

Block hash can be computed from BlockHeaderLight by

fn compute_block_hash(block_header_lite: &BlockHeaderLight) -> Hash {
    sha256(concat(
        sha256(concat(
            sha256(block_header_lite.inner_lite.hash()),
            sha256(block_header_lite.inner_rest_hash)
        )),
        block_header_lite.prev_hash
    ))
}

The expected block merkle root can be computed by

block_hash = compute_block_hash(block_header_lite);
block_merkle_root = compute_root(block_hash, block_proof);

which must match the block merkle root in the light client block of the light client head.

To compute root we use

fn compute_root(node: &Hash, path: MerklePath) -> Hash {
    let mut hash: Hash = *node;
    for item in path.items {
        hash = match item.direction {
            MERKLE_PATH_LEFT => sha256(concat(item.hash(), hash)),
            MERKLE_PATH_RIGHT => sha256(concat(hash, item.hash())),
        }
        .try_into()
        .unwrap()
    }
    return hash;
}