This section documents how programs generated by Cairo Native keep track of gas and builtins during execution.
Gas management in a blockchain environment involves accounting for the amount of computation performed during the execution of a transaction. This is used to accurately charge the user at the end of the execution or to revert early if the transaction consumes more gas than provided by the sender.
This documentation assumes prior knowledge about Sierra and about the way gas accounting is performed in Sierra. For those seeking to deepen their understanding, refer to Enitrat’s Medium post about Sierra and greged’s about gas accounting in Sierra.
The gas builtin is used in Sierra in order to perform gas accounting. It is
passed as an input to all function calls and holds the current remaining
gas. It is represented in MLIR by a simple u64.
The process of calculating gas begins at the very outset of the compilation process. During the initial setup of the Sierra program, metadata about the program, including gas information, is extracted. Using gas helper functions from the Cairo compiler, the consumed cost (steps, memory holes, builtins usage) for each statement in the Sierra code is stored in a HashMap.
The action of withdrawing gas can be split in two steps:
- Calculating Total Gas Cost: Using the previously constructed HashMap, we iterate over the various cost tokens (including steps, built-in usage, and memory holes) for the statement, convert them into a common gas unit, and sum them up to get the total gas cost for the statement.
- Executing Gas Withdrawal: The previously calculated gas cost is used
when the current statement is a
withdraw_gaslibfunc call.
The withdraw_gas libfunc takes the current leftover gas as input and uses
the calculated gas cost for the statement to deduct the appropriate amount
from the gas builtin. In the compiled IR, gas withdrawal appears as the
total gas being reduced by a predefined constant. Additionally, the libfunc
branches based on whether the remaining gas is greater than or equal to the
amount being withdrawn.
Let's illustrate this with a simple example using the following Cairo 1 code:
fn run_test() {
let mut i: u8 = 0;
let mut val = 0;
while i < 5 {
val = val + i;
i = i + 1;
}
}As noted earlier, gas usage is initially computed by the Cairo compiler for each state. A snippet of the resulting HashMap shows the cost for each statement:
...
(
StatementIdx(26),
Const,
): 2680,
(
StatementIdx(26),
Pedersen,
): 0,
(
StatementIdx(26),
Poseidon,
): 0,
...For statement 26, the cost of the Const token type (a combination of step,
memory hole, and range check costs) is 2680, while other costs are 0.
Let's see which libfunc is called at statement 26:
...
disable_ap_tracking() -> (); // 25
withdraw_gas([0], [1]) { fallthrough([4], [5]) 84([6], [7]) }; // 26
branch_align() -> (); // 27
const_as_immediate<Const<u8, 5>>() -> ([8]); // 28
...When the Cairo native compiler reaches statement 26, it combines all costs
into gas using the Cairo compiler code. In this example, the total cost is
2680 gas. This value is used in the withdraw_gas libfunc and the compiled
corresponding IR to withdraw the gas and determine whether execution should
revert or continue. This can be observed in the following MLIR dump:
llvm.func @"test::test::run_test[expr16](f0)"(%arg0: i64 loc(unknown), %arg1: i128 loc(unknown), %arg2: i8 loc(unknown), %arg3: i8 loc(unknown)) -> !llvm.struct<(i64, i128, struct<(i64, array<24 x i8>)>)> attributes {llvm.emit_c_interface} {
...
%12 = llvm.mlir.constant(5 : i8) : i8 loc(#loc1)
%13 = llvm.mlir.constant(2680 : i128) : i128 loc(#loc1)
%14 = llvm.mlir.constant(1 : i64) : i64 loc(#loc1)
...
^bb1(%27: i64 loc(unknown), %28: i128 loc(unknown), %29: i8 loc(unknown), %30: i8 loc(unknown)): // 2 preds: ^bb0, ^bb6
%31 = llvm.add %27, %14 : i64 loc(#loc13)
%32 = llvm.icmp "uge" %28, %13 : i128 loc(#loc13)
%33 = llvm.intr.usub.sat(%28, %13) : (i128, i128) -> i128 loc(#loc13)
llvm.cond_br %32, ^bb2(%29 : i8), ^bb7(%5, %23, %23, %31 : i252, !llvm.ptr, !llvm.ptr, i64) loc(#loc13)
...Here, we see the constant 2680 defined at the begining of the function.
In basic block 1, the withdraw_gas operations are performed: by comparing
%28 (remaining gas) and %13 (gas cost), the result stored in %32
determines the conditional branching. A saturating subtraction between the
remaining gas and the gas cost is then performed, updating the remaining gas
in the IR.
The final gas usage can be easily retrieved from the gas builtin value returned by the function. This is accomplished when parsing the return values from the function call:
...
for type_id in &function_signature.ret_types {
let type_info = registry.get_type(type_id).unwrap();
match type_info {
CoreTypeConcrete::GasBuiltin(_) => {
remaining_gas = Some(match &mut return_ptr {
Some(return_ptr) => unsafe { *read_value::<u128>(return_ptr) },
None => {
// If there's no return ptr then the function only returned the gas. We don't
// need to bother with the syscall handler builtin.
((ret_registers[1] as u128) << 64) | ret_registers[0] as u128
}
});
}
...
}
...
}
...This code snippet extracts the remaining gas from the return pointer based on the function's signature. If the function only returns the gas value, the absence of a return pointer is handled appropriately, ensuring accurate gas accounting.
The Cairo Native compiler records the usage of each builtins in order to provide information about the program's builtins consumption. This information is NOT used for the gas calculation, as the gas cost of builtins is already taken into account during the gas accounting process. The builtins counter types can each be found in the types folder. Taking the Pedersen hash as an example, we see that the counters will be represented as i64 integers in MLIR. Counters are then simply incremented by one each time the builtins are called from within the program.
Let us consider the following Cairo program which uses the pedersen builtin:
use core::integer::bitwise;
use core::pedersen::pedersen;
fn run_test() {
let mut hash = pedersen(1.into(), 2.into());
hash += 1;
}We expect Native to increment the pedersen counter by 1 given the above code.
Let's first check how this compiles to Sierra:
const_as_immediate<Const<felt252, 1>>() -> ([1]); // 0
const_as_immediate<Const<felt252, 2>>() -> ([2]); // 1
store_temp<felt252>([1]) -> ([1]); // 2
store_temp<felt252>([2]) -> ([2]); // 3
pedersen([0], [1], [2]) -> ([3], [4]); // 4
drop<felt252>([4]) -> (); // 5
store_temp<Pedersen>([3]) -> ([3]); // 6
return([3]); // 7
contracts::run_test@0([0]: Pedersen) -> (Pedersen);
In the compiled Sierra, we can see that the pedersen builtin is passed
with the call to the run_test which starts at statement 0. It is then
used in the call to the pedersen libfunc. We would expect to see the
pedersen counter incremented by 1 in the Native compiler. Below is the
compiled MLIR dump for the same program:
...
llvm.func @"test::test::run_test(f0)"(%arg0: i64 loc(unknown)) -> i64 attributes {llvm.emit_c_interface} {
%0 = llvm.mlir.constant(2 : i256) : i256 loc(#loc1)
%1 = llvm.mlir.constant(1 : i256) : i256 loc(#loc1)
%2 = llvm.mlir.constant(1 : i64) : i64 loc(#loc1)
%3 = llvm.alloca %2 x i256 {alignment = 16 : i64} : (i64) -> !llvm.ptr loc(#loc2)
%4 = llvm.alloca %2 x i256 {alignment = 16 : i64} : (i64) -> !llvm.ptr loc(#loc2)
%5 = llvm.alloca %2 x i256 {alignment = 16 : i64} : (i64) -> !llvm.ptr loc(#loc2)
%6 = llvm.add %arg0, %2 : i64 loc(#loc2)
%7 = llvm.intr.bswap(%1) : (i256) -> i256 loc(#loc2)
%8 = llvm.intr.bswap(%0) : (i256) -> i256 loc(#loc2)
llvm.store %7, %3 {alignment = 16 : i64} : i256, !llvm.ptr loc(#loc2)
llvm.store %8, %4 {alignment = 16 : i64} : i256, !llvm.ptr loc(#loc2)
llvm.call @cairo_native__libfunc__pedersen(%5, %3, %4) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> () loc(#loc2)
llvm.return %6 : i64 loc(#loc3)
} loc(#loc1)
...The compiled MLIR function run_test takes a single argument as input, the
pedersen counter and returns the incremented counter at the end of the call.
The counter is incremented by 1 in the MLIR code, in the statement
%6 = llvm.add %arg0, %2 : i64 loc(#loc2), which takes the %arg0 input
and adds %2 to it. We can see from statement
%2 = llvm.mlir.constant(1 : i64) : i64 loc(#loc1) that %2 holds the
constant 1.
When this compiled MLIR code is called, the initial value of all builtin
counters is set to 0 as can be seen in the
invoke_dynamic function.