Nakamoto invented the longest chain protocol, and claimed its security by analyzing the private double-spend attack, a race between the adversary and the honest nodes to grow a longer chain. But is it the worst attack? We answer the question in the affirmative for three classes of longest chain protocols, designed for different consensus models: 1) Nakamoto's original Proof-of-Work protocol; 2) Ouroboros and SnowWhite Proof-of-Stake protocols; 3) Chia Proof-of-Space protocol. As a consequence, exact characterization of the maximum tolerable adversary power is obtained for each protocol as a function of the average block time normalized by the network delay. The security analysis of these protocols is performed in a unified manner by a novel method of reducing all attacks to a race between the adversary and the honest nodes.

We consider the problem of reconstructing a finite-alphabet signal corrupted by a known memoryless channel with a general output alphabet. The goodness of the reconstruction is measured by a given loss function. We (constructively) establish the existence of a universal (sequence of) denoiser(s) attaining asymptotically the optimum distribution-dependent performance for any stationary source that may be generating the noiseless signal. We show, in fact, that there is a whole family of denoiser sequences with this property. These schemes are shown to be universal also in a semistochastic setting, where the only randomness assumed is that associated with the channel noise. The scheme is practical, requiring O(n/sup 1+/spl epsiv//) operations (for any /spl epsiv/>0) and working storage size sublinear in the input data length. This extends recent work that presented a discrete universal denoiser for recovering a discrete source corrupted by a discrete memoryless channel (DMC).

This paper describes the universal denoising for the finite-input-general-output channel. The present work is in the case where the components of the underlying noise-free signal are still finite valued, yet their noisy observations take values in a general alphabet. This channel is assumed as discrete memoryless in this case. A discrete signal corrupted by a known discrete memoryless channel can be asymptotically optimal and practically denoised with no a-priori knowledge of statistical (or any other) properties of the signal.

Consider the problem of finite-rate filtering of a discrete memoryless process {X/sub i/}/sub i/spl ges/1/ based on its noisy observation sequence {Z/sub i/}/sub i/spl ges/1/, which is the output of a discrete memoryless channel (DMC) whose input is {X/sub i/}/sub i/spl ges/1/. When the distribution of the pairs (X/sub i/,Z/sub i/), P/sub X,Z/, is known, and for a given distortion measure, the solution to this problem is well known to be given by classical rate-distortion theory upon the introduction of a modified distortion measure. We address the case where P/sub X,Z/, rather than being completely specified, is only known to belong to some set /spl Lambda/. For a fixed encoding rate R, we look at the worst case, over all /spl theta//spl isin//spl Lambda/, of the difference between the expected distortion of a given scheme which is not allowed to depend on the active source /spl theta//spl isin//spl Lambda/ and the value of the distortion-rate function at R corresponding to the noisy source /spl theta/. We study the minimum attainable value achievable by any scheme operating at rate R for this worst case quantity, denoted by D(/spl Lambda/, R). Linking this problem and that of source coding under several distortion measures, we prove a coding theorem for the latter problem and apply it to characterize D(/spl Lambda/, R) for the case where all members of /spl Lambda/ share the same noisy marginal. For the case of a general /spl Lambda/, we obtain a single-letter characterization of D(/spl Lambda/, R) for the finite-alphabet case. This gives, in particular, a necessary and sufficient condition on the set /spl Lambda/ for the existence of a coding scheme which is universally optimal for all members of /spl Lambda/ and characterizes the approximation-estimation tradeoff for statistical modeling of noisy source coding problems. Finally, we obtain D(/spl Lambda/, R) in closed form for cases where /spl Lambda/ consists of distributions on the (channel) input-output pair of a Bernoulli source corrupted by a binary-symmetric channel (BSC). In particular, for the case where /spl Lambda/ consists of two sources: the all-zero source corrupted by a BSC with crossover probability r and the Bernoulli(r) source with a noise-free channel; we find that universality becomes increasingly hard with increasing rate.

We present a development of parts of rate-distortion theory and pattern-matching algorithms for lossy data compression, centered around a lossy version of the asymptotic equipartition property (AEP). This treatment closely parallels the corresponding development in lossless compression, a point of view that was advanced in an important paper of Wyner and Ziv in 1989. In the lossless case, we review how the AEP underlies the analysis of the Lempel-Ziv algorithm by viewing it as a random code and reducing it to the idealized Shannon code. This also provides information about the redundancy of the Lempel-Ziv algorithm and about the asymptotic behavior of several relevant quantities. In the lossy case, we give various versions of the statement of the generalized AEP and we outline the general methodology of its proof via large deviations. Its relationship with Barron (1985) and Orey's (1985, 1986) generalized AEP is also discussed. The lossy AEP is applied to (i) prove strengthened versions, of Shannon's(1948, 1974) direct source-coding theorem and universal coding theorems; (ii) characterize the performance of "mismatched" codebooks in lossy data compression; ( iii) analyze the performance of pattern-matching algorithms for lossy compression (including Lempel-Ziv schemes); and (iv) determine the first-order asymptotic of waiting times between stationary processes. A refinement to the lossy AEP is then presented, and it is used to (i) prove second-order (direct and converse) lossy source-coding theorems, including universal coding theorems; (ii) characterize which sources are quantitatively easier to compress; (iii) determine the second-order asymptotic of waiting times between stationary processes; and (iv) determine the precise asymptotic behavior of longest match-lengths between stationary processes. Finally, we discuss extensions of the above framework and results to random fields.

The following critical phenomenon was recently discovered. When a memoryless source is compressed using a variable-length fixed-distortion code, the fastest convergence rate of the (pointwise) compression ratio to R(D) is either O(/spl radic/n) or O(log n). We show it is always O(/spl radic/n), except for discrete, uniformly distributed sources.

Precise analytical asymptotic exponential rates of error, and bounds on those rates, for differential multiplephase-shift keying (DMPSK) systems that include post-detection integration are provided. Easily computed bounds on these rates are provided, both in the case of floor bit error probability (i.e., with no additive noise) and in the case of weak additive noise. The derivation uses the theory of large deviations and illustrates its applicability to the analysis of communications systems.>

Bounds on the symmetric binary cutoff rate for a pulse amplitude modulated (PAM) signaling over dispersive Gaussian channels are evaluated and discussed. These easily calculable bounds can be used to estimate the reliable rate of information transmission and the error exponent behavior for binary (two-level) PAM schemes, operating through a prefiltered additive white Gaussian channel, the memory of which is long enough to make the exact evaluation of the cutoff rate formidable. The core of the bounding technique relies on a probabilistic interpretation of a fundamental theorem in matrix theory, regarding the logarithm of the largest eigenvalue of a nonnegative primitive matrix, commonly applied in large deviation problems. These bounds are calculated for some examples and their respective tightness is considered. Further potential applications of the proposed bounding technique are pointed out.>

Data compression of independent samples drawn from a fractal set is considered. The asymptotic ratio of rate to magnitude log distortion characterizes the effective dimension occupied by the underlying distribution. This quantity is shown to be identical to Renyi's (1959) information dimension. For self-similar fractal sets this dimension is distribution dependent-in sharp contrast with the behavior of absolutely continuous measures. The rate-distortion dimension of a set is defined as the maximal rate-distortion dimension for distributions supported on this set. Kolmogorov's metric dimension is an upper bound on the rate-distortion dimension, while the Hausdorff dimension is a lower bound. Examples of sets for which the rate-distortion dimension differs from these bounds are provided.>

The role of inequalities in information theory is reviewed, and the relationship of these inequalities to inequalities in other branches of mathematics is developed. The simple inequalities for differential entropy are applied to the standard multivariate normal to furnish new and simpler proofs of the major determinant inequalities in classical mathematics. The authors discuss differential entropy inequalities for random subsets of samples. These inequalities when specialized to multivariate normal variables provide the determinant inequalities that are presented. The authors focus on the entropy power inequality (including the related Brunn-Minkowski, Young's, and Fisher information inequalities) and address various uncertainty principles and their interrelations.>

Classical methods from optimal control theory are used in deriving general forms for neural network weights. The network learning or application task is encoded in a performance index of a general structure. Consequently, different instances of this performance index lead to special cases of weight rules, including some well-known forms. Comparisons are made with the outer product rule, spectral methods, and recurrent back-propagation. Simulation results and comparisons are presented.

Fast recursive algorithms for updating coefficients in digital echo cancellers can be derived from the well-known method of least squares. Unless zero initial conditions are assumed, the exact initialization of these algorithms is yet unknown. For random data of more than twice the order of the filter, the existence of a unique least squares solution is proven. A constructive recursive procedure in time and order for computing the pseudoinverse solution for the initial steps is derived. Since the data matrix is composed of integers, this technique facilitates the implementation of stable tap-update algorithms.>

Model-free learning for synchronous and asynchronous quasi-static networks is presented. The network weights are continuously perturbed, while the time-varying performance index is measured and correlated with the perturbation signals; the correlation output determines the changes in the weights. The perturbation may be either via noise sources or orthogonal signals. The invariance to detailed network structure mitigates large variability between supposedly identical networks as well as implementation defects. This local, regular, and completely distributed mechanism requires no central control and involves only a few global signals. Thus, it allows for integrated, on-chip learning in large analog and optical networks.

The efficient representation of the excitation signal to an LPC (linear predictive coding) synthesis filter by means of a vector expansion of the residual signal is examined. According to this approach the excitation signal is represented as a linear combination of a small number of vectors taken from a given vector set, known at both ends of the transmission channel. It is demonstrated that this approach provides a unified framework for describing and analyzing a wide range of residual speech coders, from multipulse LPC and code-excited linear prediction to residual transform coders, and leads to generalization of some of these schemes. Optimally conditions based on the singular-value decomposition (SVD) of the impulse-response matrix of the perceptually weighted LPC synthesis filter are given. A resulting simplified predictive transform coder is proposed and examined by computer simulation.>

Some important features of various known constructions of associative memories based on linear threshold functions are analyzed. Two important features are dealt with: (a) the ability to select an arbitrary set of desired memory vectors and design a network for this set; (b) the sizes and shapes of the domains of attraction of the desired memory vectors and their relation to various design parameters. The static capacity for randomly chosen desired memories is also analyzed. Two extremal examples of sets of desired memories are then analyzed in detail. For spectral schemes with randomly chosen O(N/ln N) memories, it is shown that almost all of the Hamming sphere around each memory is directly attracted.>

A very simple proof of M.H. Costa's result (see ibid., vol.IT-31, p.751-60, 1985) that the entropy power of X/sub t/=X+N(O,tI) is concave in t, is derived as an immediate consequence of an inequality concerning Fisher information. This relationship between Fisher information and entropy is found to be useful for proving the central limit theorem. Thus, one who seeks new entropy inequalities should try first to find new equalities about Fisher information, or at least to exploit the existing ones in new ways.>

M. Pinsker and P. Ebert (Bell Syst. Tech. J., p.1705-1712, Oct.1970) proved that in channels with additive Gaussian noise, feedback at most doubles the capacity. Recently, T. Cover and S. Pombra (ibid., vol.35, no.1, p.37-43, Jan.1989) proved that feedback at most adds half a bit per transmission. Following their approach, the author proves that in the limit as signal power approaches either zero (very low SNR) or infinity (very high SNR), feedback does not increase the finite block-length capacity (which for nonstationary Gaussian channels replaces the standard notion of capacity that may not exist). Tighter upper bounds on the capacity are obtained in the process. Specializing these results to stationary channels, the author recovers some of the bounds recently obtained by L.H. Ozarow (to appear in IEEE Trans. Inf. Theory) using a different bounding technique.>

The class of nonnegative definite Toeplitz matrices that can be embedded in nonnegative definite circulant matrices of a larger size is characterized. An equivalent characterization in terms of the spectrum of the underlying process is also presented, together with the corresponding extremal processes. It is shown that a given finite-duration sequence rho can be extended to be the covariance of a periodic stationary processes whenever the Toeplitz matrix R generated by this sequence is strictly positive definite. The sequence rho =1, cos alpha , cos 2 alpha with ( alpha / pi ) irrational, which has a unique nonperiodic extension as a covariance sequence, demonstrates that the strictness is needed. A simple constructive proof supplies a bound on the abovementioned period in terms of the minimal eigenvalue of R. It also yields, under the same conditions, an extension of rho to covariances that eventually decay to zero. For the maximum-likelihood estimate of the covariance of a stationary Gaussian process, the extension length required for using the estimate-maximize iterative algorithm is determined.>

An iterative approach for minimum-discrimination-information (MDI) hidden Markov modeling of information sources is proposed. The approach is developed for sources characterized by a given set of partial covariance matrices and for hidden Markov models (HMMs) with Gaussian autoregressive output probability distributions (PDs). The approach aims at estimating the HMM which yields the MDI with respect to all sources that could have produced the given set of partial covariance matrices. Each iteration of the MDI algorithm generates a new HMM as follows. First, a PD for the source is estimated by minimizing the discrimination information measure with respect to the old model over all PDs which satisfy the given set of partial covariance matrices. Then a new model that decreases the discrimination information measure between the estimated PD of the source and the PD of the old model is developed. The problem of estimating the PD of the source is formulated as a standard constrained minimization problem in the Euclidean space. The estimation of a new model given the PD of the source is done by a procedure that generalizes the Baum algorithm. The MDI approach is shown to be a descent algorithm for the discrimination information measure, and its local convergence is proved.>

Easily computable bounds on the extreme eigenvalues of positive semidefinite (PSD) Toeplitz matrices are presented. The bounds are especially suitable for matrices of relatively small dimension. The bounds are derived for the wider class of PSD Hermitian matrices and interpreted via the Levinson-Durbin Algorithm for Toeplitz matrices. As a by-product of this derivation an order-recursive algorithm for the eigenvector/eigenvalue decomposition is obtained, and certain properties of the eigenvalues distribution are revealed.>

The problem of estimating the number of transitions of finite-state continuous-time Markov processes observed by a noisy sensor is considered. A finite-dimensional exact filter is derived, and using the EM algorithm (an extension of the Baum-Welch algorithm for the discrete-time case), an application is made to the problem of estimating the unknown transition matrix of a finite-state continuous-time Markov process.>

A new iterative approach for hidden Markov modeling of information sources which aims at minimizing the discrimination information (or the cross-entropy) between the source and the model is proposed. This approach does not require the commonly used assumption that the source to be modeled is a hidden Markov process. The algorithm is started from the model estimated by the traditional maximum likelihood (ML) approach and alternatively decreases the discrimination information over all probability distributions of the source which agree with the given measurements and all hidden Markov models. The proposed procedure generalizes the Baum algorithm for ML hidden Markov modeling. The procedure is shown to be a descent algorithm for the discrimination information measure and its local convergence is proved.

A statistical model is used for the optimal design of analysis/synthesis systems which include quantization of the signals in the separate bands. Two error measures are used. One is a generalization of the usual statistical mean square error (MSE) to time-varying systems (since analysis/synthesis systems with decimation and interpolation are time varying). The second measure is the time average of the expected ℓ2distance between the output of the analysis stage and the analyzed reconstructed signal. The proposed design methods are based on minimizing these error measures and shown to apply not only with the DFT but also with any linear regular transform (e.g. Hadamard, DCT). The above two error measures are shown to be equivalent for a wide class of transforms (including the DFT). The design methods is applicable to either finding an optimal synthesis window for a given analysis window, or finding an optimal analysis window for a given synthesis window. The optimal windows (filters) are obtained by solving a set of linear equations. An optimal analysis/synthesis system is obtained using an iterative algorithm which is based on alternately solving these two sets of linear equations. When no quantization is applied the new design methods coincides with previously reported methods.

Two new ideas for the design of multipulse excited LPC coders are presented in this paper. The first idea relates to improving the extraction of the all-pole filter parameters by taking into account the error weighting function. This function, which takes advantage of the noise masking properties of the ear, is ignored in the conventional covariance and autocorrelation methods. The new approach leads to an iterative algorithm, in which the first iteration is essentially the covariance method. Each new iteration involves estimation of the residual and increases a likelihood function, taking into account the error weighting function. The second idea relates to improving the derivation of the excitation parameters. A recursive algorithm for the optimal choice of the i-th pulse location, given the previously obtained (i-l) pulse locations, is presented. The low complexity of the new algorithm enables its combination with a tree search algorithm, thus giving a solution which is better than the solution of the algorithms reported earlier , when the error weighting function is used