Origami: Simplifying Ethereum's VDF with Customized Plonk

Table of Contents

Ethereum relies on a Verifiable Delay Function (VDF) to ensure fairness and security in its consensus protocol. The Ethereum community has been considering the adoption of the MinRoot VDF, a sophisticated mathematical construct. However, this choice comes with its own set of challenges, particularly in terms of efficiency and computational demands. Enter Origami VDF – an ingenious solution designed to streamline and enhance the MinRoot VDF.

I. Understanding why we need Origami

Origami VDF, at its core, is a groundbreaking approach to implementing the MinRoot VDF. To truly appreciate Origami's significance, let's break down its key elements.

Origami VDF Overview: Origami VDF is like a masterful piece of origami, folding and simplifying the complex MinRoot VDF. Its primary mission is to make the MinRoot VDF more efficient and user-friendly. But why is this important?

Importance of VDF: In the world of Ethereum, Verifiable Delay Functions play a vital role. Think of VDFs as digital hourglasses, ensuring that no one can manipulate time to their advantage. They are crucial for ensuring fairness and security within Ethereum's consensus protocol.

Ethereum's Need: Ethereum validators contribute random data to a process called RANDAO, a fundamental part of the consensus protocol. Without a VDF, the last validator in line could potentially manipulate the outcome by choosing when to reveal their input. Origami VDF steps in to mitigate this vulnerability.

Efficiency Matters: The world of blockchain operates at the speed of technology, and efficiency is paramount. Origami VDF is a response to the need for an efficient VDF construction. It aims to ensure that the VDF doesn't become a bottleneck, allowing Ethereum and other blockchain systems to function smoothly and securely.

Origami VDF simplifies the MinRoot VDF while maintaining its core function - to provide verifiable delay and fairness. It's like streamlining a complex machine to make it more user-friendly and efficient, ensuring that Ethereum remains secure and accessible to all. Now, let's delve deeper into the technical aspects that underpin Origami VDF.

II. Background before diving in

Before delving deeper into Origami VDF, let's clarify some essential concepts and notation used in this discussion.

MinRoot Hash: The MinRoot VDF is the focal point of our exploration. It involves a chain of MinRoot hashes and a Nova zero-knowledge proof (ZKP). The MinRoot VDF has been earmarked for deployment on Ethereum due to its importance in securing billions of on-chain assets.

Plonk Arithmetization: Plonk is a mathematical framework used for building VDFs. It relies on gates and constraints to achieve its objectives.

Polynomial Commitment Scheme: A crucial element in VDFs, this scheme enhances efficiency by allowing the use of commitments instead of sending entire polynomials.

Folding Scheme: Folding schemes are essential for aggregating instances of a relation into a single instance, reducing computational complexity.

Recursive Proofs: These proofs play a pivotal role in optimizing VDFs. They enable various applications, including making Ethereum Virtual Machine (EVM) incompatible proofs compatible and aggregating multiple proofs into a single proof.

III. The MinRoot VDF

To appreciate Origami VDF's significance, it's crucial to understand the foundation upon which it's built - the MinRoot VDF. Let's delve deeper into the MinRoot VDF, its structure, challenges, and existing implementations.

Overview of the MinRoot VDF: The MinRoot VDF is at the forefront of secure and efficient delay functions, making it a prime candidate for adoption within the Ethereum ecosystem. Its core structure involves a chain of MinRoot hashes and a Nova zero-knowledge proof.

- Structure and Components: The MinRoot VDF's structure consists of a sequence of MinRoot hashes. These hashes are linked together, forming a chain. To validate the output of this chain, a Nova zero-knowledge proof is employed. This combination ensures both delay and verifiability, making it suitable for Ethereum's needs.

Existing MinRoot VDF Implementation: The MinRoot VDF is not just a theoretical concept; it has been implemented in practice.

- Reference Code and Computational Requirements: There exists a reference implementation of the MinRoot VDF, providing a practical solution for the Ethereum community. However, the computational requirements of this implementation present significant challenges.

- Proof Generation Time: A critical aspect of the MinRoot VDF's performance is the time it takes to generate proofs. For N iterations of the MinRoot hash, the proof generation time is primarily dominated by 6N group multiplications. This means that the proof itself requires substantial computational effort, potentially exceeding the time required for the hash chain's computation.

Challenges in Optimizing the MinRoot VDF: The MinRoot VDF is a powerful tool, but it also presents challenges that need to be overcome.

- Proof Size and Computation Cost: One of the primary challenges lies in the size of the proofs and their computational cost. Each hash iteration requires a field exponentiation for the hash and six group multiplications for the proof. These operations demand substantial computational resources.

Origami VDF's design takes these challenges into account, aiming to enhance the MinRoot VDF's efficiency and usability. By addressing the issues related to proof size and computational complexity, Origami VDF provides a practical and efficient solution for Ethereum and the broader blockchain community. It represents a step forward in the evolution of VDFs, making them more accessible and powerful tools for securing blockchain networks.

IV. Origami VDF Design

Origami VDF represents a significant leap forward in VDF technology. It introduces innovative approaches to address the challenges of efficiency and computational complexity that have historically surrounded VDF implementations.

Introduction to Origami VDF: Origami VDF is not just about simplifying the MinRoot VDF; it's about making VDFs in general more accessible and efficient. Here's an overview of how Origami VDF accomplishes this:

- Motivation and Goals: The motivation behind Origami VDF is to streamline the MinRoot VDF's complexity while maintaining its core functionality. The primary goal is to create a VDF that is both efficient to compute and easy to verify.

- Overview of the Proposed Approach: Origami VDF achieves these goals through a combination of a custom Plonk prover and an innovative folding scheme. These components work in harmony to reduce computational requirements and enhance overall performance.

Customized Plonk Prover: One of the standout features of Origami VDF is its customized Plonk prover, which plays a pivotal role in optimizing the VDF. Here's a closer look at this component:

- Design and Benefits: The custom gate for the MinRoot hash is a key element of the Plonk prover. This gate is meticulously designed to prove a MinRoot iteration with just a single constraint. This is a significant improvement compared to traditional Plonk gates, which typically require three constraints per iteration. The benefits are clear: reduced computational load and increased efficiency.

- Reduction of Constraints per Iteration: The reduction in constraints per iteration is a game-changer. It means that each step of the MinRoot hash can be verified with fewer computational resources, making the VDF considerably more efficient.

Folding Scheme for Origami: Another crucial aspect of Origami VDF's design is the folding scheme. This component enhances the VDF's overall performance by simplifying and aggregating instances. Here's what you need to know:

- Design and Explanation: The folding scheme is like a clever organizational tool. It breaks down the complex MinRoot hash chain into manageable sub-chains. As each sub-chain is evaluated, it can be proved, and its results can be seamlessly folded into the existing instance. This approach significantly reduces the computational workload and speeds up the verification process.

- Impact on Prover's Workload: The folding scheme's impact on the prover's workload cannot be overstated. It transforms what was once a resource-intensive task into a more streamlined and efficient process. This reduction in workload translates to faster VDF computation and lower costs.

Recursive Proof (Optional): While not a core component, Origami VDF also offers the option of using recursive proofs. Let's explore this optional feature:

- Discussion of the Optional Recursive Proof: Recursive proofs are powerful tools in the world of VDFs. They allow one proof to assert the correctness of another. This feature is particularly useful for various applications, such as making proofs compatible across different blockchains and aggregating multiple proofs into a single proof.

- Trade-Offs in Proof Size and Computation: The use of recursive proofs introduces trade-offs. While it can significantly optimize VDFs, it can also impact proof size and computation complexity. Decisions around whether to employ recursive proofs depend on specific use cases and priorities.

Origami VDF's design is a testament to innovation in the blockchain world. It combines a customized Plonk prover, a folding scheme, and the option for recursive proofs to create a VDF that is both efficient and versatile. It simplifies complex processes, reduces computational demands, and ultimately contributes to the efficiency and security of Ethereum and other blockchain systems.

V. Performance and Deployment

Understanding the performance and deployment considerations of Origami VDF is crucial in assessing its real-world impact on blockchain systems, particularly within the Ethereum ecosystem.

Performance Comparison: Origami VDF's performance is a key highlight, and it's essential to compare it with existing solutions, such as the MinRoot VDF.

- Comparison with MinRoot VDF: Origami VDF offers a substantial improvement in performance compared to the MinRoot VDF. It achieves this by reducing computational requirements and optimizing the proof generation process. This enhancement results in faster proving times and lower computational costs.

- Improvements in Proving Time and Computation Cost: Origami VDF's streamlined approach significantly reduces the time required for proof generation, ensuring that it aligns with the hash chain's computation time. This improvement is critical for maintaining the efficiency and security of blockchain systems.

Deployment Considerations: When deploying Origami VDF within the Ethereum ecosystem or any other blockchain network, several important considerations come into play.

- Choice of Curve for Ethereum Use Cases: Ethereum's specific use cases and requirements dictate the choice of curve for Origami VDF. Curve selection impacts performance, as different curves have varying parameters and characteristics.

- Implications of Curve Selection on Performance: The choice of curve has implications for both the hash chain proof's generation speed and the optional recursive proof's size and efficiency. Ethereum's use cases and performance requirements will guide this decision-making process.

- Estimations of Constraints and Proof Size: Estimating the number of constraints for Origami VDF's verification circuit is crucial for assessing its computational requirements. These estimates are instrumental in determining the hardware and computational resources needed for deployment.

Origami VDF's deployment considerations are pivotal for its practical application. Making informed decisions about curve selection and understanding the associated implications on performance is essential for optimizing its usage within the Ethereum community and the broader blockchain landscape. Summary, Origami VDF's performance enhancements and deployment considerations make it a valuable tool for improving the efficiency and security of blockchain systems. Its ability to deliver faster proving times and reduce computational costs has a significant impact on the practicality and accessibility of VDFs within Ethereum and other blockchain networks.

Conclusion

Origami VDF represents a significant step forward in simplifying Ethereum's VDF implementation. Its contributions extend beyond Ethereum, potentially benefiting the broader blockchain community. The adoption of Origami VDF holds the promise of improved efficiency and security in Ethereum's consensus protocol. As the blockchain landscape continues to evolve, Origami VDF stands as a testament to the spirit of innovation and optimization in this ever-changing field.

About Orochi Network

Orochi Network is a cutting-edge zkOS (An operating system based on zero-knowledge proof) designed to tackle the challenges of computation limitation, data correctness, and data availability in the Web3 industry. With the well-rounded solutions for Web3 Applications, Orochi Network omits the current performance-related barriers and makes ways for more comprehensive dApps hence, becoming the backbone of Web3's infrastructure landscape.