論文の概要: Computing Optimal Manipulations in Cryptographic Self-Selection Proof-of-Stake Protocols
- arxiv url: http://arxiv.org/abs/2406.15282v1
- Date: Fri, 21 Jun 2024 16:20:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-24 12:34:06.781257
- Title: Computing Optimal Manipulations in Cryptographic Self-Selection Proof-of-Stake Protocols
- Title（参考訳）: 暗号自己選択プロトコルにおける最適操作
- Authors: Matheus V. X. Ferreira, Aadityan Ganesh, Jack Hourigan, Hannah Huh, S. Matthew Weinberg, Catherine Yu,
- Abstract要約: 任意の所望の$(alpha,beta)$に対して$f(alpha,beta)$を任意の精度まで確実に釘付けする方法を開発する。
技術的課題の1つは、対象分布の平均値の自然サンプリングに基づく推定は、偏りのない推定値であるということである。
- 参考スコア（独自算出の注目度）: 3.3139913966251227
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Cryptographic Self-Selection is a paradigm employed by modern Proof-of-Stake consensus protocols to select a block-proposing "leader." Algorand [Chen and Micali, 2019] proposes a canonical protocol, and Ferreira et al. [2022] establish bounds $f(\alpha,\beta)$ on the maximum fraction of rounds a strategic player can lead as a function of their stake $\alpha$ and a network connectivity parameter $\beta$. While both their lower and upper bounds are non-trivial, there is a substantial gap between them (for example, they establish $f(10\%,1) \in [10.08\%, 21.12\%]$), leaving open the question of how significant of a concern these manipulations are. We develop computational methods to provably nail $f(\alpha,\beta)$ for any desired $(\alpha,\beta)$ up to arbitrary precision, and implement our method on a wide range of parameters (for example, we confirm $f(10\%,1) \in [10.08\%, 10.15\%]$). Methodologically, estimating $f(\alpha,\beta)$ can be phrased as estimating to high precision the value of a Markov Decision Process whose states are countably-long lists of real numbers. Our methodological contributions involve (a) reformulating the question instead as computing to high precision the expected value of a distribution that is a fixed-point of a non-linear sampling operator, and (b) provably bounding the error induced by various truncations and sampling estimations of this distribution (which appears intractable to solve in closed form). One technical challenge, for example, is that natural sampling-based estimates of the mean of our target distribution are \emph{not} unbiased estimators, and therefore our methods necessarily go beyond claiming sufficiently-many samples to be close to the mean.
- Abstract（参考訳）: 暗号自己選択(英: Cryptographic Self-Selection)は、現代のProof-of-Stakeコンセンサスプロトコルで採用されているパラダイムであり、ブロックプロポーシングの「リーダー」を選択する。
Algorand [Chen and Micali, 2019] は標準的なプロトコルを提案し、Ferreira et al [2022] は境界$f(\alpha,\beta)$を設定する。
下界と上界はどちらも自明ではないが、それらの間にはかなりのギャップがある(例えば、$f(10\%,1) \in [10.08\%, 21.12\%]$)。
我々は、任意の所望の$(\alpha,\beta)$に対して$f(\alpha,\beta)$を確実に釘付けし、任意の精度で計算方法を開発し、幅広いパラメータに実装する(例えば、$f(10\%, 1) \in [10.08\%, 10.15\%]$)。
メソジカルには、$f(\alpha,\beta)$を推定することは、実数の数えきれないほど長いリストを持つマルコフ決定過程の値を高精度に推定することを意味する。
私たちの方法論的貢献は
(a)非線形サンプリング演算子の固定点である分布の期待値を高精度に計算する代わりに、問題を再検討し、
b) 様々なトランケーションによって引き起こされる誤差を証明的に束縛し、この分布のサンプリング推定を行う(これは閉形式で解くのに難しそうに思える)。
例えば、対象分布の平均の自然サンプリングに基づく推定は、偏りのない推定器であるので、我々の手法は必ずしも平均に近づくだけの十分な多くのサンプルを主張する以上のものである。
関連論文リスト
- Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares [4.335413713700667]
我々は citekothari2018robust で導入された正準平方和プログラムを新たに解析する。
このプログラムは,すべての $varepsilon に対して[0,frac12)$ の誤差率を効率よく達成できることを示す。
論文 参考訳（メタデータ） (2024-11-21T16:57:05Z) - Active Learning for Level Set Estimation Using Randomized Straddle Algorithms [18.96269063427081]
本稿では,関数が与えられたしきい値の上(または下)に値を取る入力点の集合を同定する新しい手法を提案する。
提案手法の信頼性パラメータは,反復数や候補点に依存しず,保守的でないという利点がある。
論文 参考訳（メタデータ） (2024-08-06T12:39:12Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Truncation Sampling as Language Model Desmoothing [115.28983143361681]
ニューラルネットワークモデルからのテキストの長いサンプルは、品質が劣る可能性がある。
トランケーションサンプリングアルゴリズムは、各ステップでいくつかの単語の確率を0に設定する。
本稿では,単語をエントロピーに依存した確率閾値以下に切り詰める$eta$-samplingを導入する。
論文 参考訳（メタデータ） (2022-10-27T05:52:35Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - PAC Mode Estimation using PPR Martingale Confidence Sequences [5.623190096715942]
離散分布 $mathcalP$ のモードを十分に高い確率で正確に同定する問題を考える。
モード推定の一般化を提案し、$mathcalP$は$K geq 2$値を取ることができる。
結果,PPR-MEと表される停止規則は,対数係数までのサンプル複雑性において最適である。
論文 参考訳（メタデータ） (2021-09-10T18:11:38Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Active learning for distributionally robust level-set estimation [16.869069414080847]
評価コストの高いブラックボックス関数 $f$ が 2 種類の変数 $bm x$ と $bm w$ に依存することを示す。
頑健性の自然な測度は、$f(bm x, bm w)$が与えられた閾値$h$を超える確率である。
本稿では,この問題に対する理論的基礎と計算学的に効率的な能動学習法を提案する。
論文 参考訳（メタデータ） (2021-02-08T04:43:31Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。
仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。
より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
論文 参考訳（メタデータ） (2020-06-18T17:47:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。