Cost model
The cost model that ziskemu uses to price an execution. Explains the cost version (ZISK_COSTS_VERSION), the formula behind each cost, and lists the costs of the main step, the opcodes, the precompiles, the DMA operations, and memory at cost version 1.
Every figure in a ziskemu report, and in cargo-zisk run --profiling,
is a profiling cost: an estimate of the proving area an execution
needs, in columns × rows. It is computed from a fixed table of costs per
operation, and that table is the cost model. For how to read the reports,
see Statistics & reports.
Cost version
The cost model is versioned. The current version is
ZISK_COSTS_VERSION = 1, defined in core/src/zisk_ops_costs.rs.
The version is increased whenever the result of a cost evaluation can
change:
- any cost in
core/src/zisk_ops_costs.rs(opcodes) oremulator/src/emu_costs.rs(memory, main, ROM, tables); - the way costs are accumulated, i.e. what is charged for an operation or a memory access;
- the FROPS (frequent operations) tables, or the way they are evaluated.
Every report states the version it was priced with:
| Output | Where the version appears |
|---|---|
ziskemu -X | REPORT (cost version 1) |
ziskemu -X --sdk, cargo-zisk run --profiling | REPORT SUMMARY (cost version 1) |
--save-stats snapshots | First line: COSTS_VERSION,1 (with the default separator) |
A change in the cost version changes the price of the same execution.
A drop in cost between two reports of different versions may come from
the new model, not from your code. Compare two reports or snapshots only
when they carry the same cost version. --ref-stats and --diff-stats
do not check the version for you.
How a cost is computed
The cost of an operation is the area of the state machine (AIR) that
proves it. Each AIR has a total number of columns (Total) and may pack
several operations per row (ops_per_row, from lanes_x_row,
op_x_row, or LANES). The cost per operation is:
cost = ⌈Total / ops_per_row⌉ × rows_per_op
When several instances can prove an opcode, the model takes the
cheapest one. For example, add costs ⌈83 / 4⌉ = 21, from
BinaryAddHuge (83 columns, 4 lanes).
The cost of a run is the sum of five categories:
TOTAL = BASE + VARIABLE
VARIABLE = MAIN + OPCODES + PRECOMPILES + MEMORY
MAIN = STEPS × MAIN_COST
BASE is fixed for every program: ROM_COST + TABLES_COST. A
precompile's own cost covers only the area of its AIR. Its memory
accesses are charged on top, in MEMORY, at the RAM, ROM or input cost
of each aligned word it reads or writes.
Profiling cost is not the final proving cost. The prover allocates operations to fixed-capacity instances, so the final cost moves in steps. See Profiling cost vs. final cost.
Cost tables (version 1)
The tables below list each cost at version 1. Previous is the last unversioned value, just before version 1 was introduced, shown for reference only. It is not necessarily the value a ZisK 1.3 release used.
Main and standard operations
| Cost | Opcodes | Instance (Total / ops per row) | Previous | Version 1 |
|---|---|---|---|---|
MAIN_COST (per step) | all | Main 245 / 4 | 68 | 62 |
BINARY_COST | minu, min, maxu, max, ltu, lt, eq, sub, leu, le, and, or, xor, *_w, brev8, andn, orn, xnor, sh1add, sh2add, sh3add, unal8 | BinaryHuge 219 / 4 | 60 | 55 |
BINARY_ADD_COST | add | BinaryAddHuge 83 / 4 | 25 | 21 |
BINARY_ADD_HI_COST | add of the hi shape (add_hi0 / add_hif with --opcode-breakdown) | BinaryAddHiHuge 93 / 8 | 15 | 12 |
BINARY_E_COST | sll, srl, sra, *_w, signextend_*, rev8, pack*, rol*, ror*, clz*, ctz*, cpop*, orc_b, bclr, bext, binv, bset, clmul*, xperm*, czero_* | BinaryExtensionLarge 110 / 2 | 56 | 55 |
SLL_U_W_COST | sll_u_w | = BINARY_E_COST | 56 | 55 |
ADD_U_W_COST | add_u_w | MAIN + BINARY + BINARY_ADD | 153 | 138 |
SH_ADD_COST | decomposed sh*add | MAIN + BINARY_E + BINARY_ADD | 149 | 138 |
SH_ADD_U_W_COST | sh1add_u_w, sh2add_u_w, sh3add_u_w | MAIN + BINARY + BINARY | 188 | 172 |
ARITHAM32_COST / ARITHA32_COST | mul*, div*, rem* | Arith 97 / 1 | 97 | 97 |
Precompiles
| Cost | Opcodes | Instance (Total × rows per op) | Previous | Version 1 |
|---|---|---|---|---|
KECCAK_COST | keccak | Keccakf 615 × 135 rows / 2 ops per slot | 41,512 | 41,513 |
SHA256_COST | sha256 | Sha256f 122 × 72 | 8,784 | 8,784 |
POSEIDON_COST | poseidon1, poseidon2 | Poseidon 392 × 14 | 5,488 | 5,488 |
POSEIDON2_KOALABEAR_COST | poseidon2_koalabear | Poseidon2KoalaBear 499 × 30 | 14,970 | 14,970 |
BLAKE2B_COST (per round) | blake2b | Blake2br 233 × 8 | 1,896 | 1,864 |
BLAKE2S_COST | blake2s | Blake2s 115 × 80 | 9,200 | 9,200 |
BLAKE3_COST | blake3 | Blake3f 221 × 56 / 2 lanes | 6,188 | 6,188 |
ARITH_256_COST | arith256, arith256_mod | Arith256X 54 × 16 | 1,440 | 864 |
ARITH_SECP256K1_COST | secp256k1_add, secp256k1_dbl | ArithSecp256K1 72 × 16 | 1,440 | 1,152 |
ARITH_BN254_COST | bn254_curve_add, bn254_curve_dbl, bn254_complex_add, bn254_complex_sub, bn254_complex_mul | ArithBn254 78 × 16 | 1,440 | 1,248 |
ARITH_EQ_COST | secp256r1_add, secp256r1_dbl | ArithEq 90 × 16 | 1,440 | 1,440 |
ARITH_EQ_384_COST | arith384_mod, bls12_381_* | ArithEq384 80 × 24 | 1,920 | 1,920 |
TWISTED_EDWARDS_COST | babyjubjub_add, ed25519_add | TwistedEdwards 109 × 16 | 1,744 | 1,744 |
ADD256_COST | add256 | Add256 104 × 1 | 104 | 104 |
JUMP_DEST_COST (per 64-bit source word) | jump_dest | JumpDest 66 / 2 ops per row | 252 | 33 |
keccak, for example, costs ⌈615 × 135 / 2⌉ = 41,513: a slot of 135
rows holds two Keccak-f permutations. Its 25 word reads and 25 word
writes are charged to MEMORY on top.
DMA
DMA costs are per row. An aligned loop takes ⌈words / DIVISOR⌉ rows,
so its cost is written as COST / DIVISOR.
| Cost | Instance | Previous | Version 1 |
|---|---|---|---|
DMA_COST (memcmp, memset) | Dma 63 (one instance proves every operation) | 61 | 63 |
DMA_MEMCPY_COST | Dma 63 | 46 | 63 |
DMA_INPUTCPY_COST | Dma 63 | 40 | 63 |
DMA_PRE_POST_COST (memcmp, memset) | DmaPrePost 104 (one instance) | 104 | 104 |
DMA_PRE_POST_MEMCPY_COST | DmaPrePost 104 | 91 | 104 |
DMA_PRE_POST_INPUTCPY_COST | DmaPrePost 104 | 59 | 104 |
DMA_64_ALIGNED_MEMCPY_COST / DIVISOR | Dma64AlignedMemCpy 67 / 8 | 67 / 8 | 67 / 8 |
DMA_64_ALIGNED_MEMSET_COST / DIVISOR | Dma64AlignedMemSet 35 / 8 | 35 / 8 | 35 / 8 |
DMA_64_ALIGNED_MEMCMP_COST / DIVISOR | Dma64AlignedMem 50 / 4 | 50 / 4 | 50 / 4 |
DMA_64_ALIGNED_INPUTCPY_COST / DIVISOR | Dma64Aligned 77 / 4 (the only one proving it) | 58 / 4 | 77 / 4 |
DMA_UNALIGNED_COST | DmaUnaligned 42 | 42 | 42 |
Memory and base cost
| Cost | Instance | Previous | Version 1 |
|---|---|---|---|
MEM_READ_COST | Mem 87 / 4 → 22 per lane, dual RAM | 16 | 11 |
MEM_WRITE_COST | Mem 87 / 4 → 22 per lane, dual RAM | 18 | 18 |
INPUT_READ_COST | InputData 29 / 1 | 29 | 29 |
ROM_READ_COST / ROM_INIT_COST | RomData 22 / 2 | 14 | 11 |
MEM_ALIGN_COST | MemAlign 50 | 53 | 50 |
MEM_ALIGN_READ_UNALIGNED_1_COST | 2 × MEM_ALIGN | 106 | 100 |
MEM_ALIGN_READ_UNALIGNED_2_COST | 3 × MEM_ALIGN | 159 | 150 |
MEM_ALIGN_WRITE_UNALIGNED_1_COST | 3 × MEM_ALIGN | 159 | 150 |
MEM_ALIGN_WRITE_UNALIGNED_2_COST | 5 × MEM_ALIGN | 265 | 250 |
MEM_ALIGN_READ_BYTE_COST | MemAlignReadByte 25 | 25 | 25 |
MEM_ALIGN_WRITE_BYTE_COST | MemAlignWriteByte 32 | 32 | 32 |
ROM_COST | Rom 16 × 2²² | 16 × 2²² | 16 × 2²² |
TABLES_COST | VirtualTableZisk1 65 + VirtualTableZisk0 39, × 2²¹ | 105 × 2²¹ | 104 × 2²¹ |
BASE_COST | ROM_COST + TABLES_COST | 287,309,824 | 285,212,672 |
A Mem lane proves a read and a read, or a write and a read, so one access
costs between 11 (sharing a full lane) and 22 (alone in its lane). Not
every lane is full, so each access is charged a conservative share of
the dual-lane cost of 22: ⌈22 × 0.5⌉ = 11 for a read and
⌈22 × 0.8⌉ = 18 for a write.
Notes
sh3addis chargedBINARY_COST, the general case. Depending on its operands it can also be proven by BinaryAdd or BinaryAddHi, but the emulator applies that breakdown only toadd.- Every DMA operation pays the full row of the single instance that proves it.
- The precompile memory charges cover the direct
a/boperands and the operands passed through a parameter struct (arith256,arith256_mod,arith384_mod,add256).
The full derivation, with every candidate instance and the most
expensive one per cost, is in
docs/ziskemu-op-costs.md
in the ZisK repository.