AT
A. Tatabitovska
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
2 records found
1
Maximum Satisfiability (MaxSAT) is a known problem within the optimization field which has led many different solving approaches to be devised in the last several decades. From Linear Search to unsatisfiable core-based solvers, many MaxSAT algorithms rely on cardinality constraints to express how many soft clauses can be violated at most. However, as MaxSAT is expressed in the Conjunctive Normal Form, there is a need to translate, or encode, these cardinality constraints into CNF. A popular encoding algorithm, the Totalizer Encoding, is used within these solvers - a system of encoding that builds a binary tree to express the cardinality constraint. This paper aims to introduce an alternate construction for the Totalizer Encoding, referred to as the Layered Totalizer Encoding, which interleaves the mechanics of encoding and solving as to cut down on runtime as well as potentially solve previously unsolved instances. The research shows that the Layered Totalizer Encoding outperforms Linear Search on average, solves more instances than Linear Search, and can be tuned through heuristics to show even more favorable results. Moreover, the Layered Totalizer Encoding is shown to not only work as a standalone algorithm, but can also boost the performance of the OLL algorithm.
...
Maximum Satisfiability (MaxSAT) is a known problem within the optimization field which has led many different solving approaches to be devised in the last several decades. From Linear Search to unsatisfiable core-based solvers, many MaxSAT algorithms rely on cardinality constraints to express how many soft clauses can be violated at most. However, as MaxSAT is expressed in the Conjunctive Normal Form, there is a need to translate, or encode, these cardinality constraints into CNF. A popular encoding algorithm, the Totalizer Encoding, is used within these solvers - a system of encoding that builds a binary tree to express the cardinality constraint. This paper aims to introduce an alternate construction for the Totalizer Encoding, referred to as the Layered Totalizer Encoding, which interleaves the mechanics of encoding and solving as to cut down on runtime as well as potentially solve previously unsolved instances. The research shows that the Layered Totalizer Encoding outperforms Linear Search on average, solves more instances than Linear Search, and can be tuned through heuristics to show even more favorable results. Moreover, the Layered Totalizer Encoding is shown to not only work as a standalone algorithm, but can also boost the performance of the OLL algorithm.
Front-running is the illegal practice of obtaining information unavailable to the general public with regards to upcoming transactions and performing actions based on this knowledge as to gain profit. This type of attack has been an issue since the introduction of the first stock market and it is not a surprise it has spread into blockchain technologies. With the invention of Decentralized Exchange Systems, this type of exploit has been an even more common occurrence that puts both the user and system at a disadvantage. This paper aims to explore the circumstances that enable front-running in UniSwap, one of the most used DeFi Systems as of the writing of this paper. Factors such as lack of privacy, slippage, as well as a miner’s role in the exploit are analysed in a broad and UniSwap-centered context to provide more insight to the problem. Moreover, this paper analyses a potential adjustment of a commit-reveal scheme, a time lock scheme, and off-chain slippage limit as possible solutions and an overall analysis of the proposed solutions. Through comparison and adjustments of different solutions, this paper strives to expose where the root of the problem lies - the Ethereum blockchain itself.
...
Front-running is the illegal practice of obtaining information unavailable to the general public with regards to upcoming transactions and performing actions based on this knowledge as to gain profit. This type of attack has been an issue since the introduction of the first stock market and it is not a surprise it has spread into blockchain technologies. With the invention of Decentralized Exchange Systems, this type of exploit has been an even more common occurrence that puts both the user and system at a disadvantage. This paper aims to explore the circumstances that enable front-running in UniSwap, one of the most used DeFi Systems as of the writing of this paper. Factors such as lack of privacy, slippage, as well as a miner’s role in the exploit are analysed in a broad and UniSwap-centered context to provide more insight to the problem. Moreover, this paper analyses a potential adjustment of a commit-reveal scheme, a time lock scheme, and off-chain slippage limit as possible solutions and an overall analysis of the proposed solutions. Through comparison and adjustments of different solutions, this paper strives to expose where the root of the problem lies - the Ethereum blockchain itself.