package octez-libs

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

Source file ec_pbt.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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
let rec repeat n f () =
  if n > 0 then (
    f () ;
    repeat (n - 1) f ())

module MakeEquality (G : Ec_sig.BASE) = struct
  (** Verify the equality is correct with the value zero *)
  let zero () = assert (G.eq G.zero G.zero)

  (** Verify the equality is correct with the value one *)
  let one () = assert (G.eq G.one G.one)

  (** Verify the equality of two random values created invidually *)
  let random_same_objects () =
    let random = G.random () in
    assert (G.eq random random)

  (** Returns the tests to be used with Alcotest *)
  let get_tests () =
    let open Alcotest in
    ( "equality",
      [
        test_case "zero" `Quick (repeat 1 zero);
        test_case "one" `Quick (repeat 1 one);
        test_case "random_same_objects" `Quick (repeat 100 random_same_objects);
      ] )
end

module MakeValueGeneration (G : Ec_sig.BASE) = struct
  let random () = ignore @@ G.random ()

  let negation_with_random () =
    let random = G.random () in
    ignore @@ G.negate random

  let negation_with_zero () = ignore @@ G.negate G.zero

  let negation_with_one () = ignore @@ G.negate G.one

  let double_with_zero () = ignore @@ G.double G.zero

  let double_with_one () = ignore @@ G.double G.one

  let double_with_random () =
    let g = G.random () in
    ignore @@ G.double g

  let addition_generates_valid_point () =
    assert (G.(check_bytes (to_bytes (add (random ()) (random ())))))

  let double_generates_valid_point () =
    assert (G.(check_bytes (to_bytes (double (random ())))))

  let scalar_multiplication_generates_valid_point () =
    assert (G.(check_bytes (to_bytes (mul (random ()) (Scalar.random ())))))

  let check_bytes_random_with_to_bytes () =
    let g = G.random () in
    assert (G.(check_bytes (to_bytes g)))

  let negate_generates_a_valid_point () =
    let g = G.random () in
    assert (G.(check_bytes (to_bytes (negate g))))

  let of_bytes_with_to_bytes_are_inverse_functions () =
    let g = G.random () in
    assert (G.(eq (of_bytes_exn (to_bytes g)) g))

  (** Returns the tests to be used with Alcotest *)
  let get_tests () =
    let open Alcotest in
    ( "value generation",
      [
        test_case "random" `Quick (repeat 100 random);
        test_case "negate_with_one" `Quick (repeat 1 negation_with_one);
        test_case "negate_with_zero" `Quick (repeat 1 negation_with_zero);
        test_case "negate_with_random" `Quick (repeat 100 negation_with_random);
        test_case "double_with_random" `Quick (repeat 100 double_with_random);
        test_case
          "negate generates a valid point"
          `Quick
          (repeat 100 negate_generates_a_valid_point);
        test_case
          "addition generates a valid point"
          `Quick
          (repeat 100 addition_generates_valid_point);
        test_case
          "double generates a valid point"
          `Quick
          (repeat 100 double_generates_valid_point);
        test_case
          "scalar multiplication generates a valid point"
          `Quick
          (repeat 100 scalar_multiplication_generates_valid_point);
        test_case
          "of_bytes_exn and to_bytes are inverse functions"
          `Quick
          (repeat 100 of_bytes_with_to_bytes_are_inverse_functions);
        test_case
          "check bytes on random with to_bytes"
          `Quick
          (repeat 100 check_bytes_random_with_to_bytes);
        test_case "double_with_one" `Quick (repeat 1 double_with_one);
        test_case "double_with_zero" `Quick (repeat 100 double_with_zero);
      ] )
end

module MakeIsZero (G : Ec_sig.BASE) = struct
  let with_zero_value () = assert (G.is_zero G.zero = true)

  let with_one_value () = assert (G.is_zero G.one = false)

  let with_random_value () = assert (G.is_zero (G.random ()) = false)

  (** Returns the tests to be used with Alcotest *)
  let get_tests () =
    let open Alcotest in
    ( "is_zero",
      [
        test_case "with zero value" `Quick (repeat 1 with_zero_value);
        test_case "with one value" `Quick (repeat 1 with_one_value);
        test_case "with random value" `Quick (repeat 100 with_random_value);
      ] )
end

module MakeECProperties (G : Ec_sig.BASE) = struct
  (** Verify that a random point is valid *)
  let check_bytes_random () = assert (G.(check_bytes @@ to_bytes @@ random ()))

  (** Verify that the zero point is valid *)
  let check_bytes_zero () = assert (G.(check_bytes @@ to_bytes @@ zero))

  (** Verify that the fixed generator point is valid *)
  let check_bytes_one () = assert (G.(check_bytes @@ to_bytes @@ one))

  (** Verify that doubling a random point gives a valid point *)
  let check_bytes_random_double () =
    assert (G.(check_bytes @@ to_bytes @@ double (random ())))

  (** Verify that the sum of random points is valid *)
  let check_bytes_random_sum () =
    assert (G.(check_bytes @@ to_bytes @@ add (random ()) (random ())))

  (** Verify that multiplying a random point by a scalar gives a valid point *)
  let check_bytes_random_multiplication () =
    assert (G.(check_bytes @@ to_bytes @@ mul (random ()) (Scalar.random ())))

  (** Verify 0_S * g_EC = 0_EC where 0_S is the zero of the scalar field, 0_EC
  is the point at infinity and g_EC is an element of the EC *)
  let zero_scalar_nullifier_random () =
    let random = G.random () in
    assert (G.is_zero (G.mul random G.Scalar.zero))

  (** Verify 0_S * 0_EC = 0_EC where 0_S is the zero of the scalar field and
  0_EC is the point at infinity of the EC *)
  let zero_scalar_nullifier_zero () =
    assert (G.is_zero (G.mul G.zero G.Scalar.zero))

  (** Verify 0_S * 1_EC = 0_EC where 0_S is the 0 of the scalar field, 1_EC is a
  fixed generator and 0_EC is the point at infinity of the EC *)
  let zero_scalar_nullifier_one () =
    assert (G.is_zero (G.mul G.one G.Scalar.zero))

  let multiply_by_one_does_nothing () =
    let g = G.random () in
    assert (G.(eq (mul g Scalar.one) g))

  (** Verify -(-g) = g where g is an element of the EC *)
  let opposite_of_opposite () =
    let random = G.random () in
    assert (G.eq (G.negate (G.negate random)) random)

  let opposite_of_opposite_using_scalar () =
    let r = G.random () in
    assert (G.(eq r (mul r (Scalar.negate (Scalar.negate Scalar.one)))))

  (** Verify -(-0_EC) = 0_EC where 0_EC is the point at infinity of the EC *)
  let opposite_of_zero_is_zero () = assert (G.eq (G.negate G.zero) G.zero)

  (** Verify -(-0_EC) = 0_EC where 0_EC is the point at infinity of the EC *)
  let opposite_of_opposite_of_zero_is_zero () =
    assert (G.eq (G.negate (G.negate G.zero)) G.zero)

  (** Verify -(-0_EC) = 0_EC where 0_EC is the point at infinity of the EC *)
  let opposite_of_opposite_of_one_is_one () =
    assert (G.eq (G.negate (G.negate G.one)) G.one)

  (** Verify g1 + (g2 + g3) = (g1 + g2) + g3 *)
  let additive_associativity () =
    let g1 = G.random () in
    let g2 = G.random () in
    let g3 = G.random () in
    assert (G.eq (G.add (G.add g1 g2) g3) (G.add g1 (G.add g2 g3)))

  (** Verify (g1 + g2) = (g2 + g1) *)
  let additive_commutativity () =
    let g1 = G.random () in
    let g2 = G.random () in
    assert (G.eq (G.add g1 g2) (G.add g2 g1))

  (** Verify that g + (-g) = 0 *)
  let opposite_existential_property () =
    let g = G.random () in
    assert (G.(eq (add g (negate g)) zero))

  (** Verify a (g1 + g2) = a * g1 + a * g2 where a is a scalar, g1, g2 two
  elements of the EC *)
  let distributivity () =
    let s = G.Scalar.random () in
    let g1 = G.random () in
    let g2 = G.random () in
    assert (G.eq (G.mul (G.add g1 g2) s) (G.add (G.mul g1 s) (G.mul g2 s)))

  (** Verify (a + -a) * g = a * g - a * g = 0 *)
  let opposite_equality () =
    let a = G.Scalar.random () in
    let g = G.random () in
    assert (G.(eq (mul g (Scalar.add a (Scalar.negate a))) zero)) ;
    assert (G.(eq zero (add (mul g a) (mul g (Scalar.negate a))))) ;
    assert (
      G.(
        eq
          (mul g (Scalar.add a (Scalar.negate a)))
          (add (mul g a) (mul g (Scalar.negate a)))))

  (** a g + b + g = (a + b) g*)
  let additive_associativity_with_scalar () =
    let a = G.Scalar.random () in
    let b = G.Scalar.random () in
    let g = G.random () in
    let left = G.(add (mul g a) (mul g b)) in
    let right = G.(mul g (Scalar.add a b)) in
    assert (G.(eq left right))

  (** (a * b) g = a (b g) = b (a g) *)
  let multiplication_properties_on_base_field_element () =
    let a = G.Scalar.random () in
    let b = G.Scalar.random () in
    let g = G.random () in
    assert (G.(eq (mul g (Scalar.mul a b)) (mul (mul g a) b))) ;
    assert (G.(eq (mul g (Scalar.mul a b)) (mul (mul g b) a)))

  (** Verify (-s) * g = s * (-g) *)
  let opposite_of_scalar_is_opposite_of_ec () =
    let s = G.Scalar.random () in
    let g = G.random () in
    let left = G.mul g (G.Scalar.negate s) in
    let right = G.mul (G.negate g) s in
    assert (G.eq left right)

  let generator_is_of_prime_order () =
    assert (G.(eq (mul one (G.Scalar.of_z G.Scalar.order)) zero))

  let mul_by_order_of_scalar_field_equals_zero () =
    let s = G.Scalar.random () in
    let g = G.random () in
    (* (g * s) * order = zero *)
    assert (G.(eq (mul (mul g s) (G.Scalar.of_z G.Scalar.order)) zero)) ;
    (* (one * s) * order = zero *)
    assert (G.(eq (mul (mul one s) (G.Scalar.of_z G.Scalar.order)) zero))

  (** Verify 2*g = g + g *)
  let double () =
    let s = G.random () in
    assert (G.(eq (double s) (add s s)))

  let inverse_on_scalar () =
    let g = G.random () in
    let a = G.Scalar.random () in
    let inv_a = G.Scalar.inverse_exn a in
    let ga = G.mul g a in
    let ga_inv = G.mul g inv_a in
    (* g * (a * a^(-1)) *)
    let res1 = G.mul g (G.Scalar.mul inv_a a) in
    (* (g * a^(-1)) * a *)
    let res2 = G.mul ga_inv a in
    (* (g * a) * a^(-1) *)
    let res3 = G.mul ga inv_a in
    assert (G.(eq res2 res3)) ;
    (* g * (a * a^(-1)) = g *)
    assert (G.(eq res1 g)) ;
    (* (g * a^(-1)) * a = g *)
    assert (G.(eq res2 g)) ;
    (* (g * a) * a^(-1) = g *)
    assert (G.(eq res3 g))

  let zero_is_the_identity () =
    let g = G.random () in
    assert (G.(eq (add g zero) (add zero g))) ;
    assert (G.(eq (add g zero) g))

  (** Returns the tests to be used with Alcotest *)
  let get_tests () =
    let open Alcotest in
    ( "Group properties",
      [
        test_case "check_bytes_random" `Quick (repeat 100 check_bytes_random);
        test_case "check_bytes_zero" `Quick (repeat 1 check_bytes_zero);
        test_case "check_bytes_one" `Quick (repeat 1 check_bytes_one);
        test_case
          "check_bytes_random_double"
          `Quick
          (repeat 100 check_bytes_random_double);
        test_case
          "check_bytes_random_sum"
          `Quick
          (repeat 100 check_bytes_random_sum);
        test_case
          "check_bytes_random_multiplication"
          `Quick
          (repeat 100 check_bytes_random_multiplication);
        test_case
          "zero_scalar_nullifier_one"
          `Quick
          (repeat 1 zero_scalar_nullifier_one);
        test_case
          "zero_scalar_nullifier_zero"
          `Quick
          (repeat 1 zero_scalar_nullifier_zero);
        test_case
          "zero_scalar_nullifier_random"
          `Quick
          (repeat 100 zero_scalar_nullifier_random);
        test_case
          "multiply_by_one_does_nothing"
          `Quick
          (repeat 100 multiply_by_one_does_nothing);
        test_case
          "opposite_of_opposite"
          `Quick
          (repeat 100 opposite_of_opposite);
        test_case
          "opposite_of_opposite_using_scalar"
          `Quick
          (repeat 100 opposite_of_opposite_using_scalar);
        test_case
          "opposite_of_zero_is_zero"
          `Quick
          (repeat 1 opposite_of_zero_is_zero);
        test_case
          "opposite_of_opposite_of_zero_is_zero"
          `Quick
          (repeat 1 opposite_of_opposite_of_zero_is_zero);
        test_case
          "opposite_of_opposite_of_one_is_one"
          `Quick
          (repeat 1 opposite_of_opposite_of_one_is_one);
        test_case "opposite_equality" `Quick (repeat 1 opposite_equality);
        test_case
          "zero is the identity"
          `Quick
          (repeat 100 zero_is_the_identity);
        test_case "distributivity" `Quick (repeat 100 distributivity);
        test_case
          "opposite_of_scalar_is_opposite_of_ec"
          `Quick
          (repeat 100 opposite_of_scalar_is_opposite_of_ec);
        test_case
          "opposite_existential_property"
          `Quick
          (repeat 100 opposite_existential_property);
        test_case
          "mul_by_order_of_base_field_equals_element"
          `Quick
          (repeat 100 mul_by_order_of_scalar_field_equals_zero);
        test_case
          "multiplication_properties_on_base_field_element"
          `Quick
          (repeat 100 multiplication_properties_on_base_field_element);
        test_case "double" `Quick (repeat 100 double);
        test_case
          "additive_associativity_with_scalar"
          `Quick
          (repeat 100 additive_associativity_with_scalar);
        test_case "inverse on scalar" `Quick (repeat 100 inverse_on_scalar);
        test_case
          "additive_associativity"
          `Quick
          (repeat 100 additive_associativity);
        test_case
          "additive_commutativity"
          `Quick
          (repeat 100 additive_commutativity);
        test_case
          "Generator is of prime order"
          `Quick
          (repeat 1 generator_is_of_prime_order);
      ] )
end

module MakeEdwardsCurveProperties (G : Ec_sig.AffineEdwardsT) = struct
  let rec test_of_bytes_and_check_bytes_with_different_size_of_bytes () =
    (* Generate a random number of bytes between 0 and 10 * G.size_in_bytes. If
       the random value is the correct number of bytes, we ignore
    *)
    let b_size = Random.int (G.size_in_bytes * 10) in
    if b_size = G.size_in_bytes then
      test_of_bytes_and_check_bytes_with_different_size_of_bytes ()
    else
      let b = Bytes.create b_size in
      assert (not (G.check_bytes b)) ;
      assert (Option.is_none (G.of_bytes_opt b)) ;
      try
        ignore @@ G.of_bytes_exn b ;
        assert false
      with
      | G.Not_on_curve exn_bytes -> assert (Bytes.equal exn_bytes b)
      | _ -> assert false

  let test_unsafe_from_coordinates_do_not_check () =
    let u = G.Base.random () in
    let v = G.Base.random () in
    ignore @@ G.unsafe_from_coordinates ~u ~v

  let get_tests () =
    let open Alcotest in
    ( "Group properties of Edwards curve",
      [
        test_case
          "unsafe_from_coordinates do not check the point is on the curve"
          `Quick
          test_unsafe_from_coordinates_do_not_check;
        test_case
          "Test check_bytes and of_bytes_[exn/opt] with a different number of \
           bytes than expected"
          `Quick
          test_of_bytes_and_check_bytes_with_different_size_of_bytes;
      ] )
end

module MakeSerialisationProperties (G : Ec_sig.BASE) = struct
  let test_of_bytes_exn_to_bytes_are_inverse_functions () =
    let r = G.random () in
    assert (G.(eq (of_bytes_exn (to_bytes r)) r))

  let test_of_bytes_opt_to_bytes_are_inverse_functions () =
    let r = G.random () in
    assert (G.(eq (Option.get (of_bytes_opt (to_bytes r))) r))

  let get_tests () =
    let open Alcotest in
    ( "Serialisation",
      [
        test_case
          "of_bytes_exn and to_bytes are inverse functions"
          `Quick
          test_of_bytes_exn_to_bytes_are_inverse_functions;
        test_case
          "of_bytes_opt and to_bytes are inverse functions"
          `Quick
          test_of_bytes_opt_to_bytes_are_inverse_functions;
      ] )
end

module MakeCompressedSerialisationAffine (G : sig
  include Ec_sig.BASE

  val of_compressed_bytes_exn : Bytes.t -> t

  val of_compressed_bytes_opt : Bytes.t -> t option

  val to_compressed_bytes : t -> Bytes.t
end) =
struct
  let test_zero () =
    let expected_zero_bytes_compressed =
      Bytes.make (G.size_in_bytes / 2) '\000'
    in
    assert (
      Bytes.(
        equal (G.to_compressed_bytes G.zero) expected_zero_bytes_compressed))

  let test_of_compressed_bytes_exn_recover_correct_point_from_uncompressed_representation
      () =
    let g = G.random () in
    let compressed_bytes = G.to_compressed_bytes g in
    let uncompressed_g = G.of_compressed_bytes_exn compressed_bytes in
    assert (G.eq g uncompressed_g)

  let test_of_compressed_bytes_opt_recover_correct_point_from_uncompressed_representation
      () =
    let g = G.random () in
    let compressed_bytes = G.to_compressed_bytes g in
    let uncompressed_g =
      Option.get (G.of_compressed_bytes_opt compressed_bytes)
    in
    assert (G.eq g uncompressed_g)

  (* it is correct to test this for BLS12-381 *)
  let test_compressed_version_is_half_the_size () =
    let g = G.random () in
    assert (Bytes.length (G.to_compressed_bytes g) = G.size_in_bytes / 2)

  let test_of_compressed_bytes_exn_and_opt_do_not_accept_uncompressed_bytes_representation
      () =
    let x = G.random () in
    let x_uncompressed_bytes = G.to_bytes x in
    assert (Option.is_none (G.of_compressed_bytes_opt x_uncompressed_bytes)) ;
    try
      ignore @@ G.of_compressed_bytes_exn x_uncompressed_bytes ;
      assert false
    with G.Not_on_curve _b -> ()

  let test_of_bytes_exn_and_opt_do_not_accept_compressed_bytes_representation ()
      =
    let x = G.random () in
    let x_compressed_bytes = G.to_compressed_bytes x in
    assert (Option.is_none (G.of_bytes_opt x_compressed_bytes)) ;
    try
      ignore @@ G.of_bytes_exn x_compressed_bytes ;
      assert false
    with G.Not_on_curve _b -> ()

  let get_tests () =
    let open Alcotest in
    ( "Compressed representation",
      [
        test_case
          "Compressed representation of zero is the bs with zeroes"
          `Quick
          test_zero;
        test_case
          "of_compressed_bytes_exn recovers correct point from uncompressed \
           representation"
          `Quick
          (repeat
             100
             test_of_compressed_bytes_exn_recover_correct_point_from_uncompressed_representation);
        test_case
          "of_compressed_bytes_opt recovers correct point from uncompressed \
           representation"
          `Quick
          (repeat
             100
             test_of_compressed_bytes_opt_recover_correct_point_from_uncompressed_representation);
        test_case
          "Compressed version is half the size"
          `Quick
          test_compressed_version_is_half_the_size;
        test_case
          "of_compressed_bytes_exn/opt do not accept uncompressed bytes \
           representation"
          `Quick
          (repeat
             100
             test_of_compressed_bytes_exn_and_opt_do_not_accept_uncompressed_bytes_representation);
        test_case
          "of_bytes_exn/opt do not accept compressed bytes representation"
          `Quick
          (repeat
             100
             test_of_bytes_exn_and_opt_do_not_accept_compressed_bytes_representation);
      ] )
end
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