We study distributed zero-knowledge proofs, introduced by Bick, Kol, and Oshman (SODA 2022). While distributed interactive proofs have advanced rapidly in recent years, general-purpose techniques for distributed zero-knowledge remain scarce and mostly problem-specific. We address this gap by introducing distributed statistical zero-knowledge, requiring that each node's view be simulatable up to negligible statistical distance, and by lifting the robust Sumcheck protocol (Lund, Fortnow, Karloff, and Nisan; FOCS 1990) into a modular primitive for distributed zero-knowledge proofs.
Intuizione scientifica: fare competere ipergrafi di ipergrafi, potrebbe portare ad un'ottimizzazione dei sistemi, oppure rischia di corromperli imponendo il senso comune? La competizione adversarial di ipergrafi di ipergrafi sarà la successiva evoluzione di questo paper. English: Abstract: This preprint formally introduces Hypergraph Adversarial Debate (HAD), an innovative multi-agent framework operating on higher-order knowledge structures modeled via hypergraphs (ℋ). While traditional adversarial machine learning paradigms on hypergraphs rely heavily on continuous, gradient-driven statistical optimizations, HAD conceptualizes epistemic robustness as a formal, discrete, turn-based game between two competing computational agents: a Proponent (𝒫) and an Opponent/Refuter (ℛ), adjudicated by a structured Judge (𝒥). We provide a rigorous mathematical formalization of the topological state space, hypergraph mutation operators, and the minimax objective functions that govern the system's convergence. HAD bridges the gap between formal argumentation theory and structural deep learning, offering new pathways for automated scientific hypothesis verification, epistemic red-teaming, and the dynamic purification of relational Knowledge Graphs. Italiano: Riassunto: Questo preprint introduce formalmente l'Hypergraph Adversarial Debate (HAD), un framework multi-agente innovativo operante su strutture di conoscenza di ordine superiore modellate tramite ipergrafi (ℋ). Mentre i paradigmi tradizionali di apprendimento avversario su ipergrafi si affidano a ottimizzazioni statistiche continue guidate dai gradienti, l'HAD concettualizza la robustezza epistemica come un gioco formale, discreto e a turni tra due agenti computazionali in competizione: un Proponente (𝒫) e un Confutatore (ℛ), supervisionati da un Giudice strutturato (𝒥). Viene fornita una rigorosa formalizzazione matematica dello spazio degli stati topologici, degli operatori di mutazione ipergrafica e delle funzioni obiettivo minimax che governano la convergenza del sistema. L'HAD unisce la teoria dell'argomentazione formale con il deep learning strutturale, aprendo nuove prospettive per la verifica automatica di ipotesi scientifiche, il red-teaming epistemico e la purificazione dinamica di Knowledge Graph relazionali. ---------------------------------------------------------------------Roadmap di formalizzazione / Formalization Roadmap--------------------------------------------------------------------- 🇬🇧 English – Next Steps Toward a Rigorous Formalization: We outline the concrete formalisation steps required to elevate the HAD framework from conceptual architecture to a fully verified mathematical theory. 1. **Hypergraph state space (H-space)** Let 𝒱 be a finite set of vertices (concepts, entities) and ℰ ⊆ 𝒫(𝒱) a set of hyperedges (higher-order relations). The state of the debate is a labelled hypergraph H = (𝒱, ℰ, L), where L: 𝒱 ∪ ℰ → Σ assigns labels from a finite alphabet Σ (e.g., truth values, epistemic statuses). The state space 𝕊 is the set of all such hypergraphs reachable from an initial H₀ via the allowed mutation operators. 2. **Mutation operators as hypergraph rewrite rules** Each turn, the active agent applies one mutation μ from a finite set M = M_add ∪ M_del ∪ M_relabel ∪ M_fuse. We define each μ as a partial function μ: 𝕊 ⇀ 𝕊 that satisfies a locality condition (only a bounded neighbourhood is altered). These can be represented as double-pushout (DPO) rules in the category of hypergraphs, making the operational semantics algebraically precise. 3. **Debate game structure** The game is an extensive-form, perfect-information, zero-sum game with alternating moves: - State: H_t ∈ 𝕊 - Turn: agent A_t ∈ {𝒫, ℛ} - Legal moves: M(H_t) ⊆ M, defined by preconditions (e.g., no deletion of "protected" axioms) - Transition: H_{t+1} = μ(H_t) for chosen μ ∈ M(H_t) Terminal states T ⊆ 𝕊 are those where no legal moves exist for the player whose turn it is, or a predefined depth limit is reached. 4. **Judge and minimax objective** The Judge implements a scoring function J: 𝕊 → ℝ that evaluates the epistemic quality of a hypergraph (coherence, empirical adequacy, simplicity, etc.). The game value V(H, d) at depth d is defined recursively: V(H, 0) = J(H) V(H, d) = max_{μ ∈ M(H)} V(μ(H), d-1) if turn = 𝒫, min_{μ ∈ M(H)} V(μ(H), d-1) if turn = ℛ. The agents rationally select moves optimizing this value. 5. **Convergence and equilibrium** We aim to prove that, under suitable monotonicity assumptions on J (e.g., J is a Scott-continuous function on a dcpo of hypergraphs ordered by epistemic improvement), the minimax sequence converges to a fixed point or a terminal state that represents a stable, "purified" knowledge structure. Further, one can investigate Nash equilibria in mixed strategies for non-deterministic settings. 6. **Call for collaboration** The formalization of HAD draws on hypergraph rewriting, game theory, order theory, and topological logics. We invite mathematicians, computer scientists, and logicians to contribute to: - Proving convergence theorems - Implementing a prototype HAD engine - Exploring connections with abstract argumentation and persistent homology 🇮🇹 Italiano – Prossimi passi verso una formalizzazione rigorosa: Descriviamo i passi concreti necessari per elevare il framework HAD da architettura concettuale a teoria matematica completamente verificata. 1. **Spazio degli stati ipergrafico (H-spazio)** Sia 𝒱 un insieme finito di vertici (concetti, entità) e ℰ ⊆ 𝒫(𝒱) un insieme di iperarchi (relazioni di ordine superiore). Lo stato del dibattito è un ipergrafo etichettato H = (𝒱, ℰ, L), dove L: 𝒱 ∪ ℰ → Σ assegna etichette da un alfabeto finito Σ (es. valori di verità, stati epistemici). Lo spazio degli stati 𝕊 è l’insieme di tutti gli ipergrafi raggiungibili a partire da un H₀ iniziale tramite gli operatori di mutazione ammessi. 2. **Operatori di mutazione come regole di riscrittura di ipergrafi** Ad ogni turno, l’agente attivo applica una mutazione μ da un insieme finito M = M_add ∪ M_del ∪ M_relabel ∪ M_fuse. Ogni μ è definita come una funzione parziale μ: 𝕊 ⇀ 𝕊 che soddisfa una condizione di località (solo un intorno limitato viene alterato). Tali operatori possono essere rappresentati tramite regole double-pushout (DPO) nella categoria degli ipergrafi, rendendo la semantica operazionale algebricamente precisa. 3. **Struttura del gioco di dibattito** Il gioco è a forma estesa, a informazione perfetta, a somma zero, con mosse alternate: - Stato: H_t ∈ 𝕊 - Turno: agente A_t ∈ {𝒫, ℛ} - Mosse lecite: M(H_t) ⊆ M, definite da precondizioni (es. divieto di cancellare "assiomi protetti") - Transizione: H_{t+1} = μ(H_t) per μ scelta tra M(H_t) Gli stati terminali T ⊆ 𝕊 sono quelli in cui non esistono mosse legali per il giocatore di turno, oppure viene raggiunto un limite di profondità prefissato. 4. **Giudice e obiettivo minimax** Il Giudice implementa una funzione di valutazione J: 𝕊 → ℝ che misura la qualità epistemica dell’ipergrafo (coerenza, adeguatezza empirica, semplicità, ecc.). Il valore del gioco V(H, d) a profondità d è definito ricorsivamente: V(H, 0) = J(H) V(H, d) = max_{μ ∈ M(H)} V(μ(H), d-1) se turno = 𝒫, min_{μ ∈ M(H)} V(μ(H), d-1) se turno = ℛ. Gli agenti scelgono razionalmente le mosse che ottimizzano tale valore. 5. **Convergenza ed equilibrio** Ci proponiamo di dimostrare che, sotto opportune ipotesi di monotonicità su J (es. J è una funzione Scott-continua su un dcpo di ipergrafi ordinati per miglioramento epistemico), la sequenza minimax converge a un punto fisso o a uno stato terminale che rappresenta una struttura di conoscenza stabile e "purificata". Si può inoltre indagare l’esistenza di equilibri di Nash in strategie miste per scenari non deterministici. 6. **Chiamata alla collaborazione** La formalizzazione di HAD attinge alla riscrittura di ipergrafi, alla teoria dei giochi, alla teoria degli ordini e alle logiche topologiche. Invitiamo matematici, informatici e logici a contribuire a: - Dimostrare teoremi di convergenza - Implementare un prototipo del motore HAD - Esplorare connessioni con l’argomentazione astratta e l’omologia persistente ---------------------------------------------------------------------Nota dell'Autore, Luigi Usai: "Il mio background è filosofico e umanistico. Ho intuito questa struttura logica e mi sono avvalso dell'Intelligenza Artificiale per modellarla e strutturarla nel paper. Non sono un matematico, non ho le competenze per fornirvi dimostrazioni formali ed è esattamente per questo che sono qui: per mostrarvi l'architettura concettuale e chiedere il vostro aiuto per capire se è formalizzabile." ---------------------------------------------------------------------Potential Impact of HAD on Mathematical Sciences--------------------------------------------------------------------- 🇬🇧 English: If the Hypergraph Adversarial Debate framework were systematically adopted by the mathematical community, it would trigger a paradigmatic shift in the production, verification, and pedagogy of mathematics. We outline the primary structural consequences. 1. **Automated Theorem Discovery and Verification** - *Ultra-rapid proof checking*: While current proof assistants (e.g., Lean, Coq) require manual translation of informal proofs into formal code, HAD automates the search for logical flaws by letting a refuter agent continuously probe the hypergraph representation of a proof for higher-order counterexamples. - *Devil’s Advocate multi-agency*: A pool of adversarial agents constantly attacks newly proposed theorems, targeting topological “blind spots” where a hyperedge connecting three or more premises is missing, thus enabling falsification that escapes traditional linear or tree-like proof structures. - *Topological falsification*: By mapping proofs to labelled hypergraphs, the system
Abstract This note specifies a data suitability gate — a lightweight boundary criterion positioned between the output of probabilistic language models and the input of deterministic symbolic reasoning systems. The gate answers a single structural question before any inference is attempted: is this data suitable for the intended task, and if so, to what degree? The criterion is negative-first: it does not assert fit; it structurally excludes non-fit. Positive admission is graded, not proven. Note that: In terms of this paper domain (if it recognized as scope definitions, terms and explanations) is equivalent corpora, becasuse domain always grounds on corpora/norm sources 1. The Core Principle A deterministic reasoning system — one that operates over a structured index of knowledge and produces verifiable conclusions — cannot admit arbitrary input. Input that is structurally degenerate (rank-deficient, informationally empty) or structurally foreign (inconsistent with the domain's reference form) will produce wrong answers without signalling that anything is wrong. The gate prevents silent failure at the boundary. The gate operates by comparing the covariance structure of the candidate data against an external reference form derived from the target domain or query class. The comparison yields a single scalar ratio. Both tails of this ratio are refusal signals — for opposite reasons: Condition Structural meaning Ratio collapses to zero Rank-deficient data — no independent structure, informationally empty Ratio blows up Data structure foreign to the reference — not from this domain Ratio within bounded corridor Admissible; degree of fit is the value of the ratio The admissible region is a bounded corridor. Both walls are set by the reference form, not by free parameters. The gate excises both tails and keeps what could not be structurally excluded. 2. Two Questions, One Measure The same criterion answers two distinct questions about the same data, depending on what the reference form is set to: Fitness for domain/corpora synthesis. Does this data structurally belong to the domain being built? If admitted, it may extend the domain's knowledge base — adding new facts, definitions, or constraints. The reference is the existing domain structure. Fitness for answering a query. Does this data — or this query — structurally land on the assembled domain? The reference is the query class combined with the information structure of the domain as currently assembled. The two questions are two instances of the same test. The gate runs both; their combined result determines whether the data is admitted, and at which layer of the domain it should be integrated. 3. Two Levels on One Basis A knowledge domain is not a separate structure above the data. It is a layer of constraints — definitions and enforcements — applied on top of the same underlying index of Subject–Predicate–Object triples. The gate therefore operates on one basis at two levels: Raw index level — what the domain can structurally distinguish in principle. Constrained level — what the domain distinguishes under its current set of applied rules. Both levels yield a covariance form over the same index, so they are directly comparable. The gap between the two ratios localises the deficiency: Data passes at the raw level but fails at the constrained level → the index contains the relevant facts, but the domain's rules do not yet cover this case. The constraint layer needs to be extended, not the underlying data. Data fails already at the raw level → the facts are absent from the index itself. No rule extension will help; the domain simply does not cover this topic. This two-level diagnostic replaces a binary pass/fail with a precise instruction: what to fix, and at which layer. 4. The Honesty of the Criterion The gate makes an asymmetric claim — one that is worth stating explicitly: The system is exact in what it rejects, and calibrated — not certain — in what it admits. A ratio collapse or explosion is a structural proof of non-belonging. Refusal is deterministic. Admission, by contrast, is not a proof of fit — it is a measured failure to exclude. The degree of fit (the ratio value within the corridor) is a confidence weight on the admitted data, not a certification. This asymmetry is the boundary that separates a deterministic reasoning system from a probabilistic one: refusal is a fact; admission is a graded hypothesis. 5. Positioning in the Architecture The gate sits at the ingress boundary of the deterministic layer — after language model output is produced, before it enters the structured reasoning graph. It is a pure linear-algebraic check: rank and volume of the candidate covariance against the reference form. It does not re-run inference; it does not require the reasoning engine to process degenerate input speculatively. The gate is the structural counterpart — on the ingress side — of the constrained-decoding mechanisms (grammar masks, schema validators) that vendors attach to language model outputs on the egress side. Both are instances of the same pattern: when formal guarantees are required, linear algebra and formal structure are applied at the boundary; the probabilistic model is not trusted to self-regulate.
The order-statistic gaps that underlie PPP-residualized functional identity measurement are exactly invariant to log-softmax transformation, exactly equivariant under positive scaling (including temperature), and exactly invariant to any position-independent constant shift applied to the logit vector. These are not empirical approximations — they are mathematical identities that hold for any logit vector over any vocabulary size. The result has been formally verified in Coq (GapInvariance.v: 5 theorems, 2 axioms, 0 Admitted). It retroactively strengthens the empirical API-wall finding reported in earlier work: the order-statistic gap geometry measured through API logprobs does not merely "survive" the log-softmax transformation — it is mathematically immune to it. Any deviation attributable to the API boundary must come from truncation, quantization, or coverage limitations, not from the probability-domain transformation itself. Why this matters. Earlier work showed empirically that PPP-based measurements remained stable when models were accessed through APIs that expose log-probabilities instead of raw logits. This note upgrades that result from empirical robustness to mathematical invariance. It removes the probability-domain transformation itself from the list of plausible failure modes. If an API-based PPP measurement deviates from a weights-based measurement, the cause must lie in truncation, quantization, coverage limitations, or the model — not in log-softmax. The API wall is narrower than previously understood, and the space of plausible objections to API-domain model identity measurement has shrunk by one major category. Supplementary Material. This note is accompanied by GapInvariance.v, a Coq proof file that formally verifies the five gap-invariance theorems described in §2: constant-shift invariance, positive-scale equivariance, affine scaling, log-softmax invariance, and general position-independent shift invariance. The file proves 5 theorems from 2 named axioms (OS1 and OS2), with no unresolved obligations (Admitted), and compiles cleanly under the Rocq Prover 9.1.1 (the current release of the Coq proof assistant, compiled with OCaml 5.4.0). It is available for download as a supplementary file attached to this record. The Neural Network Identity Series — Mathematical foundations, empirical validation, and governance frameworks for verifying which model is running Newest addition: Technical Note: The Disappearing Window — AI Logprob Access Withdrawal and the Structural Verifiability of Frontier Model Contracts (DOI: 10.5281/zenodo.20362098) Paper 1: The δ-Gene: Inference-Time Physical Unclonable Functions from Architecture-Invariant Output Geometry (DOI: 10.5281/zenodo.18704275) Paper 2: Template-Based Endpoint Verification via Logprob Order-Statistic Geometry (DOI: 10.5281/zenodo.18776711) Paper 3: The Geometry of Model Theft: Distillation Forensics, Adversarial Erasure, and the Illusion of Spoofing (DOI: 10.5281/zenodo.18818608) Paper 4: Provenance Generalization and Verification Scaling for Neural Network Forensics (DOI: 10.5281/zenodo.18872071) Paper 5: Beneath the Character: The Structural Identity of Neural Networks — Mathematical Evidence for a Non-Narrative Layer of AI Identity (DOI: 10.5281/zenodo.18907292) Paper 6: Which Model Is Running?: Structural Identity as a Prerequisite for Trustworthy Zero-Knowledge Machine Learning (DOI: 10.5281/zenodo.19008116) Paper 7: The Deformation Laws of Neural Identity (DOI: 10.5281/zenodo.19055966) Paper 8: What Counts as Proof? — Admissible Evidence for Neural Network Identity Claims (DOI: 10.5281/zenodo.19058540) Paper 9: Composable Model Identity — Formal Hardening of Structural Attestations in the Enterprise Identity Stack (DOI: 10.5281/zenodo.19099911) Paper 10:Where Identity Comes From: Path Sensitivity and Endpoint Underdetermination in Neural Network Training (DOI: 10.5281/zenodo.19118807) Paper 11: Post-Hoc Disclosure Is Not Runtime Proof: Model Identity at Frontier Scale (DOI: 10.5281/zenodo.19216634) Paper 12: Family-Dependent Response to Reasoning Distillation Across Structural and Functional Identity Layers (DOI: 10.5281/zenodo.19298857) Paper 13: Safety-Alignment Removal as a Model-Identity Failure — Structural Evidence from Published Weight-Level Mutation Checkpoints (DOI: 10.5281/zenodo.19383019) Technical Note: Agent Identity Is Not Model Identity (DOI: 10.5281/zenodo.19240883) Technical Note: Gap Invariance: Why PPP Measurements Are Domain-Independent by Construction (DOI: 10.5281/zenodo.19275524) Technical Note: Measured Model Substitution Under Valid Agent Credentials (DOI: 10.5281/zenodo.19342848) Technical Note: Artifact Identity Is Not Runtime Identity — Trustfall Lite and the Boundary of File-Level Model Verification (DOI: 10.5281/zenodo.20019127) Formal Verification Stack for Neural Network Structural Identity (IT-PUF Coq Proofs) (DOI: 10.5281/zenodo.18930621) Copyright (c) 2026 Anthony Ray Coslett / Fall Risk AI, LLC. All Rights Reserved. Confidential and Proprietary. Patent Pending (Applications 63/982,893, 63/990,487, 63/996,680, 64/003,244).
Cross-chain technology is the key to solving the “data silo” problem in medical blockchain systems. However, it is difficult for existing cross-chain consensus mechanisms to meet the high standards of data security and consensus efficiency in medical scenarios. Therefore, this paper proposes a medical cross-chain Delegated proof of stake consensus(DPoS) scheme that integrates reputation and contribution evaluation. First, a dynamic reputation evaluation model was constructed, and the historical behaviour and communication quality of nodes were incorporated into the evaluation system, thereby mitigating the risk of centralization caused by the excessive reliance on the number of coins held in the DPoS consensus. Second, a hybrid random block generation mechanism combining the multiparty coin-tossing protocol and the secure shuffling algorithm was proposed. By collaboratively generating a verifiable global random seed and uniformly and randomly shuffling the candidate node sequence, the predictability of the block generation order was eliminated. Finally, a two-layer incentive architecture based on the Shapley value was proposed. Fine-grained contribution assessment mechanisms were established at both the candidate node layer and the voting node layer, making the reward distribution more equitable, enhancing the enthusiasm of nodes for voting and improving the consensus efficiency. Theoretical analysis and experimental results show that compared with the DPoS scheme, the proposed scheme improves the throughput by approximately 30% and reduces the average latency by approximately 50%. Compared with existing similar schemes, this scheme also has significant advantages in terms of reputation calculation overhead and malicious node elimination and can provide efficient and reliable consensus support for cross-chain scenarios in the medical field.
Prescriptive analytics seeks to identify optimal interventions for achieving desired outcomes, with causal inference playing a pivotal role in assessing intervention impacts on complex systems. However, existing approaches frequently neglect critical data privacy considerations and provide no means to verify the integrity of their recommendations. These limitations hinder its adoption in high-stakes domains such as healthcare and finance. In this paper, we introduce, zkCLEAR, a zero-knowledge proof (ZKP)-based C ausal Inference ( LEA rning and R easoning) framework for privacy-preserving and verifiable prescriptive analytics. Our solution allows data owners or service providers to cryptographically prove the validity of prescriptive conclusions derived from causal analysis without disclosing sensitive source data or proprietary causal models. We develop a suite of ZKP-friendly causal operators to build efficient causal modules, including structure learning, parameter learning, probabilistic inference, and counterfactual reasoning. To optimize performance, we also introduce a workflow decomposition strategy to facilitate efficient proof generation for complex workloads. We demonstrate the utility of zkCLEAR through three real-world applications. The framework faithfully follows the behavior of non-ZKP counterparts, with moderate overheads for privacy and verifiability. Additionally, we evaluate its efficiency and scalability using real-world datasets. It shows up to a 35.1× speedup in proof generation time and a 214.5× reduction in proof size compared to current general-purpose ZKP systems.
Card-based cryptography enables players to compute logical and arithmetic operations securely, such as bitwise AND and addition of integers. Several multiparty computation protocols and zero-knowledge proof protocols utilizing these secure computations have been developed as its applications. However, the realization of an efficient protocol for an arithmetic operation other than addition and subtraction remains an open problem. This paper proposes card-based protocols, based on integer commitment, for multiplication, division, and square root. Compared to general constructions for protocols for these operations based on binary integer commitment, the proposed protocols exhibit superior simplicity and efficiency. Furthermore, these protocols introduce novel applications for card-based cryptography to secure statistical data aggregation.
Environmental impact and sustainability challenges in the cryptocurrencies has become increasingly examined in the literature. However, studies of the multiple attribute group decision making (MAGDM) method for major selection of cryptocurrencies in advancing sustainability are still at an early stage. In particular, research on the fuzzy-MAGDM method in the evaluation of sustainability in cryptocurrencies is scarce. This paper adds contributions by developing a novel MAGDM approach to evaluate the sustainability development of major cryptocurrencies. It proposes a similarity measure for interval-valued Pythagorean fuzzy numbers (IVPFNs) based on whitenisation weight function and membership function in grey systems theory for IVPFNs. It further developed a novel generalised interval-valued Pythagorean fuzzy weighted grey similarity (GIPFWGS) measure approach to provide a more rigorous evaluation in complex decision marking problem with embedding ideal solution and membership degree. It also conducts a sustainability evaluation model of major cryptocurrencies as a numerical application and performs a robustness assessment with different variations of the expert's weight to test how different values of parameter θ can affect the ranking results of alternatives. The results suggest that Stellar is the most sustainable cryptocurrency, while Bitcoin with its intensive energy consumption, high mining cost and high computing power provides the least effective support for its sustainable development. A comparative analysis with the average value method and Euclidean distance method was performed to validate the reliability of the proposed decision-making model and provides evidence that the GIPFWGS has better fault tolerance.
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.
Sandra Johnson, David Hyland-Wood, Anders L. Madsen, Kerrie Mengersen
The concept of 'Stateless Ethereum' was conceived with the primary aim of mitigating Ethereum's unbounded state growth. The key facilitator of Stateless Ethereum is through the introduction of 'witnesses' into the ecosystem. The changes and potential consequences that these additional data packets pose on the network need to be identified and analysed to ensure that the Ethereum ecosystem can continue operating securely and efficiently. In this paper we propose a Bayesian Network model, a probabilistic graphical modelling approach, to capture the key factors and their interactions in Ethereum mainnet, the public Ethereum blockchain, focussing on the changes being introduced by Stateless Ethereum to estimate the health of the resulting Ethereum ecosystem. We use a mixture of empirical data and expert knowledge, where data are unavailable, to quantify the model. Based on the data and expert knowledge available to use at the time of modelling, the Ethereum ecosystem is expected to remain healthy following the introduction of Stateless Ethereum.
We consider the problem of efficiently inferring interventional distributions in a causal Bayesian network from a finite number of observations. Let $\mathcal{P}$ be a causal model on a set $\mathbf{V}$ of observable variables on a given causal graph $G$. For sets $\mathbf{X},\mathbf{Y}\subseteq \mathbf{V}$, and setting ${\bf x}$ to $\mathbf{X}$, let $P_{\bf x}(\mathbf{Y})$ denote the interventional distribution on $\mathbf{Y}$ with respect to an intervention ${\bf x}$ to variables ${\bf x}$. Shpitser and Pearl (AAAI 2006), building on the work of Tian and Pearl (AAAI 2001), gave an exact characterization of the class of causal graphs for which the interventional distribution $P_{\bf x}({\mathbf{Y}})$ can be uniquely determined. We give the first efficient version of the Shpitser-Pearl algorithm. In particular, under natural assumptions, we give a polynomial-time algorithm that on input a causal graph $G$ on observable variables $\mathbf{V}$, a setting ${\bf x}$ of a set $\mathbf{X} \subseteq \mathbf{V}$ of bounded size, outputs succinct descriptions of both an evaluator and a generator for a distribution $\hat{P}$ that is $\varepsilon$-close (in total variation distance) to $P_{\bf x}({\mathbf{Y}})$ where $Y=\mathbf{V}\setminus \mathbf{X}$, if $P_{\bf x}(\mathbf{Y})$ is identifiable. We also show that when $\mathbf{Y}$ is an arbitrary set, there is no efficient algorithm that outputs an evaluator of a distribution that is $\varepsilon$-close to $P_{\bf x}({\mathbf{Y}})$ unless all problems that have statistical zero-knowledge proofs, including the Graph Isomorphism problem, have efficient randomized algorithms.
Marc Jourdan, Sébastien Blandin, Laura Wynter, Pralhad Deshpande
The Bitcoin transaction graph is a public data structure organized as transactions between addresses, each associated with a logical entity. In this work, we introduce a complete probabilistic model of the Bitcoin Blockchain, setting the basis for follow-up AI applications on Bitcoin transactions. We first formulate a set of conditional dependencies induced by the Bitcoin protocol at the block level and derive a corresponding fully observed graphical model of a Bitcoin block. We then extend the model to include hidden entity attributes such as the functional category of the associated logical agent and derive asymptotic bounds on the privacy properties implied by this model. At the network level, we show evidence of complex transaction-to-transaction behavior and present a relevant discriminative model of the agent categories. Performance of both the block-based graphical model and the network-level discriminative model are evaluated on a subset of the public Bitcoin Blockchain.
Bitcoin is one of the first decentralized, peer to peer, payment systems based on the so-called Proof-of-Work (PoW). PoW is an algorithm that requires the computation of a hard function in order to gain access to a resource but, at the same time, the correctness of the computed result should be easily checked. The use of a PoW removes the necessity of a centralized third party and so the consistency of the network may be altered directly by the involved users. Peers, to solve the PoW more efficiently, usually organize themselves into mining pools, to increase the overall computational power: this situation, unfortunately, leads to a network centralization. In this paper we consider two typical scenarios of a Bitcoin network and we model them by probabilistic logic programming (PLP): the centralization of the hashing power by large pools and the “double spending attack”. In the first one, we verify the effectiveness of a protocol that attempts to discourage the formation of large pools. In the second one, we compute the probability of success of an attacker. Both scenarios are modeled using the PLP package cplint.
Abstract. We study the probability that two or more agents can attain common knowledge of nontrivial events when the size of the state space grows large. We adopt the standard epistemic model where the knowledge of an agent is represented by a partition of the state space. Each agent is endowed with a partition generated by a random scheme consistent with his cognitive capacity. Assuming that agents ’ partitions are independently distributed, we prove that the asymptotic probability of nontrivial common knowledge undergoes a phase transition. Regardless of the number of agents, when their cognitive capacity is sufficiently large, the probability goes to one; and when it is small, it goes to zero. Our proofs rely on a graph-theoretic characterization of common knowledge that has independent interest.
As the use of Internet grows beyond all boundaries, the number of menaces rises to become subject of concern and increasing research. Against this, Network Intrusion Detection Systems (NIDS) monitor local networks to separate legitimate from dangerous behaviours. According to their capabilities and goals, NIDS are divided into misuse detection systems (which aim to detect well-known attacks) and anomaly detection systems (which aim to detect zero-day attacks). So far, no system to our knowledge combines advantages of both without any of their disadvantages. Moreover, the use of historical data for analysis or sequential adaptation is usually ignored, missing in this way the possibility of anticipating the behaviour of the target system. ESIDE-Depian, a Bayesian-networks-based misuse and anomaly detection system. In another work, we detailed the composition of the Bayesian network, its training methodology and showed general performance results. Here we have focused on evaluating the integration of misuse and anomaly detection. To this end, we have adopted Snort (a well-known misuse detector) as misuse detector trainer so the Bayesian Network of ï¬ve experts is able to react against both misuse and anomalies. The Bayesian experts are devoted to the analysis of different network protocol aspects and obtain the common knowledge model by means of separated Snort-driven automated learning process Since ESIDE-Depian has passed the experiments brilliantly, it is possible to conclude that ESIDE-Depian using of Bayesian Networking concepts allows to conï¬rm an excellent basis for paradigm unifying Network Intrusion Detection, providing not only stable Misuse Detection but also effective Anomaly Detection capabilities, with one only flexible knowledge representation model and a well-proofed inference and adaptation bunch of methods. On the other hand, the Bayesian approach also enables to implement powerful features over it, such as Dynamic-Bayesian-Network-based full representation of time, in order to accomplish totally-characterised connection tracking and low level chronological event correlation, or explanation tracking of the inferred cause-effect reasoning processes. Furthermore, contrary to other approaches such as Neural Networks, Bayesian networks allow administrative managing of inner information structures, so speciï¬c relationships among packet detection parameters and ï¬nal conclusion can be explained, in a white-box manner. Moreover, it is not only possible to recover reasoning information, but also to act on both Bayesian network
Many backtracking algorithms exhibit heavy-tailed distributions, in which their running time is often much longer than their median. We analyze the behavior of two natural variants of the Davis-Putnam-Logemann-Loveland (DPLL) algorithm for Graph 3-Coloring on sparse random graphs G(n,p=c/n). Let P_c(b) be the probability that DPLL backtracks b times. First, we calculate analytically the probability P_c(0) that these algorithms find a 3-coloring with no backtracking at all, and show that it goes to zero faster than any analytic function as c \to c^* = 3.847... Then we show that even in the ``easy'' phase 1 < c < c^* where P_c(0) > 0, including just above the emergence of the giant component, the expected number of backtracks is exponentially large with positive probability. To our knowledge this is the first rigorous proof that the running time of a natural backtracking algorithm has a heavy tail for graph coloring. Moreover, our results show that these algorithms take exponential time, not just below the 3-colorability threshold, but just above the degree c=1 at which the giant component first appears. In addition, we give experimental evidence and heuristic arguments that this tail takes the form P_c(b) ~ b^{-1} up to an exponential cutoff.
A proof is whatever convinces me. Shimon Even (1935–2004) The glory attached to the creativity involved in finding proofs makes us forget that it is the less glorified process of verification that gives proofs their value. Conceptually speaking, proofs are secondary to the verification process, whereas technically speaking, proof systems are defined in terms of their verification procedures. The notion of a verification procedure presumes the notion of computation and furthermore the notion of efficient computation. This implicit stipulation is made explicit in the definition of NP , where efficient computation is associated with deterministic polynomial-time algorithms. However, as argued next, we can gain a lot if we are willing to take a somewhat non-traditional step and allow probabilistic verification procedures. In this chapter, we shall study three types of probabilistic proof systems, called interactive proofs, zero-knowledge proofs , and probabilistic checkable proofs . In each of these three cases, we shall present fascinating results that cannot be obtained when considering the analogous deterministic proof systems. Summary: The association of efficient procedures with deterministic polynomial-time procedures is the basis for viewing NP-proof systems as the canonical formulation of proof systems (with efficient verification procedures). Allowing probabilistic verification procedures and, moreover, ruling by statistical evidence gives rise to various types of probabilistic proof systems. Indeed, these probabilistic proof systems carry a probability of error (which is explicitly bounded and can be reduced by successive applications of the proof system), yet they offer various advantages over the traditional (deterministic and errorless) proof systems. […]