Expanding instruction set of Distaff VM

zk-s[nt]arks
5

I’ve just released the next update of Distaff VM (v0.4). The biggest improvement in this update is the Distaff Assembly language which makes writing programs for the VM much much simpler. Some benefits of Distaff assembly are:

  1. Simple, text-based representation.
  2. Many new useful instructions. For example, there are now instruction for less than, greater than, and hash operations. You can also now compute a root of a Merkle path with a single instruction.
  3. The language supports conditional execution natively. That is, you can now use normal if/else statements.

The last point is pretty significant. Up until now, conditional branches were very difficult to do in the VM. But now, you can write a program like this:

read
read
dup.2
gt.128
if.true
  add
else
  mul
endif
rc.64

The above program does the following:

  1. Reads 2 values from the secret inputs tape
  2. If the second values is greater than the first, adds them; otherwise multiplies them.
  3. If the result of the previous operation is less than 2^{64}, outputs 1; otherwise, outputs 0.

The way branching is handled is described in some detail here and here. It is largely based on the MAST approach I described in the very first post about Distaff VM. It has some limitations, which I hope to eliminate in the future.

Overall, there are only 2 limitations left which separate Distaff from a general-purpose VM:

  1. There is still no RAM - though, I have a pretty good idea of how to implement it. This will also enable unlimited number of public inputs and outputs.
  2. The VM is not Turing-complete - i.e. there are no loops, and there are limits to conditional logic. This would be a bit tougher to address - but I think it is possible to get very close to Turing-completeness (including support for un-bounded loops).
6 Likes