Separate prover and verifier

[jimouris]

Hi,

I am trying to separate the prover and the verifier to different files and also write the proof to a .proof file. To my understanding, the proof is the class bairWitness, right? So what has to be done is to serialize this class to the prover-side and de-serialize it to the verifier-side.

Thanks in advance,
Dimitris

[MichaelRiabzev]

Dear @jimouris ,
I would like to first note that libSTARK simulates an interactive proof-system, making it noninteractive would require some additional effort on top of just separating the verifier from the prover.

Now, how to separate:
At src/protocols/protocol.cpp line 118 you have the function executeProtocol, simulating the execution of the interactive system. It has some dirt in it, as the barManager thread responsible on showing a bar in the console while the parties are busy, so the user won't get bored, you can ignore that and clean that out, it is only for UI.
Additionally, the function receives the parameter onlyVerifierData, used to simulate verifiers execution without actually running a prover, you can fix that to true simplifying the function even more. Cleaning it a bit more will get you something as simple as:

while (!verifier.doneInteracting()) {
        const auto vMsg = verifier.sendMessage();
        prover.receiveMessage(*vMsg);
        const auto pMsg = prover.sendMessage();
        verifier.receiveMessage(*pMsg);
 }

Given this code, it is easy to see how one can separate the prover and the verifier, all you need is to implement serialization/deserialization for vMsg and pMsg (it should be quite easy, as the original design included that requirement), and you can split the two parties to different machines.

[jimouris]

Dear Michael,

Thank you for the quick response. So all vMsg and pMsg that the two parties exchange is the proof, right? Also, what is the factor that affects how many communication iterations will take place?

[MichaelRiabzev]

@jimouris,

as I've mentioned above, the system is interactive. The vMsgs are messages from the verifier to the prover, and the pMsgs are message from the prover to the verifier. There is no noniteractive proof here, in order to make it noninteractive one could use the Fiat-Shamir heuristic, where the verifiers randomness is defined by the messages sent by the prover, in such case the "proof" is simply the concatenation of all messages from the prover (all pMsgs). But currently, there is no object in the system one can call "the proof" (at least not in the way people usually think about it).

I will try to explain:
Let's say I'm claiming I know how to break SHA2, specifically, for any x, I can find y such that SHA2(y)=x.
We can meet, and you could test me, by drawing a few random values of x, and I would present you the respective y values. This might impress you, and convince of my great abilities, but there is no noniteractive proof here, the interactive phase is essential for the soundness, as if you would record our interaction and publish it online, people would suspect your challenges could have been prepared so it would be easy for me to solve.
A way to make this test to produce a noninteractive proof could be manipulating our test, so that the first challenge x_{0} is simply 123, and every challenge x_{i+1} is defined by x_{i+1} = SHA2(x_{i}) XOR SHA2(y_{i}). Now, publishing this transcript (the initial x_{0} value, and my responses) can be defined as a proof to my abilities, and probably could convince anyone on the network without them needing to interact with me.

So, back to libSTARK, in libSTARK the verifier's randomness (the challenges) are defined randomly and independently. Thus, just as in the example of the interactive test, there is no proof object here. In order to get a (noninteractive) proof, one should manipulate the verifiers randomness source using the Fiat-Shamir heuristic.

[jimouris]

Nice explanation, thanks, I completely understood!