Google Drive
Gist
Clipboard
Webauthn enables secure passkey authentication via face ID, touch ID, and passwords, perfect for onboarding new crypto users.
However, the current signature scheme for webauthn(secp256R1 elliptical curve) in solidity is highly gas-intensive around 1.2million gas. On even L2s this amount of gas will turn into huge overhead charge.
Our off-chain approach using groth16 and PLONK in a ZK circuit for signature verification significantly reduces gas usage to around 300k, making it more efficient and cost-effective.
Overall, the objective is to make signature verification more efficient and cost-effective, promoting wider accessibility and adoption of crypto.
The benefits of this project for the Ethereum ecosystem are significant.
Benefits for Users:
Benefits for Developers and Researchers:
Hence, it offers significant benefits to both users and developers in the Ethereum ecosystem.
How many people are working on this project?
Please list their names and roles for the project as well as how many hours per month will each person work on this project?
The team will initally consist of two members:
Also
Our team presented Banana Wallet SDK at ETH India 2022. Banana Wallet received lots of love from developers at ETH India and has won
We have been working on this project from 3 months now and gained quite a lot of expierence and developed a deep understanding of EIP 4337 and account abstraction.
We both are ETH India Fellows and have been working from past 7 weeks to build Banana SDK with webauthn capability. We have developed an in-house SDK which Dapps can integrate for allowing users to create a wallet in less than 1 min using their face ID or touch ID. Our package is also live on npmjs. We have been working closely with Tom Teman who is our mentor from Ethereum Foundation at Ethereum India research fellowship 3.0 to refine our idea and build the product.
We will be happy to provide any additional proofs, documents or code needed for verification.
How do you plan to achieve your research objectives?
I have already started the backgroud work needed for building the circuits. We encountered a major hurdle in our preliminary investigation: current zkSNARK proving systems are limited to specific elliptic curves that only allow operations on numbers represented as residues modulo a specific prime. This restricts the maximum "register size" for numbers used in zkSNARK proofs to \(254\) bits, which is insufficient for handling operations on the secp256R1 elliptic curve. This curve is widely used standard in Hardware Security Modules like secure enclaves, but is not "SNARK-friendly," as it requires arithmetic on \(256\) bit numbers that overflow the \(254\) bit registers allowed in current SNARK systems.
To address this challenge, we plan to use non-native field arithmetic circuits for Big Int arithmetic and secp256R1 operations using \(254\) bit registers. This will enable us to implement ECDSA algorithm for signature verification and aggregation within the constraints of zkSNARK proving systems.
We will represent large numbers such as private keys, public key coordinates, and other \(256\) bit numbers in a little-endian form that is adapted to zkSNARKs. For instance, we use arrays of four signals constrained to \(64\) bits each to represent \(256\) bit numbers, with an array interpreted as the number.
\[arr[0]+ (2 ^{**} 64) * arr[1] + (2 ^{**} 64 * 2) * arr[2] + (2 ^{**} 64 * 3) * arr[3]\]
Scalar multiplication is an important operation in ECDSA, during verification we calculate
\[ Private Key: P_v \]
\[ q = u_1 . G + u_2 . (P_v .G) \]
where \[ u_1 = Hash(message). inv(s) \]
\[ u_2 = r . inv(s) \]
and
\[ signature = (r,s) \]
For the calculation of \(u_1.G\) we need scalar multiplication. As \(G\) is the generator point of secp256R1 curve.
\[ G_x=0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
\] \[ G_y=0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
\]
To achieve this in a non-native field of \(254\) 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.
\[ 356 = 3 * 10^2 + 5 * 10^1 + 6 * 10^0 \] where \[ base=10 \]
\[ 11 = 1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0 \] where \[ base=2 \]
So the idea is to present a number in following format:
\[ number = \sum_{l=0}^{ceil(log_{base}(number))} b_l * base^l \]
\[ b_i \in [0,base-1] \]
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 \(k\) registers of \(n\) 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 \(G\) by powers of two.We need to store the pre-computed values of \(b_l * base^l * G\) in a 2D array \(powers(i,j)\). \(w\) is the window length, which represents how many bits are selected for iteration.
Where
\[[0 \le i < \frac{n}{w}*k] \]
\[\&\]
\[ 0\le j<2^k \]
\[ arr[i,j] = j * (2^w)^i * G \]
This element will be containing \(2k\) values(\(k\) values for \(x,y\) co-ordinate each).
For BigInt number multiplications normally, with \(k\) registers, a naive multiplication implementation uses two for-loops to compute intermediate products, for \(O(k^2)\) constraints, followed by a bunch of carries that takes \(O(nk)\) constraints
When implementing big Int multiplication in zkSNARKs with \(k\) registers, a naive approach will involve using two for-loops to compute intermediate products, resulting in \(O(k^2)\) constraints. After this carry operations that take \(O(nk)\) constraints will be performed, where the primary cost is a set of range checks that ensure that each of the \(2k\) registers is no more than n bits in size. What we can do is represent each number in an a proper number format with base value equal to \(2^{**}64\). \[ a = a[0] * (2 ^{**} 64 * 0) + a[1] * (2 ^{**} 64 * 1) + ... + a[k-1] * (2 ^{**} 64 * k-1)\]
We will write this number such that each coffecient is following the m-overflow representation i.e each coeffient in above equation is less than \((m * x)\). In our case each coefficient should be less that \((2 ^{**} 64 )\).
If we take \(2\) such numbers, lets call them a and b in the above format and take a multiplication. The resulting number will be having \((2^{**} 64 -1)\) coefficients. We also need to take care of the carry term for each coefficient. As it may happen that each term might cross the \((2^{**} 64 - 1)\) mark and we need to make sure if that happens carries are handled properly. We can also convert this \(O(k ^{**} 2)\) multiplication process into \(O(k)\) steps by comparing the coefficients of same power terms in \(a * b = c\) equation.
In point addition, we will perform elliptic curve point addition with 2 distinct points P and Q giving R.
\[ P + Q = R \]
\[ (x_p,y_p) + (x_q,y_q) = (x_r,y_r) \]
So the result is
\[ x_r=\lambda ^2 - x_p-x_q \]
\[ y_r=\lambda . (x_p-x_r) - y_p \]
where,
\[ \lambda = \frac{y_q-y_p}{x_q-x_p} \]
Similar approach will be used for point doubling where
\[ \lambda = \frac{3x_p^2 + a}{2y_p} \]
We will not be converting it to Jacobian form for addition as it was mentioned in the 0xParcs blog that inside Zk circuits the difference in number of constraints of modulo inverse and module multiplications operation is almost same. So it does not improve the performance.
Finally all this will come together in a final circuit where we will calculate
\[ q = u_1 . G + u_2 . (Pub_k .G) \]
In the result we will output public key with \(k\) registers each for \((x,y)\) co-ordinates.
In conclusion, we will conduct an extensive literature review and investigate existing research in this area, in order to build upon previous work and identify the most effective approaches for our specific use case. This work is inspired from 0xParc's work on ZK ECDSA for secp256k1 curve. We will also collaborate with our mentor from the Ethereum Foundation to refine our methodology and ensure that our research is aligned with current industry standards and best practices.
Our Github project link.
Handwritten solved examples for reference here.
A rough timeline would look like:
We are requesting an amount 20,000$ from the grant committee. These funds will be used to support our reseach and developement for 4 months. Apart from supporting the team it will also be used for various tasks.
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe