## Introduction

The Light Client (LC) provides a streamlined and efficient way to verify blockchain state transitions and proofs without needing to store or synchronize the entire blockchain. This documentation outlines the client’s features, API endpoints, and data structures, providing developers with comprehensive guidance for effective integration.

## LC high level design

At the core of the LC there are two features:
- Prove epoch transition on the Aptos chain, which is effectively proving a transition from one set of validator to another one.
- Prove at any given point that an account is part of the Aptos state to provide the bridging capabalities between the Aptos chain and Ethereum.


### Epoch Transition Proof (ETP)

The Aptos consensus has at any given time as set of validators that is charged with executing blocks and sign them to append them to the chain state.

A set of given validators is updated at the last block of every epoch on the chain. An epoch on the Aptos chain has a duration of 2 hours.

For a given epoch `N` with a set of validators `Vn`, it is expected to have a block for the transition to epoch `N+1` signed by `Vn` containing the new validator set `Vn+1`.

It is the job of the LC to produce a proof at every epoch change to verify the signature on the validators for the new epoch.

### Account Inclusion Proof (AIP)

To bridge an account from the Aptos chain to the Ethereum chain at any given time the LC needs to prove that the given account exists in the chain state for the latest block produce.

To do so, the LC will first need to verify that the signature on the latest block corresponds to the validator list known for the current epoch. Then, it will have to prove that the account is part of the updated state that this block commits.

### Edge case

The worst edge case that can happen for our LC is when a user wants to get both proofs at the start of a new epoch, meaning that we want to prove both the ETP and the AIP at the same time.

A naïve approach would lead us to a total proving time being equal the sum of their respecting time `Dtotal = Detp + Daip`.

However, in our setting we can have an optimistic approach where we consider that the epoch transition received is valid. Thus, starting both proof generation in prallel. As the proving time for the two proofs is equivalent we end up with `Dtotal = 2 * Detp` which can be reduced to `Dtotal = 2 * Dsig_ver_proving` as most of the proving time is dedicated to the signature verification.

## Aptos Data Structures

Now that we have in mind the high level features brought by the LC, we can take a closer look to the core data structures in the Aptos codebase that are of interest for us to generate the two proofs.

### `ValidatorVerifier`

[*Aptos Core*](https://github.com/aptos-labs/aptos-core/blob/1c6bf2f2940f6357fabcee9260c35ff2ed0119a7/types/src/validator_verifier.rs#L131-L144)

The `ValidatorVerifier` is the representation of a validator list. It contains all information about the validators like their public key or their balance.

### `LedgerInfoWithSignatures`

[*Aptos Core*](https://github.com/aptos-labs/aptos-core/blob/4eae1fa3cf34218dd8b1f2bc1572bd043c3e58cd/types/src/ledger_info.rs#L153-L155)

A `LedgerInfoWithSignatures` represents a signed block by a set of validators. The structure contains two main data of interest to us: the aggregated signature for the block and the block information. This means that the data structures embodies the transition of the chain from one state to another.

For an epoch transition, the block information contains data about the next epoch (i.e. the `ValidatorVerifier` for the next epoch).

### `EpochChangeProof`

[*Aptos Core*](https://github.com/aptos-labs/aptos-core/blob/4eae1fa3cf34218dd8b1f2bc1572bd043c3e58cd/types/src/epoch_change.rs#L39-L42)

The `EpochChangeProof` data structure contains all the necessary data to transition from a given epoch to another one. This can be translated to an `EpochChangeProof` containing all the `LedgerInfoWithSignatures` that represent every increment of epoch along with their respoective change of `ValidatorVerifier`.

### Proof of inclusion for an account

The inclusion of an account in the state needs two data structures to be proven. While a `LedgerInfoWithSignatures` represents a new state of the chain signed by a set of validators, this new state is represented by an accumulation of transaction in the Aptos codebase, with each transaction setting a new state checkpoint.

This means that we need two data structures representing inclusion proofs to prove that an account exists on the chain: a `TransactionAccumulatorProof` and a `SparseMerkleProof`.

### `TransactionAccumulatorProof`

[*Aptos Core*](https://github.com/aptos-labs/aptos-core/blob/4eae1fa3cf34218dd8b1f2bc1572bd043c3e58cd/types/src/proof/definition.rs#L129)

A `TransactionAccumulatorProof` is a data structure used to verify that a given transaction is a part of a `LedgerInfoWithSignatures` and thus is a valid part of the state. The inclusion can be conceptually tied to a Merkle proof, leading to a root hash that is part of the message signed by the validators in a `LedgerInfoWithSignatures`.

### `SparseMerkleProof`

[*Aptos Core*](https://github.com/aptos-labs/aptos-core/blob/4eae1fa3cf34218dd8b1f2bc1572bd043c3e58cd/types/src/proof/definition.rs#L137-L152)

The `SparseMerkleProof` is a Merkle proof for an account leaf in the state tree. Its verification outputs a Merkle Tree root hash, which represents a state checkpoint that is part of a transaction in the `TransactionAccumulatorProof`.

## Verification

**Epoch Change Message (Every 2 Hours)**: The Light Client sends the ValidatorVerifier hash along with the epoch change proof. It then extracts the public values (the ValidatorVerifier) and compares them to verify that the proof is accurate and that the computation was successful.
**Account Inclusion Message (On Demand)**: The Light Client sends the required Merkle proof data for account inclusion, accompanied by the relevant state hash and the corresponding proof. The Merkle proofs are then used to generate the state root hash, which is compared against the proof output to ensure data consistency.

> Note:
All necessary data required for on-chain verification, along with the proof itself, will be returned after the computation is completed to enable efficient and accurate validation.

## Implementation

To generate the two proofs we need we have created to WP1 programs the can be leveraged both at proving and verification time. Those programs can be found in our [`example-light-client-internals`](https://github.com/wormhole-foundation/example-zk-light-clients-internal/) repositiory.

*[`Epoch transition program`](https://github.com/wormhole-foundation/example-zk-light-clients-internal/blob/main/aptos/programs/ratchet/src/main.rs)*
*[`Account inclusion proof`](https://github.com/wormhole-foundation/example-zk-light-clients-internal/blob/main/aptos/programs/merkle/src/main.rs)*

### Epoch transition program IO

#### Inputs

The following data structures are required for proof generation (detailed data structure references can be found at the end of this document):

- **Latest Known `TrustedState`**: The most recent known state, representing the trusted state for the current epoch.

- **`ValidatorVerifier`:** Validator set information for epoch N, provided by the user.

- **`EpochChangeProof`**: Proof structure required to transition to the next epoch.

- **`LedgerInfoWithSignatures`:** Signed ledger info that includes the new validator set for epoch N+1, provided by the user.

#### Outputs

- **Previous `ValidatorVerifier` Hash:** The previous validator verifier hash, used for comparison.
- **Ratcheted `ValidatorVerifier` Hash:** The hash representing the new validator set for epoch N+1.

### Account inclusion program IO

#### Inputs

The following data structures are required for proof generation (detailed data structure references can be found at the end of this document):

- **Block Validation**
- **Latest `LedgerInfoWithSignatures`:** Contains the signed ledger info that acts as a root of trust for the current epoch.
- **`ValidatorVerifier`:** The verifier set for the current epoch.
- **Merkle Inclusion**
- **Transaction Inclusion in `LedgerInfo`:** Verifies that the specified transaction exists in the block with a valid state checkpoint.
- **`TransactionInfo`:** Details of the transaction to be verified.
- **Transaction Index in Block:** Position of the transaction within the block.
- **`TransactionAccumulatorProof`:** Accumulator proof that confirms the transaction’s inclusion.
- **Latest `LedgerInfoWithSignatures`:** Acts as a root of trust.
- **Account Inclusion in State Checkpoint:** Verifies that the account exists in the blockchain’s state at the block level.
- **`SparseMerkleProof`:** Proof that the account is included in the state.
- **Account Key in Tree:** Path of the account within the Merkle tree.
- **Value Hash for Account Leaf:** Initial hash used for inclusion verification.

#### Outputs

- **Previous `ValidatorVerifier` Hash:** The previous validtor verifier hash, used to validate the incoming data.
- **State Root Hash:** The root hash of the state, derived from the `TransactionInfo::state_checkpoint`.

### Verification Process and Predicate Integration

The Light Client verification mechanism integrates three fundamental predicates to ensure the integrity and authenticity of blockchain data:

1. Predicate $P1(n)$:
Validates the existence of a block header at block height $h$ containing the Merkle root $S_h$, which is signed validly by the committee with hash $H_n$. This ensures that the block header and its contents are legitimate and recognized by the current validator set.

2. Predicate $P2(n)$:
Confirms the existence of a block header that includes the stake table with hash $H_{n+1}$, signed by the committee with hash $H_n$. This predicate is mandatory for the epoch transition proof where the validator set for the next epoch $(H_{n+1})$ must be authenticated by the current epoch's validators $(H_n)$.

3. Predicate $P3(A, V, S_h)$:
Demonstrates the inclusion of value $V$ for account $A$ in the Merkle root $S_h$. This predicate is essential for verifying that a specific account state is included in the verified block.

#### Integration with Light Client Programs
Epoch Transition Proof (ETP) primarily implements Predicate $P2(n)$. It utilizes the `EpochChangeProof` and the current `ValidatorVerifier` to authenticate the transition from one validator set to another, ensuring that the transition is recognized and signed by the current set of validators.

Account Inclusion Proof (AIP) incorporates both Predicate $P1(n)$ and Predicate $P3(A, V, S_h)$. It leverages the `LedgerInfoWithSignatures` to validate the existence and correctness of a block header $(P1)$, and uses `SparseMerkleProof` along with `TransactionAccumulatorProof` to validate the inclusion of an account's state value $(P3)$.

### Sequential Verification for Account Inclusion
To demonstrate an account's inclusion at any block height, the verifier, that updates and maintain the latest known validator set hash $(H_n)$, can use the proofs in the following sequence:

1. Ratcheting the Validator Set:
A sequence of `EpochChangeProof` $(P2(i) for i = 0..N)$ allows the verifier to authenticate each epoch's transition and update the known validator set accordingly.

2. Validating Account State:
Once the latest validator set is established, the Light Client can use the Account Inclusion Proof to verify the presence of an account's state in the latest valid block. This proof uses the final validator set to ensure the account state's inclusion, corresponding to Predicate $P3$ applied to the result of $P1$ for the largest $N$.

By structuring the verification process around these predicates, the Light Client ensures the integrity of the blockchain data it processes while providing a clear, verifiable path for external parties to trust the proofs it generates.

### Implementation References
To explore the implementation of these verification mechanisms, please refer to our example programs:

- [Epoch Transition Program](https://github.com/wormhole-foundation/example-zk-light-clients-internal/blob/main/aptos/programs/ratchet/src/main.rs): Implements the logic for ratcheting through epoch transitions.
- [Account Inclusion Proof Program](https://github.com/wormhole-foundation/example-zk-light-clients-internal/blob/main/aptos/programs/merkle/src/main.rs): Provides the mechanism to verify account inclusion through Merkle proofs.

### Run verification

The verification for our programs can be done leveraging WP1 features when not on a chain.

To do so, leverage the `wp1-sdk` crate and its `ProverClient` structure. Some examples of this can be found in our [tests](https://github.com/wormhole-foundation/example-zk-light-clients-internal/blob/main/aptos/light-client/src/merkle.rs#L250-L255) or [benchmarks](https://github.com/wormhole-foundation/example-zk-light-clients-internal/blob/main/aptos/light-client/benches/merkle/src/main.rs#L61-L65).

> Note:
> You will need the compiled program to be able to verify a proof for it. The binaries for our programs can also be found in our repository, both for the [ETP](https://github.com/wormhole-foundation/example-zk-light-clients-internal/blob/main/aptos/aptos-programs/artifacts/ratchet-program) and [AIP](https://github.com/wormhole-foundation/example-zk-light-clients-internal/blob/main/aptos/aptos-programs/artifacts/merkle-program).