Exact and Linear-Time Gas-Cost Analysis

Static Analysis Symposium


Blockchains support execution of smart contracts: programs encoding complex transaction protocols between distrusting parties. Due to their distributed nature, blockchains rely on third-party miners to execute and validate transactions. Miners are compensated by charging users with gas based on the execution cost of the transaction. To compute the exact gas cost, blockchains track gas cost dynamically creating its own overhead. This paper presents a static exact gas-cost analysis technique that can be employed to eliminate dynamic gas tracking. This approach presents further benefits such as providing miners with a trusted gas bound that can be verified in linear time, and eliminating out-of-gas exceptions. To handle recursion and unbounded computation, we propose a novel amortization technique that stores gas inside data structures. We have implemented our analysis technique in a tool called GasBoX that takes a contract as input and infers the gas cost of its functions automatically. We have evaluated GasBoX on 13 standard smart contracts borrowed from real-world blockchain projects. Our soundness theorem proves that the gas bound inferred by GasBoX exactly matches the gas cost at runtime and no dynamic gas tracking is necessary.

Related Publications

All Publications

PETS - July 16, 2021

HashWires: Hyperefficient Credential-Based Range Proofs

Konstantinos (Kostas) Chalkias, Shir Cohen, Kevin Lewi, Fredric Moezinia, Yolan Romailler

ICML - July 17, 2021

Recovering AES Keys with a Deep Cold Boot Attack

Itamar Zimerman, Eliya Nachmani, Lior Wolf

Trusted Smart Contracts Workshop at Financial Cryptography (FC) - May 12, 2021

Reactive Key-Loss Protection in Blockchains

Sam Blackshear, Konstantinos (Kostas) Chalkias, Panagiotis Chatzigiannis, Riyaz Faizullabhoy, Irakliy Khaburzaniya, Lefteris Kokoris Kogias, Joshua Lind, David Wong, Tim Zakian

VLDB - July 31, 2021

CALYPSO: Private Data Management for Decentralized Ledgers

Eleftherios Kokoris-Kogias, Enis Ceyhun Alp, Linus Gasser, Philipp Jovanovic, Ewa Syta, Bryan Ford

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookie Policy