Fiat-Shamir Transform

Now let's put all the pieces together.

In practice, we often want a non-interactive proof system so that we can compute the proofs at one point in time on a given machine, and check them later when needed. To achieve this, we use the Fiat-Shamir transformation, where we assume a hash function behaves as a random oracle. The idea is that the prover himself can generate "unbiased" challenges based on the messages he would send to the verifier in an interactive version of the protocol by using a hash function. See for instance the following two functions that operate over a string that we will call a "transcript".

The first function $\mathsf{\text{push}}$ adds values to the transcript (field elements, curve elements) by using delimiters to separate them. The $\mathsf{\text{generate\_challenge}}$ function will hash a given transcript and create an element in $\mathbb{F}$ from the hash.

import hashlib

def push(v, transcript, delim="|"):
    return transcript + delim + str(v)


def generate_challenge(transcript):
    # Encode the transcript string into bytes for the hash function
    transcript_bytes = transcript.encode('utf-8')
    
    # Compute the SHA256 hash and get its hexadecimal representation
    sha256_hash = hashlib.sha256(transcript_bytes).hexdigest()
    
    # Convert the hexadecimal hash string to an integer
    hash_int = int(sha256_hash, 16)
    
    # Cast the integer into an element of our finite field F
    return F(hash_int)

#Examples

transcript = ""
print(f"Initial transcript: '{transcript}'")

# Push a number and an elliptic curve point to the transcript
transcript = push(12345, transcript)
transcript = push(kzg.P, transcript)
print(f"Updated transcript: '{transcript}'")

# # Generate a challenge from the transcript
challenge = generate_challenge(transcript)
print(f"Generated challenge: {challenge}")

Step 1

We start with an empty transcript and add the initial values $a(\omega )$ and $b(\omega )$ which should be $0$ and $1$ to the transcript, as well as the output $c({\omega }^4)$ which should be 9. We also add commitments to the blinded polynomials $a\mathrm{\_}blind,b\mathrm{\_}blind,c\mathrm{\_}blind$.

Exercise 19

Push the values discussed above in order to the empty transcript. Also compute proofs for the openings of $a,b,c$ corresponding to the inputs and output. Proofs are not added to the transcript.

transcript = ""
#Solve here!
value_a = #?
value_b = #?
value_c = #?
c_a = #?
c_b = #?
c_c = #?
proof_value_a       = 
proof_value_b       = 
proof_output  =