IOTA【技術解説】署名と承認。 - 改訂版

**English [here](https://iotafan.jp/en/developer/signature_and_validation_20180101/).**

#改訂版の背景　
　以前の記事内で更新していない箇所があったため、その結果長い間誤った情報を皆様にお伝えしてしまっていたことをお詫び致します。以前の記事との大きな変更点は**ハッシュ回数の決定方法**です。以前の記事では、ハッシュ回数を単純にトライト`9ABCD...Z`においての9からの距離というふうに説明いたしました。
　しかし、それはバグだったという報告をいただき、最新のソースコードを確認したところ以前とハッシュ回数の決定方法が変わっておりました。
　改訂版ではハッシュ回数についての訂正を行い、旧バージョンで語りきれなかったsecurityという引数による挙動の違いについても言及しました。

# CurlとKerl
　IOTAのハッシュ関数。Curlを改正したのがKerl。発音がどう違うのかは不明。IOTAではハッシュ関数を場所ごとに使い分けている。その早見表は[こちら](https://github.com/iotaledger/kerl)。

# アドレス生成
　まず、シードからPrivate Keyを生成する。詳細は[こちら](https://qiita.com/ABmushi/items/e271ff05884a7d47658d#%E3%82%A2%E3%83%89%E3%83%AC%E3%82%B9)。
①　シードから生成されるPrivate Keyを用意する。
②　Private Keyを27個のセグメントに分割し、それぞれのセグメントごとを**26**回ハッシュ関数に通す。（'L'は最後のセグメントのインデックス。）L = security * 27。
③　②で生成されたすべてのセグメントをまとめてハッシュ関数に通す。その結果得られた値をdigestと呼ぶ。
④　digestを2回ハッシュ関数に通す。その結果得られた値をアドレスと呼ぶ。

![address_gen.png](https://qiita-image-store.s3.amazonaws.com/0/187795/68daa91a-3ffb-c7de-afcc-28e78929ade8.png)

　Private keyはsecurityという引数に代入した1~3の整数の値によって長さを変えることができる。（一応4以上も設計上可能であるが、その分Bundleの署名部分が長くなり、Tangleとのデータ通信効率が悪くなる。[詳細](https://qiita.com/ABmushi/items/0c9f73e08fdb6597ab9c#%E5%85%A5%E5%8A%9B%E9%83%A8---input)）


#署名の方法
①　Private Keyを（アドレス生成と同じやり方で）27個のセグメントに分割する。
②　セグメントごとにN回分ハッシュ関数に通す。
>**Nの求め方**
**署名されるデータ（Signed Data）**のi番目のTryteを見る（A〜Zか9、の全27種類）そのTryteが[この表](https://qiita-image-store.s3.amazonaws.com/0/187795/e325fe61-7773-8e64-46e0-2e98d66aacf4.png)のdecimalのどの数字dに対応しているか確認する。（9ならd=0、Aならd=1...Mならd=13、Nならd=-13...Yならd=-2、Zならd=-1）
*Ni = 13 - d*
i番目のセグメントをNi回ハッシュ関数に通す。

③　そのようにしてハッシュ関数で置き換えられたセグメントたちを順番に横に並べたものをSignature（署名）とする。

![signing1.png](https://qiita-image-store.s3.amazonaws.com/0/187795/303a022c-19ef-fdd9-4125-700f51a8a005.png)




#承認の方法（アドレスの逆生成）
①　署名を（アドレス生成と同じやり方で）27個のセグメントに分割する。
②　セグメントごとにM回分ハッシュ関数に通す。
>**Mの求め方（基本的にNと類似）**
署名されたデータ（Signed Data）のi番目のTryteを見る（A〜Zか9、の全27種類）そのTryteが[この表](https://qiita-image-store.s3.amazonaws.com/0/187795/e325fe61-7773-8e64-46e0-2e98d66aacf4.png)のdecimalのどの数字dに対応しているか確認する。（9ならd=0、Aならd=1...Mならd=13、Nならd=-13...Yならd=-2、Zならd=-1）
*Mi = 13+d*
i番目のセグメントをMi回ハッシュ関数に通す。

③　②で生成されたすべてのセグメントをまとめてハッシュ関数に通す。その結果得られた値をdigestと呼ぶ。
④　digestを2回ハッシュ関数に通す。その結果得られた値がアドレスと一致したら**承認**される。

![validate1.png](https://qiita-image-store.s3.amazonaws.com/0/187795/e4f2e7de-2a46-e25e-4fe9-25a024ad7eba.png)

# 署名されるデータ（Signed Data）
　IOTAの署名は[この記事](https://qiita.com/ABmushi/items/0c9f73e08fdb6597ab9c#%E5%85%A5%E5%8A%9B%E9%83%A8---input)でも説明した通り、**入力部**の生成で必要となったことを思い出して欲しい。Signed DataをPrivate Keyで署名し、署名は入力部の`signatureFragment`に保管される。では、その*Signed Data（署名されるデータ）*は何に当たるのかを最後に説明したい。
　それは、**Bundleのハッシュ（81トライト）**である。（厳密にいうとBundleのハッシュを少々ずらしたNormalized Bundleと呼ばれる中間生成物である。Normalized Bundleも81トライトの文字列でほぼBundleハッシュとして扱えるので細かい話は後に回す。）

 ![singed_data.png](https://qiita-image-store.s3.amazonaws.com/0/187795/f0c3dbb7-503c-51a7-64c3-579162c6fb71.png)

　*Signed Data（署名されるデータ）*は上図のように、data[0]、data[1]、data[2]というNormalized Bundleを分割したものを使う。27セグメントを何回ハッシュに通すかはSigned Dataの27トライトに対応していた。この27トライトが上図のdata[i]である。`security`との関係だが、`security`レベルによってPrivate keyの長さ（`= security * 2187`）は変化し、それによってセグメントの数（`=security*27`）が変化したことを思い出してほしい。`security=2`の場合、セグメント数は54個、つまりdata[0]とdata[1]合わせた54トライトと対応させてセグメントを一つずつN回ハッシュにかける。（Nの求め方は上で説明した。）
　Bundle生成の話と繋げる。`security`によって署名の数が増えた理由は、署名①はdata[0]、署名②はdata[1]、という風に署名されるデータの分担を行なっていたからである。

> デフォルトのAPIでは発行できないが理論上、`security`が4以上もTangleで承認される。（マルチシグはその特性を利用する）。その際はNormalized Bundleが81トライトという理由で、data[2]の次はdata[0]という風にループさせて署名されるデータを作る。

##Normalized Bundleの生成
　口では説明し難いのでソースコードにコメントをふった。マニアックすぎるので正直言って無視して良い。
　なるべくトライト表の両端にあるアルファベット（ABCやXYZ）を中間方面（...IJKL...）へ寄せバランスを取らせている。これは後述するアドレス再利用の際のリスクを軽減させる作用がある。

```java:Bundle.java
/**
     * Normalized the bundle.
     * return the bundle each tryte is written in integer[-13~13]
     *
     * @param bundleHash BundleのHash。
     * @return normalizedBundle A normalized bundle hash.
     */
    public int[] normalizedBundle(String bundleHash) {

        //  normalized Bundle 81トライト。
        //  これに値を当てはめてreturnする。
        int[] normalizedBundle = new int[81];

        //  Bundle Hash(81 トライト)を３つのセクションに分割(1つあたり27トライト)
        for (int i = 0; i < 3; i++) {

            // sum セクションの合計。
            long sum = 0;

            //  1セクション内を１トライトずつ確認し、
            //  そのトライトに対応する整数[-13~13]を求めてセクションの合計に加えていく。
            for (int j = 0; j < 27; j++) {

                //  sum += value
                //  value = normalizedBundleのi*27+j番目のトライト[9~Z]を数字[-13~13]に変換
                sum += 
                    //  トライトに対応する整数[-13~13]をnormalizedBundleの該当ポジションに代入。
                    (normalizedBundle[i * 27 + j] = 

                        //  トライト[9ABC...Z]を整数[-13~13]に変換
                        Converter.value(Converter.tritsString("" + bundleHash.charAt(i * 27 + j)))
                    );
            }

            // もし、sumが0以上なら、
            if (sum >= 0) {

                //  sumが0になるまで
                while (sum-- > 0) {

                    //  セクション内で[-13]以上のトライトを-1する。一つ-1したら最初から。
                    for (int j = 0; j < 27; j++) {
                        if (normalizedBundle[i * 27 + j] > -13) {
                            normalizedBundle[i * 27 + j]--;
                            break;
                        }
                    }
                }

            //  もし、sumが0以下なら、
            } else {

                //  sumが0になるまで
                while (sum++ < 0) {

                    //  セクション内で[13]以下のトライトを+1する。一つ+1したら最初から。
                    for (int j = 0; j < 27; j++) {

                        if (normalizedBundle[i * 27 + j] < 13) {
                            normalizedBundle[i * 27 + j]++;
                            break;
                        }
                    }
                }
            }
        }

        return normalizedBundle;
    }
```

#アドレス再利用のリスク
　基本的にIOTAのアドレスは**再利用できない。**
　言い換えると、**一度支払い元として使ったアドレスに入金できない。**
　厳密に言うと、**一度入力アドレスとして使ったアドレスはもう一度入力アドレスとして使ってはならない。**
　もっと厳密に言うと、**一度署名に使ったPrivate Keyを別の署名に使わない。**

　何故こうなるのかというと、2回目に署名されるデータによっては、Private Key内の**複数**のセグメントにおいて、2回目の署名時に行うハッシュ回数$N_2$が1回目に行ったハッシュ回数$N_1$より大きくなり、1回目の署名からその部分だけ$N_2-N_1$回分少なくハッシュにかければ、その部分だけ2回目の署名を生成することができてしまう。先ほど**複数**という風に表現したが、確率的には50%のセグメントにおいて2回目の署名が誰にでも可能になる。
　言い換えると1回目に署名されたトライトの場所が、2回目署名時にそれ以上（ここで言うトライトの大小は小さい方から9ABC...XYZである）のトライトがある場所だった場合、1回目の署名からその場所を抜き出して、足りないハッシュ回数分、ハッシュの続きを行うことで、古い署名から新しい署名をそのトライトの部位においては作り出せる。もう一度言うと、この部分は全体の約50%（`security=1`なら約13トライトのBundleハッシュ分）になるはずだ。（50% = 署名されるデータ内のある場所において、1回目より2回目のトライトの方が大きくなる確率）
　前の章でBundleハッシュをNormalizeしたのは、なるべくBundleハッシュ内の`9やA,B,C`などのハッシュ回数が少なくなるトライトを大きい数字に変えることでPrivate Keyが再利用された時に少しでもPrivate Key露出率を50%から下げるためである。

　技術的なことが分からなくても、とりあえずIOTAで送金をするたびに、ウォレットの"受取"のところからアドレスを生成するだけで防げるが実はここに盲点がある。スナップショット後はアドレス使用履歴がホストノード上のTangleでは消去されるが、Permanodeには残っている。
　アドレスを生成した後は必ず[Tangle Explorer](https://thetangle.org/)などでそのアドレスを検索して以前使われた（負の額のtxが存在する）かどうかを最終確認する。

## 量子計算耐性
　この署名方式を採択した背景には量子コンピュータ耐性を持たせると言う目的がある。IOTAが採用した署名はWOTS署名と呼ばれる。これについては[Winternitz one-time signature](https://eprint.iacr.org/2011/191.pdf)という論文がある。また、このWOTS署名のアイデアの元となったランポート署名については、[量子コンピュータ耐性があるランポート署名について解説&シェルスクリプトで実装してみた](https://qiita.com/onokatio/items/689965fa484d40d851ce)という記事が参考になるかもしれない。

#トライト表
<img width="184" alt="tryte.png" src="https://qiita-image-store.s3.amazonaws.com/0/187795/e325fe61-7773-8e64-46e0-2e98d66aacf4.png">

#参考文献
IOTA公式ライブラリ [https://github.com/iotaledger](https://github.com/iotaledger)
本記事はSigningという部分。JavaScriptなら[signing.js](https://github.com/iotaledger/iota.lib.js/blob/master/lib/crypto/signing/signing.js)、Javaなら[Signing.java](https://github.com/iotaledger/iota.lib.java/blob/master/jota/src/main/java/jota/utils/Signing.java)から。


　[IOTA](https://iota.org/)の公式[Slack](https://slack.iota.org/)に参加お待ちしております。また、本記事の間違いなどは、コメント欄でもTwitterからでもご報告いただけると幸いです。