Implementing fibonacci sequence example

[osuketh]

I'm currently trying out implementing fibonacci sequence example using libstark.
see here: https://github.com/LayerXcom/libSTARK/tree/macOS/simpleadd , referring to the stark-dpm example.

I am in trouble because I cannot get it working correctly.
Both libstark::BairWitnessChecker::verify(bair_instance, bair_witness) and libstark::Protocols::executeProtocol return false.

I have no idea how to fix it.

I guess there is something wrong with the constraints(Add_EvalPoly.cpp).
(I found libstark::BairWitnessChecker::verify(bair_instance, bair_witness) returns true if this constraint is removed, but still executeProtocol returns false.)

You can execute the program with ./simple-add t a.

The first argument is t representing the number of iterations the sequence with public input.
The second argument is a representing the tth number of the fibonacci sequence with private input.

So you can build make -j8 and then execute like ./simple-add 8 21. (because the 8th fibonacci number is 21)

Can you tell me how to fix it?
Thanks.

[MichaelRiabzev]

Dear osuketh,
could you please provide a scheme explaining the witness you are generating, and the constraints you are using?
A minimal failing concrete example would be very helpful for debugging your issue.

[osuketh]

Thank you for your reply.
There are three registers(B00, B01, B02) for fibonacci sequence representing B00 + B01 = B02 for each steps, so the generated witness looks like this.

The corresponding code is here. https://github.com/LayerXcom/libSTARK/blob/macOS/simpleadd/Add_GenWitness.cpp#L18-L41

The using constraints are B00_next + B01, B01_next+B02, (B00 + B01 + B02) * (B00 + B01) .(last one*(B00+B01) is used for first steps)
The code is here. https://github.com/LayerXcom/libSTARK/blob/macOS/simpleadd/Add_EvalPoly.cpp#L23-L25

There are boundary constraints for B00 = 0, B01 = 0 with first step and B02 = a (private input) with last step.
https://github.com/LayerXcom/libSTARK/blob/macOS/simpleadd/Add_instance.cpp#L47-L54

./simple-add 8 21 executes the program that the witness is assumed satisfying the constraints, but it fails.

[elistark]

Hi, You're aware that the STARK is over a binary field (characteristic 2), which means a Fibonacci sequence will look pretty repetitive. If you start it with a, b, and letting c:=a xor b, the sequence will be: a, b, c, a, b, c, a, b, c,...

…

On Tue, Dec 11, 2018 at 12:25 PM Osuke ***@***.***> wrote: Thank you for your reply. There are three registers(B00, B01, B02) for fibonacci sequence representing B00 + B01 = B02 for each steps, so the generated witness looks like this. [image: img_0663] <https://user-images.githubusercontent.com/20852667/49792902-33651c00-fd77-11e8-8ff9-684eccc31696.JPG> The corresponding code is here. https://github.com/LayerXcom/libSTARK/blob/macOS/simpleadd/Add_GenWitness.cpp#L18-L41 The using constraints are B00_next + B01, B01_next+B02, (B00 + B01 + B02) * (B00 + B01) .(last one*(B00+B01) is used for first steps) The code is here. https://github.com/LayerXcom/libSTARK/blob/macOS/simpleadd/Add_EvalPoly.cpp#L23-L25 There are boundary constraints for B00 = 0, B01 = 0 with first step and B02 = a (private input) with last step. https://github.com/LayerXcom/libSTARK/blob/macOS/simpleadd/Add_instance.cpp#L47-L54 ./simple-add 8 21 executes the program that the witness is assumed satisfying the constraints, but it fails. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#17 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AmDav8KYsybj6eAIOwlckXBwq9wT47a6ks5u34gugaJpZM4ZMlr7> .

[osuketh]

Ah, thank you! Once I fixed to over a binary field, then libstark::BairWitnessChecker::verify(bair_instance, bair_witness) returns true.

But still, it shows Verifier decision: REJECT (libstark::Protocols::executeProtocol(bair_instance, bair_witness, securityParameter, false, false, true) returns false.)

I think this means encoding to polynomials could be correct, but there is something wrong with generating proof or verification, right?
Could you tell me how to fix this?

The generating witness is

void genWitnessAddWithPadding(witnessType arr, const unsigned int a, const unsigned int b) {         
        DBGGET(arr, 0, reg::A) = mapIntegerToFieldElement(0, 64, a);
        DBGGET(arr, 0, reg::B) = mapIntegerToFieldElement(0, 64, b);
        DBGGET(arr, 0, reg::C) = arr[0][reg::A] + arr[0][reg::B];

        for (size_t i = 1;i < Add::lastStep + 1; i++) {                                    
             DBGGET(arr, i, reg::A) = arr[i - 1][reg::B];
             DBGGET(arr, i, reg::B) = arr[i - 1][reg::C];
             DBGGET(arr, i, reg::C) = arr[i][reg::A] + arr[i][reg::B];
        }                
    }

The used constraints is

FieldElement evalp::ep(const std::vector<FieldElement>& vars) { 
        randCoeff[0] = Algebra::generateRandom();

        FieldElement tval = randCoeff[RI(0)] * (vars[reg::A + NUMREGS] + vars[reg::B]);
        tval += randCoeff[RI(1)] * (vars[reg::B + NUMREGS] + vars[reg::C]);
        tval += randCoeff[RI(2)] * (vars[reg::C + NUMREGS] + vars[reg::A]);
        tval += randCoeff[RI(3)] * (vars[reg::A] + vars[reg::B] + vars[reg::C]);

        return tval;

[MichaelRiabzev]

Could you please post the printouts? It might help me figure out what is happening.

[osuketh]

Thank you so much. This is the printouts.
https://gist.github.com/osuketh/dde70318074b83e0b92bbeb18c729dab

[MichaelRiabzev]

Dear osuketh, I believe I understood what is the problem.

Solution:
In Add_EvalPoly.cpp update RN to 4, and remove the first line of evalp::ep (randCoeff[] = ...).

Explanation:
the values of randCoeff can be arbitrary (and should be random for soundness), but must be set only ones, and not changed during execution. (specifically, must be the same when Prover and Verify evaluate the constraints polynomial). This is of course not the case when at every execution the value od randCoeffs[0] is changed.

[osuketh]

Thank you for helping me. Finally it works!
https://twitter.com/zoom_zoomzo/status/1075939535316348928