Miyaji Laboratory

ブロックチェーンでは規模に比例して取引の正当性を確認するための計算量が大きくなる.この問題の解決策として Key-Value Commitments が提案されている.Agrawal らの Key-Value Commitments [1] を使用すると,リストの値を圧縮したコミットメント,認証したい key-value ペア,集合に所属している証明書の 3 つの要素を用いてO(1) で認証が可能となる.しかし,この方式では集合の一部に変化があるたびに全ての key-value ペアに対応する証明書を変更する必要があるため,n 人の更新の合計の計算量が O(n) となる.本研究では,証明書の更新の計算量を削減する方法を提案する.また,証明書を更新しない時間が存在しても,復帰時の情報のみで復元可能とする.