Seed + Index

暗号通貨ではPrivate keyをハッシュに通して署名をしてたりしますが、その中でも3進数を使うIOTA(アイオータ)は Private Keyのさらなる上層的な文字列"Seed"があります。　詳しい署名の解説は @ABmushi さんのIOTA【技術解説】署名と承認。 - 改訂版をご覧ください。

ともあれIOTAの署名は
Seed + index[n] -> private key -> digest -> address(public address)

といった形で SeedとIndexのコンビネーションで Private keyが変化するのですが、 "SeedとIndexをどうやってくっつけてるのかな" と気になったので調べてみました。

signing.js

var Kerl = require("../kerl/kerl");
var Converter = require("../converter/converter");
var Bundle = require("../bundle/bundle");
var add = require("../helpers/adder");
var oldSigning = require("./oldSigning");
var errors = require("../../errors/inputErrors");

/**
*           Signing related functions
*
**/
var key = function(seed, index, length) {

    while ((seed.length % 243) !== 0) {
      seed.push(0); //Seedが短いとTryte "9"を足しまくる。
    }

    var indexTrits = Converter.fromValue( index );
    var subseed = add( seed.slice( ), indexTrits ); //<-こいつ

でなにやら独自のaddなるものを書いているようでして。
中身はこんな感じになっています。

adder.js

/* copyright Paul Handy, 2017 */

function sum( a, b ) {

    var s = a + b;

    switch( s ) {

        case 2: return -1;
        case -2: return 1;
        default: return s;

    }
}

function cons( a, b ) {

    if( a === b ) {

        return a;

    }

    return 0;
}

function any( a, b ) {

    var s = a + b;

    if ( s > 0 ) {

        return 1;

    } else if ( s < 0 ) {

        return -1;

    }

    return 0;
}

function full_add( a, b, c ) {

    var s_a     =   sum( a, b );
    var c_a     =   cons( a, b );
    var c_b     =   cons( s_a, c );
    var c_out   =   any( c_a, c_b );
    var s_out   =   sum( s_a, c );

    return [ s_out, c_out ];

}

function add( a, b ) {

    var out = new Array( Math.max( a.length, b.length ) );
    var carry = 0;
    var a_i, b_i;

    for( var i = 0; i < out.length; i++ ) {

        a_i = i < a.length ? a[ i ] : 0;
        b_i = i < b.length ? b[ i ] : 0;
        var f_a = full_add( a_i, b_i, carry );
        out[ i ] = f_a[ 0 ];
        carry = f_a[ 1 ];

    }

    return out;

}

どうやら sum,cons,anyというのを駆使して、トリッツ (trits)の配列をごりごりループしております。sum,cons,any はふむふむといった感じなのですが。

前処理

sum(0,0);   // 0
sum(1,-1);  // 0
sum(-1,1);  // 0
sum(0,1);   // 1
sum(1,0);   // 1
sum(0,-1);  // -1
sum(-1,0);  // -1
sum(1,1);   // 2 -> -1
sum(-1,-1); // -2 -> 1

cons(0,0);  // 0
cons(1,-1); // 0
cons(-1,1); // 0
cons(0,1);  // 0
cons(1,0);  // 0
cons(0,-1); // 0
cons(-1,0); // 0
cons(1,1);  // 1
cons(-1,-1);// -1

any(0,0);  // 0
any(1,-1); // 0
any(-1,1); // 0
any(0,1);  // 1
any(1,0);  // 1
any(0,-1); // -1
any(-1,0); // -1
any(1,1);  // 2 -> 1
any(-1,-1);// -2 -> -1

最終的なaddを見てもちんぷんかんぷんです。

add答え


add([0], [0])  //[0]
add([0], [1])  //[1]
add([0], [-1]) //[-1]

add([0,0], [0]) //(2) [0, 0]
add([0,0], [1]) //(2) [1, 0]
add([0,0], [-1]) //(2) [-1, 0]


add([0,0,0], [0,0,0,1,1])  //(5) [0, 0, 0, 1, 1]
add([0,0,0], [0,0,0,1,1])  //(5) [0, 0, 0, 1, 1]
add([0,0,0], [1,0,0,1,1])  //(5) [1, 0, 0, 1, 1]
add([0,0,0], [1,1,0,1,1])  //(5) [1, 1, 0, 1, 1]

add([1,0,0], [0,0,0,1,1])  //(5) [1, 0, 0, 1, 1]

add([1,1,0], [0,0,0,1,1])  //(5) [1, 1, 0, 1, 1]
add([1,1,0], [1,1,-1,1,1]) //(5) [-1, 0, 0, 1, 1]
add([1,1,0], [1,0,-1,1,1]) //(5) [-1, -1, 0, 1, 1]
add([1,1,0], [1,1,0,1,1])  //(5) [-1, 0, 1, 1, 1]
add([1,1,0], [1,1,1,1,1])  //(5) [-1, 0, -1, -1, -1]
add([1,1,0], [1,1,1,0,0])  //(5) [-1, 0, -1, 1, 0]

add([1,1,1], [1,0,-1,1,1]) //(5) [-1, -1, 1, 1, 1]

とりあえずなんか良い感じにごちゃ混ぜてるのかなと諦めかけたのですが。
トリッツから文字列のトライツ(Trytes) に変換してみたら、なんと普通にincrementしているだけでした３進数の足し算は大変なのですね...

/* 実際には index値は３進数でこうやって増えていくので */
fromValue(0) //[]
fromValue(1) //[1]
fromValue(2) //(2) [-1, 1]
fromValue(3) //(2) [0, 1]
fromValue(4) //(2) [1, 1]
fromValue(5) //(3) [-1, -1, 1]

add([-1,1,0,0,1,1,0,-1,1,1,0,1,1,0,0,0,0,-1,1,-1,0,1], [1])
//(22) [0, 1, 0, 0, 1, 1, 0, -1, 1, 1, 0, 1, 1, 0, 0, 0, 0, -1, 1, -1, 0, 1]
//-> "CLFJARY"

add([-1,1,0,0,1,1,0,-1,1,1,0,1,1,0,0,0,0,-1,1,-1,0,1], [-1,1])
//(22) [1, 1, 0, 0, 1, 1, 0, -1, 1, 1, 0, 1, 1, 0, 0, 0, 0, -1, 1, -1, 0, 1]
//-> "DLFJARY"

add([-1,1,0,0,1,1,0,-1,1,1,0,1,1,0,0,0,0,-1,1,-1,0,1], [0,1])
//(22) [-1, -1, 1, 0, 1, 1, 0, -1, 1, 1, 0, 1, 1, 0, 0, 0, 0, -1, 1, -1, 0, 1]
//-> "ELFJARY"

add([-1,1,0,0,1,1,0,-1,1,1,0,1,1,0,0,0,0,-1,1,-1,0,1], [1,1])
//(22) [0, -1, 1, 0, 1, 1, 0, -1, 1, 1, 0, 1, 1, 0, 0, 0, 0, -1, 1, -1, 0, 1]
//-> "FLFJARY"

add([-1,1,0,0,1,1,0,-1,1,1,0,1,1,0,0,0,0,-1,1,-1,0,1], [-1,-1,1])
//(22) [1, -1, 1, 0, 1, 1, 0, -1, 1, 1, 0, 1, 1, 0, 0, 0, 0, -1, 1, -1, 0, 1]
//-> "GLFJARY"

実際のハッシュ関数に通すと

ということでお試しに SEED: IOTATESTONQIITA9IOTATESTONQIITA9THISISONLYFORTESTUSE9PUTSMALLANOUNTOFIOTAHER99999 を使って Index:0 と Index:1 でどのように生成される Private Keyが変化するのか見てみましょう。

> var Kerl = require("../kerl/kerl"); 
> var Converter = require("../converter/converter"); 
> var add = require("../helpers/adder");       
> var seed = "IOTATESTONQIITA9IOTATESTONQIITA9THISISONLYFORTESTUSE9PUTSMALLANOUNTOFIOTAHER99999"
> Converter.trytes(key(seed,0,1))                  
subseed: IOTATESTONQIITA9IOTATESTONQIITA9THISISONLYFORTESTUSE9PUTSMALLANOUNTOFIOTAHER99999              
'OEEITO9SQPBAYCTGR9WLBXRJYGBSOQIL9CMOJDOEOTMBOHHWNSDFHAGIFTRSKBVFIBHKWFV9JTJTGEMWAJQLGKMNIYHCQNFTFHAVLY
E9TTMIGI9XIXDWQHMEMNEZDSTUWJNXGTBSLTE99WIPZYLYIPMVH9OVGOYQXXDLAMB9SURSOAIUSASTNUTMUIQXASXKIMJZBNTQKRACS
DXSDTORFQLUDXYKUHTQSNAZYNLJOZQGSJEMHE9ETXXEJLELNMJYF9DTILBPNORIDXNWEPWPRMBUPBVDBBFGITTTJTUWUVSG9VLAYWCN
XNH9MKQVMIZSOSZCEZZNQJCTLLSOTYIBPWSMWSFFQ9ETPNLBWOKGRUVLQCRALLZCPALLGYCWDNWXTHKSBURDB9GNQ9HCUPZJCOAZPNG
HCDAGTRXOBSUIJZIYAQSWRIAGR9VSQFSAXVZVVAOFTWWQE9HOPNKLKKY9NNCDRGHKWEF9IEKCMXJJSCFTSEDUOXNVUYKSJUFCNTMZUC
RBPA9H9PAJYWYOBL9JIZTROKCAKJCSWGGWWHYUSUAINMX9ATHHMXWQTBDBDZJCFKAUQYRUXBTGE9HSEZXBWFHRDVUWNTSKWIHZLQJOS
SDIHCYHIGKDCLFDPIQQUOLZINLBXZBCSJDFYYSDVMDFDLAERQJQSPVL9CCUTFBPD9MTRGZTZSKXBDHESVZSCFFNFZSWVCNXBQBCJLXE
UACCPEDMCN9FEUCFTXKNOWYTINZJHAVSQGEXDLISCZZUAWVVFKIFQGXZMGYKBMVGCXPIPLZD9FBRCYIHFSGDSJEXZWYWVFQMOFYHUOA
RZPONUOWBEDKSEUM9KWQXBNQLOOPPBUBZITG9N9IXL9BOSHES9DCOLGAWMMVPOQHJXACPLEBWNCLGIJNXTYD9ETZABIFMDRPUOPYAEY
FVCIKZFESBDATKCWBKCOYHPUYNXBZLUHARWRLAGVYKJJ9WBMYCCCNKKQHUKQ9C9PISRRHI9ALVPPKXCBDTHZNOIBLYTWYCQZRXEUEMK
ROCWDIL9BFWNTJWRMXR9YIAWSPHZGQBHG9IHONGXWKFGCMWYHFHYLAVYNIIEQNVTRFYAACLHJKJHKBSTQZDHKSSM9TTNHIDVGXQMVWF
UXZFYKJJFTUHXKVBCXBKDDVAAASPGKWMREDCVTN9PRYYQOOUSPBCGNEYUDT9CKLRQWNTCKQLIIWYFFGCT9YFKEOQNAA9ZPLXSURDERJ
YRJPYVUFFHCVEKTMZLFEBPWRWUWYMYSEJW9DXCNBWAKFYJ9JRPMBNDERLUFOANYAKWIVGYGLAHXIOSWUGLIXWEY9EUFAXNTPZJXHDEU
KZ9CLHOVATSBAXNWRFUQRIAJYZUEYAMAZ9NGVZWXIJXDRKCSTAXDNMEPB9HRYVGHSYWNSCXQWDFMDM9TYYOMBRYORXFZ9HULJGFLLDW
ODPTRYKPWOUHXUZO9MAWNAGINQFRTZVIMLQ9JJTOYFYJZFMKTHLVERBJMPGHIBAKQVVHUYKKHDTGEAWBQRGCSERSEDLHCKROEBMJQAU
VSHVFVQKQAYI9WGADEBF9VACETB9YBX9CPQIE9OORHLPZ9EKYXQC9QDVRJRQ9JZAREANDTNXMAJDSQ9GI9UOVOJRDSDNKHHWSDDMBVV
ANZQFFAVXLOFATIWELMFIQN9HCPMPCBSRZIINHBFTHVAPLJDSTYGNZHNAWOSLFXHJOSIWCSTOUXADSHAWMKDWQFBZSSAYDQIMIDFWBN
KOJOURZWCDITDZGGFZLMOG9DY9NRSBPZYNMPNTWPMQXA9KGDGZCWHXWRIWMJYBJEIQVJZPGAMHEVRBOJKPYITTEAAWUQWGBIACXFFYP
XHMDOWDQMZKHORUHLEPGYXDJEUFXFOKWJIFQAJJSDQDPNKFDUNOUDWPFIWZEVCJLYYTOVZRVKFGWUQENUEEVZBKXPZWRPFZVOZJNDHA
WEPUCX9JUPSHEVMFUSWBCQTNPHR9CKCUAHADOZIDIYJEFHMBWPIOYYEBBMATOCNLDXDAZCFGFKDIECKILAEJBBCXUAPDQGTUCVJKNSA
HMEIPPTVPBPAQQRGDK9EPGMROFWMJZQQPGLQA9TBDNSAWNAWZPCAPUSYARXKCYOUWARCTNSJIDBGKA9GMSOORBQKCYWTZTVGFQZ9MZF
LHVEULJJLFVXB9KHCFHALKF9W'                         
> Converter.trytes(key(seed,1,1))                  
subseed: JOTATESTONQIITA9IOTATESTONQIITA9THISISONLYFORTESTUSE9PUTSMALLANOUNTOFIOTAHER99999              
'SMHAON9JVKWCHCZTIQDRKJUZMHTVFZTDSBWW9HYZVFJQJJRAXYYWMGDXOHQMSQTLFGQQVATYGNNKBLFTAGEGQLYBJTTCHCQFGPDIHN
MG9PZFFI9FQGEUDQTWNCABSLARJVGROCEBBUANNPTQSTBJQPUZFULONNJBUZLK9IGQKBBAYKQYAWL9GJPRAZ99QBTOKBMER9PHX9HO9
O9FYDIWPZPLPOK9PFQOLXRXBILZSEFTI9KHLNDPEUHECNHKNQARLZESEXNMTMCTABDQKWGWQUCGAAROWVPMM9QKPCOTPWKTRAGTJVVA
OW9IESXVYDDTUJXCLBFTHEIYNZFZVOJO9ECHKMUTOQRQFSYBGV9CEGAPSIV9VYVYOHBSTFVAFZYQHMVFZKKPOLQSQRVQEGDHCSNMIKY
XSCRVNLYPCOMNTUNOCSSW9SPIKYPEGIIFQ9ON9WJRQCWCOXWRBSLELTYLMTQT9ONRZVZQ9LKMK9TYLZYXKBZKQQVCDPZHLKEEVPDZPG
B9HBGYMPHKP9UCFV9FFF9LKHH9DTIEKTVYWLOBIJSBEZLKVLAQOQZBAOCRSULMWSQXYHYTAATHRAKMFJLYACZOGLPVPDMYKRSPIOQZT
IGQHHLTAVNF9DTZTAHCTIRHPAMUCSAATOVGBBDMCHKSXIGSQMO9RJMMLDXIGPTRTGEFVDUMAPIHPXLG9SZIIDZRUYECPIXEDEXIHPDY
VRWBKYOZDNFEKVIMMOWSLEWSLKFALWIJDPUGPDTVZZVSPPOUJSPSXOWNSXLFSQYPRZEOUJJLSRQAUYQYKUSVZ9UYCWNVISVK9FW9DFJ
ICMZDOTPMDGLVTDPDKGYDXXKNBFNARGVVFGUU9KOHKM9UOJCXRCXWVFYLWOFPFAQCVHADOYJIVTTRTISLFYDNBRRBFCVKKJLWGGBTC9
V9TFLKTLVCJBLOKBLFWVWELXMHINGYHGSCHCHZHKWMGXTDDRDHH9WFFQJIAENKMTGRGGAOREZHPGNAHRZA9MWHRNERKKGVFIECOV9JB
KNZJWQWNJAKLDXHHZKWHDZQXSSGTXPTQCKWGULSEAWDZBVZ9TYQIQ9ASYXTXCLKVBJ9YUOCEW9KXL9HIZLGOJMSN9Z9MIBXXT9EZTGE
YCDBNMRVMS9OTHVOONMOSSFNMKYNRYMXPEODC9ENHARDYBMQKFKAJKUD9WFPPTWJXVTXECFKXAGFWEXGURABKTLAZHMRKXZNERHSRNM
MUQUZRBLOVBQMRVMOSEQFVIFYTGCXNMRQWIESEJ9FWKMDRIQH9RALUMUEUK9BUKYCYAHODXDICITYJLGZUDFJZUFSWGZPAYNWXNYPEW
OBSAXCOT9WAMNXRQ9ZKR9BKPYIUYOYGNXXMIOZ9LVB9ENCQOOXOIJIYUVSUMONJMBLYVCWHJHQXQBDHFHI9CTOL9NYX9LESMGNXL9RG
BSWCKVWNVRLFLSSQXL9KJMBHJBUROEUB99IGPSMOIABBKQYIWILHICHIEIBVBGJUOMPFYIDSCHBRGTBGGICWBBFD9URKAFAXVCUVLAR
IOTANUXVRCWRWKZTATYVNFAPOYPSLEDNYJAQNZSOPBOBTZEJNEDKEKJ9JSVEVZFYV9KLAGTJDHGCBWGLEQTGYOMGUPZGXIKKOIVVLNC
PO9S9GLCXYVWGFXDJCCNSSWGALJO9C9CNQIOQMZTZZARFINXRACFQYF9LPLWBHZQZRLISEGF9IHPXX9DRYC9JRVYHPRICQWTNRAKZEQ
PTWNQPXHPFEUWD9BKYBBPPGGMQMXREXBSXWWSFO9VZYVT9HHPLLKODOALJOHYATRXUZZKAUCWGIKBNIXNKKZEIPER9AITXZUSWBWQBI
YGGVIBNGZCHEDDFRPBDUOXZJACCWEAVAKJIVOVGDISDQGTGNWBGENMAHQD9LFNHRWOATPQSZK9CLFNDLQHWBQTBTGWDPRCDZ9JUAOMH
ASWOHCGLRATEPUQHJNAFBRPUDBFLMQXGPDRXYSPWIKRMTSASKHUABY9JGCOWZEBHQAHKWGBGTJHMEPQUBMHYWWSQZDOHHRLYJDXFSFO
YXMML99SOEGBXJNWRADQCVAQXGDJMKCMMIXPSTOUZWBMPFDRULVFJLKQLPOPPYHFLJEORCLNGEWAIRQH9KTRGPKTHRPLRQVR9DAVRWX
EIWJETPHVKIYDWSRYIHMMZHCX'

+1 incrementされるだけで期待どうりまったく違う文字列になっておりました
ハッシュ関数のOneway-ness が非常に面白いなぁと最近興味を惹かれているのでいつか SHA3 Keccakの中身をみていく記事書きたいなぁ。

IOTAの署名に使われるSeedのindex値 深ぼってみる

Seed + Index

実際のハッシュ関数に通すと

IOTAの署名に使われるSeedのindex値深ぼってみる