At Statebox we are exploring using boolean circuits to model computation. One thing we’d like to do is verify correct computation on a blockchain in a scalable way. A zero-knowledge proof system, like a zkSNARK, can do this. In my last post I explained how to create a zkSNARK that verifies a boolean circuit in Libsnark.
In this post, I’d like to take a closer look at the core bit of mathematics that makes a zkSNARK work: the elliptic curve pairing.
Usually in cryptography we want our encryption functions to destroy as much information as possible. The inputs to these…
At Statebox we use category theory to model computation, where the objects of a category represent the possible states of a system and morphisms between states represent a computation taking some state to another. One natural way to express these kinds of morphisms is to use boolean circuits.
A boolean circuit is a function that transforms a bitstring of
m bits into a bitstring of
n bits. It is called a circuit because it can be imagined as a diagram of wires and gates, where a 1 is a wire carrying a charge and a 0 is a wire with…
I’ve been diving deep into zk-SNARKs again. These objects are constructed out of many different parts with different functions, like an automobile. If you wanted a deeper understanding of how a car works, what would you study? The pedals? The steering wheel? Or the engine?
The engine of zk-SNARKs is, in my opinion, the bilinear pairing used to keep private information private. Pairings are special maps that obscure information but still allow you to do some limited arithmetic with it. They are pretty fascinating creatures. …
We’ve learned how to use matrices and matrix multiplication to represent recipes for coffee beverages in a tidy way. We can also use these techniques to solve mathematical problems.
A local business wants to reserve your coffee shop for a two-hour meeting. They prepay for 30 lattes and 18 cappuccinos for their guests. How much espresso and milk should you set aside for this meeting?
We can approach this problem using matrices. The business is ordering 30 lattes and 18 cappuccinos.
If you are seeing this for the first time, I highly encourage you to start with my previous article, Matrices for Coffee Lovers. (Part 1).
In part one we used matrices to represent the recipes of our coffee beverages. We used a key shortcut that allowed us to break our system of equations down as much as possible and write it entirely with matrices.
Here is the rule from Part 1:
Big deal. It’s a box with numbers in it. Who cares?
This is what I thought when I first saw a matrix in 8th grade algebra. We learned to add and subtract matrices. I was still unimpressed. You just add or subtract the corresponding entries! They were just making me do addition and subtraction again except this time the numbers were written in a rectangle with brackets on either side. Why don’t I just write numbers in a circle and call it a new thing, too?
No one told me what a matrix really was. I wish someone had. …
I am not interested in facts. I could never remember them very well for school. Many grade-school students must memorize their times tables, the Gettysburg Address, common English prepositions, the fifty states in alphabetical order, the U.S. presidents and their inaugural years. I could never do it. Only a few dry facts ever stuck in my mind. There are 5280 feet in a mile. Lincoln was the 16th president.
Numerical facts are especially difficult to memorize. Every number looks more-or-less the same to me. Not like words.
A few years ago I was surprised by a numerical fact that immediately…
While writing my last article This is Not a Circle: The Extraordinary Algorithm of Liu Hui I came across a reference to rod calculus, the method of computation available to the Liu Hui and the other Chinese mathematicians of his time. Computing anything with rod calculus looks quite complicated — like computing in Roman numerals if the numerals were made of matchsticks. One little puff of wind and your 53 might look like 71.
After developing the method mentioned in This is Not a Circle, Liu Hui reformulated his method to avoid having to compute square roots in rod calculus.
This is not a circle.
It is a polygon. Look closely. It has 192 sides and 192 corners. Can you tell?
Lacking overpriced calculators with plastic pi buttons to do the heavy lifting, ancient mathematicians relied on polygons like this one to compute accurate values for pi.
This is precisely what the ancient Chinese mathematicians Liu Hui, and later Zu Chongzhi, were able to do in the third and fifth centuries. They computed the perimeters of polygons with a huge number of sides, getting an excellent approximation for pi in the process.
They had no powerful computing tools. No calculators…
The post on the Zcash blog gives a little example of a use of a homomorphic hiding. I wanted to recreate this example with the Unpadded RSA homomorphism, but I found that it has a critical flaw. The second property of a homomorphic hiding given on the Zcash blog is not satisfied by Unpadded RSA. The second property states:
Without this property there are multiple inputs of the homomorphism that are sent to the same output. With this caveat in mind, let’s explore the rest of the example.
Suppose I have discovered how to factor a “large” number, say 899…
Joshua is a mathematician, educator, cryptographer, and developer. He is a developer at @statebox.