cb-mpc/src/cbmpc/zk/zk_unknown_order.cpp at master · coinbase/cb-mpc · GitHub

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
#include <cbmpc/internal/crypto/ro.h>
#include <cbmpc/internal/zk/zk_paillier.h>
#include <cbmpc/internal/zk/zk_unknown_order.h>
namespace coinbase::zk {

void unknown_order_dl_t::prove(const bn_t& a, const bn_t& b, const mod_t& N, const int l, const bn_t& w, mem_t sid,
                               const uint64_t aux) {
  cb_assert(w.get_bits_count() <= l);
  int r_size = l + SEC_P_STAT + 1;

  bn_t gcd_test;
  MODULO(N) gcd_test = a * b;
  cb_assert(mod_t::coprime(gcd_test, N) && "unknown_order_dl_t::prove: gcd(a*b, N) != 1");

  bn_t R[SEC_P_COM];
  for (int i = 0; i < SEC_P_COM; i++) {
    z[i] = bn_t::rand_bitlen(r_size);
    MODULO(N) R[i] = a.pow(z[i]);
  }

  e = crypto::ro::hash_string(a, b, N, l, R, sid, aux).bitlen(SEC_P_COM);

  for (int i = 0; i < SEC_P_COM; i++) {
    if (coinbase::bits_t::get(e.data(), i)) z[i] = z[i] + w;
  }
}

error_t unknown_order_dl_t::verify(const bn_t& a, const bn_t& b, const mod_t& N, const int l, mem_t sid,
                                   uint64_t aux) const {
  crypto::vartime_scope_t vartime_scope;
  error_t rv = UNINITIALIZED_ERROR;

  if (l <= 0) return coinbase::error(E_CRYPTO, "unknown_order_dl_t::verify: l <= 0");
  if (e.size() != coinbase::bits_to_bytes(SEC_P_COM))
    return coinbase::error(E_CRYPTO, "unknown_order_dl_t::verify: invalid e size");

  // Ensure `b` is invertible mod N before attempting BN_mod_inverse (which asserts on failure).
  if (rv = coinbase::crypto::check_open_range(0, b, N))
    return coinbase::error(rv, "unknown_order_dl_t::verify: invalid b");
  if (!mod_t::coprime(b, N)) return coinbase::error(E_CRYPTO, "unknown_order_dl_t::verify: gcd(b, N) != 1");

  const int max_z_bits = l + SEC_P_STAT + 2;
  for (int i = 0; i < SEC_P_COM; i++) {
    if (z[i] < 0) return coinbase::error(E_CRYPTO, "unknown_order_dl_t::verify: z[i] < 0");
    if (z[i].get_bits_count() > max_z_bits)
      return coinbase::error(E_CRYPTO, "unknown_order_dl_t::verify: z[i] too large");
  }

  bn_t gcd_test;
  MODULO(N) gcd_test = a * b;
  if (!mod_t::coprime(gcd_test, N)) return coinbase::error(E_CRYPTO, "unknown_order_dl_t::verify: gcd(a*b, N) != 1");

  bn_t b_inv = N.inv(b);

  bn_t R_tag;
  MODULO(N) R_tag = a * b;

  bn_t R[SEC_P_COM];
  for (int i = 0; i < SEC_P_COM; i++) {
    MODULO(N) R[i] = a.pow(z[i]);
    if (coinbase::bits_t::get(e.data(), i)) MODULO(N) R[i] = R[i] * b_inv;

    MODULO(N) R_tag *= R[i];
  }

  buf_t e_tag = crypto::ro::hash_string(a, b, N, l, R, sid, aux).bitlen(SEC_P_COM);
  if (e != e_tag) {
    return coinbase::error(E_CRYPTO);
  }

  if (!mod_t::coprime(R_tag, N)) return coinbase::error(E_CRYPTO);
  return SUCCESS;
}

}  // namespace coinbase::zk