Search

Your search keyword '"Albert Rubio"' showing total 139 results
Start Over Author "Albert Rubio"
139 results on '"Albert Rubio"'

3. The computability path ordering

Author

Frédéric Blanqui, Jean-Pierre Jouannaud, and Albert Rubio

Subjects
computer science - logic in computer science, Logic, BC1-199, Electronic computers. Computer science, QA75.5-76.95
Abstract

This paper aims at carrying out termination proofs for simply typed higher-order calculi automatically by using ordering comparisons. To this end, we introduce the computability path ordering (CPO), a recursive relation on terms obtained by lifting a precedence on function symbols. A first version, core CPO, is essentially obtained from the higher-order recursive path ordering (HORPO) by eliminating type checks from some recursive calls and by incorporating the treatment of bound variables as in the com-putability closure. The well-foundedness proof shows that core CPO captures the essence of computability arguments \'a la Tait and Girard, therefore explaining its name. We further show that no further type check can be eliminated from its recursive calls without loosing well-foundedness, but for one for which we found no counterexample yet. Two extensions of core CPO are then introduced which allow one to consider: the first, higher-order inductive types; the second, a precedence in which some function symbols are smaller than application and abstraction.

Published
2015
Full Text
View/download PDF

22. Super-optimization of Smart Contracts

Author

Elvira Albert, Pablo Gordillo, Alejandro Hernández-Cerezo, Albert Rubio, and Maria A. Schett

Subjects
Software
Abstract

Smart contracts are programs deployed on a blockchain. They are executed for a monetary fee paid in gas —a clear optimization target for smart contract compilers. Because smart contracts are a young, fast-moving field without (manually) fine-tuned compilers, they highly benefit from automated and adaptable approaches, especially as smart contracts are effectively immutable, and as such need a high level of assurance. This makes them an ideal domain for applying formal methods. Super-optimization is a technique to find the best translation of a block of instructions by trying all possible sequences of instructions that produce the same result. We present a framework for super-optimizing smart contracts based on Max-SMT with two main ingredients: (1) a stack functional specification extracted from the basic blocks of a smart contract, which is simplified using rules capturing the semantics of arithmetic, bit-wise, and relational operations, and (2) the synthesis of optimized blocks , which finds—by means of an efficient SMT encoding—basic blocks with minimal gas cost whose stack functional specification is equal (modulo commutativity) to the extracted one. We implemented our framework in the tool syrup 2.0 . Through large-scale experiments on real-world smart contracts, we analyze performance improvements for different SMT encodings, as well as tradeoffs between quality of optimizations and required optimization time.

Published
2022

45. CIRCOM: A Robust and Scalable Language for Building Complex Zero-Knowledge Circuits

Author

Jordi Baylina, Albert Rubio, Miguel Isabel, Marta Belles, and Jose L. Muñoz-Tapia

Abstract

A zero-knowledge (ZK) proof guarantees that the result of a computation is correct while keeping part of the computation details private. Some ZK proofs are tiny and can be verified in short time, which makes them one of the most promising technologies for solving two key aspects: the challenge of enabling privacy to public and transparent distributed ledgers and, enhancing the scalability limitations of distributed ledgers. Most practical ZK systems require the computation to be expressed as an arithmetic circuit that is encoded as a set of equations called rank-1 constraint system (R1CS).In this paper, we present \circom, a programming language and a compiler for designing arithmetic circuits that are compiled to R1CS. More precisely, with \circom, programmers can design arithmetic circuits, and the compiler outputs (i) a file with the R1CS description, (ii) \wasm and \cpp programs to efficiently compute all values of the circuit. We also provide an open-source library called \circomlib, with multiple circuit templates. Moreover, \circom can be complemented with \snarkjs, a tool for generating and validating ZK proofs from R1CS. Altogether, our software tools abstract the complexity of the proving mechanisms and provide a friendly interface to model low-level descriptions of arithmetic circuits.

Published
2022

Catalog

Books, media, physical & digital resources
See catalog results