ZK Bool proof randomly fails when computing the AND operator

[nuno-faria]

When computing the AND operator with ZK Bool (for example, as a result of multiplications with Integers), the proof sometimes fails. More specifically, when the function andgate_correctness_check_manage is called, which adds the error emp_zk_bool AND batch check.

Here's a reproducible script, based on the test/bool/example.cpp test:

#include "emp-tool/emp-tool.h"
#include <emp-zk/emp-zk.h>
#include <iostream>
using namespace emp;
using namespace std;

int port, party;
const int threads = 10;

void test_circuit_zk(BoolIO<NetIO> *ios[threads], int party) {
  setup_zk_bool<BoolIO<NetIO>>(ios, threads, party);

  for (int i = 0; i < 1000000; i++) {
    Integer a(64, i, ALICE);
    Integer b(64, i, ALICE);
    Integer c = a * b;

    // print the error(s) when the proof fails
    if (CheatRecord::cheated()) {
      std::cout << "Failed at index " << i << std::endl;
      for (const auto& message: CheatRecord::message) {
        std::cout << message << std::endl;
      }
      break;
    }
  }

  bool cheat = finalize_zk_bool<BoolIO<NetIO>>();
  if (cheat)
    error("cheat!\n");
}

// unchanged
int main(int argc, char **argv) {
  parse_party_and_port(argv, &party, &port);
  BoolIO<NetIO> *ios[threads];
  for (int i = 0; i < threads; ++i)
    ios[i] = new BoolIO<NetIO>(
        new NetIO(party == ALICE ? nullptr : "127.0.0.1", port + i),
        party == ALICE);

  test_circuit_zk(ios, party);

  for (int i = 0; i < threads; ++i) {
    delete ios[i]->io;
    delete ios[i];
  }
  return 0;
}

There doesn't appear to be a pattern with this error. Here are some cases where it happened:

...
Failed at index 847341
emp_zk_bool AND batch check
cheat!

...
Failed at index 245248
emp_zk_bool AND batch check
cheat!

...
Failed at index 345600
emp_zk_bool AND batch check
cheat!

And here is the stack trace when the error occurs:

#0  CheatRecord::put (s="emp_zk_bool AND batch check") at /emp-zk/emp-zk/emp-zk-bool/emp-zk-bool.cpp:4
#1  0x0000555555595afc in OSTriple<emp::BoolIO<emp::NetIO> >::andgate_correctness_check_manage (this=this@entry=0x55555563b660) at /emp-zk/emp-zk/emp-zk-bool/ostriple.h:206
#2  0x0000555555595d8e in OSTriple<emp::BoolIO<emp::NetIO> >::auth_compute_and(long long __vector(2), long long __vector(2)) (b=..., a=..., this=0x55555563b660) at /emp-zk/emp-zk/emp-zk-bool/ostriple.h:119
#3  ZKBoolCircExec<emp::BoolIO<emp::NetIO> >::and_gate(long long __vector(2) const&, long long __vector(2) const&) (this=<optimized out>, a=..., b=...) at /emp-zk/emp-zk/emp-zk-bool/zk_bool_circuit_exec.h:16
#4  0x0000555555570bdb in emp::Bit::operator& (rhs=..., this=<optimized out>) at /usr/local/include/emp-tool/circuits/bit.hpp:38
#5  emp::mul_full (dest=0x5555555b7e40, op1=0x5555555cd950, op2=<optimized out>, size=<optimized out>) at /usr/local/include/emp-tool/circuits/integer.hpp:66
#6  0x000055555556c7cd in emp::Integer::operator* (rhs=..., this=0x7fffffffdc60) at /usr/local/include/emp-tool/circuits/integer.hpp:364
#7  test_circuit_zk (ios=ios@entry=0x7fffffffdf60, party=<optimized out>) at /emp-zk/test/bool/example.cpp:16
#8  0x000055555556a603 in main (argc=<optimized out>, argv=<optimized out>) at /emp-zk/test/bool/example.cpp:42

It's worth noting that the error is relatively rare, so the script might need to be called more than once to reproduce it.

Details:

• OS: Ubuntu 24.04 LTS (amd64)
• EMP libraries installed with python3 install.py --deps --tool --ot --zk
• Compiler: g++ (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
• LibSSL: libssl-dev:amd64 3.0.13-0ubuntu3.4 amd64