IETF hash to g2

[mratsim]

This a WIP implementing the new hashToG2 primitive according to the IETF draft spec.

• IETF Standard Draft: https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-04
  • Formatted HTML version: https://cfrg.github.io/draft-irtf-cfrg-hash-to-curve/draft-irtf-cfrg-hash-to-curve.html
• IETF Implementation: https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve
  • The following can be used as a test vector generator: https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/blob/6cf7fa97/poc/suite_bls12381g2.sage
• Ethereum Foundation implementation: https://github.com/ethereum/py_ecc
  • Specific PR: https://github.com/ethereum/py_ecc/pull/83/files

Currently, the implementation is incorrect and need heavy debugging. Unfortunately I'm lacking some test vectors. Py-ECC code doesn't follow the spec for the implementations but reference papers. The code from MCL is at the moment incomplete: https://github.com/herumi/mcl/commit/8ec855f162f97f64b1bab9838068b1425ad0d39a, there is no vectors. Alternative implementations are also missing vectors: https://github.com/kwantam/bls12-381_hash/tree/master/src / https://github.com/kwantam/bls_sigs_ref / https://github.com/algorand/bls_sigs_ref

Dropping Milagro

If we want to drop Milagro, this is a good time.

Alternative 1 - Herumi's MCL / BLS

This would be a battery included library, supported by the EF. Note that in our context (ARM devices within a MIT/Apache codebase) the major speed bonuses probably won't apply:

• Cannot use GMP
• Cannot use the JIT Assembler Xbyak

The main draw is that we only have to wrap.

Alternative 2 - Using Riad S. Wahby C implementation

Riad is the one of the co-lead for the IETF draft specification and has a constant-time C implementation at https://github.com/kwantam/bls12-381_hash (Apache v2 License).

Edit: I didn't see that it's using GMP :/

Switching cost

Using Riad's code will require reimplementing signature aggregation and proof-of-possession on top of their primitives: https://tools.ietf.org/html/draft-irtf-cfrg-bls-signature-00#section-2.7

I think this is also true for Milagro, unless the aggregation/PoP scheme is the same as 0.9.x

Other blockchains

With @arnetheduck nbindgen we can reuse Zcash pairing library: https://github.com/zkcrypto/pairing. (Apache v2 + MIT License)

However the code by Zcash (https://github.com/zkcrypto/pairing) implements neither hash_to_curve nor aggregation/Proof-of-Possessions at the moment and such development doesn't seem to have started.

Alternatively there is a Go/C/C++ port by the University of Berkeley at https://github.com/ucbrise/jedi-pairing (BSD-3-Clause license) but same problem.

The code by Dfinity is using MCL: https://github.com/dfinity-side-projects/random-beacon

The code by Chia is using outdated hashToG2 and aggregates/PoP like us: https://github.com/Chia-Network/bls-signatures

Not dropping Milagro

Not dropping Milagro means fixing this PR, which may be quite involved.

1. For example, assuming FP2 an extension field of characteristic P (prime) of order 2:

   • FP2 elements are complex big integers in the form A + iB (mod P),
   • the spec requires (A + iB) div (C + iD) (mod P) in multiple places
   • Milagro doesn't provide a modular complex bigint division, so right now it's implemented by multiplying by the multiplicative inverse (mod P), which may or may not be OK.
   • If that is an issue that might require implementing complex bigint division.

2. The draft implementation accompanying the spec requires Python 2 to run: https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/issues/199. It would however help to produce intermediate test-vectors to narrow-down what components are creating errors.

3. Py-ECC can be edited to output intermediate results: https://github.com/mratsim/py_ecc/commit/d09c42c73c73f0a24d0498568eb061b1eac16ab0, this requires some playing around the G2 points representation: Jacobian (x, y, z) coordinates or Affine (x, y) / x + iy coordinates. We can output to both format but the input will require some extra code as there is no builtin Milagro functions.

4. At the moment it is unknown if our aggregation scheme is conforming to the new IETF spec.

---

Thoughts?

[mratsim]

Good news, I have found a partial Rust Milagro-based implementation of the hash_to_curve.

In particular it implements and tests the second part "mapToCurveG2" which is the part that I couldn't find proper test vectors for. The first part hashToBaseFP2 is correct up until the conversion to FP2. I didn't check the FP2 conversion yet due to Milagro defaulting to affine coordinates while Py-ECC defaulting to jacobian coordinates.

The bad news is that somehow just converting from hex to FP2 gives different results between milagro C and milagro Rust

https://github.com/sigp/incubator-milagro-crypto-rust/blob/4956346708710dd8045de2191de3b2ce3be5e965/src/bls381.rs#L297-L302 The conversion goes like this:

Hex -> BigInt -> FP (i.e. bigint mod P) -> FP2. The conversion from BigInt to FP is called nres and for Milagro C it leaves the bigint unchanged but on the Rust side it's mysteriously changed. Complete mystery at the moment.

[mratsim]

The "naive" clearCofactor clearing method in https://github.com/status-im/nim-blscurve/pull/30/commits/35c7773b624b915028db870f4faa5f8fad51301b wasn't working.

Fortunately, instead of having to implement the complex "psi" function and "addition_chains" from this code: https://github.com/kwantam/bls12-381_hash/blob/23c1930039f58606138459557677668fabc8ce39/src/curve2/ops2.c#L106-L204, the original fast clear cofactor method was actually implemented in Milagro at https://github.com/status-im/nim-blscurve/blob/cae83b3a45df51e9fccd8a0ed921a45c2d2fa93f/blscurve/csources/64/ecp2_BLS381.c#L681-L709

Concretely, after https://github.com/status-im/nim-blscurve/pull/30/commits/7fc31e02413d2db808a4facb57bdfe306a321a70 all components of the new hashToG2 are:

• implemented
• in constant-time for anything that manipulate secret data
• using the recommended fast constant-time implementation from the IETF spec and Wahby and Boneh paper: Fast and simple constant-time hashingto the BLS12-381 elliptic curve

The components seem to pass "debugecho" test vectors for:

• hash_to_base (map seq[byte] to (FP2, FP2) via HKDF)
• isogeny_map_swu (map (FP2, FP2) to P', point of isogenous curve E'2)
• iso_map_to_G2 (map P' to P, point of E2 of BLS12-381)
• clearCofactor (map P to the subgroup G2 of E2)

So the remaining TODOs for the PR are adding a test suite and maybe add a compile-time switch between old/new hashToG2.

Ideally in another PR, I will replace the add/mul/sub operation by +, +=, *, *=, -, -= to improve code readability.

[arnetheduck]

replace the add/mul/sub

would it have the same semantics though? ie raise on overflow and all that? if not, perhaps better keep the spelled out names?

[mratsim]

There is no overflow on modular arithmetic

[mratsim]

We are passing 1 vector end-to-end vector from PyECC, given the nature of the cryptographic beast, I expect the implementation is correct.

TODO:

• The new test vectors are expected by end of day according to yesterday's implementer call and can then replace "case01" and "case02": https://github.com/status-im/nim-blscurve/blob/cae83b3a45df51e9fccd8a0ed921a45c2d2fa93f/tests/test_vectors.nim#L203-L227
• I'm pretty sure we crash or do bad things on empty strings/message
• The spec requires appending a '\0' byte before HKDF for cryptographic reasons (not C-compat). As an optimization, I rely on Nim strings being always terminated by '\0'. This means that we need distinct string and openarray[byte] interfaces. The openarray one will reallocate the input in a larger buffer that can accomodate the terminating '\0', the string one will handle empty strings.

[mratsim]

For some reason the following test is working on Windows 64bit, Linux 32bit and not Windows 32bit: https://github.com/status-im/nim-blscurve/blob/39a37ba979d6390d32c6742a2c230073de23c101/blscurve/hash_to_curve.nim#L531-L555

Could it be a calling convention issue?

Stack traces

• https://dev.azure.com/nimbus-dev/nim-blscurve/_build/results?buildId=1467&view=logs&j=6cac9158-38e5-53c4-2402-3f3c0d2abb77&t=0b881912-f73b-5df2-49f2-827c2be866e5&l=57
• https://ci.appveyor.com/project/nimbus/nim-milagro-crypto/builds/30576537/job/rs0v2y2wfkrugjjd#L80

  Success hashToBaseFP2 msg_ctr0
  Success hashToBaseFP2 msg_ctr1
  d:\a\1\s\blscurve\hash_to_curve.nim(558) hash_to_curve
  d:\a\1\s\blscurve\hash_to_curve.nim(542) test_MilagroRust_1
  d:\a\1\s\blscurve\hash_to_curve.nim(342) mapToCurveG2
  d:\a\1\s\blscurve\hash_to_curve.nim(326) isogeny_map_G2
  D:\a\1\s\NimBinaries\nim-stable\lib\system\assertions.nim(27) failedAssertImpl
  D:\a\1\s\NimBinaries\nim-stable\lib\system\assertions.nim(20) raiseAssert
  D:\a\1\s\NimBinaries\nim-stable\lib\system\fatal.nim(39) sysFatal
  Error: unhandled exception: d:\a\1\s\blscurve\hash_to_curve.nim(326, 10) `onCurve`  [AssertionError]
  Error: execution of an external program failed: 'd:\a\1\s\build\hash_to_curve.exe '
  stack trace: (most recent call last)
  C:\Users\VSSADM~1\AppData\Local\Temp\nimblecache\nimscriptapi.nim(165, 16)
  d:\a\1\s\blscurve_2200.nims(27, 8) testTask
  d:\a\1\s\blscurve_2200.nims(21, 8) test
  D:\a\1\s\NimBinaries\nim-stable\lib\system\nimscript.nim(252, 7) exec
  D:\a\1\s\NimBinaries\nim-stable\lib\system\nimscript.nim(252, 7) Error: unhandled exception: FAILED: nim c --outdir:build -r --hints:off --warnings:off blscurve/hash_to_curve.nim [OSError]
     Tip: 1 messages have been suppressed, use --verbose to show them.
   Error: Exception raised during nimble script execution

Failure is in isogeny_map_G2 last line: https://github.com/status-im/nim-blscurve/blob/39a37ba979d6390d32c6742a2c230073de23c101/blscurve/hash_to_curve.nim#L215-L326

Expected stacktrace (from Linux 32-bit)

https://dev.azure.com/nimbus-dev/nim-blscurve/_build/results?buildId=1467&view=logs&j=feb88f62-8c3b-59ff-0076-513faf7289e9&t=9457d589-49b9-57d2-0dd7-867fec436873&l=52

Success hashToBaseFP2 msg_ctr0
Success hashToBaseFP2 msg_ctr1
-------------------------------------------
Point P (before clearCofactor):
([059c2a965ad0883a784e8812329a872c46e804cd3b7dc1e2df0d33b72819f6a501e2649b9b71f1b242c42e9bf6e52637, 17c71d3ae5f9f848eac924f8564291b7542fc247434995e288ac58ac27cf995a15fb56879593798f1351bbf2e954f9ac], [0fa4f19f6e4d83ee6c0bf366cb22dd780dca8656e2459e0297da20b916ecd71bd4c545eead3fcb53c8256ab83b82ba9c, 07809c47b0f93f92aec66b7c2ce73888cb957cff52e52028a308440df8c2ebe870fdb87b5abe72b0cd8d0b39b2eac56f])
-------------------------------------------
Point P (after clearCofactor):
In jacobian projective coordinates (x, y, z)
([04861c41efcc5fc56e62273692b48da25d950d2a0aaffb34eff80e8dbdc2d41ca38555ceb8554368436aea47d16056b5, 09db5217528c55d982cf05fc54242bdcd25f1ebb73372e00e16d8e0f19dc3aeabdeef2d42d693405a04c37d60961526a], [177d05b95e7879a7ddbd83c15114b5a4e9846fde72b2263072dc9e60db548ccbadaacb92cc4952d4f47425fe3c5e0172, 0fc82c99b928ed9df12a74f9215c3df8ae1e9a3fa54c00897889296890b23a0edcbb9653f9170bf715f882b35c0b4647], [000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001, 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000])
In affine coordinate (x, y)
([04861c41efcc5fc56e62273692b48da25d950d2a0aaffb34eff80e8dbdc2d41ca38555ceb8554368436aea47d16056b5, 09db5217528c55d982cf05fc54242bdcd25f1ebb73372e00e16d8e0f19dc3aeabdeef2d42d693405a04c37d60961526a], [177d05b95e7879a7ddbd83c15114b5a4e9846fde72b2263072dc9e60db548ccbadaacb92cc4952d4f47425fe3c5e0172, 0fc82c99b928ed9df12a74f9215c3df8ae1e9a3fa54c00897889296890b23a0edcbb9653f9170bf715f882b35c0b4647])
Success mapToCurveG2 MilagroRust_1
-------------------------------------------
Point P (before clearCofactor):
In jacobian projective coordinates (x, y, z)
([066ba76b52e102065bd2173e3c5782a2ba5f39626127e0b22407cdf5dd48c4e5517fc1777ff947104577f2434983519a, 17b5251c7d5078e7d38b1dd8c984c920e7ac92fc2eb1a48cda87817737cd17856ffe010fc302c6f83802e2708c3f6eee], [16a350d7eee6792adef46b36161cc454858657727bde6dc6fb5718590d46f1605748ca7d3da5a766c8a3c585ce373d27, 06cfa60de97d8dc411adaa34b64d9651635d98d6868c23f2a78564fa64ffe527667270af01c3da26b6cd313ca37adf7b], [102e03b2e75f4752b9b80269df592c3785e5bae45702953e3b746c7d0317f65753f493fe57181ef04c00cfd9c9264b41, 16ccad77968ebace006bbfae849571ff4efd0a691443d4de0fcdd2713e7bdd60709a4c2404844bd866fc57f6479c3728])
In affine coordinate (x, y)
([00b33d7ffd2ad00e126e8bcfdd74790de2450f99884ce66470e2d097e16be48a96b83e8dc24bc2a6cb86f46e5d23acd7, 0981ca11a04c2c4be6628268ea471ca194c6f2ba8bb513b8c75434c744fc4cff1f5c188f53f5edfb410da82d24591a5b], [0701249bde632dd6d07d543f030e93a169ccfe76990f7da99ab9d7a4b2c384735210b976086f5535450803fa38e7d94e, 03ac28d89eb2b879aa3fddbd1bd83e144caab694e39e321f1fa13a8d2a6d35ba4f8bb16877e8155cace0fa7baf35e291])
-------------------------------------------
Point P (after clearCofactor):
In jacobian projective coordinates (x, y, z)
([07896efdac56b0f6cbd8c78841676d63fc733b692628687bf25273aa8a107bd8cb53bbdb705b551e239dffe019abd4df, 0bd557eda8d16ab2cb2e71cca4d7b343985064daad04734e07da5cdda26610b59cdc0810a25276467d24b315bf7860e0], [001bdb6290cae9f30f263dd40f014b9f4406c3fbbc5fea47e2ebd45e42332553961eb53a15c09e5e090d7a7122dc6657, 18370459c44e799af8ef31634a683e340e79c3a06f912594d287a443620933b47a2a3e5ce4470539eae50f6d49b8ebd6], [000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001, 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000])
In affine coordinate (x, y)
([07896efdac56b0f6cbd8c78841676d63fc733b692628687bf25273aa8a107bd8cb53bbdb705b551e239dffe019abd4df, 0bd557eda8d16ab2cb2e71cca4d7b343985064daad04734e07da5cdda26610b59cdc0810a25276467d24b315bf7860e0], [001bdb6290cae9f30f263dd40f014b9f4406c3fbbc5fea47e2ebd45e42332553961eb53a15c09e5e090d7a7122dc6657, 18370459c44e799af8ef31634a683e340e79c3a06f912594d287a443620933b47a2a3e5ce4470539eae50f6d49b8ebd6])
Success mapToCurveG2 PyECC_1_msg