~/bend-docscommunity

proofs/crypto/secp256k1/fwrap.bend source

proofs/crypto/secp256k1/fwrap.bend on the hub · documented module

# GENERATED by tools/generators/rw.py from ../../../tools/generators/secp256k1_hand/fwrap.src; edit the .srcimport Baseimport ../../../spec/lib/common.bend as Cimport ../../../spec/crypto/secp256k1/field.bend as FSimport ../../../src/crypto/secp256k1/limbs.bend as Limport ../../../src/crypto/secp256k1/field.bend as Fimport ../../../src/crypto/secp256k1/scalar.bend as Simport ../../lib/nat.bend as Nimport ../../lib/lemmas/proofs/nat_algebra.bend as NAimport ../../math/typed/width.bend as WWimport ./semiring.bend as SRimport ./limbs.bend as LVimport ./fprot.bend as FRimport ./consts.bend as Kimport ./listops.bend as LO# The tests of src/crypto/secp256k1/field.bend and scalar.bend (zero,# equality, parity, a < p, a < n, a > n / 2) are the specification's tests# on the values.# ---- GF(p) ----def is_zero_f(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>) -> {F.is_zero(a) == Nat.is_eq(FS.value(one, a), 0n) : Bool}:  %Equal.sym(Bool, L.is_zero(a), Nat.is_eq(LV.ev(a), 0n), LO.is_zero_v(a)) : {_ == Nat.is_eq(FS.value(one, a), 0n) : Bool}  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Nat.is_eq(LV.ev(a), 0n) == Nat.is_eq(_, 0n) : Bool}  {==}def eq_f(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>, +b: List<&2, Nat>, +ha: {FS.limbs16(one, 16n, a) == True{} : Bool}, +hb: {FS.limbs16(one, 16n, b) == True{} : Bool}) -> {F.eq(a, b) == Nat.is_eq(FS.value(one, a), FS.value(one, b)) : Bool}:  %Equal.sym(Bool, F.eq(a, b), L.eq(a, b), FR.f_eq(a, b)) : {_ == Nat.is_eq(FS.value(one, a), FS.value(one, b)) : Bool}  %Equal.sym(Bool, L.eq(a, b), Nat.is_eq(LV.ev(a), LV.ev(b)), LO.eq_v(one, h1, a, b, ha, hb)) : {_ == Nat.is_eq(FS.value(one, a), FS.value(one, b)) : Bool}  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Nat.is_eq(LV.ev(a), LV.ev(b)) == Nat.is_eq(_, FS.value(one, b)) : Bool}  %Equal.sym(Nat, FS.value(one, b), LV.ev(b), LV.ev_value(one, h1, b)) : {Nat.is_eq(LV.ev(a), LV.ev(b)) == Nat.is_eq(LV.ev(a), _) : Bool}  {==}def parity_f(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>) -> {F.parity(a) == Nat.mod(FS.value(one, a), 2n) : Nat}:  %Equal.sym(Nat, Nat.mod(L.hd0(a), 2n), Nat.mod(LV.ev(a), 2n), LO.parity_v(a)) : {_ == Nat.mod(FS.value(one, a), 2n) : Nat}  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Nat.mod(LV.ev(a), 2n) == Nat.mod(_, 2n) : Nat}  {==}def lt_p_f(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>) -> {F.lt_p(a) == Nat.is_lt(FS.value(one, a), FS.prime(one)) : Bool}:  %Equal.sym(Bool, L.ltm(F.c(), a), Nat.is_lt(LV.ev(a), 1n+K.pp(one)), LO.ltm_vv(one, h1, K.pp(one), F.c(), K.hm_p(one, h1), a)) : {_ == Nat.is_lt(FS.value(one, a), FS.prime(one)) : Bool}  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Nat.is_lt(LV.ev(a), 1n+K.pp(one)) == Nat.is_lt(_, FS.prime(one)) : Bool}  %Equal.sym(Nat, FS.prime(one), 1n+K.pp(one), K.prime_eq(one, h1)) : {Nat.is_lt(LV.ev(a), 1n+K.pp(one)) == Nat.is_lt(LV.ev(a), _) : Bool}  {==}# ---- Z / n ----def is_zero_s(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>) -> {S.is_zero(a) == Nat.is_eq(FS.value(one, a), 0n) : Bool}:  %Equal.sym(Bool, L.is_zero(a), Nat.is_eq(LV.ev(a), 0n), LO.is_zero_v(a)) : {_ == Nat.is_eq(FS.value(one, a), 0n) : Bool}  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Nat.is_eq(LV.ev(a), 0n) == Nat.is_eq(_, 0n) : Bool}  {==}def eq_s(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>, +b: List<&2, Nat>, +ha: {FS.limbs16(one, 16n, a) == True{} : Bool}, +hb: {FS.limbs16(one, 16n, b) == True{} : Bool}) -> {S.eq(a, b) == Nat.is_eq(FS.value(one, a), FS.value(one, b)) : Bool}:  %Equal.sym(Bool, S.eq(a, b), L.eq(a, b), FR.s_eq(a, b)) : {_ == Nat.is_eq(FS.value(one, a), FS.value(one, b)) : Bool}  %Equal.sym(Bool, L.eq(a, b), Nat.is_eq(LV.ev(a), LV.ev(b)), LO.eq_v(one, h1, a, b, ha, hb)) : {_ == Nat.is_eq(FS.value(one, a), FS.value(one, b)) : Bool}  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Nat.is_eq(LV.ev(a), LV.ev(b)) == Nat.is_eq(_, FS.value(one, b)) : Bool}  %Equal.sym(Nat, FS.value(one, b), LV.ev(b), LV.ev_value(one, h1, b)) : {Nat.is_eq(LV.ev(a), LV.ev(b)) == Nat.is_eq(LV.ev(a), _) : Bool}  {==}def lt_n_s(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>) -> {S.lt_n(a) == Nat.is_lt(FS.value(one, a), FS.order(one)) : Bool}:  %Equal.sym(Bool, L.ltm(S.c(), a), Nat.is_lt(LV.ev(a), 1n+K.np(one)), LO.ltm_vv(one, h1, K.np(one), S.c(), K.hm_n(one, h1), a)) : {_ == Nat.is_lt(FS.value(one, a), FS.order(one)) : Bool}  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Nat.is_lt(LV.ev(a), 1n+K.np(one)) == Nat.is_lt(_, FS.order(one)) : Bool}  %Equal.sym(Nat, FS.order(one), 1n+K.np(one), K.order_eq(one, h1)) : {Nat.is_lt(LV.ev(a), 1n+K.np(one)) == Nat.is_lt(LV.ev(a), _) : Bool}  {==}# a leading digit one largerdef dig1(+one: Nat, +h1: {one == 1n : Nat}, +d: Nat, +r: Nat) -> {Nat.add(Nat.mul(one, 1n+d), r) == 1n+Nat.add(Nat.mul(one, d), r) : Nat}:  %Equal.sym(Nat, one, 1n, h1) : {Nat.add(Nat.mul(_, 1n+d), r) == 1n+Nat.add(Nat.mul(one, d), r) : Nat}  %Equal.sym(Nat, one, 1n, h1) : {Nat.add(Nat.mul(1n, 1n+d), r) == 1n+Nat.add(Nat.mul(_, d), r) : Nat}  %Equal.sym(Nat, 1n+d, Nat.add(d, 1n), SR.succ_add(1n, d)) : {Nat.add(Nat.mul(1n, _), r) == 1n+Nat.add(Nat.mul(1n, d), r) : Nat}  %Equal.sym(Nat, Nat.mul(1n, Nat.add(d, 1n)), Nat.add(d, 1n), SR.one_mul(Nat.add(d, 1n))) : {Nat.add(_, r) == 1n+Nat.add(Nat.mul(1n, d), r) : Nat}  %Equal.sym(Nat, Nat.add(Nat.add(d, 1n), r), Nat.add(d, Nat.add(1n, r)), NA.add_assoc(d, 1n, r)) : {_ == 1n+Nat.add(Nat.mul(1n, d), r) : Nat}  %Equal.sym(Nat, Nat.add(1n, r), Nat.add(r, 1n), NA.add_comm(1n, r)) : {Nat.add(d, _) == 1n+Nat.add(Nat.mul(1n, d), r) : Nat}  %Equal.sym(Nat, Nat.mul(1n, d), d, SR.one_mul(d)) : {Nat.add(d, Nat.add(r, 1n)) == 1n+Nat.add(_, r) : Nat}  %Equal.sym(Nat, 1n+Nat.add(d, r), Nat.add(Nat.add(d, r), 1n), SR.succ_add(1n, Nat.add(d, r))) : {Nat.add(d, Nat.add(r, 1n)) == _ : Nat}  %Equal.sym(Nat, Nat.add(Nat.add(d, r), 1n), Nat.add(d, Nat.add(r, 1n)), NA.add_assoc(d, r, 1n)) : {Nat.add(d, Nat.add(r, 1n)) == _ : Nat}  {==}# n + 1 + (2^256 - n - 1) = 2^256def hm_n1(+one: Nat, +h1: {one == 1n : Nat}) -> {Nat.add(1n+(1n+K.np(one)), FS.value(one, S.cm1())) == C.shift(256n, one) : Nat}:  +r = C.shift(16n, FS.digits(one, [12233n, 41331n, 16429n, 24516n, 20663n, 8985n, 17745n, 1n]))  %Equal.sym(Nat, C.shift(256n, one), Nat.add(1n+K.np(one), FS.cn(one)), Equal.sym(Nat, Nat.add(1n+K.np(one), FS.cn(one)), C.shift(256n, one), K.hm_n(one, h1))) : {Nat.add(1n+1n+K.np(one), Nat.add(Nat.mul(one, 48830n), r)) == _ : Nat}  %Equal.sym(Nat, Nat.add(Nat.mul(one, 48831n), r), 1n+Nat.add(Nat.mul(one, 48830n), r), dig1(one, h1, 48830n, r)) : {Nat.add(1n+1n+K.np(one), Nat.add(Nat.mul(one, 48830n), r)) == Nat.add(1n+K.np(one), _) : Nat}  %Equal.sym(Nat, 1n+K.np(one), Nat.add(K.np(one), 1n), SR.succ_add(1n, K.np(one))) : {Nat.add(1n+_, Nat.add(Nat.mul(one, 48830n), r)) == Nat.add(1n+K.np(one), 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}  %Equal.sym(Nat, 1n+Nat.add(K.np(one), 1n), Nat.add(Nat.add(K.np(one), 1n), 1n), SR.succ_add(1n, Nat.add(K.np(one), 1n))) : {Nat.add(_, Nat.add(Nat.mul(one, 48830n), r)) == Nat.add(1n+K.np(one), 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}  %Equal.sym(Nat, Nat.add(Nat.add(K.np(one), 1n), 1n), Nat.add(K.np(one), Nat.add(1n, 1n)), NA.add_assoc(K.np(one), 1n, 1n)) : {Nat.add(_, Nat.add(Nat.mul(one, 48830n), r)) == Nat.add(1n+K.np(one), 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}  %Equal.sym(Nat, Nat.add(1n, 1n), 2n, {==}) : {Nat.add(Nat.add(K.np(one), _), Nat.add(Nat.mul(one, 48830n), r)) == Nat.add(1n+K.np(one), 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}  %Equal.sym(Nat, Nat.add(Nat.add(K.np(one), 2n), Nat.add(Nat.mul(one, 48830n), r)), Nat.add(K.np(one), Nat.add(2n, Nat.add(Nat.mul(one, 48830n), r))), NA.add_assoc(K.np(one), 2n, Nat.add(Nat.mul(one, 48830n), r))) : {_ == Nat.add(1n+K.np(one), 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}  %Equal.sym(Nat, Nat.add(2n, Nat.add(Nat.mul(one, 48830n), r)), Nat.add(Nat.mul(one, 48830n), Nat.add(2n, r)), NA.add_swap(2n, Nat.mul(one, 48830n), r)) : {Nat.add(K.np(one), _) == Nat.add(1n+K.np(one), 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}  %Equal.sym(Nat, Nat.add(2n, r), Nat.add(r, 2n), NA.add_comm(2n, r)) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), _)) == Nat.add(1n+K.np(one), 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}  %Equal.sym(Nat, 1n+K.np(one), Nat.add(K.np(one), 1n), SR.succ_add(1n, K.np(one))) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 2n))) == Nat.add(_, 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}  %Equal.sym(Nat, 1n+Nat.add(Nat.mul(one, 48830n), r), Nat.add(Nat.add(Nat.mul(one, 48830n), r), 1n), SR.succ_add(1n, Nat.add(Nat.mul(one, 48830n), r))) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 2n))) == Nat.add(Nat.add(K.np(one), 1n), _) : Nat}  %Equal.sym(Nat, Nat.add(Nat.add(Nat.mul(one, 48830n), r), 1n), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 1n)), NA.add_assoc(Nat.mul(one, 48830n), r, 1n)) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 2n))) == Nat.add(Nat.add(K.np(one), 1n), _) : Nat}  %Equal.sym(Nat, Nat.add(Nat.add(K.np(one), 1n), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 1n))), Nat.add(K.np(one), Nat.add(1n, Nat.add(Nat.mul(one, 48830n), Nat.add(r, 1n)))), NA.add_assoc(K.np(one), 1n, Nat.add(Nat.mul(one, 48830n), Nat.add(r, 1n)))) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 2n))) == _ : Nat}  %Equal.sym(Nat, Nat.add(1n, Nat.add(Nat.mul(one, 48830n), Nat.add(r, 1n))), Nat.add(Nat.mul(one, 48830n), Nat.add(1n, Nat.add(r, 1n))), NA.add_swap(1n, Nat.mul(one, 48830n), Nat.add(r, 1n))) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 2n))) == Nat.add(K.np(one), _) : Nat}  %Equal.sym(Nat, Nat.add(1n, Nat.add(r, 1n)), Nat.add(r, Nat.add(1n, 1n)), NA.add_swap(1n, r, 1n)) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 2n))) == Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), _)) : Nat}  %Equal.sym(Nat, Nat.add(1n, 1n), 2n, {==}) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 2n))) == Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, _))) : Nat}  {==}# not (x < m + 1) is m < xdef nlt(x: Nat, m: Nat) -> {Bool.not(Nat.is_lt(x, 1n+m)) == Nat.is_lt(m, x) : Bool}:  match x m:    case 0n _:      Equal.sym(Bool, Nat.is_lt(m, 0n), False{}, N.not_lt_zero(m))    case 1n+y 0n:      %Equal.sym(Bool, Nat.is_lt(y, 0n), False{}, N.not_lt_zero(y)) : {Bool.not(_) == True{} : Bool}      {==}    case 1n+y 1n+k:      nlt(y, k)def is_high_s(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>) -> {S.is_high(a) == Nat.is_lt(FS.order(one), Nat.double(FS.value(one, a))) : Bool}:  %Equal.sym(Bool, L.ltm(S.cm1(), L.scal(2n, a)), Nat.is_lt(LV.ev(L.scal(2n, a)), 1n+1n+K.np(one)), LO.ltm_vv(one, h1, 1n+K.np(one), S.cm1(), hm_n1(one, h1), L.scal(2n, a))) : {Bool.not(_) == Nat.is_lt(FS.order(one), Nat.double(FS.value(one, a))) : Bool}  %Equal.sym(Nat, LV.ev(L.scal(2n, a)), Nat.mul(LV.ev(a), 2n), LV.scal_v(2n, a)) : {Bool.not(Nat.is_lt(_, 1n+1n+K.np(one))) == Nat.is_lt(FS.order(one), Nat.double(FS.value(one, a))) : Bool}  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Bool.not(Nat.is_lt(Nat.mul(LV.ev(a), 2n), 1n+1n+K.np(one))) == Nat.is_lt(FS.order(one), Nat.double(_)) : Bool}  %Equal.sym(Bool, Bool.not(Nat.is_lt(Nat.mul(LV.ev(a), 2n), 1n+1n+K.np(one))), Nat.is_lt(1n+K.np(one), Nat.mul(LV.ev(a), 2n)), nlt(Nat.mul(LV.ev(a), 2n), 1n+K.np(one))) : {_ == Nat.is_lt(FS.order(one), Nat.double(LV.ev(a))) : Bool}  %Equal.sym(Nat, FS.order(one), 1n+K.np(one), K.order_eq(one, h1)) : {Nat.is_lt(1n+K.np(one), Nat.mul(LV.ev(a), 2n)) == Nat.is_lt(_, Nat.double(LV.ev(a))) : Bool}  %Equal.sym(Nat, Nat.double(LV.ev(a)), Nat.mul(2n, LV.ev(a)), NA.double_mul(LV.ev(a))) : {Nat.is_lt(1n+K.np(one), Nat.mul(LV.ev(a), 2n)) == Nat.is_lt(1n+K.np(one), _) : Bool}  %Equal.sym(Nat, Nat.mul(2n, LV.ev(a)), Nat.mul(LV.ev(a), 2n), NA.mul_comm(2n, LV.ev(a))) : {Nat.is_lt(1n+K.np(one), Nat.mul(LV.ev(a), 2n)) == Nat.is_lt(1n+K.np(one), _) : Bool}  {==}