stdlib icon indicating copy to clipboard operation
stdlib copied to clipboard

Adding modulo field prime to scalar.new

Open logicalmechanism opened this issue 5 months ago • 6 comments

When using the Fiat-Shamir heuristic with the available in crypto hash functions it is possible to get values larger than the field prime of bls12-381. I have two options, truncating the hash at my function level or I add in a modulo the field prime term for values larger than the field prime.

I opt for modulo the field prime.

Example:

pub fn fiat_shamir_heuristic(
  // compressed g element
  g_b: ByteArray,
  // compressed g^r element
  g_r_b: ByteArray,
  // compressed g^x element
  u_b: ByteArray,
  // upper bound as bytearray
  b: ByteArray,
) -> ByteArray {
  // concat g_b, g_r_b, u_b, and b together then hash the result
  // blake2b_256 is the cheapest on chain
  g_b
    |> bytearray.concat(g_r_b)
    |> bytearray.concat(u_b)
    |> bytearray.concat(b)
    |> crypto.blake2b_256()
}
test real_fiat_shamir_transform() {
  fiat_shamir_heuristic(
    #"97f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb",
    #"81b223cea171a87feba9b7749a2df7601c5a75ae01155fadc124a2ac49099a514cf1e7d9cdc769dceab14a95bd6cb0bd",
    #"a09d99e02f7200526dc55ef722cc171e7aa14fc732614c02ac58d59d7026a7eb18d8798f6928ea2b513f3a4feb0c94d1",
    #"acab",
  ) == #"8f9409d05727322c9f2d1d0adf817b8d0e3a681977edc9ab866879a4a4f8f5b9"
}

The resulting challenge value from the Fiat-Shamir transform will crash at validation, due to an expect erroring because scalar.new is a scaler if and only if it is in range, thus preventing spending when performing my NIZK.

If we just added a modulo field prime for values larger than the field prime then this never happens.

Also about 54% of blake2b_256 hashes will be larger than the field prime so it probably a good idea to account for this.

logicalmechanism avatar Sep 16 '24 20:09 logicalmechanism