# Bandersnatch Thin VRF Implementatoin Notes

Crates:
- [bandersnatch_vrfs](https://github.com/w3f/ring-vrf/tree/master/bandersnatch_vrfs)
- [dleq_vrfs](https://github.com/w3f/ring-vrf/tree/master/dleq_vrf)

RFC 9381 Notes: https://hackmd.io/@davxy/B1EB_Yr0p

## VRF Input (H)

(aka `VrfInput`)

Currently we're hashing the user domain and input data `𝛼` using `ark-transcript`.
(I'm not sure what hashing technique `ark-transcript` is using internally).

https://github.com/w3f/ring-vrf/blob/e9782f938629c90f3adb3fff2358bc8d1386af3e/bandersnatch_vrfs/src/lib.rs#L67-L81

⚠️ Replace with Elligator2 (ref 5.4.1 of RFC) as soon as ark-ec v0.4.3 is released
(shoud include https://github.com/arkworks-rs/algebra/pull/758)

## VRF Pre-Output (P)

(aka `VrfPreOutput`)

Computed as per RFC 9381 (`P = x·H`)

## VRF Nonce

Random bytes from xof. Even though it is not one of the ones specified by the RFC,
IMHO this is fine and interoperability is ensured regardless of this.

Code refs:

https://github.com/w3f/ring-vrf/blob/e9782f938629c90f3adb3fff2358bc8d1386af3e/dleq_vrf/src/thin.rs#L80

https://github.com/w3f/ring-vrf/blob/e9782f938629c90f3adb3fff2358bc8d1386af3e/dleq_vrf/src/keys.rs#L212

## VRF Proof

(aka `VrfSignature`)

`VrfInput` and `VrfPreOut` are kept within as a single structure (`VrfInOut`).

Compared to RFC 9381 `bandersnatch_vrfs` allows to:
- have a sequence of `VrfInOut`.
- sign additional data (as an `ark_transcript::Transcript`) which doesn't influence the VRF output.

Parameters:
- `x`: secret key scalar
- `Y`: public key (`x·B`)
- `ad`: additional data to be signed (`Transcript`)
- `𝛼`: VRF input (can be a sequence)

Function:
- `thin_vrf_merge`: merge user io, public key, additional data
- `challenge`: Fiat-Sharmir transform
- `nonce`: random nonce

Steps:

  H = encode_to_curve(𝛼)             // We need to do this using Elligator2
  t = Transcript(ad)
  P = x·H                            // NOTE: in the impl, this is a sequence of inputs
  io = (H, P)
  t = thin_vrf_merge(t, Y, (H, P))

  (H', P') = vrf_delinearize(t, io)
 
  k = nonce(t)
  R = k·H'                           // impl: fn new_thin_witness

  t.append(R)                        // Append serialized (compressed) R to the transcript.
  c = t.challenge()                  // Fiat-Shamir(ad, Y, 𝛼, R)

  s = k + x·c

  𝜋 = (P, R, s)

The signature is mostly a *classic* Schnorr signature `(R, s)` where:
- `R` is computed using `H'` instead of the fixed base point `B`.
- Fiat-Shamir transform also takes `R` as input

Code refs:

Signing:
https://github.com/w3f/ring-vrf/blob/e9782f938629c90f3adb3fff2358bc8d1386af3e/dleq_vrf/src/thin.rs#L103

Transcript to vrf in/out:
https://github.com/w3f/ring-vrf/blob/e9782f938629c90f3adb3fff2358bc8d1386af3e/dleq_vrf/src/vrf.rs#L270

Internally, from the user additional data `t`, public key `Y` and a list of `VrfInOut`
a single `VrfInOut` is derived:

`io = thin_vrf_merge(t, Y, ios)`

Code refs:

https://github.com/w3f/ring-vrf/blob/e9782f938629c90f3adb3fff2358bc8d1386af3e/dleq_vrf/src/thin.rs#L93

## VRF Verify

Parameters:
- `Y`: public key
- `ad`: user additional data to be signed (`Transcript`)
- `𝛼`: VRF input (can be a sequence)
- `𝜋`: VRF signature

Steps:

  (P, R, s) = 𝜋

  H = encode_to_curve(𝛼)             // We need to do this using Elligator2
  t = Transcript(ad)
  io = (H, P)

  t = thin_vrf_merge(t, Y, (H, P))
  
  (H', P') = vrf_delinearize(t, io)

  t.append(R)                      // Append witness R to the transcript hash.
  c = t.challenge()

  z = R + P'·c - H'·s

  check if z·cofactor == 0

Final step expansion (under correct signature):

    z = R + P'·c - H'·s
      = k·H' + P'·c - H'·k - H'·x·c
      = k·H' + H'·x·c - H'·k - H'·x·c
      = 0

In practice is a Schnorr signature where the `R` is computed using vrf-input point
instead of the group generator. And vrf-output point is used in place of pub key.

    vrf_in·s = vrf_in·k + vrf_in·x·c
             = R + vrf_out·c

## Spec Notes

- Usage of `Transcript` to accumulate and hash various components