package octez-libs

  1. Overview
  2. Docs
package octez-libs
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

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)
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct