Bandersnatch Test Vectors

# Bandersnatch VRFs Open Points As JAM third party implementations are encouraged we need to produce a set of test vectors for the crypto primitives we're using. Here's a list of open points / doubts we need to address. ## Ring Proof Related - [ ] **1** Are ring-proof and fflonk libraries stable with respect to the produced output? - We don't want to produce test vectors that are invalidated by some upcoming change. - Sergey: fflonk is not audited and can't be trusted. - Fiat sharmir implementation of ring proof is not finalized. - [x] **2** We need deterministic outputs for test vectors - The 3 last items (zk-rows) of the eval are randomly generated: https://github.com/w3f/ring-proof/blob/b273d33f9981e2bb3375ab45faeb537f7ee35224/common/src/domain.rs#L103 - Al: These are blinding factors for actually hiding the secret polynomials to actually make the protocol zk. TODO: Read the apk proof from the paper (accountable light client.) - Can we have a deterministic proof instead (e.g. use a seeded PRNG). We may have a feature to turn deterministic proofs on. It is possible. Perhaps we can change the implementation to perform it more logically than re-implementing getrandom_or_panic. - If "real" randomness is absolutely required, then we need to add a feature which is enabled for testing (and for test vectors gen) which uses a seeded PRNG. - (see above) - [ ] **3** AFAK SRS in Lagrange form allows for faster proving (O(d) vs O(log(d)·d) of monomial form). Yes but it is not the only reason. For Sassaferas is an optimization but for verifiable we need this form for a bigger ring to generate partial commitment. Using lagrange form, one could spread the commitment over multiple blocks for example. - I imagine that we want to use Lagrangian form for the committer key (i.e. PcsParams::ck_with_lagrangian)? (committer key, is commiting to public key of validator). Yes. - If yes, we need Lagrangian SRS for domain size 2048 (much like what we have [here](https://github.com/w3f/ring-vrf/tree/master/bandersnatch_vrfs)) extracted from zcash [output](https://zfnd.org/conclusion-of-the-powers-of-tau-ceremony). - Yes and if they don't have the lagrange form you can compute it from their monomial forms. - [ ] **4** In JAM we're using Edwards form for PKs Bandersnatch points. - Ring-proof requires Weierstrass form - Workaround: internally, just before generation of Prover/Verifier keys, we map the pks points from Edwards to Weierstrass form using the procedure from Syed: https://github.com/arkworks-rs/algebra/pull/804 - Is this approach acceptable (This is done once per epoch to generate PK, VK)? - Al says yes it is acceptable. - Al also says: - It might be viable to change the SNARK to use TE constrains internally provided there is a good affine addition formula for TE: - [15:29:15] Alistair> So are their nice formulas for non-projective TE with 2 coordinates? [edited] [15:29:31] Alistair> Going to 3 coordinates is definitely too expensive. [15:31:07] Syed> I can look into it :-) [15:31:20] Syed> that is why I said it is a good exercise. [15:32:38] Alistair> Sure you can see if we can get a nice conditional incomplete addition constraints. [15:32:53] Syed> assuming we have good affine addition formulas then there shouldn't be a huge overhead compared to Snark with SW formula used to build its polynomial right? [15:33:21] Alistair> If you can get the same degree and 2 coordinates, then there is no overhead. [15:33:51] Alistair> If the degree is higher, then the prover is more expensive, but the verifier costs the same. [15:34:11] Alistair> If we can get the former, then TE throughout would indeed simplify the spec. [15:49:17] Alistair> Things like formula 5 from https://iacr.org/archive/asiacrypt2008/53500329/53500329.pdf looks promising. [15:49:52] Alistair> The usual formula with a degree 4 thing in the denominator seems like it might give us degree 5 instead of 3. - [ ] **5** Maybe we need to move Sergey's ring-proof specs (currently here: https://hackmd.io/ulW5nFFpTwClHsD0kusJAA) to a github repo? - Bandersnatch VRF spec is currently referencing hackmd.io but you need an account to view it. - [ ] **6** We need to have ring-proof and fflonk published on crates.io. See question 1. ## IETF VRF - [x] **7** Can we have more eyes on https://github.com/davxy/bandersnatch-vrfs-spec before producing the test vectors? - Another review would be nice (I'm not sure if Al looked into it yet) - Al read and reviewed the Spec. - [x] **8** Currently we're using "Try-And-Increment" technique for Hash2Curve when constructing VRF input point. - We're going to switch the Elligator2 implementation from Syed: https://github.com/arkworks-rs/algebra/blob/master/ec/src/hashing/curve_maps/elligator2.rs - What hasher we want to use as FieldHasher? - Syed example is using Sha256 but IIRC he suggested to use Sha512? We need to take a decision (and possibly motivate the choice) - Al says whatever either 2x256 or one 512. ## Gray Paper - [x] **9** In the paper there is a pending point that we need to fill appropriately. See here: https://pasteboard.co/bLDJsAqs06oW.png - From the gray paper (see the picture in the link): $R([H_B]) ∈ Y_R ≡ ...$ - See: https://github.com/w3f/ring-proof/blob/master/ring/src/piop/params.rs#L56 - https://github.com/w3f/ring-proof/blob/b273d33f9981e2bb3375ab45faeb537f7ee35224/ring/src/ring.rs#L27 - The paper describes this formula components this way: - $R$: "The Bandersnatch ring root function" (this is commitment to public keys) - $[H_B]$: "The sequence of public key points (bandersnatch pks)" - $Y_R$: "The set of Bandersnatch ring roots" - Challenge: Is required to fill the dots - What the gray paper describes as "$R$" I think is the KZG commitment function, so I guess the "..." must be replaced with the commitment output? - What about $R([H_B]) ∈ Y_R ≡ \text{KZG_commit}(\bar{pk}_x, \bar{pk}_y, \text{ring_selector})$ ? - This doesn't take into accout the PiopParams. But is this sufficient in this *brief* context? The reader should obviously go through Sergey's spec.