A rollup is a scaling solution built on top of an existing blockchain. Rollups separate execution from consensus, but are required to post the data used for state updates to the underlying blockchain. This data is required to ensure that execution of state updates are performed correctly. As writing data to a public blockchain is not free, rollups are incentivized to minimize the amount of data they post on-chain. Rollups therefore aggregate and compress the data used for executions in order to save on fees associated with writing data to the blockchain. In this work, we explore the methods for posting data on-chain and the compression techniques used by real-world rollups. We explore differences in implementations and contrast the approaches used by both optimistic and zero-knowledge rollups. We also explore approaches which enable domain-specific compression, consider upcoming changes to data storage on Ethereum, and suggest improvements for rollup compression.

The blockchain ecosystem has evolved into a multi-chain world with various blockchains vying for use. Although each blockchain may have its own native cryptocurrency or digital assets, there are use cases to transfer these assets between blockchains. Systems that bring these digital assets across blockchains are called bridges, and have become important parts of the ecosystem. The designs of bridges vary and range from quite primitive to extremely complex. However, they typically consist of smart contracts holding and releasing digital assets, as well as nodes that help facilitate user interactions between chains. In this paper we first provide a high level break-down of components in a bridge and the different processes for some bridge designs. Then, we analyse past exploits in the blockchain ecosystem that specifically targeted bridges. In doing this, we identify risks associated with bridge components.

The crossing number is the smallest number of pairwise edge crossings when drawing a graph into the plane. There are only very few graph classes for which the exact crossing number is known or for which there at least exist constant approximation ratios. Furthermore, up to now, general crossing number computations have never been successfully tackled using bounded width of graph decompositions, like treewidth or pathwidth. In this paper, we show that the crossing number is tractable (even in linear time) for maximal graphs of bounded pathwidth 3. The technique also shows that the crossing number and the rectilinear (a.k.a. straight-line) crossing number are identical for this graph class, and that we require only an $$O(n)\times O(n)$$ O(n)×O(n)-grid to achieve such a drawing. Our techniques can further be extended to devise a 2-approximation for general graphs with pathwidth 3. One crucial ingredient here is that the crossing number of a graph with a separation pair can be lower-bounded using the crossing numbers of its cut-components, a result that may be interesting in its own right. Finally, we give a $$4{\mathbf{w}}^3$$ 4w3-approximation of the crossing number for maximal graphs of pathwidth $${\mathbf{w}}$$ w. This is a constant approximation for bounded pathwidth. We complement this with an NP-hardness proof of the weighted crossing number already for pathwidth 3 graphs and bicliques $$K_{3,n}$$ K3,n.

In this paper, we prove that every planar graph has a 1-string B_2-VPG representation - a string representation using paths in a rectangular grid that contain at most two bends. Furthermore, two paths representing vertices u, v intersect precisely once whenever there is an edge between u and v.