In this paper we show that the generalization error of AdaBoost is $Θ\big(\tfrac{d\ln(nγ^{2}/d)}{nγ^2}+\tfrac{\ln(1/δ)}{n}\big)$, where $γ$ is the advantage guaranteed by the weak learner, $d$ is the VC-dimension of the class containing the weak hypotheses, $n$ is the sample size, and $δ$ is the confidence parameter. The contribution of this paper is the upper bound; the matching lower bound follows from prior work. The upper bound proof follows by combining the known fact that AdaBoost outputs a voting classifier whose voting function has zero empirical $γ/2$-margin loss with what is, to the best of our knowledge, a new margin-based generalization bound for voting classifiers.
Executive Summary This paper introduces a deterministic mathematical framework for nested learning designed to eliminate catastrophic forgetting in continuous learning systems. Standing as the first Proof of Concept (POC) of its type ever made, it completely flips the traditional AI safety paradigm. Instead of letting all data into a model and relying on post-hoc, probabilistic safeguards or heuristic mitigations to fix corruption after it occurs, this architecture implements an immutable mathematical gatekeeper called the H2E Sheriff. By filtering incoming data at the doorstep, it ensures that incoherent or corrupting inputs are rejected before they can ever modify or overwrite stored knowledge, ensuring absolute preservation of prior learning by architectural design. Theoretical Foundation & Key Components The framework anchors AI learning governance to absolute mathematical ground truths rather than learned data distributions or human preferences. Arithmetic Spectral Theory (AST): Synthesizes four classical transforms—Laplace, Euler, Fourier, and Mellin—into a single spectral operator, the L-EFM operator. At the critical line ($\sigma = 0.5$), the normalized magnitude of this operator evaluates to exactly 1 over prime sets, creating a universal coherence invariant. Empirical testing across diverse finite prime-related sets demonstrates that the system achieves a steady-state spectral coherence of exactly 0.5 at this critical line. Safety Thresholds ($\Lambda$): Computed directly from the Euler attenuation product over the first $n$ primes rather than being trained on data. The framework identifies $\Lambda_{12} = 0.9944590549$ as the primary perimeter gate boundary. The H2E Sheriff Manifold: Maps real-valued input embeddings onto the product manifold $\mathbb{H}^2 \times SPD(3)$. Incoming data is geometrically evaluated against a prime-anchored reference center ($x^*$) constructed from normalized prime coordinates. Spectral Risk Overlap Index (SROI): A metric determining an embedding's proximity to the coherent reference center on the manifold. Inputs are processed via a strict decision rule: accepted into the knowledge base if $SROI > \Lambda$, and conservatively rejected if $SROI \le \Lambda$. Experimental Validation The framework was validated using 10-dimensional vectors with controlled noise levels under a deterministic seed and 50-decimal-place precision. Threshold Discrimination: Calibration experiments confirmed that the $\Lambda_{12}$ threshold cleanly separates stable, coherent embeddings (noise $< 1.0$) from erratic, incoherent ones (noise $\ge 2.0$). Knowledge Base Integrity: During nested learning protocols featuring mixed streams of inputs, the H2E Sheriff successfully blocked corrupting data. In a stream of 30 inputs, all 12 incoherent attempts were rejected at the gate. The final knowledge base retained an average SROI of 0.996076, demonstrating zero degradation of stored knowledge and complete preservation of prior learning. Current Limitations & Future Work As the first exploratory POC mapping absolute prime structures to continuous AI safety boundaries, the paper transparently identifies clear vectors for future scaling and development: Dimensionality & Scaling: The initial validation operates on 10-dimensional embeddings and compact knowledge bases. Because the geodesic distance and matrix logarithm calculations on $SPD(3)$ scale cubically ($O(n^3)$), evaluation on large-scale, high-dimensional neural network workloads remains untested. Hyperparameter Selection: The choices for the scaling factor ($\tau = 50$) and the optimal prime set size ($n = 12$) are empirically driven for this distribution and lack a generalized analytical method for automatic selection in new problem domains. Modality Generalization: The threshold was calibrated on Gaussian noise and has not yet been exposed to complex embedding distributions like large language model tokens or image feature vectors. Neural Network Integration: The current implementation acts as a post-hoc filter on static vectors. Integrating this rigid mathematical gatekeeping into backpropagation-based training loops—where internal representations continually shift—remains an open architectural challenge. Theoretical Completeness: The core spectral coherence value of 0.5 at $\sigma = 0.5$ is an empirical invariant observed across finite sets; a formal, universal proof extending this to all infinite prime sets or establishing its absolute equivalence to the Riemann Hypothesis is not yet established.
We describe a protocol that produces byte-identical outputs from frontier-scale language model inferenceand binds each output to a portable, offline-verifiable signed receipt. The construction has three parts.First, an inference substrate that runs models up to seventy-two billion dense parameters and forty-sevenbillion mixture-of-experts active parameters on NVIDIA H100, with cross-vendor extension to AMDInstinct MI300X. Output hashes match byte-for-byte across fresh process launches in every configurationmeasured; at single-GPU bf16 with eager attention the AMD and NVIDIA hashes are themselves byte-identical, including over fifty-one tokens of compounding frontier-scale generation, and at two-GPUtensor-parallel they differ as predicted by the underlying NCCL-ring versus RCCL-fabric all-reducetopology. Both are individually deterministic. Second, a canonical CBOR receipt schema with an Ed25519signature over a domain-separated message, implemented in Go, Python, and Rust, with cross-languagebyte-identity verified end-to-end and AMD-produced receipts verifying byte-for-byte through a Rustverifier built on x86 NVIDIA hardware. Third, a probabilistic spot-check verifier that re-executes asmall sample of receipts and rejects on mismatch; we prove a soundness lemma of the form 1−(1−f )kand validate it empirically across seventy adversary-verifier configurations with seven hundred thousandMonte Carlo trials. Verification costs about eighty microseconds per receipt on a single core. Eleventhousand sequential warm-model inferences ran without a single byte-identity failure. The contribution isthe construction itself: a primitive that gives issuer-independent fabrication soundness for AI inference atproduction cost, without a hardware-vendor dependency and without zero-knowledge proofs.
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.
We present NanoZK, a zero-knowledge proof system for verifiable LLM inference: clients and third-party auditors check that a provider executed the advertised model on a committed input without learning weights or activations. NanoZK introduces a layerwise proof framework that decomposes transformer inference into independently provable layers linked by a SHA-256 commitment chain, yielding constant-size sub-circuit proofs (3.5-3.7 KB; about 83 KB total at L=12), comparable in total size to and substantially more parallelizable than prior ZKML's monolithic 101-126 KB proofs. We prove compositional soundness and zero-knowledge under standard assumptions, design 16-bit lookup-table approximations for softmax, GELU, and normalization with measured perplexity degradation below 1e-4 across six model/dataset combinations, and add a Fisher-information-guided audit-budget triage as an efficiency tool (full soundness still requires verifying every layer). On CPU the MLP sub-circuit proves in about 6.3 s prove-only (about 43 s setup plus prove) with about 22 ms verification at any width; attention prove-only time scales from 0.9 s (d=16) to 184 s (d=256); full-block end-to-end proofs are measured to d=128, with a projected GPU time of about 68 s per block at d=768 from measured O(d^2) MSM scaling and a conservative 15-30x GPU-MSM speedup range based on Icicle's published 30x result for n >= 2^20 and extrapolated to the smaller-n regime. Privacy scope: NanoZK hides weights and activations from verifiers and auditors but does not hide the prompt from the prover; this is complementary to HE/MPC.
Guilhem Repetto, Nojan Sheybani, Gabrielle De Micheli, Farinaz Koushanfar
Privacy concerns in machine learning systems have grown significantly with the increasing reliance on sensitive user data for training large-scale models. This paper introduces a novel framework combining Probably Approximately Correct (PAC) Privacy with zero-knowledge proofs (ZKPs) to provide verifiable privacy guarantees in trustless computing environments. Our approach addresses the limitations of traditional privacy-preserving techniques by enabling users to verify both the correctness of computations and the proper application of privacy-preserving noise, particularly in cloud-based systems. We leverage non-interactive ZKP schemes to generate proofs that attest to the correct implementation of PAC privacy mechanisms while maintaining the confidentiality of proprietary systems. Our results demonstrate the feasibility of achieving verifiable PAC privacy in outsourced computation, offering a practical solution for maintaining trust in privacy-preserving machine learning and database systems while ensuring computational integrity.
We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible via an honest polynomial-time reduction to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends work by Saks and Santhanam (CCC 2022). (Saks and Santhanam showed that promise problems that can be reduced in this way to such an approximation of the Kolmogorov-random strings have (possibly interactive) zero-knowledge proof systems, and they did not address the converse implication.) We build on this to give new characterizations of Statistical Zero Knowledge SZK , as well as the related classes NISZK L and SZK L .
A set of multivariate polynomials is algebraically independent if they exhibit no non-trivial algebraic relations, and this notion is fundamental in algebra. When these polynomials are given as algebraic circuits, deciding algebraic independence has several applications in algebraic complexity theory. Over fields of zero (or exponentially large) characteristic, this problem is known to have an efficient randomized algorithm. Over finite fields of small characteristic, a sequence of works has culminated in showing that algebraic independence admits Arthur-Merlin proofs, in particular giving the complexity bound of AM∩coAM ([Guo et al., 2019]). We improve the complexity of deciding algebraic independence over finite fields by showing that it admits zero-knowledge proofs, in particular giving the upper bound of NISZK ⊆ AM∩coAM, the class of problems admitting non-interactive statistical zero-knowledge proofs. This is achieved by arguing that algebraically independent polynomials yield maps whose output distribution has high-entropy, while algebraically dependent polynomials yield maps with low-entropy. We can then reduce to the question of approximating entropy, which is a known NISZK-complete problem. We also more generally show that transcendence degree, which quantifies the independence of a set of possibly dependent polynomials, can be computed in NISZK.
In the face of the regulatory failure problem caused by blockchain hidden addresses, existing solutions often fall into a dilemma where 'privacy protection' and 'compliance review' are either one or the other.This paper proposes an innovative integration framework that transforms the behavioural elements in anti-money laundering and other legal provisions (such as 'high-frequency and small-scale transactions') into computable logic.Based on zero-knowledge proof technology, it generates verifiable credentials to determine whether the transaction behaviour is compliant without revealing the true identity of the address.Experiments on a public blockchain transaction dataset (elliptic) show that this framework achieves an average improvement of over 15% in core identification performance compared to traditional non-private rule-based methods, while maintaining an acceptable performance overhead.As a proof-of-concept validation conducted on a transparent dataset with simulated concealment, the actual performance may differ in native privacy-preserving chains.This research provides a new approach that combines legal rigor with technical feasibility for achieving effective on-chain behaviour supervision while protecting user privacy.
Federatívne učenie (FL) umožňuje spoločné trénovanie modelu bez priameho zdieľania údajov, ale často sa spolieha na silné predpoklady o čestnom správaní klienta a servera. To je dôvod, prečo štandardné FL protokoly poskytujú iba obmedzenú záruku ohľadom výpočtov na strane klienta, integrity odoslaných informácii, alebo ohľadom správnosti agregácie na strane servera. Táto diplomová práca skúma použitie systémov s nulovými znalosťami (ZKP) spolu s podpornými metódami na vytvorenie dôvery v FL prostredí. V tejto práci sa po úvode k FL a ZKP ďalej skúma prehľad existujúcich ZKP nástrojov v prostredí FL. Na základe tejto analýzy je vytvorená kategorizácia existujúcich prístupov FL založených na ZKP, ktorá je postavená najmä na cieľoch daného systému. Na základe identifikovaných možností zlepšenia práca navrhuje overiteľný protokol váženej agregácie. V tomto protokole je každý prijatý príspevok previazaný s autorizovanou váhou, prípustnou skrytou aktualizáciou, konzistentným váženým vstupom a výslednou aktualizáciou modelu, ktorú je možné verejne overiť prepočítaním. Tento protokol bol implementovaný ako prototyp s plne funkčnými kryptografickými komponentami. Následne je tento protokol vyhodnotený.
We introduce the Y.I.N. Mazari Ordering, a fundamental primitive for achieving verifiable differential privacy in federated learning systems. The ordering (noise → proof → encrypt → aggregate) is proven to be necessary—no efficient alternative exists—and universal across all encryption schemes, proof systems, and aggregation topologies. Patent pending: US 63/923,348, US 19/399,646, US 19/403,244 Keywords: Verifiable Differential Privacy, Federated Learning, Zero-Knowledge Proofs, Homomorphic Encryption, Privacy-Preserving Machine Learning
Zero-knowledge proofs of training (zkPoT) allow a party to prove that a model is trained correctly on a committed dataset without revealing any additional information about the model or the dataset. Existing zkPoT protocols prove the entire training process in zero knowledge; i.e., they prove that the final model was obtained in an iterative fashion starting from the training data and a random seed (and potentially other parameters) and applying the correct algorithm at each iteration. This approach inherently requires the prover to perform work linear to the number of iterations.
Thomas Haines, Rafieh Mosaheb, Johannes Müller, Reetika
Zero-Knowledge Proofs (ZKPs) are cryptographic building blocks of many privacy-preserving security protocols. An important research focus in this area is the development of post-quantum ZKPs. These are ZKPs whose security is reduced to computational hardness assumptions that are assumed to be intractable even by scalable quantum computers. In this paper, we study the post-quantum ZKPs of Jain, Krenn, Pietrzak, and Tentes (Asiacrypt 2012). These are the only ZKPs for proving arbitrary binary statements whose security reduces to the Learning Parity with Noise (LPN) problem-a very conservative post-quantum hardness assumption. We make the following contributions to further develop the potential and understanding of these ZKPs. First, we optimize the efficiency of the verifier by several orders of magnitude, making this part as computationally light as that of the prover. Second, we show that the only open source implementation of these ZKPs does not implement them correctly, allowing a malicious prover to convince the verifier of false statements. Third, we formally verify for the first time the security of these (optimized) ZKPs in EasyCrypt. Fourth, we show how these ZKPs can be used to construct the first code-based ZKP of shuffle and verifiable e- voting protocol.
Stefanos Chaliasos, Imam Al-Fath, Alastair F. Donaldson
Zero-knowledge proofs (ZKPs) have evolved from a theoretical cryptographic concept into a powerful tool for implementing privacy-preserving and verifiable applications without requiring trust assumptions. Despite significant progress in the field, implementing and using ZKPs via \emph{ZKP circuits} remains challenging, leading to numerous bugs that affect ZKP circuits in practice, and \emph{fuzzing} remains largely unexplored as a method to detect bugs in ZKP circuits. We discuss the unique challenges of applying fuzzing to ZKP circuits, examine the oracle problem and its potential solutions, and propose techniques for input generation and test harness construction. We demonstrate that fuzzing can be effective in this domain by implementing a fuzzer for \texttt{zk-regex}, a cornerstone library in modern ZKP applications. In our case study, we discovered \textit{$10$} new bugs that have been confirmed by the developers.
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.
In their recent breakthrough result, Slofstra and the second author show that there is a two-player one-round perfect zero-knowledge MIP* protocol for RE (STOC'24). We build on their result to show that there exists a succinct two-player one-round perfect zero-knowledge MIP* protocol for RE against dishonest verifiers with polylog question size and O(1) answer size, or with O(1) question size and polylog answer size. To prove our result, we study the three central compression techniques underlying the MIP*=RE proof (Ji et al. '20): question reduction, oracularization, and answer reduction. We show that question reduction preserves the perfect (as well as statistical and computational) zero-knowledge properties of the original protocol against dishonest verifiers, and oracularization and answer reduction preserve the perfect (as well as statistical and computational) zero-knowledge properties of the original protocol against honest verifiers. Secondly, we show that every constraint-constraint binary constraint system (BCS) nonlocal game, which provides a quantum information characterization of MIP*, can be converted to a synchronous constraint-variable BCS game to preserve perfect completeness for our compression. Lastly, we present a parametrized perfect-zero-knowledge transformation of MIP* protocols, which generalizes the transformation in (Slofstra and Kieran STOC'24) . This transformation allows us to preserve the zero-knowledge property against dishonest verifiers in the recursively oracularized protocols in our compression.
Zero-knowledge proofs introduce a mechanism to prove that certain computations were performed without revealing any underlying information and are used commonly in blockchain-based decentralized apps (dapps). This cryptographic technique addresses trust issues prevalent in blockchain applications, and has now been adapted for machine learning (ML) services, known as Zero-Knowledge Machine Learning (ZKML). By leveraging the distributed nature of blockchains, this approach enhances the trustworthiness of ML deployments, and opens up new possibilities for privacy-preserving and robust ML applications within dapps. This paper provides a comprehensive overview of the ZKML process and its critical components for verifying ML services on-chain. Furthermore, this paper explores how blockchain technology and smart contracts can offer verifiable, trustless proof that a specific ML model has been used correctly to perform inference, all without relying on a single trusted entity. Additionally, the paper compares and reviews existing frameworks for implementing ZKML in dapps, serving as a reference point for researchers interested in this emerging field. • An analytical and synthetic review of core on-chain ZKML concepts, supported by an extensive examination of both white and grey literature, establishing a foundational understanding of the field. • Through a detailed analysis, modelling, and descriptive approaches, the paper outlines the processes integral to on-chain ZKML. The study is focused on two distinct frameworks – EZKL and Orion , highlighting the differences between the two approaches, as well as the difference between the underlying ZKP systems, where the former framework is based on zk-SNARKs and the latter on zk-STARKs. • A laboratory experiment, coupled with a comparative analysis and use case execution comparison, was conducted to implement basic neural networks (NNs) across the two chosen frameworks, highlighting their capabilities and limitations in supporting on-chain ZKML.
Chenhao Shi, Ruibang Liu, H. B. Chen, Guoqiang Li · 5 authors
The communities of blockchains and distributed ledgers have been stirred up by the introduction of zero-knowledge proofs (ZKPs). Originally designed as a solution to privacy issues, ZKPs have now evolved into an effective remedy for scalability concerns. To enable ZKPs, Rank-1 Constraint Systems (R1CSs) offer a verifier for bilinear equations. In order to accurately and efficiently represent R1CSs, several language tools, such as Circom, Noir, and Snarky, have been proposed to automate the compilation of advanced programs into R1CSs. However, due to the flexible nature of R1CS representation, there can be significant differences in the compiled R1CS forms generated from circuit language programs with the same underlying semantics. To address this issue, this article puts forth a dataflow-based R1CS paradigm algorithm, which produces a standardized format for different R1CS instances with identical semantics. Additionally, we present an R1CS benchmark, and our experimental evaluation demonstrates the efficacy of our methods.
Haochen Sun, J. Li, Change Institutions to: University of Waterloo
The recent surge in artificial intelligence (AI), characterized by the prominence of large language models (LLMs), has ushered in fundamental transformations across the globe. However, alongside these advancements, concerns surrounding the legitimacy of LLMs have grown, posing legal challenges to their extensive applications. Compounding these concerns, the parameters of LLMs are often treated as intellectual property, restricting direct investigations. In this study, we address a fundamental challenge within the realm of AI legislation: the need to establish the authenticity of outputs generated by LLMs. To tackle this issue, we present zkLLM, which stands as the inaugural specialized zero-knowledge proof tailored for LLMs to the best of our knowledge. Addressing the persistent challenge of non-arithmetic operations in deep learning, we introduce tlookup, a parallelized lookup argument designed for non-arithmetic tensor operations in deep learning, offering a solution with no asymptotic overhead. Furthermore, leveraging the foundation of tlookup, we introduce zkAttn, a specialized zero-knowledge proof crafted for the attention mechanism, carefully balancing considerations of running time, memory usage, and accuracy. Empowered by our fully parallelized CUDA implementation, zkLLM emerges as a significant stride towards achieving efficient zero-knowledge verifiable computations over LLMs. Remarkably, for LLMs boasting 13 billion parameters, our approach enables the generation of a correctness proof for the entire inference process in under 15 minutes. The resulting proof, compactly sized at less than 200 kB, is designed to uphold the privacy of the model parameters, ensuring no inadvertent information leakage.
Conventionally, organizations have used Privileged Access Management (PAM) techniques to secure, control, and monitor access to their critical information and resources. The PAM concepts have envisioned designing protocols that help protect user accounts that are deemed to have access to sensitive data ?the most valuable asset of a business. While in the past these techniques have proven vital to data protection and security, the onset of increasingly sophisticated technologies and more determined malicious actors warrants a change of data control and privacy strategies. It becomes impossible to secure a system to achieve 100 percent efficiency. Any system that is attached to the internet is vulnerable to cyberattacks. Hackers have numerous ways to compromise systems if traditional boundary security mechanisms are deployed. Detecting an intrusion in such a setup becomes increasingly challenging if an attacker successfully breaches that boundary layer of defense. Since traditional authentication and authorization might not be reliable in network systems, the zero - knowledge proof model comes in handy. Adding the zero - knowledge proof to the PAM to authenticate users or members and disclose or anonymize them through decentralized identifiers helps in solving the identification and privacy protection problem. We propose a PAM and zero - knowledge proof - inspired approach to address the authentication, data security, and privacy concerns. A zero - knowledge proof is a method that allows the prover to prove to the verifier that they know a certain information without disclosing it.
Standard probabilistic models face fundamental challenges such as data scarcity, a large hypothesis space, and poor data transparency. To address these challenges, we propose a novel probabilistic model of data-driven temporal propositional reasoning. Unlike conventional probabilistic models where data is a product of domain knowledge encoded in the probabilistic model, we explore the reverse direction where domain knowledge is a product of data encoded in the probabilistic model. This more data-driven perspective suggests no distinction between maximum likelihood parameter learning and temporal propositional reasoning. We show that our probabilistic model is equivalent to a highest-order, i.e., full-memory, Markov chain, and it can also be viewed as a hidden Markov model requiring no distinction between hidden and observable variables. We discuss that limits provide a natural and mathematically rigorous way to handle data scarcity, including the zero-frequency problem. We also discuss that a probability distribution over data generated by our probabilistic model helps data transparency by revealing influential data used in predictions. The reproducibility of this theoretical work is fully demonstrated by the included proofs.