In this article, I will explain how to implement symmetric encryption in Circom using simple to understand algorithms that are zkSNARK friendly. In particular, we’ll use the Poseidon hash function to implement encryption and decryption.

Many traditional symmetric encryption schemes aren’t suited for prime field arithmetic because they rely on heavy bit manipulation, which is considerably more expensive and complicated to perform within Circom.

I will not cover the basics of Circom in this article, it’s expected the reader has a basic understanding of how Circom works.

This article DOES NOT cover on how to ensure authenticity and non-malleability of messages.

Code snippets used in this article ARE NOT secure and should not be used in production.

The General Idea

Let’s assume the message we want to encrypt is contained within a single signal. Each party has access to the same key (thus — symmetric key) and uses it to perform encryption and decryption on transmitted messages.

The main idea behind this encryption algorithm is masking the message with a secret number that is derived from the key.

Aside from a key to encrypt with, every new encryption would need to use a one-time random value (an ephemeral key) which is referred to by the name of nonce in all following code sections. The nonce is always public information.

To encrypt, you sum the hash of the key and the nonce with the message. When decrypting, you reverse the process by subtracting the hash from the encrypted message.

The following code illustrates the main idea clearly, but it should be noted it’s not secure and lacks protection against various types of attacks.

Encrypting A Single Signal

include "circomlib/circuits/poseidon.circom";

template SymmetricEncrypt() {
    signal input message;  // private
    signal input key;  // private
    signal input nonce;  // public

    signal output encrypteMessage;

    component hasher = Poseidon(2);

    hasher.inputs[0] <== key;
    hasher.inputs[1] <== nonce;

    encrypteMessage <== hasher.out + message;
}

Decrypting A Single Signal

include "circomlib/circuits/poseidon.circom";

template SymmetricDecrypt() {
    signal input encryptedMessage; // public
    signal input key;  // private
    signal input nonce; // public 

    signal output message;

    component hasher = Poseidon(2);

    hasher.inputs[0] <== key;
    hasher.inputs[1] <== nonce;

    message <== encryptedMessage - hasher.out;
}

How Does It Work?

It may sound too simple to work, but if you think about it, the sum of two numbers in a prime field bears no information on the two individual numbers that were summed. The hash is uniformly random and there is no practical way to guess it.

However, messages aren’t uniformly random. The contents of a message rely heavily on the context in which they are sent. For example, if an encrypted message represents a vote for 1 of 8 candidates, there are only 8 possible values the message can be.

If an attacker were to guess correctly the contents of an encrypted message, it would enable them to retrieve the underlying hash and as a result to decrypt every other encrypted message that shared the same hash.

That’s why it’s crucial each encryption that is done with the same key, uses a unique nonce. A unique nonce ensures that no duplicate hashes are derived from a single key.

Encrypting And Decrypting Longer Messages

By default, Circom uses the BN254 curve. Under this curve, a single signal can consistently carry up to 253-bits of information. But what if we want to send messages that have more than 253-bits of information?

Representing longer messages requires using a combination of multiple signals, and encrypting each signal independently with the method above is not ideal. That would require generating a unique nonce for each signal and because nonces are public it adds overhead to the verification process.

Instead, we’ll use Poseidon in sponge mode. We begin by setting the initial input of the Poseidon function. Then, the Poseidon function is applied numerous times, each iteration using the last’s iteration output as its input. In a process known as “absorption”, we also integrate parts of the message into the input of each iteration. Iterations are performed until no parts of the message are left to be absorbed.

Absorption is done for security reasons, which are out of scope for this article.

Using Poseidon in sponge mode, we are able to generate hashes for each signal that comprises our message and by that solve the need for multiple nonces.

Additionally, you’ll notice that the encrypted message is one signal longer than the original one. This is because the last signal serves as validation that the message wasn’t altered.

Another change you’ll notice is that each Poseidon iteration produces a hash 2 signals in length ( out[0] and out[1]). This is because it’s important that some parts of the hash aren’t used for masking in the encrypted message but do affect the hashes of subsequent iterations.

include "circomlib/circuits/poseidon.circom";

template SymmetricEncrypt(length) {
    signal input message[length];  // private
    signal input key;  // private
    signal input nonce;  // public

    signal output encrypteMessage[length + 1];

    component hashers[length + 1];
    hashers[0] = PoseidonEx(2, 2);
    hashers[0].initialState <== 0;
    hashers[0].inputs[0] <== key;
    hashers[0].inputs[1] <== nonce;

    for (var i = 0; i < length; i++) {
        encryptedMessage[i] <== hashers[i].out[1] + message[i];
        hashers[i + 1] = PoseidonEx(1, 2);
        hashers[i + 1].initialState <== hashers[i].out[0];
        hashers[i + 1].inputs[0] <== encryptedMessage[i];
    }

    encryptedMessage[length] <== hashers[length].out[1];
}

The decryption process is very similar — using the key and the nonce, the receiver starts by generating the same initial hash, and as they unmask the contents of the message they feed it into the sponge and generate the rest of the appropriate hashes needed to unmask the contents of the message:

include "circomlib/circuits/poseidon.circom";

template SymmetricEncrypt(length) {
    signal input encryptedMessage[length + 1];  // public
    signal input key;  // private
    signal input nonce;  // public

    signal output message[length];

    component hashers[length + 1];
    hashers[0] = PoseidonEx(2, 2);
    hashers[0].initialState <== 0;
    hashers[0].inputs[0] <== key;
    hashers[0].inputs[1] <== nonce;

    for (var i = 0; i < length; i++) {
        message[i] <== encryptedMessage[i] - hashers[i].out[1];
        hashers[i + 1] = PoseidonEx(1, 2);
        hashers[i + 1].initialState <== hashers[i].out[0];
        hashers[i + 1].inputs[0] <== encryptedMessage[i];
    }

    encryptedMessage[length] === hashers[length].out[1];
}

How Can Two Parties Generate A Shared Key?

I won’t go over this myself because there are many good resources already online, but one way to achieve a shared key between two parties is using an Elliptic Curve Diffie-Hellman (ECDH) key exchange. Here is a page explaining how it works:

https://cryptobook.nakov.com/asymmetric-key-ciphers/ecdh-key-exchange

Implementations

Sadly, I found only one Circom implementation of this scheme:

GitHub - Shigoto-dev19/poseidon-encryption-circom2: Poseidon encryption in Typescript and circom2 (decryption only) on the BN254 elliptic curve

This is a fork of a different implementation that was made for Circom 1.0, re-modified to work in Circom 2.0.

The paper the implementation is based upon:

https://web.archive.org/web/20221114185153/https://dusk.network/uploads/Encryption-with-Poseidon.pdf

It should be noted that there are a couple of differences between my example implementation and this implementation:

• Keys are 2 signals long, not 1 (They are used to represent a point on an elliptic curve)
• The length of the message is incorporated into the initial hash
• A single Poseidon iteration generates a hash 4 signals long, not 2 — which allows to mask 3 signals of information in a single iteration

Github: https://github.com/rubydusa/circom-graceful-labeling

When I first heard about zkSNARKs I was fascinated. I couldn’t stop reading about them and trying to understand how they work. There is something so poetic about the idea of proving a statement while withholding evidence.

A lot of projects written in Circom are hard to understand for beginners, especially for people with no academic background in cryptography. As a part of a bigger project I’m working on, I wrote a circuit to create proofs of solutions to the Graceful Tree Labeling problem — and I believe I can share a couple of interesting techniques and insights from it.

Even though the name of the Graceful Tree Labeling problem sounds intimidating, I promise it’s really easy to understand. Contrary to many other Circom projects, this problem has nothing to do with cryptography.

I will not cover the basics of Circom in this article, it’s expected the reader has a basic understanding of how Circom works.

What Is The Graceful Tree Labeling Problem?

A quick overview of graph theory terminology:

The Graceful Labeling Problem is a math problem in graph theory, where each node is labeled with a unique number such that the difference between every two nodes is unique. The labels of the nodes range between 0 and the number of edges.

As you can see above, the range of the nodes’ labels is from 0 to 5 (the number of edges), each node is unique and so is each edge.

Not every graph can be labeled gracefully. A graph that can, is said to be graceful.

There exists a conjecture in graph theory that states that every tree graph is graceful. A ‘tree’ just means a graph that has no cycles. You can visualize any such graph as a ‘tree’ by choosing an arbitrary node to be the ‘root’, and display its connections below it in a recursive manner.

At last, here is an example of a graceful labeling for a tree:

In short, the Graceful Tree Labeling problem is solving the Graceful Labeling problem for tree graphs.

Approaching The Problem In Circom

We will not write a Circom circuit to solve the problem for a given graph, but rather we will write a circuit to verify that a given solution is correct. Then, we will be able to create Zero-Knowledge-Proofs that we know a labeling solution to a certain tree.

In general, it’s a good rule of thumb that Circom code should verify, not compute.

To verify a given solution we need to check in an input tree that:

1. Each label is unique
2. Each label is between 0 and the number of edges
3. Each edge is unique

If we can show that all these requirements are met, we have proved a tree to be graceful.

There remains one obvious problem: How do we represent trees in Circom?

Circom is very primitive and low-level. There are no data types, only numbers (field elements). Because of this, we need to get creative when representing more complex data types.

How To Represent A Tree

This was a really fun exercise for me personally. I’d recommend you give it a try to come up yourself with a way to represent trees.

If you didn’t succeed / can’t bother, I present you with my solution:

We imagine the tree (with N nodes) consists of indexed nodes from 0 to N — 1. We represent the tree using an array of length N — 1, where the array describes the structure of the tree by describing for each node who’s their parent.

The node indexed 0 is always the root node, which means it has no parents. The value at index 0 of the array is the parent of the node indexed 1, the value at index 1 of the array is the parent of the node indexed 2, and so on.

Example: If at index 5 is the number 4, it means the parent of the node indexed with the number 6 (5 + 1) is the node indexed 4.

In order to avoid cycles (two nodes or more having each other as their parents) the index of a parent node must be lower than the index of the child node.

That way, no two nodes can point at each other because at least one of them has a smaller index and can’t point to a parent with a higher index than theirs.

Finally, in order to label the nodes we simply have an additional array of length N such that the i’th value is the labeling of the i’th node.

Note: This way of representing trees is not one-to-one — there are multiple ways to represent the same tree with different arrays.

How To Index An Array Using A Signal

In order to compute the value of an edge, you need to access the labels of the two nodes at the ends of the edge.

The indices of the nodes depend on the structure of the tree, and this raises a problem: You can’t index an array with dynamic input. Well, at least not directly.

This is a really common problem and it has a really simple solution: in order to index using a signal you sum up the elements of the array, but before adding them together you multiply each of them by whether their index is equal to the index signal.

// sum in[N]
template CalculateTotal(N) {
    signal input in[N];
    signal output out;

    signal outs[N];
    outs[0] <== in[0];

    for (var i=1; i < N; i++) {
        outs[i] <== outs[i - 1] + in[i];
    }

    out <== outs[N - 1];
}

// array[index] when index is a signal
// O(n) because of how circuits work
template AtIndex(N) {
    signal input array[N];
    signal input index;

    signal output out;

    component result = CalculateTotal(N);
    for (var i = 0; i < N; i++) {
        var isEqual = IsEqual()([i, index]);  // IsEqual() taken from circomlib
        result.in[i] <== isEqual * array[i];
    }

    out <== result.out;
}

We’re (Almost) Done!

Once we know how to represent our data and access it, all that’s left to do is putting it all together.

I won’t go over all of the code because that would be boring, but if you’re curious you may head over to the Github repository and take a look for yourself: https://github.com/rubydusa/circom-graceful-labeling

Optimizing Using Bit Manipulation

One of the benefits of zkSNARKs is that their verification is constant-time*.

Well, not exactly.

There is overhead (especially with on-chain verification) caused by the amount of public inputs a circuit has. The more public inputs it has, the more gas will be needed to verify it on-chain.

In my use-case, the public input of the circuit is the parents array, so for a tree of size N there will be N — 1 public inputs. This gets quite expensive to verify on-chain even for moderately sized trees.

One solution would be to make the parents array private, and instead create a new public signal which will be the hash of the array. This way, the verification of the structure of the tree is done elsewhere.

The above solution works depends on how you intend to use on-chain verifications and what for, and in my case it’s not really relevant.

A different way to optimize would be to use bit manipulation, and store multiple numbers within a single number. In our code, we’ll unpack the packed input into an array that consists of the numbers we actually care about:

// amount of bits needed to represent n
function bits(n) {
    var result = 1;
    while (n > 1) {
        n \= 2;
        result++;
    }
    return result;
}

// amount of bits needed to represent N numbers with max value of MAX_VALUE
function bit_usage(MAX_VALUE, AMOUNT) {
    var b = bits(MAX_VALUE);

    return b * AMOUNT;
}

// amount of signals needed to represent N numbers with max value of MAX_VALUE
function bit_usage_signals(MAX_VALUE, AMOUNT) {
    var b = bits(MAX_VALUE);

    return ((b * AMOUNT) \ 254) + 1;
}

// take in the minimal amount 
template FromCompressed(MAX_VALUE, AMOUNT) {
    var bitsOfV = bits(MAX_VALUE);
    var bitsNeeded = bit_usage(MAX_VALUE, AMOUNT);
    var signalsNeeded = bit_usage_signals(MAX_VALUE, AMOUNT);

    signal input in[signalsNeeded];
    signal output out[AMOUNT];

    component asBits[signalsNeeded];

    for (var i = 0; i < signalsNeeded; i++) {
        var curBits = i == signalsNeeded - 1 ? bitsNeeded % 254 : 254;

        asBits[i] = Num2Bits(curBits);  // Num2Bits() taken from circomlib
        asBits[i].in <== in[i];
    }

    var values[AMOUNT];
    for (var i = 0; i < AMOUNT; i++) {
        values[i] = 0;
    }

    for (var i = 0; i < bitsNeeded; i++) {
        var valuesIndex = i \ bitsOfV;
        var asBitsIndex = i \ 254;

        var currentPower = 2 ** (i % bitsOfV);

        values[valuesIndex] += currentPower * asBits[asBitsIndex].out[i % 254];
    }

    for (var i = 0; i < AMOUNT; i++) {
        out[i] <== values[i];
    }
}

This adds additional constraints to our circuit, but it decreases significantly the amount of public inputs.

Conclusions

This was a fun project for me, and I hope you learned something and/or get inspired.

The source code is available at the top of the article.

Depending on how you install paper.js locally, ES6 syntax and features may not work properly. You may experience Uncaught SyntaxError: Unexpected token if you use the keywords const and let, or use arrow functions and so on.

How To Fix This

Assuming you already have an HTML file, add this script tag:

<script src='https://cdnjs.cloudflare.com/ajax/libs/acorn/8.8.2/acorn.js'></script>

Full example of usage:

<!DOCTYPE html>
<html>
    <head>
        <<script type="text/javascript" src="js/paper.js"></script>
        <script src='https://cdnjs.cloudflare.com/ajax/libs/acorn/8.8.2/acorn.js'></script>
        <script type="text/paperscript" canvas="canvas">
            const path = new Path.Circle({
                center: new Point(0, 0),
                radius: 100,
                fillColor: 'black'
            });
        </script>
    </head>
    <body>
        <canvas id="canvas" resize></canvas>
    </body>
</html>

Also, if you don’t want to depend on cloudflare you can also install acorn locally and import it that way. At the time of writing the latest version is 8.8.2 but that might change by the time you read this.

Why Does This Happen

paper.js is quite an old library, and it was created before ES6 existed. It depends on a library called acron to parse JavaScript within JavaScript, and the version of acorn used in paper.js releases does not support ES6.

If paper.js detects there is a different version of acorn loaded, it will use it instead.

Related Issues On Github

• Support ES 2015 in Paperscript · Issue #1183 · paperjs/paper.js
• Seems like generator functions are not supported in paperscript · Issue #1357 · paperjs/paper.js

When I tried to dive in On-Chain Generated Art with no prior experience I made plentiful crucial mistakes, and as a result I’ve wasted precious time I could have saved if only I’ve known better from the start

Hopefully this will serve as a helpful guide for anyone wanting to experiment with on-chain generated art. This article focuses specifically on EVM-based chains, however, some ideas are more general and may apply to other blockchains as well

Introduction

Why generate the art on-chain at all? There are three main reasons:

1. Dynamic Content — Unlike static images and videos, generated art can read data from the blockchain and shape itself accordingly
2. Censorship Resilience — Centralized hosting of media is unreliable in the light of censorship and goes against the spirit of decentralization. IPFS hosting and other decentralized hosting methods are also partially prone to censorship, and also are unreliable if there are only a few nodes storing the media
3. Composability — If done correctly, on-chain generated art can be composed with one another

However, blockchains are usually not designed in mind to handle generative art. One of the biggest factors is the gas cost of deploying on-chain art, so if you are planning on deploying on a chain like Ethereum, expect to pay hundreds of dollars in gas costs.

The main concept of how to do generative NFT art lies in Data URLs — Data URLs allow you to pass images and other forms of media in the URL itself. NFT Metadata Standards support the usage of data URLs in token metadata so your NFT tokens will render on OpenSea and other major NFT marketplaces.

Helpful Sources

Opensea Metadata Standards — Opensea’s Metadata Standard. You should also refer to the official EIP-721 metadata specification

Data URLs — The official Mozilla docs on data URLs and how they work

Relic Protocol — Fully On-Chain NFTs (Relic Protocol)— This is a great article by Relic Protocol that includes optimization tips for storing images on-chain and insight to the benefits of on-chain art

On-Chain generative 3D roller coaster (xtremetom) — Cool twitter thread with great tips and tools for on-chain generative art

Scripty.sol (@0xthedude and xtremetom) — Gas-efficient HTML builder that can combine multiple JS and a data storage solution that allows on-chain composable generative art (description copied from repo)

fully-on-chain.sol (@nounsfes) — A collection of solidity libraries to generate SVGs on-chain

The Formats You Can Use

The two main formats of media you can use are HTML and SVG. Both are tag languages which makes it easy to create HTML and SVG files programatically.

These two formats are not exclusive — you can embed HTML into SVG files using foreignObject (always make sure to check support for intended platforms) and SVG elements work directly inside an HTML file.

SVGs are slightly easier to compose with themselves than HTMLs since laying out elements is more straightforward and HTML based art may not rely on elements at all and use exclusively the canvas element.

HTML is by far more expressive and gives you far greater artistic freedom:

• Interactivity is easy to achieve with Javascript compared to CSS
• You can use existing Javascript graphics libraries
• Custom art generation logic by utilizing the Canvas API

However, if your content is generative but not animated or interactive it may be preferable to use SVGs for the sake of simplicity, and also because rendering batches of SVGs is more efficient than of HTMLs

Gas Usage In View Functions Still Matters!

You may think that because on-chain art relies on view functions it doesn’t matter how much gas do you use to generate your art. Well, it does.

Many RPC providers will block view calls that exceed the gas limit and for a good reason: High gas usage in a view call may indicate a high amount of reads to the state of blockchain — which is expensive. Even if the executed bytecode is mostly arithmetic, an RPC server has no way to know.

With that said, don’t optimize prematurely. Start by writing your code as you normally would, but beware the possibility of getting blocked.

The main gas pitfalls in on-chain generative art have to do with string manipulation, and it’s really easy to accidentally write inefficient code because Solidity was not designed in mind for cheap string manipulation.

Here is a comparison between three functions whose purpose is to produce a string that represents a rectangle element with data inside of it:

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

import "@openzeppelin/contracts/utils/Strings.sol";

contract Test {
  using Strings for uint256;

  bytes constant START_STRING = "<rect>";
  bytes constant END_STRING = "</rect>";

  // 3744 gas
  function svg0(uint256 data) external pure returns (bytes memory) {
    return bytes.concat(
      START_STRING,
      bytes(data.toString()),
      END_STRING
    );
  }

  // 3748 gas
  function svg1(uint256 data) external pure returns (bytes memory) {
    bytes memory start = "<rect>";
    bytes memory end = "</rect>";

    return bytes.concat(
      start,
      bytes(data.toString()),
      end
    );
  }

  bytes6 constant START = "<rect>";
  bytes7 constant END = "</rect>";

  // 3220 gas
  function svg2(uint256 data) external pure returns (bytes memory) {
    return bytes.concat(
      START,
      bytes(data.toString()),
      END
    );
  }
}

Slightly more than 500 gas units saved and all these functions do is wrap a number around a rect tag.

The difference is that the first two functions load the strings into memory and then create a copy of each. Because in the last function a string variable is never declared, the string data is put in its destination directly, without making a copy.

Another tip is that for large constant strings, you should look into saving the string on-chain as the bytecode of a contract and use EXTCODECOPY to retrieve it (Make sure the first byte in your contract’s source code is 0 to ensure it cannot be ran and accidentally be self-destructed)

In general, if you end up having issues with gas you should research more in depth how to optimize around string manipulation. There’s also a chance you’ll never have to deal with optimization.

Use URL character encoding!

Some characters that are often used in HTML and SVG files (such as <, >, “) are invalid URL characters.

A way to deal with this is to encode the files in base64, but the problem is that for large files they significantly bring up the gas cost.

More so, in certain cases you might need to do base64 conversion multiple times (e.g. if you want the function to return JSON metadata, you’ll need the convert once the SVG/HTML itself to base64 encoding, and then the whole JSON to base64 encoding)

The solution is to use URL encoding, which is a way to encode special characters inside a URL. That way, all strings are valid and composable with each other easily.

Rendering The Art In A Website

This is probably obvious to people familiar with front-end development, but the ideal way to render the art in a website is to use an iframe tag.

The reason I’m mentioning this at all is because in my personal project I used plain SVG generation, and I tried various ways to render the art on the front-end and all of them caused issues.

In this short tutorial I will demonstrate how to import and use SnarkJS in a react project, prior knowledge of circom and react are expected.

Make sure to check the official docs on the matter first: https://github.com/iden3/snarkjs#in-the-browser

Developers with experience with react could probably put the pieces together from the docs, but personally it took me quite a while to figure it out so I hope this tutorial reaches other newbies like me.

Importing SnarkJS

1. Install SnarkJS through npm:

npm i snarkjs

2. Copy snarkjs.min.js to the public folder

// in the root directory

cp node_modules/snarkjs/build/snarkjs.min.js public/

3. Add this script tag to public/index.html

<head>
  ...
  <script src="/snarkjs.min.js"></script>
  ...
</head>

Using SnarkJS

1. Load SnarkJS in App.js (or any other react component)

const snarkjs = window.snarkjs;

2. You’re done! You may now use SnarkJS as you would in node.

function App() {
  return (
    <div>
      <button onClick={async () => 
        const {proof, publicSignals} = await snarkjs.groth16.fullProve({ a: 11, b: 3 }, "circuit.wasm", "circuit.zkey")
        console.log({ proof, publicSignals });}>
      </button>
    </div>
  )
}

Notice that wasm and zkey files should be placed under the public directory (e.g. public/circuit.wasmand public/circuit.zkey)

Recently there is a rise in discussion about the potentials of ZKP — Zero Knowledge Proofs in crypto. Jumping on the bandwagon, I decided to learn circom and try to implement Conway’s Game of Life as a zkSNARK circuit, as well as use the circuit in an NFT smart contract.

In this post I will write briefly about the technologies in use, present my circuit, and explain how it works.

You can view the code here: https://github.com/rubydusa/proof-of-life

Brief Overview of ZKP, zkSNARK and Circom

For the purposes of this post, a Zero-Knowledge-Proof means a mathematical proof that a piece of data upholds a set of constraints, without revealing what that piece of data is, and without revealing anything else about it.

a zkSNARK — Zero Knowledge Succinct Non-Interactive Argument of Knowledge is a type of a Zero Knowledge Proof that requires a single interaction between the prover and verifier, and is short.

Circom is a programming language to write programs (called circuits) that take a set of inputs, and describe constraints about them, as well as having one, many or no outputs.

Using these constraints, you can generate proofs that you know a set of inputs that uphold the constraints as well as verify proofs.

What is Being Built?

In this post I will show an NFT contract that mints a token anytime someone provides a proof that they have a solution to the following problem:

Find a Game of Life grid state such that after N iterations, the grid state matches some predefined state:

For a finite grid state of life, I’ll be using the wrapped variant:

To clarify, whenever I say “solution” I refer to grid states that apply to the problem aforementioned .

Duplicate Solutions are not allowed.

ZKPs allow us to keep the solutions private after submission, prevent frontrunning, and create large puzzles of this sort.

The Details

This section will cover implementation details and explain the architecture of the project:

The Circuit

The circuit is parameterized over N — number of iterations, W — grid width, H — grid height.

It has three outputs:

• out — the state of the grid after N iterations
• solutionHash — the hash of “out”, required so the contract can verify it is not a duplicate solution
• hash — the hash of “address” combined with “solutionHash”, required in order to prevent frontrunning (more on that later)

And two inputs:

• address (public) — the address of the prover
• data (private) — the solution to “out”

The grid state is represented as a single* 254 bit-number, and broken down to a W×H bit matrix. Then, the life algorithm is applied N times and the output is constrained to be whatever happens to be the result.

*In the actual circuit it is extended to support grids that have more than 254 cells by patching together the bits of a sequence of 254 bit-numbers

The Verifier Contract

In order to verify proofs on-chain, we need to compile our circuits into solidity contract templates. These contracts have a single public function that take proof data as an input, and return a boolean value indicating whether the proof is valid or not.

In the case of the groth16 protocol, the function signature looks like this:

function verifyProof( 
    uint[2] memory a,

    uint[2][2] memory b,

    uint[2] memory c,

    uint[4] memory input

) public view returns (bool r)

Since I’m not a cryptographer I’m not able to explain the details of a, b, and c — think of them as “the private part” of the proof, and the input parameter consists of the public inputs and outputs of the circuit.

Note that outputs are also part of the verification input, as the contract is only responsible for validating a proof, not computing it.

The NFT Contract

The NFT contract inherits from ERC721Enumerable, and has these additional storage variables:

uint256 public prizenum;

mapping(uint256 => bool) public proofs;

IGroth16Verifier public verifier;

• prizenum — The sought-after grid state
• proofs — A mapping to keep track of already submitted solutions
• verifier — The address of the verifier contract

And it adds an external function “mint” that mints a token when provided with a unique proof:

function mint(

uint256 solutionHash,

uint256 hash,

uint256[2] memory a,

uint256[2][2] memory b,

uint256[2] memory c

) external {

require(!proofs[solutionHash], "GOLNFT: Solution already exists!");

require(verifier.verifyProof(a, b, c, [

solutionHash,

hash,

prizenum,

uint256(uint160(msg.sender))

]), "GOLNFT: Invalid proof");

_safeMint(msg.sender, totalSupply());

proofs[solutionHash] = true;

}

How do Zero-Knowledge-Proofs Prevent Frontrunning?

If we were to not care about keeping the solutions private, we could have simply simulated the execution of life inside a solidity smart contract and it’d be much less burden.

So why use ZKPs in the first place?

The problem with the aforementioned approach is that malicious actors could steal solutions to the puzzle by listening to broadcast transactions. A malicious actor would simply copy the calldata, submit a transaction with a higher gas fee and reap the rewards:

A hash commitment scheme where a user commits to a hash of a solution before submitting it, and gets punished if he fails to submit the solution within some time-frame would be better, but has major flaws:

1. If the cost of commitment is too high it would prevent users with insufficient capital from participating
2. If the cost of commitment is too low, malicious actors can front-run commitments and intentionally lose money if it’s beneficial for them to gatekeep tokens

We are able to prevent this by requiring the transaction caller to provide the hash of his address combined with his solution. The verfier contract is able to verify that the public address and the private solution match the provided hash.

Now, if a frontrunner tries to steal a solution, him calling the mint function with the same inputs would fail since his address won’t match the hash.

How do Zero-Knowledge-Proofs Achieve Scalability?

If we even disregard frontrunning, there is another major benefit of using ZKPs: scalability. Verification is constant time and as a result the gas used in the verifier contract is bounded. Alternatively, implementing life in solidity for large grids with a large number of iterations would probably consume the gas limit many times over.

The downside is that groth16, the zkSNARK protocol in use requires a circuit-specific trusted setup — which means that in order to deploy the application into some chain you’ll need to conduct a trusted setup ceremony beforehand.

A trusted setup is an essential source of randomness used in the proof generation and verification processes and if it’s created by a single party, that party is able to forge false proofs, unless they discard the “secret key” that enables them to do so (hence trusted).

A trusted setup ceremony is a method for multiple parties to create a trusted setup such that as long as a single party is honest (discards their part of the “secret key”) the trusted setup is secure.

Stay Tuned!

I’m planning on creating a react site for demonstration purposes. If you have any questions about the project feel free to ask and contact me at https://twitter.com/rubydusav

New to trading? Try crypto trading bots or copy trading

Proof of Life: Zero-Knowledge-Proof Implementation of Conway’s Game of Life with Circom and… was originally published in Coinmonks on Medium, where people are continuing the conversation by highlighting and responding to this story.

By default, The flatten feature in hardhat doesn’t solve SPDX license identifiers conflicts. In this article I’ll provide two solutions:

• Modifying hardhat.config.js
• Script that fixes broken flattened contracts

These solutions are simplified and cleaner versions of BoringCrypto’s solution to this problem, found on #1050 at the hardhat github

These also deal with multiple experimental ABI encoders deceleration in a file

Hardhat

For hardhat users, this can be fixed by adding the following task to your hardhat.config.js file:

This creates a task flat that has the exact same syntax and function as flatten, but changes the syntax of every SPDX-License-Identifier comment to match the MIXED SPDX-License-Identifier

How To Use

The newly created flat task operates identically to the flatten task. Example:

> npx hardhat flat contracts/ContractToFlatten.sol > path/to/Output.sol

Script

If you’re not using hardhat, the solution is the same but instead of the fix being a hardhat task, it is a script:

In this script the path to the flattened broken contract is set as a constant, but depending on your use case you may want to modify the script to accept input from the command line / return the fixed version as a value from a function

Incompatible Licenses

In the two solutions I provided, a program modifies a flattened contract with multiple SPDX license identifiers to a flattened contract with the SPDX License Identifier: MIXED and multiple license identifiers that define the mixed license.

Unfortunately, detecting incompatible SPDX licenses is not a trivial task, so solidity compilers won’t pick up on all incompatibility issues.

This shouldn’t be an issue most of the time since most of the popular smart contract libraries have very permissive licenses. For example, the Openzeppelin Contracts library is licensed under the MIT license

However, for a large serious project that uses code from a couple of different sources — extra caution may be needed