Rohan Goyal, Venkatesan Guruswami, Yihang Sun, Mary Wootters
Proximity gaps are a property of error correcting codes that arise in the study of Interactive Oracle Proofs (IOPs) and Succinct Non-interactive Arguments of Zero Knowledge (SNARKs). Recent work of Goyal and Guruswami has established near-optimal proximity gaps for many families of codes, including subspace design codes, as well as random ensembles like random linear codes, Reed-Solomon codes with random evaluation points, and Gallager's ensemble of LDPC codes (Goyal & Guruswami, 2025). However, the parameters for these latter randomized ensembles are worse than the parameters for subspace design codes, and degrade as the degree ell increases. In this work, we obtain improved proximity gaps for random ensembles of codes, including random linear codes, Reed-Solomon codes with random evaluation points, and Gallager's ensemble. Quantitatively, our results for these random ensembles match the results that Goyal and Guruswami attained for subspace design codes. In fact, our techniques are a black-box transference from subspace design codes: any progress on subspace design codes will automatically lead to analogous progress for these random ensembles. To obtain our results, we extend the Local Coordinate-wise Linear (LCL) property framework developed by Levi, Mosheiff, and Shagrithaya and by Brakensiek, Chen, Dhar, and Zhang to a \textit{row-span constrained} version (Levi, Mosheiff & Shagrithaya, 2025; Brakensiek, Chen, Dhar & Zhang, 2025). This allows us to cast \textit{curve-decodability} -- a property that implies proximity gaps -- directly as a row-span constrained LCL property, and make use of that machinery. In contrast, because curve-decodability is not obviously a vanilla LCL property, prior work had worked with a proxy property instead, leading to the aforementioned parameter losses.
Pol González, Adam Zahir, Chiara Grasselli, Alejandro Muñiz · 10 authors
A ML function orchestrator deploying secure ML pipelines to support near-real-time control of network services is demonstrated. A distributed ledger supports the initial key exchange to establish secure connectivity among the agents in the pipeline.
Travis C. Cuvelier, Takashi Tanaka, Robert W. Heath
We propose an adaptive coding approach to achieve linear-quadratic-Gaussian (LQG) control with near-minimum bitrate prefix-free feedback. Our approach combines a recent analysis of a quantizer design for minimum rate LQG control with work on universal lossless source coding for sources on countable alphabets. In the aforementioned quantizer design, it was established that the quantizer outputs are an asymptotically stationary, ergodic process. To enable LQG control with provably near-minimum bitrate, the quantizer outputs must be encoded into binary codewords efficiently. This is possible given knowledge of the probability distributions of the quantizer outputs, or of their limiting distribution. Obtaining such knowledge is challenging; the distributions do not readily admit closed form descriptions. This motivates the application of universal source coding. Our main theoretical contribution in this work is a proof that (after an invertible transformation), the quantizer outputs are random variables that fall within an exponential or power-law envelope class (depending on the plant dimension). Using ideas from universal coding on envelope classes, we develop a practical, zero-delay version of these algorithms that operates with fixed precision arithmetic. We evaluate the performance of this algorithm numerically, and demonstrate competitive results with respect to fundamental tradeoffs between bitrate and LQG control performance.
Light nodes in blockchain systems are known to be vulnerable to data availability (DA) attacks where they accept an invalid block with unavailable portions. Previous works have used LDPC and 2-D Reed Solomon (2D-RS) codes with Merkle Trees to mitigate DA attacks. While these codes have demonstrated improved performance across a variety of metrics such as DA detection probability, they are difficult to apply to blockchains with large blocks due to generally intractable code guarantees for large codelengths (LDPC), large decoding complexity (2D-RS), or large coding fraud proof sizes (2D-RS). We address these issues by proposing the novel Polar Coded Merkle Tree (PCMT) which is a Merkle Tree built from the encoding graphs of polar codes and a specialized polar code construction called Sampling-Efficient Freezing (SEF). We demonstrate that the PCMT with SEF polar codes performs well in detecting DA attacks for large block sizes.
The protocol for cryptocurrencies can be divided into three parts, namely consensus, wallet, and networking overlay. The aim of the consensus part is to bring trustless rational peer-to-peer nodes to an agreement to the current status of the blockchain. The status must be updated through valid transactions. A proof-of-work (PoW) based consensus mechanism has been proven to be secure and robust owing to its simple rule and has served as a firm foundation for cryptocurrencies such as Bitcoin and Ethereum. Specialized mining devices have emerged, as rational miners aim to maximize profit, and caused two problems: i) the re-centralization of a mining market and ii) the huge energy spending in mining. In this paper, we aim to propose a new PoW called Error-Correction Codes PoW (ECCPoW) where the error-correction codes and their decoder can be utilized for PoW. In ECCPoW, puzzles can be intentionally generated to vary from block to block, leading to a time-variant puzzle generation mechanism. This mechanism is useful in repressing the emergence of the specialized mining devices. It can serve as a solution to the two problems of recentralization and energy spending.
This article presents a novel way to reduce blockchain nodes’ memory requirements using error correcting codes. In particular, LDPC codes are taken as examples to explicitly demonstrate the scheme. The proposed coding scheme encodes data across multiple blocks, respectively, block headers, in the blockchain. This leads to a significant reduction in required memory at each node. We then apply the proposed coding technique to blockchains organized in two different ways. Our first scheme has the same protocol for mining, broadcasting, and verification of blocks, as Bitcoin-type blockchains. Our scheme is different in thatfull nodesdo not have to store all blocks. Instead they will need to store only one block of a group of$t$blocks. In the second scheme, we consider a new block verification protocol and an account-based model under the assumption that transmission between any two nodes can be established, as well as the broadcast transmission. Our block verification protocol uses the Byzantine fault tolerance algorithm and requires sending a newly mined block to only a small number of verification nodes, instead of broadcasting it to the entire network, which leads to a reduction of the network load.
Today's state of the art blockchains suffer from two major setbacks. The first among these, bootstrapping, is the introduction of new nodes into the peer-to-peer (P2P) network in the presence of adversarial nodes. It is crucial that new nodes are prevented from joining adversarial nodes to protect the integrity of the network. The second challenge that today's blockchains face is that of storage efficiency. Blockchains use replication to store the data (or ledger) among users. Users acting as full nodes need to store the entire ledger. As opposed to replication, coding techniques such as fountain codes can be utilised to create an efficient distributed storage system.
This paper proposes transparent blockchain codes to distribute blockchain history. The history data on each node is uncoded (transparent), but entire data obeys the soliton distribution. It not only keeps decentralization, but also brings low bandwidth consumption and good scalability
The importance of big data in machine learning cannot be overemphasized in recent times. Through the evolution of big data, most scientific technologies that relied heavily on enormous data in solving complex issues in human lives gained grounds; machine learning is an instance of these technologies. Various machine learning models that yield groundbreaking throughputs with high efficiency rates in predicting, detecting, classifying, discovering and acquiring in-depth knowledge about events that would otherwise be very difficult to ascertain have been made possible due to big data. Although big data has undoubtedly helped in the field of machine learning research ,over the years, its mode of acquisition has posed great challenge in industries,education and other agencies that obtained them for various purposes. This is because these large quantities of data cannot be stored on personal computers with limited storage capabicity but required the use of high storage capacity servers for effective storage. These servers may be owned by a group of companies or individuals who had the singular priviledge to modify the data in their possession as and when deemed relevant thus the creation of a centralized data storage environment. These were mostly refered to as the Third Parties (TP) in the data acquisition process. For the services they rendered, these trusted parties priced data in their possession expensively. The adverse effect is a limitation on various researches that could help solve a number of problems in human lives. It is worth mentioning that the security of these data being purchased expensively cannot be even assured limiting various researches that thrive on secured data. In order to curb these occurrences and have better machine learning models, the incorporation of Blockchain Technology databases into machine learning. This paper discusses the concept of big data, Machine Learning and Blockchains. It further discusses how Big data has impacted the Machine learning Community, the significance of Machine Learning and how the BlockChain Technology could be used similarly impact the Machine Learning Community. The aim of this paper is to encourge further research in incoporating the BlockChain Technology into Machine Learning.
In this paper we present a new 5-pass identification scheme with asymptotic cheating probability 1/2 based on the syndrome decoding problem. Our protocol is related to the Stern identification scheme but has a reduced communication cost compared to previous code-based zero-knowledge schemes, moreover our scheme permits to obtain a very low size of public key and secret key. The contribution of this paper is twofold, first we propose a variation on the Stern authentication scheme which permits to decrease asymptotically the cheating probability to 1/2 rather than 2/3 (and very close to 1/2 in practice) but with less communication. Our solution is based on deriving new challenges from the secret key through cyclic shifts of the initial public key syndrome; a new proof of soundness for this case is given Secondly we propose a new way to deal with hashed commitments in zero-knowledge schemes based on Stern's scheme, so that in terms of communication, on the average, only one hash value is sent rather than two or three. Overall our new scheme has the good features of having a zero-knowledge security proof based on well known hard problem of coding theory, a small size of secret and public key (a few hundred bits), a small calculation complexity, for an overall communication cost of 19kb for authentication (for a $2^{16}$ security) and a signature of size of 93kb (11.5kB) (for security $2^{80}$), an improvement of 40% compared to previous schemes based on coding theory.