DROPS

Document

DOI: 10.4230/LIPIcs.AFT.2024.6

Analyzing and Benchmarking ZK-Rollups

Authors: Stefanos Chaliasos, Itamar Reif, Adrià Torralba-Agell, Jens Ernstberger, Assimakis Kattis, and Benjamin Livshits

Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)

Abstract

As blockchain technology continues to transform the realm of digital transactions, scalability has emerged as a critical issue. This challenge has spurred the creation of innovative solutions, particularly Layer 2 scalability techniques like rollups. Among these, ZK-Rollups are notable for employing Zero-Knowledge Proofs to facilitate prompt on-chain transaction verification, thereby improving scalability and efficiency without sacrificing security. Nevertheless, the intrinsic complexity of ZK-Rollups has hindered an exhaustive evaluation of their efficiency, economic impact, and performance. This paper offers a theoretical and empirical examination aimed at comprehending and evaluating ZK-Rollups, with particular attention to ZK-EVMs. We conduct a qualitative analysis to break down the costs linked to ZK-Rollups and scrutinize the design choices of well-known implementations. Confronting the inherent difficulties in benchmarking such intricate systems, we introduce a systematic methodology for their assessment, applying our method to two prominent ZK-Rollups: Polygon zkEVM and zkSync Era. Our research provides initial findings that illuminate trade-offs and areas for enhancement in ZK-Rollup implementations, delivering valuable insights for future research, development, and deployment of these systems.

Cite as

Stefanos Chaliasos, Itamar Reif, Adrià Torralba-Agell, Jens Ernstberger, Assimakis Kattis, and Benjamin Livshits. Analyzing and Benchmarking ZK-Rollups. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 6:1-6:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chaliasos_et_al:LIPIcs.AFT.2024.6,
  author =	{Chaliasos, Stefanos and Reif, Itamar and Torralba-Agell, Adri\`{a} and Ernstberger, Jens and Kattis, Assimakis and Livshits, Benjamin},
  title =	{{Analyzing and Benchmarking ZK-Rollups}},
  booktitle =	{6th Conference on Advances in Financial Technologies (AFT 2024)},
  pages =	{6:1--6:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-345-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{316},
  editor =	{B\"{o}hme, Rainer and Kiffer, Lucianna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.6},
  URN =		{urn:nbn:de:0030-drops-209420},
  doi =		{10.4230/LIPIcs.AFT.2024.6},
  annote =	{Keywords: Zero-Knowledge Proofs, ZK-Rollups, Benchmarking, Blockchain Scalability}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2017.45

Lower Bounds for Differential Privacy from Gaussian Width

Authors: Assimakis Kattis and Aleksandar Nikolov

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract

We study the optimal sample complexity of a given workload of linear queries under the constraints of differential privacy. The sample complexity of a query answering mechanism under error parameter alpha is the smallest n such that the mechanism answers the workload with error at most alpha on any database of size n. Following a line of research started by Hardt and Talwar [STOC 2010], we analyze sample complexity using the tools of asymptotic convex geometry. We study the sensitivity polytope, a natural convex body associated with a query workload that quantifies how query answers can change between neighboring databases. This is the information that, roughly speaking, is protected by a differentially private algorithm, and, for this reason, we expect that a "bigger" sensitivity polytope implies larger sample complexity. Our results identify the mean Gaussian width as an appropriate measure of the size of the polytope, and show sample complexity lower bounds in terms of this quantity. Our lower bounds completely characterize the workloads for which the Gaussian noise mechanism is optimal up to constants as those having asymptotically maximal Gaussian width. Our techniques also yield an alternative proof of Pisier's Volume Number Theorem which also suggests an approach to improving the parameters of the theorem.

Cite as

Assimakis Kattis and Aleksandar Nikolov. Lower Bounds for Differential Privacy from Gaussian Width. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kattis_et_al:LIPIcs.SoCG.2017.45,
  author =	{Kattis, Assimakis and Nikolov, Aleksandar},
  title =	{{Lower Bounds for Differential Privacy from Gaussian Width}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{45:1--45:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.45},
  URN =		{urn:nbn:de:0030-drops-72368},
  doi =		{10.4230/LIPIcs.SoCG.2017.45},
  annote =	{Keywords: differential privacy, convex geometry, lower bounds, sample complexity}
}

Search Results

Documents authored by Kattis, Assimakis

Analyzing and Benchmarking ZK-Rollups

Abstract

Cite as

Lower Bounds for Differential Privacy from Gaussian Width

Abstract

Cite as

Thanks for your feedback!

Could not send message