I talked with some ZKP experts, and the problem with the 1e6 overhead is that you need to generate the proof for each token in context, which adds several OOMs (e.g., 4 OOMs with avg. 10k context). Apparently there are forthcoming solutions to this though.
Why do we need to generate the proof for each token in the context? To be clear, I’m thinking of each decode step as a program that takes inputs = (kv_cache, input_tokens)and returns outputs = (new_keys_and_values, new_token). The prover publishes hashes of all keys and values. Then the verifier samples a decode step at random, and the prover must produce a ZKP that outputs = P(inputs).
Writing it this way, though, I see that I made an error in my previous estimate for the amount of covert communication the prover can perform without getting caught. I’d assumed that, for each fraudulent decode step, the prover can send one token’s worth of covert information out of the rack. I realize now that the correct amount of information is the size of outputs, which is dominated by new_keys_and_values. ChatGPT estimates new_keys_and_values is around 30kB for Kimi K3, which is ~4 OOMs larger than new_token. So, assuming 1e6 ZKP overhead as before, and 0.1% of compute set aside for producing ZKPs, the total covert communication volume is tens of terabytes (not gigabytes, as I claimed in the OP). Still doesn’t seem too bad to me.
Why do we need to generate the proof for each token in the context? To be clear, I’m thinking of each decode step as a program that takes
inputs = (kv_cache, input_tokens)and returnsoutputs = (new_keys_and_values, new_token). The prover publishes hashes of all keys and values. Then the verifier samples a decode step at random, and the prover must produce a ZKP thatoutputs = P(inputs).Writing it this way, though, I see that I made an error in my previous estimate for the amount of covert communication the prover can perform without getting caught. I’d assumed that, for each fraudulent decode step, the prover can send one token’s worth of covert information out of the rack. I realize now that the correct amount of information is the size of
outputs, which is dominated bynew_keys_and_values. ChatGPT estimatesnew_keys_and_valuesis around 30kB for Kimi K3, which is ~4 OOMs larger thannew_token. So, assuming 1e6 ZKP overhead as before, and 0.1% of compute set aside for producing ZKPs, the total covert communication volume is tens of terabytes (not gigabytes, as I claimed in the OP). Still doesn’t seem too bad to me.