[Proposal] Introduce a notion of verifiable objects

[ljedrz]

💥 Proposal

It is currently not easy to immediately tell if an object has been verified or not (examples: https://github.com/AleoHQ/snarkVM/pull/990, https://github.com/AleoHQ/snarkVM/pull/1011). This could be solved with types, which would provide a zero-cost way to enforce the verification of objects where necessary, and do so in a very clear way.

The simplest way of achieving it would be with a wrapper type:

pub struct Verified<T>(T);

impl<T> AsRef<T> for Verified<T> {
    fn as_ref(&self) -> &T {
        &self.0
    }
}

impl<T> Verified<T> {
    pub fn into_inner(self) -> T {
        self.0
    }
}

pub trait Verifiable where Self: Sized {
    type Error;

    fn verify(self) -> Result<Verified<Self>, Self::Error>;
}

however, this approach would be limited, as the applicable types would need to have extra variants to ensure that their members have been verified as well (e.g. enforcing verified transactions within a verified block). The right way:tm: to do this is using marker types (playground link):

use anyhow::Result; // for API compatibility with snarkVM
use std::marker::PhantomData;

// The trait allowing objects to be marked as either unverified or verified.
pub trait MaybeVerified {}

// A marker type indicating that an object had been verified.
pub struct Verified;
// A marker type indicating that an object had been unverified.
pub struct Unverified;

impl MaybeVerified for Verified {}
impl MaybeVerified for Unverified {}

// A simplified Transaction object; the _verified marker would be added to the
// regular Transaction object (and all of its members that require verification,
// if lower-level granularity is desired).
struct Transaction<V: MaybeVerified> {
    _verified: PhantomData<V>,
}

// This impl (and the one for the Block), could be derived automatically with
// a proc macro.
impl Transaction<Unverified> {
    pub fn into_verified(self) -> Transaction<Verified> {
        Transaction {
            _verified: Default::default(),
        }
    }
}

// This definition forces all the members of Block to be either Unverified
// or Verified, making the entire object consistent in terms of verification.
struct Block<V: MaybeVerified> {
    transactions: Vec<Transaction<V>>,
}

// This assumes that the Block is marked as verified all at once, but if it were
// to be destructured upon verification, it could be done in a more fine-grained
// fashion.
impl Block<Unverified> {
    pub fn into_verified(self) -> Block<Verified> {
        Block {
            transactions: self.transactions.into_iter().map(|tx| tx.into_verified()).collect(),
        }
    }
}

// A simplified Ledger object to simulate the current snarkVM API.
struct Ledger;

impl Ledger {
    // Any method returning verifiable objects from the Ledger would return
    // either a reference or the value of Object<Verified>, as them being a
    // part of the Ledger means they had already been validated upon insertion.
    
    // Any method validating an object with the Ledger would expect an 
    // Object<Unverified> (taken by value) and return an Object<Verified>.
    
    // Any method introducing a new object to the Ledger would expect an 
    // Object<Verified>.
    
    // Any method where the verification state of a verifiable object is
    // irrelevant can just be generic over MaybeVerified.

    // An obvious candidate for this change: checking an unverified block and
    // marking it as verified if it passes all the checks.
    pub fn check_next_block(&self, block: Block<Unverified>) -> Result<Block<Verified>> {
        // Perform block checks.
        
        // Mark the block as verified.
        let verified_block = block.into_verified();
        
        Ok(verified_block)
    }
    
    // Another obvious candidate: note that the transaction is expected to have
    // been verified at this point.
    pub fn add_to_memory_pool(&mut self, transaction: Transaction<Verified>) -> Result<()> {
        // This method can safely assume that all the transaction-specific  
        // checks have already been performed.
        
        // Perform any memory-pool-specific checks and insert the transaction.
        
        Ok(())
    }
}

At the little extra cost of complexity (an extra trait and marker types) we'd gain:

• safety (as it would no longer be ambiguous if an object has been verified or not)
• greater performance (duplicate checks could easily be found and removed)
• potential for even greater performance in the future (e.g. if verified objects could keep components like proofs in their serialized form when retrieved from own database, reducing deserialization-related penalties)

I'd be happy to lead this change if this proposal is accepted.