Digital Signature

sited from wiki

電子簽章是一種透過加密/演算法等方式來驗證身分/或是達到其他驗證目的的方式。

簡化來說就是傳訊方（signer）將想要傳遞給收訊方（verifier）的訊息進行簽章，再由收訊方（verifier）進行驗章的動作。

這樣的簽章（Signature）方式不僅可以維護安全性（不會揭露簽章後的東西）又可以當作驗證身分的工具。

What is ECDSA?

ECDSA 的全名為 Elliptic Curve Digital Signature Algorithm，是一種用來簽章與驗章的演算法，其使用了橢圓曲線加密（Elliptic Curve Cyptogaphy, ECC）這種加密方法。

ECC

橢圓曲線方程式為 y^2 = x^3 + ax + b，此曲線對稱於 x 軸，且這條曲線必須滿足 4a^3 + 25b^2 ≠ 0 才能有唯一解。

這個曲線具有幾個有趣的特性：

1. 在曲線上任何一點都以 x 軸反射。
2. 任一不垂直的線與曲線最多只有三個交點。

A dot B = C
A dot C = D
A dot D = E
...

原本為 A 的點經過 d 次的自行 dot (見上圖) 後，會得到一個最終點 B。

透過這樣的方式可以得到公鑰（B）與私鑰（d）。

因此會有 B = d * A 這樣的關係式。

(詳細可見此文章)

Asymmetric Cryptography

ECC 是一種「公開密鑰加密演算法」aka「非對稱式加密演算法」。舉例來說，設 d() 為我們拿來加密的函式/ 演算法，人類和電腦都難以從 d(A) 來推算回 A（原本的資料）。

由於難以回推出原本的數據，因此驗證會以正向驗證的方式來進行，也就是透過 A -> d(A) => d(A) 的方式驗證。

ECDSA 原理

這邊設私鑰為 d、公鑰為 B、簽署的訊息 x。
以 ECDSA 而言，d 與 B 的關係是:B = d * A (A 為在橢圓曲線上隨機取的某點)。

私鑰如何簽名:

1. 會先取一密鑰 Ke。
2. R = Ke * A = (Xr, Yr)
3. let r = Xr
4. 簽章: s = ((h(x) + d * r))mod q

公鑰如何驗證:

1. let
   • u1 = (h(x) / s) mod q
   • u2 = (r / s) mod q
2. P = u1 * A + u2 * B = (Xp, Yp)
3. verify:
   我們只要驗證 R 的 X 座標 == P 的 X 座標 就可以證明此簽章是由本人發出的。

s = (h(x) + d * r) / S mod q
Ke = (h(x) / s) + (d * r / s)
   = u1 + d * u2
Ke * A = u1 * A + d * A * u2 (B = d * A)
Ke * A = u1 * A + u2 * B
------   ---------------
 R點            P點

because Xr == Xp => "valid"

更詳細可見我朋友 Yanlong 的文章還有 Alu 的文章

以太坊公私鑰

拿以太坊為例，每個錢包產生的時會產生一組「隨機生成的私鑰」。這把私鑰會透過橢圓曲線生成公鑰，這把公鑰會再經由 keccak256() 再取部分資訊成為在 MetaMask 上可以看到的地址。

在以太坊中我們可以透過 MetaMask（在 local 端儲存著我們的私鑰）將交易進行簽章，provider 再將包好的交易廣播到網路上，最後再經由礦工驗證與打包 => (後方流程見此)。

如果我們只是要進行線下的簽章，可以使用 web3.eth.accounts.sign 或是下面會用到的方式。

Implement

Steps

Sign

簽署的步驟有三個:

1. 輸入傳入的資訊。
2. 進行 hash。
3. 簽署整個資訊。

這部分會在線下進行

const account = accounts[0];
const message = buf2hex(keccak256("Verify Your Ticket."));

window.ethereum.request({
  method: "personal_sign",
  params: [
    account, 
    message
  ]
})
.then(console.log);

account 就是目前 MetaMask 上的地址，message 則是為了要傳入 verify() 中而進行 keccak256()。 personal_sign 可以呼叫 MetaMask 進行簽章，並回傳 signature。

在鏈上我們可以利用這樣的方式來驗證傳訊者是否為你的帳號。

Verify

這邊不使用 OZ 中的 ECDSA contract 進行驗證，而是用自己寫好的合約來進行。

首先寫好一個用來驗證的 Contract，其主要的驗證函式為 verify()。

hash()

function verify(address _signer, string memory _message, bytes32 memory _sig) 
    external pure 
    returns(bool) 
{
    bytes32 messageHash = getMessageHash(_message);
    bytes32 ethSignedMessageHash = getEthSignedMessageHash(messageHash);
    
    return (recover(ethSignedMessageHash, _sig) == _signer);
}

function getMessageHash(string memory _message) 
    public pure 
    returns(bytes32) 
{
    return keccak256(abi.encodePacked(_message));
}
function getEthSignedMessageHash(bytes32 memory _messageHash) 
    public pure 
    returns(bytes32) 
{
    return keccak256(abi.encodePacked(
        "\x19Ethereum Signed Message:\n32",
        _message));
}

這邊會用到兩層 Hash，第一層會先進行 keccak256()，而第二層 getEthSignedMessage() 會加上一個 prefix: "\x19Ethereum Signed Message:\n32" 再進行 hash()。

在以太坊的簽章中會加入這段 prefix 一起進行 hash() 最後得到 signature。

recover()

接下來會進行驗證，主要透過在 solidity 中內建的函式 ecrecover()，其中會傳入四個 params，經過 hash 的資訊，v, r, s。

而 r, s, v 三者分別是 signature 中帶有的資訊，這邊使用 _split() 將它們分割。

在 _split() 中用了 assembly 的方式把 _sig 中的 bytes 分割並存入三個變數中。詳細的語法可以見這個影片

function recover(bytes32 _ethSignedMessageHash, bytes memory _sig)  
    public pure 
    returns(address)
{
    (bytes32 r, bytes32 s, uint8 v) = _split(_sig);
    return ecrecover(_ethSignedMessageHash, v, r, s);
}

function _split(bytes32 _sig) 
    internal pure 
    returns(bytes32 r, bytes32 s, uint8 v) 
{
    require(_sig.length == 65, "Invalid Signature Length")
    assembly {
        r := mload(add(_sig, 32))
        s := mload(add(_sig, 64))
        v := byte(0, mload(add(_sig, 96)))
    }
} 

Display

先用一個 useState(): sig 來儲存線下簽章得到的 signature。

接下來跟先前一樣，使用 web3.contract.call() 來得到一個 boolean 的回傳值。

const verifyAddress = "0xE456372bDA3c8C37756339842b9E53EF4e9fda80";
const web3 = new Web3(Web3.givenProvider);

const verifyContract = new web3.eth.Contract(abi, verifyAddress);
await verifyContract.methods.verify(message, sig).call({
  from: window.ethereum.selectedAddress
})
.then( (result)=> {
  console.log(result);
});

可以看到回傳為 true：（上方為 signature）

Closing

今天的內容對於我這個不需要修微積分的三類生來說真的非常的痛苦，不管是對於橢圓方程式中數學的理解，還是驗證的過程都花費了我很久的時間才搞懂。

這也讓我了解自己與本科生的差距有多少，還有非常多東西需要補強，加油！

Ref:

• Using Signatures (ECDSA) for NFT Whitelists
• Backend signature verification
• A Point of Practice for Signature Verification in Solidity Contracts
• ECC (Elliptic Curve Cryptosystem)
• Verify Signature | Solidity 0.8
• Verifying Signature

若有文章內有任何錯誤的地方歡迎指點與討論！非常感謝！

歡迎贊助窮困潦倒大學生
0xd8538ea74825080c0c80B9B175f57e91Ff885Cb4