🌟SPARC

Sight AI team proposed SPARC to solve the verifiable FHE problem

SPARC is in its early stages of research. Progress updates are provided regularly. For more information, please contact the team for details on ongoing efforts.

Introduction

SPARC (Structure-Preserved Arguments for Computing) is a cryptographic proof system tailored to verify the correctness of computations performed by untrusted servers. While it shares the foundational framework of STARK (Scalable Transparent Arguments of Knowledge), SPARC distinguishes itself by optimizing proofs for specific computational problems rather than general NP (non-deterministic polynomial time) problems.

Framework and Optimization of SPARC

The original STARK framework operates through three primary steps:

1. Convert Computational Problems: Transform the computational problems into arithmetic intermediate representations (AIR) and generate an interactive oracle proof (IOP) for the AIR.

2. Compress the IOP: Utilize cryptographic compilers like Merkle commitments to compress the IOP into a succinct (interactive) proof.

3. Non-Interactive Conversion: Convert the proof system into a non-interactive one via the Fiat-Shamir transform.

SPARC diverges in the initial step by creating a representation tailored to the underlying structure of the specific problem, especially in scenarios involving Fully Homomorphic Encryption (FHE) circuits. This focus on leveraging the inherent structure of FHE circuits significantly reduces unnecessary overhead, making SPARC more efficient for these specialized computations.

Key Features of SPARC

• Scalability, Transparency, and Post-Quantum Security: SPARC inherits these robust features from STARKs, ensuring it remains secure and efficient even against quantum adversaries.

• Reduced Overhead: By targeting specific computational problems and utilizing their structural properties, SPARC minimizes overhead compared to traditional zk-SNARKs designed for general NP problems.

Technique Details

• Ring-PCP/IOP: Probabilistic Checkable Proofs (PCPs) or Interactive Oracle Proofs (IOPs) are fundamental components in all zk-SNARK protocols. These are information-theoretical proofs that do not rely on any cryptographic assumptions. In standard zk-SNARKs, PCPs/IOPs are constructed over finite fields, such as the AIR used in STARK. However, FHE circuits operate on rings or modules, typically based on ring-LWE. This mismatch introduces significant overhead when applying standard zk-SNARKs to FHE circuits. In SPARC, we design ring-PCPs/IOPs, where the intermediate representation is built on the rings used by FHE.

• Efficient Cryptographic Hash Functions: Cryptographic hash functions are crucial components in STARK approaches. On top of ring-PCPs/IOPs, cryptographic compilers convert the PCP/IOP proofs into non-interactive and succinct proofs. Popular cryptographic compilers, like Merkle commitments and the Fiat-Shamir transform, have been proven secure in the random oracle model. In constructing STARKs, it is essential to instantiate the random oracle with a cryptographic hash function, which will be executed many times. The key difference is that STARKs use a general hash function for all problems, while in SPARC, we can exploit the structure of the proof system to design cryptographic hash functions that are both efficient and provably secure.

Updates

We started posting our updated research findings on SPARC in June 2024. Please refer to the subpage for our most recent works.