Latency grows with the number of GGM trees, aka O(T) about emp-zk HOT 5 CLOSED

Actually, why there will be T rounds in each thread? I thought there should be O(1) round in each thread and all threads are in parallel.

from emp-zk.

Let me correct that it would be T / threads rounds but still O(T).

The reason is that after splitting the job of T into each thread, each thread does the T / threads one by one.

for (auto i = start; i < end; ++i) {
	if(party == ALICE) {
		ggm_tree[i] = sparse_vector+i*leave_n;
		senders[i]->compute(ggm_tree[i], secret_share_x, triple_yz[i]);
		senders[i]->template send<OTPre<IO>>(ot, ios[start/width], i);
		if(is_malicious) senders[i]->consistency_check_msg_gen(check_VW_buf[i], ios[start/width]);
		ios[start/width]->flush();
	} else {
		recvers[i]->template recv<OTPre<IO>>(ot, ios[start/width], i);
		ggm_tree[i] = sparse_vector+i*leave_n;
		recvers[i]->compute(ggm_tree[i], triple_yz[i]);
		if(is_malicious) recvers[i]->consistency_check_msg_gen(check_chialpha_buf[i], check_VW_buf[i], ios[start/width], triple_yz[i]);
		ios[start/width]->flush();
	}
}

Ideally, this should still be O(1) round, since we should have the sender always be sending and the receiver always be receiving. In that case, the "round" disappears, as it is merely a stream.

But the problem is that, in this step:

if(is_malicious) senders[i]->consistency_check_msg_gen(check_VW_buf[i], ios[start/width]);

The sender is trying to receive something from the receiver, so the sender is now waiting for the receiver to get back.

For that to happen, the sender needs to wait for the receiver to receive the GGM tree data in

senders[i]->template send<OTPre<IO>>(ot, ios[start/width], i);

So the sender at least waits for the network latency. This is bad because recall that each thread does the job one by one, so each thread essentially waits for network_latency * T / threads.

from emp-zk.

In other words, ideally, when the sender finishes sending the GGM tree info, the sender should immediately go to the next tree and start computing the GGM tree, but now, the sender actually sits there and waits for the challenge for some RTT, not doing the next tree.

from emp-zk.

Adding for reference, in SPCOT SENDer side,

void consistency_check_msg_gen(__uint128_t& V, IO *io2) {
	block seed;

	/************/
	io2->recv_data(&seed, sizeof(block));
	/************/

	__uint128_t *chi = new __uint128_t[leave_n];
	Hash hash;
	__uint128_t digest = mod(_mm_extract_epi64(hash.hash_for_block(&seed, sizeof(block)), 0));
	uni_hash_coeff_gen(chi, digest, leave_n);

	// V = \sum{chi_i*v_i}
	V = vector_inn_prdt_sum_red(chi, (__uint128_t*)ggm_tree, leave_n);

	delete[] chi;
}

It is receiving.

from emp-zk.

You are right! got it!

from emp-zk.