Custom ISA: Achieving Ultimate Efficiency in zk-Proving

Published on:
Jul 4, 2024
Written by:
Lita Team
Read time:
10 Min
Category:
Education

Lita Team

Custom ISA (Instruction Set Architecture)

The current discourse surrounding zero-knowledge virtual machine (zkVM) architecture often revolves around a binary choice: general-purpose vs. custom Instruction Set Architectures (ISAs). At Lita, we propose a more nuanced perspective. We believe that zero-knowledge proofs (ZKPs), with their unique computational demands, necessitate an infrastructure specifically optimized for their efficient execution. This conviction led us to develop a custom ISA within our Valida zkVM solution, unlocking maximum efficiency for SNARK-proving.

However, a recognized challenge with custom ISAs is the lack of existing compiler toolchain and, consequently, high-level language support, potentially compromising usability for performance. We chose to tackle this challenge by developing our Valida LLVM compiler toolchain, which bridges this gap and enables developers to use familiar languages like C within our custom ISA.

>>>Learn more about Valida C Compiler Toolchain

This "dual approach" eliminates the need to choose between peak performance and developer accessibility. It unlocks maximum efficiency within a user-friendly framework, paving the way for the next generation of secure and efficient ZKP applications.

1. What is Instruction Set Architecture in zkVM?

An Instruction Set of Architecture is a model of computation that can be implemented by a physical computer or a virtual machine (VM). In the context of a zkVM, an instruction set architecture defines the format of machine code generated by the compiler and executed by the VM. It encompasses key elements such as:

  • Registers : Small, fast storage for temporary data and instructions, enabling quick data access and manipulation.
  • Program (RAM): Temporary storage for data and instructions during execution, providing fast access and modification.
  • Program Memory: Permanent storage for the program's code, ensuring that the code is available for execution and proof generation.
  • Instruction Types: Categories of operations (arithmetic, data movement, control flow, etc.) designed to balance expressiveness and proof efficiency.
  • Instruction Formats: Structures defining instructions, including opcodes and operands, optimized for efficient execution and proof encoding.
  • Addressing Modes: Methods for locating data or instructions in memory, supporting efficient access patterns and simple address calculations for proofs.

These elements play vital roles in shaping the capabilities and performance of a zkVM and in generating zero-knowledge proofs (ZKPs).

In the context of a zkVM, an Instruction Set Architecture defines the format of machine code generated by the compiler and executed by the VM

Since this article delves deeper into custom ISAs, we won't cover the broader role of ISAs within the zkVM process flow. For a more comprehensive overview of ISAs in zkVM design choices, please refer to our previous blogs.

2. Motivation for Building Custom ISA

The motivation to develop a custom ISA arises from recognizing two key limitations: firstly, traditional ISAs are inadequate in zkVM contexts, and secondly, the cost of registers in zkVM arithmetization.

Why Traditional ISAs Fall Short in zkVM Contexts

Traditional Instruction Set Architectures are designed for hardware execution, optimized to address memory locality concerns. In hardware systems, data needs to traverse physical distances on silicon, leading to increased latency as the distance grows. General-purpose registers in traditional ISAs help alleviate this issue by offering temporary storage inclose proximity to the CPU's arithmetic logic unit (ALU), facilitating rapid access for computations. These registers play a crucial role in the ISA, functioning as operands for ALU operations.

However, the context of SNARK-proving in zkVMs is fundamentally different. Unlike hardware, accessing RAM in a zkVM incurs no additional cost compared to accessing a register. This makes the motivation to use traditional general-purpose registers irrelevant in zkVMs.

One distinction between electronic processors and zk circuits is that electronic processors are very efficient at handling branching conditions, quickly executing different code paths based on conditions. In contrast, zk circuits require computational resources for every possible branch, regardless of which path is taken.

To address this inefficiency, combining several instructions with closely related functionality into single, more complex instructions can be advantageous. This approach reduces the number of branches and minimizes the overall computational cost, even if it increases the total instruction count of the program.

The Cost of Registers in zkVM Arithmetization

In the context of SNARKs, the VM's operations are arithmetized into Algebraic Intermediate Representations (AIRs) or Plonkish arithmetizations. This process translates the VM's operations into polynomial constraints that can be verified efficiently.

However, each register in this setup translates to a dedicated column in the execution trace. The total costs for the prover are roughly no. of columns x TlogT, where T is the height of each column. This results in:

  • Increased Prover Costs: Each additional register requires an extra column in the trace. This directly increases the workload for the prover, making the proof generation more resource-intensive.
  • Complexity Management: Handling multiple columns for registers increases the complexity of the proof generation and verification process, potentially leading to more points of failure or inefficiency.

By recognizing and adapting to the distinct context of zkVMs, Valida's custom ISA eliminates the irrelevant aspects of traditional register use, ensuring a streamlined and efficient architecture for zk-proof generation.

3. Valida Custom ISA Design: Simplified and Specialized

The custom ISA design of Valida is based on addressing the limitations and costs incurred from traditional general-purpose ISAs. We’ve summarized the key differences between the 2 different types of instruction set architectures in the table below.

Valida's custom Instruction Set Architecture (ISA) addresses the limitations of general-purpose Instruction Set Architectures.

Unlike ordinary CPUs, Valida does not include general-purpose registers. This simplification eliminates the need for saving and restoring registers during function calls, avoiding register spilling and reducing code generation complexity. In zkVMs, where RAM access incurs no additional cost, this design choice streamlines proof generation.

It’s noteworthy that Valida simplifies its architecture by supporting only two special-purpose registers:

Program Counter (PC): Tracks the address of the current instruction in memory

Function:

  • Ensures the sequential execution of instructions by keeping track of the current position in the program.

Benefits:

  • Facilitates efficient control flow management.
  • Simplifies the instruction fetch process, leading to faster execution.

Frame Pointer (FP): Marks the beginning of the stack frame.

Function:

  • Provides a fixed reference point within the stack, which helps manage function calls and local variables.

Benefits:

  • Streamlines stack management by providing a stable point of reference for accessing local variables and function parameters.
  • Reduces the complexity of managing dynamic memory allocation within the stack.

No Dedicated Stack Pointer (SP) Register

Valida uses constant-sized stack frames, storing variable-sized locals and arguments on the heap. This design choice further simplifies the architecture and reduces complexity in proof generation.

A Modular Design

Valida’s custom-made RISC-inspired, modular, zk-friendly design includes various specialized modules or "chips" such as:

  • 32-bit ALU Chips: Handling 32-bit unsigned integer arithmetic, bitwise operations, and bit shifts.
  • CPU Chip
  • Memory Chip (RAM)
  • Program Chip (ROM)
  • 8-bit Range Checker Chip

Having a modular architecture allows Valida to be extended with application-specific chips which optimize key cost centers in a particular application. For example, an application that computes many SHA-256 hashes could have its proving accelerated by using a version of Valida that incorporates a SHA-256 chip.

Valida's custom, zk-specialized Instruction Set Architecture (ISA) is designed to achieve maximum efficiency in zk-proof generation.

Inherent Trade-offs of Custom ISAs

Custom instruction set architectures come with inherent trade-offs, such as developer unfriendliness. The steep learning curve associated with specialized ISAs can deter developers, especially those accustomed to more conventional programming languages. This can lead to a smaller pool of developers capable of effectively working with the technology, potentially slowing down innovation and adoption.

A custom toolchain, like the Valida LLVM compiler, removes this trade-off by allowing developers to use familiar languages such as C within this specialized ISA framework. The investment of time and effort is well worth it, as it offers long-term development advantages.

4. Why Valida ISA Could be the Future Standard

By developing a custom ISA that eliminates the inefficiencies of traditional ISAs, Valida establishes a new benchmark for zkVM performance. This demonstrates that a streamlined, purpose-built approach can deliver superior results in zk-proof generation.

Tailored Design: By creating a custom ISA, we can optimize the architecture specifically for zk-proof generation. This enables us to eliminate unnecessary components like general-purpose registers and incorporate only the essential special-purpose registers, greatly improving performance and efficiency.

Specialized Compiler: To complement our custom ISA, we have developed a dedicated compiler toolchain, Valida LLVM. This toolchain is specifically optimized to leverage the unique features of our ISA, ensuring the efficient translation of high-level code into machine instructions. This approach enables developers to benefit from the excellent performance of a custom ISA while coding in familiar languages.

Optimization Synergy: The combination of a custom Instruction Set Architecture and a dedicated compiler enables profound optimization at all stages of code execution. Unlike conventional compilers, Valida LLVM can implement precise optimizations achievable only with a comprehensive grasp of the underlying ISA, resulting in substantial enhancements in zk-proof generation efficiency.

Proven Advantages: Our performance benchmarks against industry peers such as RISC Zero, SP1, and Jolt have shown that in some cases, Valida achieves multiple orders of magnitude faster and more efficient zk-proof generation. This is not just an incremental improvement but a substantial leap forward in capability.

By pioneering this approach, we are setting a new standard for zkVMs and verifiable computation. Our commitment to innovation and optimization ensures that Valida is not only a highly effective solution today but is also designed with a future-proof architecture to lead the industry into the future.

Valida achieves multiple orders of magnitude faster and more efficient zk-proof generation
Valida performance benchmarks against industry peers such as RISC Zero, SP1, and Jolt

5. Beyond Efficiency: A Glimpse into the Future

From the 1960s to the 2000s and beyond, the evolution of computing architecture has been driven by the need for increased efficiency, performance, and specialization. Initially, Instruction Set Architectures were tailored to specific market niches, but the industry has progressively moved towards more unified and versatile architectures.

As integrated circuits advanced, the debate between CISC and RISC highlighted the trade-offs between complexity and efficiency. RISC architectures, with their simplified instructions, gained prominence as high-level languages and efficient execution became more critical.

Modern computing trends are shifting towards domain-specific architectures (DSAs), which are designed for specific tasks such as graphics processing or neural network inference. This shift is motivated by the necessity for energy efficiency and performance optimization as Moore's Law and Dennard Scaling approach their limits.

The Trend Towards Custom, Domain-Specific ISAs

The future of computing lies in custom, domain-specific ISAs that optimize performance and efficiency for specific applications. Valida's custom ISA exemplifies this trend by eliminating irrelevant components and focusing on zk-proof generation. Moving forward, custom ISAs hold the key to unlocking a new era of specialized computing, pushing the boundaries of performance and efficiency.

—---

Explore Valida with Our C Compiler

Now you can explore the efficiency of our zk-optimized VM featuring a universal compiler. We invite you to experience the alpha release of our compiler toolchain, enabling you to compile, run, and test C programs on Valida.

—---

This concludes our 3-part series delving into the world of zkVMs. We hope you found this exploration informative and insightful. As the field of verifiable computing continues to evolve, we at Lita are committed to fostering open dialogue. We welcome your comments, questions, and ideas – let's keep the conversation going! To dive deeper, visit our website and GitBook to learn more about what we're building and how you can get involved.

________________________________________

Disclaimer:

The content of this blog, including text, graphics, and images, is protected by copyright © 2023 - 2024 Lita.Foundation. All rights reserved. Unauthorized use and/or duplication of this material without express and written permission from this site’s author and/or owner is strictly prohibited. Excerpts and links may be used, provided that full and clear credit is given to Lita.Foundation with appropriate and specific direction to the original content.

For any questions or permissions, please contact Lita Foundation.

You may also like

Exploring zk-VM Design Trade-offs

June 12, 2024

Exploring zk-VM Design Trade-offs

Announcing Lita's Valida zkVM & C Compiler

May 27, 2024

Announcing Lita's Valida zkVM & C Compiler

What is zkVM?

May 26, 2024

What is zkVM?