ARC-0043: Extending the Puzzle to a Full SNARK

[howardwu]

ARC-0043: Extending the Puzzle to a Full SNARK

---

arc: 0043
title: Extending the Puzzle to a Full SNARK
authors: @howardwu
discussion: #77
topic: Protocol
status: Draft
created: October 15, 2024

Abstract

This ARC proposes extending the current blockchain puzzle from a synthesis-focused operation to a full Succinct Non-interactive Argument of Knowledge (SNARK). The primary goals are to incentivize the acceleration of a full SNARK on dedicated hardware and improve block verification times through succinct puzzle verification. This proposal aims to mitigate bottlenecks in the block verification pipeline caused by synthesis operations, and to leverage recent advancements in GPU and FPGA acceleration to improve the puzzle challenge for provers.

Background

SNARK generation has seen significant performance improvements over the past several years, in part due to efforts such as the Aleo Testnets and ZPrize. While proof generation was initially bottlenecked by algorithms such as Multi-Scalar Multiplication (MSM) and Number Theoretic Transform (NTT), these algorithms have been accelerated significantly, resulting in synthesis becoming the most time consuming operation. With recent improvements to synthesis resulting from the launch of the Aleo Mainnet, there is now an opportunity to further optimize the end-to-end proving and verifying process.

Proposal

This proposal extends the current puzzle to a full SNARK with the following key changes:

1. Increase the number of instructions in the puzzle
2. Expand the types of instructions and operands
3. Implement a zkSNARK for verification

1. Increased Instruction Count

The current puzzle has an artificially constrained number of instructions due to limitations in consensus verification. By implementing a full SNARK, one can expand the instruction count by orders of magnitude. This will significantly harden the puzzle for provers, expanding the utility of dedicated hardware and improving on current computational requirements for proving.

2. Expanded Instruction Set

Introducing a zkSNARK for verification allows for the inclusion of richer opcodes with larger operands. This expansion of the instruction set will increase the complexity and versatility of the puzzle challenge. However, careful consideration must be given to instruction selection to avoid degeneracy of operands (e.g., operands becoming 0 and propagating through the remainder of the function).

3. zkSNARK Verification

Implementing a zkSNARK for verification will enable succinct puzzle proof verification. This will improve block verification times, enhancing overall network performance.

Technical Considerations

1. The extension will be built on the existing proof system and elliptic curve to minimize technical risk and debt in snarkOS and snarkVM.
2. The existing synthesizer is capable of expanding both the number and types of instructions in the Varuna SNARK.
3. To maintain non-malleability and non-amortizability, the puzzle will be extended to a SNARK, not a zkSNARK. This is crucial to prevent grindability on a single proof, which would simplify the problem for provers.

Benefits

1. Incentivizes the development and use of dedicated hardware for full SNARK acceleration.
2. Significantly improves block verification times through succinct puzzle verification.
3. Enhances puzzle complexity and security by allowing for a much larger instruction set.
4. Leverages recent advancements in GPU and FPGA acceleration for synthesis operations.

Risks and Mitigations

Risk: Increased complexity in puzzle design and verification.
Mitigation: Thorough testing and gradual implementation, with potential for a phased rollout.

Risk: Potential for new attack vectors due to expanded instruction set.
Mitigation: Rigorous security analysis & audits, alongside careful selection of new instructions.

Risk: Increased hardware requirements for miners/provers.
Mitigation: Phased implementation to allow for gradual hardware upgrades.

Conclusion

Extending the current puzzle to a full SNARK incentivizes a significant advancement for proving hardware. It addresses current bottlenecks for consensus, improves overall network performance, and incentivizes hardware acceleration for cryptographic operations. The next step is to gather community feedback to refine and improve this proposal.

[apruden2008]

Thanks. I am supportive in principle of expanding the scope of the puzzle in order to make it more “useful”.

What are the implications of this change on the economics? In other words, are there any changes expected in the puzzle difficulty adjustment algorithm that would potentially affect the inflation rate of ALEO?

[mingo6666666666]

May I ask when the algorithm upgrade is expected to start?

[howardwu]

This ARC is currently a proposal in draft stage. As discussions and design proposals mature, this ARC will converge on a concrete design that can be implemented, analyzed, and reviewed.

[zkxuerb]

I think this is the right direction both for incentivising the improvement of dedicated hardware for cryptographic operations and very importantly improving network performance.

Do we have an idea on what the current impact of puzzle verification is to network consensus as a bottleneck ( in terms of time to verify ) ?

[vicsn]

Do we have an idea on what the current impact of puzzle verification is to network consensus as a bottleneck ( in terms of time to verify ) ?

Because of the high verification requirements (0.5 GiB memory, takes 100s of ms), MAX_SOLUTIONS per block is set to only 4 at the moment to ensure solutions don't slow down consensus. If the puzzle was replaced by a full snark, this limitation could be removed, as verification of a Transmission::Solution would be as fast to verify as an (execution) Transmission::Transaction.

[Ryan-MetaworksLab]

Hi, we are Metaworks Lab from Australia. We are keen to contribute to Aleo and hope to work with the community to participate in the improvement and implementation of the ARC0043 proposal.

We work with the ZK hardware accelerator team to do software and hardware co-design. We have the ability to support ARC43 and can also do general ZK accelerator. We can do:

1. Increase the number of instructions in the puzzle, expand the types of instructions and operands
   • We can implement operation instructions and data types that are compatible with the CPU and GPU versions, and can run efficiently in parallel
2. Generate zkSNARK proofs for puzzles
   • After executing the R1CS of the puzzle, use the generated Constraints to generate the prove of KZG Polynomial Commitments, where MSM is accelerated by CUDA
   • Later, FPGA and ASIC dedicated to Aleo puzzle solving can be provided
3. zkSNARK verification of puzzles
   • Verify the verify of KZG Polynomial Commitments, MSM is accelerated on the CPU using the Pippenger algorithm

We are Metaworks Lab from Australia, with 8 full-time ZKP R&D personnel in Shanghai. We have been actively participating in the testnet and mainnet mining of the Aleo project, with strong computing power support and optimized mining algorithms.

[LoiusZK]

Hi, as a loyal fan of Aleo, I have a few questions to ask:

1. How much will the TPS be improved after the implementation of this PR? Do you have internal test data?
2. If the block time is stabilized at about 10 seconds, can the daily transactions volume reach tens of millions?
3. Will the block capacity or transaction capacity affect TPS?
4. How long will it take to implement this PR? Is there a time plan and arrangement?

The current TPS is indeed very bad and needs to be solved urgently, otherwise the ecosystem cannot develop. Thanks.

[howardwu]

@LoiusZK The most straightforward way to increasing TPS is by introducing more validators into the network. This ARC is likely to have little impact on TPS, as consensus currently verifies at most 4 valid puzzle solutions per block, each at around 100-200ms. This ARC would likely reduce the amount of time needed, but could also enable more puzzle solutions to be submitted in each block, allowing for more provers to earn rewards.

[LoiusZK]

@howardwu If simply increase the number of validators based on the current instruction set puzzle algorithm, won’t the block time also increase? Cause we know the final calculation result of the current instruction set puzzle algorithm is not a Proof, so the validators need to execute it individually to verify, and cannot execute Proof verification in batches, which will also affect TPS. I think this ARC should also be a preparation for adding more validators in the future right?
According to what you said, the maximum number of solutions will increase to more than 4 for per block, which is of great concern to the provers, but I am more concerned about the original intention of proposing this ARC, that is, and the original intention of optimizing and updating the puzzle algorithm in the future. My understanding is that the current and future optimization of the puzzle algorithm is to accelerate zkvm and improve TPS. In fact, for Aleo, the biggest difficulty is to take into account the output of PoW+PoS in line with the expected planning of the economic model, while ensuring that there is a high enough TPS to support the development of a large-scale ecosystem.

[d0cd]

While all three improvements to the puzzle are desirable, it appears that Goal #3: implementing a SNARK for verification is the most important. Without it, increasing the instruction count and complexity would only increase the solution verification time. In these benchmarks, we find that a puzzle program with 1000 instructions results in a solution that takes ~500ms to verify. Ideally, we'd like to increase instruction count well beyond this number. With succinct solution verification, we can increase program complexity in meaningful (and virtually unbounded) ways.

An added benefit is that the protocol can support a larger number of solutions per block, allowing rewards to be distributed to more provers.

One open question is: how do validators synthesize the verifying key? Furthermore, how do clients, which may have lower compute resources get this key? Solutions are verified live during consensus. Furthermore, the puzzle program changes every epoch. Even for small programs, the overall circuit can contain millions of constraints. Synthesizing verifying keys in these settings can take a significant amount of time. A naive design is to require validators to synthesize the key at the beginning of the epoch, however this could result in a verification delay.

A possible solution is introduce a buffer during which a validator can synthesize the key. For example, the puzzle program can be generated using the previous epoch hash, while the seed for the puzzle inputs can use the current epoch hash. Validators are then responsible for storing and distributing verification keys to clients.

Curious to hear what people think and other approaches to consider!

[howardwu]

Thanks for the thoughts @d0cd. Do you see any possibility of having a pipelined design, whereby provers have 1 full epoch to synthesize the verifying key and get it to all validators, then 1 full epoch to find solutions for the puzzle? By pipelining these two stages, one can have a continuous puzzle and verifying key synthesis procedure.

[c00567056]

When will the algorithm upgrade be completed? Can you give a plan?

[howardwu]

This ARC is currently a proposal in draft stage. As discussions and design proposals mature, this ARC will converge on a concrete design that can be implemented, analyzed, and reviewed.

[c00567056]

thank you very much!