Blockchain Papers

Jincheng Zhang

Distributed consensus algorithms are fundamental to many critical systems, including blockchain networks, sensor networks, and distributed databases. However, these systems are vulnerable to Byzantine faults, where malicious nodes can arbitrarily deviate from the agreed-upon protocol. Verifying the convergence and correctness of consensus algorithms under these conditions is a notoriously difficult problem. This paper presents a novel approach to probabilistic formal verification of distributed consensus algorithms with Byzantine fault tolerance. We model the consensus algorithm as a stochastic process and leverage probability covers and Markov chain analysis to derive rigorous proofs of convergence and fault tolerance. This method allows us to quantify the probability of correct operation even in the presence of arbitrary malicious behavior, offering a significant advancement over traditional approaches that often rely on idealized assumptions. The key contribution lies in the ability to provide probabilistic guarantees for consensus algorithm behavior, rather than simply demonstrating eventual convergence. We illustrate the application of this framework with a simplified example, highlighting its potential for scaling to more complex consensus protocols.

Muzzamal Ramzan,Abeesha Shahnawaz,Bilal Rasheed,Muhammad Zunnurain Hussain,Muhammad Zulkifl Hasan

No abstract is available for this record.

Seung Bum Park, Won Cheol Lee

This paper proposes a blockchain-based automated frequency coordination system (BAFCS) for secure and reliable spectrum sharing without causing any harmful interference to an existing system. For the exact assessment of whether the incumbent is interfered with by the spectrum sharer, the received signal strength (RSS) associated with the incumbent should be measured with sufficient accuracy at every location within the area of interest. However, since it requires brute force to carry out empirical measurements around an entire region, to lessen the burden, only the confined portion of the RSSs associated with the incumbent as a kind of primary user are observed and the omitted residuals are conventionally estimated by carrying out the well-known Kriging interpolation with regard to the geostatistical characteristics. This paper proposes a frequency coordination system capable of identifying whether a requested frequency band can be eligible for spectrum sharing while exchanging adequate information over blockchain network to confirm the usability. This paper proposes the Support Vector Machine (SVM)-based Kriging interpolation for recapitulating the radio environment map (REM) when only a fraction of the RSS measurements is acquired by the voluntary sensing participant (VSP). The nonparametric modeling approach for variograms proposed in this paper was determined to have a vital role in making a confident decision regarding spectrum sharing. The simulation result confirmed the effectiveness and the superiority of the proposed BAFCS with several affirmative features, such as enabling the consensus-based approval of spectrum sharing, the secure transaction of the information, and reliable assurance of no harmful interference.

Paweł Śniatała, M. Hadi Amini, Kianoosh G. Boroojeni

Information fusion has been a topic of immense interest owing to its applicability in various applications. This brings to the fore the need for a flexible and accurate fusion algorithm that can be versatile. The Brooks–Iyengar algorithm is one such fusion algorithm. It has since its inception found numerous applications that deal with the fusion of data from multiple sources. The uniqueness of the Brooks–Iyengar algorithm is the ease with which the data from multiple sensors in a local system can be fused and also reach consensus in a distributed system with the added capability of fault tolerance. Blockchain has found its use as a distributed ledger and has successfully supported and fueled many crypto-currencies over the years. Information fusion with regard to blockchains is a topic of great research interest in the past couple of years. Since blockchain has no official node, the introduction of a decentralized network and a consensus algorithm is required in making the interactions and exchanges between multiple suppliers easier and thus leads to business being carried out without any hassles. In this paper, we attempt to understand and describe the deployment of multiple sensors to measure various aspects of the physical world. We discuss a novel technique of employing the Brooks–Iyengar algorithm in the design of the system that would decentralize the data source from the corresponding measurements and thus ensure the integrity of the transactions in the blockchain. Finally, a theoretical analysis of the performance of the algorithm when used in a blockchain based decentralized environment is also discussed.

S. S. Iyengar, Sanjeev Kaushik Ramani, Buke Ao

Information fusion has been a topic of immense interest owing to its applicability in various applications. This brings to the fore the need for a flexible and accurate fusion algorithm that can be versatile. The Brooks–Iyengar algorithm is one such fusion algorithm. It has since its inception found numerous applications that deal with the fusion of data from multiple sources. The uniqueness of the Brooks–Iyengar algorithm is the ease with which the data from multiple sensors in a local system can be fused and also reach consensus in a distributed system with the added capability of fault tolerance. Blockchain has found its use as a distributed ledger and has successfully supported and fueled many crypto-currencies over the years. Information fusion with regards to Blockchains is a topic of great research interest in the past couple of years. Since blockchain has no official node, the introduction of a decentralized network and a consensus algorithm is required in making the interactions and exchanges between multiple suppliers easier and thus leads to business being carried out without any hassles. In this paper, we attempt to understand and describe the deployment of multiple sensors to measure various aspects of the physical world. We discuss a novel technique of employing the Brooks–Iyengar algorithm in the design of the system that would decentralize the data source from the corresponding measurements and thus ensure the integrity of the transactions in the Blockchain. Finally, a theoretical analysis of the performance of the algorithm when used in a blockchain based decentralized environment is also discussed.

Jayakrishnan Unnikrishnan, Saeid Haghighatshoar, Martin Vetterli

We study the problem of solving a linear sensing system when the observations are unlabeled. Specifically we seek a solution to a linear system of equations y = Ax when the order of the observations in the vector y is unknown. Focusing on the setting in which A is a random matrix with i.i.d. entries, we show that if the sensing matrix A admits an oversampling ratio of 2 or higher, then, with probability 1, it is possible to recover x exactly without the knowledge of the order of the observations in y. Furthermore, if x is of dimension K, then any 2K entries of y are sufficient to recover x. This result implies the existence of deterministic unlabeled sensing matrices with an oversampling factor of 2 that admit perfect reconstruction. The result is universal in that conditioned on the realization of matrix A, recovery is guaranteed for all possible choices of x. While the proof is constructive, it uses a combinatorial algorithm which is not practical, leaving the question of complexity open. We also analyze a noisy version of the problem and show that local stability is guaranteed by the solution. In particular, for every x, the recovery error tends to zero as the signal-to-noise ratio tends to infinity. The question of universal stability is unclear. In addition, we obtain a converse of the result in the noiseless case: If the number of observations in y is less than 2K, then with probability 1, universal recovery fails, i.e., with probability 1, there exist distinct choices of x which lead to the same unordered list of observations in y. We also present extensions of the result of the noiseless case to special cases with non-i.i.d. entries in A, and to a different setting in which the labels of a portion of the observations y are known. In terms of applications, the unlabeled sensing problem is related to data association problems encountered in different domains including robotics where it is appears in a method called “simultaneous localization and mapping”, multi-target tracking applications, and in sampling signals in the presence of jitter.

Lachlan James Gunn

No measurement system is perfect, and two varieties of error compete to frustrate their designers and operators. Random errors produce measurement-to-measurement to variation, while systematic errors result in consistently-incorrect results. The interplay between these two phenomena has been the subject of research for many years, particularly within the area of stochastic resonance, which focusses upon cases where the signal-to-noise ratio of a nonlinear system can increase with the addition of noise to its input signal. While it has been demonstrated many times that noise can overcome systematic deficiencies in a measurement system, there remain open questions on how to take advantage of this in practical systems, what information can be extracted, and whether such ‘randomised’ systems are useful in other settings. In this thesis, we consider this general theme in the context of two main settings: the adversarial, and the nonadversarial. In both cases, there is a significant advantage to be gained from the use of techniques that are adapted to the problem domain, in contrast to previous ad-hoc approaches that have failed to take advantage of the structures of the problems at hand. The first part of this thesis considers the elimination of static nonlinearity from noisy measurements. We start with the phenomenon of ‘classical’ stochastic resonance, showing how input noise can be used to linearise the response of a nonlinear system. This phenomenon has been observed in the past, however we demonstrate that the use of nonlinear signal processing allows the linearisation to take place with far smaller levels of noise. We then investigate several approaches to the implementation of this technique, with the aim of supporting real-time operation in embedded systems and vlsi. The remainder of the thesis concerns the use of randomness in measurements made as part of adversarial systems. This can be split into two situations: that where the operation of a system requires that measurement be difficult, and that where measurement must be straightforward. We first discuss the Kish key distribution system, a proposed classical alternative to quantum key distribution. This system claims to derive its security from the second law of thermodynamics, however these claims have been the subject of controversy. We examine the claims in detail, and show that the use of random signals does not render implausible the measurement of the system state. Finally, we describe a number of approaches to the topical problems of key distribution and identity verification. We show how various forms of multi-path probing can be treated as a form of random sampling; much like in the first section, this randomness allows for the characterisation of systematic errors, in this case the consistent changes introduced by an attacker. We then compute bounds on the probability that an attacker achieves a deception against a user taking part in this sampling process. The first approach that we consider uses an anonymising system such as Tor or a mixnet; if all users make anonymous requests to a service in lock-step, then a malicious service cannot guarantee a self-consistent set of responses to anyone without providing the malicious response to all users. This allows the development of a statistically guaranteed consensus, and thus permits auditors to assure themselves that they have examined the same data as has been provided to other users. This provides an attractive alternative to blockchain technology, avoiding the complexity of the proof-of-work and proof-of-stake-based systems that dominate the landscape today. We have developed a second approach that allows the random-sampling approach to be used with the existing public-key infrastructure. By demonstrating that the entities chosen to carry out the verification of an identity holder are selected at random from a substantial number of independent entities, relying parties can be confident that small numbers of compromised verifiers cannot unilaterally issue certificates for identities that they do not hold. This provides a basis for the development of highly robust distributed certificate issuance systems that do not share the current ‘weakest-link’ nature of the existing public-key infrastructure.
\nUltimately, these systems all hold in common the use of randomness in their measurement conditions in order to characterise systematic effects. While this phenomenon has been acknowledged, its potential to characterise real systems has until now not been realised. We demonstrate that randomness, whether natural and unavoidable or artificially introduced, can ironically render far more predictable the behaviour of many systems, and in more realistic situations than have been seen in the literature to date.

David L. Donoho, Adel Javanmard, Andrea Montanari

We study the compressed sensing reconstruction problem for a broad class of random, band-diagonal sensing matrices. This construction is inspired by the idea of spatial coupling in coding theory. As demonstrated heuristically and numerically by Krzakala et al. \cite{KrzakalaEtAl}, message passing algorithms can effectively solve the reconstruction problem for spatially coupled measurements with undersampling rates close to the fraction of non-zero coordinates. We use an approximate message passing (AMP) algorithm and analyze it through the state evolution method. We give a rigorous proof that this approach is successful as soon as the undersampling rate $δ$ exceeds the (upper) Rényi information dimension of the signal, $\uRenyi(p_X)$. More precisely, for a sequence of signals of diverging dimension $n$ whose empirical distribution converges to $p_X$, reconstruction is with high probability successful from $\uRenyi(p_X)\, n+o(n)$ measurements taken according to a band diagonal matrix. For sparse signals, i.e., sequences of dimension $n$ and $k(n)$ non-zero entries, this implies reconstruction from $k(n)+o(n)$ measurements. For `discrete' signals, i.e., signals whose coordinates take a fixed finite set of values, this implies reconstruction from $o(n)$ measurements. The result is robust with respect to noise, does not apply uniquely to random signals, but requires the knowledge of the empirical distribution of the signal $p_X$.