Source file `degree_check.ml`

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
open Bls
open Utils
module Proof = Commitment.Single

type prover_public_parameters = Srs_g1.t

type verifier_public_parameters = {srs_0 : G2.t; srs_n_d : G2.t}

type secret = Poly.t

(* p(X) of degree n. Max degree that can be committed: d, which is also the
   SRS's length - 1. We take d = t.max_polynomial_length - 1 since we don't want to commit
   polynomials with degree greater than polynomials to be erasure-encoded.

   We consider the bilinear groups (G_1, G_2, G_T) with G_1=<g> and G_2=<h>.
   - Commit (p X^{d-n}) such that deg (p X^{d-n}) = d the max degree
   that can be committed
   - Verify: checks if e(commit(p), commit(X^{d-n})) = e(commit(p X^{d-n}), h)
   using the commitments for p and p X^{d-n}, and computing the commitment for
   X^{d-n} on G_2. *)

(* Proves that degree(p) < t.max_polynomial_length *)
(* FIXME https://gitlab.com/tezos/tezos/-/issues/4192
   Generalize this function to pass the slot_size in parameter. *)
let prove ~max_commit ~max_degree srs p =
  (* Note: this reallocates a buffer of size (Srs_g1.size t.srs.raw.srs_g1)
     (2^21 elements in practice), so roughly 100MB. We can get rid of the
     allocation by giving an offset for the SRS in Pippenger. *)
  Poly.mul_xn p (max_commit - max_degree) Scalar.zero
  |> Commitment.Single.commit srs

(* Verifies that the degree of the committed polynomial is < t.max_polynomial_length *)
let verify {srs_0; srs_n_d} (cm : Commitment.Single.t) proof =
  (* checking that cm * committed_offset_monomial = proof *)
  Pairing.pairing_check [(G1.negate cm, srs_n_d); (proof, srs_0)]

let prove_multi ~max_commit ~max_degree srs transcript cm p =
  let transcript = Transcript.expand Commitment.t cm transcript in
  let r, transcript = Fr_generation.random_fr transcript in
  let rs = Fr_generation.powers (SMap.cardinal cm) r in
  let p, _ =
    SMap.fold
      (fun _ p (acc, i) -> (Poly.(acc + mul_by_scalar rs.(i) p), i + 1))
      p
      (Poly.zero, 0)
  in
  let proof = (prove ~max_commit ~max_degree srs) p in
  (proof, transcript)

(* Verifies that the degree of the committed polynomial is < t.max_polynomial_length *)
let verify_multi pp transcript (cm : Commitment.t) proof =
  (* checking that cm * committed_offset_monomial = proof *)
  let transcript = Transcript.expand Commitment.t cm transcript in
  let r, transcript = Fr_generation.random_fr transcript in
  let rs = Fr_generation.powers (SMap.cardinal cm) r in
  let cm =
    Commitment.Commit.with_affine_array_1 (SMap.values cm |> Array.of_list) rs
  in
  let check = verify pp cm proof in
  (check, transcript)