一、概要

????Sponge是IOTA自身抽象的 柳沙，目前有兩種實現(xiàn)窟赏，一個是kerl,另外一個curl妓柜。而kerl 是基于hash 散列函數(shù)Keccak 封裝。而curl 自是自己法明的hash 散列函數(shù)涯穷。一方面棍掐，像區(qū)塊鏈地址生成，交易簽名的實現(xiàn)等拷况，都需要依賴于此hash散列函數(shù)作煌；另一方面，基于該類hash 簽名具有防量子算法攻擊的作用赚瘦，導致iota 目前的 賬戶體系的特殊(區(qū)塊鏈地址不可重用粟誓，后面在詳細分析)，所以起意，有必要深入該算法實現(xiàn)鹰服。

二、詳細介紹&解析

???? IOTA 使用了三進制作為編碼方式揽咕，所以使用了 SHA-3 發(fā)明者設計的三進制哈希算法 Curl悲酷；但是波士頓和 MIT 大學在 2017 年 9 月發(fā)布了一篇名為IOTA Vulnerability Report: Cryptanalysis of the Curl Hash Function Enabling Practical Signature Forgery Attacks on the IOTA Cryptocurrency的報告，指出IOTA 的簽名實現(xiàn)中亲善，使用 Curl 三進制哈希算法设易，會存在hash 碰撞。

???? 作為區(qū)塊鏈項目底層的重要設施的哈希算法蛹头，Curl 并沒有經(jīng)歷過較長時間的研究和審查就這樣使用在了公鏈中顿肺，這種做法并不是特別的明智，在出現(xiàn)安全隱患之后渣蜗，IOTA 團隊切換至更加成熟的 Keccak 哈希算法屠尊，當然，curl 本身作為hash 摘要還是沒問題的袍睡。這里額外像補充密碼學中的一條『黃金法則』- 永遠不要自己發(fā)明加密算法知染。

The golden rule of cryptographic systems is “don’t roll your own crypto.”

因此，本章節(jié)打算用4小節(jié)來詳細分析
1）Sponge 算法蔟設計
2）Keccak 算法詳解
3）Kerl 算法詳解
4）Curl 算法詳解

2.1 Sponge算法蔟設計

Sponge 算法蔟

????上面為IOTA 設計的海綿函數(shù)類圖斑胜，主要實現(xiàn)有Kerl 以及 Curl控淡。然后下面為這倆類函數(shù)在IOTA 中的用途：

Sponge 用途

????根據(jù)[Sponge 用途]總結，我們可以知道止潘，區(qū)塊鏈地址生成掺炭、簽名生成、驗簽 以及 bundle hash 生成都是使用Kerl hash 算法凭戴，另外涧狮，iota 地址是81t'rytes組成，然后在用9個trytes 作為校驗和；這里需要注意的是者冤，在iota 中的bundle模型 才對應我們日常理解的transaction肤视，而iota 中的transaction 模型 則對應比特幣中input/output，這個在后續(xù)會詳細分析涉枫。邢滑，
????另外Curl-P-N 中的N 則表明對一個輸入運算相同的hash 轉換函數(shù)N 次；transaction 模型的hash 生成 以及 bundle 中的微型 pow 使用Curl-P-81, Milestone 校驗則使用Curl-P-27愿汰。

2.2 Keccak 算法詳解

????在介紹Sponge 前困后，我們先來介紹Keccak，Keccak使用的是海綿函數(shù):

海綿函數(shù)

它使用有限的狀態(tài)衬廷，接收任何長度的輸入字節(jié)數(shù)組摇予，然后按照指定長度字節(jié)數(shù)組輸出。

海綿函數(shù)是由三個部分組成：

• 一個內存狀態(tài) S吗跋，包含 b個 bit
• 一個能置換或者轉換內存狀態(tài)侧戴，固定大小的轉換函數(shù) f
• 一個填充函數(shù)（padding function）P

內存狀態(tài)會分成兩個區(qū)塊，R（大小為 r bit）與 C（大小為b-r bit）小腊。這里的參數(shù) r又叫做轉換率（bitrate）救鲤，而 c叫做容量（capacity）。填充函數(shù)會在輸入里面增加足夠的長度秩冈，讓輸入的比特流長度變成 r的整數(shù)倍。因此填充過后的輸入可以被切成長度為 r的數(shù)個分段斥扛。然后入问，海綿函數(shù)運作如下：

• S先初始化為零
• 輸入經(jīng)過填充函數(shù)處理
• 填充后輸入的前面 r個bit會與R進行XOR運算
• S經(jīng)過函數(shù) f轉換成 f(S)
• 如果填充后輸入還有剩余，下一 r bit的分段與 R進行XOR運算
• S轉換成f(S)
• …

這過程一直重復到所有的輸入都用完為止（在海棉的譬喻里面稀颁，被函數(shù)“吸收[absorb]”了）芬失。

現(xiàn)在海綿函數(shù)可以依照如下的過程輸出（“擠出”[squeeze]內容）：

• 此時 R里面的數(shù)據(jù)是輸出的前面 r個 bit
• 如果需要更多輸出，先把 S轉換成f(S)
• 此時R里面的數(shù)據(jù)是輸出的下面 r個bit
• …

這過程會重復到滿足輸出所需要的長度為止匾灶。這里值得注意的地方是棱烂，輸入絕對不會與C這部分的存儲器作XOR運算，而且 C這一部分存儲器也不會直接被輸出阶女。 C這一部分的存儲器僅僅只和轉換函數(shù)f相關颊糜。在散列里面，防止撞擊攻擊（Collision attack）或者原像攻擊（preimage attack）是依靠 C這段存儲器作到的秃踩。一般實做上 C的大小會是所希望防止等級的兩倍衬鱼。

????開源hash算法實現(xiàn)org.bouncycastle中，其海綿函數(shù)實現(xiàn)則對應于 KeccakDigest(implement of Keccak)憔杨。這里補充一下鸟赫，sha3 的核心是進一步封裝了KeccakDigest 中 absorb 以及 squeeze。我們通過一段代碼來了解一下：

    // 接受任意長度的字節(jié)數(shù)組內容輸入
    // 返回長度為 256字節(jié)的散列結果
    public static byte[] sha3_256(byte[] bytes) {
        Digest digest256 = new SHA3Digest(256);
        //absorb
        digest256.update(bytes, 0, bytes.length);

        //結果存放，大小為256
        byte[] result = new byte[digest256.getDigestSize()];

        // squeeze抛蚤，將散列結果寫入result
        digest256.doFinal(result, 0);

        return result;
    }

   //SHA3Digest 繼承于 Keccak 台谢，對hash 結果的大小進行裁剪封裝
    public class SHA3Digest extends KeccakDigest {
        public SHA3Digest(int bitLength) {
            //KeccakDigest(int bitLength)
            super(checkBitLength(bitLength));
        }
    }

上述代碼段是sha3_256 的封裝，入?yún)⑹侨我忾L度的字節(jié)數(shù)組岁经，返回長度為 256/8 = 32字節(jié)數(shù)組的散列結果对碌，具體的做法是通過海綿函數(shù)Keccak所提供absorb-squeeze 來實現(xiàn)，當然蒿偎，根據(jù)上述absorb-squeeze 可以反復調用的朽们，具體看使用者如何來架構自身的加密體系。另外诉位，本章節(jié)不會升入Keccak 中的absorb-squeeze的代碼詳細骑脱。

????而IOTA 中的Kerl hash 算法，同樣也是封裝了KeccakDigest(384),下面詳細分析苍糠。

2.3 Kerl 算法詳解

????經(jīng)過上面的分析叁丧，我們了解了Keccak 算法的實現(xiàn)原理。一方面岳瞭，我們在《IOTA基石 - 三進制系統(tǒng)之 Trit 和 Tryte》章節(jié)中已詳細分析iota 是基于三級制構建的拥娄，而KeccakDigest 接受的輸入是byte 數(shù)組，返回也是字節(jié)數(shù)組瞳筏；因此稚瘾，Kerl 算法核心是在將輸入的三進制數(shù)組轉成 byte 數(shù)組作為輸入，經(jīng)過Keccak的absorb-squeeze 后姚炕，把輸出結果轉為再次轉為三進制摊欠，詳細先看absorb：

    public void absorb(final byte[] trits, final int offset, final int length) {
        if (length % 243 != 0) {
            throw new RuntimeException("Illegal length: " + length);
        }
        // HASH_LENGTH = 243
        // 分段處理
        for (int pos = offset; pos < offset + length; pos += HASH_LENGTH) {
            //BYTE_HASH_LENGTH = 384/8
            //convert to bytes && update
            byte[] state = new byte[BYTE_HASH_LENGTH];
            // 最后一位設置為0？
            trits[pos + HASH_LENGTH - 1] = 0;
            bytesFromBigInt(bigIntFromTrits(trits, pos, HASH_LENGTH), state);
            // absorb
            keccak.update(state);
        }
    }

上述代碼段為封裝keccak的absorb的實現(xiàn)柱宦，核心是先通過bigIntFromTrits(...)將傳進的三進制字節(jié)轉bigInt,然后在通過bytesFromBigInt(...)將biguInt 轉成正常的字節(jié)數(shù)組些椒，最后在使用keccak原生的absorb 實現(xiàn)。當然掸刊，這里是以243大小 對trits進行分段absorb免糕，基于iota 定義hash 大小為243。對于具體的bigIntFromTrits(...) 以及 bytesFromBigInt(...) 已在《IOTA 三進制系統(tǒng)之 Trit 和 Tryte》中詳細分析忧侧，這里不再深入石窑。我們接著分析squeeze(...):

    public void squeeze(final byte[] trits, final int offset, final int length) {
        if (length % 243 != 0) {
            throw new IllegalArgumentException("Illegal length: " + length);
        }
        try {
            for (int pos = offset; pos < offset + length; pos += HASH_LENGTH) {

                byte[] state = new byte[BYTE_HASH_LENGTH];
                //squeeze
                keccak.digest(state, 0, BYTE_HASH_LENGTH);

                //convert into trits
                BigInteger value = new BigInteger(state);
                tritsFromBigInt(value, trits, pos, Sponge.HASH_LENGTH);
                trits[pos + HASH_LENGTH - 1] = 0;

                //calculate hash again
                for (int i = state.length; i-- > 0; ) {
                    state[i] = (byte) (state[i] ^ 0xFF);
                }
                keccak.update(state);
            }
        } catch (DigestException e) {
            e.printStackTrace(System.err);
            throw new RuntimeException(e);
        }
    }

基于absorb 是分段處理，同理苍柏，squeeze也需要分段處理尼斧，通過keccak原生的squeeze(這里對應方法keccak.digest(state, 0, BYTE_HASH_LENGTH))對相應的243 分段獲取hash摘要結果，結果是byte 字節(jié)數(shù)組试吁，存放于臨時字節(jié)數(shù)組遍歷state中棺棵，然后在通過tritsFromBigInt(...)將state 轉為 trits楼咳。
到這里，kerl 實現(xiàn)分析完畢烛恤。

2.4 Curl 算法詳解

????剛剛在上文有提到母怜，Curl hash 算法用途主要有兩類，一類是生成transaction 模型的唯一hash缚柏，另外一類主要是用于pow 運行苹熏；而Curl 的pow 類運算實現(xiàn)已有相應PearlDiver (可理解為Curl中相應的pow 實現(xiàn)被移到PearlDiver 中)類實現(xiàn)，因此币喧，本章節(jié)不會分析pow 相應hash 運算轨域，會在后續(xù)的pow 實現(xiàn)中在詳細分析，這里主要是分析生成唯一hash的轉換實現(xiàn)杀餐。當然干发，這里也只是分析其工程實現(xiàn)，至于具體的數(shù)學論證本章節(jié)不會涉及史翘。

????因為Curl 也是海綿函數(shù)枉长，因此我們只需分析absorb-squeeze 即可：

//------------------------absorb
    private static final int STATE_LENGTH = 3 * HASH_LENGTH; // HASH_LENGTH = 243

    private final byte[] state;

    // 構造函數(shù)，27/81
    protected Curl(SpongeFactory.Mode mode) {
        switch(mode) {
            case CURLP27: {
                numberOfRounds = NUMBER_OF_ROUNDSP27;
            } break;
            case CURLP81: {
                numberOfRounds = NUMBER_OF_ROUNDSP81;
            } break;
            default: throw new NoSuchElementException("Only Curl-P-27 and Curl-P-81 are supported.");
        }
        state = new byte[STATE_LENGTH];
        //...
    }

    public JCurl absorb(final int[] trits) {
        return absorb(trits, 0, trits.length);
    }

    public JCurl absorb(final int[] trits, int offset, int length) {

        do {
            System.arraycopy(trits, offset, state, 0, length < HASH_LENGTH ? length : HASH_LENGTH);
            transform();
            offset += HASH_LENGTH;
        } while ((length -= HASH_LENGTH) > 0);

        return this;
    }

    public int[] squeeze(final int[] trits) {
        return squeeze(trits, 0, trits.length);
    }
//-------------------------- sqeeze
    public int[] squeeze(final int[] trits, int offset, int length) {

        do {
            System.arraycopy(state, 0, trits, offset, length < HASH_LENGTH ? length : HASH_LENGTH);
            transform();
            offset += HASH_LENGTH;
        } while ((length -= HASH_LENGTH) > 0);

        return state;
    }

從上述實現(xiàn)中琼讽，我們可以看到absorb以及 squeeze 實現(xiàn)一致必峰，首先都是 分段處理輸入，每段大小為3 * 243钻蹬；然后在通過當前狀態(tài)存儲 字節(jié)數(shù)組 state 以及 入?yún)rits作transform()轉換吼蚁。當然，absorb 流程中脉让，將入?yún)rits 的內容作為 state 的初始值桂敛；因此，我們繼續(xù)深入transform()：

    private static final byte[] TRUTH_TABLE = {1, 0, -1, 2, 1, -1, 0, 2, -1, 1, 0};

    private final byte[] state;

    // STATE_LENGTH = 3 * 243
    private final byte[] scratchpad = new byte[STATE_LENGTH];

    private void transform() {

        int scratchpadIndex = 0;
        int prevScratchpadIndex = 0;
        // 轉換輪次numberOfRounds(27/81)
        for (int round = 0; round < numberOfRounds; round++) {
             // 將沒一輪次的轉換結果state 全量拷貝至scratchpad
            System.arraycopy(state, 0, scratchpad, 0, STATE_LENGTH);
            for (int stateIndex = 0; stateIndex < STATE_LENGTH; stateIndex++) {
                prevScratchpadIndex = scratchpadIndex;
                if (scratchpadIndex < 365) {
                    scratchpadIndex += 364;
                } else {
                    scratchpadIndex += -365;
                }
                state[stateIndex] = TRUTH_TABLE[scratchpad[prevScratchpadIndex] + (scratchpad[scratchpadIndex] << 2) + 5];
            }
        }
    }

上面的轉換算法比較簡單易讀溅潜，核心是反復對自身轉換的結果按照同樣的方式進行轉換指定次數(shù)(27 或者 81 次)，第一個for 主要是控制轉換輪次薪伏，并將上一次轉換結果全量拷貝至輔助狀態(tài)scratchpad 中(兩者都是長度相同的字節(jié)數(shù)組)滚澜；第二個for 循環(huán)式執(zhí)行正真的轉換，根據(jù)上次轉換結果scratchpad 作為參考轉嫁怀。

轉換方式如下：

stateIndex從0到STATE_LENGTH 重新計算每一個state[stateIndex] 的數(shù)值设捐。計算方式為TRUTH_TABLE[scratchpad[prevScratchpadIndex] + (scratchpad[scratchpadIndex] << 2) + 5] 。即根據(jù)scratchpad[prevScratchpadIndex] + (scratchpad[scratchpadIndex] << 2) + 5作為index塘淑，從TRUTH_TABLE 獲取相應的整數(shù)值萝招。scratchpadIndex 從0開始，每一次for 循環(huán)作一次變更存捺，變更條件是如果當前scratchpadIndex值小于365,則加364槐沼，否則減365曙蒸；而prevScratchpadIndex則取上一次scratchpadIndex的值。上述所使用的是(代換-置換網(wǎng)絡)算法實現(xiàn)岗钩。

到這里纽窟，Sponge 算法詳解 分析完畢。