book

Probabilistic Data Structures for Blockchain-Based Internet of Things Applications

Name: Probabilistic Data Structures for Blockchain-Based Internet of Things Applications
ISBN: 9781000327694

by Neeraj Kumar, Arzoo Miglani

January 2021

Intermediate to advanced

322 pages

7h 23m

English

CRC Press

Read now

Unlock full access

Cover
Half Title
Title Page
Copyright Page
Contents
Foreword
Preface
Biography
I Background
1 Overview of Internet of Things
1.1 Understanding the Concept of Internet of Things1.1.1 Components of IoT1.2 Big Data Revolution1.2.1 Big data and IoT1.3 Understanding edge computing

2 Smart Applications
2.1 Internet-of-Energy2.2 Autonomous Vehicles2.3 Healthcare2.4 Smart Farming2.5 Smart Education2.6 Smart Industry2.7 Smart City
3 IoT challenges
3.1 Security3.2 Data Management3.3 Privacy3.4 Heterogeneity3.5 Latency3.6 Communication Challenge in IoT
II Blockchain Overview
4 Python Basics
4.1 Introduction4.2 Comments4.3 Multi-line Statement4.4 Blocks and Indentation4.5 Creating Variables and Assigning Values4.6 Data Types4.7 Operators4.7.1 Arithmetic operator4.7.2 Comparison operator4.7.3 Logical operator4.7.4 Python Bitwise operator4.7.5 Assignment operator4.7.6 Membership operator4.7.7 Identity Operators4.8 Input and Output in Python4.9 List4.10 Dictionary4.11 Python Conditions and if-else4.12 Loops4.13 Functions in Python4.14 Classes and Objects in Python4.15 File Handling in Python4.15.1 open() function4.15.2 close() function4.15.3 read() function4.16 write() function
5 Cryptography Primitives
5.1 Introduction5.2 Encryption/Decryption Process5.2.1 Encryption5.2.2 Decryption5.2.3 Symmetric key encryption5.2.4 Asymmetric key encryption5.2.5 Public key5.2.6 Private key5.3 Cryptographic Hash Functions5.3.1 Typical properties of a hash function5.3.2 Requirements of hash function:5.3.3 Applications of cryptographic hash functions5.3.4 MD5 message-digest algorithm5.3.5 SHA-2565.4 Digital Signatures5.4.1 Model of digital signature5.5 Zero-Knowledge Proof5.6 Hash Tables5.6.1 Separate chaining5.6.2 Linear probing5.6.3 Quadratic probing5.6.4 Double hashing5.7 RSA5.7.1 Steps for key generation:5.7.2 Encryption5.7.3 Decryption5.7.4 RSA example5.8 Elliptic Curve Cryptography
6 Blockchain Technology and Technical Foundations
6.1 Fundamentals of Blockchain6.1.1 Characteristics of blockchain technology6.1.2 What constitutes a block of blockchain?6.1.3 Bitcoin basics6.2 Types of Blockchain6.3 Blockchain Applications6.4 Smart Contracts6.5 Issues with Blockchain6.5.1 IPFS: A solution to decentralized data stoge problem6.6 Python Implementation of Blockchain
7 Verification and Validation Methods Used by Blockchain
7.1 Consensus Mechanism7.1.1 Proof-of-Work7.1.2 Proof-of-Stake7.1.3 Delegated Proof-of-Stake7.1.4 Practical Byzantine Fault Tolerance7.1.5 Proof-of-Authority7.1.6 Proof-of-Capacity7.1.7 Proof-of-Burn7.1.8 Proof-of-Luck7.2 Simplified Payment Verification7.3 Block Validation7.4 Transaction Validation
8 Data Structures for Blockchain
8.1 Data Structures for Blockchain
III Probabilistic Data Structures: An Overview
9 Introduction to Probabilistic Data Structures
9.1 Need of Probabilistic Data Structures9.2 Deterministic Data Structures vs. Probabilistic Data Structures9.3 Probabilistic Data Structures Applications9.4 Probabilistic Data Structure Challenges
10 Membership Query Probabilistic Data Structures
10.1 Membership Query Probabilistic Data Structures10.2 Bloom Filter and its Variants10.2.1 Structure of Bloom filter10.2.2 Implementation of BF in Python10.2.3 Variants of BF10.2.3.1 Counting BF10.2.3.2 Compressed BF10.2.3.3 Spectral BF10.2.3.4 Deletable Bloom Filter (DBF)10.2.3.5 Stable BF10.2.3.6 Retouched Bloom Filter (RBF)10.2.3.7 Dynamic Bloom Filter10.2.3.8 Cuckoo Filter10.2.3.9 Hierarchical BF10.2.3.10 Stochastic Fair Blue10.3 Quotient Filter10.4 Skip List10.4.1 Skiplist implementation in Python
11 Cardinality Estimation Probabilistic Data Structures
11.1 Introduction11.2 Linear Counting11.2.1 Implemtation code of linear counting11.3 LogLog11.3.1 Implementation of LogLog in Python11.4 HyperLogLog11.4.1 Implementation of HLL in Python
12 Frequency Count Query Probabilistic Data Structures
12.1 Introduction12.2 Count-Min Sketch12.2.1 Implementation of CMS with Python12.2.2 Count-mean-min-sketch12.3 Count-sketch12.4 Count-Min with Conservative Update Sketch
13 Approximate Similarity Search Query Probabilistic Data Structures
13.1 Introduction13.2 Minhashing13.3 Locality Sensitive Hashing13.3.1 Simhash
IV Integration of Probabilistic Data Structures with Blockchain
14 Applicability of Membership Query PDS with Blockchain
14.1 Full Blockchain Client vs Lightweight Blockchain Client14.2 BF with probabilistic data structures14.2.1 Bitcoin using BF14.2.1.1 PoW using BF14.2.2 Ethereum using BF14.2.3 Integration of blockchain and BF for certificate revocation14.2.4 Integration of blockchain and BF in smart grid sector14.2.5 Integration of blockchain and Bitcoin for bodyworn sensing devices14.2.6 Graphene: Block propagation protocol14.2.7 Anti-malware software using BF and blockchain14.2.8 Transaction execution in disaster prone area using BF and blockchain14.2.9 Non-equivocation with BF and blockchain14.2.10 Outdoor health monitoring using blockchain and BF14.2.11 Multi-domain collaboration for MEC in 5G and beyond based on blockchain and BF14.3 Integration of QF with Blockchain14.4 Integration of Skiplist with Blockchain
15 Applicability of Cardinality Estimation PDS with Blockchain
15.1 DDoS Attack in Blockchain15.2 Mempool Transaction Count15.3 Interation of Linear Counting, LogLog and HyperLogLog with Blockchain15.3.1 Counting transaction in mempool15.3.2 HLL to prevent DoS attack15.3.3 IoT chain
16 Applicability of Frequency Estimation PDS with Blockchain
16.1 RFID Tag Cloning16.2 Understanding Heavy Hitters16.3 Integration of CMS with Blockchain16.3.1 Detecting DoS attack16.3.2 Detecting RFID tag cloning
17 Applicability of Approximate Similarity Search PDS with Blockchain
17.1 Approximate Nearest Neighbor Binary Search Algorithm for Wireless Multimedia Sensor Network17.2 A Blockchain of Image Copyrights Using Locality Sensitive Hashing
Bibliography
Index

Content preview from Probabilistic Data Structures for Blockchain-Based Internet of Things Applications

10 Membership Query Probabilistic Data Structures

10.1 Membership Query Probabilistic Data Structures

Oftentimes while processing streaming IoT data, searching for a particular item is required with minimum latency and space. The aim of membership query probabilistic data structures (MSQ PDS) is to check the presence of an element x in a large set $(S)$ of elements. The membership query operation using a linked list, array or a balanced binary tree requires a memory space linear to the size of set S. Hash table also has a larger size so, the memory it takes will also be larger. On the other hand, MSQ PDS are getting popular for handling queries of big data and streaming applications as these data structures consume less memory. Also, MSQ PDS ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781000327694

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Probabilistic Data Structures for Blockchain-Based Internet of Things Applications

by Neeraj Kumar, Arzoo Miglani

10

Membership Query Probabilistic Data Structures

10.1 Membership Query Probabilistic Data Structures

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.