Skip to main content

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) or emulator/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:

OutputWhere the version appears
ziskemu -XREPORT (cost version 1)
ziskemu -X --sdk, cargo-zisk run --profilingREPORT SUMMARY (cost version 1)
--save-stats snapshotsFirst line: COSTS_VERSION,1 (with the default separator)
Never compare figures from different cost versions

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.

note

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​

CostOpcodesInstance (Total / ops per row)PreviousVersion 1
MAIN_COST (per step)allMain 245 / 46862
BINARY_COSTminu, min, maxu, max, ltu, lt, eq, sub, leu, le, and, or, xor, *_w, brev8, andn, orn, xnor, sh1add, sh2add, sh3add, unal8BinaryHuge 219 / 46055
BINARY_ADD_COSTaddBinaryAddHuge 83 / 42521
BINARY_ADD_HI_COSTadd of the hi shape (add_hi0 / add_hif with --opcode-breakdown)BinaryAddHiHuge 93 / 81512
BINARY_E_COSTsll, srl, sra, *_w, signextend_*, rev8, pack*, rol*, ror*, clz*, ctz*, cpop*, orc_b, bclr, bext, binv, bset, clmul*, xperm*, czero_*BinaryExtensionLarge 110 / 25655
SLL_U_W_COSTsll_u_w= BINARY_E_COST5655
ADD_U_W_COSTadd_u_wMAIN + BINARY + BINARY_ADD153138
SH_ADD_COSTdecomposed sh*addMAIN + BINARY_E + BINARY_ADD149138
SH_ADD_U_W_COSTsh1add_u_w, sh2add_u_w, sh3add_u_wMAIN + BINARY + BINARY188172
ARITHAM32_COST / ARITHA32_COSTmul*, div*, rem*Arith 97 / 19797

Precompiles​

CostOpcodesInstance (Total × rows per op)PreviousVersion 1
KECCAK_COSTkeccakKeccakf 615 × 135 rows / 2 ops per slot41,51241,513
SHA256_COSTsha256Sha256f 122 × 728,7848,784
POSEIDON_COSTposeidon1, poseidon2Poseidon 392 × 145,4885,488
POSEIDON2_KOALABEAR_COSTposeidon2_koalabearPoseidon2KoalaBear 499 × 3014,97014,970
BLAKE2B_COST (per round)blake2bBlake2br 233 × 81,8961,864
BLAKE2S_COSTblake2sBlake2s 115 × 809,2009,200
BLAKE3_COSTblake3Blake3f 221 × 56 / 2 lanes6,1886,188
ARITH_256_COSTarith256, arith256_modArith256X 54 × 161,440864
ARITH_SECP256K1_COSTsecp256k1_add, secp256k1_dblArithSecp256K1 72 × 161,4401,152
ARITH_BN254_COSTbn254_curve_add, bn254_curve_dbl, bn254_complex_add, bn254_complex_sub, bn254_complex_mulArithBn254 78 × 161,4401,248
ARITH_EQ_COSTsecp256r1_add, secp256r1_dblArithEq 90 × 161,4401,440
ARITH_EQ_384_COSTarith384_mod, bls12_381_*ArithEq384 80 × 241,9201,920
TWISTED_EDWARDS_COSTbabyjubjub_add, ed25519_addTwistedEdwards 109 × 161,7441,744
ADD256_COSTadd256Add256 104 × 1104104
JUMP_DEST_COST (per 64-bit source word)jump_destJumpDest 66 / 2 ops per row25233

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.

CostInstancePreviousVersion 1
DMA_COST (memcmp, memset)Dma 63 (one instance proves every operation)6163
DMA_MEMCPY_COSTDma 634663
DMA_INPUTCPY_COSTDma 634063
DMA_PRE_POST_COST (memcmp, memset)DmaPrePost 104 (one instance)104104
DMA_PRE_POST_MEMCPY_COSTDmaPrePost 10491104
DMA_PRE_POST_INPUTCPY_COSTDmaPrePost 10459104
DMA_64_ALIGNED_MEMCPY_COST / DIVISORDma64AlignedMemCpy 67 / 867 / 867 / 8
DMA_64_ALIGNED_MEMSET_COST / DIVISORDma64AlignedMemSet 35 / 835 / 835 / 8
DMA_64_ALIGNED_MEMCMP_COST / DIVISORDma64AlignedMem 50 / 450 / 450 / 4
DMA_64_ALIGNED_INPUTCPY_COST / DIVISORDma64Aligned 77 / 4 (the only one proving it)58 / 477 / 4
DMA_UNALIGNED_COSTDmaUnaligned 424242

Memory and base cost​

CostInstancePreviousVersion 1
MEM_READ_COSTMem 87 / 4 → 22 per lane, dual RAM1611
MEM_WRITE_COSTMem 87 / 4 → 22 per lane, dual RAM1818
INPUT_READ_COSTInputData 29 / 12929
ROM_READ_COST / ROM_INIT_COSTRomData 22 / 21411
MEM_ALIGN_COSTMemAlign 505350
MEM_ALIGN_READ_UNALIGNED_1_COST2 × MEM_ALIGN106100
MEM_ALIGN_READ_UNALIGNED_2_COST3 × MEM_ALIGN159150
MEM_ALIGN_WRITE_UNALIGNED_1_COST3 × MEM_ALIGN159150
MEM_ALIGN_WRITE_UNALIGNED_2_COST5 × MEM_ALIGN265250
MEM_ALIGN_READ_BYTE_COSTMemAlignReadByte 252525
MEM_ALIGN_WRITE_BYTE_COSTMemAlignWriteByte 323232
ROM_COSTRom 16 × 2²²16 × 2²²16 × 2²²
TABLES_COSTVirtualTableZisk1 65 + VirtualTableZisk0 39, × 2²¹105 × 2²¹104 × 2²¹
BASE_COSTROM_COST + TABLES_COST287,309,824285,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​

  • sh3add is charged BINARY_COST, the general case. Depending on its operands it can also be proven by BinaryAdd or BinaryAddHi, but the emulator applies that breakdown only to add.
  • Every DMA operation pays the full row of the single instance that proves it.
  • The precompile memory charges cover the direct a/b operands 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.