ブルームフィルターを利用してトランザクションの検証を高速化する

特許第6467540号

ディクショナリを参照するトランザクションの数を減らして、真が出力された場合のみディクショナリを参照して検証する発明です。

 

トランザクションをメモリプールに記憶する際に、過去に合意されたブロックに含まれるトランザクションではないかについての検証や、他のノードにおいて生成されたブロックに含まれるトランザクションに対する検証を行う場合があります。

 

これらの検証は、過去に合意されたブロックに含まれるすべてのトランザクションに対するトランザクションIDのディクショナリを保持しておき、新たなトランザクションを受け取るたびにディクショナリを参照して、過去に存在していないことの確認を行わなければなりません。

 

今回の発明は、新たなトランザクションを受けるたびにディクショナリを参照するという処理に代えて、ブロックチェーンネットワークにおいて過去に合意されたブロックに含まれる1又は複数のトランザクションに基づいて生成されたブルームフィルターに対して、検証対象となるトランザクションを入力します。

 

そして、真が出力として得られた場合にのみディクショナリへのアクセスを行うようにしています。

ディクショナリへのアクセス数を抑えることができるので、トランザクションの検証に必要な時間を短縮することができます。

 

f:id:tanakaIP:20210621151721j:plain

ブルームフィルタの挙動を観察してみます。

検証対象として入力されたトランザクションが過去に合意されたブロックに含まれないトランザクションである場合に偽を返します。

過去に存在したトランザクションであるとき、またはそうでないときに真を返します。

過去に存在しないにもかかわらず真を返す偽陽性を、今回の発明ではどのように評価しているのか。

 

偽陰性を許容できない環境ではブルームフィルターを使用できません。

 

今回の発明では、陽性の出力を受けたあと、ディクショナリを検索してトランザクションの有無を判定しています。

ディクショナリで再度、トランザクションの有無を判定して偽陽性を打ち消すという仕組みです。

 

ブルームフィルターとディクショナリをカスケードに接続して、偽陽性を許容する環境を構築しています。

 

田中特許事務所

弁理士 田中智雄