  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.
