DEV Community: Laszlo Fazekas

How Machines Can Learn: Gradient Descent in Tensorflow and PyTorch

Laszlo Fazekas — Sun, 28 Jan 2024 09:00:22 +0000

Artificial Intelligence (AI) and machine learning are at the forefront of technological innovation, driving advancements in fields ranging from autonomous vehicles to real-time translation and voice recognition. These transformative applications rely fundamentally on machine learning to function. However, the question remains: How do machines acquire this capability? In this article, we will delve into the core mechanisms that enable machines to learn, bypassing the often-discussed topic of neural networks. Instead, we will explore the foundational principles that lie at the very heart of machine learning, unveiling the underlying processes that power these sophisticated systems.

One of the best presentations about machine learning is Fei Fei Li’s TED talk.

In her presentation, Li highlighted the initial attempts by programmers to tackle computer vision challenges through algorithmic solutions. These early algorithms were designed to identify objects by searching for specific shapes, operating on a set of predefined rules. However, this approach proved inadequate for the complexity of computer vision tasks. The intricacy of interpreting visual data through rigid algorithms was quickly recognized as an insurmountable barrier. This realization paved the way for the integration of machine learning, marking a pivotal shift in strategy towards a more adaptable and nuanced approach to understanding visual information.

If we cannot write the program, let’s write a program that writes it instead of us.

Machine learning algorithms excel in this domain by leveraging vast datasets to autonomously derive the algorithms that predict outputs from given inputs. Specifically in the realm of image recognition, the input is the image itself, while the output can be a label or a descriptive annotation of the image's contents. This process involves the algorithm analyzing patterns and features within the data, learning to correlate specific inputs with their corresponding outputs, thereby enabling the machine to accurately identify and describe new, unseen images.

This dedication to advancing the field of computer vision is what motivated Li and her team to create ImageNet. This monumental achievement stood as the largest labeled image database globally at the time. With an extensive collection of 15 million images spanning 22,000 distinct categories, ImageNet provided an unprecedented resource for training machine learning models, significantly contributing to breakthroughs in the accuracy and efficiency of image recognition technologies.

Thanks to ImageNet, we had enough data, but how did programmers use it to solve the problem of image recognition? This is the point where I should talk about neural networks like Li does, but I won’t. Neural networks are indeed inspired by the biological brain, but today’s transformers are far from the biological model.

This is why I think the name ‘neural network’ is misleading. But what would be a better name?

My favorite is Karpathy’s (head of AI @ Tesla) Software 2.0.

As Karpathy said in this talk, Software 1.0 is the classical software, where the programmer writes the code, but in the case of Software 2.0, another software finds it based on big data. But how can a software write another software? Let me quote Karpathy:

Gradient descent can write code better than you. I’m sorry.

Gradient descent is the name of the magic that is used by most machine learning systems. To understand it, let’s imagine a machine learning system. It’s a black box with inputs and outputs. If the purpose of the system is image recognition, then the input is an array of pixels, and the output is a probability distribution vector.

If the system can identify cats and dogs, and the input is an image of a cat, the output will be like 10% dog and 90% cat. So, the inputs are numbers, the outputs are also numbers, and the content of the black box is a giant (really huge) mathematical expression. The black box calculates the output vector from the pixel data.

I promised to talk about programs writing programs, and now I’m talking about mathematical expression. But in fact, programs are mathematical expressions. CPUs are built from logic gates. They use the binary representation of numbers and logic operators.

Any existing algorithm can be implemented by these logical expressions, so a long logical expression can represent any program that can run on classical computers. As you see, classical programs are also not more than binary calculations from a binary input to a binary output.

Machine learning systems use real numbers and operators instead of binary numbers and operators, but basically, these mathematical expressions are also “programs.”

Alan Turing wrote a paper in 1948 about “B-type unorganized machines.” These machines are built from interconnected logical NAND gates and can be trained by enabling/disabling the wires between the nodes. In binary algebra, NAND is a universal operator, because every other operator can be expressed by it. These B-type unorganized machines are universal computers because every algorithm can be implemented on them.

These B-type machines are similar to nowadays neural networks, but they are implemented upon logic gates like today’s CPUs, so the algorithms that are implemented by these B-type machines would be more like today’s algorithms.

Unfortunately, Turing never published the paper, this is why we do not know him as an inventor of early neural networks. The problem with these B-type networks is that they cannot be trained efficiently.

If we have a set of inputs and outputs and a parameterized expression, how can we find the correct parameters that calculate the outputs from the inputs with the fewest errors? It is something like a black box that has many potentiometers. Every combination of the potentiometer positions is a program, and we are searching for the correct positions.

To solve this problem, let’s imagine the error function. It looks like a landscape with hills and valleys. Every single parameter of the expression is a dimension of the landscape, and the height of the current point is the error with the given parameters.

When we initialize the expression with random numbers, we are at a random location on the landscape. To minimize the errors, we have to come down to the lowest point (that represents the lowest error). The problem is that we are completely blind. How can we come down from the hill?

We can grope around to find the steepest slope and go there. But how can we determine the slope of a function? Here comes the gradient in the picture. Gradient shows how steep the slope on the function is at a given point. This is why we call this method “gradient descent.”

The gradient at the given point can be calculated by partial derivation. A function has to satisfy some requirements to be derivable. If we want to use gradient descent for optimization, we have to use these types of functions. If the functions are derivable, then the chain of functions will also be derivable, and there is an algorithmic method to calculate the gradient.

Now we have all the knowledge to understand how TensorFlow and PyTorch (the two most popular machine learning frameworks) find the correct parameters for our expression.

First, let’s look at TensorFlow.

In Tensorflow, there is a gradient registry where gradient functions are registered for the operators by the RegisterGradient method. In the learning phase, in every step, a GradientTape has to be started. GradientTape is something like a video recorder. When TensorFlow does any operation, the gradient tape logs it.

After the end of the forward phase (when the output is generated from the input), we stop the gradient tape that goes backward on the log by using the error and calculating the gradients using the registered gradient functions. We can modify the parameters and repeat the process until we reach the minimum error by using the gradients.

Let’s look at the code in Python:

# Linear regression using GradientTape
# based on https://sanjayasubedi.com.np/deeplearning/tensorflow-2-linear-regression-from-scratch/

import tensorflow as tf
import numpy as np
import matplotlib.pyplot as plt

class Model:
    def __init__(self):
        self.W = tf.Variable(16.0)
        self.b = tf.Variable(10.0)

    def __call__(self, x):
        return self.W * x + self.b

TRUE_W = 3.0 # slope
TRUE_b = 0.5 # intercept

NUM_EXAMPLES = 1000

X = tf.random.normal(shape=(NUM_EXAMPLES,))
noise = tf.random.normal(shape=(NUM_EXAMPLES,))
y = X * TRUE_W + TRUE_b + noise

model = Model()

plt.figure()
plt.scatter(X, y, label="true")
plt.scatter(X, model(X), label="predicted")
plt.legend()
plt.show()

def loss(y, y_pred):
    return tf.reduce_mean(tf.square(y - y_pred))

def train(model, X, y, lr=0.01):
    with tf.GradientTape() as t:
        current_loss = loss(y, model(X))

    dW, db = t.gradient(current_loss, [model.W, model.b])
    model.W.assign_sub(lr * dW)
    model.b.assign_sub(lr * db)

Ws, bs = [], []
epochs = 20
for epoch in range(epochs):
    Ws.append(model.W.numpy()) # eager execution allows us to do this
    bs.append(model.b.numpy())

    current_loss = loss(y, model(X))

    train(model, X, y, lr=0.1)
    print(f"Epoch {epoch}: Loss: {current_loss.numpy()}")

plt.figure()
plt.plot(range(epochs), Ws, 'r', range(epochs), bs, 'b')
plt.plot([TRUE_W] * epochs, 'r--', [TRUE_b] * epochs, 'b--')
plt.legend(['W', 'b', 'true W', 'true b'])
plt.show()

plt.figure()
plt.scatter(X, y, label="true")
plt.scatter(X, model(X), label="predicted")
plt.legend()
plt.show()

This code shows how we can solve the simplest problem (linear regression) by using gradient descent in TensorFlow. The aim of linear regression is to find the parameters of a line that is closest to each point, where the closest means that the sum of squares of the distances is minimal.

TensorFlow uses tensor operations for the calculations. Tensors are generalizations of matrices. From the programmer’s perspective, tensors are simple arrays. A zero-dimensional tensor is a scalar, a one-dimensional tensor is a vector, a two-dimensional tensor is a matrix, and from the third dimension, tensors are simply tensors. Tensor operations can be done in parallel to run efficiently, especially on GPUs or TPUs.

At the beginning of the code, we define our model, which is a linear expression. It has two scalar parameters, W and b, and the expression is y=W*x+b. The default value of W is 16, and b is 10. This is in our black box, our code will change the W and the b to minimize the error. Real-world models have millions or billions of parameters, but these two parameters are enough to understand the method.

From line 21 to line 23, we define the random point set. The tf.random.normal method generates a vector with 1,000 random numbers in a normal distribution, and we use that to generate the points near a line.

The loss function is defined in line 34. y and y_pred parameters are vectors. y_pred is the actual output of our model, and y is the expected output. The square function calculates the square of every vector element, and the output is also a vector with the squares. The reduce_mean function calculates the mean of elements, and its result is a scalar. This is the error itself that we want to minimize.

The gradient descent is from line 36 to line 42. This is the essence of the code where the learning happens. Line 37 is a Python expression. It calls the parameter object’s _enter_ method at the beginning of the block and _exit_ at the end.

In the case of GradientTape, the _enter_ method starts the recording, and _exit_ stops it. In the block (line 38), we calculate the model output by model(X) and the error. In line 40, the GradientTape calculates the gradients for the parameters (dW and db), and in lines 41 and 42, modify the parameters.

There are different optimization strategies. We are using the simplest, where the gradients are multiplied by a fixed learning rate (lr).

In a nutshell, this is how gradient descent and TensorFlow’s GradientTape work. You can find many tutorials on TensorFlow’s webpage. Neural networks for image recognition, reinforcement learning, etc., but keep in mind, there are always tensor operations and a GradientTape.

Now, let’s see how gradient descent works in the other big framework, PyTorch.

PyTorch uses the autograd system for gradient calculation, which is embedded into the torch tensors. If a tensor is a result of an operator, it contains a back pointer to the operator and the source tensors. The source tensors also contain back pointers, etc., and the full operator chain is traceable.

Every operator can calculate its own gradient. When you call the backward method on the last tensor, it goes back on the chain and calculates the gradients to the tensors.

Let’s see the previous linear regression code in PyTorch:

import torch
import matplotlib.pyplot as plt
from torch.autograd import Variable


class Model:
    def __init__(self):
        self.W = Variable(torch.as_tensor(16.), requires_grad=True)
        self.b = Variable(torch.as_tensor(10.), requires_grad=True)

    def __call__(self, x):
        return self.W * x + self.b


TRUE_W = 3.0  # slope
TRUE_b = 0.5  # intercept

NUM_EXAMPLES = 1000

X = torch.normal(0.0, 1.0, size=(NUM_EXAMPLES,))
noise = torch.normal(0.0, 1.0, size=(NUM_EXAMPLES,))
y = X * TRUE_W + TRUE_b + noise

model = Model()

plt.figure()
plt.scatter(X, y, label="true")
plt.scatter(X, model(X).detach().numpy(), label="predicted")
plt.legend()
plt.show()


def loss(y, y_pred):
    return torch.square(y_pred - y).mean()


def train(model, X, y, lr=0.01):
    current_loss = loss(y, model(X))
    current_loss.backward()

    with torch.no_grad():
        model.W -= model.W.grad.data * lr
        model.b -= model.b.grad.data * lr

    model.W.grad.data.zero_()
    model.b.grad.data.zero_()


Ws, bs = [], []
epochs = 20
for epoch in range(epochs):
    with torch.no_grad():
        Ws.append(model.W.numpy().item())
        bs.append(model.b.numpy().item())

        current_loss = loss(y, model(X))

    train(model, X, y, lr=0.1)
    print(f"Epoch {epoch}: Loss: {current_loss.numpy()}")

plt.figure()
plt.plot(range(epochs), Ws, 'r', range(epochs), bs, 'b')
plt.plot([TRUE_W] * epochs, 'r--', [TRUE_b] * epochs, 'b--')
plt.legend(['W', 'b', 'true W', 'true b'])
plt.show()

plt.figure()
plt.scatter(X, y, label="true")
plt.scatter(X, model(X).detach().numpy(), label="predicted")
plt.legend()
plt.show()

The model and the loss part are very similar to TensorFlow. You find the difference in the train method from line 37 to line 46. After the calculation of the current_loss tensor, we call the backward method on it. It recursively goes back on the chain and calculates the gradient for the W and b tensors.

From line 41 to line 43, we modify the W and b tensors. It’s important that this calculation is in a torch.no_grad() block. The no_grad() method temporarily disables the gradient calculation for the operators, which is not needed when we modify the parameters.

At the end of the train method calling the zero method clears the gradients. Without this, PyTorch will sum up the gradients, which results in strange behavior. The other parts of the code are very similar to TensorFlow. Like TensorFlow, PyTorch also has good tutorials, community, and documentation.

You will find everything to build any neural network, but the most important part is the autograd system, which is the base of the training.

If you want to understand how autograd system works deep inside, watch Karpathy’s video about backpropagation. In this video, Karpathy builds an autograd system from zero in Python. High school math is enough to understand it, so it’s not a problem if you are not a big friend of math.

Next time, when you see a picture that DALL-E generates, a car that drives itself, or simply wonder how ChatGPT answers your questions, you will know how the magic works, and how an algorithm (the gradient descent) wrote these cool algorithms for us.

How I Built an Anonymous Voting System on the Ethereum Blockchain Using Zero-Knowledge Proof

Laszlo Fazekas — Mon, 01 Jan 2024 18:37:04 +0000

I’ve started to deal with the technology of zero-knowledge proofs because I was curious if it was possible to create an anonymous, unhackable voting system on the blockchain.

Paper-based voting (like the Elections) is a very expensive way of voting. I have no exact data, but it costs billions of dollars, and it is always in the air that somebody cheated it.

A blockchain-based system costs only a fraction of this price, and it is super secure because the blockchain is public and everybody can track everything on it.

The only thing that is untrackable is who voted to which party thanks to the zero-knowledge proof (for a more detailed explanation, please read my previous article). So, blockchain-based voting seems like the holy grail of voting.

In my previous article, I promised a simple proof of concept. It is now completed and available on GitHub. I will show you how it works in this article.

The method that I’m using is the same as what is used by Tornado Cash. Tornado Cash is a non-custodial Ethereum and ERC20 privacy solution based on zkSNARKs.

The main component of it is a smart contract where you can deposit your money with a commitment that you can withdraw later by a nullifier. One commitment is assigned to only one nullifier, but nobody knows which nullifier is assigned to which commitment.

This is also usable for anonymous voting because everybody should vote only once, but nobody should know which vote is assigned to which voter. (I have a full article about the topic.)

My voting app is an Ethereum dApp. It is a static page with JavaScript without any backend (the backend is the smart contract on Ethereum). Because of this, it is tough to attack the system, because, on the blockchain, there is no single point of failure.

If you want to test it locally, the easiest way is to run a local blockchain by:

npx hardhat node

and setup the accounts in MetaMask. We will use the first 2 accounts.

In the first step, clone the repo, deploy the smart contracts, and start the app:

git clone https://github.com/TheBojda/zktree-vote
cd zktree-vote
npm i
npm run prepare (optional, npm i should run it)
npm run deploy
npm start

The dApp uses MetaMask to communicate the blockchain, so if you use it from your desktop browser, MetaMask has to be installed, and if you use it from your mobile phone, open it in the MetaMask application’s embedded browser.

When you open http://localhost:1234/ you will see the menu of the app:

Click on the registration to vote to open the registration page.

When you open the page, it automatically generates the commitment and the nullifier in the background, and stores it in the browser’s local storage.

The validation of the voter can be done in person at the voting place, or online by using a video conferencing system, etc. The validator can use the “Validator tool” for it:

To make it easy, I have added a QR reader to the page, so sending the commitment to the validator can be done by scanning the voter’s QR code, or the voter can copy it and send it in the chat (online validation).

When the validator checked the voter’s identity by checking her identity card, etc., he sends the commitment to the blockchain with a unique hash that can be the hash of the user’s ID card or any unique identifier.

This ensures that one voter will be registered only once with one commitment, which means she can vote only once.

The voting process is easy. You choose one option and send it to the blockchain. The app will use the nullifier that is generated in the background.

On the last page, you can check the results of the voting in real-time.

That’s it. Simple and very comfortable way of voting, but it has all of the advantages of paper-based voting without all of the disadvantages.

After this short intro, let’s see some code.

To develop this voting dApp, I’ve used my zk-merkle-tree library. It is a JavaScript library that uses Tornado Cash’s zkSNARK-based method and hides all of the complexity of zero-knowledge proofs.

I have a full article about this library, so in this article, I won’t write about it in more detail.

The smart contract of the voting system looks like this:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.17;

import "zk-merkle-tree/contracts/ZKTree.sol";

contract ZKTreeVote is ZKTree {
    address public owner;
    mapping(address => bool) public validators;
    mapping(uint256 => bool) uniqueHashes;
    uint numOptions;
    mapping(uint => uint) optionCounter;

    constructor(
        uint32 _levels,
        IHasher _hasher,
        IVerifier _verifier,
        uint _numOptions
    ) ZKTree(_levels, _hasher, _verifier) {
        owner = msg.sender;
        numOptions = _numOptions;
        for (uint i = 0; i <= numOptions; i++) optionCounter[i] = 0;
    }

    function registerValidator(address _validator) external {
        require(msg.sender == owner, "Only owner can add validator!");
        validators[_validator] = true;
    }

    function registerCommitment(
        uint256 _uniqueHash,
        uint256 _commitment
    ) external {
        require(validators[msg.sender], "Only validator can commit!");
        require(
            !uniqueHashes[_uniqueHash],
            "This unique hash is already used!"
        );
        _commit(bytes32(_commitment));
        uniqueHashes[_uniqueHash] = true;
    }

    function vote(
        uint _option,
        uint256 _nullifier,
        uint256 _root,
        uint[2] memory _proof_a,
        uint[2][2] memory _proof_b,
        uint[2] memory _proof_c
    ) external {
        require(_option <= numOptions, "Invalid option!");
        _nullify(
            bytes32(_nullifier),
            bytes32(_root),
            _proof_a,
            _proof_b,
            _proof_c
        );
        optionCounter[_option] = optionCounter[_option] + 1;
    }

    function getOptionCounter(uint _option) external view returns (uint) {
        return optionCounter[_option];
    }
}

The smart contract is inherited from ZKTree (from the zk-merkle-tree library) and uses its _commit and _nullify methods. The _commit method stores the commitment, and the _nullify method stores the nullifier and verifies the zero-knowledge proof for it.

The owner can add the validators by calling the registerValidator method. Only validators can send a commitment to the smart contract after checking the voter’s identity.

The last method is getOptionCounter which you can use to query the result of the voting in real-time.

That’s all. Thanks to zk-merkle-tree, the voting contract is super simple, every complexity is hidden behind the library.

The dApp itself is a vue.js single-page application. The commitment and the nullifier are generated in the VoterRegistration component by using the generateCommitment from zk-merkle-tree and stored in the local storage.

this.commitment = JSON.parse(
  localStorage.getItem("zktree-vote-commitment")
);
if (!this.commitment) {
  this.commitment = await generateCommitment();
  localStorage.setItem(
    "zktree-vote-commitment",
    JSON.stringify(this.commitment)
  );
}

The ValidatorTool component is used by the validator to send the commitment to the blockchain. It reads the contract address from the contracts.json (generated by the deployment process) and sends the commitment with the unique hash to the voting contract.

const abi = [
  "function registerCommitment(uint256 _uniqueHash, uint256 _commitment)",
];
const provider = new ethers.providers.Web3Provider(
  (window as any).ethereum
);
await provider.send("eth_requestAccounts", []);
const signer = provider.getSigner();
const contracts = await (await fetch("contracts.json")).json();
const contract = new ethers.Contract(contracts.zktreevote, abi, signer);
try {
  await contract.registerCommitment(this.uniqueHash, this.commitment);
} catch (e) {
  alert(e.reason);
}

The Vote component is used by the voter for voting. It generates the ZK proof by using the calculateMerkleRootAndZKProof method from zk-merkle-tree and sends it to the blockchain with the nullified.

const commitment = JSON.parse(
  localStorage.getItem("zktree-vote-commitment")
);

const abi = [
  "function vote(uint _option,uint256 _nullifier,uint256 _root, 
   uint[2] memory _proof_a,uint[2][2] memory _proof_b,
   uint[2] memory _proof_c)",
];
const provider = new ethers.providers.Web3Provider(
  (window as any).ethereum
);
await provider.send("eth_requestAccounts", []);
const signer = provider.getSigner();
const contracts = await (await fetch("contracts.json")).json();
const contract = new ethers.Contract(contracts.zktreevote, abi, signer);
const cd = await calculateMerkleRootAndZKProof(
  contracts.zktreevote,
  signer,
  TREE_LEVELS,
  commitment,
  "verifier.zkey"
);
try {
  await contract.vote(
    this.option,
    cd.nullifierHash,
    cd.root,
    cd.proof_a,
    cd.proof_b,
    cd.proof_c
  );
} catch (e) {
  alert(e.reason);
}

As you can see, the code is really simple, because all of the complexity of ZKP is hidden by the zk-merkle-tree library. Based on this code, you can easily build your own voting system.

Possible improvements:

Voter whitelisting. You can build a Merkle tree from the unique hashes of the voters before voting, and check the voter’s existence in it when the validator sends the commitment. It prevents the use of fake identities.
Better validator management. If there are thousands of validators, then a Merkle tree is a better way to batch-register them. If voters and validators are divided into districts, then you can generate separate Merkle trees for districts, and assign the validators to these trees.
Better validation method. The only way to cheat in this system is if somebody uses a fake identity for voting. This is why validation is very important. There are more methods to prevent malicious validators. For example, the system can randomly choose 2 or 3 validators for one voter. It has very little chance that all of them are malicious. Or it can record the validation process, and other validators randomly check the recorded videos. Cheating on voting is a crime, so it has a very high risk for the validator to be malicious.
Integration of video conferencing systems like Jitsi Meet. Sending the commitment, and the whole validation process can be very easy if the video conferencing system is integrated. Voters can fill out a form with their data and send it before the validation. The validator has to only check the ID card through the camera, and if everything is well, he can send the commitment and the unique hash to the blockchain with a button click.
Digital ID card support. If the voter has a digital ID card that can be used for digitally signing the commitment, then the whole validation process can be skipped. This method is super cheap because no human resource is needed, so it can be used frequently, and voters can be more involved in decision-making.

Democracy is the most important aspect of blockchain, and Web3 and blockchain-based anonymous voting are the holy grail of it.

I hope this short article and the zk-merkle-tree library can be a good starting point for others to make their own systems that will be used in the real world one day.

Karma: An ERC20-compatible Reputation-based Money on the Ethereum Blockchain

Laszlo Fazekas — Fri, 29 Dec 2023 08:58:07 +0000

Have you ever thought about how money is created? Well, typically, it is made out of nothing by banks. When someone takes out a loan, the bank adds the borrowed money to the amount already recorded in its database for the bank account. So if $100 was already present in the database entry for the bank account and someone takes out a loan of $10,000, the bank will rewrite the entry's content to $10,100. Thus, the bank loans out money it does not have. Of course, the loan must be repaid.

When the loan is repaid, the money created by the loan disappears. So this money comes out of nothing and disappears into nothing (let’s not get into the subject of interest, which complicates matters a bit). This money thus only exists temporarily. There is a parable about the point of money that exists only temporarily.

A cowboy walks into the bar. After a few drinks, the barkeep asks him if he would lend him $10 to fix a hole in the roof. The cowboy agrees to lend the $10, with the condition that it would be paid back in a week. The barkeep calls a roofer, who fixes the roof, and the barkeep pays the $10. Meanwhile, the roofer’s shoe falls apart, and he goes to the cobbler to buy a new one for another $10. The cobbler is delighted by his unexpected windfall and quickly has the money spent in the same bar. The $10 thus returns to the barkeep.

When a week passes, the cowboy returns and the barkeep returns the $10. The cowboy thanks him, pulls out a match, and burns the money. The barkeep, eyes wide, asks, ‘Why did you do that?’, to which the cowboy replies, ‘It’s fake money; it’s worth nothing.’

In the parable, the cowboy is like a bank. He lends money he doesn’t have. He creates this money out of thin air, and it disappears like bank loans when it is burned. Nevertheless, the bar got a new roof from this temporary money, the roofer received a new pair of shoes, and the cobbler had enough money to down a few drinks. These are tangible results of money that exists only temporarily. So what we use as money is nothing more than somebody’s debt. Money is debt!

The value of money is ultimately based on a form of trust. We trust that others value it as well, so when we do something for someone in exchange, we accept money because we trust that it will be accepted when we require something in return. This trust makes money a universal medium of exchange.

A good example of this is Bitcoin. Our Bitcoin balance is nothing more than an entry in a distributed ledger. There is nothing to back it up, yet people around the world are willing to pay real money for Bitcoin. The value of Bitcoin is thus purely a matter of trust. Money is trust!

These were the basic ideas that inspired the concept of karma money. What if everyone operated like a bank? Instead of taking money on credit, they would create it themselves. Of course, such a system would only work if there was a limit to the amount of money that could be created. So everyone’s debt would be public.

If I had to choose who to sell my products or services to, I would give it to the one with the least debt, as this gives the best chance of it being paid back quickly. Therefore, everyone is interested in keeping their debt low by repaying it.

Let’s look at how a cowboy parable would look in this system. There is no need for a cowboy (bank), as the barkeeper can create the $10 for the roofer himself. This creates a $10 debt for the barkeeper visible to everyone, but in return, his roof is fixed. The roofer passes this $10 on to the cobbler, and when the cobbler passes it back to the barkeeper, the $10 is destroyed along with the barkeeper’s debt. Thus, the barkeeper’s debt is again zero.

Thus, the process of creating transient money works well even without banks. All that is needed is for the roofer to trust the money created by the barkeeper and to believe that it is equally good money as the $10 created by the bank.

I have realized this karma money on the Ethereum Blockchain with a simple Solidity smart contract. My karma implementation is an ERC20 contract, which is great because it can easily be used with any Ethereum wallet. The peculiarity of karma is that, while in the case of other currencies, we spend from our balance, here, our balance starts from zero and increases with every spending (money creation). The greater our balance, the more indebted we become, so the goal is to reduce our balance.

Let’s look at a brief example. Alice wants to buy apples from John, so she pays John ten karma dollars for the apples. Alice’s balance thus increases to $10. Later, John buys oranges from Alice, so when he pays $10 to Alice, the debt is settled, and Alice’s balance is reduced back to $0.

After the theory, let us take a look at the code (available on GitHub):

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.19;

import "@openzeppelin/contracts/token/ERC20/ERC20.sol";
import "@openzeppelin/contracts/token/ERC20/extensions/IERC20Metadata.sol";

contract Karma is IERC20, IERC20Metadata {
    mapping(address => uint256) private _balances;
    mapping(address => mapping(address => uint256)) private _debts;
    mapping(address => mapping(address => uint256)) private _allowances;

    string private _name;
    string private _symbol;
    uint private _cycleReward;

    constructor(string memory name_, string memory symbol_, uint cycleReward) {
        _name = name_;
        _symbol = symbol_;
        _cycleReward = cycleReward;
    }

    function name() public view virtual override returns (string memory) {
        return _name;
    }

    function symbol() public view virtual override returns (string memory) {
        return _symbol;
    }

    function decimals() public view virtual override returns (uint8) {
        return 18;
    }

    // totalSupply is meaningless
    function totalSupply() public view virtual override returns (uint256) {
        return 0;
    }

    function balanceOf(
        address account
    ) public view virtual override returns (uint256) {
        return _balances[account];
    }

    function debtOf(
        address debtor,
        address creditor
    ) public view virtual returns (uint256) {
        return _debts[debtor][creditor];
    }

    function transfer(
        address to,
        uint256 amount
    ) public virtual override returns (bool) {
        _transfer(msg.sender, to, amount);
        return true;
    }

    function allowance(
        address owner,
        address spender
    ) public view virtual override returns (uint256) {
        return _allowances[owner][spender];
    }

    function approve(
        address spender,
        uint256 amount
    ) public virtual override returns (bool) {
        require(spender != address(0), "ERC20: approve to the zero address");

        address owner = msg.sender;
        _allowances[owner][spender] = amount;
        emit Approval(owner, spender, amount);
        return true;
    }

    function transferFrom(
        address from,
        address to,
        uint256 amount
    ) public virtual override returns (bool) {
        _spendAllowance(from, msg.sender, amount);
        _transfer(from, to, amount);
        return true;
    }

    function mineCycle(
        address[] memory nodes,
        uint256 amount
    ) public virtual returns (bool) {
        // checking debts in cycle from 0..n
        for (uint i = 0; i < nodes.length - 1; i++) {
            require(
                _debts[nodes[i]][nodes[i + 1]] >= amount,
                "Karma: Not enough debt for the cycle"
            );
        }

        // checking the last debt (end of cycle)
        require(
            _debts[nodes[nodes.length - 1]][nodes[0]] >= amount,
            "Karma: Not enough debt for the cycle"
        );

        // decreasing the debts and balances and pay cyleReward
        for (uint i = 0; i < nodes.length - 1; i++) {
            _debts[nodes[i]][nodes[i + 1]] -= amount;
            _balances[nodes[i]] -= amount;
            _transfer(nodes[i], msg.sender, _cycleReward);
        }

        _debts[nodes[nodes.length - 1]][nodes[0]] -= amount;
        _balances[nodes[nodes.length - 1]] -= amount;
        _transfer(nodes[nodes.length - 1], msg.sender, _cycleReward);

        return true;
    }

    function _transfer(
        address from,
        address to,
        uint256 amount
    ) internal virtual {
        require(to != address(0), "ERC20: transfer to the zero address");

        _balances[from] += amount;
        _debts[from][to] += amount;

        emit Transfer(from, to, amount);
    }

    function _spendAllowance(
        address owner,
        address spender,
        uint256 amount
    ) internal virtual {
        uint256 currentAllowance = allowance(owner, spender);
        if (currentAllowance != type(uint256).max) {
            require(
                currentAllowance >= amount,
                "ERC20: insufficient allowance"
            );

            uint256 newAmount = currentAllowance - amount;
            _allowances[owner][spender] = newAmount;
            emit Approval(owner, spender, newAmount);
        }
    }
}

As can be seen, this is a completely standard ERC20 token. In the constructor, we can specify the token name and symbol and a parameter called cycleReward, which we will discuss later. Karma can represent dollars, euros, any money, but also time (e.g., I will work for you for one hour in exchange for one hour of work) or anything else. So karma is a general lending system.

The ERC20 standard’s balanceOf method is for querying any individual’s balance. Each person must be only linked to one Ethereum address. If that were not the case, then if someone got very indebted, they would simply open a new account, thus the whole system would be pointless. Fortunately, there are solutions such as Proof of Humanity or WorldCoin, which can ensure that each individual has a unique address.

I also introduced a debtOf function, which can precisely query who owes how many points to whom.

The standard transfer function is used for moving the balance. On the one hand, this increases the user’s balance; on the other, it records the debt to the receiving party. Therefore, if Alice pays John $10, Alice’s balance will be increased by $10, and it will be noted that Alice owes John $10.

It may appear that the code isn’t exactly doing what I described earlier. For instance, if John now pays Alice $10, instead of Alice and John having a balance of $0, Alice’s balance will stay at $10, and John’s balance will also become $10. In addition, in the debt matrix, Alice will now owe John $10, and John will owe Alice $10. Why doesn’t the smart contract resolve these debts?

Alice and John’s case is very straightforward, but typically, much more complicated debt chains form. In the cowboy example, there were three people along the chain. However, it is conceivable for a chain to contain ten or more people. Finding such chains is by no means trivial. This is why karma miners are needed.

The karma miners constantly watch the debt graph; if they discover a cycle, they can submit it to the smart contract. This is what the mineCycle method is for. The method checks the submitted chain; if it is valid, it will execute the modifications to balances. For this, the miner will receive a small karma from each member of the chain for reducing their balances (the amount of reward is defined by the cycleReward).

Thus, karma mining is almost exactly the same as mining Bitcoin. The member runs a program on their machine, consuming electricity and computation power (finding cycles in a graph), producing karma in return.

There are still a few ERC20 standard-related methods, but these are not of interest from a system standpoint.

Karma can be an ideal solution for communities seeking an alternative to the traditional money system. But members of such a system can also be companies or projects. For example, an open source project can accept donations and pay developers in karma, who can then exchange this for, say, locally grown vegetables and fruits in a community using karma.

Of course, there is no legal framework backing up karma like there is for actual money, but Bitcoin has shown that a currency can work purely on trust — without any backing. Compared to Bitcoin, karma does not require huge computing power, nor does it have a country’s energy consumption. The system relies on trust, and our identity backs the money.

UPDATE: I wrote a short article about how karma could be implemented on any blockchain paying the gas fee in karma instead of the chain’s native currency.

How to Implement a ZK rollup

Laszlo Fazekas — Tue, 26 Dec 2023 22:51:28 +0000

Zero-knowledge rollups (ZK-rollups) are layer 2 scaling solutions that increase throughput on Ethereum Mainnet by moving computation and state-storage off-chain. ZK-rollups can process thousands of transactions in a batch and then only post some minimal summary data to Mainnet. This summary data defines the changes that should be made to the Ethereum state and some cryptographic proof that those changes are correct. - Ethereum documentation

Sounds good? Why not implement our own rollup just for fun?

In this article, we will develop a minimal Zero-knowledge rollup. It is important to note that the article's primary goal is for the reader to understand the technology, so rather than focusing on efficiency, the emphasis will be on simplicity and understandability.

The prerequisite for understanding this article is knowing the basics of ZKP technology, the Circom language, and the SnarkJS library. If these topics are all foreign to you, then it is worth reading my article on ZKP technology, as well as my article on programming with Circom and SnarkJS.

Implementing a zkRollup is not a straightforward task. Before we get started, we need to become familiar with the concept of Sparse Merkle Tree (SMT).

The Sparse Merkle Tree is a key/value storage. In this respect, it is similar to a Merkle Patricia Trie (Ethereum stores all data in such structures) but much simpler. Whereas the Merkle Patricia Tree is a complex data structure, the Sparse Merkle Tree is a simple binary tree, where each parent stores the hash of its children, with the stored values being the leaf elements, similar to a general Merkle tree. It becomes a key/value storage by having the child elements' paths determined by the key bits. Let's look at the following very simple Merkle tree, which is two levels deep and contains 4 values:

In this tree, two-bit keys can address the elements. If the key's given bit is 0, we go left in the tree; if it's 1, we go right. For example, if the key is 10, first we go right and then left, thus reaching the element L3. Of course, a two-bit key doesn't make much sense in practice, and the tree's size grows exponentially with the key's size, hence storing such a tree requires a lot of storage capacity for large keys. So if we wanted to store, say, five numbers in the tree but the key size is 16 bits, we'd have to store 65536 values, 5 of which are meaningful and 65531 of which are 0. That is why this structure is called the Sparse Merkle Tree because we typically store far fewer values in it than its capacity. Fortunately, such a structure can be compressed quite adeptly: it is enough to go down a structure as deep as there are relevant bits.

Let's store 3 values in the above structure. Their keys are 00, 01, 10. To store the values corresponding to keys 00 and 01, we must go to level 2, but the value corresponding to the key 10 we can store on level 1. So, we get a tree where on the left side of the root element there is a branch node with 2 leaves, whereas on the right side, there is a leaf node directly. With this “pruning” of the binary tree, we can store the elements very efficiently.

The advantage of SMT over the general Merkle tree is that it not only allows us to provide an inclusion proof but also an exclusion proof. This means that we can prove that a tree does not contain a value for the given key. Thanks to this, we can prove any operation (insert, delete, update), which will be a very important property of our rollup. Fortunately, Circomlib (and CircomlibJS) includes an SMT implementation, so we do not need to implement this ourselves.

Our rollup will store NFTs in an SMT. The NFT's ID will be the key, with its value being the current owner's public key. For NFTs to be transferred, the owner must produce a digitally signed transaction containing the new owner's public key and the NFT's identifier. The owner must prove two things: one, that they signed the transaction, and two, that they are the owner of the NFT so that their public key is stored with the NFT's ID. If these two proofs are valid, then the ownership of the NFT will be changed to the new owner.

The sequencer collects these NFT transfer transactions, calculates the Merkle root following the transactions, and then sends the new root, list of transactions, and a zero-knowledge proof to a smart contract that proves that the sent transactions truly generate the sent root. The smart contract checks the zero-knowledge proof and if the check is successful, modifies the root.

Anyone can submit transaction batches to a smart contract if they present the corresponding zero-knowledge proofs. To do this, they need to set up the SMT which is easily accomplished since all the transactions are written on the blockchain. There is a special variation of Rollups, called Validium, where the transactions are not written on the blockchain but stored on an external repository (e.g. IPFS or Swarm). This is an even cheaper solution but we have to guarantee data availability. For example, in a DAO, we must select validators who have to sign the state root modification and only then sign the transaction after they have verified that the data is indeed available.

Here is a very simple summary graphic from Vitalik Buterin:

In a nutshell, that's how our rollup works. Doesn't sound too complicated, right? We'll see from the code that the devil is in the details. Let's take a look at the code. (Of course, all code is available on GitHub.)

For simplicity, we will pre-create the NFTs and they cannot be moved from the rollup to the blockchain (the NFTs only exist on the rollup), so it is enough to implement the NFT transfer (which itself is sufficiently complex). At the end of the article, I will explain how to further develop our rollup to enable NFTs to be moved between the blockchain and the rollup.

As a first step, let's generate the wallet user accounts. Similar to Ethereum accounts, each Rollup account will have a private key, a public key, and an address, however, instead of ECDSA we use EDDSA for digital signing of transactions. EDDSA is a ZKP-friendly digital signature format. We'll randomly generate the private keys and generate the addresses from the public keys with the help of Poseidon Hash (a ZKP-friendly hash algorithm). Here's the code that generates 5 test accounts:

for (let i = 0; i < 5; i++) {
  // generate private and public eddsa keys, 
  // the public address is the poseidon hash of the public key
  const prvKey = randomBytes(32);
  const pubKey = eddsa.prv2pub(prvKey);
  accounts[i] = {
    prvKey: prvKey,
    pubKey: pubKey,
    address: trie.F.toObject(poseidon(pubKey))
  }
}

We convert the Poseidon hash to a finite field at address generation using the trie.F.toObject function.

The next step is to create the NFTs. For this, we create an SMT and fill it correctly. The key in the SMT is the NFT ID and the associated value is the address of the NFT owner. (I will write about nonce SMT later.)

// generate 5 NFTs, and set the first account as owner
for (let i = 1; i <= 5; i++) {
  await trie.insert(i, accounts[0].address)
  await nonceTrie.insert(i, 0)
}

The first task to solve is to enable users to create digitally signed transactions. A transaction consists of 3 data elements. The NFT ID of the asset to be moved, the destination address of the NFT to be sent, and a nonce. The nonce is an incrementing counter needed to make each transaction unique and only executable once. This is very similar to the solution that Ethereum uses for making transactions unique, except that Ethereum assigns the nonce to the Ethereum address, while in our case we assign it to the NFT. If we were to assign the nonce to the address, we would need a larger SMT (if the address is the key then the key size is 32-bit), so it is more practical to associate with the NFT (which needs only a 10-bit tree). Therefore the transaction is a Poseidon hash of these 3 values. This is digitally signed using EDDSA.

const createTransferRequest = (owner: Account, target: Account, 
  nftID: number, nonce: number): TransferRequest => {
  const transactionHash = poseidon([
    buffer2hex(target.address), nftID, buffer2hex(nonce)
  ])
  const signature = eddsa.signPoseidon(owner.prvKey, 
    transactionHash);
  return {
    ownerPubKey: owner.pubKey,
    targetAddress: target.address,
    nftID: nftID,
    nonce: nonce,
    signature: signature
  }
}

This transaction can be verified with the following Circom circuit:

pragma circom 2.0.0;

include "../node_modules/circomlib/circuits/eddsaposeidon.circom";
include "../node_modules/circomlib/circuits/poseidon.circom";

template VerifyTransferRequest() {

    signal input targetAddress;
    signal input nftID;
    signal input nonce;

    signal input Ax;
    signal input Ay;
    signal input S;
    signal input R8x;
    signal input R8y;

    component eddsa = EdDSAPoseidonVerifier();
    component poseidon = Poseidon(3);

    // calculate the transaction hash

    poseidon.inputs[0] <== targetAddress;
    poseidon.inputs[1] <== nftID;
    poseidon.inputs[2] <== nonce;

    // verify the signature on the transaction hash

    eddsa.enabled <== 1;
    eddsa.Ax <== Ax;
    eddsa.Ay <== Ay;
    eddsa.S <== S;
    eddsa.R8x <== R8x;
    eddsa.R8y <== R8y;
    eddsa.M <== poseidon.out;

}

The first 3 input signals (targetAddress, nftID, nonce) are the data of the transaction, while the next 5 (Ax, Ay, S, R8x, R8y) are the public key and digital signature. The circuit first calculates the poseidon hash from the data of the transaction, then verifies the digital signature and that it belongs to the given public key.

The following code snippet shows how to check the circuit using TypeScript:

const transferRequest = await createTransferRequest(accounts[0], accounts[1], 1, 0)

const inputs = {
  targetAddress: buffer2hex(transferRequest.targetAddress),
  nftID: transferRequest.nftID,
  nonce: buffer2hex(transferRequest.nonce),
  Ax: eddsa.F.toObject(transferRequest.ownerPubKey[0]),
  Ay: eddsa.F.toObject(transferRequest.ownerPubKey[1]),
  R8x: eddsa.F.toObject(transferRequest.signature.R8[0]),
  R8y: eddsa.F.toObject(transferRequest.signature.R8[1]),
  S: transferRequest.signature.S,
}

const w = await verifyTransferCircuit.calculateWitness(inputs, true);
await verifyTransferCircuit.checkConstraints(w);

Every input signal of the circuit is a BigNumber. The targetAddress and the nonce are converted to hexadecimal BigNumber format using the bufer2hex function, while the Ax, Ay, R8x, and R8y signals are converted to finite field format using eddsa.F.toObject. This is necessary because, in the world of zero-knowledge proofs, all calculations are done in a finite field. For the targetAddress, the nonce, the nftID, and the S parameter, this is not necessary, since they are already mapped to a finite field.

I used the circom_tester library to check a circuit, which is a very effective solution for testing circuits since there is no need to compile the circuit for testing. The calculateWitness function calculates the witness which is then checked by checkConstraints.

The next step is to run a full transaction and generate the proof for it:

const transferNFT = async (from: Account, to: Account, nftID: number) => {
  // get the nonce for the NFT
  const nonce = BigNumber.from(
    nonceTrie.F.toObject((await nonceTrie.find(nftID)).foundValue)
  ).toNumber()

  // creating transfer request
  const transferRequest = await createTransferRequest(from, to, nftID, nonce)

  // move the NFT to the new owner
  const nft_res = await trie.update(nftID, transferRequest.targetAddress)

  // increase nonce for the NFT
  const nonce_res = await nonceTrie.update(nftID, transferRequest.nonce + 1)

  // generate and check zkp
  let nft_siblings = convertSiblings(nft_res.siblings)
  let nonce_siblings = convertSiblings(nonce_res.siblings)

  const inputs = {
    targetAddress: buffer2hex(transferRequest.targetAddress),
    nftID: transferRequest.nftID,
    nonce: buffer2hex(transferRequest.nonce),
    Ax: eddsa.F.toObject(transferRequest.ownerPubKey[0]),
    Ay: eddsa.F.toObject(transferRequest.ownerPubKey[1]),
    R8x: eddsa.F.toObject(transferRequest.signature.R8[0]),
    R8y: eddsa.F.toObject(transferRequest.signature.R8[1]),
    S: transferRequest.signature.S,
    oldRoot: trie.F.toObject(nft_res.oldRoot),
    siblings: nft_siblings,
    nonceOldRoot: trie.F.toObject(nonce_res.oldRoot),
    nonceSiblings: nonce_siblings
  }

  const w = await verifyRollupTransactionCircuit.calculateWitness(inputs, true);
  await verifyRollupTransactionCircuit.checkConstraints(w);
  await verifyRollupTransactionCircuit.assertOut(w, {
    newRoot: trie.F.toObject(nft_res.newRoot),
    nonceNewRoot: trie.F.toObject(nonce_res.newRoot)
  });

}

As a first step, we read the nonce associated with the NFT to generate the transaction. To run the transaction, we update the SMT from the owner to the new owner and increment the nonce value by one in the nonce SMT. The update function, in addition to performing the modifications, returns the siblings that are needed to prove the operation.

We check the proper execution of the circuit as usual with the checkConstraints function. If the circuit works correctly, then the two outputs must match the new roots of the SMTs.

Let's look at the circuit that verifies the transaction:

pragma circom 2.0.0;

include "verify-transfer-req.circom";
include "../node_modules/circomlib/circuits/smt/smtprocessor.circom";
include "../node_modules/circomlib/circuits/poseidon.circom";

template RollupTransactionVerifier(nLevels) {

    signal input targetAddress;
    signal input nftID;
    signal input nonce;

    signal input Ax;
    signal input Ay;
    signal input S;
    signal input R8x;
    signal input R8y;

    signal input oldRoot;
    signal input siblings[nLevels];

    signal input nonceOldRoot;
    signal input nonceSiblings[nLevels];

    signal output newRoot;
    signal output nonceNewRoot;

    component transferRequestVerifier = VerifyTransferRequest();
    component smtVerifier = SMTProcessor(nLevels);
    component nonceVerifier = SMTProcessor(nLevels);
    component poseidon = Poseidon(2);

    // verify the transfer request

    transferRequestVerifier.targetAddress <== targetAddress;
    transferRequestVerifier.nftID <== nftID;
    transferRequestVerifier.nonce <== nonce;

    transferRequestVerifier.Ax <== Ax;
    transferRequestVerifier.Ay <== Ay;
    transferRequestVerifier.S <== S;
    transferRequestVerifier.R8x <== R8x;
    transferRequestVerifier.R8y <== R8y;

    // verify the SMT update
    // the old value of the NFT ID key has to be the poseidon hash of 
    // the signers public key, 
    // the new value is the target address 

    poseidon.inputs[0] <== Ax;
    poseidon.inputs[1] <== Ay;

    smtVerifier.fnc[0] <== 0;
    smtVerifier.fnc[1] <== 1;
    smtVerifier.oldRoot <== oldRoot;
    smtVerifier.siblings <== siblings;
    smtVerifier.oldKey <== nftID;
    smtVerifier.oldValue <== poseidon.out;
    smtVerifier.isOld0 <== 0; 
    smtVerifier.newKey <== nftID;
    smtVerifier.newValue <== targetAddress;

    // verify nonce SMT update, the new value has to be the old value + 1

    nonceVerifier.fnc[0] <== 0;
    nonceVerifier.fnc[1] <== 1;
    nonceVerifier.oldRoot <== nonceOldRoot;
    nonceVerifier.siblings <== nonceSiblings;
    nonceVerifier.oldKey <== nftID;
    nonceVerifier.oldValue <== nonce;
    nonceVerifier.isOld0 <== 0; 
    nonceVerifier.newKey <== nftID;
    nonceVerifier.newValue <== nonce + 1;

    newRoot <== smtVerifier.newRoot; 
    nonceNewRoot <== nonceVerifier.newRoot;

}

The RollupTransactionVerifier template has one parameter: the depth of the SMT. The inputs are the digitally signed transaction, the previous roots of the SMT-s, and the siblings. We have to prove that:

The transaction is valid
The address of the user signing the transaction is associated with the NFT moved in the SMT
In the SMT the address associated with the NFT was modified to the new address (targetAddress)
The nonce was increased by one in the SMT for the associated NFT.

In the first block, we verify the transaction with the VerifyTransferRequest circuit previously presented.

In the second block, we validate the SMT modification. To do this, we calculate the address of the transaction signer from the Ax and Ay parameters using a Poseidon hash. The transaction is valid if this address was originally assigned to the NFT.

We can prove SMT modification with the SMTProcessor circuit. This is a general circuit that is suitable for proving every transformation (insert, update, delete). The fnc signal determines the function of the circuit. If the fnc value is 01, we can prove an update. The transaction is valid if the old value (oldValue) linked to the nftID is the address of the signer of the transaction (the Poseidon hash of the public key) and the new value (newValue) is the tragetAddress specified in the transaction.

In the third block, we validate that the nonce in SMT has increased by one. If all conditions have been met, then the circuit output is the new root of SMT and the nonce SMT.

Now that we can validate a transaction, all that is left to do is create the final circuit that can validate a whole batch. This is what the final circuit looks like:

pragma circom 2.0.0;

include "rollup-tx.circom";
include "../node_modules/circomlib/circuits/sha256/sha256.circom";
include "../node_modules/circomlib/circuits/bitify.circom";
include "../node_modules/circomlib/circuits/poseidon.circom";

template Rollup(nLevels, nTransactions) {

    signal input oldRoot;
    signal input newRoot;

    signal input nonceOldRoot;
    signal input nonceNewRoot;

    signal input nonceList[nTransactions];
    signal input targetAddressList[nTransactions];
    signal input nftIDList[nTransactions];

    signal input AxList[nTransactions];
    signal input AyList[nTransactions];
    signal input SList[nTransactions];
    signal input R8xList[nTransactions];
    signal input R8yList[nTransactions];

    signal input siblingsList[nTransactions][nLevels];
    signal input nonceSiblingsList[nTransactions][nLevels];

    signal input transactionListHash;
    signal input oldStateHash;
    signal input newStateHash;

    // verify the transactions in the transaction list, and calculate the new roots

    var root = oldRoot;
    var nonceRoot = nonceOldRoot;
    component rollupVerifiers[nTransactions];
    for (var i = 0; i < nTransactions; i++) {
        rollupVerifiers[i] = RollupTransactionVerifier(nLevels);

        rollupVerifiers[i].targetAddress <== targetAddressList[i];
        rollupVerifiers[i].nftID <== nftIDList[i];
        rollupVerifiers[i].nonce <== nonceList[i];

        rollupVerifiers[i].Ax <== AxList[i];
        rollupVerifiers[i].Ay <== AyList[i];
        rollupVerifiers[i].S <== SList[i];
        rollupVerifiers[i].R8x <== R8xList[i];
        rollupVerifiers[i].R8y <== R8yList[i];

        rollupVerifiers[i].siblings <== siblingsList[i];
        rollupVerifiers[i].oldRoot <== root;

        rollupVerifiers[i].nonceSiblings <== nonceSiblingsList[i];
        rollupVerifiers[i].nonceOldRoot <== nonceRoot;

        root = rollupVerifiers[i].newRoot;
        nonceRoot = rollupVerifiers[i].nonceNewRoot;
    }

    // compute sha256 hash of the transaction list

    component sha = Sha256(nTransactions * 2 * 32 * 8);
    component address2bits[nTransactions];
    component nftid2bits[nTransactions];

    var c = 0;

    for(var i=0; i<nTransactions; i++) {
        address2bits[i] = Num2Bits(32 * 8);
        address2bits[i].in <== targetAddressList[i];
        for(var j=0; j<32 * 8; j++) {
            sha.in[c] <== address2bits[i].out[(32 * 8) - 1 - j];
            c++;
        }
    }

    for(var i=0; i<nTransactions; i++) {
        nftid2bits[i] = Num2Bits(32 * 8);
        nftid2bits[i].in <== nftIDList[i];
        for(var j=0; j<32 * 8; j++) {
            sha.in[c] <== nftid2bits[i].out[(32 * 8) - 1 - j];
            c++;
        }
    }

    component bits2num = Bits2Num(256);
    for(var i=0; i<256; i++) {
        bits2num.in[i] <== sha.out[255 - i];
    }

    // check the constraints

    transactionListHash === bits2num.out;
    newRoot === root;
    nonceNewRoot === nonceRoot;

    component oldStateHasher = Poseidon(2);
    oldStateHasher.inputs[0] <== oldRoot;
    oldStateHasher.inputs[1] <== nonceOldRoot;

    component newStateHasher = Poseidon(2);
    newStateHasher.inputs[0] <== newRoot;
    newStateHasher.inputs[1] <== nonceNewRoot;

    oldStateHash === oldStateHasher.out;
    newStateHash === newStateHasher.out;

}

component main {public [oldStateHash, newStateHash, transactionListHash]} = 
  Rollup(10, 8);

The main point is the first block where we invoke the RollupTransactionVerifier that we introduced earlier in an iteration. We set the root and the nonceRoot variables to the current root of the SMT and the nonce SMT respectively. Then we execute the transactions sequentially and always update the values of the root and the nonceRoot variables. After executing the transactions, we get the final roots which can be stored on the blockchain. The first version of the rollup only included this block, and the transaction data was public inputs, but it was not very efficient.

If we validate a zero-knowledge proof on-chain with a smart contract, the cost of validation depends on the number of public variables, thus the cost of validation increases with the number of transactions as well. Therefore, I modified the rollup circuit to use the sha256 hash of the transactions instead of the list of transactions. This is sufficient for validating the transactions and only 1 input instead of many. The second block thus calculates the sha256 hash of the transactions and compares it with the transactionListHash input, which is produced by the smart contract. Computing the sha256 hash in a circom circuit is a bit tricky as the order of bits is not trivial, but after a few days of research, reading, and trying out, I found the correct method for calculating the hash.

At the end of the circuit, there is still a little optimization in block 3. The circuit originally used 2 SMT roots, the NFT state root, and the nonce state root. From these I formed an oldStateHash and a newStateHash value via a Poseidon hash, so instead of 4 the number of state parameters was reduced to 2 and only 1 state root needs to be stored on the blockchain instead of 2. Therefore, the rollup finally had 3 public inputs: the oldStateHash which is the initial state, the transactionListHash which is the sha256 hash of the transaction list and the newStateHash which is the final state that will be stored on the blockchain.

This is the TypeScript code that produces the zero-knowledge proof using the above circuit, which validates a full batch:

const generateBatchTransferZKP = async (_trie: any, _nonceTrie, 
  transferRequestList: TransferRequest[]) => {
  let targetAddressList = []
  let nftIDList = []
  let nonceList = []
  let AxList = []
  let AyList = []
  let SList = []
  let R8xList = []
  let R8yList = []
  let siblingsList = []
  let nonceSiblingsList = []

  const oldRoot = _trie.F.toObject(_trie.root)
  const nonceOldRoot = _nonceTrie.F.toObject(_nonceTrie.root)

  for (const transferRequest of transferRequestList) {
    targetAddressList.push(buffer2hex(transferRequest.targetAddress))
    nftIDList.push(buffer2hex(transferRequest.nftID))
    nonceList.push(buffer2hex(transferRequest.nonce))
    AxList.push(eddsa.F.toObject(transferRequest.ownerPubKey[0]))
    AyList.push(eddsa.F.toObject(transferRequest.ownerPubKey[1]))
    SList.push(transferRequest.signature.S)
    R8xList.push(eddsa.F.toObject(transferRequest.signature.R8[0]))
    R8yList.push(eddsa.F.toObject(transferRequest.signature.R8[1]))

    const res = await _trie.update(transferRequest.nftID, 
      transferRequest.targetAddress)
    siblingsList.push(convertSiblings(res.siblings))

    const res2 = await _nonceTrie.update(transferRequest.nftID, 
      transferRequest.nonce + 1)
    nonceSiblingsList.push(convertSiblings(res2.siblings))
  }

 const newRoot = _trie.F.toObject(_trie.root)
  const nonceNewRoot = _nonceTrie.F.toObject(_nonceTrie.root)

  let transactionBuffers = []
  for (const transferRequest of transferRequestList) {
    transactionBuffers.push(numToBuffer(transferRequest.targetAddress))
  }
  for (const transferRequest of transferRequestList) {
    transactionBuffers.push(numToBuffer(transferRequest.nftID))
  }
  const hash = createHash("sha256").update(Buffer.concat(transactionBuffers))
    .digest("hex")
  const ffhash = BigNumber.from('0x' + hash).mod(FIELD_SIZE)

  const oldStateHash = poseidon([oldRoot, nonceOldRoot])
  const newStateHash = poseidon([newRoot, nonceNewRoot])

  return await snarkjs.groth16.fullProve(
    {
      targetAddressList: targetAddressList,
      nftIDList: nftIDList,
      nonceList: nonceList,
      AxList: AxList,
      AyList: AyList,
      R8xList: R8xList,
      R8yList: R8yList,
      SList: SList,
      siblingsList: siblingsList,
      nonceSiblingsList: nonceSiblingsList,
      oldRoot: oldRoot,
      nonceOldRoot: nonceOldRoot,
      newRoot: newRoot,
      nonceNewRoot: nonceNewRoot,
      transactionListHash: ffhash.toHexString(),
      oldStateHash: poseidon.F.toObject(oldStateHash),
      newStateHash: poseidon.F.toObject(newStateHash)
    },
    "./build/rollup_js/rollup.wasm",
    "./build/rollup.zkey");
}

Finally, the smart contract, which stores the state root on the blockchain, as well as validates the zero-knowledge proof:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.19;

import "./RollupVerifier.sol";
import "hardhat/console.sol";

uint256 constant FIELD_SIZE = 
  21888242871839275222246405745257275088548364400416034343698204186575808495617;

interface IVerifier {
    function verifyProof(
        uint[2] memory a,
        uint[2][2] memory b,
        uint[2] memory c,
        uint[3] memory input
    ) external pure returns (bool r);
}

contract Rollup {
    IVerifier public immutable verifier;

    event RootChanged(uint newRoot);

    uint root;

    constructor(uint _root, IVerifier _verifier) {
        root = _root;
        verifier = _verifier;
    }

    function updateState(
        uint[2] calldata _pA,
        uint[2][2] calldata _pB,
        uint[2] calldata _pC,
        uint _oldRoot,
        uint _newRoot,
        uint[16] calldata transactionList
    ) external {
        require(root == _oldRoot, "Invalid old root");

        uint256 hash = uint256(sha256(abi.encodePacked(transactionList)));
        hash = addmod(hash, 0, FIELD_SIZE);

        require(
            verifier.verifyProof(_pA, _pB, _pC, [hash, _oldRoot, _newRoot]),
            "Verification failed"
        );

        root = _newRoot;
        emit RootChanged(root);
    }

    function getRoot() public view virtual returns (uint) {
        return root;
    }

}

The rollup contract itself is relatively simple. In the constructor, it receives the initial state root and the address of the ZKP verifier contract, which can be generated from snarkjs for the circuit. The contract has a single variable named root which stores the state root and emits a RootChanged event after each batch run.

The contract has a single updateState method. The first three parameters (_pA, _pB, _pC) of the method are the zero-knowledge proof. The _oldRoot is the old state root, the _newRoot is the new state root, and the transactionList is a list of transactions. The list includes a list of NFTs that we are moving and a list of target addresses that are the new owners of the NFTs. Since our example rollup consists of 8 elements, the transactionList will be 16 elements.

First, check if the _oldRoot matches the root stored in the smart contract. Then calculate the sha256 hash of the transaction list. Since, in the case of ZKP, every calculation is done in a finite field, we need to convert the hash into a finite field, which we do with the addmod function. Then run the validation on the proof, and if everything is OK, set the new root.

This is a TypeScript example code that produces the zero-knowledge proof and calls the smart contract:

trie = await newMemEmptyTrie()
nonceTrie = await newMemEmptyTrie()
let transferRequests = []
for (let i = 1; i <= BATCH_SIZE; i++) {
  await trie.insert(i, accounts[0].address)
  await nonceTrie.insert(i, 0)
  transferRequests.push(createTransferRequest(accounts[0], accounts[1], i, 0))
}

const oldRoot = trie.F.toObject(trie.root)
const nonceOldRoot = nonceTrie.F.toObject(nonceTrie.root)
const oldStateHash = poseidon.F.toObject(poseidon([oldRoot, nonceOldRoot]))

const Rollup = await ethers.getContractFactory("Rollup");
rollup = await Rollup.deploy(oldStateHash, await rollupVerifier.getAddress());

const { proof, publicSignals } = await generateBatchTransferZKP(
  trie, nonceTrie, transferRequests
)

const newRoot = trie.F.toObject(trie.root)
const nonceNewRoot = nonceTrie.F.toObject(nonceTrie.root)
const newStateHash = poseidon.F.toObject(poseidon([newRoot, nonceNewRoot]))

let transactionList: any = []
for (const transferRequest of transferRequests) {
  transactionList.push(transferRequest.targetAddress)
}
for (const transferRequest of transferRequests) {
  transactionList.push(BigNumber.from(transferRequest.nftID).toBigInt())
}

await rollup.updateState(
  [proof.pi_a[0], proof.pi_a[1]],
  [[proof.pi_b[0][1], proof.pi_b[0][0]], [proof.pi_b[1][1], proof.pi_b[1][0]]],
  [proof.pi_c[0], proof.pi_c[1]],
  publicSignals[1], publicSignals[2], transactionList
)

assert.equal(await rollup.getRoot(), newStateHash);

At the beginning of the article, we mentioned that the Rollup differs from Validium by storing the transaction list on the blockchain in the calldata. This is important because if anyone wants to submit a new batch to the smart contract, they need to build the SMTs. With Rollup, this can be easily done because every transaction is stored on the blockchain, from which the SMTs can be constructed. Let’s see the code that implements this:

 trie = await newMemEmptyTrie()
 nonceTrie = await newMemEmptyTrie()

 for (let i = 1; i <= BATCH_SIZE; i++) {
   await trie.insert(i, accounts[0].address)
   await nonceTrie.insert(i, 0)
 }

 const events = await rollup.queryFilter(rollup.filters.RootChanged)
 for (const event of events) {
   const tx = await event.provider.getTransaction(event.transactionHash)
   const pubSignals = rollup.interface.parseTransaction(tx).args.at(5)
   for (let i = 0; i < BATCH_SIZE; i++) {
     const address = pubSignals[i];
     const nftID = pubSignals[BATCH_SIZE + i];
     await trie.update(nftID, address)
     const nonce = BigNumber.from(
       nonceTrie.F.toObject((await nonceTrie.find(nftID)).foundValue)
     ).toNumber()
     await nonceTrie.update(nftID, nonce + 1)
   }

   const newRoot = trie.F.toObject(trie.root)
   const nonceNewRoot = nonceTrie.F.toObject(nonceTrie.root)
   const newStateHash = poseidon.F.toObject(poseidon([newRoot, nonceNewRoot]))

   assert.equal(newStateHash, rollup.interface.parseTransaction(tx).args.at(4))
}

As I wrote, a smart contract emits a RootChanged event after each batch run. This is useful because it enables us to collect the transactions from which we can extract the transaction data. In the code above, we query the events with the queryFilter method. The transaction hash associated with the event is available for the full transaction, which can be extracted with the parseTransaction method for the calldata, making the transactions accessible from which the SMT can be reconstructed, which is necessary for submitting new batches.

In a nutshell, this is how the minimalist NFT rollup works. Let's have a quick recap.

The Good

I compared a traditional NFT contract with a 64-element batch-size rollup. Moving 64 NFTs on-chain cost 2,965,696 gas, while running the 64-element batch cost only 299,575 gas. The cost of moving NFTs on rollup is thus about 10% of the on-chain solution, and we only store one root on the blockchain plus the list of transactions in the calldata (or nothing in the case of validium). This sounds pretty good. Moreover, the cost of ZKP validation does not depend on the number of transactions, so if there were 2x or 4x as many transactions in the batch, it wouldn't be much more expensive, so even more gas could be saved, and even more space on the blockchain.

The Bad

To compile a circuit, a lot of RAM and computational capability is required. On my laptop (24G RAM, i7) the largest circuit I could compile was around 64 elements. For a larger batch-size circuit (say 256 elements), a huge amount of RAM is needed. The compile time was also around half to one hour, and the fan was really roaring. Thankfully, generating the proof for the batch was much faster, but still had to wait a few minutes. This time can probably be improved a lot by using rapidsnark for proof generation, and the technology will also probably improve a lot in the future, for example using GPU or ASICs-based proof generation.

The Ugly

As I wrote at the beginning of the article, this is a minimalistic solution, whose aim is not efficiency but rather understanding, therefore, a lot more could still be improved.

Rollups typically compress transaction data to make use of fewer calldata. Our rollup stores addresses in 32 bytes and NFT IDs in 32 bytes as well, so every transaction in the batch uses 64 bytes of calldata. That is 4096 bytes for a 64-element batch. If we were to store NFT IDs in only 4 bytes and introduce a new SMT that maps addresses to IDs, then 4 bytes would be enough to store addresses too. That would mean only 8 bytes per transaction, resulting in only 512 calldata for a 64-element batch.

The other thing we mentioned is that it is not possible to move NFTs between the rollup and the blockchain, so we have to pre-generate all NFTs and keep them on the rollup only. We did this to keep our code simple. Moving items to rollup (deposits) could be accomplished through the introduction of a new Merkle tree. If someone wants to move an NFT to the rollup, they should lock it in the smart contract and provide the rollup address which will become the owner of the NFT on the rollup. This is stored in a Merkle tree managed by the smart contract. Then, a zero-knowledge proof has to be produced, including an SMT insert proof and an inclusion proof to ensure that the same address is supplied with the NFT in the Merkle tree managed by the smart contract. If all checks out okay, then the NFT will appear on the rollup and can be moved around as previously discussed.

To withdraw an NFT onto the blockchain, an SMT delete proof has to be sent to the rollup contract, digitally signed (with EDDSA) by the current owner of the NFT, and provided an Ethereum address where the smart contract can transfer the NFT.

Summary

Zero-knowledge proof technology and zk rollups are some of the hottest fields in the blockchain world where many breakthroughs can be expected. I envision the sole duty of the blockchains of the future being the validation of zk proofs and management of state roots since every asset will exist on rollups. There will be no need to run smart contracts on the blockchain as those will run off-chain and only the state root changes will be written to the blockchain which will be validated by the accompanying zero-knowledge proof. With this solution computing and storage will be much more efficiently distributed and blockchains will be able to much higher performance. An evermore efficient yet decentralized system.

These solutions already exist in our days. An example of this is the mina protocol, where smart contracts run off-chain and the PoS validators only collect and store the transactions. Mina isn't a blockchain since it replaces it with recursive proofs. Each block contains a proof of the validity of the previous block. Thanks to this, the “blockchain” of mina is only 22KB in size.

The future is very exciting. It is therefore worthwhile to get acquainted with zero-knowledge proof technology, as it is becoming an increasingly integral part of the blockchain world.

The Future of the World Wide Web May Be a Massive Vector Database

Laszlo Fazekas — Sun, 10 Dec 2023 07:40:39 +0000

Do you know how large corporate document databases work, where you can ask questions about the content of millions of documents? A Large Language Model (LLM) could be trained, but that would be prohibitively expensive and resource-intensive. Instead, the documents are chopped into chunks, each of which is assigned a vector and stored in a vector database. When someone asks a question, the question is also transformed into a vector, and the database is searched for chunks with vectors closest to the question vector. These chunks are then passed to an LLM to create a consistent answer to the question. The name of this technique is RAG. This process of converting document chunks into vectors is known as embedding. For instance, OpenAI’s ada-002 model maps document chunks to 1536-dimensional vectors. This means that each document chunk corresponds to a point in a 1536-dimensional space, with chunks of similar content being close to each other in this space, while those with differing content are farther apart. But is this enough? Can we map all possible questions and thoughts in the world to 1536 numbers?

In fact, 32 bytes is enough.

Distributed file systems like IPFS or Ethereum Swarm are content-addressable storage systems. Both systems are based on a distributed database, where content can be accessed based on a given hash. When we want to access a file in such a system, we can do so with a 32-byte hash.

By submitting this identifier to the system, it returns the content to us. This 32-byte identifier is generated based on the content and is unique for each piece of content. This means that every piece of content in the world can be assigned a unique 32-byte number.

Think about how fascinating this is. For every video, song, text, book, or program that has ever been created or will be created, there is a unique 32-byte identifier. If this were not the case, IPFS or Swarm would not be able to function, as an identifier would be associated with two different pieces of content in the system, causing collisions.

However, no one has ever found such a collision.

Although 32 bytes might not seem like much, it seems that in the world, we are able to compress almost everything into this size. Even a 32-byte hash can be imagined as a point in a 32-dimensional space. Therefore, embedding is a type of compression, similar to hashing. However, there is a major difference between hashing and embedding.

Hash algorithms map the contents to completely random points in the multi-dimensional space, while in the case of embedding, it is important for similar contents to be close to each other.

This is why hash algorithms use a relatively simple, fixed calculation, while embedding is a complex algorithm that is typically learned through training.

In the case of a distributed file system, we can access specific content with concrete hashes, while in the case of a large language model, we search for tokens that best match the embedding vector (which is some kind of a hash).

In both cases, we are talking about a vast database, but in the first case, the database contains specific values associated with concrete keys, while in the second case, both the keys and values are located in a continuous space.

How can we build a system that has access to all the knowledge in the world and can answer questions about anything? The first solution is a centralized system. Something like ChatGPT, which uses crawlers to collect data from the web, and then trains the model on it. Such systems are very static since if we want to add new knowledge to the model, it needs to be retrained (or at least fine-tuned).

We can give the LLM the ability to use tools, like a web search engine (as ChatGPT is also capable of doing this). In this case, the system is already dynamic but still centralized. The system’s operation is controlled by the operating company. Couldn’t this be somehow decentralized, as IPFS or Swarm does for storage?

Imagine the next version of the Web that is “self indexed”. Instead of crawling for information for central search engines and LLMs, content owners would generate embedding vectors for their content. This system would be similar to IPFS or Swarm in that the individual chunks can be accessed using hashes, but here we would use embedding vectors instead of the hash. Similarly to distributed file systems, we would store which content is available where in a DHT, but instead of using Kademlia distance, we would use cosine similarity. If someone wants to query the system, they would generate an embedding vector from the query and send it to known nodes with the lowest cosine similarity. The nodes would further broadcast the query to their known nodes and so on, similar to how we search in a DHT. The nodes respond by sending back the K closest chunks for that query. Finally, the chunks received as a result are summarized on the client side and the response is given to an LLM which provides a consistent response to the query.

This system is very similar to the way large corporate document databases operate, but a decentralized system takes the place of the vector database. This database is owned by no one and is always up-to-date. Data mining from the web would not be necessary as the web itself would be the database.

Of course, many problems should be solved with such a system. For instance, how can we trust the embeddings produced by the content creators? One solution would be to also generate a zero-knowledge proof for the embedding (ZKML), which would prove that the embedding was indeed generated from the document chunk. The zero-knowledge proof can be easily validated by the client, eliminating any false chunks.

A similar problem is filtering out fake data. One solution to this could be to rank the chunks or their creators on the basis of some kind of reputation system.

The users could rate the answers given by the system, which would result in feedback on the chunk’s reputation, and through federated learning, also adjust the LLM accordingly, so that the system itself could evolve. This is a form of RLHF.

In a nutshell, this is my concept of what the web’s future may look like, in the form of distributed artificial intelligence.

Zero-Knowledge Proofs Using SnarkJS and Circom

Laszlo Fazekas — Sat, 14 Jan 2023 00:10:18 +0000

The technology of zero-knowledge proof and especially zk-SNARK is one of the most exciting ones in the field of crypto because of the following reasons:

You can prove you have information without revealing it (for example, you can use it for anonymous voting).
The proof is small and easy to verify on the blockchain, so it can be used for rollups.

Rollup is a blockchain scaling solution where the computation is done off-chain, and after a given number of transactions the state is synchronized back to the blockchain. This solution gives you the security of the blockchain (after the synchronization), but the proof needs much less space (and less gas) than the original transactions. So zk-rollups are the ideal scaling solutions for the blockchain.

I have a previous article where I show how zero-knowledge proofs work through the source code of the Tornado Cash coin mixer. If you are not familiar with the technology, it is strongly recommended to read that article before this one.

In this article, I will show you how you can use zk-SNARK in your JavaScript project.

If you have read my previous article, you know that you need a circuit to generate a zero-knowledge proof. A circuit is a huge mathematical expression used by the system to calculate the outputs and the proof. The zero-knowledge proof itself is proof that you have successfully done the calculation.

A circuit can be really complex, but fortunately, there are circuit programming languages and libraries that make it easy to write your own circuits. We will use Circom. Circom is written in Rust. To install it, you have to install the Rust environment with the following command:

curl --proto '=https' --tlsv1.2 https://sh.rustup.rs -sSf | sh

After the Rust installation, clone the Circom repo and build the compiler:

git clone https://github.com/iden3/circom.git
cd circom
cargo build --release
cargo install --path circom

If everything went well, now you have the Circom compiler installed.

The other thing we need is the circomlib. Circomlib is a programming library with many useful predefined circuits. So, create an empty project, and install circomlib using this code:

npm init
npm i circomlib

Now, everything is ready to create our circuit. Here’s what that looks like:

pragma circom 2.0.0;

include "node_modules/circomlib/circuits/poseidon.circom";

template PoseidonHasher() {
    signal input in;
    signal output out;

    component poseidon = Poseidon(1);
    poseidon.inputs[0] <== in;
    out <== poseidon.out;
}

component main = PoseidonHasher();

This simple circuit has a private input and an output signal. We are using the poseidon hasher from circomlib to generate the input hash. Using this circuit, we can prove that we know the original data for the given hash without revealing it.

In the first step, we compile the circuit by the circom compiler that will generate a wasm and an r1cs file.

circom poseidon_hasher.circom --wasm --r1cs -o ./build

The generated wasm and r1cs files are available in the build folder. To generate the proof, we need a proving key file, and to generate this file, we need a ptau file. This ptau file can be generated by snarkjs, or you can download a pregenerated one (you can find the links in the snarkjs repo). For testing, the generated one is good for us, but in your production app, it’s recommended to do the ceremony and generate your own ptau file. (You can read about it in my previous article.)

wget https://hermez.s3-eu-west-1.amazonaws.com/powersOfTau28_hez_final_12.ptau

Now we can generate the proving key (zkey file) by using the circuit and the ptau file:

npx snarkjs groth16 setup build/poseidon_hasher.r1cs powersOfTau28_hez_final_12.ptau circuit_0000.zkey

It is not recommended to use this zkey file for production, but for testing, it will be good for us (for more info, please check the snarkjs documentation).

Now, everything is ready to generate the proof. We will use snarkjs, so install it with this command:

npm i snarkjs

The generation of proof looks like this:

const { proof, publicSignals } = await snarkjs.groth16.fullProve(
  { in: 10 }, 
  "build/poseidon_hasher_js/poseidon_hasher.wasm", 
  "circuit_0000.zkey");
console.log(publicSignals);
console.log(proof);

The input signals are passed in the first parameter of the fullProve function. The second parameter is the compiled circuit, and the last parameter is the generated proving key. The function returns the outputs of the circuit and the proof.

We need a verification key that can be generated from the proving key to verify the proof. Here’s how to get that:

npx snarkjs zkey export verificationkey circuit_0000.zkey verification_key.json

The verification code looks like this:

const vKey = JSON.parse(fs.readFileSync("verification_key.json"));
const res = await snarkjs.groth16.verify(vKey, publicSignals, proof);

if (res === true) {
  console.log("Verification OK");
} else {
  console.log("Invalid proof");
}

The verification key is the first parameter of the verify function, and the outputs and proof are the second and third parameters. The result of the function is a simple boolean.

In this example, we used the circuit to calculate the hash, but it is not always possible because the hash can be a partial result, or our circuit would look like this:

pragma circom 2.0.0;

include "node_modules/circomlib/circuits/poseidon.circom";

template PoseidonHasher() {
    signal input in;
    signal input hash;

    component poseidon = Poseidon(1);
    poseidon.inputs[0] <== in;
    hash === poseidon.out;
}

component main {public [hash]} = PoseidonHasher();

This circuit has no outputs, only two inputs. The first input is the data, and the second is the hash of it. In the last line of the template, we check the hash. The circuit will run successfully only if the given hash is the poseidon hash of the given data. But how can we calculate the poseidon hash in JS?

Circomlib has a JS implementation that can be used for this. Let’s install it:

npm i circomlibjs

Now we can calculate the hash by using the following code:

 const poseidon = await circomlibjs.buildPoseidon();
 const hash = poseidon.F.toString(poseidon([10]));
 console.log(hash);

The result of the poseidon function is a Buffer, which we have to convert to a number. In zk-SNARK, every calculation is done in a finite field, so we have to use poseidon.F.toString for the conversion.

Circomlibjs and snarkjs work well in Node.js and the browser, so you can generate or verify proofs on the client side. It is also possible to generate a smart contract for verification that you can use in your Solidity code to verify the proof. (For more info, please check the snarkjs documentation.)

Circomlibjs also has smart contract generators. For example, if you want to generate a poseidon hash on-chain, you can do it by the generated code.

This was my very short tutorial on using zk-SNARK in JavaScript. It’s not a full course, and you probably have many questions, but I hope I helped you to start your journey. Circom and snarkjs are well documented, and you can also learn a lot from existing projects like Tornado Cash.

The source codes for this tutorial are available in this GitHub repo.