ブロックチェーンのユースケースの1つに、モノの輸送履歴をトラッキングするサプライチェーン・トレーサビリティが挙げられます。 誰もが自由にアクセス可能な台帳に、モノの輸送を記録することで、企業や国をまたぐ輸送の記録を誰もがいつでも自由に検証でき、 オープンなブロックチェーンのユースケースの1つとして適しています。 一方、ブロックチェーンに記録可能なデータサイズは限定的で、データサイズを増やすことが可能だったとしても、 分散ネットワークにおけるデータの増加は参加ノードの運用コストの上昇とトレードオフになります このため、大量のモノの輸送をブロックチェーンに記録する場合、データのトレースが証明可能な状態でいかにコンパクトにするかが、 ブロックチェーンのスループットやディスクスペースにおいて重要な課題となります。 本節では、これらの課題に対処するためにTapyrusで採用している拡張プロトコルについて紹介します。

1 トラッキングトランザクション

UTXO 型のブロックチェーンである Tapyrus では、トランザクションのインプットで既存の有効な UTXO を消費して(送金元、送金の原資)、トランザクションのアウトプットで新しい UTXO を生成(送金先)します。 トレーサビリティのようなユースケースでは、インプットをモノの輸送元、アウトプットを輸送先として表現することが可能です。

トラッキングペイロード トラッキングトランザクションは、送信先のアウトプットに加えて、 輸送するモノの情報を記録するトランザクションペイロードを持つアウトプットを余分に1つ保持します。 このアウトプットが存在することで、このトランザクションがトラッキングトランザクションであることを示します。 トラッキングペイロードのアウトプットは OP_RETURNを使用した以下の形式になります：

OP_RETURN < Tracking Payload >

トラッキングペイロードは Table #1 のデータで構成されます：

フィールド サイズ 内容
マーカー 2バイト 常に 0x5450 。トラッキングプロトコル = TP を表す Hex 値
バージョン 1バイト 現在は 0x01
ペイロードサイズ CompactSize ペイロードのサイズ
ペイロード 可変 輸送するアイテムの一意な識別子で作成されたアキュムレーター値(3. アキュムレーターを使用したデータの圧縮 を参照)

Table #1: トラッキングペイロードのデータ

2 トレースルール

トラッキングにおける、輸送元と輸送先は以下のルールにより決定します：

輸送元 輸送元はトランザクションインプットで表現され、次のルールにより決定

  • 輸送を新規開始する場合
    • トランザクションインプットの内、先頭のインプットを輸送元のアドレスとします
  • 輸送の途中である場合
    • インプットが参照する UTXO の内、トラッキングペイロードが適用される UTXO をすべて輸送元のアドレスとします

輸送先 輸送先はアウトプットの内、トラッキングペイロードのアウトプットの直後にセットされているUTXO を輸送先のアドレスと規定します。 なお、1つのトラッキングトランザクションに対して、複数の輸送先を定義することを可能とします。 これはアウトプットにトラッキングペイロードが複数定義できることを意味します。各ペイロードの適用先はその直後の UTXOとします。

消費 インプットが参照する UTXO に適用されたトラッキングペイロードに包含されるモノのうち、 輸送先のアドレスが指定されないものは消費されたものと規定します。

3 アキュムレータを使用したデータの圧縮

トラッキングペイロードには、輸送するモノの識別子を単純に記録するのではなく、識別子を含むアキュムレーターの値が記録されます。 これは一意の識別子をそのまま登録すると、その識別子の数に比例してペイロードのデータサイズが増えるのを避けるためです。 アキュムレーターとは、任意の数のアイテムの追加、削除かつ、任意のアイテムがそのアイテムに含まれているかを照会が可能であるものの、 アキュムレーター内に追加されたアイテムのリストは取得できないという特性を持つアルゴリズムです。

このようなアルゴリズムには、ハッシュの二分木を利用するアルゴリズムや、 RSA暗号を利用するアルゴリズム、 多項式コミットメントを利用するアルゴリズムなどさまざまなものがあります。 Tapyrus のトラッキングプロトコルv1では、この内 RSA 暗号を利用した RSA アキュムレーターを使用します。 これは RSA アキュムレーターの以下の特性を考慮した結果です：

  • アキュムレーターにどれだけアイテムを追加してもアキュムレーターのサイズは一定である。
  • アキュムレーターに対してデータを追加、削除するにあたってアイテムの順番を考慮しなくて良い。

4 RSA アキュムレーター

利用するRSAアキュムレーターの概要は以下のとおりです。

セットアップ

最初に以下のセットアップを行い、RSAアキュムレーターを初期化します：

  1. 巨大な素数pとqを選択し、N = p * qを計算する
  2. NをモジュラスとしたRSA群を生成する
  3. RSA群のジェネレーターgを選択する
  4. アキュムレーターを初期化する。A0 = g

※ Nの合成数が分かるとチートが可能になるため、これはTrusted Setupとなります。

要素の追加

要素xをアキュムレーターに追加する場合は、要素xのハッシュ値x’ = Hp(x)を計算します。 ここでHp()は素数を出力するハッシュ関数です。このハッシュ値x’を使って以下のようにアキュムレーターを更新します。

$A1 = g^{x’} \mod N$

A1がA0に要素xを追加したアキュムレーター値になります。

要素のメンバーシップ証明

A1にxが含まれていることを証明したい場合、その包含証明（witness）はA0となります。

A0とxが提供された検証者は、xのハッシュ値（x’）を計算し、$A0^{x’} = A1$が成立するか検証します。 これが成立する場合、xはA1に含まれています。

アキュムレーターの計算は冪剰余の計算であるため、アキュムレーター値と要素の値から包含証明を計算することは不可能です。 そのため、包含証明を提供するProof Providerはすべての要素のデータを保持している必要があります。

要素の削除

アキュムレーターに含まれる要素xを削除する場合、xと削除後のアキュムレーター値を提供します。A1からxを削除する場合、 xとA0を提供し、$A0^{x’} = A1$が成立する場合、A0はxが削除された後のアキュムレーターであることが保証されます。

説明ではシンプルにA0とA1しか登場しませんが、A1の上に多数の要素を追加した後でも同様に機能します。

要素の非メンバーシップ証明

要素がアキュムレーター内に含まれていないことは、ベズー係数を用いた非包含証明を提供することで可能です。

たとえば、ハッシュ値が3, 5, 11の３つの要素を持つアキュムレーター$A = g^{3 \cdot 5 \cdot 11} \mod N$に対して、 ハッシュ値が７の要素の非メンバーシップ証明を行う場合、

  1. a * 7 + b * (3 * 5 * 11) = 1を満たすベズー係数を求めます。この場合、a = -47, b = 2となります。
  2. 算出したベズー係数を用いて非包含証明$(g^a, b) = (g^{-47}, 2)$を計算します。
  3. 非包含証明を提供された検証者は、$g^{a \cdot x} \cdot A^b = g^{-47 \cdot 7} \cdot g^{3 \cdot 5 \cdot 11 \cdot 2} = g^{-329 + 330} = g^1$が成立するかチェックします。

その他、複数の要素のバック削除や、検証者の計算コストを抑えるためのProof of Exponentiationなどの最適化をサポートしています。

これらのアキュムレーター値がトラッキングペイロードに含まれています。

ユースケース

追跡情報を記録する

以下のシナリオを考えてみましょう。

  • カカオ農家の Ivan Farm がカカオ豆をカカオ加工業者であるA社、B社、C社へ送りたい。
  • それぞれへ送るカカオは識別子 A, B, Cが振られている。3社に送るには輸出業者である Dave Trade を経由して送る必要がある。
  • Dave Trade は輸送の都合により、初めに A社, B社に送る。その後、別便で C社 へと送る。

1. Ivan が Dave に荷物 A, B, C を送る

発行されるトランザクションは、

  • インプット
    1. Ivan の utxo
  • アウトプット
    1. ‘A’, ‘B’, ‘C’ を含むトラッキングペイロード
    2. Dave に向けた output。nValue は dust_limit の値
    3. Ivan へのお釣り用の output。nValue は [input の nValue] - dust_limit - fee となる

※ dust_limitは、UTXOで保持すべき最小限のコインの量です。

2. その後、Dave が A, B をそれぞれ A社, B社 に送る

発行されるトランザクションは、

  • インプット
    1. 1で Dave が受け取った UTXO
    2. 手数料を支払うための Dave の UTXO
  • アウトプット
    1. ‘A’ を含むトラッキングペイロード
    2. A社 に向けた output。nValue は dust_limit の値
    3. ‘B’ を含むトラッキングペイロード
    4. B社 に向けた output。nValue は dust_limit の値
    5. ‘C’ を含むトラッキングペイロード
    6. Dave に向けた output。nValue は dust_limit の値
    7. Dave へのお釣り用の output。nValue は [手数料のための input の nValue] - dust_limit * 3 - fee となる

3. その後、別便でDave が C を C社 に送る

発行されるトランザクションは、

  • インプット
    • 2 の 6番目の output
    • 手数料を支払うための Dave の UTXO
  • アウトプット
    • ‘C’ を含むトラッキングペイロード
    • C社 に向けた output。nValue は dust_limit の値
    • Dave へのお釣り用の output。nValue は [手数料のための input の nValue] - dust_limit - fee となる

トレースする

カカオに紐付けられた一意のIDを元に、上記のトランザクションチェーンをたどり、アキュムレーターを検証することでAのカカオの流通経路を探索します。