OKVS with u64 arithmetic add

[lzjluzijie]

I'm trying to use OKVS for u64 type. The default helper works normally with xor operation of u64:

using ValueType = u64;

template<typename T>
struct Helper {
  using value_type = T;
  using iterator = T *;
  using const_iterator = const T *;

  // mutable version of value_type
  using mut_value_type = std::remove_const_t<value_type>;
  using mut_iterator = mut_value_type *;

  // internal mask used to multiply a value with a bit.
  // Assumes the zero bit string is the zero element.
  std::array<mut_value_type, 2> zeroOneMask;

  Helper() {
    memset(&zeroOneMask[0], 0, sizeof(T));
    memset(&zeroOneMask[1], -1, sizeof(T));
  }

  Helper(const Helper &) = default;

  // return a element that the user can use.
  inline static mut_value_type newElement() { return {}; }

  // return the iterator for the return type of newElement().
  mut_iterator asPtr(mut_value_type &t) { return &t; }

  // return a vector of elements that the user can use.
  inline static PxVector<mut_value_type> newVec(u64 size) { return {size}; }

  // assign the src to the dst, ie *dst = *src.
  inline static void assign(mut_iterator dst, const_iterator src) { *dst = *src; }

  // add the src to the dst, ie *dst += *src.
  inline static void add(mut_iterator dst, const_iterator src1) { *dst = *dst ^ *src1; }

  // multiply src1 with m and add the result to the dst, ie *dst += (*src) * m.
  inline static void multAdd(mut_iterator dst, const_iterator src1, const block &m) {
    if constexpr (std::is_same<block, mut_value_type>::value)
      *dst = *dst ^ src1->gf128Mul(m);
    else
      throw std::runtime_error("the gf128 dense encoding is only implemented for block type. " LOCATION);
  }

  // multiply src1 with bit and add the result to the dst, ie *dst += (*src) * bit.
  inline void multAdd(mut_iterator dst, const_iterator src1, const u8 &bit) {
    assert(bit < 2);
    *dst = *dst ^ (*src1 & zeroOneMask[bit]);
  }

  // return the iterator plus the given number of rows
  inline static auto iterPlus(const_iterator p, u64 i) { return p + i; }

  // return the iterator plus the given number of rows
  inline static auto iterPlus(mut_iterator p, u64 i) { return p + i; }

  // randomize the given element.
  inline static void randomize(mut_iterator p, oc::PRNG &prng) {
    prng.get(p, 1);
  }


  inline static auto eq(iterator p0, iterator p1) {
    return *p0 == *p1;
  }
};

void paxos() {
  u64 n = 1 << 15;
  u64 w = 3;

  PRNG prng(oc::sysRandomSeed());
  block seed1 = prng.get();

  Helper<ValueType> helper;

  Paxos<u32> paxos;
  Paxos<u32> paxos2;
  paxos.init(n, w, 40, PaxosParam::Binary, seed1);
  paxos2.init(n, w, 40, PaxosParam::Binary, seed1);

  std::vector<block> items(n);
  std::vector<ValueType> values0(n), values1(n), values2(n);
  std::vector<ValueType> p0(paxos.size()), p1(paxos.size()), p2(paxos.size());

  prng.get(items.data(), items.size());
  prng.get(values0.data(), values0.size());
  prng.get(values1.data(), values1.size()); {
    paxos.setInput(items);
    PxVector<const ValueType> V(values0);
    PxVector<ValueType> P(p0);
    paxos.encode(V, P, helper, nullptr);
  } {
    paxos.setInput(items);
    PxVector<const ValueType> V(values1);
    PxVector<ValueType> P(p1);
    paxos.encode(V, P, helper, nullptr);
  }

  u64 lim = 227;
  for (u64 i = 0; i < lim; i++) {
    items[i] = prng.get();
  }
  for (u64 i = 0; i < paxos.size(); i++) {
    p2[i] = p0[i] ^ p1[i];
  }
  paxos2.decode<ValueType>(items, values2, p2);

  for (u64 i = 0; i < n; i++) {
    if (i < lim) {
      if (values2[i] == (values0[i] ^ values1[i])) {
        throw RTE_LOC;
      }
    } else {
      if ((values0[i] ^ values1[i]) != values2[i]) {
        std::printf("%lu\n", i);
        throw RTE_LOC;
      }
    }
  }

  std::printf("paxos ok\n");
}

However, I try to use the arithmetic add, the code didn't work:

using ValueType = u64;

template<typename T>
struct Helper {
  using value_type = T;
  using iterator = T *;
  using const_iterator = const T *;

  // mutable version of value_type
  using mut_value_type = std::remove_const_t<value_type>;
  using mut_iterator = mut_value_type *;

  // return a element that the user can use.
  inline static mut_value_type newElement() { return {}; }

  // return the iterator for the return type of newElement().
  mut_iterator asPtr(mut_value_type &t) { return &t; }

  // return a vector of elements that the user can use.
  inline static PxVector<mut_value_type> newVec(u64 size) { return {size}; }

  // assign the src to the dst, ie *dst = *src.
  inline static void assign(mut_iterator dst, const_iterator src) { *dst = *src; }

  // add the src to the dst, ie *dst += *src.
  inline static void add(mut_iterator dst, const_iterator src1) { *dst = *dst + *src1; }

  // multiply src1 with m and add the result to the dst, ie *dst += (*src) * m.
  inline static void multAdd(mut_iterator dst, const_iterator src1, const block &m) {
    throw std::runtime_error("the gf128 dense encoding is only implemented for block type. " LOCATION);
  }

  // multiply src1 with bit and add the result to the dst, ie *dst += (*src) * bit.
  inline void multAdd(mut_iterator dst, const_iterator src1, const u8 &bit) {
    assert(bit < 2);
    *dst = *dst + (*src1 * bit);
  }

  // return the iterator plus the given number of rows
  inline static auto iterPlus(const_iterator p, u64 i) { return p + i; }

  // return the iterator plus the given number of rows
  inline static auto iterPlus(mut_iterator p, u64 i) { return p + i; }

  // randomize the given element.
  inline static void randomize(mut_iterator p, oc::PRNG &prng) {
    prng.get(p, 1);
  }

  inline static auto eq(iterator p0, iterator p1) {
    return *p0 == *p1;
  }
};

void paxos() {
  u64 n = 1 << 15;
  u64 w = 3;

  PRNG prng(oc::sysRandomSeed());
  block seed1 = prng.get();

  Helper<ValueType> helper;

  Paxos<u32> paxos;
  Paxos<u32> paxos2;
  paxos.init(n, w, 40, PaxosParam::Binary, seed1);
  paxos2.init(n, w, 40, PaxosParam::Binary, seed1);

  std::vector<block> items(n);
  std::vector<ValueType> values0(n), values1(n), values2(n);
  std::vector<ValueType> p0(paxos.size()), p1(paxos.size()), p2(paxos.size());

  prng.get(items.data(), items.size());
  prng.get(values0.data(), values0.size());
  prng.get(values1.data(), values1.size());

  // encode p0
  {
    paxos.setInput(items);
    PxVector<const ValueType> V(values0);
    PxVector<ValueType> P(p0);
    paxos.encode(V, P, helper, nullptr);
  }

  // encode p1
  {
    paxos.setInput(items);
    PxVector<const ValueType> V(values1);
    PxVector<ValueType> P(p1);
    paxos.encode(V, P, helper, nullptr);
  }

  u64 lim = 227;
  for (u64 i = 0; i < lim; i++) {
    items[i] = prng.get();
  }
  for (u64 i = 0; i < paxos.size(); i++) {
    p2[i] = p0[i] + p1[i];
  }
  paxos2.decode<ValueType>(items, values2, p2);

  for (u64 i = 0; i < n; i++) {
    if (i < lim) {
      if (values2[i] == (values0[i] + values1[i])) {
        throw RTE_LOC;
      }
    } else {
      if ((values0[i] + values1[i]) != values2[i]) {
        std::printf("%lu\n", i);
        throw RTE_LOC;
      }
    }
  }

  std::printf("paxos ok\n");
}

as we got values0[i] + values1[i]) != values2[i]. I think the OKVS requires the ValueType to be a field, so I also tried prime field:

u64 p = 10007;
using ValueType = u64;

template<typename T>
struct Helper {
  using value_type = T;
  using iterator = T *;
  using const_iterator = const T *;

  // mutable version of value_type
  using mut_value_type = std::remove_const_t<value_type>;
  using mut_iterator = mut_value_type *;

  // return a element that the user can use.
  inline static mut_value_type newElement() { return {}; }

  // return the iterator for the return type of newElement().
  mut_iterator asPtr(mut_value_type &t) { return &t; }

  // return a vector of elements that the user can use.
  inline static PxVector<mut_value_type> newVec(u64 size) { return {size}; }

  // assign the src to the dst, ie *dst = *src.
  inline static void assign(mut_iterator dst, const_iterator src) { *dst = *src; }

  // add the src to the dst, ie *dst += *src.
  inline static void add(mut_iterator dst, const_iterator src1) { *dst = (*dst + *src1) % p; }

  // multiply src1 with m and add the result to the dst, ie *dst += (*src) * m.
  inline static void multAdd(mut_iterator dst, const_iterator src1, const block &m) {
    throw std::runtime_error("the gf128 dense encoding is only implemented for block type. " LOCATION);
  }

  // multiply src1 with bit and add the result to the dst, ie *dst += (*src) * bit.
  inline void multAdd(mut_iterator dst, const_iterator src1, const u8 &bit) {
    assert(bit < 2);
    *dst = (*dst + (*src1 * bit)) % p;
  }

  // return the iterator plus the given number of rows
  inline static auto iterPlus(const_iterator p, u64 i) { return p + i; }

  // return the iterator plus the given number of rows
  inline static auto iterPlus(mut_iterator p, u64 i) { return p + i; }

  // randomize the given element.
  inline static void randomize(mut_iterator p, oc::PRNG &prng) {
    prng.get(p, 1);
  }

  inline static auto eq(iterator p0, iterator p1) {
    return (*p0 % p) == (*p1 % p);
  }
};

void paxos() {
  u64 n = 1 << 15;
  u64 w = 3;

  PRNG prng(oc::sysRandomSeed());
  block seed1 = prng.get();

  Helper<ValueType> helper;

  Paxos<u32> paxos;
  Paxos<u32> paxos2;
  paxos.init(n, w, 40, PaxosParam::Binary, seed1);
  paxos2.init(n, w, 40, PaxosParam::Binary, seed1);

  std::vector<block> items(n);
  std::vector<ValueType> values0(n), values1(n), values2(n);
  std::vector<ValueType> p0(paxos.size()), p1(paxos.size()), p2(paxos.size());

  prng.get(items.data(), items.size());
  prng.get(values0.data(), values0.size());
  prng.get(values1.data(), values1.size());

  for (u64 i = 0; i < n; i++) {
    values0[i] = values0[i] % p;
    values1[i] = values1[i] % p;
  }

  // encode p0
  {
    paxos.setInput(items);
    PxVector<const ValueType> V(values0);
    PxVector<ValueType> P(p0);
    paxos.encode(V, P, helper, nullptr);
  }

  // encode p1
  {
    paxos.setInput(items);
    PxVector<const ValueType> V(values1);
    PxVector<ValueType> P(p1);
    paxos.encode(V, P, helper, nullptr);
  }

  u64 lim = 227;
  for (u64 i = 0; i < lim; i++) {
    items[i] = prng.get();
  }
  for (u64 i = 0; i < paxos.size(); i++) {
    p2[i] = (p0[i] + p1[i]) % p;
  }
  paxos2.decode<ValueType>(items, values2, p2);

  for (u64 i = 0; i < n; i++) {
    if (i < lim) {
      if ((values2[i] % p) == ((values0[i] + values1[i]) % p)) {
        throw RTE_LOC;
      }
    } else {
      if (((values0[i] + values1[i]) % p) != (values2[i] % p)) {
        std::printf("%lu\n", i);
        throw RTE_LOC;
      }
    }
  }

  std::printf("paxos ok\n");
}

But I got the same error. I think I might be missing the inverse part, but the helper does not have a inverse function. Could you give me some instructions. Thank you!

[ladnir]

OK, I'll take a look

[ladnir]

ok, so it seems slightly non trivial to change the field from anything that is not characteristic 2.

In various places its assumed that minus is the same as plus. To make it work with say addition mod 2^64, you would need to update the code accordingly. The main algorithm is described here https://github.com/Visa-Research/volepsi/blob/main/volePSI/PaxosImpl.h#L1334

You would need to add a helper.minus function and then update the code accordingly. Also, when inverting the dense E region, you need to invert over the new group, e.g. Z_{2^64}. The binary version is what I would start with as that's probably easier.

[lzjluzijie]

Makes sense to me, I will try to make it general and send a PR later