Proof Of Elapsed Time

User computes VDF and submits on-chain.

import hashlib
import time

class VerifiableDelayFunction:
    def __init__(self, x, C, T_target):
        """
        Initialize the VDF parameters.
        
        :param x: Initial input value for the VDF function (string).
        :param C: Random challenge issued (string).
        :param T_target: Target time in seconds for the VDF computation (float).
        """
        self.x = x
        self.C = C
        self.T_target = T_target
        self.T_prime = self.calibrate_steps()

    def hash_function(self, input_value):
        """
        Compute SHA-256 hash of the input value.
        
        :param input_value: Input value to hash (string).
        :return: Hexadecimal hash digest (string).
        """
        return hashlib.sha256(input_value.encode()).hexdigest()

    def calibrate_steps(self):
        """
        Calibrate the number of sequential steps (T') to approximate T_target time.
        
        :return: Number of sequential steps T' (int).
        """
        test_iterations = 1000
        start_time = time.time()
        
        # Perform a test run of 1000 hash computations
        v = self.hash_function(self.x + self.C)
        for _ in range(test_iterations):
            v = self.hash_function(v)

        end_time = time.time()
        time_per_hash = (end_time - start_time) / test_iterations
        
        # Calculate T' based on the target time and average time per hash
        T_prime = int(self.T_target / time_per_hash)
        print(f"Calibrated T' to {T_prime} steps for target time {self.T_target} seconds.")
        return T_prime

    def compute_sequence(self):
        """
        Perform the sequential hash computations to obtain the final value (timestamp).
        :return: The final value v_T' (string), and a list of intermediate values (list).
        """
        v = self.hash_function(self.x + self.C)
        sequence = [v]

        # Perform T' sequential steps
        for _ in range(1, self.T_prime):
            v = self.hash_function(v)
            sequence.append(v)

        v_T_prime = sequence[-1]
        return v_T_prime, sequence

    def prove(self):
        """
        Generate the proof by computing the final value and selected intermediate values.
        :return: Proof containing the final value v_T' and selected checkpoints (dict).
        """
        v_T_prime, sequence = self.compute_sequence()
        
        # Select checkpoints for verification (e.g., every 10% of T')
        checkpoints = {}
        step_interval = max(1, self.T_prime // 10)
        for i in range(0, self.T_prime, step_interval):
            checkpoints[i] = sequence[i]

        proof = {
            "v_T_prime": v_T_prime,
            "checkpoints": checkpoints
        }
        return proof

    def verify(self, proof):
        """
        Verify the proof by recomputing the sequence up to the final value.
        :param proof: The proof containing v_T' and checkpoints (dict).
        :return: Boolean indicating whether the proof is valid (bool).
        """
        v_T_prime = proof["v_T_prime"]
        checkpoints = proof["checkpoints"]

        # Recompute the sequence and verify checkpoints
        v = self.hash_function(self.x + self.C)
        for i in range(1, self.T_prime):
            v = self.hash_function(v)

            # Check against the provided checkpoints
            if i in checkpoints and checkpoints[i] != v:
                print(f"Verification failed at step {i}.")
                return False

        # Check the final value
        if v != v_T_prime:
            print("Final value does not match the proof.")
            return False

        print("Proof successfully verified.")
        return True


# Example usage
if __name__ == "__main__":
    # Parameters
    x = "example_input_value"
    C = "random_challenge_string"
    T_target = 5.0  # Target time in seconds

    # Initialize VDF
    vdf = VerifiableDelayFunction(x, C, T_target)

    # Generate proof
    proof = vdf.prove()
    print("Proof generated:", proof)

    # Verify proof
    is_valid = vdf.verify(proof)
    print("Verification result:", is_valid)

The provided Python script implements a Verifiable Delay Function (VDF), which is a cryptographic construct designed to prove that a certain amount of computation has taken place within a specific time frame. In this implementation, the VDF computes a cryptographic result (a mathematical timestamp) based on a sequential process, ensuring that the computation cannot be sped up through parallelization, and the amount of time spent can be verified.
The script consists of a class VerifiableDelayFunction, which contains methods for:
1. Calibrating the number of sequential steps required to meet the target time.
2. Computing the sequential hash chain that produces the final timestamp.
3. Generating a proof that includes the final result and intermediate values.
4. Verifying the proof to ensure that the computation was correctly performed and completed in the specified time.
Detailed Breakdown of the Code
1. Class Initialization (__init__):
- Purpose: Initializes the Verifiable Delay Function (VDF) with the input parameters.
- Parameters:
  - x: The initial value (string) used as the input for the VDF function.
  - C: A random challenge string that is used in the hash computations to ensure unpredictability.
  - T_target: The target time (in seconds) for how long the computation should take.
- Action: The class computes the number of sequential steps (T') necessary for the computation to approximately take the target time (T_target). This is done by the calibrate_steps() method.
2. Hash Function (hash_function):
- Purpose: Computes the SHA-256 hash of an input value.
- Input: A string (input_value).
- Output: The SHA-256 hash of the input value, returned as a hexadecimal string.
- Importance: The hash function is crucial for the sequential computation chain. It ensures that each step depends on the previous step, which makes it impossible to skip or parallelize the computation.
3. Calibrating Steps (calibrate_steps):
- Purpose: Determines the number of sequential steps (T') needed to approximate the target time (T_target).
- Method:
  1. The method first runs a test to calculate the average time it takes to compute a single hash.
  2. The script runs 1000 hash computations to measure the time taken for each hash and calculates the average time per hash.
  3. The number of sequential steps (T') is then calibrated so that the total time spent on T' steps is approximately equal to T_target.
- Output: Returns the calibrated number of steps T'.
4. Compute Sequence (compute_sequence):
- Purpose: Performs the sequential computation to generate the final value (the mathematical timestamp).
- Method:
  1. The computation starts with the hash of the initial input x concatenated with the challenge C (i.e., v_0 = hash(x || C)).
  2. The script then performs T' sequential hash computations, where each step’s result depends on the previous one (i.e., v_i = hash(v_{i-1})).
  3. The final value v_T' is the output of the last step in the sequence.
- Output: The final computed value v_T' and the full sequence of intermediate values.
5. Proof Generation (prove):
- Purpose: Generates a proof that includes the final computed value (v_T') and selected intermediate values from the computation.
- Method:
  1. After computing the sequence, the method selects some checkpoints (intermediate values) from the sequence at regular intervals (e.g., every 10% of the total steps).
  2. The proof includes the final value v_T' and the selected checkpoints. These checkpoints allow the verifier to efficiently check the validity of the computation.
- Output: A dictionary containing the final value v_T' and the intermediate checkpoint values.
6. Proof Verification (verify):
- Purpose: Verifies that the proof provided by the prover is valid and that the computation was performed correctly.
- Method:
  1. The verifier starts by recomputing the sequence from the beginning, just as the prover did.
  2. It checks if the recomputed values at the checkpoints match the values provided in the proof.
  3. The verifier also checks if the final value v_T' matches the value in the proof.
  4. If any discrepancies are found (e.g., if a checkpoint value doesn’t match or the final value doesn’t match), the proof is considered invalid.
- Output: A Boolean indicating whether the proof is valid (True if valid, False otherwise).
Example Usage:
In the __main__ section, an instance of the VerifiableDelayFunction class is created with the following parameters:
- x = "example_input_value": The initial input string for the VDF.
- C = "random_challenge_string": A random challenge string.
- T_target = 5.0: The target time for the computation (5 seconds).
The prove() method is called to generate the proof, and then the verify() method is called to validate the proof.
Summary of What the Script Does:
- The script implements a VDF that performs a sequential computation using SHA-256 hashes. This computation is calibrated to take approximately a given amount of time (T_target).
- The prover generates a proof consisting of the final computed value and intermediate values, which can be verified by an independent party.
- The proof demonstrates that the prover has performed the computation within the specified time (T_target) and has followed the correct sequence of computations.
- The verification process checks that the prover has correctly followed the sequence and that no steps were skipped, effectively ensuring that the computation is both time-bound and verifiable.
Use Case:
This script is useful for scenarios where you need to prove that a certain amount of computation has taken place within a specific time period, such as:
- Proving that a specific amount of work has been done without relying on traditional timestamps or external clocks.
- Cryptographic applications requiring verifiable delay to prevent fraud or fast computation shortcuts.

PreviousOverview NextVDF Reserve Ratio

Last updated 8 months ago

Detailed Breakdown of the Code

Example Usage:

Summary of What the Script Does:

Use Case: