Distaff assembly is a simple, low-level language for writing programs for Distaff VM. It stands just above raw Distaff VM instructions, and in fact, many instructions in Distaff assembly map directly to raw instruction of Distaff VM. However, Distaff assembly has several advantages:
- Distaff assembly supports macro instructions. These instructions expand into sequences of raw Distaff VM instructions making it easier to encode common operations.
- Distaff assembler takes care of properly aligning and padding all instructions reducing the amount of mental bookkeeping needed for writing programs.
- Distaff assembly natively supports control flow expression which the assembler automatically transforms into a program execution graph needed by Distaff VM.
To compile Distaff assembly source code into a program for Distaff VM, you can use the compile() function from the assembly module. This function takes the following parameters:
source: &str- a reference to a string containing Distaff assembly source code.
The compile() function returns Result<Program, AssemblyError> which will contain the compiled program if the compilation was successful, or if the source code contained errors, description of the first encountered error.
For example:
use distaff::{ assembly };
// the program pushes values 3 and 5 onto the stack and adds them
let program = assembly::compile("begin push.3 push.5 add end").unwrap();A Distaff assembly program is just a sequence of instructions each describing a specific operation. You can use any combination of whitespace characters to separate one instruction from another. Every program must start with a begin instruction and terminate with an end instruction.
In addition to simple instructions sequences, Distaff VM supports the following control structures:
- if-then-(else) expressions for conditional execution;
- repeat expressions for bounded counter-controlled loops;
- while expressions for unbounded condition-controlled loops.
Each of these is described below.
Conditional execution in Distaff VM can be accomplished with if-then-(else) statements. These statements look like so:
if.true
<instructions>
else
<instructions>
end
where instructions can be a sequence of any instructions, including nested control structures; the else clause is optional. The above does the following:
- Pops the top item from the stack.
- If the value of the item is
1, instructions in theif.truebranch executed. - If the value of the item is
0, instructions in theelsebranch are executed. - If the value is not binary (i.e. not
0or1), the operation fails.
A couple of notes on performance:
- Number of instructions in each of the branches must be one less than a multiple of 16 (e.g. 15, 31, 47 etc.). If there not enough instructions, the assembler will pad the instructions with the appropriate number of
noop's. So, you don't need to worry about insertingnoop's manually. But, for simple if-then-(else) statements, it might be more efficient to use selection instructions instead. - For every level of nesting, the VM must allocate an additional register. To limit potential impact of this on performance, currently, if-then-(else) can be nested at most 16 levels deep. This should be sufficient for most use case, and if there is a need, will be increased in the future.
The above affects only nested if-then-(else) statements. So, when one if-then-(else) statement follows another, the VM does no need to allocate any additional registers.
Executing a sequence of instructions a predefined number of times can be accomplished with repeat statements. These statements look like so:
repeat.<count>
<instructions>
end
where:
instructionscan be a sequence of any instructions, including nested control structures.countis the number of times theinstructionssequence should be repeated (e.g.count.10).countmust be an integer greater than 1.
The assembler actually unfolds the body of the loop at compile time into repeated sequences of instructions. So, a repeat statement is just syntactic sugar.
A note on performance:
- Number of instructions in the body of the loop must be one less than a multiple of 16 (e.g. 15, 31, 47 etc.). As with if-then-(else) statements, the assembler will take care of all required padding, but if the loop is simple and/or repeated a small number of times, it might be more efficient to write out the repeated instructions manually.
Executing a sequence of instructions zero or more times based on some condition can be accomplished with while loop expressions. These expressions look like so:
while.true
<instructions>
end
where instructions can be a sequence of any instructions, including nested control structures. The above does the following:
- Pops the top item from the stack.
- If the value of the item is
1,instructionsin the loop body are executed.- After the body is executed, the stack is popped again, and if the popped value is
1, the body is executed again. - If the popped value is
0, the loop is exited. - If the popped value is not binary (i.e. not
0or1), the operation fails.
- After the body is executed, the stack is popped again, and if the popped value is
- If the value of the item is
0, execution of loop body is skipped. - If the value is not binary (i.e. not
0or1), the operation fails.
A note on performance:
- For every nested loop, the VM must allocate 2 additional registers. To limit potential impact of this on performance, currently, loops can be nested at most 8 levels deep. This should be sufficient for most use case, and if there is a need, will be increased in the future.
The above affects only nested loops. So, when one loop follows another, the VM does no need to allocate any additional registers.
Instructions in Distaff VM are just keywords separated from each other by any combination of whitespace characters. Many instructions can be parametrized with a single parameter. The notation for specifying parameters is operation.parameter. For example, push.123 describes a push operation which is parametrized with value 123.
For most instructions which support parameters, the default parameter is set to 1. For example, dup is equivalent to dup.1, choose is equivalent to choose.1 and so on.
A single instruction may take multiple VM cycles to execute. The number of cycles frequently depends on the specified parameter, and sometimes depends on other factors (e.g. place of the operation in the execution path). The tables below include this number of cycles in the last column.
| Operation | Description | Cycles |
|---|---|---|
| assert | Pops the top item from the stack and checks if it is equal to 1. If it is not equal to 1, the operation fails. |
1 |
| assert.eq | Pops top two items from the stack and checks if they are equal. If they are not equal, the operation fails. | 1 |
| Operation | Description | Cycles |
|---|---|---|
| push.x | Pushes x onto the stack. x can be any valid field element. push operations can be executed only on steps which are multiples of 8 (e.g. 0, 8, 16 etc.). If a push operation in your program does not align with this, the assembler will pad it with the appropriate number of noop's. |
1 - 7 |
| read.a | Pushes the next value from the input tape A onto the stack. |
1 |
| read.ab | Pushes the next values from input tapes A and B onto the stack. Value from input tape A is pushed first, followed by the value from input tape B. |
1 |
Distaff VM has two input tapes for supplying secret inputs to a program: tape A and tape B. You can use read.a and read.ab instructions to move value from these tapes onto the stack. When a value is read from a tape, tape pointer advances to the next value. This means, that a value can be read from a tape only once. If you try to read values from a tape which has no more values, the operation fails.
| Operation | Description | Cycles |
|---|---|---|
| noop | Does nothing. | 1 |
| dup.n | Pushes copies of the top n stack items onto the stack. n can be any integer between 1 and 4. | 1 - 3 |
| pad.n | Pushes n 0's onto the stack; n can be any integer between 1 and 8. |
1 - 4 |
| pick.n | Pushes a copy of the item with index n onto the stack. For example, assuming S0 is the top of the stack, executing pick.2 transforms S0 S1 S2 S3 into S2 S0 S1 S2 S3. n can be any integer between 1 and 3. |
2 - 5 |
| drop.n | Removes top n items from the stack; n can be any integer between 1 and 8. | 1 - 3 |
| swap.1 | Moves the second from the top stack item to the top of the stack (swaps top two stack items). | 1 |
| swap.2 | Moves 3rd and 4th stack items to the top of the stack. For example, assuming S0 is the top of the stack, S0 S1 S2 S3 becomes S2 S3 S0 S1. |
1 |
| swap.4 | Moves 5th through 8th stack items to the top of the stack. For example, assuming S0 is the top of the stack, S0 S1 S2 S3 S4 S5 S6 S7 becomes S4 S5 S6 S7 S0 S1 S2 S3. |
1 |
| roll.4 | Moves 4th stack item to the top of the stack. For example, assuming S0 is the top of the stack, S0 S1 S2 S3 becomes S3 S0 S1 S2. |
1 |
| roll.8 | Moves 8th stack item to the top of the stack. For example, assuming S0 is the top of the stack, S0 S1 S2 S3 S4 S5 S6 S7 becomes S7 S0 S1 S2 S3 S4 S5 S6. |
1 |
| Operation | Description | Cycles |
|---|---|---|
| add | Pops top two items from the stack, adds them, and pushes the result onto the stack. | 1 |
| sub | Pops top two items from the stack, subtracts the 1st item from the 2nd item, and pushes the result onto the stack. | 2 |
| mul | Pops top two items from the stack, multiplies them, and pushes the result onto the stack. | 1 |
| div | Pops top two items from the stack, divides the 2nd item by the 1st item, and pushes the result onto the stack. If the item at the top of the stack is 0, this operation fails. |
2 |
| neg | Pops the top item from the stack, computes its additive inverse, and pushes the result onto the stack. | 1 |
| inv | Pops the top item from the stack, computes its multiplicative inverse, and pushes the result onto the stack. If the value at the top of the stack is 0, this operation fails. |
1 |
| not | Pops the top item from the stack, subtracts it from value 1 and pushes the result onto the stack. In other words, 0 becomes 1, and 1 becomes 0. If the item at the top of the stack is not binary (i.e. not 0 or 1), this operation fails. |
1 |
| and | Pops top two items from the stack, computes an equivalent of their boolean AND (which, for binary values, is just multiplication), and pushes the result onto the stack. If either of the values is not binary, the operation fails. |
1 |
| or | Pops top two items from the stack, computes an equivalent of their boolean OR, and pushes the result onto the stack. If either of the values is not binary, the operation fails. |
1 |
All arithmetic operations in Distaff VM happen in a prime field with modulus 340282366920938463463374557953744961537 (which can also be written as 2128 - 45 * 240 + 1). This means that overflow happens after a value exceeds field modulus. So, for example: 340282366920938463463374557953744961536 + 1 = 0.
Divisions in prime fields are defined as inverse of multiplication. Specifically, c = a / b means: find such c that b * c = a. This may lead to unintuitive results. For example, 1 / 2 = 170141183460469231731687278976872480769.
| Operation | Description | Cycles |
|---|---|---|
| eq | Pops top two items from the stack, compares them, and if their values are equal, pushes 1 onto the stack; otherwise pushes 0 onto the stack. |
2 |
| ne | Pops top two items from the stack, compares them, and if their values are not equal, pushes 1 onto the stack; otherwise pushes 0 onto the stack. |
3 |
| gt.n | Pops top two items from the stack, compares them, and if the 1st value is greater than the 2nd value, pushes 1 onto the stack; otherwise pushes 0 onto the stack. If either of the values is greater than 2n, the operation fails. n can be any integer between 4 and 128. |
n + 14 |
| lt.n | Pops top two items from the stack, compares them, and if the 1st value is less than the 2nd value, pushes 1 onto the stack; otherwise pushes 0 onto the stack. If either of the values is greater than 2n, the operation fails. n can be any integer between 4 and 128. |
n + 13 |
| rc.n | Pops the top item from the stack, checks if it is less than 2n, and if it is, pushes 1 onto the stack; otherwise pushes 0 onto the stack. n can be any integer between 4 and 128. |
n + 8 |
| isodd.n | Pops the top item from the stack, and if its value is odd, pushes 1 onto the stack; otherwise pushes 0 onto the stack. If the value is greater than 2n, the operation fails. n can be any integer between 4 and 128. |
n + 12 |
| Operation | Description | Cycles |
|---|---|---|
| choose.1 | Pops top 3 items from the stack, and pushes either the 1st or the 2nd value back onto the stack depending on whether the 3rd value is 1 or 0. For example, assuming S0 is the top of the stack, S0 S1 1 becomes S0, while S0 S1 0 becomes S1. This operation fails if the 3rd stack item is not a binary value. |
1 |
| choose.2 | Pops top 6 items from the stack, and pushes either the 1st or the 2nd pair of values back onto the stack depending on whether the 5th value is 1 or 0. For example, assuming S0 is the top of the stack, S0 S1 S2 S3 1 S5 becomes S0 S1, while S0 S1 S2 S3 0 S5 becomes S2 S3 (notice that S5 is discarded in both cases). This operation fails if the 5th stack item is not a binary value. |
1 |
Selection instructions can be used to simulate conditional execution. This, in turn, can be used to eliminate simple if-then-(else) expressions. For example, if we have a program with conditional branches which looks like so:
if.true
<instructions>
else
<instructions>
end
We can transform it into a linear program using selection instructions like so:
- First, execute instructions in the
if.truebranch and leave the result on the stack. - Then, execute instructions in the
elsebranch and leave the result on the stack. - Finally, use
chooseorchoose.2instruction to select between the two results based on the desired condition.
| Operation | Description | Cycles |
|---|---|---|
| hash.n | Pops top n items from the stack, computes their hash using Rescue hash function, and pushes the result onto the stack. The result is always represented by 2 stack items. n can be any integer between 1 and 4. | ~ 16 |
| smpath.n | Pops top 2 items from the stack, uses them to compute a root of a Merkle authentication path for a tree of depth n, and pushes the result onto the stack. The result is always represented by 2 stack items. Input tapes A and B are expected to contain nodes of the Merkle authentication path as well as binary representation of the leaf's index (see here for more info). |
~ 16n |
| pmpath.n | Pops top 3 items from the stack, uses the first 2 items to compute a root of a Merkle authentication path for a tree of depth n and a leaf indicated by the 3rd stack item, and pushes the result onto the stack. The result is always represented by 2 stack items. Input tapes A and B are expected to contain nodes of the Merkle authentication path (see here for more info). |
~ 32n |
Distaff VM uses a modified version of Rescue hash function. This modification adds half-rounds to the beginning and to the end of the standard Rescue hash function to make the arithmetization of the function fully foldable. High-level pseudo-code for the modified version looks like so:
for 10 iterations do:
add round constants;
apply s-box;
apply MDS;
add round constants;
apply inverse s-box;
apply MDS;
This modification should not impact security properties of the function, but it is worth noting that it has not been studied to the same extent as the standard Rescue hash function.
Parameters used for the hash function are:
- State width of 6 elements: 4 elements for rate + 2 elements for capacity.
- S-Box of power 3, though, in the future this may be changed to S-Box of power 5.
As mentioned above, smpath and pmpath instructions can be used to compute roots of Merkle authentication paths, but the semantics of these instruction are somewhat complicated and deserve a bit more explanation.
Both instructions work in a similar manner, but they are intended for different use cases. Specifically:
smpathinstruction expects both the nodes of the Merkle authentication path and leaf index to be provided via input tapesAandB.pmpathinstruction expects only the nodes of the Merkle authentication path to be provided via input tapesAandB. The leaf index is expected to be provided via the stack.
First, we'll describe pmpath instruction. Suppose we have a Merkle tree of depth 3 which looks like so:
abcd
/ \
ab cd
/ \ / \
a b c d
where: ab = hash(a, b), cd = hash(c, d), and abcd = hash(ab, cd). All of these values are 256 bits in size, and thus, we'd need two 128-bit field elements to represent each of them in Distaff VM.
If we consider leaf c, Merkle authentication path for this leaf would be: [d, ab], and the root of this path would be abcd. To compute this root in Distaff VM we can use pmpath instruction like so:
- First, we need to put two elements representing leaf
conto the stack. - Then, we need to execute
pmpath.3instruction. We set the parameter to3because the depth of our Merkle tree is 3. - The result of the operation will be the value of
abcdsitting in the top two registers of the stack.
For the above to work, we also need to populate input tapes A and B with additional data. Specifically, these tapes should contain:
- Values of Merkle path nodes
dandab. Since these values are 256 bits each, we need to split each value across tapesAandB. For example,dwill be represented by two 128-bit values: d0 and d1. - Binary decomposition of
c's index in the tree. In our example, this index is 2, and its binary representation is10. Starting with the least significant bit, each bit should be put into a separate slot on tapeA, interlaced with nodes of the Merkle path.
Applying the above to our example, we'd get inputs tapes looking like so:
| A | B |
|---|---|
| d0 | d1 |
| 0 | 0 |
| ab0 | ab1 |
| 1 | 0 |
Here is a brief explanation:
- First, we put the value
drepresented by d0 and d1 into tapesAandB. - Then we put the least significant bit of
c's index (which is0) into tapeA, and also complement it with0in tapeB. - Next, we put the value
abrepresented by ab0 and ab1 into tapesAandB. - Finally, we put the next bit of
c's index (which is1) into tapeA, and complement it with0in tapeB.
Note that even though we use only tape A for bits of c's index, we always complement these inputs with 0's in tape B.
To summarize: if our input tapes are set up as shown above, and if our stack state is [c1, c0], where c1 is at the top of the stack, executing smpath.3 will transform the stack into [abcd1, abcd0].
As mentioned above, pmpath works similarly to smpath but there are two important differences:
First, pmpath expects the index of the leaf which the Merkle path authenticates to be located in the 3rd item of the stack. So, for the example in the previous section, before we execute pmpath instruction, we should arrange the stack like so:
[c_1, c_0, 2]
where 2 is the position of our leaf in the Merkle tree.
Second, since the leaf's index is on the stack, we no longer need to put it onto input tapes. So, input tapes A and B would need to be populated like so:
| A | B |
|---|---|
| d0 | d1 |
| ab0 | ab1 |
Then, we can execute pmpath.3 instruction (since 3 is the depth of our Merkle tree), and after the operation completes, the value of abcd will be sitting in the top two registers of the stack.
Note that index value will be discarded. That is, the operation pops 3 values from the top of the stack but pushes back only 2 values.