Lite-PoT: Practical Powers-of-Tau Setup Ceremony

• URL: http://arxiv.org/abs/2503.04549v1
• Date: Thu, 06 Mar 2025 15:34:50 GMT
• Title: Lite-PoT: Practical Powers-of-Tau Setup Ceremony
• Authors: Lucien K. L. Ng, Pedro Moreno-Sanchez, Mohsen Minaei, Panagiotis Chatzigiannis, Adithya Bhat, Duc V. Le,
• Abstract summary: Zk-SNARKs rely on a one-time trusted setup to generate a public parameter, often known as the Powers of Tau" (PoT) string.<n>The leakage of the secret parameter, $tau$, in the string would allow attackers to generate false proofs, compromising the soundness of all zk-SNARK systems built on it.<n>We present Lite-PoT, which includes two key protocols designed to reduce participation costs.
• Score: 11.689131565202945
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARK) schemes have gained significant adoption in privacy-preserving applications, decentralized systems (e.g., blockchain), and verifiable computation due to their efficiency. However, the most efficient zk-SNARKs often rely on a one-time trusted setup to generate a public parameter, often known as the ``Powers of Tau" (PoT) string. The leakage of the secret parameter, $\tau$, in the string would allow attackers to generate false proofs, compromising the soundness of all zk-SNARK systems built on it. Prior proposals for decentralized setup ceremonies have utilized blockchain-based smart contracts to allow any party to contribute randomness to $\tau$ while also preventing censorship of contributions. For a PoT string of $d$-degree generated by the randomness of $m$ contributors, these solutions required a total of $O(md)$ on-chain operations (i.e., in terms of both storage and cryptographic operations). These operations primarily consisted of costly group operations, particularly scalar multiplication on pairing curves, which discouraged participation and limited the impact of decentralization In this work, we present Lite-PoT, which includes two key protocols designed to reduce participation costs: \emph{(i)} a fraud-proof protocol to reduce the number of expensive on-chain cryptographic group operations to $O(1)$ per contributor. Our experimental results show that (with one transaction per update) our protocol enables decentralized ceremonies for PoT strings up to a $2^{15}$ degree, an $\approx 16x$ improvement over existing on-chain solutions; \emph{(ii)} a proof aggregation technique that batches $m$ randomness contributions into one on-chain update with only $O(d)$ on-chain operations, independent of $m$. This significantly reduces the monetary cost of on-chain updates by $m$-fold via amortization.

Related papers

• Proofs of Useful Work from Arbitrary Matrix Multiplication [10.61664303118825]
  We revisit the longstanding open problem of implementing Nakamoto's proof-of-work (PoW) consensus based on a real-world computational task. We produce a PoW certificate with prescribed hardness and with negligible computational overhead. We conjecture that our protocol has optimal security in the sense that a malicious prover cannot obtain any significant advantage over an honest prover.
  arXiv  Detail & Related papers  (2025-04-14T08:22:40Z)
• Optimal Computational Secret Sharing [51.599517747577266]
  In $(t, n)$-threshold secret sharing, a secret $S$ is distributed among $n$ participants.<n>We present a construction achieving a share size of $tfrac|S|t + |K|t$.
  arXiv  Detail & Related papers  (2025-02-04T23:37:16Z)
• Unified Breakdown Analysis for Byzantine Robust Gossip [15.69624587054777]
  In decentralized machine learning, different devices communicate in a peer-to-peer manner to collaboratively learn from each other's data.<n>We introduce $mathrmFtext-rm RG$, a general framework for building robust decentralized algorithms.<n>We show an upper bound on the number of adversaries that decentralized algorithms can tolerate.
  arXiv  Detail & Related papers  (2024-10-14T12:10:52Z)
• The Latency Price of Threshold Cryptosystem in Blockchains [52.359230560289745]
  We study the interplay between threshold cryptography and a class of blockchains that use Byzantine-fault tolerant (BFT) consensus protocols. Existing approaches for threshold cryptosystems introduce a latency overhead of at least one message delay for running the threshold cryptographic protocol. We propose a mechanism to eliminate this overhead for blockchain-native threshold cryptosystems with tight thresholds.
  arXiv  Detail & Related papers  (2024-07-16T20:53:04Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Fast and Secure Decentralized Optimistic Rollups Using Setchain [1.1534313664323634]
  Layer 2 optimistic rollups (L2) are a faster alternative that offer the same interface in terms of smart contract development and user interaction. We propose a decentralized L2 optimistic rollup based on Setchain, a decentralized Byzantine-tolerant implementation of sets.
  arXiv  Detail & Related papers  (2024-06-04T13:45:12Z)
• Fully Automated Selfish Mining Analysis in Efficient Proof Systems Blockchains [5.864854777864723]
  We study selfish mining attacks in longest-chain blockchains like Bitcoin, but where the proof of work is replaced with efficient proof systems. We propose a novel selfish mining attack that aims to maximize expected relative revenue of the adversary. We present a formal analysis procedure which computes an $epsilon$-tight lower bound on the optimal expected relative revenue in the MDP.
  arXiv  Detail & Related papers  (2024-05-07T15:44:39Z)
• Travelers: A scalable fair ordering BFT system [7.891481513306302]
  Most efficient BFT consensus requires $O(nTL + n2T)$ communication complexity. We propose a new system of BFT fair ordering protocols, Travelers, that substantially reduce the communication complexity.
  arXiv  Detail & Related papers  (2024-01-04T02:14:18Z)
• Scalable and Adaptively Secure Any-Trust Distributed Key Generation and All-hands Checkpointing [3.1771413727096154]
  We propose a practical DKG for DLog-based cryptosystems, which achieves (quasi-)linear and communication per-node cost with the help of a common coin. Our protocol is secure against adaptive adversaries, which can corrupt less than half of all nodes. We present a generic transformer that enables us to efficiently deploy a conventional distributed protocol like our DKG, even when the participants have different weights.
  arXiv  Detail & Related papers  (2023-11-16T06:05:01Z)
• WR-ONE2SET: Towards Well-Calibrated Keyphrase Generation [57.11538133231843]
  Keyphrase generation aims to automatically generate short phrases summarizing an input document. The recently emerged ONE2SET paradigm generates keyphrases as a set and has achieved competitive performance. We propose WR-ONE2SET which extends ONE2SET with an adaptive instance-level cost Weighting strategy and a target Re-assignment mechanism.
  arXiv  Detail & Related papers  (2022-11-13T09:56:24Z)
• Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security [67.06003361150228]
  A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
  arXiv  Detail & Related papers  (2020-12-30T18:03:56Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB)
  arXiv  Detail & Related papers  (2020-06-17T22:32:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.