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

Workaround for compile-time modulus and negInvModWord #16

Closed
mratsim opened this issue Mar 15, 2020 · 1 comment
Closed

Workaround for compile-time modulus and negInvModWord #16

mratsim opened this issue Mar 15, 2020 · 1 comment

Comments

@mratsim
Copy link
Owner

mratsim commented Mar 15, 2020

Due to upstream bug nim-lang/Nim#9679 and another hard-to reproduce one for static Word, the use of compile-time property of the modulus requires lots of workarounds.

Bug 2 gives the following errors:

========================================================================================
Running tests/test_io_fields
========================================================================================
/home/beta/Programming/Nim/constantine/tests/test_io_fields.nim(19, 9) template/generic instantiation of `suite` from here
/home/beta/Programming/Nim/constantine/tests/test_io_fields.nim(20, 10) template/generic instantiation of `test` from here
/home/beta/Programming/Nim/constantine/tests/test_io_fields.nim(26, 10) template/generic instantiation of `fromUint` from here
/home/beta/Programming/Nim/constantine/constantine/io/io_fields.nim(29, 6) template/generic instantiation of `fromBig` from here
/home/beta/Programming/Nim/constantine/constantine/arithmetic/finite_fields.nim(64, 11) Error: type mismatch: got <BigInt[61], BigInt[61], BigInt[61], BigInt[61], static[Word](2305843009213693953)>
but expected one of: 
func montyResidue(mres: var BigInt; a, N, r2modN: BigInt; negInvModWord: static Word)
  first type mismatch at position: 5
  required type for negInvModWord: static[Word]
  but expression '2305843009213693953' is of type: static[Word](2305843009213693953)

Trying to reduce it to a minimal example makes it disappear ...

import macros

type Word = distinct uint64
const WordBitSize = 63

func wordsRequired*(bits: int): int {.compileTime.} =
  (bits + WordBitSize - 1) div WordBitSize

type
  BigInt*[bits: static int] = object
    bitLength: uint32
    limbs: array[bits.wordsRequired, Word]

  Curve = enum
    BN254
    BLS12_381

const CurveBitSize = [
  BN254: 254,
  BLS12_381: 381
]

template matchingBigInt(C: static Curve): untyped =
  # Need template indirection to avoid a sigmatch bug
  BigInt[CurveBitSize[C]]

type
  FiniteField*[C: static enum] = object
    big: matchingBigInt(C)

const BN254_Modulus = BigInt[254]()
const BN254_NegInvModWord = Word(2305843009213693953)

{.experimental: "dynamicBindSym".}

macro getModulus(C: static Curve): untyped =
  result = bindSym($C & "_Modulus")

macro getNegInvModWord(C: static Curve): untyped =
  result = bindSym($C & "_NegInvModWord")

func foo(mres: var BigInt, a, N: BigInt, negInvModWord: static Word) =
  discard

func bar(r: var FiniteField, a: FiniteField) =
  foo(r.big, a.big, a.C.getModulus(), a.C.getNegInvModWord())

var r: FiniteField[BN254]
let a = FiniteField[BN254]()

bar(r, a)
@mratsim
Copy link
Owner Author

mratsim commented Mar 21, 2020

Closing, even if it's fixed upstream, we are not trying to write a generic all-purpose finite field libraries.

Only supporting preconfigured moduli as like today is enough.

@mratsim mratsim closed this as completed Mar 21, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant