Benefits and Challenges of StarkNet Built-In Functions

StarkNet Built-In Functions: Pros and Cons

Original: Builtins and Dynamic Layouts

Translated and Proofread by: “StarkNet Chinese Community”

Summary

Built-in functions optimize the proof process. However, each proof is calculated based on a layout. For specific proof work, if the layout efficiency is low, the advantage of built-in functions will be greatly reduced. Currently, there is a small static list of layouts, and each proof is calculated based on the most suitable layout in the list. There are two shortcomings of this layout static list. Firstly, the layout types are limited. This is inefficient for most proof work and can result in complex charging mechanisms that impose unnecessary costs on users. Secondly, manual maintenance of the list is difficult. Once the number of built-in functions is too large, manual maintenance becomes difficult and actually hinders efficient built-in functions that support many subtle details in the proof process. To solve these problems, the StarkWare team is developing a dynamic layout system, where the layout is tailored for each proof workload.

• Why is LSDFi considered a transparent narrative?
• How does Ethereum adapt to and influence traditional finance?
• Looking for Alpha on-chain: which are the fastest-growing protocols? What are the current trends and narratives?

The Cairo stack promotes provable general computation by compiling Cairo code into instructions that are compatible with STARK-friendly CPU architectures: Cairo VM (CVM). Many of the advantages of a general CPU come at an inherent cost, and CVM is not optimized for some common operations. Keccak, Pedersen, Poseidon hash functions are such common operations, as well as elliptic curve operations, range checks (checking whether a specific number is within a specific value range), and other operations.

To solve the problem of CVM’s relative inefficiency, the Cairo stack introduces the concept of built-in functions for critical operations: plugins that optimize the proof complexity of such operations. Built-in functions can be compared to ASIC: ASICs are specialized integrated circuits, while built-in functions are application-specific algebraic constraints (AIR). If you don’t know or remember what AIR is, the article will briefly introduce it later; for more detailed information, please read this article.

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

After explaining the benefits of built-in functions, you know why it is necessary to develop built-in functions for many common operations. It is easier said than done. Currently, the process of introducing new built-in functions into Starknet includes the following steps:

1. Write AIR

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

3. Integrate with Starknet, i.e., modify its codebase and developer tools to use the new built-in functions

Aside from the challenge of writing the AIR, there is also a lot of room for improvement in the other two stages. This advanced-level article will go into more detail on the built-in functions as application-specific AIR, on the issues discussed above, and on future plans.

Built-in Functions: Application-Specific AIR

AIR stands for Algebraic Intermediate Representation. In this paper and other StarkWare articles, AIR is a polynomial system that represents a virtual machine. For example, Cairo stands for CPU AIR: a polynomial system representing a specific CPU architecture. The solution to this polynomial system represents valid state transitions, called Algebraic Execution Traces (AETs).

STARK verifies the validity of the virtual machine’s operations by proving that the given AIR corresponds to an effective execution trace. Essentially, the execution trace is a set of numeric tables, and the STARK protocol proves that these numbers together solve a polynomial system.

There can be multiple ways to perform the same operation, and some of these computations are more efficient than others. In this paper, proof complexity is essentially determined by the trace size, i.e., the number of trace cells in the table. Because the trace is generated for a given AIR, application-specific AIRs can significantly reduce the size of the execution trace for specific computations. Built-in functions are application-specific AIRs optimized for applications.

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

Trace Layout: Present and Future

As mentioned earlier, an AET is essentially a numeric table that encodes the ordering of steps (i.e., program execution) that encode the virtual machine. To compute the proof, the prover runs the STARK protocol on the relevant AIR’s execution trace.

In the previous section, we introduced built-in functions as application-specific AIRs designed to minimize proof complexity by reducing the number of trace cells required to encode specific computations. However, integrating built-in functions arbitrarily in Starknet may waste many trace cells and reduce the expected benefits. Let’s explain this in more detail below.

In short, trace layout allocates trace cells to different “components.” In this paper, these components are the CVM and built-in functions. Specifically, the layout specifies the relative number of trace cells each component receives. (Layout construction is always for simplifying verification. For more information, read the “Succinctness” section in this article.)

The key point is that the complexity of a proof depends on the total number of trace cells allocated by the layout, which may be larger than what is actually needed. For example, proving the step sequence of CVM is about twice as efficient with a layout that only allocates trace cells to the CVM component as compared to a layout that allocates half of the trace cells to Poseidon built-in functions. In general, an appropriate layout can greatly reduce the complexity of proving a specific computation.

There is currently a manually-maintained list of layouts, which grows mainly due to two reasons:

1. Built-in functions can only be used for layouts that allocate trace cells to them. Therefore, adding built-in functions requires at least one new layout.

2. Layouts customized for executing Cairo code can optimize cell allocation. Therefore, optimizations of use cases within cells often require new layouts.

The code of the prover and verifiers (Solidity and Cairo verifiers) is configured according to the list of layouts.

As Keccak and Poseidon built-in functions are added, it becomes increasingly difficult to maintain a small list of layouts that accommodates many built-in functions while keeping most StarkNet blocks efficiently executed. Furthermore, as additional built-in functions are introduced, efficiency is expected to decrease significantly, as layouts must consider many possible combinations and ratios between built-in functions.

The StarkWare team is currently working to improve the system by abandoning the pre-determined list of layouts and supporting “dynamic layouts,” i.e., customizing them on-the-fly for each execution of Cairo code. Dynamic layouts will always allocate cells in the best possible ratio for the verification work at hand. From an engineering perspective, supporting dynamic inputs requires significant changes to the codebase. However, the StarkWare team hopes to leverage dynamic layouts to improve trace cell utilization, better utilize the prover, and simplify the proof layer of StarkNet.

With dynamic layouts, the hassle of manually maintaining many built-in functions will no longer exist, simplifying the process of integrating more new built-in functions into StarkNet.

Dynamic Layouts and Fees

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

Currently, because the prover charges fees based on the total trace rather than utilization ratio, wasted resources are borne by the user. Dynamic layouts will increase trace cell utilization, thereby reducing the collection of “unnecessary” transaction fees (including resource consumption not directly generated by user transactions).

Starknet Built-in Function Integration

With this, integrating the built-in functions is just one step away, which is to modify the Starknet codebase to make actual use of them. The extent and layout of code modifications needed to ensure that the Starknet operating system calls the built-in functions when it is possible depends on the application. For example, the Starknet operating system calls the Poseidon hash function during Cairo code execution and needs to call the Poseidon built-in function at the same time.

Similar to the layout, Starknet built-in functions can now be supported manually. However, unlike the layout, this manual support does not pose an obstacle to integration even if there are many built-in functions. In other words, support for Starknet built-in functions is not an obstacle to integration, and dynamic layout will truly pave the way for creating and integrating additional built-in functions.

Conclusion

In this article, we explained what built-in functions are, their benefits, the challenges involved, and StarkWare’s plans. Currently, the focus is on dynamic layout, which not only improves the efficiency of the proof process, but also facilitates the integration of new built-in functions.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!