# Problem set 1: Range proofs to polynomials
# Reading https://vitalik.ca/general/2017/11/09/starks_part_1.html

# Prove that you know the millionth Fibonacci number ?

# TODO: Create a list containing the first 10 Fibonacci numbers

x = [1,1]

def fib(x):
    for i in range(2,8):
        x.append(x[i-2]+x[i-1])
    return(x)

x = fib(x)

print(x[-1])

# TODO simulate an evil genius, simulate an attacker able to switch a singel bit durin gthe computation and see what the final result is ? Is it different ?

x_evil = [0,1]
print(fib(x_evil)[-1])

# TODO: Range proof check: Check that a list of numbers are all between in the range 0 , 9. This is basically means make a for look that does > < checks ;) no proofs needed.

x = [1,2,3,4,5,6,7,8,9]

for i in x: 
    assert(i > 0 and i < 10)

## TODO: Make a function that evaluates a polynomial in coefficient format. For example x*2 + 2 + 3 is [3, 2, 1]

def eval(coeffs, x):
    out = 0 
    for i, coeff in enumerate(coeffs):
        out += (coeff * (x**i))
    return(out)

assert ( eval([3,2,1] , 1) == 6)

## TODO: Find the coefficeint form of a polynomial that is `0 for x in [1,2,3,4,5,6,7,8,9]` this polynomial is called `c(x)`

## TODO: Change your range checker function to use evaluations of this polynomial

## TODO: FInd the coeffieients o the polynomial p(x) where the first 1 million values are in the range (0, 9)

## TODO: Change your range checker function to use evaluation fo P(x) as well as c(x)

## TODO: Calculate Z(x) the polynomail that any polynomail that equals 0 for all x from 1 to 1,000,000 is a multiple of Z(x)

## TODO: Calulate D(x) this is the polynomial that c(P(x)) / Z(x) = D(x)

## TODO: Make a merkle tree of the first 1 million evalusastions of C(x) , P(x) , D(x) , Z(x)

## TODO: use Fiat shamir transform to generate a randome number.

## TODO: Open all polynomials at the random point r

## TODO: Verify the equation C(P(x) == Z(x) D(x) at this point.

## TODO: Which of of the polynoials are are prover key ? Which are our verificaion key and which are the ones the prover must produce ?

## TODO Implement a proof of the 1 millionth Fibonachi number

## TODO Create an attack that breaks this proof ? ;) We will fix that after our next learning group on Fri :D:D:D