feat: alternative designs for local RAM

[letypequividelespoubelles]

Summary

At the moment, every read/write memory (i.e. RAM) requires a dedicated timestamp variable which is threaded through all functions that access the given RAM, starting from main. This is somewhat undesirable, as it means functions which logically have no need to "know" about the RAM in question are forced to: (i) declared it; (ii) pay the overhead of passing its timestamp around. The goal of this issue is to consider alternative designs to support some notion of a "local RAM".

Example

The example which is of particular concern here is that of keccak used within the RISC-V interpreter. We can model its usage with the following minimal example:

input data(addr:u32) -> (byte:u8)
memory RAM(addr:u32) -> (byte:u8)
memory scratch(addr:u8) -> (byte:u8)

const N:u32=1024

fn main<RAM,scratch>() {
   // copy data into RAM
   for i:u32=0;i<N;i=i+1 {
     RAM[i] = data[i]
   }
   // initialise call sequence
   keccak(0)
}

fn keccak<RAM,scratch>(offset:u32) {
   if offset < N {
      // process in blocks of 256 bytes
      for j:u16=0;j<256;j=j+1 {
          var offset_j:u32 = offset + (j as u32)
          scratch[j as u8] = RAM[offset_j]
      }
      // process scratch block
      keccak_f()
      // trigger next block
      keccak(offset+256)
   }
}

fn keccak_f<scratch>() {
  // dummy implementation
  for i:u16=0;i<256;i=i+1 {
    if scratch[i as u8] == 0xff {
      fail
    }
  }
}

Whilst this example is somewhat artificial, it roughly illustrates the point. Depending on the problem being considered, we might assume N could be arbitrarily large --- e.g. such that a complete execution of keccak(0) might not fit within a single shard. With this assumption, it would already necessarily be the case that keccak() was placed on the bus.

The example illustrates that scratch is intuitively "local" to keccak() and, hence, it seems awkward that: (i) main() must have scratch in its list of memory effects; (ii) main() must store and thread the timestamp for scratch.

Approaches

There are (at least) a few different approaches to solving this problem:

• (Unified RAM) By far the easiest solution is have a single unified RAM memory which includes the scratch space needed for keccak_f() and, thus, the latter goes from keccak_f<scratch>() to keccak_f<RAM>(). PRO: there is only one timestamp threaded throughout; CON the width of the RAM timestamp might be e.g. u64 and everyone, even keccak_f pays the price for this.

• (Local Memory) In this model, scratch is implemented as a true local memory (e.g. which does not use the bus and, instead, uses direct lookups). There are two variations on this approach: shared and unshared (see below for more details).

• (One Shot Buffer) In this model, a write-once memory is used as a "one shot" buffer. Specifically, keccak would copy data into this buffer and then call keccak_f with the offset/length of that data in the buffer. The keccak_f would no longer access a scratch memory at all and, instead, would use the one-shot buffer for its scratch space as well. This requires some mechanism for ensuring each call to keccak gets a fresh location in the one-shot buffer --- but this potentially could be found non-deterministically.

Approach (Local Memory)

In this approach, our various functions might be declared something like this:

...
fn main<RAM>() { ... }

fn keccak<RAM>(offset:u32) {
  // local memory declaration
  memory scratch(addr:u8) -> (byte:u8)
  ...
}

fn keccak_f<scratch>() { ... }

The implementation of scratch would differ from a typical read/write memory as it would not use the bus. There are different strategies which can be used for this, such as: sorted permutation argument; paired lookup argument, etc. Its not clear to me which is the best for this choice but, for example, the "paired lookup argument" requires either an initialisation or finalisation phase (meaning a shared implementation might seem better as it amortizes this cost).

(Shared Implementation) Then, the (shard-local) table for keccak would have a stamp column(s) for scratch. Every frame of keccak would produce an updated stamp' column (exactly matching how timestamp threading works already), and local constraints would enforce that: (i) stamp[0] ==0 holds for the first frame; (ii) that stamp[i] == stamp'[i-1] for subsequent frames. This is called the "shared" approach because the timestamp is shared across frames within the same shard. Thus, in principle, frames could communicate with each other via this channel --- but only on the same shard (effectively making such communication pointless anyway).

(Unshared Implementation) This is similar, except that each occurrence of keccak in the shard-local table is given a unique identifier which (roughly speaking) gives it access to a unique local memory (i.e. keccak() would not need to thread a timestamp for scratch). Depending on the implementation of the local memory, there may be some costs here (for example, need to initialise/finalise each unique memory individually).