仮想通貨
暗号通貨
iota

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

English here.

改訂版の背景 

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

CurlとKerl

 IOTAのハッシュ関数。Curlを改正したのがKerl。発音がどう違うのかは不明。IOTAではハッシュ関数を場所ごとに使い分けている。その早見表はこちら

アドレス生成

 まず、シードからPrivate Keyを生成する。詳細はこちら
① シードから生成されるPrivate Keyを用意する。
② Private Keyを27個のセグメントに分割し、それぞれのセグメントごとを26回ハッシュ関数に通す。('L'は最後のセグメントのインデックス。)L = security * 27。
③ ②で生成されたすべてのセグメントをまとめてハッシュ関数に通す。その結果得られた値をdigestと呼ぶ。
④ digestを2回ハッシュ関数に通す。その結果得られた値をアドレスと呼ぶ。

address_gen.png

 Private keyはsecurityという引数に代入した1~3の整数の値によって長さを変えることができる。(一応4以上も設計上可能であるが、その分Bundleの署名部分が長くなり、Tangleとのデータ通信効率が悪くなる。詳細

署名の方法

① Private Keyを(アドレス生成と同じやり方で)27個のセグメントに分割する。
② セグメントごとにN回分ハッシュ関数に通す。

Nの求め方
署名されるデータ(Signed Data)のi番目のTryteを見る(A〜Zか9、の全27種類)そのTryteがこの表の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

承認の方法(アドレスの逆生成)

① 署名を(アドレス生成と同じやり方で)27個のセグメントに分割する。
② セグメントごとにM回分ハッシュ関数に通す。

Mの求め方(基本的にNと類似)
署名されたデータ(Signed Data)のi番目のTryteを見る(A〜Zか9、の全27種類)そのTryteがこの表の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

署名されるデータ(Signed Data)

 IOTAの署名はこの記事でも説明した通り、入力部の生成で必要となったことを思い出して欲しい。Signed DataをPrivate Keyで署名し、署名は入力部のsignatureFragmentに保管される。では、そのSigned Data(署名されるデータ)は何に当たるのかを最後に説明したい。
 それは、Bundleのハッシュ(81トライト)である。(厳密にいうとBundleのハッシュを少々ずらしたNormalized Bundleと呼ばれる中間生成物である。Normalized Bundleも81トライトの文字列でほぼBundleハッシュとして扱えるので細かい話は後に回す。)

singed_data.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の生成

 口では説明し難いのでソースコードにコメントをふった。マニアックすぎるので正直言って無視して良い。
 なるべくトライト表の中間にあるアルファベット(..IJKLMNOP..)を[ABCやXYZ]方面へ寄せバランスを取らせている。しかし、その意義は残念ながら分からない。こうすることで、セクション全体として見ると平均ハッシュ回数を13にする。

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 トライト)を3つのセクションに分割(1つあたり27トライト)
        for (int i = 0; i < 3; i++) {

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

            //  1セクション内を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 Supportからウォレットの"タングルにアタッチ"機能とセキュリティの関係について記事が出され、個人的にいくつかの疑問点が払拭されたので説明する。まず、署名方法の中のNの求め方を見てほしい。

Nの求め方
署名されるデータ(Signed Data)のi番目のTryteを見る(A〜Zか9、の全27種類)そのTryteがこの表の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回ハッシュ関数に通す。

 データ内i番目のトライトがによって、Prvate Key内のi番目のセグメントにハッシュ関数が少なくなる場合がある。例えばMなら0回だ(13-13=0)。もし、署名されるデータがMを多く含むものであった場合、電子署名はPrivate Keyの部分的な生データを総当たりで求められてしまう。つまり、同じアドレスを再利用して様々なデータにそのアドレス名義で署名を行えば行うほど、生のPrivate Keyがハックされてしまう可能性が高まる。
 また、ハッシュ回数が少ないとBundleが再生成されてしまう。

これを防ぐためにすることは、一度使ったアドレスは二度と使わない。
言い換えると、一度支払いに使ったアドレスに入金しない。
厳密に言うと、一度入力アドレスとして使ったアドレスはもう一度入力アドレスとして使ってはならない。
もっと厳密に言うと、一度署名に使ったPrivate Keyを別の署名に使わない。
 技術的なことが分からなくても、とりあえずIOTAで送金をするたびに、ウォレットの"受取"のところからアドレスを生成するだけで防げるが実はここに盲点がある。スナップショット後はアドレス使用履歴がホストノード上のTangleでは消去されるが、Permanodeには残っている。
 アドレスを生成した後は必ずTangle Explorerなどでそのアドレスを検索して以前使われた(負の額のtxが存在する)かどうかを最終確認する。

量子計算耐性

 このような署名メカニズムを採択した背景には量子コンピュータ耐性を持たせると言う目的がある。Winternitz one-time signatureという論文でこの署名方法について知ることができるらしい。うーん。分からん。量子コンピュータ耐性があるランポート署名について解説&シェルスクリプトで実装してみたという記事も参考になるかもしれない。

トライト表

tryte.png

参考文献

IOTA公式ライブラリ https://github.com/iotaledger
本記事はSigningという部分。JavaScriptならsigning.js、JavaならSigning.javaから。

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