Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Fused modular square root on 32-bit - wrong "isSquare" result #43

Closed
mratsim opened this issue Jun 8, 2020 · 1 comment · Fixed by #58
Closed

Fused modular square root on 32-bit - wrong "isSquare" result #43

mratsim opened this issue Jun 8, 2020 · 1 comment · Fixed by #58
Labels
bug 🪲 Something isn't working has repro 🎯

Comments

@mratsim
Copy link
Owner

mratsim commented Jun 8, 2020

Reproduced locally in 32-bit mode (might not be related to 32-bit as the RNG will initialize differently)

test_ec_weierstrass_projective_g1 xoshiro512** seed: 1591646170

[Suite] Elliptic curve in Short Weierstrass form y² = x³ + a x + b with projective coordinates (X, Y, Z): Y²Z = X³ + aXZ² + bZ³ i.e. X = xZ, Y = yZ
  [OK] The infinity point is the neutral element w.r.t. to EC addition
  [OK] Adding opposites gives an infinity point
  [OK] EC add is commutative
  [OK] EC add is associative
    /home/beta/Programming/Nim/constantine/tests/test_ec_weierstrass_projective_g1.nim(170, 19): Check failed: bool(r0 == r1)
  [FAILED] EC double and EC add are consistent
  [OK] EC mul [0]P == Inf
  [OK] EC mul [Order]P == Inf
  [OK] EC mul [1]P == P
  [OK] EC mul [2]P == P.double()
  [OK] EC mul is distributive over EC add
  [OK] EC mul constant-time is equivalent to a simple double-and-add algorithm
Error: execution of an external program failed: '/home/beta/Programming/Nim/constantine/build/test_ec_weierstrass_projective_g1 '

test "EC double and EC add are consistent":
proc test(F: typedesc, randZ: static bool) =
for _ in 0 ..< Iters:
when randZ:
let a = rng.random_unsafe_with_randZ(ECP_SWei_Proj[F])
else:
let a = rng.random_unsafe(ECP_SWei_Proj[F])
var r0{.noInit.}, r1{.noInit.}: ECP_SWei_Proj[F]
r0.double(a)
r1.sum(a, a)
check: bool(r0 == r1)
test(Fp[BN254_Snarks], randZ = false)
test(Fp[BN254_Snarks], randZ = true)
test(Fp[BLS12_381], randZ = false)
test(Fp[BLS12_381], randZ = true)

@mratsim mratsim added the bug 🪲 Something isn't working label Jun 8, 2020
@mratsim mratsim added the heisenbug 🐈 This bug seems random label Jun 18, 2020
@mratsim
Copy link
Owner Author

mratsim commented Jun 19, 2020

Similar to #30 and #43 another square root bug:

import
  # Standard library
  std/[unittest, times],
  # Internals
  ../constantine/config/[common, curves],
  ../constantine/arithmetic,
  ../constantine/io/[io_bigints, io_fields],
  ../constantine/elliptic/[ec_weierstrass_affine, ec_weierstrass_projective]

proc trySetFromCoordX_debug*[F](P: var ECP_SWei_Proj[F], x: F): SecretBool =
  ## Try to create a point the elliptic curve
  ## y² = x³ + a x + b     (affine coordinate)
  ##
  ## The `Z` coordinates is set to 1
  ##
  ## return true and update `P` if `x` leads to a valid point
  ## return false otherwise, in that case `P` is undefined.
  ##
  ## Note: Dedicated robust procedures for hashing-to-curve
  ##       will be provided, this is intended for testing purposes.
  P.y.curve_eq_rhs(x)
  # TODO: supports non p ≡ 3 (mod 4) modulus like BLS12-377

  echo "P.y: ", P.y.toHex()
  echo "P.y.isSquare: ", bool P.y.isSquare
  result = sqrt_if_square_p3mod4(P.y)
  echo "P.y.wasSquare: ", bool result
  P.x = x
  P.z.setOne()

var a: ECP_SWei_Proj[Fp[BLS12_381]]

var x: Fp[BLS12_381]
x.fromHex("0x1494859e30da25337d020ccf8629c81df7ddab3185acee7a5712c47e2192bc71d6bf74db134d3c7f7f21e43b59242ff3")

let ok = a.trySetFromCoordX_debug(x)

echo "ok: ", bool ok
echo "a.x: ", a.x.toHex()
echo "a.y: ", a.y.toHex()

doAssert bool isOnCurve(a.x, a.y)

var r0{.noInit.}, r1{.noInit.}: ECP_SWei_Proj[Fp[BLS12_381]]

r0.double(a)
r1.sum(a, a)

doAssert bool(r0 == r1)
P.y: 0x0f16d7854229d8804bcadd889f70411d6a482bde840d238033bf868e89558d39d52f9df60b2d745e02584375f16c34a3
P.y.isSquare: false
P.y.wasSquare: true
ok: true
a.x: 0x1494859e30da25337d020ccf8629c81df7ddab3185acee7a5712c47e2192bc71d6bf74db134d3c7f7f21e43b59242ff3
a.y: 0x0aad1bf39cd801cc5b917b70205bac4706e330eb8b5bac50967780f9db6025149b60fe93402bdea86f4b403807d3f4ea
...../Programming/Nim/constantine/build/debug_double_add.nim(43) debug_double_add
...../.choosenim/toolchains/nim-#devel/lib/system/assertions.nim(29) failedAssertImpl
...../.choosenim/toolchains/nim-#devel/lib/system/assertions.nim(22) raiseAssert
...../.choosenim/toolchains/nim-#devel/lib/system/fatal.nim(49) sysFatal
Error: unhandled exception: /home/beta/Programming/Nim/constantine/build/debug_double_add.nim(43, 10) `bool isOnCurve(a.x, a.y)`  [AssertionDefect]

@mratsim mratsim changed the title EC add / EC double inconsistency Fused modular square root on 32-bit - wrong "isSquare" result Jun 19, 2020
mratsim added a commit that referenced this issue Jun 20, 2020
@mratsim mratsim removed the heisenbug 🐈 This bug seems random label Jun 20, 2020
mratsim added a commit that referenced this issue Jun 20, 2020
mratsim added a commit that referenced this issue Jun 22, 2020
mratsim added a commit that referenced this issue Jun 22, 2020
mratsim added a commit that referenced this issue Jun 22, 2020
@mratsim mratsim linked a pull request Jun 22, 2020 that will close this issue
2 tasks
mratsim added a commit that referenced this issue Jun 22, 2020
* Add test case for #30 - Euler's criterion doesn't return 1 for a square

* Detect #42 in the test suite

* Detect #43 in the test suite

* comment in sqrt tests

* Add #67 to the anti-regression suite

* Add #61 to the anti-regression suite

* Add #62 to anti-regression suite

* Add #60 to the anti-regression suite

* Add #64 to the test suite

* Add #65 - case 1

* Add #65 case 2

* Add #65 case 3

* Add debug check to isSquare/Euler's Criterion/Legendre Symbol

* Make sure our primitives are correct

* For now deactivate montySquare CIOS fix #61 #62

* Narrow down #42 and #43 to powinv on 32-bit

* Detect #42 #43 at the fast squaring level

* More #42, #43 tests, Use multiplication instead of squaring as a temporary workaround, see #68

* Prevent regression of #67 now that squaring is "fixed"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug 🪲 Something isn't working has repro 🎯
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant