# VRF upgrade (v6 -> v9)

# What's the difference
1. `ECVRF_hash_to_curve_elligator2_25519` -> `ECVRF_hash_to_curve_h2c_suite`
2. `hash_to_curve` no longer takes a suite_string as explicit input
3. `decode_proof` takes an extra 0-byte as input for domain separation
4. `hash_points` has minor differences

## 1. encode_to_curve

#### Implementation steps

 encode_to_curve(msg)
 Input: msg, an arbitrary-length byte string.
 Output: P, a point in G.
 
 Steps:
 1. u = hash_to_field(msg, 1)
 2. Q = map_to_curve(u[0])
 3. P = clear_cofactor(Q)
 4. return P

#### `hash_to_field(msg, count=1)`

 Parameters:
 - DST ("ECVRF_edwards25519_XMD:SHA-512_ELL2_NU_0x04")
 - F, a finite field of characteristic p and order q = p^m. (?)
 - q, p^m = (2^255 - 19)^1
 - p, (2^255 - 19)
 - m, (1)
 - L = ceil((ceil(log2(p)) + k) / 8) = (48)
 - expand_message, a function that expands a byte string and
 domain separation tag into a uniformly random byte string ("expand_message_xmd")
 
 Inputs:
 - msg, a byte string containing the message to hash.
 - count, the number of elements of F to output. (1)
 
 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)
 // count = 1 -> Do 1 time -> elm_offset = 0 -> return u_0
 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_xmd(msg, DST, len_in_bytes)`

 Parameters:
 - H, a hash function (sha512)
 - b_in_bytes, b / 8 for b the output size of H in bits. (64)
 For example, for b = 256, b_in_bytes = 32.
 - r_in_bytes, the input block size of H, measured in bytes (see
 discussion above). For example, for SHA-256, r_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. (64)
 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, r_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)
 // In our case ell = 1, so it'll skip the loop
 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(u)`

map_to_curve_elligator2_edwards(u)
 Input: u, an element of F.
 Output: (v, w), a point on E.
 1. (s, t) = map_to_curve_elligator2(u) # (s, t) is on M
 2. (v, w) = rational_map(s, t) # (v, w) is on E
 3. return (v, w)

#### `map_to_curve_elligator2(u)`

Constants:
 * J, (486662)
 * K, (1)
 * Z, (2)
 
 Sign of t: this mapping fixes the sign of t as specified in [BHKL13].
 No additional adjustment is required.
 
 Exceptions: The exceptional case is Z * u^2 == -1, i.e., 1 + Z * u^2
 == 0. Implementations must detect this case and set x1 = -(J / K).
 Note that this can only happen when q = 3 (mod 4).
 
 Operations:
 1. x1 = -(J / K) * inv0(1 + Z * u^2)
 2. If x1 == 0, set x1 = -(J / K)
 3. gx1 = x1^3 + (J / K) * x1^2 + x1 / K^2
 4. x2 = -x1 - (J / K)
 // gx2 might not happen? (Because gx1 is always square.)
 5. gx2 = x2^3 + (J / K) * x2^2 + x2 / K^2
 6. If is_square(gx1), set x = x1, y = sqrt(gx1), and sgn0(y) == 1.
 7. Else set x = x2, y = sqrt(gx2), and sgn0(y) == 0.
 // -----------
 8. s = x * K
 9. t = y * K
 10. return (s, t)

#### `rational_map`

The birational maps are:
 (u, v) = ((1+y)/(1-y), sqrt(-486664)*u/x)
 (x, y) = (sqrt(-486664)*u/v, (u-1)/(u+1))

---

### `clear_cofactor`

The clear_cofactor function is parameterized by a scalar h_eff.
* h_eff = 8

 Specifically,
 clear_cofactor(P) := h_eff * P
 
 where * represents scalar multiplication. When a curve does not
 support a fast cofactor clearing method, h_eff = h and the cofactor
 MUST be cleared via scalar multiplication.

---

## 2. de

## Utility function

### `I2OSP(x, xLen)`

 I2OSP converts a nonnegative integer to an octet string of a
 specified length.
 
 Input:
 x nonnegative integer to be converted
 xLen intended length of the resulting octet string
 
 Output:
 X corresponding octet string of length xLen
 Error: "integer too large"
 
 Steps:
 1. If x >= 256^xLen, output "integer too large" and stop.
 2. Write the integer x in its unique xLen-digit representation in
 base 256:
 
 x = x_(xLen-1) 256^(xLen-1) + x_(xLen-2) 256^(xLen-2) + ...
 + x_1 256 + x_0,
 where 0 <= x_i < 256 (note that one or more leading digits
 will be zero if x is less than 256^(xLen-1)).
 
 3. Let the octet X_i have the integer value x_(xLen-i) for 1 <= i
 <= xLen. Output the octet string
 
 X = X_1 X_2 ... X_xLen.

### `OS2IP(X)`

 OS2IP converts an octet string to a nonnegative integer.

 Input: X octet string to be converted
 Output: x corresponding nonnegative integer
 
 Steps:
 1. Let X_1 X_2 ... X_xLen be the octets of X from first to last,
 and let x_(xLen-i) be the integer value of the octet X_i for 1
 <= i <= xLen.
 
 2. Let x = x_(xLen-1) 256^(xLen-1) + x_(xLen-2) 256^(xLen-2) +
 ... + x_1 256 + x_0.
 
 3. Output x.

### `sgn0(x)`

* sgn0(x): This function returns either 0 or 1 indicating the "sign"
 of x, where sgn0(x) == 1 just when x is "negative". (In other
 words, this function always considers 0 to be positive.)
 Section 4.1 defines this function and discusses its
 implementation.

### `is_sqaure(x)`

is_square(x): This function returns True whenever the value x is a
 square in the field F. By Euler’s criterion, this function can be
 calculated in constant time as
 is_square(x) := { True, if x^((q - 1) / 2) is 0 or 1 in F;
 { False, otherwise.

## Question
- `"ECVRF_" || "edwards25519_XMD:SHA-512_ELL2_NU_" || suite_string` when do we use it and is it DST?