proofs/crypto/secp256k1/ineq.bend

bend-collections-laws-crypto@1.0.0.0 · 84 lines · 17 definitions

1# GENERATED by tools/generators/rw.py from ../../../tools/generators/secp256k1_hand/ineq.src; edit the .src
2import Base
3import bend-collections-laws-crypto@1.0.0.0/spec/lib/common.bend as C
4import bend-collections-laws-crypto@1.0.0.0/proofs/lib/nat.bend as N
5import bend-collections-laws-crypto@1.0.0.0/proofs/lib/logic.bend as Lg
6import bend-collections-laws-crypto@1.0.0.0/proofs/lib/arith.bend as AR
7import bend-collections-laws-crypto@1.0.0.0/proofs/lib/lemmas/proofs/nat_algebra.bend as NA
8import bend-collections-laws-crypto@1.0.0.0/proofs/math/typed/width.bend as WW
9
10# Order facts on Nat used by the secp256k1 bound proofs (monotonicity of
11# +, * and C.shift), all as {... == True{} : Bool}.
12
13def le_subst_r(+a: Nat, +b: Nat, +c: Nat, +e: {b == c : Nat}, +h: {Nat.is_le(a, b) == True{} : Bool}) -> {Nat.is_le(a, c) == True{} : Bool}:
14  Lg.subst(Nat, z => {Nat.is_le(a, z) == True{} : Bool}, b, c, e, h)
15
16def le_subst_l(+a: Nat, +b: Nat, +c: Nat, +e: {a == b : Nat}, +h: {Nat.is_le(a, c) == True{} : Bool}) -> {Nat.is_le(b, c) == True{} : Bool}:
17  Lg.subst(Nat, z => {Nat.is_le(z, c) == True{} : Bool}, a, b, e, h)
18
19def lt_subst_r(+a: Nat, +b: Nat, +c: Nat, +e: {b == c : Nat}, +h: {Nat.is_lt(a, b) == True{} : Bool}) -> {Nat.is_lt(a, c) == True{} : Bool}:
20  Lg.subst(Nat, z => {Nat.is_lt(a, z) == True{} : Bool}, b, c, e, h)
21
22def lt_subst_l(+a: Nat, +b: Nat, +c: Nat, +e: {a == b : Nat}, +h: {Nat.is_lt(a, c) == True{} : Bool}) -> {Nat.is_lt(b, c) == True{} : Bool}:
23  Lg.subst(Nat, z => {Nat.is_lt(z, c) == True{} : Bool}, a, b, e, h)
24
25# b <= a + b
26def le_add_l(+a: Nat, +b: Nat) -> {Nat.is_le(b, Nat.add(a, b)) == True{} : Bool}:
27  le_subst_r(b, Nat.add(b, a), Nat.add(a, b), NA.add_comm(b, a), N.le_add_right(b, a))
28
29# a <= c, b <= d: a + b <= c + d
30def le_add2(+a: Nat, +b: Nat, +c: Nat, +d: Nat, +h1: {Nat.is_le(a, c) == True{} : Bool}, +h2: {Nat.is_le(b, d) == True{} : Bool}) -> {Nat.is_le(Nat.add(a, b), Nat.add(c, d)) == True{} : Bool}:
31  N.le_trans(Nat.add(a, b), Nat.add(c, b), Nat.add(c, d), WW.le_add_r(a, c, b, h1), N.le_add_left(b, d, c, h2))
32
33# a < c, b <= d: a + b < c + d
34def lt_le_add(+a: Nat, +b: Nat, +c: Nat, +d: Nat, +h1: {Nat.is_lt(a, c) == True{} : Bool}, +h2: {Nat.is_le(b, d) == True{} : Bool}) -> {Nat.is_lt(Nat.add(a, b), Nat.add(c, d)) == True{} : Bool}:
35  N.lt_le_trans(Nat.add(a, b), Nat.add(c, b), Nat.add(c, d), N.lt_add_r2(a, c, b, h1), N.le_add_left(b, d, c, h2))
36
37# a <= c, b < d: a + b < c + d
38def le_lt_add(+a: Nat, +b: Nat, +c: Nat, +d: Nat, +h1: {Nat.is_le(a, c) == True{} : Bool}, +h2: {Nat.is_lt(b, d) == True{} : Bool}) -> {Nat.is_lt(Nat.add(a, b), Nat.add(c, d)) == True{} : Bool}:
39  N.le_lt_trans(Nat.add(a, b), Nat.add(c, b), Nat.add(c, d), WW.le_add_r(a, c, b, h1), N.lt_add_left(b, d, c, h2))
40
41# b <= c: a b <= a c
42def le_mul_r(+a: Nat, +b: Nat, +c: Nat, +h: {Nat.is_le(b, c) == True{} : Bool}) -> {Nat.is_le(Nat.mul(a, b), Nat.mul(a, c)) == True{} : Bool}:
43  %Equal.sym(Nat, Nat.mul(a, b), Nat.mul(b, a), NA.mul_comm(a, b)) : {Nat.is_le(_, Nat.mul(a, c)) == True{} : Bool}
44  %Equal.sym(Nat, Nat.mul(a, c), Nat.mul(c, a), NA.mul_comm(a, c)) : {Nat.is_le(Nat.mul(b, a), _) == True{} : Bool}
45  AR.mul_le(b, c, a, h)
46
47# a <= c, b <= d: a b <= c d
48def le_mul2(+a: Nat, +b: Nat, +c: Nat, +d: Nat, +h1: {Nat.is_le(a, c) == True{} : Bool}, +h2: {Nat.is_le(b, d) == True{} : Bool}) -> {Nat.is_le(Nat.mul(a, b), Nat.mul(c, d)) == True{} : Bool}:
49  N.le_trans(Nat.mul(a, b), Nat.mul(c, b), Nat.mul(c, d), AR.mul_le(a, c, b, h1), le_mul_r(c, b, d, h2))
50
51def shift_le(k: Nat, +a: Nat, +b: Nat, +h: {Nat.is_le(a, b) == True{} : Bool}) -> {Nat.is_le(C.shift(k, a), C.shift(k, b)) == True{} : Bool}:
52  match k:
53    case 0n:
54      h
55    case 1n+ +j:
56      N.double_le(C.shift(j, a), C.shift(j, b), shift_le(j, a, b, h))
57
58def shift_lt(+k: Nat, +a: Nat, +b: Nat, +h: {Nat.is_lt(a, b) == True{} : Bool}) -> {Nat.is_lt(C.shift(k, a), C.shift(k, b)) == True{} : Bool}:
59  WW.shift_lt(k, a, b, h)
60
61# a < b gives a + 1 <= b
62def lt_succ_le(+a: Nat, +b: Nat, +h: {Nat.is_lt(a, b) == True{} : Bool}) -> {Nat.is_le(Nat.add(a, 1n), b) == True{} : Bool}:
63  %Equal.sym(Nat, Nat.add(a, 1n), Nat.add(1n, a), NA.add_comm(a, 1n)) : {Nat.is_le(_, b) == True{} : Bool}
64  N.lt_succ_le_succ(a, b, h)
65
66# a < 2^k and e < P: a + 2^k e < 2^k P (2^k written C.shift(k, one))
67def digit_lt(+k: Nat, +one: Nat, +h1: {one == 1n : Nat}, +a: Nat, +e: Nat, +pp: Nat, +ha: {Nat.is_lt(a, C.shift(k, one)) == True{} : Bool}, +he: {Nat.is_lt(e, pp) == True{} : Bool}) -> {Nat.is_lt(Nat.add(a, C.shift(k, e)), C.shift(k, pp)) == True{} : Bool}:
68  +s1 = lt_le_add(a, C.shift(k, e), C.shift(k, one), C.shift(k, e), ha, N.le_refl(C.shift(k, e)))
69  +e1 = Equal.trans(Nat, Nat.add(C.shift(k, one), C.shift(k, e)), C.shift(k, Nat.add(one, e)), C.shift(k, Nat.add(e, 1n)), Equal.sym(Nat, C.shift(k, Nat.add(one, e)), Nat.add(C.shift(k, one), C.shift(k, e)), WW.shift_add(k, one, e)),
70    Equal.cong(Nat, Nat, z => C.shift(k, z), Nat.add(one, e), Nat.add(e, 1n), Equal.trans(Nat, Nat.add(one, e), Nat.add(e, one), Nat.add(e, 1n), NA.add_comm(one, e), Equal.cong(Nat, Nat, z => Nat.add(e, z), one, 1n, h1))))
71  N.lt_le_trans(Nat.add(a, C.shift(k, e)), C.shift(k, Nat.add(e, 1n)), C.shift(k, pp), lt_subst_r(Nat.add(a, C.shift(k, e)), Nat.add(C.shift(k, one), C.shift(k, e)), C.shift(k, Nat.add(e, 1n)), e1, s1), shift_le(k, Nat.add(e, 1n), pp, lt_succ_le(e, pp, he)))
72
73# x < b and b <= c: x < c, and friends with rewriting
74def lt_of_le_lt(+a: Nat, +b: Nat, +c: Nat, +h1: {Nat.is_le(a, b) == True{} : Bool}, +h2: {Nat.is_lt(b, c) == True{} : Bool}) -> {Nat.is_lt(a, c) == True{} : Bool}:
75  N.le_lt_trans(a, b, c, h1, h2)
76
77# 0 < b: a < a + b
78def lt_add_pos(+a: Nat, +b: Nat, +h: {Nat.is_lt(0n, b) == True{} : Bool}) -> {Nat.is_lt(a, Nat.add(a, b)) == True{} : Bool}:
79  +s = N.lt_add_left(0n, b, a, h)
80  lt_subst_l(Nat.add(a, 0n), a, Nat.add(a, b), NA.add_zero(a), s)
81
82# a <= a + b, and a <= a * b for b >= 1
83def le_mul_pos(+a: Nat, +b: Nat, +h: {Nat.is_le(1n, b) == True{} : Bool}) -> {Nat.is_le(a, Nat.mul(a, b)) == True{} : Bool}:
84  le_subst_l(Nat.mul(a, 1n), a, Nat.mul(a, b), NA.mul_one(a), le_mul_r(a, 1n, b, h))