Benefits and Challenges of Starknet Built-in Functions

Original: Builtins and Dynamic Layouts

Translation and proofreading: "StarkNet Chinese Community"

Summary

Built-in functions optimize the proof process. However, each proof is computed from the layout. For certain proof work, the advantages of built-in functions will be greatly reduced if the layout is inefficient. Currently, there is a small static list of layouts, and each proof is computed based on the most appropriate layout from that list. This way of laying out static lists has two drawbacks. First, there is a limited variety of layouts. This is inefficient for most proof work and creates complex fee mechanisms that impose unnecessary costs on users. Second, maintaining the list manually is difficult. Once the number of builtins gets too high, manual maintenance becomes difficult and can actually hinder the process of proving efficient builtins that support a large number of nuances. To address these issues, the StarkWare team is developing a dynamic layout system where layouts are custom-made for each proof of work.

The Cairo stack facilitates provably general-purpose computing by compiling Cairo code into instructions for STARK-friendly CPU architectures: the Cairo VM (hereafter referred to as CVM). Many of the advantages of general-purpose CPUs come at an inherent cost, and CVM is not optimized for some common operations. Keccak, Pedersen, Poseidon hash functions are common such operations, as are elliptic curve operations, range checking (i.e. checking whether a particular number is within a particular range of values), and others.

To address the relative inefficiency of CVMs, the Cairo stack introduces the concept of built-ins for critical operations: plugins that optimize such operations to prove complexity. Built-in functions can be compared to ASICs: ASICs are application-specific integrated circuits, and built-in functions are application-specific algebraic constraints (AIR). If you don't know or don't remember what AIR is, it's briefly covered later in this article; read this article for more details.

In short, proof complexity is related (roughly linear) to resources called trace units, and built-in functions simplify proofs of specific operations by using much fewer trace units than Cairo VM.

Now that the benefits of built-in functions have been explained, it becomes clear why built-in functions were developed for many common operations. This is easier said than done. The current process of introducing new built-ins into Starknet consists of the following steps:

1. Writing AIR

2. Integrate with the prover by creating a new layout (described below)

3. Integrate into Starknet, i.e. modify its code base and developer tools to use new built-in functions

In addition to the challenges of writing AIR, there is a lot of room for improvement in the remaining two phases. This advanced article will describe in more detail AIR's built-in functions as application-specific, the above issues, and future plans.

Built-in Functions: Application Specific AIR

AIR is an acronym for Algebraic Intermediate Representation. In this and other StarkWare articles, AIR is a polynomial system for representing virtual machines. For example, Cairo takes its name from CPU AIR: a polynomial system representing a specific CPU architecture. The solutions of this polynomial system represent efficient state transitions, called efficient algebraic execution trajectories (AETs).

STARK proves that the operation of the virtual machine is correct by proving that the execution trajectory corresponding to a given AIR is valid. Roughly speaking, an execution trajectory is a table of numbers, and the STARK protocol proves that these numbers together solve a polynomial system.

The same operation can be calculated in many ways, some of which are more efficient. In this paper, the proof complexity basically depends on the track size, i.e. the number of track cells in the table. Because the traces are generated for AIR, AIR is designed for applications to significantly reduce the execution traces for specific calculations. Built-in functions are specialized AIR optimized for the application.

The table below shows the efficiency improvements for specific built-in functions (all in production).

Trajectory layout: present and future

As mentioned earlier, AET is roughly a table of numbers that represents the sequence of steps in the coded virtual machine (that is, the execution of the program). To compute the proof, the prover runs the STARK protocol on the execution track of the associated AIR.

Above, we introduced built-in functions as application-specific AIR designed to minimize the complexity of proofs by reducing the number of trace units required to encode computations. However, if built-in functions are randomly integrated in Starknet, many trajectory units may be wasted, and the expected benefits will be reduced. Let's explain in detail below.

In short, track layout is the assignment of track cells to different "components". In this article, these components are the CVM and built-in functions. Specifically, the layout specifies the relative number of track cells each component gets. (Layout constructs are always used to simplify validation. To learn more, read the "Simplicity" section of this post).

The key point is that the proof complexity depends on the total number of track cells allocated by the layout, and the track cell allocation may be larger than actually needed. For example, to demonstrate the step ordering of CVMs, a layout that assigns only trace cells to CVM components is roughly twice as efficient as a layout that assigns half of the trace cells to Poseidon built-in functions. In conclusion, a suitable layout can greatly reduce the complexity of proving a particular computation.

There is currently a manually maintained list of layouts that grows over time for two main reasons:

1. The built-in functions can only be used for the layout of the track unit assigned to them. Therefore, adding built-ins requires at least a new layout.

2. A layout tailored to execute Cairo code optimizes cell allocation. Therefore, optimization of use cases in cells often requires new layouts.

The code for the prover and validator (Solidity and Cairo validators) is configured according to the layout list.

As the Keccak and Poseidon builtins were added, it became increasingly difficult to keep layout lists small enough to accommodate many builtins and keep most Starknet blocks executing efficiently. Furthermore, efficiency is expected to drop significantly as additional built-ins are introduced, since the layout must account for the many possible combinations and ratios among built-ins.

The StarkWare team is currently working on improving the system by ditching pre-made layout lists in favor of "dynamic layouts", which are instant customizations for each execution of Cairo code. Dynamic Layout will always do the best-proportioned allocation for the verification job at hand. From an engineering standpoint, supporting dynamic typing would require considerable changes to the codebase. However, the StarkWare team hopes to simplify Starknet's proof layer by taking advantage of dynamic layout, improved track unit utilization, and better utilization of provers.

With dynamic layouts, the hassle of manually maintaining many built-ins disappears, simplifying the process of integrating more new built-ins into Starknet.

Dynamic Layout and Fees

One purpose of transaction fees is to charge users the marginal protocol cost incurred by transactions. Since the unit of transaction fees is currency, the fee mechanism involves conversion from resources (eg, virtual machine steps, built-in functions, calldata, Ethereum gas) to tokens (eg, STRK, ETH).

Currently, because provers charge fees based on total traces rather than utilization ratios, wasted resources are borne by users. Dynamic layout will improve track unit utilization, thereby reducing the charging of "unnecessary" transaction fees (including resource consumption not directly caused by user transactions).

Starknet built-in function integration

At this point, the integration of built-in functions is short of the last step, which is to modify the Starknet code base to realize practical use. The extent of code modification is related to the layout application, and it is necessary to modify the code to ensure that the Starknet operating system calls built-in functions when possible. For example, the Starknet operating system calls the Poseidon hash function during the execution of Cairo code, and at the same time calls the Poseidon built-in function.

Similar to layouts, Starknet builtins can now be manually supported. However, unlike the layout case, this manual support is not a barrier to integration even though there are many built-in functions. In other words, Starknet builtins support is not a barrier to integration, dynamic layout will really pave the way for creating and integrating additional builtins.

Summarize

In this article we explain what built-in functions are, their benefits, the challenges involved, and StarkWare's plans. The current focus is on dynamic layout, which will not only improve the efficiency of the proof process, but also facilitate the integration of new built-ins.