New DA verification logic

[eyusufatik]

The current DA layer verification logic is something we inherited from sov-sdk. It was written for DA-oriented blockchains, not Bitcoin. In this logic, the circuits are passed blobs of data from the DA layer + inclusion and completeness proofs.

**Inclusion proof**: Proves that given blobs are included in the DA block.

**Completeness proof**: Proves that no relevant transaction from DA was left out.

**Relevant transaction**: DA layer transactions that are relevant to the rollup.

And the DaVerifier trait is defined as:

pub trait DaVerifier: Send + Sync {
    /// The set of types required by the DA layer.
    type Spec: DaSpec;

    /// The error type returned by the DA layer's verification function
    /// TODO: Should we add `std::Error` bound so it can be `()?` ?
    type Error: Debug;

    /// Create a new da verifier with the given chain parameters
    fn new(params: <Self::Spec as DaSpec>::ChainParams) -> Self;

    /// Verify a claimed set of transactions of the given namespace against a block header.
    fn verify_transactions(
        &self,
        block_header: &<Self::Spec as DaSpec>::BlockHeader,
        txs: &[<Self::Spec as DaSpec>::BlobTransaction],
        inclusion_proof: <Self::Spec as DaSpec>::InclusionMultiProof,
        completeness_proof: <Self::Spec as DaSpec>::CompletenessProof,
        namespace: DaNamespace,
    ) -> Result<(), Self::Error>;

    /// Verify that the block header is valid for the given previous light client proof output
    fn verify_header_chain(
        &self,
        latest_da_state: Option<&LatestDaState>,
        block_header: &<Self::Spec as DaSpec>::BlockHeader,
        network: Network,
    ) -> Result<LatestDaState, Self::Error>;

    /// Decompress chunks to complete
    fn decompress_chunks(&self, complete_chunks: &[u8]) -> Result<Vec<u8>, Self::Error>;
}

For a DA layer like Celestia, inclusion and completeness proofs won’t contain the actual contents of the blob. Rather, you supply the blobs, there is some verification logic of blobs against the proofs.

In the Bitcoin case, inclusion proofs and completeness proofs are defined as:

**Inclusion proof**: List of wtxid's in the Bitcoin block, the coinbase transaction (first tx in Bitcoin block), and coinbase transaction txid merkle proof with respect to the block header.

**Completeness proof**: List of relevant transactions in the block. 

**Relevant transaction**: Any transaction with wtxid starting with 0x0101 or 0x0202.

Blobs are of course derived from the Bitcoin transaction, specifically extracted from the witness field of the Bitcoin transaction.

Now realize that, we are passing the data we are interested to the circuits twice, once in the txs (blobs) field in the verify_transaction function and in the CompletenessProof field (in the form of a Bitcoin transaction), which is defined as complete list of Bitcoin transactions relevant to us.

We can parse the “blobs” from the CompletenessProof while we are verifying it, and we actually already do, we check that it is equal to the blob (named tx in the function). So we can skip supplying the circuits with already parsed data, and parse them from the CompletenessProof.

Then we would be left with:

    /// Verify a claimed set of transactions of the given namespace against a block header.
    fn verify_transactions(
        &self,
        block_header: &<Self::Spec as DaSpec>::BlockHeader,
        inclusion_proof: <Self::Spec as DaSpec>::InclusionMultiProof,
        completeness_proof: <Self::Spec as DaSpec>::CompletenessProof,
        namespace: DaNamespace,
    ) -> Result<Vec<<Self::Spec as DaSpec>::BlobTransaction>, Self::Error>;