Zk Rust: Binary REAL Operations
This article discusses the performance of operations for secret-shared variables in Binary REAL. It doesn't discuss the performance of public operations, which represent a large amount of the operations in the ZkRust language, and can also have a large impact on the performance of your computation.
This article assumes you've read the the ZkRust introduction article.
Background
The basic types for secret-shared values in the ZkRust language are the SbuN
and SbiN types. These types represent integers composed of N secret-shared
bits. Each bit is individually secret-shared and can be accessed individually.
These bits are implemented as extension fields of a polynomial, which is
a fancy mathematical way of saying that they can be used for Multi-Party
Computation.
Whenever you use an operation on one of these types, you are possibly running a complex protocol across multiple MPC network nodes. This takes time and it consumes pre-processed materials which are the primary cost of using REAL.
ZkRust exposes the standard operations for integers on Sbu and Sbi, but
these operations are implemented by the REAL contract by using something called
XOR gates and AND gates:
- XOR gates: Takes two secret-shared bits and XORs them. Can be done locally at each MPC node. Doesn't perform any networking and are effectively free.
- AND gates: Takes two secret-shared bits and ANDs them. This AND operation requires the MPC nodes to interact and send special randomized data between them. Require network traffic and pre-processed material, which makes them much more expensive.
The two primary ways to measure performance of Multi-Party Computation operations is:
- AND gates: The number of AND gates determines the amount of pre-processed materials to be used. Less is cheaper
- Rounds: The number of network rounds, which are small network protocols, where each Multi-Party Computation node sends requests to other nodes and receives requests from other nodes. Each AND gate requires some small amount of communication, but oftentimes these AND gates are independent, and many AND gates' communication can be sent in a single round. The number of rounds will always be less than or equal to number of AND gates. Less is faster.
- XOR gates: Can be measured, but are mostly irrelevant to the performance of the computation.
Operations
Quick overview of the operations and the used number of gates. Each operation
is assumed to be done over N-bit integers:
| Operation | Rounds (Parallel?) | AND gates | XOR gates |
|---|---|---|---|
Addition (+) |
N (✓) |
N |
4*N |
Subtract (-) |
N (✓) |
N |
4*N |
Negate (-) |
N (✓) |
N |
4*N |
Comparisons (<, <=, >, >=) |
N (✓) |
N |
4*N |
Multiplication (*) |
Ca. N^2 (❌) |
O(N^2) |
O(N^2) |
Equality check (==, !=) |
log2(N) (✓) |
N-1 |
2*N |
Select (if, =; see below) |
1 (✓) |
2*N |
N+1 |
Bitwise AND (&) |
1 |
N |
0 |
Bitwise XOR (^) |
0 |
0 |
0 |
Bitwise OR (\|) |
1 |
N |
N |
Logical AND (&&) |
1 |
N |
0 |
Logical OR (\|\|) |
1 |
N |
N |
Bitwise negation (~) |
0 |
0 |
N |
Bitshifts (<<, >>) |
0 |
0 |
0 |
Field access and updates (struct.field, arr[idx]) |
0 |
0 |
0 |
Select
Select is a implicit operation that is inserted by the compiler whenever needed. It is mainly needed when:
- Returning a Sbi value from an if-expression.
- Assigning to a Sbi variable within an if-expression, if the variable is defined outside the if-expression.
Emperic Testing
It can be difficult to analyse the performance of any given piece of code, due to the implicit nature of select, the range of possible types, and the fact that the compiler and runtime may optimize unneeded away operations.
It is thus recommended that programmers test their computations using the the
Junit Contract Test
Framework,
which allows you to inspect the performace statistics of any given computation
by using the zkNodes.getComplexityOfLastComputation() function. This returns
a ZkComputationComplexity with accessors for the number of rounds and the
number of AND gates that have been executed.
Further reading
Further reading: