論文の概要: Parent-Hash DAG: A Cost Analysis of Constant-Time Append for On-Chain Registries
- arxiv url: http://arxiv.org/abs/2606.09593v1
- Date: Mon, 08 Jun 2026 15:03:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-09 14:42:07.365907
- Title: Parent-Hash DAG: A Cost Analysis of Constant-Time Append for On-Chain Registries
- Title（参考訳）: Parent-Hash DAG: オンチェーン登録のための一定時間適用のコスト分析
- Authors: Ian C. Moore, Fernando Paredes Garcia,
- Abstract要約: Provenance Treeは、パブリックブロックチェーンに固定されたアーティファクト登録の、追加のみの非循環グラフである。
我々は,PHDAGをガスコストのO(1)として定式化し,レジストリサイズや木深度に依存しないコストモデルを構築した。
また、オフチェーンの依存関係なしで、リニア時間でパブリックイベントログから信頼性のないレジストリを再構築します。
- 参考スコア（独自算出の注目度）: 45.88028371034407
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Provenance trees are append-only directed acyclic graphs of artifact registrations anchored on a public blockchain, recently introduced as the data substrate of operator-gated provenance infrastructure. Their defining data-structural pattern is a parent-hash directed acyclic graph (PHDAG), in which each append performs a constant number of storage writes to previously-untouched slots. This pattern has not previously been isolated as a standalone primitive, formally bounded with explicit constants, or benchmarked against the standard alternative, the incremental Merkle tree (IMT). We formalize PHDAG append as O(1) in gas cost, independent of registry size and tree depth, and develop a stochastic cost model for IMT in which per-insert cost is a random variable over the leaf index, deriving closed-form expressions for its mean and variance. We validate both analyses empirically on Base Sepolia across tree depths 1 to 25. PHDAG is observed to be depth-invariant at 76,276 gas (standard deviation about 6 gas), while IMT cost grows linearly with depth. The crossover below which IMT is cheaper falls far beneath the depths of every production registry surveyed. We further establish trustless registry reconstruction from public event logs in linear time with no off-chain dependency.
- Abstract（参考訳）: Provenance Treeは、パブリックブロックチェーンに固定されたアーティファクト登録の、追加のみの非循環グラフである。
彼らの定義するデータ構造パターンは、親ハッシュ指向非循環グラフ(PHDAG)であり、各アタッチメントは、前触れのないスロットに一定数のストレージ書き込みを実行する。
このパターンは、以前はスタンドアロンのプリミティブとして分離されておらず、明示的な定数で正式に境界付けられたり、標準の代替であるインクリメンタルメルクルツリー(IMT)に対してベンチマークされたりしていた。
我々は,ガスコストでPHDAGをO(1)として定式化し,その平均値とばらつきのクローズドフォーム式を導出し,各インサートコストが葉指数上のランダムな変数であるIMTの確率的コストモデルを構築した。
樹木深度1～25の範囲で,両分析を実証的に検証した。
PHDAGは76,276ガス(標準偏差は約6ガス)で深さ不変であり、IMTコストは深さとともに線形に増加する。
下記のIMTが安いクロスオーバーは、調査対象のすべての生産レジストリの深さよりもはるかに低い。
さらに、オフチェーン依存のないリニア時間で、パブリックイベントログから信頼性のないレジストリを再構築します。
関連論文リスト
- DAGGER: Gradient-Free Construction of Transiently Amplifying Networks under Hard Connectivity Constraints [0.0]
DAGGERは、過渡非正規増幅のための勾配のないシングルパスアルゴリズムである。
これは1つの前方パスにおける多重セット保存において勾配に基づく手法と一致するか、あるいは超える。
DAGGERが他の増幅ネットワークと構造的に異なる理由を示す。
論文 参考訳（メタデータ） (2026-05-31T13:20:26Z) - Stable Causal Discovery via Directed Acyclic Graph Aggregation [7.490209955333202]
誘導非巡回グラフ(DAG)は複雑な系における因果構造を明らかにする中心である。
複数の候補DAGを1つの安定表現に集約するモデル平均化フレームワークであるDAGgrを提案する。
ブートストラップ・アグリゲーション・ベースラインを常に上回りながら,DAGgrは最高の個人候補と一致または超えていることを示す。
論文 参考訳（メタデータ） (2026-05-18T16:41:31Z) - Acyclic Graph Pattern Counting under Local Differential Privacy [6.729442409066558]
局所微分プライバシー(LDP)の下での任意の非循環パターンをカウントする最初の一般解を提案する。
分散データからのパターン構築の一般化と,構築中のノード重複の排除という,2つの基本的な課題に対処する。
複数の非循環パターンをまたいだ実世界のグラフデータセットの実験により、我々のメカニズムは実用性の向上に46ドル～2600ドル、通信コストの削減に300ドル～650ドルを要した。
論文 参考訳（メタデータ） (2026-03-20T06:12:12Z) - KELP: Robust Online Log Parsing Through Evolutionary Grouping Trees [1.8479558716666362]
リアルタイムログ分析は、現代のインフラにおける可観測性の基礎である。
既存のオンラインは、生産環境のダイナミズムにはアーキテクチャ上不適である。
textbfKelp textbfEvolutionary textbfLog textbfParser)を提案する。
進化的グループ木(Evolutionary Grouping Tree)と呼ばれる新しいデータ構造の上に構築されている。
論文 参考訳（メタデータ） (2026-01-02T10:27:41Z) - Universal Hirschberg for Width Bounded Dynamic Programs [0.0]
ヒルシュベルクのアルゴリズムは、格子動的プログラム(DP)上の中点二項による$O(N2)$から$O(N)$へ、最も長い共通部分列問題の空間複雑性を減少させる。
我々は、その基礎となるアイデアが、有向非巡回グラフ(DP DAG)に局所的依存を持つ広範な動的プログラムのクラスに一般化されることを示す。
前方シングルパスモデルでは$()$空間項は避けられないことを示し、ストリーミング設定における推測される$sqrtT$-type障壁について議論する。
論文 参考訳（メタデータ） (2025-12-10T22:26:22Z) - DiffGRM: Diffusion-based Generative Recommendation Model [63.35379395455103]
ジェネレーティブレコメンデーション(GR)は、トークン化器を介して各項目をn桁のセマンティックID(SID)として表現する新興パラダイムである。
自己回帰デコーダをマスク付き離散拡散モデル(MDM)に置き換える拡散ベースGRモデルDiffGRMを提案する。
実験では、複数のデータセットに対する強力な生成的および差別的推奨ベースラインよりも一貫した利得を示す。
論文 参考訳（メタデータ） (2025-10-21T03:23:32Z) - From the One, Judge of the Whole: Typed Entailment Graph Construction
with Predicate Generation [69.91691115264132]
Entailment Graphs (EG) は、自然言語における文脈に依存しないentailment関係を示すために構築される。
本稿では,この問題に対処する多段階型述語グラフ生成器(TP-EGG)を提案する。
ベンチマークデータセットの実験では、TP-EGGは高品質でスケール制御可能なエンターメントグラフを生成することができる。
論文 参考訳（メタデータ） (2023-06-07T05:46:19Z) - Joint Bayesian Inference of Graphical Structure and Parameters with a
Single Generative Flow Network [59.79008107609297]
本稿では,ベイジアンネットワークの構造上の結合後部を近似する手法を提案する。
サンプリングポリシが2フェーズプロセスに従う単一のGFlowNetを使用します。
パラメータは後部分布に含まれるため、これは局所確率モデルに対してより柔軟である。
論文 参考訳（メタデータ） (2023-05-30T19:16:44Z) - Generalizing electrocardiogram delineation: training convolutional
neural networks with synthetic data augmentation [63.51064808536065]
ECGのデライン化のための既存のデータベースは小さく、サイズやそれらが表す病態の配列に不足している。
まず、原データベースから抽出した基本セグメントのプールを与えられたECGトレースを確率的に合成し、その整合性のある合成トレースに配置するための一連のルールを考案した。
第二に、2つの新しいセグメンテーションに基づく損失関数が開発され、これは、正確な数の独立構造の予測を強制し、サンプル数の削減に焦点をあてて、より密接なセグメンテーション境界を創出することを目的としている。
論文 参考訳（メタデータ） (2021-11-25T10:11:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。