Disjunction and Batched Disjunction for VOLE-based Zero Knowledge

This is the artifact for the paper: Batchman and Robin: Batched and Non-batched Branching for Interactive ZK to be presented on ACM CCS 2023.

Eprint link: https://eprint.iacr.org/2023/1257

Base

We acknowledge that our protocols based on QuickSilver repo available at: https://github.com/emp-toolkit/emp-zk. In particular, we fork the repo and develop based on it. We also tweak some emp libraries.

The file sha256.txt is obtained from https://homes.esat.kuleuven.be/~nsmart/MPC.

Set up Environments Including EMP Libraries

You can simply use sudo bash setup.sh. Or (step-by-step),

mkdir setup && cd setup
wget https://raw.githubusercontent.com/emp-toolkit/emp-readme/master/scripts/install.py
python[3] install.py --deps --tool --ot --zk
1. By default it will build for Release. -DCMAKE_BUILD_TYPE=[Release|Debug] option is also available.
2. No sudo? Change CMAKE_INSTALL_PREFIX.
cd ..
sudo apt install -y emacs iperf iftop clang

Install and Build

You can simply use bash install.sh. Or,

mkdir build && cd build && CC=clang CXX=clang++ cmake ../ && make && cp ../sha256.txt ./

We tested above methods already on a vanilla Ubuntu 22.04 machine.

Test

We have the following tests:

Boolean single disjunction:
1. bool_stack_mat_mul_RO: Boolean matrix multiplications, RO version.
2. bool_stack_mat_mul: Boolean matrix multiplications, Lemma 5.4 version.
3. bool_stack_sha256_RO: Repeating SHA2, RO version.
4. bool_stack_sha256: Repeating SHA2, Lemma 5.4 version.
Arithmetic single disjunction:
1. arith_stack_single_disj_matmul: Arithmetic matrix multiplications, Lemma 5.4 version.
2. arith_stack_single_disj_matmul_RO: Arithmetic matrix multiplications, RO version.
3. arith_stack_single_disj_matmul_online: Arithmetic matrix multiplications, Lemma 5.4 version, online cost only.
4. arith_stack_single_disj_matmul_online_RO: Arithmetic matrix multiplications, RO version, online cost only.
Arithmetic batched disjunction:
1. arith_stack_batched_matmul_v1: Arithmetic matrix multiplications, RO version.
Arithmetic baseline QuickSilver:
1. arith_unstack_single_disj_matmul: Arithmetic matrix multiplications, single disjunction, QuickSilver.
2. arith_unstack_single_disj_matmul_online: Arithmetic matrix multiplications, single disjunction, QuickSilver, online cost only.
3. arith_unstack_batched_disj_matmul: Arithmetic matrix multiplications, batched disjunction, QuickSilver.
Repeating single disjunction:
1. arith_stack_multi_single_disj_matmul: Arithmetic matrix multiplications, repeating single disjunction, Lemma 5.4 version.
2. arith_stack_multi_single_disj_matmul_RO: Arithmetic matrix multiplications, repeating single disjunction, RO version.

Note that the auto script will help you compile executable files (under build/bin/):

test_bool_stack_mat_mul_RO
test_bool_stack_sha256_RO
test_arith_stack_single_disj_matmul
test_arith_unstack_single_disj_matmul
test_arith_stack_batched_matmul_v1
test_arith_unstack_batched_disj_matmul
test_arith_stack_multi_single_disj_matmul

To obtain other executable files, please modify the file test/CMakeLists.txt.

How to Simulate Network Setting

We use tc command to simulate the network setting.

 DEV=lo
 
 sudo tc qdisc del dev $DEV root
 
 sudo tc qdisc add dev $DEV root handle 1: tbf rate 1Gbit burst 100000 limit 10000
 
 sudo tc qdisc add dev $DEV parent 1:1 handle 10: netem delay 2msec

Change DEV to the network card you need (e.g., ens5). Note that sudo tc qdisc del dev $DEV root needs to be executed before resetting the network. It is used to clean the tc setting.

Both P and V need to restrict the network, note that for 30ms latency, both parties should be set to delay 15msec.

You can use iperf to test the network throughput. Namely:

P: iperf -s

V: iperf -c [ip addr]

You can use ping to test the network latency. Namely:

V: ping [ip addr]

How to test the Comm. in the paper?

We tested it using linux command iftop e.g., on the P's machine, execute: