Miyaji Laboratory

Recently, Blockchain has been gathering attention which can be used in virtual currency. Blockchain can trade without using a trusted third party, but as Blockchain grows in size, the resources to validate that a transaction is true increase linearly. Key-value commitments is suggested to solve this problem.
Without key-value commitments, if we want to prove some key-value pair is in the group, we have to check the list which includes all key-value pairs, so it takes O(n) complexity if there are n pairs. However, if we use Key-Value Commitments, we can authenticate by three elements, commitment which is compression of the list, key-value pair which we want to authenticate, and proof which proves the key-value pair is in the group, so it can compute O(1) complexity. But in this method, we must change all proofs that are assigned to the key-value pair, so it takes O(n) complexity at total when there are n pairs. In this research, we propose how to reduce the complexity of update proof.