"Check-Before-you-Solve": Verifiable Time-lock Puzzles

"Check-Before-you-Solve": Verifiable Time-lock Puzzles

Speakers: Jiajun Xin; Dimitrios Papadopoulos

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=rYU_R7pgDUQ

Overview

In the realm of modern cryptography and decentralized systems, time-lock puzzles (TLPs) have emerged as a foundational primitive, enabling a variety of applications from secure auctions to blockchain front-running resistance. These puzzles are designed such that generating them is computationally easy, but solving them requires a predetermined, sequential computational effort, often denoted as t steps. This inherent asymmetry ensures that a solution can only be revealed after a specified time delay, regardless of parallel processing power. However, a critical vulnerability arises from this very property: there is no inherent mechanism to verify the legitimacy or content of a time-lock puzzle before expending the significant computational resources required to solve it. An attacker could exploit this by generating arbitrary, meaningless puzzles and falsely claiming they contain valuable information, thereby wasting the computational power of solvers.

This presentation by Jiajun Xin and his advisor Dimitrios Papadopoulos from Hong Kong introduces Verifiable Time-lock Puzzles (VTLPs), a novel cryptographic construction designed to address this fundamental trust deficit. Their work provides a robust framework for proving the validity and content of a time-lock puzzle without requiring its full solution, effectively enabling a "check-before-you-solve" paradigm. This innovation is crucial for applications where trust cannot wait for a solution to be computed, ensuring that every delay is meaningful and every computational effort is justified.

The significance of VTLPs extends across numerous domains, particularly in blockchain technology, where issues like front-running and transaction ordering remain pressing concerns. By allowing users to encode transactions within verifiable time-lock puzzles, the system can ensure that the hidden information is legitimate and relevant before any solver commits resources. The research not only formalizes the definition of VTLPs with new properties like stunkness, zero-knowledge, and synchroness but also provides highly efficient constructions, drastically reducing the computational overhead compared to previous methods.

Background

▶ Watch: Introduction to Time-lock Puzzles and the Trust Problem (0:00)

Time-lock puzzles (TLPs), first introduced by Rivest, Shamir, and Wagner (RSW) in 1996, are cryptographic primitives designed to encapsulate a secret that can only be revealed after a specified amount of sequential computation. The core principle is asymmetry: puzzle generation is computationally trivial, while solving requires t sequential computational steps. This delay mechanism has found applications in various fields, including:

• Timed Transactions for Blockchains: To mitigate front-running attacks, users can submit transactions encoded in a TLP, which can only be opened after a certain block height or time.
• Payment Channel Networks: Protocols like Hashed Time-lock Contracts (HTLCs) rely on time-lock techniques to ensure atomic swaps and secure state transitions.
• Sealed-Bid Auctions: A classic application where bids are submitted as TLPs, and only after a set time can they be opened and revealed.

The security of many TLPs, particularly the RSW construction, hinges on the hardness of factoring large numbers and the sequential squaring assumption. The RSW puzzle typically involves computing s + α^(2^t) mod N, where N is a large RSA modulus, s is the secret, and α is a random number. The puzzle generator uses trapdoor information (the factorization of N) to compute this efficiently. A solver, lacking the trapdoor, must perform t sequential modular squarings to arrive at the solution.

However, the inherent asymmetry of TLPs introduces a critical vulnerability. As highlighted in the talk, an attacker can exploit this property by generating a random puzzle and falsely claiming it contains, for instance, a valid transaction. This wastes the computational resources of anyone attempting to solve it. In scenarios like blockchain front-running, users might encode their transactions in TLPs to hide information until a later reveal. But if there's no way to verify the puzzle's legitimacy beforehand, an attacker could still waste network resources or even submit malicious, unverifiable puzzles. The problem is that "solving takes time, but trust cannot wait." Solvers need confirmation that their efforts are not wasted before committing to the t sequential steps.

Current approaches to address transaction revealing in blockchains often involve:

1. Public Transactions: The default for most blockchains, making them susceptible to front-running and Miner Extractable Value (MEV) attacks.
2. Commitment Schemes: Users commit to transactions and reveal them later. However, attackers can selectively reveal their commitments, still enabling front-running.
3. TLP Encoding: Encoding transactions in TLPs offers a promising path, but as discussed, it's only viable if there's a proof to validate the TLP before solving.

The challenge lies in efficiently validating the complex relationship within a TLP, such as Z = S + α^(2^t) mod N, where S is the hash of a valid, signed transaction. Directly checking such a relation within a Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (SNARK) circuit is extremely inefficient. For example, using a Groth16 system, validating this relation requires approximately 72 million constraints and takes around 5 minutes to prove. This computational burden makes direct SNARK verification impractical for most real-world applications, especially in high-throughput decentralized systems. This bottleneck underscores the urgent need for a more efficient method to verify TLPs without solving them.

Key Findings

▶ Watch: RSW Time-lock Puzzle and SNARK validation challenges (3:20)

The research presented by Xin and Papadopoulos introduces several groundbreaking contributions to the field of verifiable computation and cryptographic primitives:

1. Formal Definition of Verifiable Time-lock Puzzles (VTLPs): The authors provide the first formal definition of VTLPs, extending the properties of traditional TLPs to include verifiability. This definition incorporates new, crucial properties:

• Stunkness: Ensures that only valid puzzles can be proven.
• Zero-Knowledge: Guarantees that the proof reveals no information about the hidden solution S beyond its validity.
• Synchroness: Relates the time required to solve the puzzle to the actual wall-clock time, ensuring the intended delay.

1. Efficient VTLP Construction via SNARK Offloading: A primary contribution is a highly efficient construction for VTLPs based on a novel SNARK offloading technique. This method dramatically reduces the computational cost of proving the validity of a TLP. The prover time for their VTLP construction is 140 times faster than directly checking the TLP inside a SNARK, reducing proof generation from over 300 seconds to just 2 seconds. This efficiency makes VTLPs practical for real-world applications.

1. Direct Application to Timed Transactions and Verifiable Time-lock Signatures: The VTLP construction directly addresses the front-running problem in blockchains by enabling efficient verifiable timed transactions. Furthermore, it facilitates the creation of efficient verifiable time-lock signatures, where the verification time can be reduced from 40 seconds to a mere 1 millisecond. This improvement opens avenues for secure and efficient delayed revelation of signed messages.

1. Efficient RSA Signature Offloading Technique: As a significant byproduct of their VTLP construction, the researchers developed an extremely efficient technique for offloading RSA signature verification into SNARKs. This technique requires only 800 constraints for an RSA signature verification, a stark contrast to systems like Mimic hash, which uses 350 constraints just for hashing, or native field EdDSA signatures (also known as "baby jubjub"), which can require around 7 million constraints for 1,000 signatures. Their method is even faster than native field EdDSA for batched signature verifications inside a SNARK, making it highly valuable for privacy-preserving and verifiable computation applications involving RSA.

1. VTLP for RSA Signatures and Verifiable Random Functions (VRFs) without SNARKs: Beyond SNARK-based constructions, the work also provides an efficient VTLP for RSA signatures and Verifiable Random Functions (VRFs) that does not rely on SNARKs. This alternative construction is particularly suitable for applications requiring reliable distributed randomness generation, offering flexibility and potentially lower overhead in specific use cases where a full SNARK might be overkill or impractical.

These findings collectively represent a substantial leap forward in verifiable computation, providing practical, efficient, and provably secure methods for ensuring the integrity of time-locked information.

Technical Deep Dive

▶ Watch: Overview of paper's contributions and performance gains (4:41)

The core innovation behind the efficient VTLP construction lies in a sophisticated SNARK offloading technique for modular exponentiation, specifically targeting the verification of expressions like alpha^x mod N. Directly verifying such an exponentiation in a SNARK circuit is notoriously expensive due to the sequential nature of modular arithmetic and the large numbers involved (e.g., N being 2048 bits). The authors' approach simplifies this complex problem into a form that SNARKs can handle much more efficiently.

The problem, as simplified for SNARK offloading, is to check α^x mod N where α and N are public, and x is a private exponent with a bit length of N around 2048. The solution leverages two key observations:

Observation 1: Binary Decomposition of the Exponent

The first observation is to represent the exponent x in its binary form. If x can be written as x = x_k 2^k + x_{k-1} 2^{k-1} + ... + x_1 2^1 + x_0 2^0, where x_i are binary bits (0 or 1), then α^x mod N can be rewritten as:

α^x mod N = α^(x_k 2^k + ... + x_0 2^0) mod N

= (α^(2^k))^(x_k) (α^(2^(k-1)))^(x_{k-1}) ... * (α^(2^0))^(x_0) mod N

This transforms a single large exponentiation into a modular product of terms. Each term (α^(2^i))^(x_i) is either α^(2^i) (if x_i = 1) or 1 (if x_i = 0). The powers α^(2^i) mod N can be precomputed outside the SNARK circuit. The SNARK then only needs to verify the correct selection and modular product of these precomputed terms based on the private bits x_i. This significantly reduces the complexity within the SNARK because modular exponentiation is reduced to a series of modular multiplications.

Observation 2: Offloading Product Checking with Proof of Knowledge of Double Exponent

The second, more intricate observation addresses the efficient verification of this modular product within the SNARK. Checking the product of integers, especially when these integers are results of modular exponentiations, can still be burdensome. The authors propose offloading this product checking using a specialized cryptographic primitive: a proof of knowledge of a double exponent in a hidden odd group.

This technique involves constructing a proof that a prover knows the value of x such that g^x = Y (where g and Y are elements in a group) without revealing x. When applied to modular exponentiation verification, this allows the SNARK to verify the correctness of the modular product without performing all the expensive modular multiplications itself. Previous protocols for this type of proof often suffered from proof sizes and verification times that were linear with the security parameter, specifically the bit length of the exponent. The innovation here is that their protocol achieves constant proof size and verification time.

This "proof of knowledge of double exponent in a hidden odd group" essentially acts as a compact certificate that the modular product computation was performed correctly according to the binary representation of x. By offloading this part, the SNARK circuit is drastically simplified. Instead of embedding a full modular exponentiation or even a complex modular product chain, it verifies a much smaller, constant-sized proof generated by this specialized protocol. This is the mechanism that allows for the 140x speedup in prover time, as the SNARK's work is reduced to verifying a succinct proof rather than executing the entire computation.

Furthermore, this modular exponentiation offloading technique has a direct impact on the efficiency of RSA signature verification within SNARKs. An RSA signature verification involves checking s^e = m mod N (or m = s^d mod N), which is fundamentally a modular exponentiation. By applying their offloading technique, they achieve an RSA signature verification that requires only 800 constraints. This is remarkably efficient compared to other SNARK-friendly signature schemes like native field EdDSA (baby jubjub), which, while generally faster in native environments, can require millions of constraints for batched verification inside a SNARK (e.g., 7 million constraints for 1,000 EdDSA signatures). This offloading makes RSA signatures a viable and, in some SNARK contexts, superior alternative for verifiable computation.

In essence, the technical deep dive reveals a clever decomposition of a complex cryptographic operation (modular exponentiation) into simpler components, followed by an innovative offloading mechanism that leverages specialized proofs to drastically reduce the burden on the SNARK, leading to unprecedented efficiency gains for VTLPs and related primitives.

Demo / Proof of Concept

▶ Watch: Experimental results: Demonstrating significant speed-ups (7:01)

The practical viability of the proposed Verifiable Time-lock Puzzles and related cryptographic primitives was demonstrated through comprehensive experimental results. The experiments were conducted on a standard laptop equipped with eight CPU cores and 16 GB of memory, utilizing the Groth16 (G16) SNARK system by Garg for their SNARK-based constructions. These specifications represent a typical developer or research environment, highlighting the accessibility and practicality of their solution.

The key performance metrics and improvements showcased during the presentation include:

1. Verifiable Time-lock Puzzles (VTLPs):

• The most significant result for VTLPs was a 140-fold acceleration in prover time compared to directly embedding and checking time-lock puzzles within a SNARK circuit.
• This translates into a reduction of proof generation time from more than 300 seconds (5 minutes) to a mere 2 seconds. This dramatic speedup is critical for real-world applications where rapid proof generation is essential, such as in blockchain transaction processing or real-time verifiable computation.

1. SNARK Offloaded RSA Signatures:

• The efficiency of their offloaded RSA signature verification technique was also impressive. It was shown to be approximately 1.5 to 6 times faster than verifying native field EdDSA signatures (also known as "baby jubjub") when performed inside a SNARK.
• For verifying 1,000 RSA signatures, their method required only 1.3 million constraints, a substantial improvement over the 7 million constraints typically needed for 1,000 EdDSA signatures within a SNARK. This demonstrates that for certain SNARK applications, particularly those involving batch verification, RSA signatures, when optimized with their offloading technique, can outperform schemes often considered more "SNARK-friendly."

These experimental results provide strong evidence that the proposed SNARK offloading techniques are not merely theoretical improvements but yield tangible and significant performance benefits. The ability to generate proofs for VTLPs in seconds rather than minutes fundamentally changes the landscape for secure, verifiable delayed computation. The efficiency gains for RSA signature verification within SNARKs also open new possibilities for privacy-preserving applications that rely on established cryptographic standards.

The speakers also highlighted that the open-source code and benchmarks are available, encouraging further research and adoption of their techniques. This commitment to transparency and reproducibility reinforces the validity and potential impact of their work.

Defensive Implications

▶ Watch: Conclusion and key takeaways of the research (8:16)

The introduction of Verifiable Time-lock Puzzles (VTLPs) and the associated SNARK offloading techniques carries profound implications for defensive strategies across various cybersecurity domains, particularly in decentralized systems and verifiable computation. The ability to "check before you solve" fundamentally enhances trust, efficiency, and security.

1. Mitigating Front-Running and MEV in Blockchains:

• Verifiable Timed Transactions: The primary application highlighted is the resistance against front-running attacks in blockchains. Users can now encode their transactions within VTLPs. Before a validator or miner expends resources to solve the puzzle, they can efficiently verify that the puzzle indeed contains a valid, signed transaction. This prevents attackers from submitting dummy puzzles to waste resources or from selectively revealing commitments to gain an unfair advantage. It ensures that transaction ordering can be managed more fairly and transparently.
• Reduced Resource Waste: By enabling pre-verification, the system avoids wasting computational power on solving invalid or malicious puzzles. This translates to more efficient network operation and higher resilience against denial-of-service attempts that leverage TLP vulnerabilities.

1. Enhanced Security for Payment Channel Networks and HTLCs:

• While Hashed Time-lock Contracts (HTLCs) are already a cornerstone of payment channels, VTLPs could potentially introduce an extra layer of verifiability. Although not explicitly detailed for HTLCs in the talk, the general principle of verifying the contents of a time-lock before commitment could lead to more robust and auditable channel operations, potentially reducing certain classes of attack vectors or disputes.

1. Secure and Fair Sealed-Bid Auctions:

• In classic sealed-bid auctions, participants submit bids that are revealed only after the auction closes. Using VTLPs, bidders can prove that their submitted puzzle contains a valid bid (e.g., within a certain range, signed by them) without revealing the bid amount itself. This prevents participants from submitting invalid bids or using the system for other malicious purposes, ensuring the integrity and fairness of the auction process.

1. Efficient Verifiable Computation and Privacy-Preserving Systems:

• SNARK Offloaded RSA Signatures: The efficient RSA signature offloading technique is a powerful tool for privacy-preserving applications. Many enterprise and legacy systems rely on RSA signatures. The ability to verify these signatures efficiently within SNARKs enables the construction of systems where sensitive data can be processed and verified without revealing the underlying information. For example, proving eligibility for a service based on an RSA-signed credential without revealing the credential itself.
• Batched Verification: The significant reduction in constraints for batched RSA signature verification makes it practical to verify large sets of digital signatures within a SNARK, which is crucial for scalable, privacy-preserving identity systems, verifiable credentials, or auditable logs.

1. Reliable Distributed Randomness Generation:

• The non-SNARK VTLP construction for RSA signatures and Verifiable Random Functions (VRFs) offers a robust mechanism for generating reliable distributed randomness. This is vital for applications requiring unbiased and unpredictable outcomes, such as leader election in decentralized protocols, lotteries, or secure parameter generation in cryptographic systems. By ensuring the verifiability of the VRF output, the system can prevent manipulation and ensure fairness.

In summary, VTLPs provide a critical missing piece in the puzzle of secure and efficient verifiable computation. By enabling proactive validation of time-locked information, they empower defenders to build more resilient, transparent, and fair decentralized systems, effectively closing a significant trust gap in existing cryptographic paradigms.

Key Takeaways

• Verifiable Time-lock Puzzles (VTLPs) are essential for trust: Traditional time-lock puzzles lack a mechanism to verify their content before solving, leading to potential resource waste and attack vectors like front-running. VTLPs introduce this crucial verifiability.
• Novel VTLP Definition and Properties: The research provides the first formal definition of VTLPs, incorporating new properties of stunkness, zero-knowledge, and synchroness to ensure validity, privacy, and time-bound reliability.
• SNARK Offloading Achieves Dramatic Efficiency: A sophisticated SNARK offloading technique for modular exponentiation drastically reduces the computational cost of VTLP verification. This innovation achieves a 140 times faster prover time, cutting proof generation from over 300 seconds to just 2 seconds.
• Practical for Blockchain Front-Running Resistance: VTLPs directly address the problem of front-running in blockchains by allowing transactions to be hidden in verifiable puzzles, ensuring their legitimacy before commitment and preventing malicious resource expenditure.
• Efficient RSA Signature Verification in SNARKs: As a significant byproduct, the work introduces an incredibly efficient RSA signature offloading technique for SNARKs, requiring only 800 constraints and outperforming native field EdDSA signatures (baby jubjub) in SNARK contexts, especially for batched verification.
• Supports Diverse Applications: Beyond timed transactions, VTLPs and their underlying techniques enable efficient verifiable time-lock signatures, reliable distributed randomness generation (even without SNARKs), and generally enhance the security and efficiency of verifiable computation across various decentralized applications.

About the Speaker(s)

The talk "Check-Before-you-Solve": Verifiable Time-lock Puzzles was presented by Jiajun Xin. He collaborated on this work with his advisor, Dimitrios Papadopoulos. Both speakers are affiliated with an institution in Hong Kong. Beyond their names and affiliation, specific professional titles or detailed biographical information were not provided within the transcript. Their research focuses on cryptographic primitives, verifiable computation, and their applications in areas like blockchain technology.