數(shù)學(xué)魔法：（以太坊中的）乘法部分

本文作者： AI研習(xí)社-譯站

2018-09-03 15:11

導(dǎo)語：在本系列中，我會(huì)對(duì)一些先進(jìn)的技術(shù)進(jìn)行推導(dǎo)。今天，我會(huì)改良 safeMul 庫。

雷鋒網(wǎng)按：本文為 AI 研習(xí)社編譯的技術(shù)博客，原標(biāo)題 Mathemagic: Full Multiplication，作者為 Remco Bloemen。

翻譯 | 余杭校對(duì) | 醬番梨審核 | 醬番梨

大量的智能合約使用 SafeMath 庫，以確保合約的結(jié)果正確，但它是通過使交易失敗，而不是矯正它們。讓我們嘗試進(jìn)行正確的數(shù)學(xué)運(yùn)算。在本系列中，我會(huì)對(duì)一些先進(jìn)的技術(shù)進(jìn)行推導(dǎo)。今天，我會(huì)改良 safeMul 庫。

如果對(duì)兩個(gè)數(shù)值進(jìn)行相乘，結(jié)果會(huì)是之前的兩倍大小。在以太坊中，對(duì)兩個(gè)數(shù)值進(jìn)行相乘，結(jié)果最高會(huì)是 512 位。但以太坊僅僅給出結(jié)果的下半部分，它會(huì)忽略剩余部分。這在數(shù)學(xué)中稱作模數(shù)運(yùn)算。

然而，省略數(shù)字在會(huì)計(jì)中是不可接受的。因此必須想辦法避免這種情況的發(fā)生，不然會(huì)導(dǎo)致某些人失去非常有價(jià)值的東西。一個(gè)非常受歡迎的庫叫做 SafeMath 。

當(dāng)這種情況發(fā)生時(shí) SafeMath 就會(huì)檢測到然后終止交易，但如果你不希望交易終止又該如何呢？

如果你想要對(duì)任意數(shù)值進(jìn)行想成并且想要得到一個(gè)完整的結(jié)果又該怎么辦呢？

溫馨提示：這是能實(shí)現(xiàn)上述功能的 Solidity 高亮代碼。

數(shù)學(xué)魔法：（以太坊中的）乘法部分

經(jīng)過優(yōu)化的在 Solidity 中完整的 512 位乘法。

在我們深入了解之前，先正確定義問題：即已知兩個(gè)無符號(hào)數(shù)值 a 和 b ，并且它們的長度都是 256 位，并且希望得到它們的乘積，即 512 位數(shù)字 x 。

數(shù)學(xué)魔法：（以太坊中的）乘法部分

因?yàn)閿?shù)值過于龐大以至于無法在代碼中呈現(xiàn)，所以我們將其拆分成最低有效 256 位和最高有效 256 位，即 r0 和 r1。對(duì)應(yīng)地：

數(shù)學(xué)魔法：（以太坊中的）乘法部分

左邊方括號(hào)帶下標(biāo)的表示模運(yùn)算，右邊帶下半括號(hào)的表示下取整運(yùn)算。

教科書算法

解決這個(gè)問題的經(jīng)典方法是長乘，這個(gè)方法我們?cè)趯W(xué)校已經(jīng)學(xué)習(xí)過了。把大數(shù)拆分成較小的數(shù)，乘以對(duì)應(yīng)位的數(shù)值，然后把結(jié)果相加。這個(gè)方法同樣適用于二進(jìn)制和其他進(jìn)制。讓我快速地向你們展示在這里如何使用它.

因?yàn)橹С?256 位內(nèi)置乘法，所以我們可以對(duì)任意兩個(gè) 128 位數(shù)相乘然后得到全部的結(jié)果。因此如果把大數(shù)拆分成每組 128 位，那么我們可以計(jì)算出所有的結(jié)果。取 a0 和 a1 分別對(duì)應(yīng)于 a 的最低有效 128 位和最高有效 128 位，對(duì) b 也是類似的操作：

數(shù)學(xué)魔法：（以太坊中的）乘法部分

現(xiàn)在原始數(shù)值 a 和 b 可以等同地寫作：

數(shù)學(xué)魔法：（以太坊中的）乘法部分

如果我們將其替換進(jìn)結(jié)果等式，那么原等式可寫作：

數(shù)學(xué)魔法：（以太坊中的）乘法部分

忽略常數(shù)部分，我們得到了四個(gè)乘式而不是之前的一個(gè)。因?yàn)樗膫€(gè)乘式的數(shù)值都小于 2 的 128 次方，因此可以被直接計(jì)算。但結(jié)果依然過于龐大，因此仍然需要用兩個(gè)數(shù) r0 和 r1 來表示它。

我會(huì)跳過如何從這個(gè)表達(dá)式中獲取 r0 和 r1 的部分，因?yàn)樗m然直接，但是轉(zhuǎn)換和代入過程非常惱人。最終的結(jié)果是：

數(shù)學(xué)魔法：（以太坊中的）乘法部分

支持 512 位的教科書算法

（請(qǐng)注意如果 Solidity 編譯器的版本為 0.4.18，那么在編譯上述實(shí)例時(shí)會(huì)失敗，因?yàn)榫幾g器無法處理過多的本地變量。但這可以通過內(nèi)聯(lián)表達(dá)式很輕松地解決，但因?yàn)檫@會(huì)降低可讀性所以我沒有選擇在本例中使用內(nèi)聯(lián)表達(dá)式。）

i01 以及 i10 兩個(gè)乘式可以通過 Karatsuba 算法合并成一個(gè)乘式，這是在消耗額外的 gas 為代價(jià)的前提下。因?yàn)轭~外的 gas 量為 3，而整個(gè)乘式消耗的 gas 量為 5，因此并不值得使用 Karatsuba 算法。但是如果想要做更大位數(shù)的乘法（比如 4096 位），那么值得使用 Karastuba 算法。

通過使用兩個(gè)取模運(yùn)算，四個(gè)除法，六個(gè)加法，兩個(gè)條件分支，以及不少于六個(gè)乘法，我們已經(jīng)解決了這個(gè)問題。整個(gè)函數(shù)總消耗超過 300 gas。這似乎還不錯(cuò)，但是 gas 的消耗量已經(jīng)超過正常乘法 5 gas 消耗的 2 個(gè)數(shù)量級(jí)，或是標(biāo)準(zhǔn) safeMul 的 90 倍。我們可以做得更好。

中國的余數(shù)定理

技巧部分：使用 mulmod 指令以及中國的余數(shù)定理，簡而言之，定理闡述的是如果已知一個(gè)數(shù)的模是 2 的 256 次方以及 2 的 256 次方 -1，那么我們可以計(jì)算出它的 512 位表示方法，使用的函數(shù)是 ChineseRemainder , 在 a previous post 中有過相關(guān)描述。我們首先需要計(jì)算出兩個(gè)取模運(yùn)算的結(jié)果：

數(shù)學(xué)魔法：（以太坊中的）乘法部分