[](https://)# Full PLUME Proof

To prove the whole nullifier scheme, we need to include all of these checks to reach parity with the verification of the new signature as it is in Rust/JS here: https://github.com/zk-nullifier-sig/zk-nullifier-sig/ .

## Remaining work
Note that these circuits refer to the analogous ones in https://github.com/0xPARC/circom-ecdsa/ .

We want a circuit that combines the below hash-to-curve in circom work with the following sub-circuits:

ECDSAPrivToPub on s
Secp256k1ScalarMult on pk and c
Invert that using inverse code from ECDSAVerifyNoPubkeyCheck
Add those with Secp256k1AddUnequal to get g^r

h = hash_to_curve[m, g^sk]
Secp256k1ScalarMult on h and s
Secp256k1ScalarMult on nul and c
Invert thay by negating the y coordinate (p-y via BigSub and Get_Secp256k1_Prime)
Add those with Secp256k1AddUnequal to get h^r

Array concatentation on all 6 of these signals
sha256 on concatenation

# secp256k1 hash-to-curve in circom

Repo: https://github.com/geometryresearch/secp256k1_hash_to_curve/

## Dependency graph

secp256k1_XMD:SHA-256_SSWU_RO_
- hash_to_field (1881345 constraints where msg.length == 3)
  - expand_message (1877629 constraints where msg.length == 3)
    - sha256
        - 614k constraints to compute b0 = sha256(msg_prime) for the shortest strings (e.g. msg = "abc")
        - 410060 constraints to compute b1 = sha256(b0)
        - strxor (1728 constraints for two 32-byte inputs)
    - Optional: a circuit that parameterises the message length using a signal so we don't need one circuit per possible message length? Note that SHA256 supports "windows" and the circuit will need to be modified...
- map_to_curve (68792 constraints)
  - modulo Fp: 2773 constraints (`BigMod`)
  - multiplication in Fp: 3752 constraints (`BigMultModP`)
  - addition in Fp: 3027 constraints (`BigAdd` and `BigMod`)
  - subtraction in Fp: 534 constraints (`BigSubModP`)
  - modulo inverse in Fp: 3990 constraints
  - is_square in Fp (to be implemented)
  - cmov: (36 constraints) use mux1 from circomlib
  - sqrt in Fp: combiner a selector for gx1 and gx2, and use the `(res * res) mod p === input` technique
  - sgn0 in Fp (16 constraints)
- secp256k1 point addition
- isogeny map (iso_map) (95331 constraints)

The algorithm: `secp256k1_XMD:SHA-256_SSWU_RO_ `

Reference document: https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-13.html#name-secp256k1_xmdsha-256_sswu_r

secp256k1_XMD:SHA-256_SSWU_RO_ is defined as follows:

encoding type: hash_to_curve (Section 3)
E: y^2 = x^3 + 7
p: 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1
m: 1
k: 128
expand_message: expand_message_xmd (Section 5.4.1)
H: SHA-256
L: 48
f: Simplified SWU for AB == 0 (Section 6.6.3)
Z: -11
E': y'^2 = x'^3 + A' * x' + B', where

A': 0x3f8731abdd661adca08a5558f0f5d272e953d363cb6f0e5d405447c01a444533
B': 1771
iso_map: the 3-isogeny map from E' to E given in Appendix E.1
h_eff: 1
secp256k1_XMD:SHA-256_SSWU_NU_ is identical to secp256k1_XMD:SHA-256_SSWU_RO_, except that the encoding type is encode_to_curve (Section 3).

An optimized example implementation of the Simplified SWU mapping to the curve E' isogenous to secp256k1 is given in Appendix F.2.

## `hash_to_curve`
From the spec:

hash_to_curve is a uniform encoding from byte strings to points in G. That is, the distribution of its output is statistically close to uniform in G.

This function is suitable for most applications requiring a random oracle returning points in G, when instantiated with any of the map_to_curve functions described in Section 6. See Section 10 for further discussion.

hash_to_curve(msg)

Input: msg, an arbitrary-length byte string.
Output: P, a point in G.
Steps:
1. u = hash_to_field(msg, 2)
2. Q0 = map_to_curve(u[0])
3. Q1 = map_to_curve(u[1])
4. R = Q0 + Q1              # Point addition
5. P = clear_cofactor(R)
6. return P

Each hash-to-curve suite in Section 8 instantiates one of these encoding functions for a specifc elliptic curve.
### `hash_to_field`

https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-13.html#hashtofield

hash_to_field(msg, count)

Parameters:
- DST, a domain separation tag (see discussion above).
- F, a finite field of characteristic p and order q = p^m.
- p, the characteristic of F (see immediately above).
- m, the extension degree of F, m >= 1 (see immediately above).
- L = ceil((ceil(log2(p)) + k) / 8), where k is the security
  parameter of the suite (e.g., k = 128).
- expand_message, a function that expands a byte string and
  domain separation tag into a uniformly random byte string
  (see discussion above).

Inputs:
- msg, a byte string containing the message to hash.
- count, the number of elements of F to output.

Outputs:
- (u_0, ..., u_(count - 1)), a list of field elements.

Steps:
1. len_in_bytes = count * m * L
2. uniform_bytes = expand_message(msg, DST, len_in_bytes)
3. for i in (0, ..., count - 1):
4.   for j in (0, ..., m - 1):
5.     elm_offset = L * (j + i * m)
6.     tv = substr(uniform_bytes, elm_offset, L)
7.     e_j = OS2IP(tv) mod p
8.   u_i = (e_0, ..., e_(m - 1))
9. return (u_0, ..., u_(count - 1))

#### `expand_message`

https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-13.html#hashtofield-expand-xmd

Looks like most of the values can be precomputed

expand_message_xmd(msg, DST, len_in_bytes)

Parameters:
- H, a hash function (see requirements above).
- b_in_bytes, b / 8 for b the output size of H in bits.
  For example, for b = 256, b_in_bytes = 32.
- s_in_bytes, the input block size of H, measured in bytes (see
  discussion above). For example, for SHA-256, s_in_bytes = 64.

Input:
- msg, a byte string.
- DST, a byte string of at most 255 bytes.
  See below for information on using longer DSTs.
- len_in_bytes, the length of the requested output in bytes,
  not greater than the lesser of (255 * b_in_bytes) or 2^16-1.

Output:
- uniform_bytes, a byte string.

Steps:
1.  ell = ceil(len_in_bytes / b_in_bytes)
2.  ABORT if ell > 255
3.  DST_prime = DST || I2OSP(len(DST), 1)
4.  Z_pad = I2OSP(0, s_in_bytes)
5.  l_i_b_str = I2OSP(len_in_bytes, 2)
6.  msg_prime = Z_pad || msg || l_i_b_str || I2OSP(0, 1) || DST_prime
7.  b_0 = H(msg_prime)
8.  b_1 = H(b_0 || I2OSP(1, 1) || DST_prime)
9.  for i in (2, ..., ell):
10.    b_i = H(strxor(b_0, b_(i - 1)) || I2OSP(i, 1) || DST_prime)
11. uniform_bytes = b_1 || ... || b_ell
12. return substr(uniform_bytes, 0, len_in_bytes)

### `map_to_curve`

https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-13.html#simple-swu-AB0

Use this straight-line implementation: https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-13.html#appendix-F.2

1. (x', y') = map_to_curve_simple_swu(u)    # (x', y') is on E'
2.   (x, y) = iso_map(x', y')               # (x, y) is on E
3. return (x, y)

map_to_curve_simple_swu(u)

Input: u, an element of F.
Output: (x, y), a point on E.

Steps:
1.  tv1 = u^2
2.  tv1 = Z * tv1
3.  tv2 = tv1^2
4.  tv2 = tv2 + tv1
5.  tv3 = tv2 + 1
6.  tv3 = B * tv3
7.  tv4 = CMOV(Z, -tv2, tv2 != 0)
8.  tv4 = A * tv4
9.  tv2 = tv3^2
10. tv6 = tv4^2
11. tv5 = A * tv6
12. tv2 = tv2 + tv5
13. tv2 = tv2 * tv3
14. tv6 = tv6 * tv4
15. tv5 = B * tv6
16. tv2 = tv2 + tv5
17.   x = tv1 * tv3
18. (is_gx1_square, y1) = sqrt_ratio(tv2, tv6)
19.   y = tv1 * u
20.   y = y * y1
21.   x = CMOV(x, tv3, is_gx1_square)
22.   y = CMOV(y, y1, is_gx1_square)
23.  e1 = sgn0(u) == sgn0(y)
24.   y = CMOV(-y, y, e1)
25.   x = x / tv4
26. return (x, y)

`x` and `y` are a point on `E'`. To convert them to a point on `E`, apply `iso_map()`.

#### `iso_map()`

https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-13.html#appx-iso-secp256k1

### `clear_cofactor`

https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-13.html#cofactor-clearing

No need to implement this because `h_eff` equals 1 for secp256k1.

## `expand_message_xmd`
See `expand_message` above.

## `iso_map`

https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-13.html#appx-iso-secp256k1

## General SHA256 circuit

The SHA256 circuit provided by iden3 is parameterised by the message length. This is not ideal because our signature scheme and hash-to-curve circuit (currently) requires aribtrary-length inputs. As such it is infeasible to have a trusted setup per message length (e.g. msg.length = 16, 17, 18, ...).

A simple change to iden3's SHA256 circuit, with an additional check on the input, can address this.

First, the SHA256 circuit should be modified to accept a raw array of bits. These bits are assumed to already been padded per [RFC4634, section 4.1](https://www.rfc-editor.org/rfc/rfc4634#section-4.1).

Next, a new circuit should be written to convert a message to an array of padded bits as per RFC4634. This array must represent the (padded) preimage of the `MsgPrime` input to `HashMsgPrimeToB0`.

Finally, `HashMsgPrimeToB0` should be rewritten to accept the above-described array of padded bits.