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
HackMD
