{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:29:16Z","timestamp":1740180556405,"version":"3.37.3"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,11,2]],"date-time":"2021-11-02T00:00:00Z","timestamp":1635811200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,2]],"date-time":"2021-11-02T00:00:00Z","timestamp":1635811200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"IMC","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cybersecur"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 <jats:italic>without<\/jats:italic> 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\u2019s 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\u2019s 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.<\/jats:p>","DOI":"10.1186\/s42400-021-00101-w","type":"journal-article","created":{"date-parts":[[2021,11,2]],"date-time":"2021-11-02T03:02:29Z","timestamp":1635822149000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Indexing structures for the PLS blockchain"],"prefix":"10.1186","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8796-6542","authenticated-orcid":false,"given":"Alex","family":"Shafarenko","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,11,2]]},"reference":[{"issue":"4","key":"101_CR1","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/302350.302353","volume":"32","author":"R Anderson","year":"1998","unstructured":"Anderson R, Bergadano F, Crispo B, Lee JH, Manifavas C, Needham R (1998) A new family of authentication protocols. SIGOPS Oper Syst Rev 32(4):9\u201320","journal-title":"SIGOPS Oper Syst Rev"},{"key":"101_CR2","first-page":"43","volume":"2113","author":"A Bacher","year":"2018","unstructured":"Bacher A, Bodini O, Hollender A, Lumbroso J (2018) Mergeshuffle: a very fast, parallel random permutation algorithm. CEUR Workshop Proc 2113:43\u201352","journal-title":"CEUR Workshop Proc"},{"key":"101_CR3","first-page":"340","volume":"2021","author":"B Bailey","year":"2021","unstructured":"Bailey B, Sankagiri S (2021) Merkle trees optimized for stateless clients in bitcoin. IACR Cryptol ePrint Arch 2021:340","journal-title":"IACR Cryptol ePrint Arch"},{"key":"101_CR4","unstructured":"Bauer M (2004) Proofs of zero knowledge. CoRR, cs.CR\/0406058"},{"key":"101_CR5","doi-asserted-by":"crossref","unstructured":"Dahlberg R, Pulls T, Peeters R (2016) Efficient sparse merkle trees\u2014caching strategies and secure (non-)membership proofs. In Billy\u00a0BB, and Juha R (eds) Secure IT Systems\u201421st Nordic Conference, NordSec 2016, Oulu, Finland, November 2\u20134, 2016, Proceedings, volume 10014 of Lecture Notes in Computer Science, pp 199\u2013215","DOI":"10.1007\/978-3-319-47560-8_13"},{"key":"101_CR6","unstructured":"Espressif Systems. ESP32 Technical Reference Manual. Available as https:\/\/www.espressif.com\/sites\/default\/files\/documentation\/esp32_technical_reference_manual_en.pdf"},{"key":"101_CR7","volume-title":"Statistical tables for biological, agricultural and medical research","author":"RA Fisher","year":"1963","unstructured":"Fisher RA, Yates F (1963) Statistical tables for biological, agricultural and medical research, 6th edn. Oliver & Boyd, Edinburgh","edition":"6"},{"issue":"5","key":"101_CR8","first-page":"761","volume":"60","author":"S Jo","year":"2017","unstructured":"Jo S, Joannou S, Okanohara D, Raman R, Satti SR (2017) Compressed bit vectors based on variable-to-fixed encodings. Comput J 60(5):761\u2013775","journal-title":"Comput J"},{"key":"101_CR9","unstructured":"Lehmer DH (1951) Mathematical methods in large-scale computing units. In: Proceedings of the second symposium on large scale digital computing machinery. Cambridge, United Kingdom, 1951. Harvard University Press, pp 141\u2013146"},{"key":"101_CR10","unstructured":"LoRa and LoRaWAN: a technical overview. Technical report, Sentech Corporation, December 2019"},{"key":"101_CR11","doi-asserted-by":"crossref","unstructured":"Merkle RC (1988) A digital signature based on a conventional encryption function. In: Carl P (Ed) Advances in cryptology\u2014CRYPTO \u201987. Springer, Berlin, pp 369\u2013378","DOI":"10.1007\/3-540-48184-2_32"},{"issue":"1","key":"101_CR12","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1186\/s42400-020-00068-0","volume":"4","author":"A Shafarenko","year":"2021","unstructured":"Shafarenko A (2021) A PLS blockchain for IoT applications: protocols and architecture. Cybersecurity 4(1):4","journal-title":"Cybersecurity"},{"key":"101_CR13","unstructured":"Tunstall BP (1967) Synthesis of noiseless compression codes. Ph.D. thesis, Georgia Technology"},{"key":"101_CR14","doi-asserted-by":"crossref","unstructured":"Webster AF, Tavares SE (1986) On the design of s-boxes. In: Lecture Notes in Computer Sciences, 218 on Advances in Cryptology\u2014CRYPTO 85. Springer, Berlin, pp 523\u2013534","DOI":"10.1007\/3-540-39799-X_41"},{"key":"101_CR15","doi-asserted-by":"crossref","unstructured":"Yue C, Xie Z, Zhang M, Chen G, Ooi BC, Wang S, Xiao X (2020) Analysis of indexing structures for immutable data. In: Proceedings of the 2020 ACM SIGMOD international conference on management of data, SIGMOD \u201920, New York, NY, USA, 2020. Association for Computing Machinery, pp 925\u2013935","DOI":"10.1145\/3318464.3389773"}],"container-title":["Cybersecurity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-021-00101-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s42400-021-00101-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-021-00101-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,2]],"date-time":"2021-11-02T03:03:09Z","timestamp":1635822189000},"score":1,"resource":{"primary":{"URL":"https:\/\/cybersecurity.springeropen.com\/articles\/10.1186\/s42400-021-00101-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,2]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["101"],"URL":"https:\/\/doi.org\/10.1186\/s42400-021-00101-w","relation":{},"ISSN":["2523-3246"],"issn-type":[{"type":"electronic","value":"2523-3246"}],"subject":[],"published":{"date-parts":[[2021,11,2]]},"assertion":[{"value":"22 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"The author declares no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"36"}}