Indexing structures for the PLS blockchain  

作　　者：Alex Shafarenko 

机构地区：[1]University of Hertfordshire,AL1O 9AB Hertfordshire,UK

出　　处：《Cybersecurity》2022年第1期28-46,共19页网络空间安全科学与技术（英文）

基　　金：supported in part by IMC corporation,Slovakia,under EU Project BRAINE(Grant 876967).

摘　　要：This paper studies known indexing structures from a new point of view:minimisation of data exchange between an IoT device acting as a blockchain client and the blockchain server running a protocol suite that includes two Guy Fawkes protocols,PLS and SLVP.The PLS blockchain is not a cryptocurrency instrument;it is an immutable ledger offering guaranteed non-repudiation to low-power clients without use of public key crypto.The novelty of the situation is in the fact that every PLS client has to obtain a proof of absence in all blocks of the chain to which its counterparty does not contribute,and we show that it is possible without traversing the block's Merkle tree.We obtain weight statistics of a leaf path on a sparse Merkle tree theoretically,as our ground case.Using the theory we quantify the communication cost of a client interacting with the blockchain.We show that large savings can be achieved by providing a bitmap index of the tree compressed using Tunstall's method.We further show that even in the case of correlated access,as in two IoT devices posting messages for each other in consecutive blocks,it is possible to prevent compression degradation by re-randomising the IDs using a pseudorandom bijective function.We propose a low-cost function of this kind and evaluate its quality by simulation,using the avalanche criterion.

关 键 词：PLS blockchain Guy Fawkes protocol Content-addressable storage Data-structure statistics Tunstall coding Pseudorandom bijections 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]