簡單聊聊ECDSA與Ethereum的sign message

    本篇不會牽涉到數學公式或是算法，只是簡單解釋格式上的差異

    在我們應用中，會有兩個場景需要對訊息做簽章的動作，一個是簽章完送到smart contract裡用ecrecover做身份確認，另一個是單純把訊息（例如：個人資料）做簽章，確保訊息確實是本人的（就像簽名一樣）。

    我們產品中會有iOS, Android或是後端的C#或JAVA，每種語言對ECDSA的使用方式都有所不同，有原生也有third party library，加上Web3也有提供sign message的功能，一開始大家一知半解，不太知道差異，所以在開發的時候，搞得人仰馬翻。本篇就是針對標準ECDSA跟Web3提供的sign message做一點“簡單”的解釋。

    首先，你要先知道 r s v，不用知道他背後的意義（因為我也不清楚 ＸＤ），但是你需要知道sign（本篇的sign都是指ECDSA）過的message可以被分解為 r s，咦？！ 說好的 v 勒？？ 先破題，這就是標準ECDSA跟Ethereum用來可以recover signed message的差異（其實Ethereum是沿用Bitcoin的）。

    在ECDSA sign完的訊息可以分解成 r 跟 s ，不過只靠rs所反解的public key會有四組，不過實際上大家都只看兩組，因為另外兩組出現機率很低，這篇解答中的推文有解釋。

27 = lower X even Y. 28 = lower X odd Y. 29 = higher X even Y. 30 = higher X odd Y. Note that 29 and 30 are exceedingly rarely, and will in practice only ever be seen in specifically generated examples. There are only two possible X values if r is between 1 and (p mod n), which has a chance of about 0.000000000000000000000000000000000000373 % to happen randomly. 

    那在Ethereum裡怎麼知道signed的訊息是哪組public key呢？我們可以看一下Web3j 實際的implementation

int headerByte; for(headerByte = 0; headerByte < 4; ++headerByte) { BigInteger k = recoverFromSignature(headerByte, sig, messageHash); if (k != null && k.equals(publicKey)) { recId = headerByte; break; } }

    這是在Sign.signMessage中的片段（org.web3j.crypto package中），我們可以看到這裡的for loop跑四次，把各種可能跑過一次。所以實際出來的值應該會是0,1,2,3，不過如上面所解釋，2跟3出現機率低，所以都只有0跟1。在應用上把對的那組public key的值記成v。這就是 v 的由來，很簡單吧！關於public key recovery這裡還有一篇解釋。
    然後Ethereum會把得出來的 v 值加上27，所以在Ethereum中會看到27 or 28，不過！！在EIP155中，把這個值改成v = CHAIN_ID * 2 + 35 or v = CHAIN_ID * 2 + 36，所以在主鏈上會變成37 or 38。 

    再來，會針對格式做一些解釋。首先，先解釋ECDSA所產出的格式，這裡有詳細的解釋。基本上是DER format，長度會是71, 72或73 bytes，可以看Bitcoin wiki的介紹，sign完後的資料會長得像這樣

3045022100d5e90a3ce97af1f9645c46600ba178b9ad6f5b3abb183088d0c0bd881abe054c022030d0de96e fb49474f5aeb64b56a27ac020056f5e8a019e5419a6ccad217cad97

根據連結中的解釋，格式如下

30 + len(z) + 02 + len(r) + r + 02 + len(s) + s

所以可以把訊息拆成這樣

    這也就是為什麼，每次sign完的訊息都是3045, 3046或是3047(47好像比較少見)開頭。再來，有個比較奇怪的是，為什麼r, s是32 bytes，但有時候長度會是33 bytes，因為第一個byte的值如果大於"0x7f"（就是第一個bit 為 1, 0x80），則前面會加上"00"作為判別。以上圖為例，可以看到 02 21 00 d5e9....，"0xde"大於"0x7f"，所以前面就多"00"。

接著，我們回來看r s v 的格式，r s v就相對簡單，就 

    r : 32 bytes
    s : 32 bytes
    v : 1 byte

    今天大概就介紹到這裡，我本身沒有數學的基礎，都是統整google來的資訊，所以如果有誤，歡迎也麻煩指正。