We study lossy compression of a finite statement source generated in a fixed deductive environment. The source symbols are statements in a knowledge base endowed with a shared proof system, and reconstruction fidelity is measured by preservation of deductive closure rather than by symbolwise equality. Fixing the proof system and a canonical scan order yields a decomposition of the source alphabet into an irredundant core and redundant stored consequences. At zero distortion, each core symbol induces a set of distortion-free reconstructions. In the nonconfusable (disjoint-core) regime, we show that the minimum zero-distortion rate equals the source mass of the core times the entropy of the source conditioned on that core. In the general confusable-core regime, we characterise the exact zero-distortion rate via a hypergraph-entropy quantity induced by jointly realisable core subsets, with a reduction to Korner-style graph entropy under a natural pairwise realisability condition. For reconstruction alphabets contained in the deductive closure of the source knowledge base, we further prove that the full rate-distortion function depends only on the core, so redundant states are invisible to both rate and distortion. Finally, when the decoder is limited to a bounded inference-depth budget (a bounded number of iterations of the immediate-consequence operator), we obtain an exact rate-depth-distortion characterisation. Under an additional order-robustness assumption identifying the chosen core with the order-free essential set, this characterisation interpolates between classical symbolwise compression and unconstrained deductive compression.
This paper introduces the Quantum Tensor Sequence (.qtsq) format, a universal file format built to compress any kind of data — whether it's images, audio, video, text, structured data, or raw binary. Instead of treating everything as a generic stream of bytes like most compressors do, .qtsq looks at what the data actually is before deciding how to compress it. An internal component we call the "Spaghettification Engine" analyzes the input, figures out which of 16 data types it belongs to, and picks the best compression strategy for it: Iterated Function Systems (IFS) for images, Discrete Fourier Transform (DFT) for audio and signals, dictionary-schema encoding for text and structured data, and procedural seed generation for binary data. Everything is packed into a single 80-byte header that supports 11 features: type-aware compression, lazy partial decompression, AES-256-GCM encryption, Schnorr zero-knowledge proofs, Reed-Solomon error correction, inter-file deduplication through wormhole links, compressed-domain differential updates, multi-resolution quality scaling, and adaptive size thresholds. The whole thing is organized around a five-layer architecture inspired by black hole physics — each region of the black hole maps to a stage of the compression pipeline. As far as we know, no existing file format brings all of these capabilities together in one place. Based on the theoretical properties of the algorithms involved, we expect compression ratios somewhere between 18:1 and 55:1 on mixed-type data. Real-world benchmarks using the reference implementation will follow in a separate paper.
Michele Battagliola, Laura Mattiuz, Alessio Meneghetti
Abstract The Vector Oblivious Linear Evaluation in the Head (VOLEitH) paradigm has proven to be a versatile tool to design zero-knowledge proofs and signatures in post-quantum cryptography. In this paper, we propose three VOLE-friendly modellings for Proofs of Knowledge (PoK) of a solution of an instance of the Linear Code Equivalence Problem (LEP). For the first two schemes, we propose two new reductions from LEP to the Multivariate Quadratic (MQ) problem, that may be of independent interest for the cryptanalysis of LEP. Instead, the last model is obtained by generalizing a recent work by Bettaieb et al. to the context of monomial matrices instead of permutation matrices. While our proposed schemes exhibit larger signature sizes compared to LESS, they improve the computational efficiency, reducing the overall complexity from $$O(n^3)$$ to $$O(n^2\log n )$$ and $$O(n^2\log ^2 n )$$ , where n is the length of the code.
Compression algorithms and functions have been extensively utilized in various applications, e.g., in digital storage and communication. In recent years and with the popularity of machine learning applications, researchers have utilized compression techniques for addressing key problems in machine learning, e.g., for compressing artificial neural networks or for optimizing KV-cache memory in LLMs. Due to extensive applications of compression algorithms in different domains, a whole new era of innovations and applications for data compression algorithms can be envisioned. In this article, we discuss that compression functions with interesting properties, e.g., fully homomorphic compression (FHC) algorithms, can have applications beyond compressing data. FHC algorithms can potentially enable performing computation on compressed (and encrypted) data. Thus, fully homomorphic compression techniques can be used for reducing the computational and communication costs of compute and communication-intensive workloads, such as fully homomorphic encryption (FHE) & zero-knowledge proof (ZKP) applications, (secure) vector databases (VDBs and SVDBs), blockchain-based technologies, image and video processing, privacy-preserving or private LLMs, and LLM & AI inference, etc.
Zero-Knowledge Proofs (ZKP) and Homomorphic Encryption (HE) are crucial for data privacy in applications like cloud, blockchain, and analytics. However, the real-world adoption often faces performance challenges, particularly in the execution of the Number Theoretic Transform (NTT) required for polynomial multiplication involving sizes beyond \(2^{20}\) and large integer widths (e.g., 256 bits). FPGAs offer a promising platform for acceleration, but efficiently implementing large-size NTTs remains difficult due to the limited on-chip resources. The widely adopted four-step NTT method, used to relieve the need for large on-chip memory, introduces performance bottlenecks. Initially, the traditional dataflow NTT architecture may not fully exploit available compute capability, which hinders achieving peak performance. Furthermore, during the matrix transpose phase, the non-sequential access to external High-Bandwidth Memory (HBM) causes inefficiency. To address these challenges, we introduce HiFA, an FPGA-based automatic accelerator framework designed for high-performance and flexible large-size NTT computations. HiFA utilizes a stacked NTT architecture for high parallelism, maximizing HBM throughput. It supports various decomposed polynomial sizes via a novel reordering module. Additionally, a specialized cyclic shuffle module is integrated to optimize data movement during the matrix transpose step, alleviating random memory access delay. HiFA also provides an automatic Design Space Exploration (DSE) framework that identifies optimal four-step decomposition parameters and generates corresponding hardware configurations. Our experiments show that the FPGA implementation of HiFA achieves an average speedup of 2.97× and up to 7.25× improvement in latency over prior state-of-the-art FPGA solutions. Compared to prior GPU-based methods, HiFA achieves an average energy efficiency gain of 2.24×.
Assume that, given a sequence of n integers from 1 to n arranged in random order, we want to sort them, provided that the only acceptable operation is a prefix reversal, which means to take any number of integers (sub-sequence) from the left of the sequence, reverse the order of the sub-sequence, and return them to the original sequence. This problem is called “pancake sorting,” and sorting an arbitrary sequence with the minimum number of operations restricted in this way is known to be NP-hard. In this paper, we consider applying the concept of zero-knowledge proofs to the pancake sorting problem. That is, we design card-based zero-knowledge proof protocols in which a user (the prover) who knows how to sort a given sequence with ℓ operations can convince another user (the verifier) that the prover knows this information without divulging it.
Cryptocurrency price prediction has become crucial for informed trading decisions due to the volatile nature of assets like Bitcoin, Ethereum, Ripple, and Litecoin. Traditional methods like ARIMA and GARCH struggle with this volatility, while modern approaches such as machine learning and deep learning provide better accuracy. This study evaluates advanced models, including LSTM, GRU, and Light GBM, to predict cryptocurrency prices and assess trading strategies before and after the COVID-19 pandemic. GRU and LSTM excel at identifying patterns in price data, with GRU performing best for Ripple. Ensemble methods like Light GBM proved highly accurate for Bitcoin and Ethereum across time periods. Simpler models like RNN were sufficient for Ripple and Litecoin. The COVID-19 pandemic significantly impacted market dynamics, emphasizing the importance of precise predictions. Trading strategies based on model predictions showed that ensemble methods like Light GBM yielded the highest profitability post-pandemic. The findings highlight the need to tailor models to specific cryptocurrencies and market conditions. Improved deep learning tools can enhance trading efficiency and provide actionable insights for investors and policymakers. Future research could focus on predicting multiple cryptocurrencies simultaneously and optimizing portfolio-based trading strategies. Key Words: LSTM, ARIMA, GARCH, RNN
Security protocols, protocols to achieve consensus, those for maintaining memory consistency and coherence, distributed ledgers, multi-party computation, and many similar software systems are examples of distributed message-passing based computation. Ensuring correctness of such distributed systems is a challenging problem for many automatic verification approaches. The deductive verification approach for reasoning about such systems involves computing a program invariant, i.e., an expression evaluates to true for every reachable program state. Several approaches for synthesizing invariants are dynamic, i.e., runs of the program and ancillary information such as target safety properties are used to learn an invariant expression. However, most existing approaches invoke a model checker (or a theorem prover) within the synthesis loop, which makes these approaches depend on the scalability of the verification tools. In this paper, we propose a counterexample-guided inductive synthesis approach called RunVS which learns invariant expressions from program runs, but without information such as target safety properties, and without invoking a model checker/theorem prover for validation. The synthesis approach pairs a decision-tree (DT) based method with a data augmentation technique: DT-learning provides an expression that classifies observed states from augmented states that are speculated to be unreachable. Validation of the learned invariant is performed by sampling program runs and states; any run that invalidates the invariant results in counterexamples used to revises the invariant. As there is no formal proof that the learned artifact is a true invariant, we call such an expression a likely invariant. An important user input to synthesis is often the set of predicates that comprise the invariant expression; we use a novel integration with a large language model (LLM) and prompt it to provide likely predicates to be used. We show empirical results of our approach on several distributed protocols implemented in the Promela modeling language.
Abstract We propose a generic compiler that can convert any zero-knowledge (ZK) proof for SIMD circuits to general circuits efficiently, and an extension that can preserve the space complexity of the proof systems. Our compiler can immediately produce new results improving upon state of the art. By plugging in our compiler to Antman, an interactive sublinear-communication protocol, we improve the overall communication complexity for general circuits from $$\mathcal {O}(C^{3/4})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>C</mml:mi> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> to $$\mathcal {O}(C^{1/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>C</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Our implementation shows that for a circuit of size $$2^{27}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>27</mml:mn> </mml:msup> </mml:math> , it achieves up to $$83.6\times $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>83.6</mml:mn> <mml:mo>×</mml:mo> </mml:mrow> </mml:math> improvement on communication compared to the state-of-the-art implementation. Its end-to-end running time is at least $$70\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>70</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> faster in a 10Mbps network. Using the recent results on compressed $$\varSigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Σ</mml:mi> </mml:math> -protocol theory, we obtain a discrete-log-based constant-round zero-knowledge argument with $$\mathcal {O}(C^{1/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>C</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> communication and common random string length, improving over the state of the art that has linear-size common random string and requires heavier computation. We improve the communication of a designated n -verifier zero-knowledge proof from $$\mathcal {O}(nC/B+n^2B^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mi>C</mml:mi> <mml:mo>/</mml:mo> <mml:mi>B</mml:mi> <mml:mo>+</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:msup> <mml:mi>B</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> to $$\mathcal {O}(nC/B+n^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mi>C</mml:mi> <mml:mo>/</mml:mo> <mml:mi>B</mml:mi> <mml:mo>+</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . To demonstrate the scalability of our compilers, we were able to extract a commit-and-prove SIMD ZK from Ligero and cast it in our framework. We also give one instantiation derived from LegoSNARK, demonstrating that the idea of CP-SNARK also fits in our methodology.
Pedro García-Cereijo, Gabriel Fernández-Blanco, Paula Fraga‐Lamas, Tiago M. Fernández‐Caramés
The deterministic nature of blockchains presents a significant challenge to pseudo-random number generation. Conventional seed-based random number generation methods may not be suitable for deterministic environments as they may be predictable and susceptible to attacks. To address this challenge, this paper proposes the integration of a pseudo-random number generation oracle for the nodes of an Ethereum network. Such an oracle acts as an external provider of pseudo-random numbers, generating random data by using the Fortuna algorithm, which can be used by smart contracts and decentralized applications on the blockchain. However, the integration of an oracle raises additional security and reliability concerns as it relies on a central node that impairs the decentralization of the blockchain and depends on the ability of the oracle to provide unpredictable and non-tampered pseudo-random numbers. The presented implementation can be used in different sectors, such as games of chance, random selection and other scenarios where randomness is essential to guarantee fairness and security. Thus, the integration of a pseudo-random number generation oracle into a Ethereum network can significantly improve the functionality and security of such decentralized applications. In order to show the performance of the proposed system, a comparison is presented that evaluates the security improvements with respect to traditional randomization methods within smart contracts.
Super-instructions are a crucial optimization method for interpreters, as they combine multiple basic instructions into single specialized operations. The optimization technique reduces dispatch overhead and enables further optimizations in the synthesized operation code for a super-instruction. However, due to combinatorial explosion, identifying super-instructions is a complex selection problem. This paper presents a novel approach for the automated synthesis of super-instructions using a combination of offline dictionary-based compression algorithms and greedy heuristics. Our method addresses the common issue of overlap between super-instructions, which previous approaches often overlook. Additionally, we introduce a meta-compiler for the Ethereum Virtual Machine (EVM) that automatically generates a new interpreter incorporating the super-instructions. The super-instructions generated with our approach result in an 8.45% speedup for the interpreter component of the EVM.
Bit-decomposition-based zero-knowledge range proofs in the discrete logarithm (DLOG) setting with a transparent setup, e.g., Bulletproof (IEEE S&P 18), Flashproof (ASIACRYPT 22), and SwiftRange (IEEE S&P 24), have garnered widespread popularity across various privacy-enhancing applications. These proofs aim to prove that a committed value falls within the non-negative range [0, 2^N-1] without revealing it, where N represents the bit length of the range. Despite their prevalence, the current implementations still suffer from suboptimal performance. Some exhibit reduced communication costs at the expense of increased computational costs while others experience the opposite. Presently, users are compelled to utilize these proofs in scenarios demanding stringent requirements for both communication and computation efficiency. In this paper, we introduce, FlashSwift, a stronger DLOG-based logarithmic-sized alternative. It stands out for its greater shortness and significantly enhanced computational efficiency compared with the cutting-edge logarithmic-sized ones for the most common ranges where N is no more than 64. It is developed by integrating the techniques from Flashproof and SwiftRange without using a trusted setup. The substantial efficiency gains stem from our dedicated efforts in overcoming the inherent incompatibility barrier between the two techniques. Specifically, when N=64, our proof achieves the same size as Bulletproof and exhibits 1.1 times communication efficiency of SwiftRange. More importantly, compared with the two, it achieves 2.3 times and 1.65 times proving efficiency, and 3.2 times and 1.7 times verification efficiency, respectively. At the time of writing, our proof also creates two new records of the smallest proof sizes, 289 bytes and 417 bytes, for 8-bit and 16-bit ranges among all the bit-decomposition-based ones without requiring trusted setups. Moreover, to the best of our knowledge, it is the first configurable range proof that is adaptable to various scenarios with different specifications, where the configurability allows to trade off communication efficiency for computational efficiency. In addition, we offer a bonus feature: FlashSwift supports the aggregation of multiple single proofs for efficiency improvement. Finally, we provide comprehensive performance benchmarks against the state-of-the-art ones to demonstrate its practicality.
Elvira Albert, María García de la Banda, Alejandro Hernández-Cerezo, Alexey Ignatiev · 6 authors
Given a loop-free sequence of instructions, superoptimization techniques use a constraint solver to search for an equivalent sequence that is optimal for a desired objective. The complexity of the search grows exponentially with the length of the solution being constructed and the problem becomes intractable for large sequences of instructions. This paper presents a new approach to superoptimizing stack-bytecode via three novel components: (1) a greedy algorithm to refine the bound on the length of the optimal solution; (2) a new representation of the optimization problem as a set of weighted soft clauses in MaxSAT; (3) a series of domain-specific dominance and redundant constraints to reduce the search space for optimal solutions. We have developed a tool, named S uper S tack , which can be used to find optimal code translations of modern stack-based bytecode, namely WebAssembly or Ethereum bytecode. Experimental evaluation on more than 500,000 sequences shows the proposed greedy, constraint-based and SAT combination is able to greatly increase optimization gains achieved by existing superoptimizers and reduce to at least a fourth the optimization time.
Multiple sequence alignment (MSA) is a fundamental algorithm in bioinformatics. In a situation when the alignment might need to be protected while revealing the other information such the input sequences and the alignment score, zero knowledge proof can be used. In this paper, a validator checks the consistency between the input sequence and the alignment, and between the alignment and the alignment score. The validator is written in Circom language which will be compile into a circuit. Using a zero knowledge prove system called zkSNARK, a cryptographic proof is generates for the circuit and its input. This proof demonstrates that all inputs are consistent without revealing the actual alignment.
Pengfei Huang, Xiaojun Ren, Teng Huang, Arthur Sandor Voundi Koe · 6 authors
Node synchronization is essential for the stability of the Bitcoin network. Critics have raised doubts about the ability of a new node to quickly and efficiently synchronize with the Bitcoin network and alleviate the storage pressure from existing full nodes to stockpile new data. Basic pruning and other techniques have been explored to address these concerns but have been insufficient to reduce node synchronization delay and effectively suppress the growth of synchronized data. In this study, we propose SnapshotPrune, a novel pruning and synchronization protocol that achieves fast node bootstrapping in the Bitcoin blockchain. Real Bitcoin historical data are leveraged to measure the synchronization time and monitor the network traffic during node bootstrapping. The protocol requires data downloads that are 99.70% less than Bitcoin Core, 81% less than CoinPrune, and 60% less than SnapshotSave, thereby saving 97.23% of download time. Findings show that the proposed design enhances the storage efficiency and reduces the node synchronization delay compared with existing techniques. We hypothesize that the efficiency of this protocol increases with the block height.
<abstract> <p>This paper proposes a deterministic nonce generation technique to address the catastrophic issues associated with nonce reuse in message signing and to enhance the efficiency of Schnorr multi-signature schemes. Additionally, this research aims to reduce computational complexity and bandwidth requirements in digital and multi-signature schemes while maintaining robust security against common attacks. The proposed method was inspired by the EdDSA approach. The methodology includes a comprehensive mathematical analysis of digital signature algorithms and a rigorous examination of their vulnerabilities to well-known cryptographic attacks. This analysis evaluates the effectiveness and robustness of the proposed nonce generation technique within the frameworks of the Schnorr digital signature and the two-round MuSig schemes. Techniques and tools employed in this research involve deterministically generating nonces by hashing the private key and subsequently hashing the result with the message. Furthermore, it is proposed to exclude the public nonce R from the challenge calculations and to allow signers to directly prove possession of their secret keys through the aggregated public key, thereby eliminating the need for non-interactive zero-knowledge (NIZK) proofs. The findings demonstrate significant reductions in computational complexity and operational requirements, thereby improving bandwidth efficiency and making this method well-suited for resource-constrained devices. The approach also exhibits strong resistance to various attacks, including nonce reuse, key cancellation, rogue keys, and virtual machine rewinding.</p> </abstract>
Open access
Handwritten Text Recognition Techniques
Advanced Steganography and Watermarking Techniques
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.
A novel data structure that enables the storage and retrieval of linear array numeric data with logarithmic time complexity updates, range sums, and rescaling is introduced and studied. Computing sums of ranges of arrays of numbers is a common computational problem encountered in data compression, coding, machine learning, computational vision, and finance, among other fields. Efficient data structures enabling log n updates of the underlying data (including range updates), queries of sums over ranges, and searches for ranges with a given sum have been extensively studied (n being the length of the array). Two solutions to this problem are well-known: Fenwick trees (also known as Binary Indexed Trees) and Segment Trees. The new data structure extends the capabilities for the first time to further enable multiplying (rescaling) ranges of the underlying data by a scalar as well in log n. Scaling by 0 can be enabled, with the effect that subsequent updates may take (log n)2time. The new data structure introduced here consists of a pair of interacting Fenwick tree-like structures, one of which holds the unscaled values and the other of which holds the scalars. Experimental results demonstrating performance improvements for the multiplication operation on arrays from a few dozen to over 30 million data points are discussed. This research was done as part of Ajna Labs in the course of developing a decentralized finance protocol. It enables an efficient on-chain encoding and processing of an order book-like data structure used to manage lending, interest, and collateral.
Blockchain received a vast amount of attention in recent years and is still growing. The second generation of blockchain, such as Ethereum, allows execution of almost any program in Ethereum Virtual Machine (EVM), making it a global protocol for distributed applications. The code deployment and each operation performed in EVM cost the network fee called gas, which price varies and can be significant. That is why code optimization and well-chosen algorithms are crucial in programming on the blockchain. This paper evaluates the gas usage of several exact pattern matching algorithms on the Ethereum Virtual Machine. We also propose an efficient implementation of the algorithms in the Solidity/YUL language. We evaluate the gas fees of all the algorithms for different parameters (such as pattern length, alphabet size, and text size). We show a significant gas fee and execution time reduction with up to 22-fold lower gas usage and 55-fold speed-up comparing to StringUtils (a popular Solidity string library).
In this paper we describe protocols which use a standard deck of cards to provide a perfectly sound zero-knowledge proof for Hamiltonian cycles and Flow Free puzzles. The latter can easily be extended to provide a protocol for a zero-knowledge proof of many-to-many k-disjoint path coverings.
In this note, we report several solutions to the STARK-Friendly Hash Challenge: a competition with the goal of finding collisions for several hash functions designed specifically for zero-knowledge proofs (ZKP) and multiparty computations (MPC). We managed to find collisions for 3 instances of 91-bit hash functions. The method used is the classic parallel collision search with distinguished points from van Oorshot and Wiener (1994). As this is a general attack on hash functions, it does not exhibit any particular weakness of the chosen hash functions. The crucial part is to optimize the implementations to make the attack cost realistic, and we describe several arithmetic tricks.
Smart contracts are autonomous software executing predefined conditions. Two of the biggest advantages of the smart contracts are secured protocols and transaction costs reduction. On the Ethereum platform, an open-source blockchain-based platform, smart contracts implement a distributed virtual machine on the distributed ledger. To avoid denial of service attacks and monetize the services, payment transactions are executed whenever code is being executed between contracts. It is thus natural to investigate if predictive analysis is capable to forecast these interactions. We have addressed this issue and propose an innovative application of the tensor decomposition CANDECOMP/PARAFAC to the temporal link prediction of smart contracts. We introduce a new approach leveraging stochastic processes for series predictions based on the tensor decomposition that can be used for smart contracts predictive analytics.
Mary Maller, Sean Bowe, Markulf Kohlweiss, Sarah Meiklejohn
Ever since their introduction, zero-knowledge proofs have become an important tool for addressing privacy and scalability concerns in a variety of applications. In many systems each client downloads and verifies every new proof, and so proofs must be small and cheap to verify. The most practical schemes require either a trusted setup, as in (pre-processing) zk-SNARKs, or verification complexity that scales linearly with the complexity of the relation, as in Bulletproofs. The structured reference strings required by most zkSNARK schemes can be constructed with multi-party computation protocols, but the resulting parameters are specific to an individual relation. Groth et al. discovered a zk-SNARK protocol with a universal structured reference string that is also updatable, but the string scales quadratically in the size of the supported relations.<br/> <br/>Here we describe a zero-knowledge SNARK, Sonic, which supports a universal and continually updatable structured reference string that scales linearly in size. We also describe a generally useful technique in which untrusted “helpers” can compute advice that allows batches of proofs to be verified more efficiently. Sonic proofs are constant size, and in the “helped” batch verification context the marginal cost of verification is comparable with the most efficient SNARKs in the literature<br/>