inkfish/proof_pietrzak.py
def generate_proof(x, T, delta, y, powers, identity,
                   generate_r_value, int_size_bits):
    """
    Generate the proof.
    Returns a list of elements derived by operations on x.
    """
    # Only even values work, since we need to do T/2
    if T % 2 != 0:
        raise ValueError("T must be even")
    i = approximate_i(T)
    mus = []
    rs = []    # random values generated using hash function
    x_p = [x]  # x prime in the paper
    y_p = [y]  # y prime in the paper

    curr_T = T
    Ts = []    # List of all of the Ts being used, T, then T/2, etc

    final_T = calculate_final_T(T, delta)

    round_index = 0
    while curr_T != final_T:
        assert(curr_T & 1 == 0)
        half_T = curr_T >> 1
        Ts.append(half_T)
        denominator = 1 << (round_index + 1)  # T/2 for initial round

        # use cache for first i rounds for fast computation
        if (round_index < i):
            mu = identity  # Compute product below

            # Get each of the cached terms, for round 3, denominator is 8.
            # The terms are T/8, 3T/8 5T/8 7T/8. If not a power of two, we
            # will not use exactly 3T/8
            for numerator in range(1, denominator, 2):
                # Number of bits in the denominator, for example 3
                # Don't include last r, since not computed yet
                num_bits = denominator.bit_length() - 2

                # Find out which rs to multiply for this term, based on bit
                # composition. For example, for 5T/8, 5 is 101 in bits, so
                # multiply r1 (but not r2)
                rs_to_mult = [
                        1 if numerator & (1 << (b + 1))
                        else rs[num_bits - b - 1]
                        for b in range(num_bits-1, -1, -1)]

                # Multiply rs together
                r_prod = 1
                for r in rs_to_mult:
                    r_prod *= r

                # Calculates the exact cached power T to use
                Ts_to_add = [
                    Ts[num_bits - b - 1] if numerator & (1 << (b + 1)) else 0
                    for b in range(num_bits)]

                T_sum = half_T
                for t in Ts_to_add:
                    T_sum += t

                mu_component = powers[T_sum]

                mu = mu * pow(mu_component, r_prod)
            mus.append(mu)
        else:
            # Compute for rounds i + 1 until the end, for low cache storage
            mu = x_p[-1]
            for _ in range(half_T):
                mu = pow(mu, 2)

            mus.append(mu)

        rs.append(generate_r_value(x, y, mus[-1], int_size_bits))
        x_p.append(pow(x_p[-1], rs[-1]) * mu)
        y_p.append(pow(mu, rs[-1]) * y_p[-1])

        # Compute the new T, and y. If T is odd, make it even, and adjust
        # the y_p accordingly, so that y_p = x_p ^ (2 ^ curr_T)
        curr_T = curr_T >> 1
        if curr_T & 1 == 1:
            curr_T += 1
            y_p[-1] = pow(y_p[-1], 2)
        round_index += 1

    assert(pow(y_p[-1], 1) == pow(x_p[-1], 1 << final_T))
    return mus

    Generate the proof.
    Returns a list of elements derived by operations on x.
    
Generate the proof.
Returns a list of elements derived by operations on x.
Generate the proof . Returns a list of elements derived by operations on x .
def generate_proof(x, T, delta, y, powers, identity,
                   generate_r_value, int_size_bits):
    if T % 2 != 0:
        raise ValueError("T must be even")
    i = approximate_i(T)
    mus = []
    rs = []    
    x_p = [x]  
    y_p = [y]  
    curr_T = T
    Ts = []    
    final_T = calculate_final_T(T, delta)
    round_index = 0
    while curr_T != final_T:
        assert(curr_T & 1 == 0)
        half_T = curr_T >> 1
        Ts.append(half_T)
        denominator = 1 << (round_index + 1)  
        if (round_index < i):
            mu = identity  
            for numerator in range(1, denominator, 2):
                num_bits = denominator.bit_length() - 2
                rs_to_mult = [
                        1 if numerator & (1 << (b + 1))
                        else rs[num_bits - b - 1]
                        for b in range(num_bits-1, -1, -1)]
                r_prod = 1
                for r in rs_to_mult:
                    r_prod *= r
                Ts_to_add = [
                    Ts[num_bits - b - 1] if numerator & (1 << (b + 1)) else 0
                    for b in range(num_bits)]
                T_sum = half_T
                for t in Ts_to_add:
                    T_sum += t
                mu_component = powers[T_sum]
                mu = mu * pow(mu_component, r_prod)
            mus.append(mu)
        else:
            mu = x_p[-1]
            for _ in range(half_T):
                mu = pow(mu, 2)
            mus.append(mu)
        rs.append(generate_r_value(x, y, mus[-1], int_size_bits))
        x_p.append(pow(x_p[-1], rs[-1]) * mu)
        y_p.append(pow(mu, rs[-1]) * y_p[-1])
        curr_T = curr_T >> 1
        if curr_T & 1 == 1:
            curr_T += 1
            y_p[-1] = pow(y_p[-1], 2)
        round_index += 1
    assert(pow(y_p[-1], 1) == pow(x_p[-1], 1 << final_T))
    return mus
def generate_proof ( x , T , delta , y , powers , identity , generate_r_value , int_size_bits ) : if T % 2 != 0 : raise ValueError ( "T must be even" ) i = approximate_i ( T ) mus = [ ] rs = [ ] x_p = [ x ] y_p = [ y ] curr_T = T Ts = [ ] final_T = calculate_final_T ( T , delta ) round_index = 0 while curr_T != final_T : assert ( curr_T & 1 == 0 ) half_T = curr_T >> 1 Ts . append ( half_T ) denominator = 1 << ( round_index + 1 ) if ( round_index < i ) : mu = identity for numerator in range ( 1 , denominator , 2 ) : num_bits = denominator . bit_length ( ) - 2 rs_to_mult = [ 1 if numerator & ( 1 << ( b + 1 ) ) else rs [ num_bits - b - 1 ] for b in range ( num_bits - 1 , - 1 , - 1 ) ] r_prod = 1 for r in rs_to_mult : r_prod *= r Ts_to_add = [ Ts [ num_bits - b - 1 ] if numerator & ( 1 << ( b + 1 ) ) else 0 for b in range ( num_bits ) ] T_sum = half_T for t in Ts_to_add : T_sum += t mu_component = powers [ T_sum ] mu = mu * pow ( mu_component , r_prod ) mus . append ( mu ) else : mu = x_p [ - 1 ] for _ in range ( half_T ) : mu = pow ( mu , 2 ) mus . append ( mu ) rs . append ( generate_r_value ( x , y , mus [ - 1 ] , int_size_bits ) ) x_p . append ( pow ( x_p [ - 1 ] , rs [ - 1 ] ) * mu ) y_p . append ( pow ( mu , rs [ - 1 ] ) * y_p [ - 1 ] ) curr_T = curr_T >> 1 if curr_T & 1 == 1 : curr_T += 1 y_p [ - 1 ] = pow ( y_p [ - 1 ] , 2 ) round_index += 1 assert ( pow ( y_p [ - 1 ] , 1 ) == pow ( x_p [ - 1 ] , 1 << final_T ) ) return mus
Generate the proof.
Generate the proof .
"""
    Generate the proof.
    Returns a list of elements derived by operations on x.
    """ # Only even values work, since we need to do T/2 # random values generated using hash function # x prime in the paper # y prime in the paper # List of all of the Ts being used, T, then T/2, etc # T/2 for initial round # use cache for first i rounds for fast computation # Compute product below # Get each of the cached terms, for round 3, denominator is 8. # The terms are T/8, 3T/8 5T/8 7T/8. If not a power of two, we # will not use exactly 3T/8 # Number of bits in the denominator, for example 3 # Don't include last r, since not computed yet # Find out which rs to multiply for this term, based on bit # composition. For example, for 5T/8, 5 is 101 in bits, so # multiply r1 (but not r2) # Multiply rs together # Calculates the exact cached power T to use # Compute for rounds i + 1 until the end, for low cache storage # Compute the new T, and y. If T is odd, make it even, and adjust # the y_p accordingly, so that y_p = x_p ^ (2 ^ curr_T)
x
T
delta
y
powers
identity
generate_r_value
int_size_bits