4 Search Results for "Merkle, Daniel"

Document
DOI: 10.4230/LIPIcs.AFT.2023.14
Proofs of Proof-Of-Stake with Sublinear Complexity

Authors: Shresth Agrawal, Joachim Neu, Ertem Nusret Tas, and Dionysis Zindros

Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)

Abstract
Popular Ethereum wallets (like MetaMask) entrust centralized infrastructure providers (e.g., Infura) to run the consensus client logic on their behalf. As a result, these wallets are light-weight and high-performant, but come with security risks. A malicious provider can mislead the wallet by faking payments and balances, or censoring transactions. On the other hand, light clients, which are not in popular use today, allow decentralization, but are concretely inefficient, often with asymptotically linear bootstrapping complexity. This poses a dilemma between decentralization and performance. We design, implement, and evaluate a new proof-of-stake (PoS) superlight client with concretely efficient and asymptotically logarithmic bootstrapping complexity. Our proofs of proof-of-stake (PoPoS) take the form of a Merkle tree of PoS epochs. The verifier enrolls the provers in a bisection game, in which honest provers are destined to win once an adversarial Merkle tree is challenged at sufficient depth. We provide an implementation for mainnet Ethereum: compared to the state-of-the-art light client construction of Ethereum, our client improves time-to-completion by 9×, communication by 180×, and energy usage by 30× (when bootstrapping after 10 years of consensus execution). As an important additional application, our construction can be used to realize trustless cross-chain bridges, in which the superlight client runs within a smart contract and takes the role of an on-chain verifier. We prove our construction is secure and show how to employ it for other PoS systems such as Cardano (with fully adaptive adversary), Algorand, and Snow White.
Cite as

Shresth Agrawal, Joachim Neu, Ertem Nusret Tas, and Dionysis Zindros. Proofs of Proof-Of-Stake with Sublinear Complexity. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 14:1-14:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.AFT.2023.14,
  author =	{Agrawal, Shresth and Neu, Joachim and Tas, Ertem Nusret and Zindros, Dionysis},
  title =	{{Proofs of Proof-Of-Stake with Sublinear Complexity}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{14:1--14:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-303-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{282},
  editor =	{Bonneau, Joseph and Weinberg, S. Matthew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.14},
  URN =		{urn:nbn:de:0030-drops-192037},
  doi =		{10.4230/LIPIcs.AFT.2023.14},
  annote =	{Keywords: Proof-of-stake, blockchain, light client, superlight, bridge, Ethereum}
}
Document
DOI: 10.4230/DagRep.7.11.28
Algorithmic Cheminformatics (Dagstuhl Seminar 17452)

Authors: Jakob L. Andersen, Christoph Flamm, Daniel Merkle, and Peter F. Stadler

Published in: Dagstuhl Reports, Volume 7, Issue 11 (2018)

Abstract
Dagstuhl Seminar 17452 "Algorithmic Cheminformatics" brought together leading researchers from both chemistry and computer science. The seminar was the second in a series of the Dagstuhl seminars and had a focus on concurrency theory as chemical systems are highly concurrent by nature. Within computer science we focused on formal approaches for chemistry and concurrency theory, including process calculi and Petri nets. The participants surveyed areas of overlapping interests and identified possible fields of joint future research.
Cite as

Jakob L. Andersen, Christoph Flamm, Daniel Merkle, and Peter F. Stadler. Algorithmic Cheminformatics (Dagstuhl Seminar 17452). In Dagstuhl Reports, Volume 7, Issue 11, pp. 28-45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{andersen_et_al:DagRep.7.11.28,
  author =	{Andersen, Jakob L. and Flamm, Christoph and Merkle, Daniel and Stadler, Peter F.},
  title =	{{Algorithmic Cheminformatics (Dagstuhl Seminar 17452)}},
  pages =	{28--45},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{11},
  editor =	{Andersen, Jakob L. and Flamm, Christoph and Merkle, Daniel and Stadler, Peter F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.11.28},
  URN =		{urn:nbn:de:0030-drops-86692},
  doi =		{10.4230/DagRep.7.11.28},
  annote =	{Keywords: Modelling, Simulation, Networks, Semantics / Formal Methods}
}
Document
DOI: 10.4230/LIPIcs.WABI.2017.17
Forbidden Time Travel: Characterization of Time-Consistent Tree Reconciliation Maps

Authors: Nikolai Nojgaard, Manuela Geiß, Daniel Merkle, Peter F. Stadler, Nicolas Wieseke, and Marc Hellmuth

Published in: LIPIcs, Volume 88, 17th International Workshop on Algorithms in Bioinformatics (WABI 2017)

Abstract
Motivation: In the absence of horizontal gene transfer it is possible to reconstruct the history of gene families from empirically determined orthology relations, which are equivalent to event-labeled gene trees. Knowledge of the event labels considerably simplifies the problem of reconciling a gene tree T with a species trees S, relative to the reconciliation problem without prior knowledge of the event types. It is well-known that optimal reconciliations in the unlabeled case may violate time-consistency and thus are not biologically feasible. Here we investigate the mathematical structure of the event labeled reconciliation problem with horizontal transfer. Results: We investigate the issue of time-consistency for the event-labeled version of the reconciliation problem, provide a convenient axiomatic framework, and derive a complete characterization of time-consistent reconciliations. This characterization depends on certain weak conditions on the event-labeled gene trees that reflect conditions under which evolutionary events are observable at least in principle. We give an O(|V(T)|log(|V(S)|))-time algorithm to decide whether a time-consistent reconciliation map exists. It does not require the construction of explicit timing maps, but relies entirely on the comparably easy task of checking whether a small auxiliary graph is acyclic. The algorithms are implemented in C++ using the boost graph library and are freely available at https://github.com/Nojgaard/tc-recon. Significance: The combinatorial characterization of time consistency and thus biologically feasible reconciliation is an important step towards the inference of gene family histories with hor- izontal transfer from orthology data, i.e., without presupposed gene and species trees. The fast algorithm to decide time consistency is useful in a broader context because it constitutes an attractive component for all tools that address tree reconciliation problems.
Cite as

Nikolai Nojgaard, Manuela Geiß, Daniel Merkle, Peter F. Stadler, Nicolas Wieseke, and Marc Hellmuth. Forbidden Time Travel: Characterization of Time-Consistent Tree Reconciliation Maps. In 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 88, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{nojgaard_et_al:LIPIcs.WABI.2017.17,
  author =	{Nojgaard, Nikolai and Gei{\ss}, Manuela and Merkle, Daniel and Stadler, Peter F. and Wieseke, Nicolas and Hellmuth, Marc},
  title =	{{Forbidden Time Travel: Characterization of Time-Consistent Tree Reconciliation Maps}},
  booktitle =	{17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
  pages =	{17:1--17:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-050-7},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{88},
  editor =	{Schwartz, Russell and Reinert, Knut},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2017.17},
  URN =		{urn:nbn:de:0030-drops-76362},
  doi =		{10.4230/LIPIcs.WABI.2017.17},
  annote =	{Keywords: Tree Reconciliation, Horizontal Gene Transfer, Reconciliation Map, Time-Consistency, History of gene families}
}
Document
DOI: 10.4230/DagRep.4.11.22
Algorithmic Cheminformatics (Dagstuhl Seminar 14452)

Authors: Wolfgang Banzhaf, Christoph Flamm, Daniel Merkle, and Peter F. Stadler

Published in: Dagstuhl Reports, Volume 4, Issue 11 (2015)

Abstract
Dagstuhl Seminar 14452 "Algorithmic Cheminformatics" brought together leading researchers from both chemistry and computer science. The meeting successfully aimed at bridging in the apparent gap between the two disciplines. The participants surveyed areas of overlapping interests and identified possible fields of joint future research.
Cite as

Wolfgang Banzhaf, Christoph Flamm, Daniel Merkle, and Peter F. Stadler. Algorithmic Cheminformatics (Dagstuhl Seminar 14452). In Dagstuhl Reports, Volume 4, Issue 11, pp. 22-39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{banzhaf_et_al:DagRep.4.11.22,
  author =	{Banzhaf, Wolfgang and Flamm, Christoph and Merkle, Daniel and Stadler, Peter F.},
  title =	{{Algorithmic Cheminformatics (Dagstuhl Seminar 14452)}},
  pages =	{22--39},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{4},
  number =	{11},
  editor =	{Banzhaf, Wolfgang and Flamm, Christoph and Merkle, Daniel and Stadler, Peter F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.11.22},
  URN =		{urn:nbn:de:0030-drops-49686},
  doi =		{10.4230/DagRep.4.11.22},
  annote =	{Keywords: Graph Transformation Systems, Graph and Hypergraph Invariants, Graph Comparison, Network Flows, Hypergraphs, Formal Languages, Algebraic Chemistry}
}
  • Refine by Author
  • 3 Merkle, Daniel
  • 3 Stadler, Peter F.
  • 2 Flamm, Christoph
  • 1 Agrawal, Shresth
  • 1 Andersen, Jakob L.
  • Show More...

  • Refine by Classification
  • 1 Security and privacy → Distributed systems security

  • Refine by Keyword
  • 1 Algebraic Chemistry
  • 1 Ethereum
  • 1 Formal Languages
  • 1 Graph Comparison
  • 1 Graph Transformation Systems
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2015
  • 1 2017
  • 1 2018
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact