4 ms·

Could someone provide a better explanation (or a link to one) of the ZKP verifiable execution thing linked to in the post? https://people.xiph.org/~greg/simple_

Could someone provide a better explanation (or a link to one) of the ZKP verifiable execution thing linked to in the post? https://people.xiph.org/~greg/simple_verifyable_execution.txt https://people.xiph.org/~greg/simple_verifyable_execution.tx... The notation is a bit weird, and I think I'm missing things here. Some confusions: - Are the AND gates actual AND gates which take in two bits and output one, or programming AND operations which operate on a couple of bytes at once? - Why is the hash of the and gate encryption keys not reversible? At max the key is only a few bytes large, which is easy to brute force. If I'm interpreting these as actual AND gates, it's a three bit key, which will neither be unique nor have a shred of security. - "I use the resulting super-commitment to select a random permutation of the encrypted gates.": What happened here? Were they just sorted by the superhash? Was the hash used as a seed in a PRNG? Would just shuffling them any which way be okay, or does the shuffle have to be such that the person the gates are sent to can verify that the shuffling was done "correctly"? This seems like a key point which was glossed over. - I'm not entirely sure what role the revealing of the gates plays here. I assume that because of the deterministic shuffling above, it's a nontrivial problem to do any jiggery-pokery with the nonrevealed gates without changing the shuffle order (and thus changing which gates are the ones not revealed)? I sort of see how this works; but I'm not convinced that it's secure.

nullc 11y ago
The "and gate" are encrypted and-gates: a table which maps encrypted bits to encrypted output bits. The encrypted values can be large enough to make bruteforcing the hash infeasible to view the rest of the table infeasable. (In the text "We can create an encrypted version of the gate by picking an encryption key for each wire in/out). Revealing the gates serves the purpose of convincing you that the gates in use are actually ANDs and not (say) gates that all return true. > What happened here? Were they just sorted by the superhash? Was the hash used as a seed in a PRNG? Would just shuffling them any which way be okay, or does the shuffle have to be such that the person the gates are sent to can verify that the shuffling was done "correctly"? This seems like a key point which was glossed over. As it says, "E.g. I use that hash to initialize a random shuffle on the gates." It needs to be a deterministic scheme set in advance with random ordering based on the collection of encrypted gates so that the prover cannot take the subset of gates that would be used in a critical part and make just those invalid. In one sense it doesn't matter how the shuffle is done so long as the prover can't use knowledge of it to cheat without being caught-- e.g. in an interactive protocol the verifier picking the shuffle works fine. And indeed, the goal of using the hash is so that the prover can't efficiently exploit knowledge of the order to adapatively cheat. (e.g. make all his gates return true, except for the ones that are going to get revealed).
- Manishearth 11y ago
  > The "and gate" are encrypted and-gates: a table which maps encrypted bits to encrypted output bits. But the encryption scheme has only two possible inputs; can't this be brute forced? Perhaps an example would help me understand here.
  - nullc 11y ago
    Here are commitments to an encrypted and-gate: a333e6e99e94fad05473f31ea377060a d967b456aa43ede06840994d5ce8547c 8ad297f72e49a1a6a48d343ec40661ae 88d626c9c58efd6d144f585e1fa6f436 Lets assume that the rest of the circuit gives us encrypted bits, 0 and 0 for the two inputs. So I reveal this to you: echo -n "0,0,1,bcxbxewrewtererwre" | md5sum - 8ad297f72e49a1a6a48d343ec40661ae Which is the third entry in the table, and we see the correct encrypted output for this gate is 1 (assuming my table was actually an encrypted and-gate table). You still have idea if in1/in2/out are are zero or one. I could tell you that in1's encryption key was 1 (so now you know that in1 was one), and you still don't know if In2/out are zero or one. Making any more more sense?
    - Manishearth 11y ago
      Sort of, but not exactly: > So I reveal this to you: echo -n "0,0,1,bcxbxewrewtererwre" | md5sum - 8ad297f72e49a1a6a48d343ec40661ae what is 1 in 0,0,1? the encrypted output? Since this salted hash must be verifiable, I must know the bcx... string, and I can brute force all 8 possible pairs of numbers to get the gate. Isn't this a problem? > and we see the correct encrypted output for this gate is 0 Where did the zero come from?
      - nullc 11y ago
        > what is 1 in 0,0,1? the encrypted output? Yes, the encrypted output. > Since this salted hash must be verifiable, I must know the bcx... string, and I can brute force all 8 possible pairs of numbers to get the gate. Isn't this a problem? I tell you it when I give you the table entry. You have the commitments, go ahead and tell me the rest of the gate if you think you can brute force it. (You can't-- the nonces are per table entry). > Where did the zero come from? From the third field in the table entry. Edit: HN won't let me respond to you, but the fact that it's the Nth entry is irrelevant; I called out the number so you'd see if was one of the values that were committed to. Sorry for adding confusion.

nullc 11y ago

The "and gate" are encrypted and-gates: a table which maps encrypted bits to encrypted output bits. The encrypted values can be large enough to make bruteforcing the hash infeasible to view the rest of the table infeasable. (In the text "We can create an encrypted version of the gate by picking an encryption key for each wire in/out). Revealing the gates serves the purpose of convincing you that the gates in use are actually ANDs and not (say) gates that all return true. > What happened here? Were they just sorted by the superhash? Was the hash used as a seed in a PRNG? Would just shuffling them any which way be okay, or does the shuffle have to be such that the person the gates are sent to can verify that the shuffling was done "correctly"? This seems like a key point which was glossed over. As it says, "E.g. I use that hash to initialize a random shuffle on the gates." It needs to be a deterministic scheme set in advance with random ordering based on the collection of encrypted gates so that the prover cannot take the subset of gates that would be used in a critical part and make just those invalid. In one sense it doesn't matter how the shuffle is done so long as the prover can't use knowledge of it to cheat without being caught-- e.g. in an interactive protocol the verifier picking the shuffle works fine. And indeed, the goal of using the hash is so that the prover can't efficiently exploit knowledge of the order to adapatively cheat. (e.g. make all his gates return true, except for the ones that are going to get revealed).

Manishearth 11y ago
> The "and gate" are encrypted and-gates: a table which maps encrypted bits to encrypted output bits. But the encryption scheme has only two possible inputs; can't this be brute forced? Perhaps an example would help me understand here.
- nullc 11y ago
  Here are commitments to an encrypted and-gate: a333e6e99e94fad05473f31ea377060a d967b456aa43ede06840994d5ce8547c 8ad297f72e49a1a6a48d343ec40661ae 88d626c9c58efd6d144f585e1fa6f436 Lets assume that the rest of the circuit gives us encrypted bits, 0 and 0 for the two inputs. So I reveal this to you: echo -n "0,0,1,bcxbxewrewtererwre" | md5sum - 8ad297f72e49a1a6a48d343ec40661ae Which is the third entry in the table, and we see the correct encrypted output for this gate is 1 (assuming my table was actually an encrypted and-gate table). You still have idea if in1/in2/out are are zero or one. I could tell you that in1's encryption key was 1 (so now you know that in1 was one), and you still don't know if In2/out are zero or one. Making any more more sense?
  - Manishearth 11y ago
    Sort of, but not exactly: > So I reveal this to you: echo -n "0,0,1,bcxbxewrewtererwre" | md5sum - 8ad297f72e49a1a6a48d343ec40661ae what is 1 in 0,0,1? the encrypted output? Since this salted hash must be verifiable, I must know the bcx... string, and I can brute force all 8 possible pairs of numbers to get the gate. Isn't this a problem? > and we see the correct encrypted output for this gate is 0 Where did the zero come from?
    - nullc 11y ago
      > what is 1 in 0,0,1? the encrypted output? Yes, the encrypted output. > Since this salted hash must be verifiable, I must know the bcx... string, and I can brute force all 8 possible pairs of numbers to get the gate. Isn't this a problem? I tell you it when I give you the table entry. You have the commitments, go ahead and tell me the rest of the gate if you think you can brute force it. (You can't-- the nonces are per table entry). > Where did the zero come from? From the third field in the table entry. Edit: HN won't let me respond to you, but the fact that it's the Nth entry is irrelevant; I called out the number so you'd see if was one of the values that were committed to. Sorry for adding confusion.