はじめに
前回のVerify編でRekorから返されたtlogの検証を行いましたが、そのうちTrillianに関連する部分はスキップしました。今回はそのTrillianに関しての記事です。Keyless Signing連載の最後です。
- curlでKeyless Signingする (1) - OpenID Connect編
- curlでKeyless Signingする (2) - Fulcio編
- curlでKeyless Signingする (3) - Signed Certificate Timestamp編
- curlでKeyless Signingする (4) - Rekor編
- curlでKeyless Signingする (5) - Verify編
- curlでKeyless Signingする (6) - Trillian編 （本記事）
Rekorはドキュメントで以下のように書いています。
Rekor aims to provide an immutable, tamper-resistant ledger of metadata generated within a software project’s supply chain.
このimmutable, tamper-resistant ledgerの部分はTrillianによって実現されています。まずこのTrilianの概要を見ていきます。
Trillianとは
Trillianは「改ざん不可能なログシステム」を提供できると謳っているOSSであり、概要は以下がわかりやすいです。
Merkel Treeを用いておりCertificate Transparency (CT)で使うためにGoogleにより開発されたようです。CTで使われていることからも分かるようにログシステムの構築に使えます。Trillianでは追加のみ可能で改ざん耐性が高くなっています。Merkle Treeはビットコインなどでも利用されているため知っている人も多いと思います。
以下にドキュメントがありますが、短くまとめられていて簡単に読めるので興味がある人は一読をおすすめします。
Trillianの良い点として「既存のシステムにも簡単に導入できる点」「スケール可能である点」「オープンソースである点」、そして「Googleによって開発されている点」を挙げています。自分で「Googleによって開発されている点」が良いと言うのはなかなか凄いですね。くりぃむしちゅー上田の「だって俺だぜ」を彷彿とさせます。最近だとStadiaの件もあり、いきなりメンテナンスやめちゃうのかなとむしろ不安になりそうではありますが、何にせよRekorではこのTrillianをバックエンドとして採用しています。
Verifiable Data Structures
Trillianにおいてデータをどのように検証するのかについてドキュメントで説明されています。
すべてのログレコードはMerkle Treeのリーフとして追加され、ハッシュ値が計算されます。以下の図だと①-④それぞれのハッシュ値がA, B, D, Fとなっています。
そしてAとBを使って新しくハッシュ値を計算しCを作ります。同様にDとFからGを作ります。同様にして2つのハッシュ値をまとめ上げていき、最終的にTree head hashであるHが作られます。
説明しておいてなんですが単なるMerkle Treeです。知らない人はググれば山ほど出てくるので見てみてください。かくいう自分も忘れてて勉強し直したりしたので記事内でも「正しいか不安」みたいなことを何度も言っています。有識者のフィードバックを得たいというのも記事を公開する目的の一つなので、何か不正確な記述があれば教えていただけると助かります。
Tree head hash
リーフの値が改ざんされればTree head hash（上の図のH）の値が変わるため検知可能です。Tree head hashは他にもTree head, Root hash, Merkle tree hashなどと呼ばれたりもします。
Signed tree head
ですがこのTree head hashが改ざんされたら元も子もないです。リーフの値を改ざんし、Tree head hashを再計算してその値をセットすれば検証を不正に通すことが可能なためです。そこでTrillianではこのTree head hashに秘密鍵で署名します。これをSigned tree hash (STH) と呼びます。
ドキュメントで以下のように書かれているように、クライアントはまずこのSTHをTrillianの公開鍵で検証する必要があります。それまでこのSTHは信頼するべきではないです。
Before trusting a tree head hash from Trillian, clients verify it using a public key that's typically published separately, depending on the application.
この検証によって信頼できるTree head hashを得ることが出来て、次で説明するInclusion proofの計算が意味のあるものになります。というのが自分の理解ですが、Cosignでは現状STHの検証を行っていません。RekorのレスポンスにSTHが含まれたのも最近です。
自分の理解が正しければこれはセキュリティ上よろしくないのではないかと思っています。誰か詳しい人がいたら教えて下さい。
Inclusion proof
クライアントはログレコードを入手後、Trillianにinclusion proofを要求する必要があります。ドキュメントにある以下の例を見てみます。
②のレコードを得たときのinclusion proofの計算は以下です。
- ②のハッシュを計算しBを得る
- Tree head hashを計算するために必要なAとDを要求する
- AとBからCを計算する
- CとDからEを計算する
- Eと別途得たtree head hashを比較する
この検証を通れば②は確かにEをheadとする木に含まれるログレコードであることが分かります。これまた普通のMerkle Treeという感じなので特に難しくはないと思います。ブロックチェーンのSPV（Simplified Payment Verification）もほぼ同じと理解していますが、あまり詳しいわけではないので間違っていたらすみません。
TrillianのドキュメントにはFull auditなどの説明もありますが、Cosignで行われる検証を理解するにはここまでの概要を知っておけば大丈夫です。
検証方法
以下ではKeyless Signingで行われる検証を見ていきます。
Inclusion proof
前回の記事 で見たRekorのレスポンスに inclusionProof というJSONフィールドが実は含まれていました。
$ jq -r '.["24296fb24b8ad77aa55d79859da86ed47339e32d51ad2a8b0640a49652f5cecf0f7eba06d2228e6c"].verification.inclusionProof' tlog.json { "checkpoint": "rekor.sigstore.dev - 2605736670972794746\n581074\nBriWiM7dZr7prBLkpV+jMbqK0pzRvewwGFZfT7aCuIo=\nTimestamp: 1665306326592902697\n\n— rekor.sigstore.dev wNI9ajBFAiAq5Q68+U4+c7f+aIFC7WKsMRcYLHifitu0qLtjKQfCxQIhAPBFWBiz3nzlTazlVeOnM8JXrVwhykS0L1mXCeZ8qn09\n", "hashes": [ "cc1a15893df16a2d596e03a42ac6ce6b98cf8cf86be3910bdd36223833689a85", "afec120963813d296b5820c20f899600540788dff18dc924f4dd557e04bdde45", "608be1e81cb15ac09f18eec8bbe0b37dd26fac8dab63883930a52e072459febd", "78049d975ede977b9e88b2d634edcedfb81f29b4e03dee144e30a52588cfba61", "3ea8b7e6f1db53f92f5079b9d08adc2edeb1be59d3f98b4f3c64c42e3c5669f8", "b2c166358bb5b4463aa261b199eb24678427c3dc59fe6fc2366bebf4d9b47bdd", "32004cfb7313c04b7ba472f660d4be9d5b0833014d53db150e1f77dc8159cdca", "b09bd5323de0eb0c83886b9127f091b712b555e3c67bcea80b5cc3f82b45c32a", "b0e41deda57b9e11b5bb5027004e34c7b22e0f36d1a9fabe4cbbb1019fb8d19c", "7799f078ae51c03583b31b0d6db843451d215f39b2d1adc14fc27abf4d18de98", "1d5eef2fc091b35fa481948f99fd66fcad99ac6ec8935073e093b9bbc238ed59", "26e30b1796943964266f3d0ebe8bb07fb2c4643b4b484aa491e2fd0141b2719b", "19714fb6b7db3e6f6d2036fac7667e78b7faf36b3a6dcddac6d04085df49fd06", "dbf30f96aa4c47533bb57d4bb3e9c8d5dc52c36a66fe3691968bbb858cdb9435", "e4560d2e44c7afdfafb28772f57fc932ab0c7fe5fee196bdd569f895e4227f61" ], "logIndex": 580670, "rootHash": "06b89688cedd66bee9ac12e4a55fa331ba8ad29cd1bdec3018565f4fb682b88a", "treeSize": 581074 }
hashes が上で説明したtree head hashを計算するために必要なinclusion proofです。そしてtree head hashは rootHash として含まれています。今回は 06b89688cedd66bee9ac12e4a55fa331ba8ad29cd1bdec3018565f4fb682b88a になっています。統一するために以下ではroot hashと呼ぶことにします。
ハッシュ計算
TrillianはCTに使われていることから、CTについての仕様を定めたRFC 6962に沿って実装がされています。この中にMerkle Treeのリーフとノードのハッシュ値の計算方法が書かれています。ログレコードが4つの場合の木を書きました。このA-Dがリーフ、hA-hDがリーフハッシュ、hAB, hCD, hABCDがノードです。
RFCは以下です。
Leaf hash
リーフハッシュの計算は以下で定義されています。
MTH({d(0)}) = SHA-256(0x00 || d(0))
要は元のデータの先頭に 0x00 をつけてハッシュ計算すれば良いというだけです。前回の記事で 0x00 をつけて計算したのはこれが理由です。
Node
node hashという表現はRFC内に見つけられなかったのでノードがハッシュ値のことを指すと思うのですが、the hash calculations for leaves and nodesのような表現もあったりして少し怪しいです。
ノードのハッシュ値の計算方法は以下です。kはn未満の最も大きい2のべき乗です。つまり k < n <= 2k を満たします。nが8だったらkは4ということになります。
MTH(D[n]) = SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n]))
難しく見えますが、先頭に 0x01 をつけた上で左側の部分木のroot hashと右側の部分木のroot hashを結合してハッシュ計算しているだけです。つまり上の例で言えば 0x01, hA, hB の順番にバイト列を並べてSHA256でハッシュします。シンプルです。
logIndex
では具体的な実装方法について考えてみます。基本はinclusion proofに含まれるハッシュ値とくっつけてハッシュ計算していけばよいだけですが、inclusion proofを左側に置くのか右側に置くのかは重要です。
リーフが8つの場合で考えてみます。
このうちFのレコードについて考えてみます。root hashを計算するまでの手順は以下です。
- Leaf hashを計算する（
hF） hEを左に繋げてnodeのハッシュ計算をする（hEF）hGHを右に繋げてnodeのハッシュ計算をする（hEFGH）hABCDを左に繋げてnodeのハッシュ計算をする（hABCDEFGH）
これでroot hashを得ることが出来ます。inclusion proofには hE, hGH, hABCD が含まれます。見れば分かる通り、最初はinclusion proofを左に繋げ、次は右、最後は左、という順番になっています。繋げる方向を間違うと当然正しいroot hashは得られません。これをどうやって得るかという話になりますが、これはindexのビットを見れば分かります。indexですが、Aを0としてHを7とすればFは5になります。5を2進数で表すと 101 になります。これはtreeのrootからどちらに進めばよいかを表します。最初は1なので右、次は0なので左、最後は1なので右になります。計算順序的には下からなので最下位ビットから見ていけば良いです。プログラムに落とし込むなら1ビットずつシフトして1とANDを取れば左右が分かります。F（index=5）の 101 を縦に書いた場合の図を載せておきます。
各ビットの値と左右が一致しているのが分かります。二進数と二分木の対応を考えたらそれはそうという感じではありますが、最初 logIndex をビットシフトするプログラムを見たときは少しの間「何で？？」となったので勉強不足で恥ずかしい限りです。大学の方角に足を向けて寝られません。
完全二分木でない場合
上の方法でリーフからroot hashの計算方法が分かったと思いきや実は不十分です。木が完全二分木でない場合があるためです。
概要
ここから先の内容はソースコードから読み取った自分の理解をただ書き記したものなので間違いがある可能性があります。そして若干複雑ですしうまく解説できる気もしません。多分ほとんどの人が読む必要のないパートです。
まずリーフが7の場合を見てみます。ここで木の各階層のことをレベルと呼ぶことにします。Merkle Treeの説明でそう呼ばれていたので倣っています。リーフのハッシュ値はレベル0です。
図を見ると分かるように、Gは結合する相手がいないのでそのまま hG が持ち上がり、 hEF と結合されます。Gのindexは6なので二進数では 110 ですが結合は2回だけですし最下位ビットの0を見て右と結合すると判断してしまうと誤りです。そのため、indexを見て結合する方向を決めるべきレベルと、右側の部分木が存在しないために常に左側と結合するべき（または結合が不要な）レベルを区別する必要があります。前者を inner 、後者を outer と呼ぶことにします。 outer は勝手な造語です。
一旦リーフが8の場合を考え直してみます。このときGに着目すると、Level 1までは右側の部分木が存在し得るので左右の判定が必要ですが、Level 2以降は常に左側の部分木しかないため左右の判定をせずに結合可能です。
つまりGに着目すると inner = 1, outer = 2 になるということです。Fに着目すれば inner = 2, outer = 1 になります。下の図ではリーフハッシュの計算はもう省いていますが基本は上と同じです。
改めて言うと、 inner は右側に部分木があるレベル帯を指します。FはLevel 0とLevel 1の時点ではどちらも右側に部分木が存在しています（ hGH を頭とする部分木）。そのため2つのレベルで右側に部分木があるということで inner = 2 となっています。このとき、結合する方向は関係ないです。 hF は hE を左側に結合していますが、 inner の計算には影響しません。
リーフが8の場合は完全二分木だったので、 inner などややこしいことを言わずとも計算可能でした。そうではないリーフが7の場合に戻り、再びGに注目します。Hは存在しませんがわかりやすさのために点線で書いています。
このとき、 hG の右側に部分木は存在しないため inner = 0 になります。逆に outer は3となります。この inner のレベルまでは上のindexをビットシフトしていく方法で左右の判定をして結合し、 outer のレベルでは左側と結合・もしくは結合しない、という処理を行うことで完全二分木ではない場合にも対応可能になります。
outer における
- 左側と結合する
- 結合しない
の判定ですが、これは簡単で同様にindexのビットを見ればよいです。ビットが立っている場合は左側と結合、立っていない場合は結合不要になります。結合が不要な場合はそもそも結合相手のハッシュ値がinclusion proofに含まれないので、もっと簡単にビットが立っている回数分だけ左側と結合すれば良いということになります。
Gのindexは6で 110 なので、outerレベルにおいて立っているビットは2つです（上の図の緑のところ）。つまり2回左側と結合すればよいです（ hEF と hABCD との結合）。0の部分は結合不要です（ hG はそのまま hG ）。途中から面倒になって結合と言っていましたが、結合したあともちろんハッシュ計算が必要です。この常に左側と結合する回数のことを border と呼ぶことにします。これはソースコード上の変数名から借用しているのですが、 border という名前的にもう少し違うイメージなのかもしれません。自分ではうまく視覚化出来なかったので一旦これで勘弁してください。
ここまでで inner と border さえ求まればroot hashが計算できるようになりました。では inner の求め方を考えます。先ほど説明したように右側に部分木が存在するかどうか、なので木における一番右側のリーフのパスに着目すれば求められそうです。言葉だと分からないと思うので、図を見てみます。リーフが6の木を考えます。このとき、右端のリーフはFになります。これをrootから辿ると右→左→右になります。
ではEに着目します。Eをrootから辿ると右→左→左になります。このとき、図ではLevel 1→0の時点でFと分離します。このFとパスが重ならなくなった地点までのレベルが inner になります。この図におけるEの inner は1ということになります。右端のリーフであるFのパスと分離してしまったので、Level 1以下はEのパスより右側に部分木が存在します。
同じ木でDに着目してみます。図を見れば分かるようにLevel 3の時点でいきなり袂を分かっています。つまりDのパスにおいては常に右側に部分木が存在するため inner = 3 になります。
こうして inner を求めることができれば、 inner より上のレベルの中で立っているビットを数えれば border は簡単に求まります。
計算方法
上では図での概要理解に努めていましたが、ここでは実際のプログラムを見つつ計算方法を確認します。Merkle Tree用のライブラリが提供されているのでそちらを参照しています。
merkle/verify.go at 8e426287c6b7195f0a95f3b4fb1c92aa6a619ff0 · transparency-dev/merkle · GitHub
まず inner を計算します。
func innerProofSize(index, size uint64) int { return bits.Len64(index ^ (size - 1)) }
index と size-1 でXORをとってビットの長さを計算しています。ここについてコメントで以下のように説明があります。
The splitting point between them is where paths to leaves |index| and |size-1| diverge.
これは上で説明したとおりです。 size - 1 は一番右側のリーフになるので、 index と size - 1 のXORを取り最上位のビットを探すことで一番最初にこの2つのパスが分かれたレベルを探しています。
例えばリーフが6の例でEに着目すると、 size - 1 が5になってEのindexである4とXORを取ると 001 になります。最初の二回は同じパスで最後の一回が異なるというのを先程図で確認しました。001 に対して bits.Len64 は1を返します。 bits.Len64 の説明は以下です。
Len64 returns the minimum number of bits required to represent x; the result is 0 for x == 0.
サンプルでは以下のようになっています。
Len64(0000000000000000000000000000000000000000000000000000000000001000) = 4
この数値を表すための最小の表現は 1000 なので長さは4ということです。言い換えれば最初に現れる1を探していると言えると思います。そしてしつこいですが言い換えると最初にパスが分離するレベルを探しています。
次に border を計算します。
border := bits.OnesCount64(index >> uint(inner))
これはもう特に難しくないと思います。indexを inner 分ビットシフトすると outer が得られます。この outer のビットの中の1の数をカウントしています。上図の例で言えば E (=100) から inner (=1) ビットシフトすると 10 になります。 bits.OnesCount64 はポップカウントでビットの立っている数を返すため、この例では1が返ります。実際に outer における結合回数は上の図で見たとおり一度だけです。
プログラム的には最初 inner のレベルにおいては左右の判断が必要だが、そこを抜けて outer のレベルでは border の回数分だけ常に左と結合するだけで良い、ということです。
コードは以下です。
merkle/verify.go at 8e426287c6b7195f0a95f3b4fb1c92aa6a619ff0 · transparency-dev/merkle · GitHub
res := chainInner(hasher, leafHash, proof[:inner], index) res = chainBorderRight(hasher, res, proof[inner:])
受け取ったinclusion proofのうち、 proof[:inner] は chainInner を呼び出し proof[inner:] は chainBorderRight を呼び出しています。名前やコメントからしても inner より上のレベルに行った場合は常に結合相手に対して右側にいる（右の部分木はない）と仮定して結合しているのが分かると思います。
// chainBorderRight chains proof hashes along tree borders. This differs from // inner chaining because |proof| contains only left-side subtree hashes. func chainBorderRight(hasher merkle.LogHasher, seed []byte, proof [][]byte) []byte { for _, h := range proof { seed = hasher.HashChildren(h, seed) } return seed }
ソースコードを見ても proof (=h) は常に左側に置いて結合しています。
なるべく図を使って説明してきましたが、自分もふわっとした理解なせいもあって意味不明だったかもしれません。以上で概要の説明は終わりです。
手動で試す
Signed tree head (STH)
上でも述べましたが、CosignではこのSTH署名検証は現在（v1.13.0時点）行われていません。しかし以下のinclusion proofの計算は行っており、うーん？？？？？となっています。root hashが信頼できないのにinclusion proofの計算する意味あるのか？！という気持ちです。
Inclusion proof
まずはリーフハッシュの計算を行います。これは実は前回の記事でも行いましたが、もう一度行っておきます。JSONの形を再度確認します。
$ jq -r '.["24296fb24b8ad77aa55d79859da86ed47339e32d51ad2a8b0640a49652f5cecf0f7eba06d2228e6c"]' tlog.json { "body": "eyJhcGlWZXJzaW9uIjoiMC4wLjEiLCJraW5kIjoiaGFzaGVkcmVrb3JkIiwic3BlYyI6eyJkYXRhIjp7Imhhc2giOnsiYWxnb3JpdGhtIjoic2hhMjU2IiwidmFsdWUiOiI2OTM5YmQxZmI0Y2YxZTgxMGVhZmNjYmY4YzY5OTI3N2NhYWU3MzY0NGNhNTlkYjFiMDhkZGE0NGY1NTg3ZjA1In19LCJzaWduYXR1cmUiOnsiY29udGVudCI6Ik1FWUNJUUNpWXZqc3BwOTVYZjNaZ3FJNTAzcTdlVUZzTjdmdVFLU3dXNFcwdHF0VERBSWhBUEJQUEk4SGREamkwUzU5U05RR1ZldUZuN0JoQTk2NFEzWi96enQ5d0lCaCIsInB1YmxpY0tleSI6eyJjb250ZW50IjoiTFMwdExTMUNSVWRKVGlCRFJWSlVTVVpKUTBGVVJTMHRMUzB0Q2sxSlNVTnZWRU5EUVdsbFowRjNTVUpCWjBsVlJ6STJRV0V3YVN0TVVVcDNUMEZWUTJwWWJYTTRlRzFzV0U1cmQwTm5XVWxMYjFwSmVtb3dSVUYzVFhjS1RucEZWazFDVFVkQk1WVkZRMmhOVFdNeWJHNWpNMUoyWTIxVmRWcEhWakpOVWpSM1NFRlpSRlpSVVVSRmVGWjZZVmRrZW1SSE9YbGFVekZ3WW01U2JBcGpiVEZzV2tkc2FHUkhWWGRJYUdOT1RXcEplRTFFUVRWTlJHY3hUbFJGZWxkb1kwNU5ha2w0VFVSQk5VMUVhM2RPVkVWNlYycEJRVTFHYTNkRmQxbElDa3R2V2tsNmFqQkRRVkZaU1V0dldrbDZhakJFUVZGalJGRm5RVVZyTUVKdGFqRkJiek42UTBwbWRXVkdkMnd4YkRWNGJIWjNhMDkyZVRkTldVOUJObUVLYjFGR2FFMWxhRWd2ZFZCSmVURkJaMEl5TDFKdlVYUldVMWxEVFhwcFZrSlBSWGRJWWtwWEsyUlpkVWhWVGpWck56WlBRMEZWV1hkblowWkRUVUUwUndwQk1WVmtSSGRGUWk5M1VVVkJkMGxJWjBSQlZFSm5UbFpJVTFWRlJFUkJTMEpuWjNKQ1owVkdRbEZqUkVGNlFXUkNaMDVXU0ZFMFJVWm5VVlY0YTJoa0NtUklhR2hUTTNKUmJqSnJZV2hwVUZobllXbDFZVWc0ZDBoM1dVUldVakJxUWtKbmQwWnZRVlV6T1ZCd2VqRlphMFZhWWpWeFRtcHdTMFpYYVhocE5Ga0tXa1E0ZDBsQldVUldVakJTUVZGSUwwSkNXWGRHU1VWVFlUSTFlR1ZYV1hsT2FrNUJXakl4YUdGWGQzVlpNamwwVFVOM1IwTnBjMGRCVVZGQ1p6YzRkd3BCVVVWRlNHMW9NR1JJUW5wUGFUaDJXakpzTUdGSVZtbE1iVTUyWWxNNWMySXlaSEJpYVRsMldWaFdNR0ZFUTBKcFoxbExTM2RaUWtKQlNGZGxVVWxGQ2tGblVqaENTRzlCWlVGQ01rRkJhR2RyZGtGdlZYWTViMUprU0ZKaGVXVkZia1ZXYmtkTGQxZFFZMDAwTUcwemJYWkRTVWRPYlRsNVFVRkJRbWMzZGpBS2JYTkpRVUZCVVVSQlJXTjNVbEZKWjBwaFMyWnJVM3BIZVZKek1HZzNNSFUyVVdSVVVubEpOVTlCVm1vMFV6TkZhRkpxWkVGRlRVRk1ZalJEU1ZGRGNBcHFWSGR0ZFU1MmVTOU9SR0k0Y1VSYVNUbEVkVXhRVUdkWFpsRnJOR05STUU4eVlscDBiRE0wVWtSQlMwSm5aM0ZvYTJwUFVGRlJSRUYzVG05QlJFSnNDa0ZxUlVGNGJGbEZja3RtTW5ORVZHUlBZek55YWtGVldFcEpUbkZhZUdwck1taFBVelJOVkVrMmRFNU9VbnB5ZVVKREswRkpiVTF2Tm5KQmJFMTRkMjBLWjAxV2VVRnFRamgyTWs1bmRIVXpkamd6VkRCSmF5dEJRVkpYWjNwS1VXTlVkWEYzYWpsd04yeGtSM1ZUYTJ3ME0waFVPVXRWU21aaFNYWktNalJsUXdwNlZXbzRaVmRWUFFvdExTMHRMVVZPUkNCRFJWSlVTVVpKUTBGVVJTMHRMUzB0Q2c9PSJ9fX19", "integratedTime": 1665305714, "logID": "c0d23d6ad406973f9559f3ba2d1ca01f84147d8ffc5b8445c224f98b9591801d", "logIndex": 4744101, "verification": { "inclusionProof": { "checkpoint": "rekor.sigstore.dev - 2605736670972794746\n581074\nBriWiM7dZr7prBLkpV+jMbqK0pzRvewwGFZfT7aCuIo=\nTimestamp: 1665306326592902697\n\n— rekor.sigstore.dev wNI9ajBFAiAq5Q68+U4+c7f+aIFC7WKsMRcYLHifitu0qLtjKQfCxQIhAPBFWBiz3nzlTazlVeOnM8JXrVwhykS0L1mXCeZ8qn09\n", "hashes": [ "cc1a15893df16a2d596e03a42ac6ce6b98cf8cf86be3910bdd36223833689a85", "afec120963813d296b5820c20f899600540788dff18dc924f4dd557e04bdde45", "608be1e81cb15ac09f18eec8bbe0b37dd26fac8dab63883930a52e072459febd", "78049d975ede977b9e88b2d634edcedfb81f29b4e03dee144e30a52588cfba61", "3ea8b7e6f1db53f92f5079b9d08adc2edeb1be59d3f98b4f3c64c42e3c5669f8", "b2c166358bb5b4463aa261b199eb24678427c3dc59fe6fc2366bebf4d9b47bdd", "32004cfb7313c04b7ba472f660d4be9d5b0833014d53db150e1f77dc8159cdca", "b09bd5323de0eb0c83886b9127f091b712b555e3c67bcea80b5cc3f82b45c32a", "b0e41deda57b9e11b5bb5027004e34c7b22e0f36d1a9fabe4cbbb1019fb8d19c", "7799f078ae51c03583b31b0d6db843451d215f39b2d1adc14fc27abf4d18de98", "1d5eef2fc091b35fa481948f99fd66fcad99ac6ec8935073e093b9bbc238ed59", "26e30b1796943964266f3d0ebe8bb07fb2c4643b4b484aa491e2fd0141b2719b", "19714fb6b7db3e6f6d2036fac7667e78b7faf36b3a6dcddac6d04085df49fd06", "dbf30f96aa4c47533bb57d4bb3e9c8d5dc52c36a66fe3691968bbb858cdb9435", "e4560d2e44c7afdfafb28772f57fc932ab0c7fe5fee196bdd569f895e4227f61" ], "logIndex": 580670, "rootHash": "06b89688cedd66bee9ac12e4a55fa331ba8ad29cd1bdec3018565f4fb682b88a", "treeSize": 581074 }, "signedEntryTimestamp": "MEUCIHYBg6VLKjd5hnjRj34+mKp2KWObE4aCGFsPaWGsxlHgAiEA5JtI46YQE67uQBp1bbnUmO84fe90NKsusHJk1Vxle28=" } }
この body をBase64デコードしたものの先頭に 0x00 をつけてハッシュすればよいのでした。
$ jq -r '.["24296fb24b8ad77aa55d79859da86ed47339e32d51ad2a8b0640a49652f5cecf0f7eba06d2228e6c"].body' tlog.json | base64 -d | jq . > body.json $ (echo -ne "\x00"; cat body.json) | sha256sum aa55d79859da86ed47339e32d51ad2a8b0640a49652f5cecf0f7eba06d2228e6c
ということでリーフハッシュを得ました。あとはinclusion proofと繋げてハッシュ計算をしていきます。inclusionProof の中身だけ proof.json などに書き出しておきます。
$ jq -r '.["24296fb24b8ad77aa55d79859da86ed47339e32d51ad2a8b0640a49652f5cecf0f7eba06d2228e6c"].verification.inclusionProof' tlog.json > proof.json
まず inner を計算しますが、このためにはリーフの数が必要です。これは treeSize に入っています。今回は581074です。これから1引いて一番右端のリーフとし、logIndex とXORを取ります。logIndex は inclusionProof 内にるのでこれを使います。ちなみに inclusionProof の外側にも logIndex がありますが、そちらではないです。自分はまさか2つあると思わずに最初外側の値を使っていて時間を無駄にしました（同じ名前にするのややこしいのでやめて欲しい）。今回の logIndex は580670です。
ではXORを取ります。
$ echo $((580670^(581074-1))) 495 $ echo -n 'obase=2;495' | bc 111101111
111101111 の長さは9なので inner = 9 であることが分かります。次に border ですが、 logIndex を9ビット右にシフトして立っているビットを数えれば良いです。
$ echo $((580670>>9)) 1134 $ echo 'obase=2;1134' | bc | grep -o 1 | wc -l 6
ということで border = 6 でした。つまりLevel 9までは logIndex のビットを見て左右を判定し、それ以降は6回左側と結合すればよいです（自分が常に右側にいる）。ちなみに inner と border の合計数はハッシュ計算する回数と一致するため、 hashes の長さと一致しなくてはなりません。
$ jq -r ".hashes[]" proof.json | wc -l 15
ということで確かに inner = 9 と border = 6 の合計と一致しています。この検証もCosign内で行われています。
inclusion proofの1つ目のハッシュ値を見てみます。
$ jq -r ".hashes[0]" proof.json cc1a15893df16a2d596e03a42ac6ce6b98cf8cf86be3910bdd36223833689a85
これを上で得たリーフハッシュに対して左右どちらに結合すれば良いのかを調べます。繰り返しになりますが、これは logIndex (=580670) のビットを見れば判定可能です。
$ echo 'obase=2;580670' | bc 10001101110000111110
logIndex は 10001101110000111110 なので最下位ビットが0であることから最初は木の左側にあることが分かります。つまり cc1a15893df16a2d596e03a42ac6ce6b98cf8cf86be3910bdd36223833689a85 を右側において結合すれば良さそうです。
$ echo -ne "\x01" > a $ echo -n a55d79859da86ed47339e32d51ad2a8b0640a49652f5cecf0f7eba06d2228e6c | xxd -r -p >> a $ echo -n cc1a15893df16a2d596e03a42ac6ce6b98cf8cf86be3910bdd36223833689a85 | xxd -r -p >> a $ sha256sum a 95ada66a7d8ca568794e9a2c364a02d07c6550bca5b229bd9670ae7ffaa781e4 a
ということでハッシュ値を得ました。あとは inner のLevel 9まで同様に繰り返し計算していくだけです。さすがに面倒だったのでシェルスクリプトを書いたのですが、それだったらもはや手動じゃないし普通にプログラム書けよって言われそうだったので「え！！手動でinclusion proofの計算を？！」「出来らぁっ！」ということで気合で手でやりました。自分は何と戦っているのでしょうか。
# Level 1: inclusion proofを左に置いて結合 $ (echo -ne "\x01"; \ echo -n afec120963813d296b5820c20f899600540788dff18dc924f4dd557e04bdde45 | xxd -r -p; \ echo -n 95ada66a7d8ca568794e9a2c364a02d07c6550bca5b229bd9670ae7ffaa781e4 | xxd -r -p) \ | sha256sum 8e7c52b18e3d45f721b6f3e5acaa26d1c7fcabad46b6d2abe5f51bcd76470ce6 - # Level 2: inclusion proofを左に置いて結合 $ (echo -ne "\x01"; \ echo -n 608be1e81cb15ac09f18eec8bbe0b37dd26fac8dab63883930a52e072459febd | xxd -r -p; \ echo -n 8e7c52b18e3d45f721b6f3e5acaa26d1c7fcabad46b6d2abe5f51bcd76470ce6 | xxd -r -p) \ | sha256sum 7f1f5967fc5b94dc023629c148b8e8d10e5c8272e48e529a0dd81442cb26777a - # Level 3: inclusion proofを左に置いて結合 $ (echo -ne "\x01"; \ echo -n 78049d975ede977b9e88b2d634edcedfb81f29b4e03dee144e30a52588cfba61 | xxd -r -p; \ echo -n 7f1f5967fc5b94dc023629c148b8e8d10e5c8272e48e529a0dd81442cb26777a | xxd -r -p) \ | sha256sum 884387bd3e198b5465904450c84c3007ba5a2f1d31a63161af09d61515663b62 - # Level 4: inclusion proofを左に置いて結合 $ (echo -ne "\x01"; \ echo -n 3ea8b7e6f1db53f92f5079b9d08adc2edeb1be59d3f98b4f3c64c42e3c5669f8 | xxd -r -p; \ echo -n 884387bd3e198b5465904450c84c3007ba5a2f1d31a63161af09d61515663b62 | xxd -r -p) \ | sha256sum 380a408e0d035c4a24b16d2af3935b9a3f70593ee8bf53b0e8050ef8e6ef20d8 - # Level 5: inclusion proofを左に置いて結合 $ (echo -ne "\x01"; \ echo -n b2c166358bb5b4463aa261b199eb24678427c3dc59fe6fc2366bebf4d9b47bdd | xxd -r -p; \ echo -n 380a408e0d035c4a24b16d2af3935b9a3f70593ee8bf53b0e8050ef8e6ef20d8 | xxd -r -p) \ | sha256sum abc55c11d2749eaa8e65c3f97f7a338fd64a4998f4991fc946dd4896492b990d - # Level 6: inclusion proofを右に置いて結合 $ (echo -ne "\x01"; \ echo -n abc55c11d2749eaa8e65c3f97f7a338fd64a4998f4991fc946dd4896492b990d | xxd -r -p; \ echo -n 32004cfb7313c04b7ba472f660d4be9d5b0833014d53db150e1f77dc8159cdca | xxd -r -p) \ | sha256sum e31926c9c9f415bc6f28b0af9e903ad506968abed079b9f318fe08bd70c8ba61 - # Level 7: inclusion proofを右に置いて結合 $ (echo -ne "\x01"; \ echo -n e31926c9c9f415bc6f28b0af9e903ad506968abed079b9f318fe08bd70c8ba61 | xxd -r -p; \ echo -n b09bd5323de0eb0c83886b9127f091b712b555e3c67bcea80b5cc3f82b45c32a | xxd -r -p) \ | sha256sum 53fd8cdcb799bc77ddcb0b7009f7d9757ae2857096624fbfccfa9f0ba6f1c510 - # Level 8: inclusion proofを右に置いて結合 $ (echo -ne "\x01"; \ echo -n 53fd8cdcb799bc77ddcb0b7009f7d9757ae2857096624fbfccfa9f0ba6f1c510 | xxd -r -p; \ echo -n b0e41deda57b9e11b5bb5027004e34c7b22e0f36d1a9fabe4cbbb1019fb8d19c | xxd -r -p) \ | sha256sum a444a21f62222f79e53beb8951bb248fda73b22f9e244601aaa31cbbd1954a83 -
そして inner を抜けたらあとは border の回数分（今回は6回）、inclusion proofを左に置いて右から結合すればよいだけです。
# Level 9: inclusion proofを左に置いて結合 $ (echo -ne "\x01"; \ echo -n 7799f078ae51c03583b31b0d6db843451d215f39b2d1adc14fc27abf4d18de98 | xxd -r -p; \ echo -n a444a21f62222f79e53beb8951bb248fda73b22f9e244601aaa31cbbd1954a83 | xxd -r -p) \ | sha256sum 485a3c9bbdb8efd1a85daeb8b8539d75111257c3718c254ff5e1ced1b1ab2499 - # Level 10: inclusion proofを左に置いて結合 $ (echo -ne "\x01"; \ echo -n 1d5eef2fc091b35fa481948f99fd66fcad99ac6ec8935073e093b9bbc238ed59 | xxd -r -p; \ echo -n 485a3c9bbdb8efd1a85daeb8b8539d75111257c3718c254ff5e1ced1b1ab2499 | xxd -r -p) \ | sha256sum 8cd88d2eba75f8b4925e3e767475a143495e93bc371c72d811a65a0bcda9e5f0 - # Level 11: inclusion proofを左に置いて結合 (echo -ne "\x01"; \ echo -n 26e30b1796943964266f3d0ebe8bb07fb2c4643b4b484aa491e2fd0141b2719b | xxd -r -p; \ echo -n 8cd88d2eba75f8b4925e3e767475a143495e93bc371c72d811a65a0bcda9e5f0 | xxd -r -p) \ | sha256sum 1652f0d5a5786edf686fd9542aa894f61a0fe8316238ca6181f76d426d654171 - # Level 12: inclusion proofを左に置いて結合 $ (echo -ne "\x01"; \ echo -n 19714fb6b7db3e6f6d2036fac7667e78b7faf36b3a6dcddac6d04085df49fd06 | xxd -r -p; \ echo -n 1652f0d5a5786edf686fd9542aa894f61a0fe8316238ca6181f76d426d654171 | xxd -r -p;) \ | sha256sum 97b9f5fab7df4afe0bbeec30bf4fd8321f2db603aa7e494b007c790bb8f1ea33 - # Level 13: inclusion proofを左に置いて結合 $ (echo -ne "\x01"; \ echo -n dbf30f96aa4c47533bb57d4bb3e9c8d5dc52c36a66fe3691968bbb858cdb9435 | xxd -r -p; \ echo -n 97b9f5fab7df4afe0bbeec30bf4fd8321f2db603aa7e494b007c790bb8f1ea33 | xxd -r -p;) \ | sha256sum a894dba1e82a44050d98c376ec7eb1856cd92f0a2dc669a1e6ec6a3b0b213db6 - # Level 14: inclusion proofを左に置いて結合 $ (echo -ne "\x01"; \ echo -n a894dba1e82a44050d98c376ec7eb1856cd92f0a2dc669a1e6ec6a3b0b213db6 | xxd -r -p;) \ | sha256sum 06b89688cedd66bee9ac12e4a55fa331ba8ad29cd1bdec3018565f4fb682b88a -
ということで 06b89688cedd66bee9ac12e4a55fa331ba8ad29cd1bdec3018565f4fb682b88a が得られました。これは確かに rootHash の値と一致しています。
これでようやくinclusion proofの計算ができました。
まとめ
何とかRekorのバックエンドとして使われているTrillianもそこそこ理解することが出来ました。これで長かったKeyless Signing連載も終了です。さすがに長過ぎて誰も読んでないと思うので、いつか概要版でも書くかもしれません。
しかしSTHを検証せずにinclusion proof計算するの意味がない気がしてならなくて夜も眠れません。
