Prerequisites: secp256k1, Finite Fields, and Elliptic Curve Point Operations#

Because this involves a lot of modular arithmetic and elliptic curve point operations, I prepared a bit of prerequisite knowledge (and put up what I learned myself as well www. Of course, if you already know this, you can skip it.

Alternatively, you can also look at my conversation with Gemini as a supplement (honestly, with AI, learning has sped up a lot

Gemini

‎Gemini - direct access to Google AI

Created with Gemini

gemini.google.com/share/f72d7ecbcf76

About an EOA Wallet Signature and Verification#

As described in the previous article, when an address ownership verification requiring an EOA wallet occurs, the following process takes place:

1. A message conforming to SIWE is sent by the frontend to the wallet to request a signature

2. For such a signature request, after the wallet receives it, it pops up a prompt asking for the user’s approval

3. After the user confirms, the wallet signing process begins

   • First, the SIWE message is computed with keccak-256 to obtain a 32-byte hash $e$ for the following calculations

   • Then, using the wallet private key $d$, the finite field $p$ of secp256k1, its standard selected base point $G$, and the order $n$ of $G$, the wallet generates a random number $k$ in the range [1,n-1] for the subsequent verification calculation (note here that because only [1,n-1] within n are usable non-repeating results, calculations such as point selection use mod n, while calculations over the whole secp256k1 range are performed within its own specified range p, i.e. mod p

   • The final generated signature is actually the concatenation of the three computed results $r/s/v$, which are 32-byte/32-byte/1-byte respectively. Their calculations are:

     • $R = kG = (R_{x}, R_{y})$

     • $r = R_{x} \bmod n$

     • $s = k^{-1} * (z + r * d) \bmod n$

     • $v$ exists because for a secp256k1 elliptic curve

       $$y^2 = x^3 + 7 \bmod p$$

       at $x=R_x$, besides the point at infinity $0$, there are two solutions symmetric about the x-axis. $v$ specifies which solution should be chosen by providing the yParity 0/1 here (of course, for secp256k1, there may also be a case where $r+n<p$, but because the probability is too small, the EVM does not consider this case during actual recovery

   • In this way, the final signature $r/s/v$ returned by the wallet to the server is generated

4. Next is the server’s verification of the obtained $r/s/v$. At this point, the server knows the secp256k1 base point $G$ / the SIWE message sent to the wallet and its keccak-256-computed hash $e$ / the signature $r/s/v$ returned from the wallet

5. Then the server begins verification:

   • For the server, it already has $G$ / $e$ / $r$ / $s$ / $v$. At this point, it needs to know whether the wallet address computed from this data is the same as the wallet address received at the beginning. According to

     $$address = keccak256(Q_x || Q_y)[12:32]$$

     (that is, the address is the last 20 bytes of the keccak-256 hash result of the public key $Q$), we can know that the current goal is to compute the public key $Q$ from the current conditions

   • Besides the above data, what we can also know is the transformation process of $s$ (an integer computation in the scalar field), namely

     $$s = k^{-1} * (z + r * d) \bmod n$$

     So we can likewise obtain a transformed form:

     $$d = r^{-1} * (s*k - z) \bmod n$$

     Then the calculation enters the realm of elliptic curve point operations. Multiply both sides of the above equation by the base point $G$

     $$\begin{align} dG &= \left(r^{-1}(sk - z) \bmod n\right)G \\ &= r^{-1}(skG - eG) \end{align}$$

     At the same time, we know that the public key $Q = dG$, $R=kG$, and we know $r=R_x$. Through $v$, we can recover $R$. Therefore, we can convert the above into a formula for solving the public key $Q$ composed of known quantities

     $$Q = r^{-1}(sR - eG)$$

     Thus, we obtain the public key $Q$ of the signing wallet through computation

   • Then compute keccak-256 on the solved public key $Q$ and take the last 20 bytes to obtain the wallet address used for verification. Then compare this address with the previously provided address. If the two are the same, the control over the current wallet can be verified using only the existing information, without knowing the private key $d$. At the same time, since $Q=dG \bmod n$ as an elliptic curve (under mod n), the result of computing $dG$ (where d is in $n$ (a large prime close to $2^{256}$)) can be quickly reached through repeated addition; while deriving d from Q belongs to the elliptic curve discrete logarithm problem on secp256k1. There is currently no feasible algorithm that can complete it within real-world resources: the complexity of a generic attack is about the $2^{128}$ level, and according to thermodynamics, even using all the energy in the universe, a $2^{256}$ computation would be impossible, thereby making it infeasible in engineering terms.

     Tip: in actual EVM verification, there are also verifications for the domain/address/chainId and other fields inside the SIWE information. This section mainly discusses the mathematical implementation, so those are skipped here

6. Therefore, the server and wallet complete confirmation of wallet ownership using only the signature, the SIWE message, and some defined mathematical information, without exposing the private key

Conclusion#

The above is roughly the mathematical proof behind a wallet signature and verification. Although it seems that with Google’s development in quantum computing, this may change soon, there should still be quite some time, and there is no problem with learning the classics (

That’s all. This can roughly be regarded as a supplement to the theoretical foundation behind the engineering practice of wallet signature verification.