~/jendhub

proofs/crypto/secp256k1/bounds.bend

bend-collections-laws-crypto@1.0.0.0 · 100 lines · 9 definitions

1# GENERATED by tools/generators/rw.py from ../../../tools/generators/secp256k1_hand/bounds.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/spec/crypto/secp256k1/field.bend as FS
5import bend-collections-laws-crypto@1.0.0.0/src/crypto/secp256k1/limbs.bend as L
6import bend-collections-laws-crypto@1.0.0.0/proofs/lib/logic.bend as Lg
7import bend-collections-laws-crypto@1.0.0.0/proofs/math/natural/arith.bend as NR
8import bend-collections-laws-crypto@1.0.0.0/proofs/math/typed/width.bend as WW
9import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/semiring.bend as SR
10import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/limbs.bend as LV
11import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/ineq.bend as I
12
13# Limb bounds: a carry pass leaves limbs below 2^16 = C.shift(16n, one);
14# n such limbs have a value below 2^(16 n) = LV.pos(n, one).
15
16def lt_one(+one: Nat, +h1: {one == 1n : Nat}) -> {Nat.is_lt(0n, one) == True{} : Bool}:
17  %Equal.sym(Nat, one, 1n, h1) : {Nat.is_lt(0n, _) == True{} : Bool}
18  {==}
19
20def pos_pos(+one: Nat, +h1: {one == 1n : Nat}, k: Nat) -> {Nat.is_lt(0n, LV.pos(k, one)) == True{} : Bool}:
21  match k:
22    case 0n:
23      lt_one(one, h1)
24    case 1n+ +j:
25      %Equal.sym(Nat, 0n, C.shift(16n, 0n), Equal.sym(Nat, C.shift(16n, 0n), 0n, WW.shift_zero(16n))) : {Nat.is_lt(_, C.shift(16n, LV.pos(j, one))) == True{} : Bool}
26      I.shift_lt(16n, 0n, LV.pos(j, one), pos_pos(one, h1, j))
27
28# 2^(16 n) y
29def pos_shift(n: Nat, +y: Nat) -> {LV.pos(n, y) == C.shift(Nat.mul(n, 16n), y) : Nat}:
30  match n:
31    case 0n:
32      {==}
33    case 1n+ +k:
34      %Equal.sym(Nat, LV.pos(k, y), C.shift(Nat.mul(k, 16n), y), pos_shift(k, y)) : {C.shift(16n, _) == C.shift(Nat.add(16n, Nat.mul(k, 16n)), y) : Nat}
35      %Equal.sym(Nat, C.shift(Nat.add(16n, Nat.mul(k, 16n)), y), C.shift(16n, C.shift(Nat.mul(k, 16n), y)), Equal.sym(Nat, C.shift(16n, C.shift(Nat.mul(k, 16n), y)), C.shift(Nat.add(16n, Nat.mul(k, 16n)), y), SR.shift_shift(16n, Nat.mul(k, 16n), y))) : {C.shift(16n, C.shift(Nat.mul(k, 16n), y)) == _ : Nat}
36      {==}
37
38# 2^256 y
39def pos16(+y: Nat) -> {LV.pos(16n, y) == C.shift(256n, y) : Nat}:
40  pos_shift(16n, y)
41
42# s mod 256 < 2^8, and the low 16 bits of s below 2^16
43def mod256_lt(+one: Nat, +h1: {one == 1n : Nat}, +s: Nat) -> {Nat.is_lt(Nat.mod(s, 256n), C.shift(8n, one)) == True{} : Bool}:
44  %Equal.sym(Nat, C.shift(8n, one), 256n, LV.b8(one, h1)) : {Nat.is_lt(Nat.mod(s, 256n), _) == True{} : Bool}
45  NR.dm_lt(255n, s)
46
47def lo16_lt(+one: Nat, +h1: {one == 1n : Nat}, +s: Nat) -> {Nat.is_lt(L.lo16(s), C.shift(16n, one)) == True{} : Bool}:
48  %Equal.sym(Nat, Nat.mul(Nat.mod(Nat.div(s, 256n), 256n), 256n), C.shift(8n, Nat.mod(Nat.div(s, 256n), 256n)), LV.m256(Nat.mod(Nat.div(s, 256n), 256n))) : {Nat.is_lt(Nat.add(Nat.mod(s, 256n), _), C.shift(16n, one)) == True{} : Bool}
49  %Equal.sym(Nat, C.shift(16n, one), C.shift(8n, C.shift(8n, one)), Equal.sym(Nat, C.shift(8n, C.shift(8n, one)), C.shift(16n, one), SR.shift_shift(8n, 8n, one))) : {Nat.is_lt(Nat.add(Nat.mod(s, 256n), C.shift(8n, Nat.mod(Nat.div(s, 256n), 256n))), _) == True{} : Bool}
50  I.digit_lt(8n, one, h1, Nat.mod(s, 256n), Nat.mod(Nat.div(s, 256n), 256n), C.shift(8n, one), mod256_lt(one, h1, s), mod256_lt(one, h1, Nat.div(s, 256n)))
51
52# the first j <= n limbs of a carry pass: exactly j limbs below 2^16
53def carry_limbs(+one: Nat, +h1: {one == 1n : Nat}, n: Nat, j: Nat, xs: List<&2, Nat>, +u: Nat, +hj: {Nat.is_le(j, n) == True{} : Bool}) -> {FS.limbs16(one, j, L.take(j, L.carry(n, xs, u))) == True{} : Bool}:
54  match n j xs:
55    case 0n 0n Nil{}:
56      {==}
57    case 0n 0n x <> t:
58      {==}
59    case 0n 1n+i _:
60      Empty.absurd({FS.limbs16(one, 1n+i, L.take(1n+i, L.carry(0n, xs, u))) == True{} : Bool}, Lg.false_true(hj))
61    case 1n+k 0n Nil{}:
62      {==}
63    case 1n+k 0n x <> t:
64      {==}
65    case 1n+ +k 1n+ +i Nil{}:
66      +s = Nat.add(u, 0n)
67      Lg.and_intro(Nat.is_lt(L.lo16(s), C.shift(16n, one)), FS.limbs16(one, i, L.take(i, L.carry(k, [], L.hi16(s)))), lo16_lt(one, h1, s), carry_limbs(one, h1, k, i, [], L.hi16(s), hj))
68    case 1n+ +k 1n+ +i +x <> +t:
69      +s = Nat.add(u, x)
70      Lg.and_intro(Nat.is_lt(L.lo16(s), C.shift(16n, one)), FS.limbs16(one, i, L.take(i, L.carry(k, t, L.hi16(s)))), lo16_lt(one, h1, s), carry_limbs(one, h1, k, i, t, L.hi16(s), hj))
71
72# k limbs below 2^16 have a value below 2^(16 k)
73def limbs_lt(+one: Nat, +h1: {one == 1n : Nat}, k: Nat, ys: List<&2, Nat>, +h: {FS.limbs16(one, k, ys) == True{} : Bool}) -> {Nat.is_lt(LV.ev(ys), LV.pos(k, one)) == True{} : Bool}:
74  match k ys:
75    case 0n Nil{}:
76      lt_one(one, h1)
77    case 0n y <> t:
78      Empty.absurd({Nat.is_lt(LV.ev(y <> t), LV.pos(0n, one)) == True{} : Bool}, Lg.false_true(h))
79    case 1n+i Nil{}:
80      Empty.absurd({Nat.is_lt(LV.ev([]), LV.pos(1n+i, one)) == True{} : Bool}, Lg.false_true(h))
81    case 1n+ +i +y <> +t:
82      +hy = Lg.and_left(Nat.is_lt(y, C.shift(16n, one)), FS.limbs16(one, i, t), h)
83      +ht = Lg.and_right(Nat.is_lt(y, C.shift(16n, one)), FS.limbs16(one, i, t), h)
84      I.digit_lt(16n, one, h1, y, LV.ev(t), LV.pos(i, one), hy, limbs_lt(one, h1, i, t, ht))
85
86# the first j limbs of a list whose first n >= j limbs are fine
87def limbs_take(+one: Nat, n: Nat, j: Nat, +xs: List<&2, Nat>, +hj: {Nat.is_le(j, n) == True{} : Bool}, +h: {FS.limbs16(one, n, L.take(n, xs)) == True{} : Bool}) -> {FS.limbs16(one, j, L.take(j, xs)) == True{} : Bool}:
88  match n j xs:
89    case 0n 0n _:
90      {==}
91    case 0n 1n+i _:
92      Empty.absurd({FS.limbs16(one, 1n+i, L.take(1n+i, xs)) == True{} : Bool}, Lg.false_true(hj))
93    case 1n+k 0n _:
94      {==}
95    case 1n+k 1n+i Nil{}:
96      Empty.absurd({FS.limbs16(one, 1n+i, L.take(1n+i, [])) == True{} : Bool}, Lg.false_true(h))
97    case 1n+ +k 1n+ +i +x <> +t:
98      +hx = Lg.and_left(Nat.is_lt(x, C.shift(16n, one)), FS.limbs16(one, k, L.take(k, t)), h)
99      +ht = Lg.and_right(Nat.is_lt(x, C.shift(16n, one)), FS.limbs16(one, k, L.take(k, t)), h)
100      Lg.and_intro(Nat.is_lt(x, C.shift(16n, one)), FS.limbs16(one, i, L.take(i, t)), hx, limbs_take(one, k, i, t, hj, ht))