Why calculating your public key is hard in ZK-Snarks?
Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (ZK Snarks) is a technology that enables the verification of certain operations on-chain without revealing the underlying data. This makes it an incredibly powerful tool for maintaining privacy and confidentiality on the blockchain. ZK Snarks have several advantages, such as their ability to reduce computational and storage requirements, as well as their ability to ensure that information remains confidential. In this article, we will see how we can calculate public key inside ZK Snarks. It is not straight forward as elliptical curve numbers are 256 bits and inside circom we have baby jubjub curve which accepts number not greater than 254 bits
Why do we want to calculate public key inside ZK-Snarks?
This is useful in calculating the group signatures. In a group signature scheme, a group of users can generate signatures on behalf of the group without revealing their individual identities. Each user has a private key and a corresponding public key, but instead of signing a message with their individual private key, they generate a group signature using a common group public key and their individual private key. This way, the group can prove that the message was signed by a member of the group without revealing the identity of the specific member who signed it. The use of multiple public keys in this scheme helps ensure the security and privacy of the group members.
The scalar multiplication method discussed for calculating the public key inside ZK Snarks can be applied for other purposes as well, such as in elliptic curve cryptography (ECC) where scalar multiplication is a fundamental operation used for key generation and message encryption/decryption.
How is public key calculated?
Your public key is the multiplication of your private key and a Generator point in the field of an elliptical curve. The private keys in the ECC are integers (in the range of the curve’s field size, typically 256-bit integers). Example of 256-bit ECC private key (hex encoded, 32 bytes, 64 hex digits) is: 0x51897b64e85c3f714bba707e867914295a1377a7463a9dae8ea6a8b914246319
The key generation in the ECC cryptography is as simple as securely generating a random integer in certain range, so it is extremely fast. Any number within the range is valid ECC private key. The public keys in the ECC are EC points — pairs of integer coordinates {x, y}, laying on the curve.
In the ECC, when we multiply a fixed EC point G (the generator point) by certain integer k (k can be considered as private key), we obtain an EC point P (its corresponding public key).
How to do it inside a ZK-Snarks?
The proving systems currently in use for zk-SNARKs use specific elliptic curves that limit the maximum “register size” for numbers used in zk-SNARK proofs to 254 bits. Unfortunately, networks like Ethereum and Bitcoin use the Elliptic Curve Digital Signature Algorithm (ECDSA) and the secp256k1 curve, which require arithmetic on 256-bit numbers. This would overflow the 254-bit registers allowed in today’s SNARK systems. To implement ECDSA algorithms inside zkSNARKs, we must perform “non-native field arithmetic” and build ZK circuits for BigInt arithmetic and secp256k1 operations using 254-bit registers.
To achieve this in a non-native field of 254254 bits we need to store the pre-computed multiplications of generator value. The idea boils down to the basic of number theory, asking how a number is represented in its respective base.
So the idea is to present a number in following format:
Here we will change the representation of scalar(256 bits) value by breaking it into smaller chunks. We need to break the scalar value in kk registers of nn bits each. Because the base point G is known and fixed in our setting, we can reduce the number of point operations by precomputing and caching multiples of GG by powers of two.We need to store the pre computed values of
in a 2D array powers(i,j). ‘w’ is the window length, which represents how many bits are selected for iteration
This element will be containing 2k values(k values for x,y co-ordinate each).
Then we will use a window approach where we will first pick up ‘w’ bytes from first register and find its corresponding value in the first row of powers array.
After we have all (n/w)∗k values of broken scalar value. We will group binary digits of the private key into groups of size ‘w’, cache multiples of G corresponding to numbers with non-zero binary digits only in a single group, and represent G as a sum of the cached elliptic curve points. For every n bits of the scalar value at position [w∗i, w∗i+w] we will find the corresponding i th row in powers array and then the j th column where Bits2Number(bits ∈[w∗i,w∗i+w]) which is non-zero, and add it to the result.
We keep adding the terms until all the windows are finished. The cached windowed method reduces the number of point additions to ceil(256 / w), which decreases as w increases. However, as w increases, we must maintain a growing cache of size ceil(256 / w) * 2**w points and select the jth element from arr[i] using a multiplexer with 2 ** w possible selections. Surprisingly, this is an expensive operation in a zk- SNARK, requiring O(2 ** w) constraints per selection.
We can get public key at last with two coordinates (x,y) each co-ordinate with k registers.
Thank you for reading! Feel free to correct me if anything is wrong or missing.
Currently I am working on Banana SDK which is a smart contract wallet infrastructure. It provides applications with easy onboarding using users biometric.
