DEEP-FRI Algebraic Hash

deep-fri.sage

e = 128
E.<X> = GF(2^e)           # E = GF(2^e)
P.<Y> = PolynomialRing(E) # P = GF(2^e)[Y]
F = E.base_ring()         # F = GF(2)
V = VectorSpace(F, e)     # V = (GF(2))^e

# isomorphism \phi : E -> V
def to_vector(elem):
    assert elem in E
    coeff = map(F, '{:b}'.format(elem.integer_representation())[::-1])
    coeff = coeff + [F(0)] * (V.dimension() - len(coeff))
    return V(coeff)

# isomorphism \phi^{-1} : V -> E
def from_vector(vec):
    assert vec in V
    return sum([X^i * c for (i, c) in enumerate(vec)])

# initial subspace L0
def subspace(dim):
    return V.subspace(
        map(to_vector, [X^i for i in range(dim)])
    )

# dimension one subspace
def subspace1(L):
    return V.subspace([L.an_element()])

# construct the subspace polynomial
def subspace_polynomial(L0):
    return prod([(Y - from_vector(v)) for v in L0])

# find the 2 distinct preimages of a dimension 1 subspace polynomial
def preimages(q, s):
    return tuple((q - s).roots(multiplicities = False))

# this is the polynomial written by the prover during COMMIT of DEEP-FRI
def B(s, q, f):
    s0, s1 = preimages(q, s)
    return P.lagrange_polynomial([
        (s0, f(s0)),
        (s1, f(s1))
    ])

# returns a function which computes H_x[f] at any point
def Hp(q, f, x):
    return lambda s: B(s, q, f)(x)

# Calculate the full polynomial for H_x[f].
# This implementation is clearly very niave:
#   In a "real implemenation" there should
#   be no reason to covert from the Lagrange to monomial basis
def H(q, f, x):
    h = Hp(q, f, x)
    p = []
    for i, e in enumerate(E):
        p.append((e, h(e)))
        if i > f.degree() / 2: # deg f / 2 + 1 points
            break
    return P.lagrange_polynomial(p)

# initial evaluation domain
L_0  = subspace(16)
L0_0 = subspace1(L_0)
q0   = subspace_polynomial(L0_0)

L_1 = map(from_vector, L_0.basis())
L_1 = map(q0, L_1)
L_1 = map(to_vector, L_1)
L_1 = V.subspace(L_1)

print('hash')

s = X^43 + X^7 + 1
x = X^32 + X^12 + X^86

f = Y^10 + Y^3 + 1

print H(q0, f, x)

def qoutient(f, z, b):
    return f - b / (Y - z)