Implement ability to determine if a note/tx script cannot be executed against a given account

[bobbinth]

With refactoring done in #826, we've removed TransactionCompiler (as it was no longer necessary). But because of this, we lost one nice feature: ability to estimate if a note/tx script may be executed against a given account. We can only "estimate" this because to know for sure, we'd need to either try to execute the note/tx script or perform some deep static analysis on the underlying code. So, the previous function basically did the following:

• Fail, if we can tell for sure that a note cannot be executed against a given account (e.g., we have a P2ID note, but the account does not have receive_asset procedure).
• Succeed otherwise.

Here is the old code that checked this:

/// Verifies that the provided program is compatible with the target account interface.
///
/// This is achieved by checking that at least one execution branch in the program is compatible
/// with the target account interface.
///
/// # Errors
/// Returns an error if the program is not compatible with the target account interface.
fn verify_program_account_compatibility(
    program: &CodeBlock,
    target_account_interface: &[Digest],
    script_type: ScriptType,
) -> Result<(), TransactionCompilerError> {
    // collect call branches
    let branches = collect_call_branches(program);

    // if none of the branches are compatible with the target account, return an error
    if !branches.iter().any(|call_targets| {
        call_targets.iter().all(|target| target_account_interface.contains(target))
    }) {
        return match script_type {
            ScriptType::NoteScript => {
                Err(TransactionCompilerError::NoteIncompatibleWithAccountInterface(program.hash()))
            },
            ScriptType::TransactionScript => Err(
                TransactionCompilerError::TxScriptIncompatibleWithAccountInterface(program.hash()),
            ),
        };
    }

    Ok(())
}

/// Collect call branches by recursively traversing through program execution branches and
/// accumulating call targets.
fn collect_call_branches(code_block: &CodeBlock) -> Vec<Vec<Digest>> {
    let mut branches = vec![vec![]];
    recursively_collect_call_branches(code_block, &mut branches);
    branches
}

/// Generates a list of calls invoked in each execution branch of the provided code block.
fn recursively_collect_call_branches(code_block: &CodeBlock, branches: &mut Vec<Vec<Digest>>) {
    match code_block {
        CodeBlock::Join(block) => {
            recursively_collect_call_branches(block.first(), branches);
            recursively_collect_call_branches(block.second(), branches);
        },
        CodeBlock::Split(block) => {
            let current_len = branches.last().expect("at least one execution branch").len();
            recursively_collect_call_branches(block.on_false(), branches);

            // If the previous branch had additional calls we need to create a new branch
            if branches.last().expect("at least one execution branch").len() > current_len {
                branches.push(
                    branches.last().expect("at least one execution branch")[..current_len].to_vec(),
                );
            }

            recursively_collect_call_branches(block.on_true(), branches);
        },
        CodeBlock::Loop(block) => {
            recursively_collect_call_branches(block.body(), branches);
        },
        CodeBlock::Call(block) => {
            if block.is_syscall() {
                return;
            }

            branches
                .last_mut()
                .expect("at least one execution branch")
                .push(block.fn_hash());
        },
        CodeBlock::Span(_) => {},
        CodeBlock::Proxy(_) => {},
        CodeBlock::Dyn(_) => {},
    }
}

We should bring back this functionality. One question, is where to put this function. I think TransactionExecutor may be a good option, but there could be alternatives as well.

[Fumuran]

The preliminary interface of the checker function could looks like so. For now I moved it to the TransactionExecutor, but we can move it somewhere else.

impl TransactionExecutor {
    pub fn verify_note_script_account_compatibility(note: &Note, account: &Account) -> Result<???, TransactionExecutorError> {
        // 1. Check whether the provided note is a "basic" note, one of the P2ID, P2IDR or SWAP 
        // notes. In that case, we just need to check whether the account has the procedures 
        // necessary for these notes consumption. If not, return an error.
        // Additionally we should perform the same checks as in the [NoteScreener](https://github.com/0xPolygonMiden/miden-client/blob/f4d3688c26499d02103706f7b1897fc43c5e8e24/crates/rust-client/src/note/note_screener.rs#L60) 
        // to make sure that the note inputs and the account state are correct.

        // 2. If the provided note is not "basic", check that the account has all the procedures
        // which will be called in the note script. If not, return an error. 
        // Check whether the procedures used in the note script are the same as in the "basic" 
        // notes. If so, make sure that the "distribute" and "burn" procedures have a fungible asset
        // as a target account.

        // 3. Perform an asset check, making sure that the assets balance is preserved (account 
        // balance plus incoming assets is greater than or equal to the outgoing assets) which is 
        // the same as a validation in the [Client](https://github.com/0xPolygonMiden/miden-client/blob/f4d3688c26499d02103706f7b1897fc43c5e8e24/crates/rust-client/src/transaction/mod.rs#L712)

        // Return a "potential success"
    }
}

The code above will for sure have some internal helper procedures calls, which could be used in other checks and places.

One of the questions is how to return the check result. In case the note can not be consumed by the account we can return an execution error, but not sure yet how to return a result like "potential sucess". It think it is not that important in case of miden-base, but could be valuable in client. @igamigo could you tell whether this information could be used somehow?

[bobbinth]

I would probably split this up into 2 (or maybe 3) parts:

Stateless check

This would be based purely on analyzing the code and would tell us whether a note with a given script could, in principle be executed against a given account. This check would return Yes, No or Maybe.

Internally, we'd split this up into the check for "well-know" note types and the rest. The interface could revolve around something like AccountInterface enum from miden-client - though, if we could merge this with account component somehow, this would be even better (not sure it is possible). Maybe it could look something like this:

pub enum AccountInterface {
    BasicWallet,
    BasicFungibleFaucet,
    Custom(Digest),
}

/// checks if a note can be consumed against an account with the specified interface
pub fn check(interface: Vec<AccountInterface>, note: &Note) -> CheckResult {

}

Statefull check

This would be checked against a specific account and blockchain state. This could be a method on the TransactionExecutor and would look somewhat similar to the execute_transaction() method - e.g., something like this:

impl TransactionExecutor {
    pub fn check(
        &self,
        account_id: AccountId,
        block_ref: BlockNumber,
        note: &Note,
        tx_args: TransactionArgs, // not sure if these are needed
    ) -> Result<(), TransactionExecutorError> {

    }
}

Internally, here we'd also do a "light check" for well-known notes, and for others, we may need to actually try to execute the transaction. But maybe, there is a way to do it in a lighter way then regular transaction execution. The idea here is that if this check succeed, the execute_transaction should succeed as well.

This is also somewhat related to #938 - so, I've assigned it to you as well. For example, we may want to change the execute_transaction() method to take input notes rather than note IDs:

pub fn execute_transaction(
    &self,
    account_id: AccountId,
    block_ref: BlockNumber,
    notes: InputNotes<InputNote>,
    tx_args: TransactionArgs,
) -> Result<ExecutedTransaction, TransactionExecutorError> {

@igamigo - question: if we provide InputNotes<InputNote> rather than &[NoteId] to execute_transaction() - would this complicate or simplify things on the client side?

[igamigo]

One of the questions is how to return the check result. In case the note can not be consumed by the account we can return an execution error, but not sure yet how to return a result like "potential sucess". It think it is not that important in case of miden-base, but could be valuable in client. @igamigo could you tell whether this information could be used somehow?

I think what's more useful is the information that the client (or a specific account ID) will never be able to execute a note successfully. This is how it currently works on the note screener. Anything else (either "might succeed" or "definitely succeeds") is treated the same way. So it's currently very binary, but in general I do think that the more granular information we can return, the better as long as it does not come with high costs.

pub fn execute_transaction(
&self,
account_id: AccountId,
block_ref: BlockNumber,
notes: InputNotes,
tx_args: TransactionArgs,
) -> Result<ExecutedTransaction, TransactionExecutorError> {
@igamigo - question: if we provide InputNotes<InputNote> rather than &[NoteId] to execute_transaction() - would this complicate or simplify things on the client side?

I don't think it would make a a significant difference, it would just be a matter of moving the retrieval of the note from the DataStore to the moment before executing.

[bobbinth]

I don't think it would make a a significant difference, it would just be a matter of moving the retrieval of the note from the DataStore to the moment before executing.

Would it change handling of unauthenticated notes somehow? With the current approach, we need to insert them into the store before executing transaction - but if notes are provided as a parameter, this may no longer be needed. Though, I guess we'd still need to insert them after the transaction is executed?

[Fumuran]

@bobbinth Just to make sure I'm following:

• The stateless check will verify that the account interface have procedures which will be called in the note script, right? It will be a straightforward check for the BasicWallet and the BasicFungibleFaucet, but for the custom account interface I think we will need to provide something like a Vec<AccountProcedureInfo>. Or, probably, just I didn't get the purpose of the Digest inside the custom account interface.
• For the stateful check we will perform the validation similar to the checks in the client, right? So for the known notes it will be the recipient account ID check and so on (that's what you meant by the "light check", right?), and for the arbitrary notes we will try to execute the transaction, but trying to make it in a "light way".

[igamigo]

I don't think it would make a a significant difference, it would just be a matter of moving the retrieval of the note from the DataStore to the moment before executing.

Would it change handling of unauthenticated notes somehow? With the current approach, we need to insert them into the store before executing transaction - but if notes are provided as a parameter, this may no longer be needed. Though, I guess we'd still need to insert them after the transaction is executed?

I was thinking we would want to insert them to track them anyway, but yes, I think this insertion could be moved to the moment after execution.

[bobbinth]

for the custom account interface I think we will need to provide something like a Vec<AccountProcedureInfo>. Or, probably, just I didn't get the purpose of the Digest inside the custom account interface.

The idea is that Vec<AccountInterface> contains all the info needed to do the check (the info would be similar to what we'd have in Vec<AccountProcedureInfo>). The Custom(Digest) variant just contains the digest of the procedures we couldn't map to any of the well-known ones (e.g., procedures which are not a part of the basic wallet)..

For the stateful check we will perform the validation similar to the checks in the client, right? So for the known notes it will be the recipient account ID check and so on (that's what you meant by the "light check", right?), and for the arbitrary notes we will try to execute the transaction, but trying to make it in a "light way".

Correct.

I think as the first step, we probably can implement the stateless checks and make this issue about that. And once this is done, we can create a follow-up issue to handle the statefull checks.