Skip to content
This repository has been archived by the owner on Jul 1, 2021. It is now read-only.

[Eth2.0] Modular_squareroot issue due to upstream Py-ECC bug #233

Closed
mratsim opened this issue Jan 28, 2019 · 0 comments
Closed

[Eth2.0] Modular_squareroot issue due to upstream Py-ECC bug #233

mratsim opened this issue Jan 28, 2019 · 0 comments
Labels

Comments

@mratsim
Copy link

mratsim commented Jan 28, 2019

What is wrong?

FYI due to ethereum/py_ecc#47 with impact details in ethereum/consensus-specs#508, the modular squareroot returned does not always match the one expected by the Eth2.0 spec.

def modular_squareroot(value: FQ2) -> FQP:
"""
``modular_squareroot(x)`` returns the value ``y`` such that ``y**2 % q == x``,
and None if this is not possible. In cases where there are two solutions,
the value with higher imaginary component is favored;
if both solutions have equal imaginary component the value with higher real
component is favored.
"""
candidate_squareroot = value ** ((FQ2_order + 8) // 16)
check = candidate_squareroot ** 2 / value
if check in eighth_roots_of_unity[::2]:
x1 = candidate_squareroot / eighth_roots_of_unity[eighth_roots_of_unity.index(check) // 2]
x2 = FQ2([-x1.coeffs[0], -x1.coeffs[1]]) # x2 = -x1
return x1 if (x1.coeffs[1], x1.coeffs[0]) > (x2.coeffs[1], x2.coeffs[0]) else x2
return None

How can it be fixed

Wait for upstream fix for ethereum/py_ecc#47

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
Projects
None yet
Development

No branches or pull requests

2 participants