Smart contract format in Rust

[bobbinth]

Below is a sketch of how we could potentially express Miden smart contracts in Rust. This is very preliminary, and I'm not sure yet if all of this is possible (or what is the best route for making it work).

Miden smart contracts can be thought of consisting of two components: Accounts and Notes. Both are described below.

First, let's start with accounts:

use miden::{
    account::{Account, std::BasicWallet},
    crypto::{
        dsa::falcon::{self, PubKey},
        crypto::hash::rpo,
    },
    Felt, tx,
};

/// Declares [MyWallet] as a Miden account. A single struct ([PubKey]) will be stored in the
/// storage of this account.
/// 
/// Implementing [Account] enables using account accessors such as `get_id()`, `incr_nonce()`,
/// `add_asset()`, `remove_asset()` etc.
/// 
/// For every [Account] struct, we'd need to output a MASM file. For example, for this one it
/// could be `my_wallet.masm`.
#[derive(Account)]
pub struct MyWallet {
    pub_key: PubKey,
}

/// This provides implementations of [BasicWallet] methods (e.g., send_asset(), receive_asset())
/// for [MyWallet].
/// 
/// Ideally, we should not be able to override any of the [BasicWallet] methods here but I'm not sure
/// this will be possible until something like https://internals.rust-lang.org/t/pre-rfc-final-trait-methods
/// is implemented.
impl BasicWallet for MyWallet {}

/// This defines additional methods for [MyWallet] account.
impl MyWallet {
    /// A method for authenticating transactions. `nonce_delta` is to be provided by the caller.
    pub fn auth_tx(&mut self, nonce_delta: u32) {
        self.incr_nonce(nonce_delta);

        // combine account and transaction identifiers into a single array of elements and compute
        // their hash using RPO hash function
        let comm: [Felt; 10] = array![
            self.get_id(),
            Felt::new(nonce_delta),
            tx::get_input_notes_hash(),
            tx::get_output_notes_hash(),
        ];
        let m = rpo::hash_elements(&comm);

        // run Falcon signature verification algorithm
        falcon::verify_sig(self.pub_key, m);
    }
}

Now that we have an account defined, we can define a note which could be executed against this account:

use miden::{
    account::{AccountId, std::BasicWallet},
    note::Note, tx,
};

/// Declares [MyNote] as a note. This note will have 2 inputs: recipient and recall_height. We'll
/// need to figure out how to handle note input limit which is currently 16 elements.
/// 
/// Implementing [Note] enables using note accessors such as `sender()` and `assets()`.
/// 
/// For every note we need to output a single MASM file - e.g., `my_note.masm`. 
#[derive(Note)]
pub struct MyNote {
    recipient: AccountId,
    recall_height: u32,
}

impl MyNote {
    /// This declares `claim()` function as one of the clauses of this note. This function can be
    /// executed against any account which implements [BasicWallet] interface.
    /// 
    /// A clause has a fixed signature: it takes `&self` as the first argument, and an account of the
    /// specified generic type as the second argument.
    ///
    /// A note can have multiple clauses, but these will need to be combined into a single Miden VM
    /// program at compile time.
    #[clause]
    pub fn claim<A: BasicWallet>(&self, account: &mut A) {
        assert!(self.recipient == account.get_id());
        for asset in self.assets() {
            account.receive_asset(asset);
        }
    }

    /// This declares `recall()` function as another clause of this note. This function can also
    /// be executed against any account which implements [BasicWallet] interface. But we could also
    /// specify a different account type for a clause.
    #[clause]
    pub fn recall<A: BasicWallet>(&self, account: &mut A) {
        assert!(tx::get_block_number() >= self.recall_height);
        assert!(self.sender() == account.get_id());
        for asset in self.assets() {
            account.receive_asset(asset);
        }
    }
}

Things not covered in the above:

• Optional transaction scripts.
• Specifying well-known note scripts.
• Calling "uniquely-defined" methods of an account from note scripts.

[jan-ferdinand]

/// Ideally, we should not be able to override any of the [BasicWallet] methods here but I'm not sure
/// this will be possible until something like https://internals.rust-lang.org/t/pre-rfc-final-trait-methods
/// is implemented.

It might be possible to use sealed traits for this. In particular, using signature-sealed default methods with public functions to call them might achieve what you want here. (Credit for that playground to the linked article.)

[bobbinth]

Thank you for the link! If I understood things correctly, it seems like we would still be able to override the callable_method() - so, it helps but not all the way.

[jan-ferdinand]

Can't you just make all methods non-overridable, like in SealedTrait here?

[bobbinth]

Ah - I see! So, in the case of BasicWallet, it could look like:

mod basic_wallet {
    mod private {
        pub struct Token;
    }

    pub fn receive_asset(account: &mut impl BasicWallet, asset: Asset) {
        account.receive_asset(asset, private::Token);
    }

    pub trait BasicWallet: Account {
        fn receive_asset(&mut self, asset: Asset, _ : private::Token) {
            self.add_asset_to_vault(asset);
        }
    }

}

And then later on (assuming MyStruct implements BasicWallet), instead of doing:

my_struct.receive_asset(some_asset);

We'd do:

receive_asset(&mut my_struct, some_asset);

So - it does work, but also feels quite a bit "hacky" to me.

[jan-ferdinand]

Yeah, feels hacky to me too. 😌 There might be better ways to go about it, but I've never faced this problem in any of my code and thus haven't explored options. Anyway, it's a bit tangential to the discussion's original topic, I suppose. 🙂

[Mightyyoung1]

Thank you for the link)!

[bobbinth]

A few more thoughts on how calling account methods could work under different use case.

In the original post I described how we can call account methods which are a part of some standard interface (e.g., BasicWallet). But some accounts may expose unique methods which are not part of any interface. So, we need a way to call such methods.

First, if we know the full implementation of a given account, we could just pass the whole account struct into a note's clause method.

impl MyNote {
    #[clause]
    pub fn foo(&self, account: &mut MyAccount) {
        // here we can call any method of `MyAccount` (even the ones which are uniquely
        // defined for this account).
    }
}

If we don't know the full implementation, we might have to define something similar to an ABI. For example, if we know a signature and MAST root for a method exposed by an account we could define ABI for it like so:

#[abi]
trait SomeAccount {
    #[mast(0x1234567)]
    fn bar(&mut self, x: u32, y: Felt, z: RpoDigest);
}

We could even use this approach to attach well-known interfaces to an account like so:

use miden::account::std::BasicWallet;

#[abi]
trait SomeAccount: BasicWallet {
    #[mast(0x1234567)]
    fn bar(&mut self, x: u32, y: Felt, z: RpoDigest);
}

For the note, we now can pass SomeAccount as a parameter into a node clause function like so:

impl MyNote {
    #[clause]
    pub fn foo<A: SomeAccount>(&self, account: &mut A) {
        <some code here>
        account.foo(x, y, z);
        <some code here>
    }
}

Note that ABI definition does not have to be exhaustive: we could have it cover only the methods we are interested in.

The next question would be is how to build an ABI for an account. If we have full source code, this should be pretty straight-forward. We could also have source code only for some of the account's methods - and that could be enough.

Without the source code, it might be difficult - but I wonder, if we could put enough information into binary MASM files to help with that.

[jjcnn]

The question of ABIs is tricky, because the note implemenation might be written after the account has been deployed.

Suppose I have some specialized account and an associated specialized note:

impl Note1Account for MyAccount { ... }
impl Note2Account for MyAccount { ... }
impl MyAccount {
  ...<lots of specialized methods>
}

impl MyNote {
  fn claim (&self, account: &mut MyAccount) { ... }
}

MyAccount is perfectly fine for notes that require the Note1Account or Note2Account, and for my specialized note, but once I deploy my account code I'm stuck supporting that set of notes AFAICT.

In particular, if someone later on defines a new type of note Note3Account, then MyAccount cannot interact with it even if MyAccount actually implements all the methods of Note3Account.

The effect of this problem feature is that note traits must be written before the accounts that support them. This may be fine, but it's something to be aware of when designing the contract language. In particular, it will almost certainly be necessary to support some form of migration from one account type to another, so that new note traits can be implemented. How to support account migration in a decentralized way is beyond me - I don't think it can be done.

Note that I have seen this problem before with account-based smart contracts, and I don't know that there is a good solution to it.

The above solution gives a high level of type safety, which in turn means that transactions won't fail (much), but it limits flexibility in contract design.

Alternatively we could ignore the traits on accounts and provide a dynamically generated ABI for each deployed account. Whenever a note is created for that account we check the note's requirements dynamically, to see if the account is valid for that note. This leads to failed transactions, though.

Another alternative is to ignore type safety altogether and just assume that the necessary methods are availalbe, and fail the transaction if they aren't.

[bobbinth]

In particular, if someone later on defines a new type of note Note3Account, then MyAccount cannot interact with it even if MyAccount actually implements all the methods of Note3Account.

This shouldn't actually be a problem. We don't implement notes for accounts. Accounts expose a set of functions which define that account's interface. Notes can then call any functions exposed by the account. So, basically, the situation is somewhat reversed: notes interact with accounts (not accounts with notes).

If we have a definition of a specific function, we can always verify if this function is implemented on a given account (by checking MAST roots). This means that handling things for well-known interfaces (e.g., BasicWallet) is straight-forward.

Even if we don't have a definition, we can still call the function if we know its MAST root - though, if we want to use it in a type-safe manner, additional info about function signature needs to be provided.

[jjcnn]

Sure, but that's all about what happens at deployment and run-time. What happens when you compile the code for the note using Rust's type system?

impl MyAccount { // <---- No trait implemented
  fn my_function() { ... }
}

trait MyNoteAccount {
  fn my_function(); // <----  Same signature as MyAccount
}

impl MyNote {
  fn claim (&self, &MyNoteAccount)  { ... }
}

let n : MyNote = ...;
let a : MyAccount = ...;
n.claim(&a); // <---- a : MyAccount does not implement MyNoteAccount, though it has the required function signatures.

Does this compile in Rust? I'd be surprised if it did, though I haven't checked.

[bobbinth]

Yep - the above is correct. But I'm not sure if such a situation would arise. We either have a full definition of an account (in which case we define unique account methods via impl MyAccount) or we don't and then we'd need to define methods via an ABI trait (i.e., MyNoteAccount).

In the latter case, the claim() method on MyNote would be defined as so:

impl MyNote {
  fn claim<A: MyNoteAccount>(&self, account: &mut A)  { ... }
}

In the former case, it would look like so:

impl MyNote {
  fn claim(&self, account: &mut MyAccount)  { ... }
}

This does mean that the way one "sees" a given note depends on whether they have a full account definition or not. And maybe we should make note code more portable. One option to do that is to say that note clauses can work only with traits and not concrete structs.

[bobbinth]

Some thoughts on the structure of the MASM output.

Let's say we have a very simple (and not very useful) account:

#[derive(Account])
pub struct MyAccount {
    count: u32
}

impl MyAccount {
    pub fn incr_count() {
        self.count += 1;
    }
}

The MASM output file for this (ideal named my_account.masm) could look something like this:

use.miden::sat::account

export.incr_count
  # load word 0 from storage onto the stack
  push.0
  exec.account::get_item
  # => [s3, s2, s1, s0, ... ]
  
  # increment element s0
  movup.3
  u32checked_add.1
  movdn.3
  # => [s3, s2, s1, s0 + 1, ... ]

  # save the updated word back into storage
  push.0
  exec.account::set_item
  # => [s3, s2, s1, s0 + 1, ... ]

  # clear the stack
  dropw
end

(there is a more efficient way to do the above using nondeterminism, but let's keep it simple for now)

There is a lot happening in how we translated the above Rust code to MASM code. But the original Rust code introduces several abstractions. If we remove these, we can get Rust code which is much closer to the above MASM code. It could look something like this:

use miden::account::Account;

pub mod my_account {
  pub fn incr_count(account: &mut Account) {
      let mut item: [u32; 4] = account.get_item(0);
      item[0] += 1;
      account.set_item(0, item);
  }
}

I would imagine that compiling the above Rust function to the desired MASM would be much simpler than compiling the original Rust struct. But the original Rust struct is much more clear and descriptive. So, I'm wondering how could we bridge the gap. One potential option (and I'm not sure how feasible) - is to use procedural macros to transform the original Rust code to the Rust code above, and then compile the latter.

Notes

We can do something similar with notes. Consider the following note:

#[derive(Note)]
pub struct MyNote {
    increment_count: bool
}

impl MyNote {
    pub fn execute(&self, account: &mut MyAccount) {
        if self.icrement_count {
            account.incr_count()
        }
    }
}

An equivalent code which would mimic the desired MASM output more closely could look something like this:

use miden::{accounts::Account, notes::Note};

pub mod my_account {
  pub fn incr_count(account: &mut Account) {
      let mut item: [u32; 4] = account.get_item(0);
      item[0] += 1;
      account.set_item(0, item);
  }
}

pub mod my_note {
    use super::my_account;

    #[entrypoint]
    pub fn execute(note: &Note, account: &mut Account) {
        if note.get_input(0) {
            my_account::incr_count(account);
        }
    }
}

[bitwalker]

We can certainly make some improvements to the ergonomics using proc macros, but there will definitely be limits, and I think we'll want to avoid transforming the code too drastically, or it will make it hard to reason about and test. We'll have to do some experimentation to see where things start to break down, I don't have a great sense of where the line is at the moment.

I actually think we might be able to do this within WASM->MASM compiler. Basically, go through all the imported functions, extract the module path from each import, and build a list of unique imported modules.

That was what I was suggesting actually, but I phrased it in a pretty confusing way now that I re-read it 😅

One other thing: I notice that in the WAT file there are a few things which seem extraneous (or at least I don't know what they are used for). For example, a few global variables, __data_end, __heap_base etc.). Are these actually needed? Or maybe we can compile with no-std or something like that simplify the emitted file even further.

Yes these are used to manage heap memory, including a shadow stack (in order to support pointers to objects on the call stack in languages like Rust or C/C++. Regardless of what high-level language we're compiling from, we'll almost certainly have globals like these used for a similar purpose. These specific globals are generated by LLVM, and are used by even the simplest of programs.

On a related note, something that is important to keep in mind is that it is unlikely that we'll be able to generate MASM from a high-level language that matches what you'd write by hand in many cases. It's the same situation as with "normal" architectures, e.g. x86_64 or AArch64 - you can hand-write an assembly program which is the maximally efficient implementation of a thing, because you control the whole program and can sacrifice abstractions which aren't needed at that level; but an equivalent program written in a high-level language may have semantics/abstractions which must be preserved when lowered to assembly, so the resulting assembly may be slightly less efficient. Some of this efficiency loss is due to NP-hard computer science problems, such as register allocation, where the compiler has to make choices that may be imperfect, but a human would be able to choose perfectly based on their knowledge of the domain/environment/etc. Basically, we should expect, in general, to see the code generated by compilers from a high-level language to be more verbose, and potentially less efficient, compared to equivalent hand-written MASM. You may already be operating under that assumption, but I just wanted to make sure we're on the same page there.

It is also interesting that get_storage_item got translated as having the type func (param i32 i32)) (which seems to take two integers as a parameter) rather than something that takes an integer and returns 4 integers (e.g., func (param i32 result i32 i32 i32 i32)). Any idea why this happened?

It got translated that way for two reasons:

1. The size of a pointer on Wasm is 32 bits
2. The C calling convention (on Wasm) dictates that return values larger than a pointer must be allocated by the caller on the stack, and then a reference is passed to the callee as the first argument (all other arguments are shifted right), the callee then writes the result to the memory allocated by the caller using that reference.

To make it clear what I mean by the second bullet point, consider the following Rust code:

pub type Felt = usize;
pub type Word = [Felt; 4];

pub extern "C" fn get_storage_item(index: usize) -> Word { [0; 4] }

pub extern "C" fn main() -> Felt {
    let word = get_storage_item(0);
   word[0]
}

This is what the compiler must translate this to when taking into account the calling convention:

pub type Felt = usize;
pub type Word = [Felt; 4];

pub fn get_storage_item(result: &mut Word, index: usize) {
    *result = [0; 4];
}

pub fn main() -> Felt {
    let mut word = [0; 4];
    get_storage_item(&mut word, 0);
    word[0]
}

Rust actually supports a variety of calling conventions, not just "C", because different platforms have different conventions based on a wide variety of criteria, but the C calling convention is by far the most common (google the System V ABI for the document which describes this convention on *NIX systems). The important thing to note here is that when a compiler is generating code for function prologues and function calls, it knows the calling convention that must be used by both caller and callee, and it ensures that they agree. On Miden, the only code that exists so far is hand-written MASM, so there has been little reason to consider how one would represent higher-level data structures in memory and pass them around. We want to support hand-written MASM, for those times where hand-writing a function is worthwhile to eke out every last bit of performance - but it will be critical to specify what the C calling convention looks like on Miden, since that will form the foundation for how functions must be called regardless of what language you are compiling from. In particular, functions in the MIden standard library will need to follow that convention.

[bobbinth]

Yes these are used to manage heap memory, including a shadow stack (in order to support pointers to objects on the call stack in languages like Rust or C/C++. Regardless of what high-level language we're compiling from, we'll almost certainly have globals like these used for a similar purpose. These specific globals are generated by LLVM, and are used by even the simplest of programs.

I guess there isn't much we can do about it (at least for now). Maybe in the future we'll find a way to rely on a native way Miden VM manages stack. There will also be a some nuance here as we have different ways to invoke procedures in Miden. Specifically:

• exec allows us to pass pointers to memory - similar to what is happening in the example we've been discussing.
• call and syscall parameters are limited to 16 elements of the stack and we can't pass memory pointers as the callee would be executed in a different memory context. To pass large data structures to procedures invoked in this way, we'd have to go through the advice provider (which could be quite expensive).

it will be critical to specify what the C calling convention looks like on Miden.

Yep, agreed. I do wonder how much control we have in the calling convention that Rust compiler works with. I saw here that we could enable multi-value return types. I'm curious how the above code would look like if we enable these flags.

[bitwalker]

Maybe in the future we'll find a way to rely on a native way Miden VM manages stack

Two things to note about Wasm:

1. The operand stack is implicit (i.e. can only be manipulated via instructions), just like in Miden
2. The call stack (i.e. the "stack" we normally are referring to in Rust/C/C++/etc.) is implicit and inaccessible. It is not visible in any way to Wasm code, and there are no instructions for manipulating the stack (though there is a subgroup working to introduce something along these lines). This is similar to Miden and its implicit procedure call stack.

Languages which allow programmers to allocate/reference the stack, or which have language features such as coroutines/generators/green threads that require manipulating the stack, are forced to use a "shadow stack" on Wasm in order to support it as a target. The shadow stack is basically just one or more heap-allocated regions of memory where locals get stored, and which is manipulated like the traditional stack would be on other architectures, a global takes the place of the stack pointer register, and serves the same purpose.

All of the high-level languages I can think of meet that criteria, i.e. it is unlikely we could compile most languages to Miden Assembly without providing a shadow stack (or providing equivalent functionality via instructions). In my opinion though, following in the footsteps of Wasm here is a perfectly suitable option.

There will also be a some nuance here as we have different ways to invoke procedures in Miden

So I've really been focusing on exec in this discussion, since for the vast majority of programs I suspect that is what most function calls will use, but this is definitely a tricky aspect of targeting Miden.

That said, syscall has very similar semantics to syscalls on *NIX systems, and the restrictions on how arguments are passed and how results are returned shouldn't be an issue there, since we will almost certainly be emitting syscalls in the compiler, rather than representing them in the high-level language. As an aside, what functions are allowed to be/must be called using syscall? I'm assuming it's a closed set (i.e. can be known by the compiler).

For call, it gets tricky, since we need to know how to distinguish between functions that are callable with exec and those callable with call, and handle the latter differently. I don't think we can allow functions to be callable with both exec and call (unless it just so happens that there is alignment in the calling convention, but that would be confusing for most people). We can make it part of the calling convention for call that large arguments/results are passed via the advice provider, and specify how that is to be done, but it isn't at all clear to me how we can represent that in Rust and Wasm. An additional complication is that Rust (and every language I'm familiar with) assumes that callers and callee are in the same address space, so it will be tough to represent the semantics of call and syscall directly in Rust (we can't even distinguish between different "types" of functions in Rust, aside from calling convention).

The way calling conventions are represented in LLVM assumes that you have a set of "immediate" arguments/result (i.e. passed by register/operand stack) and the stack, and one can define a calling convention to pass arguments/results using any combination of those, but there is no way (that I know of) to introduce another method into the mix (i.e. the advice provider). If we are compiling our own language, we can do whatever we want when lowing to MASM, but in the case of Rust/Wasm, we'll be translating Wasm where the calling convention is already implicit in the generated code and we won't be able to recognize whether a given argument/result is a pointer value. The bigger issue though is that when we get a Wasm module, we don't have any high-level program information to help us determine whether a function requires call or exec, so we need to either figure out how to enforce these constraints in Rust or in LLVM.

Yep, agreed. I do wonder how much control we have in the calling convention that Rust compiler works with

We can select one of the calling conventions that Rust supports, which is basically the set of calling conventions that LLVM supports. To add a new one, we'd need to build our own LLVM with the new convention, and then build our own Rust toolchain (e.g. wasm32-unknown-midenvm) that uses our LLVM and adds support for the new convention. It would then be possible to write Rust code that uses that convention, e.g. pub extern "Miden" fn foo()

I saw rust-lang/rust#73755 (comment) that we could enable multi-value return types. I'm curious how the above code would look like if we enable these flags

That comment is actually incorrect - in Wasm, tuple/structs up to 64 bits can be returned by value, and their example is a tuple that is exactly 64 bits, which is why it appears to work, but it isn't due to the multi-value return feature. "True" multi-value returns permit an arbitrary number of results to be returned by value, but Rust/LLVM don't do anything to support this explicitly yet AFAICT. Even with the multivalue feature enabled, our example program is still lowered using return-by-reference for the Word type. I experimented a bit to see if I could get it to do multi-value returns using tuples and raw arrays, but it doesn't appear that there is native support in Rust+LLVM for true multi-value returns yet.

---

How is the exec vs call/syscall semantic difference handled by other architectures/languages? My suspicion is that platforms which have something similar all use purpose-built programming languages which explicitly handle the distinction. On the other end of the spectrum you have Risc0, which can support any language that can target the RISC-V instruction set, but everything is in the same address space on Risc0, so it's basically sidestepping the issue by just not having such a feature (presumably Risc0 isn't oriented towards smart contract development, but rather general purpose ZK computation, so it may not be a good comparison).

Move seems to have a single address space and enforces security using its linear type system and bytecode verifier (i.e. it guarantees that a callee cannot modify memory it doesn't own, or read memory it hasn't been given access to). The Sway compiler controls all aspect of compilation, and while it uses separate address spaces when performing external calls, it is able to arrange the transfer of arguments from the caller's frame to the callee's frame explicitly when it lowers to the Fuel bytecode.

Considering some of our findings so far, in the context of the Miden rollup, a purpose-built programming language really seems like something we should be strongly considering. The more we get into some of the gritty details here, the more apparent it is to me that trying to support the rollup from a general purpose programming language (even Rust) without significant support from the language itself is likely to be intractable. Even setting aside some of the issues like exec vs call, we're already looking at contorting Rust in a way that is outside the norm for Rust programmers, and we would be fighting the tooling along the way, which gives me pause. That's not to say it isn't possible, but it does feel considerably less straightforward than we were initially thinking. The "plain" Miden VM as a target is different, since a typical program would have no need for call, and there are no constraints on what the resulting Miden Assembly looks like, so supporting Rust/Wasm for non-rollup use cases still seems worthwhile and acheivable to me.

I'm happy to run some more experiments if you have any suggestions on how we can tackle some of the problems we've found. I had originally assumed that we would be able to largely translate from Wasm to MASM without much fuss, and that this would solve for both rollup and non-rollup use cases at the same time, which made it a clear win for getting compiler support for Miden up and running in a hurry. I think that is true for the non-rollup use case, but I'm realizing now that some of the rollup constraints really throw a wrench in things, to the point that I think we may want to consider a different approach for the rollup itself (and focus on that first since we're on a pretty tight timeline in general).

[bobbinth]

It is not visible in any way to Wasm code, and there are no instructions for manipulating the stack (though there is a subgroup working to introduce something along these lines).

Yes, I saw these proposals and that's what I was actually referring to in my comment. I haven't read them in enough detail to understand whether they'll be something we could use - but it seems to me that using the "native" stack more efficiently is relevant for some use cases beyond Miden.

All of the high-level languages I can think of meet that criteria, i.e. it is unlikely we could compile most languages to Miden Assembly without providing a shadow stack (or providing equivalent functionality via instructions). In my opinion though, following in the footsteps of Wasm here is a perfectly suitable option.

Agreed! I don't think we need to invent anything new here.

So I've really been focusing on exec in this discussion, since for the vast majority of programs I suspect that is what most function calls will use, but this is definitely a tricky aspect of targeting Miden.

Thinking more about this, it may not be that big of a problem to handle call and syscall instructions. With these instructions we have the following cases:

• syscall will be handled internally. Even when we do need to use it, it will be wrapped in a procedure which can be called with simple exec.
• For account code, there will be no need to use call instruction. So, we can assume that all function calls within an account are done using simple exec.
• For notes, the only use of call instruction is to invoke account methods. We haven't really discussed this in detail, but I'm thinking we can probably automatically detect a call to an account method and handle it slightly differently from others.

That comment is actually incorrect - in Wasm, tuple/structs up to 64 bits can be returned by value, and their example is a tuple that is exactly 64 bits, which is why it appears to work, but it isn't due to the multi-value return feature. "True" multi-value returns permit an arbitrary number of results to be returned by value, but Rust/LLVM don't do anything to support this explicitly yet AFAICT. Even with the multivalue feature enabled, our example program is still lowered using return-by-reference for the Word type. I experimented a bit to see if I could get it to do multi-value returns using tuples and raw arrays, but it doesn't appear that there is native support in Rust+LLVM for true multi-value returns yet.

Ah - interesting! Too bad there isn't a true multi-value returns just yet - I think this would have simplified quite a few things. I guess this one of the cases where WASM gives us exactly what we need, but Rust/LLVM don't support this functionality yet. There are probably several strategies for how we can handle this and we should probably investigate which one of them will work best.

How is the exec vs call/syscall semantic difference handled by other architectures/languages?

As I mentioned above, I think the only case when we actually care about this is when a note invokes an account method. I'll write up a separate comment about this specific case and we can see what might be the best way to handle it.

Considering some of our findings so far, in the context of the Miden rollup, a purpose-built programming language really seems like something we should be strongly considering.

I'm not sure this is the case for a few reasons:

1. What I outlined in the original post is an almost ideal outcome it it is basically 99% Rust. If we can't use the full compiler pipeline, maybe we could re-use parts of it (i.e., have Rust AST but lower it into MASM directly).
2. Even the simplified representation we discussed in the beginning of this thread is "good enough" in the short term, and it seems like using Rust to get it work may be the most straight-forward approach.
3. I think being able to transpile stand-alone WASM programs into MASM is independently interesting, even if it is not directly applicable to the rollup.

We still have a few things to figure out here, two most important ones (in my opinion) are: (1) handling account calls (via call instruction), and handling of Felt's. We can discuss these in a separate thread though.

One thing I was thinking about, however: looking at the LLVM output, it seems like it retains much more info about the original code than WASM. Should we look into the option of going from LLVM directly to MASM? Or is that a very big lift?

[bobbinth]

btw, we should examine what other projects which compile to Rust smart contracts to WASM are doing. I looked at Near, and seems like there are quite a few similarities (at least at the high level) with what we want to do. For example:

1. A contract is defined by a crate which has a single public struct.
2. They use near_bindgen macro to annotate the contract struct and related impl.
3. They have their own set of collections which can be used for storage (this is how we could handle things like StorageMap).
4. The generated WASM can use only ints (no flats).

There are probably a few more.

Obviously, there are also differences (e.g., they don't have a concept of notes) - but I think would be interesting to see how they've approached some of the things we are thinking through.

[greenhat]

Is there a way to get rid of unsafe wrappers? Maybe we can have "unsafe" modules which are wrapped by "safe" modules and then these "safe" wrappers is what actually is exposed via external interface for things like miden::account. My hope is that the complier would erase these "pass through" calls somehow.

Yes, and a simple inlining pass can eliminate "pass through" calls. In OmniZK I introduced in 0xPolygonMiden/miden-vm#957 I'm using the wrappers to expose such functions in the API:

pub fn pub_input() -> u64 {
    #[cfg(feature = "std")]
    #[cfg(not(target_arch = "wasm32"))]
    return io_native::pub_input();

    #[cfg(target_arch = "wasm32")]
    return io_wasm::pub_input();
}

pub fn pub_output(x: u64) {
    #[cfg(feature = "std")]
    #[cfg(not(target_arch = "wasm32"))]
    return io_native::pub_output(x);

    #[cfg(target_arch = "wasm32")]
    return io_wasm::pub_output(x);
}

pub fn secret_input() -> u64 {
    #[cfg(feature = "std")]
    #[cfg(not(target_arch = "wasm32"))]
    return io_native::secret_input();

    #[cfg(target_arch = "wasm32")]
    return io_wasm::secret_input();
}

via https://github.com/greenhat/c2zk/blob/a3938457da2c7cfebb7b561c7ec04e0b55af6b3e/crates/stdlib/src/lib.rs#L56-L82

So the code that uses them:

use c2zk_stdlib::*;

#[no_mangle]
pub fn fib_seq() {
    let n = pub_input() as u32;
    let mut a: u32 = 0;
    let mut b: u32 = 1;
    for _ in 0..n {
        let c = a + b;
        a = b;
        b = c;
    }
    pub_output(a as u64);
}

via https://github.com/greenhat/omnizk/blob/main/crates/rust-wasm-tests/fib/src/fib.rs

with the entry point on for Wasm target - https://github.com/greenhat/omnizk/blob/main/crates/rust-wasm-tests/fib-bin/src/bin/fib.rs

On non-wasm targets, it will use mocked IO, so you can write regular tests in Rust when you can check and simulate the IO. Here is a test for the above code that calls it from your regular Rust tests and compares the results against the compiled code that runs in Triton VM - https://github.com/greenhat/omnizk/blob/main/crates/codegen-tritonvm/src/codegen/sem_tests/fib.rs

[bobbinth]

One of the things I mentioned as needing to be described in more detail in #12 (reply in thread) is how note scripts make calls into accounts. This is probably the only place where the compiler will need to emit call instructions instead of regular exec instructions, and the calling convention between these will differ slightly.

First, let's go over how things will work on the MASM side. Let's say we have an account which exposes two interface methods. This account would be represented by a MASM file (e.g., my_account.masm) which could look something like this:

export.foo
  <some code here>
end

export.bar
  <some code here>
end

Let's also assume that when compiled into MAST, these procedures have the following MAST roots:

• foo -> 0x1234567
• bar -> 0x7654321

Now, let's say we have a note which needs to invoke procedure foo as a part of its script. This would need to be done using call instruction and specifying the MAST root of foo. For example, the note's script could look like so:

begin
  <some code here>
  <code to put inputs for foo onto the stack>
  call.0x1234567
  <some more code here>
end

Using a call instruction works as follows:

• When we us a call instruction we go into a new execution context. This means, that the callee would not have access to the caller's memory and also the callee can access only the top 16 stack elements of the caller.
• When the callee returns, it must ensure that there are exactly 16 elements left on the top of the stack.

The above means that we can pass at most 16 values from the caller to the callee directly, and we cannot pass memory references. So, if we need to pass more than 16 values, a way to do this would be to rely on the advice provider. Specifically, we could use the following convention:

• Let's say the caller wants to pass the contents of memory between addresses 10 and 20 to the callee (i.e., memory[10..21]). This is 40 field elements, and thus we can't pass them via the stack directly.
• The caller would compute a hash of this region of memory (likely using mem_stream + hperm instructions), and place this hash onto the stack (this would take 4 field elements).
• The callee would take the hash, and "un-hash" it into memory (likely using adv_pipe + hperm instructions).

Using the above process, we can theoretically pass unlimited amount of data between the caller and the callee, however, this is much more expensive than just passing memory references. So, practically, we probably won't want to do this for more than a few hundred (or maybe few thousand) elements.

One note: the above is an example of how things could work given the current VM design. There are other ways to make it work too (e.g., by passing roots of Merkle trees), and we may also be able to update the VM in the future to introduce extra capabilities (e.g., instructions which would allow the callee to read values from the caller's memory directly).

Overall, we should define a calling convention for this specific use case to specify what the caller and callee are expected to do (i.e., how they pad and interpret the stack).

Representation in WASM/Rust

Representing the above in WASM, shouldn't be too complicated, I think. For example, something like this could work :

 (import "env" "::0x1234567" (func $::0x1234567 (type 0)))
 (import "env" "::0x7654321" (func $::0x7654321 (type 0)))

(I'm assuming that function names can start with :: - but if not, we'd need to come up with some other special way to designate account methods).

Then, when we see a call to one of these functions we'd know to emit call.0x1234567 instruction). However, an open question is how to get Rust to emit something like this.

In general, on the Rust side, we'd need to define a sort of an ABI for an account and then note scripts could make calls against this ABI. Here, I wonder if we could follow an approach similar to what NEAR is doing as well. For example:

#[abi(my_account)]
trait MyAccount {

    #[mast(0x1234567)]
    fn foo();

    #[mast(0x7654321)]
    fn bar();
}

And then to invoke it from a note, we'd do something like:

pub mod my_note {
    use super::my_account;

    #[entrypoint]
    pub fn execute() {
        my_account::foo();
    }
}

The key question is whether we can translate something similar to the above Rust to something similar to the WASM I outlined before this. Or maybe there is a better way to do this.

[greenhat]

Assuming that Rust macros can generate from:

#[abi(my_account)]
trait MyAccount {

    #[mast(0x1234567)]
    fn foo(a: u32) -> u32;
}

The following code:

mod my_account {
    pub fn foo(a: u32) -> u32 {
        extern "C" {
            fn miden_0x1234567(a: u32) -> u32;
        }
        unsafe { miden_0x1234567(a) }
    }
}

pub mod my_note {
    use crate::my_account;

    pub fn execute() {
        my_account::foo(42);
    }
}

With added:

#[no_mangle]
pub extern "C" fn main() {
    my_note::execute();
}

The above code compiles to the following Wasm code:

(module
  (type (;0;) (func (param i32) (result i32)))
  (type (;1;) (func))
  (import "env" "miden_0x1234567" (func $miden_0x1234567 (;0;) (type 0)))
  (func $main (;1;) (type 1)
    i32.const 42
    call $miden_0x1234567
    drop
  )
  (memory (;0;) 16)
  (global $__stack_pointer (;0;) (mut i32) i32.const 1048576)
  (global (;1;) i32 i32.const 1048576)
  (global (;2;) i32 i32.const 1048576)
  (export "memory" (memory 0))
  (export "main" (func $main))
  (export "__data_end" (global 1))
  (export "__heap_base" (global 2))
)

Where we can swap call $miden_0x1234567 with call.0x1234567.

I believe the implementation of a macro should be a reasonably complex but doable task. What type of arguments do we have to support in account's methods?

[bobbinth]

Yes - I think this will work! One thing I wonder: can we emit the function name as something that won't have a potential to collide with a MASM procedure (i.e., technically miden_0x1234567is a valid procedure name which could have been defined separately).

[bitwalker]

One thing I wonder: can we emit the function name as something that won't have a potential to collide with a MASM procedure

Yes, we can easily control the exported symbol name, using the #[export_name="..."] attribute for function definitions, and/or #[link_name="..."] attribute for external functions. You can use pretty much anything as a symbol name, so choosing something which isn't legal in MASM would be sufficient to avoid conflicts.