zkFibonacci

Previous Part was focused on mathematical concepts of ZK. Now, to get some intuition, you will start using o1js and then start learning Mina Protocol.

"The Fibonacci Sequence turns out to be the key to understanding how nature designs... and is... a part of the same ubiquitous music of the spheres that builds harmony into atoms, molecules, crystals, shells, suns and galaxies and makes the Universe sing" - Guy Murchie

Fibonacci sequence is discovered in... Okay, you probably know what a Fibonacci sequence is and this page is not aimed to teach you history of mathematics, right? But simply, we should describe Fibonacci sequence as this:

  • Call F(n)F(n) the n^th number in Fibonacci sequence.

  • Start with F(0)=F(1)=1F(0) = F(1) = 1.

  • General rule for the n^th Fibonacce number is given by F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)

That's all for now. Pretty simple right? Using this, you can easily construct the Fibonacci numbers by ascending number: 1, 1, 2, 3, 5, 8, 13, 21, 35, 56...

Nice! But wait a second... As you progress, numbers get bigger and bigger, so it would not be a wise thing to sum numbers by hand. Oh - Computers are handy in that situation! But, what if you want to compute a high index, like F(324)? Don't try to check it, here it is: 2304148358552416826222090648964201807510161746678049679057369028996823041483585524168262220906489642018075101617466780496790573690289968

Its pretty big. However, 325 will be greater. What about 326? Oh my god, don't even talk about 327! As you see, at some point even your computer might be slower for computing it. At that point, you might want to outsource computing right? You can ask your friend with a super-like computer to give you the 8357^th Fibonacci number.

However... Imagine this number will be used in a very important task and you have some trust issues with your friend. What happens now?

ZK Circuits

The word 'ZK Circuit' is a little bit mystifying the concept. Circuits in ZK are simply (or call it Arithmetic Circuits).

Now think about the equation (x+y)∗z=Output(x + y) * z = Output. Output is any arbitrary output depending on the values of x,y and z. When you visualize this equation :

Representation of an arithmetic circuit.

Now, as you see, it is pretty similar to the boolean circuits. Multiplication adn addition operations are represented by gates. When you have much more equations and variables, you get circuits that satisfies your inputs, hence your 'statements'.

Now let's see this in action. Fibonacci sequence can be constructed by an arithmetic circuit and can be proven in each step that calculation is done properly. We owe this to the underlying zkSNARK mechanism of Mina Protocol.

Start your project

To start a project quickly, follow these steps:

$ npm install -g zkapp-cli

Then, start a zk project:

$ zk project fibonacci

Say yes to the use Typescript in the project, since all these learning journey will be done with typescript.

✔ Create an accompanying UI project too? · none
✔ UI: Set up project
✔ Initialize Git repo
✔ Set up project
✔ NPM install
✔ NPM build contract
✔ Set project name
✔ Git init commit

Success!

Next steps:
  cd fibonacci
  git remote add origin <your-repo-url>
  git push -u origin main

After this step, open the fodler with your favorite ide. Then, delete files in the contracts/src folder. Create three files: Fibonacci.ts Fibonacci.test.ts and index.ts.

src
├── Fibonacci.test.ts
├── Fibonacci.ts
└── index.ts

Now you're ready to code.

Zk Fibonacci

To start with it is wise to start with an object that keeps elements in it. A Struct is suitable for this purpose. Struct lets you to create composite data types that can be used in zkCircuits. Why is that needed? As you've seen in the previous parts, Mina protocol in the underlying part works with circuits, (almost) everything you write is circuitized, where inputs are Finite Field elements. For that purpose, you should use Struct class of o1js. Abstract classes ( or, types ) that are used for building zkCircuits are called provable types. They are called provable, since they are used in a circuit to build proofs, hence they are 'provable'.

Now, lets continue with the Fibonacci.ts file:

import { Field, Struct, state, method, ZkProgram, SelfProof, State, SmartContract} from 'o1js';

export class Pair extends Struct ({
  first: Field,
  second: Field,
}) {
  constructor(first: Field, second: Field) {
    super({ first, second });
    this.first = first;
    this.second = second;
  }
};

Classes that you are going to use in the following is added besides the one used so far.

Field object used here is a mathematical object that is the backbone of the cryptography. See the Kimchi Book later for more theoretical details of Finite Fields.

Now that you have a container for our elements, magical ZkProgram kicks in! Importing ZkProgram and SelfProof classes, add this code to your Fibonacci.ts file:

export const FibonacciSequence = ZkProgram({
  name: "fibonacci-sequence",
  publicOutput: Pair,

  methods: {
    baseCase: {
      privateInputs: [],

      async method() {
        return new Pair(Field(1), Field(1));
      },
    },

    step: {
      privateInputs: [SelfProof],

      async method(earlierProof: SelfProof<Pair, Pair>) {
        earlierProof.verify();

        const numbers = earlierProof.publicOutput;

        return new Pair(numbers.second, numbers.first.add(numbers.second));
      },
    },
  },
});

ZkProgram helps you to build zkSNARKs and it is a high level abstraction of Pickles, one of the tools that powers Mina protocol. With ZkProgram, you can build zkSNARK proofs recursively in a flexible way. Methods defined in a ZkProgram should be async. You can name a ZkProgram and define the types of Public or Private outputs before methods.

You can give inputs to the ZkProgram as Private or/and Public inputs depending on your choice. As a result, you will get a proof of the computation you did and the public outputs that you want to expose to the public.

In our case, not only the result of the calculation of the Fibonacci sequence but also the proof that it is calculated correctly is needed. Also, You can recursively increase the steps taken, meaning that for every step you can use the previous step's output and proof generated to compute the next step and generate the next proof. Your current proof can be verified in the next proof and the proof of calculations done so far can be generated recursively. 

await FibonacciSequence.compile();

export class FibonacciSequenceProof extends ZkProgram.Proof(FibonacciSequence) {};

export class Fibonacci extends SmartContract {
  @state(Field) number1 = State<Field>();
  @state(Field) number2 = State<Field>();

  async init() {
    super.init();
    this.number1.set(Field(1));
    this.number2.set(Field(1));
  };

  @method async update(
    proof: FibonacciSequenceProof
  ) {
    proof.verify();

    // To make sure our sequence always gets bigger
    proof.publicOutput.first.assertGreaterThan(this.number1.getAndRequireEquals()); // This assertion does not result in a concurrency issue. We always accept the biggest order sequence TX in a block. See the README.md for more details.

    this.number1.set(proof.publicOutput.first);
    this.number2.set(proof.publicOutput.second);
  };

};

After you've constructed your ZkProgram, it is important to compile it with .compile() method. This compilation is not like compiling your code to machine code; the word is used for taking a ZkProgram and making it a zk Circuit.

After compilation is done, defined a class FibonacciSequenceProof. Why is that? Do you remember how ZkProgram has a public value and proof as an output? By ZkProgram.Proof, you define a class that extends the properties of FibonacciSequence ZkProgram you defined before. For settling the proof of execution done, you will be able to use that proof in the smart contract.

Now this step is important and we will talk a little bit about it later. To settle the computation you or the other party you interacted, you can use the SmartContract class.

Before writing the test of the code, open the index.ts and write:

import { Fibonacci } from './Fibonacci.js';

export { Fibonacci };

Now open to Fibonacci.test.ts file. 

import { FibonacciSequence, FibonacciSequenceProof, Fibonacci } from './Fibonacci';
import { Field, Mina, PrivateKey, PublicKey, AccountUpdate } from 'o1js';

let proofsEnabled = true;

describe('Fibonacci', () => {
  let deployerAccount: Mina.TestPublicKey,
    deployerKey: PrivateKey,
    senderAccount: Mina.TestPublicKey,
    senderKey: PrivateKey,
    zkAppAddress: PublicKey,
    zkAppPrivateKey: PrivateKey,
    zkApp: Fibonacci;

  beforeAll(async () => {
    if (proofsEnabled) await Fibonacci.compile();

    const Local = await Mina.LocalBlockchain({ proofsEnabled });
    
    Mina.setActiveInstance(Local);
    [deployerAccount,senderAccount] = Local.testAccounts;
    deployerKey = deployerAccount.key;
    senderKey = senderAccount.key;

    zkAppPrivateKey = PrivateKey.random();
    zkAppAddress = zkAppPrivateKey.toPublicKey();
    zkApp = new Fibonacci(zkAppAddress);
  });

});

Now lets go over what we did here:

  • proofsEnabled option is used in LocalBlockchain. LocalBlockchain is a simulation of the Mina blockchain and designed for test purposes. When proofsEnabled is true, zk proofs are enabled to be used in the Local chain. setting it to false speeds up the test process without losing generality.

Defined variables are deployer/sender account and their private key, which will be used in the transactions. ZkApp, zkAppAddress/PrivateKey are the variables for the ZkApp that will live in the Mina blockchain.

Before you start the calculation of Fibonacci, set the active instance of Mina blockchain by chain we defined with variable Local.

Then you should create a zkApp of Fibonacci smart contract with the address your created. 

  async function localDeploy() {
    const txn = await Mina.transaction(deployerAccount, async () => {
      AccountUpdate.fundNewAccount(deployerAccount);
      zkApp.deploy();
    });
    await txn.prove();
    // this tx needs .sign(), because `deploy()` adds an account update that requires signature authorization
    await txn.sign([deployerKey, zkAppPrivateKey]).send();
  }

Then define a function (inside describe block) for deploying the zkapp to the chain. Deployment is done with a transaction, which will cause a state change in the blockchain. In the transaction, you see a class named AccountUpdate. updates for the accounts in the blockchain is handled with this class.

In Mina blockchain, account creation is feed by 1 $MINA. For creating a zkApp, you pay 1 $MINA with your account.

After designing that transaction, sign and send the transaction.

    it('generates and deploys the `Fibonacci` smart contract', async () => {
    await localDeploy();
    const number1State = zkApp.number1.get();
    const number2State = zkApp.number2.get();

    expect(number1State).toEqual(Field(1));
    expect(number2State).toEqual(Field(1));
  });

  it('correctly updates the state on the `Fibonacci` smart contract', async () => {
    const count = 3; // We will calculate the 4th element of the sequence

    let proof = await FibonacciSequence.baseCase();
    let number1 = Field(1);
    let number2 = Field(1);
    
    for (let i = 0; i < count; i++) {
      console.log(`The ${i + 2}. element of the Fibonacci sequence is ${number2.toBigInt()}`)
      proof = await FibonacciSequence.step(proof);

      const temp = number2;
      number2 = number1.add(number2);
      number1 = temp;
    }

    // update transaction
    const txn = await Mina.transaction(senderAccount, async () => {
      zkApp.update(new FibonacciSequenceProof(proof));
    });
    await txn.prove();
    await txn.sign([senderKey]).send();

    const number1State = zkApp.number1.get();
    const number2State = zkApp.number2.get();

    expect(number1State).toEqual(number1);
    expect(number2State).toEqual(number2);

    console.log(`The ${count + 2}. element of the Fibonacci sequence is ${number2State.toString()}`);
  });
});

Finally, adding the tests above will end the program. What you do is simple: in the first test block, you initialize the Fibonacci zkApp and see check whether number1 and number2's states are equal to the base case.

In the second block, you get the proof of the base case of the FibonacciSequence. Then, iterating it for 4 times will let you get the 4th element in the fibonacci sequence recursively.

Remember, in the step method, proofs are verified in each step. Hence using it will create a proof and you will be able to get the results of the computation in a verified manner.

After you finish the code, enter to the contracts folder, go to the terminal and to this magical step:

npm run test

You will wait for around ~1.5 minutes. Then, you will see that your Fibonacci sequence calculator works!

Now you beat the trust issues with your friend. How? Using a trustless system.

PreviousOPTIONAL: Advanced ResourcesNextMina Protocol

Last updated