Open Problems Backlog

[adlrocha]

Background

I've spent some time trying to source open problems in the field to create an "Open Problems Backlog" for CL that we could work on collaboratively with the wider community. I realized early on my endeavor that the outcome of a single person working on this would be quite limited and biased, so I thought it could be a good idea to open a discussion where we can collaboratively build this backlog together and assemble a more complete view of the state-of-the-art.

Goals

The goal of this discussion is to:

• Identify interesting open problems in the field and clearly define them.
• Share papers and related work to get a better sense of the state-of-the-art and what others are working on.
• Graduate open problems into their own discussions to focus the debate and come up with potential solutions and projects.
  I welcome everyone to contribute to the discussion. I'll try to periodically gather all your contributions in this first message so everyone can have an overview of the "state of affairs" without having to navigate the whole discussion.

Disclaimer: Some of the sections are still WIP so feel free to have a first stab at it if you will. Also, feel free to contribute with papers, ideas, new open problems, interesting projects, or a better description of the existing problems. And if you rather discuss sync, drop us a message in the #consensus channel at Filecoin Slack.

Open Problems

Hierarchical/Mergeable Consensus

For a decentralized protocol to work in an offline situation, it's necessary for different groups running the same protocol to be able to connect to each other and continue running the original protocol across the full network. One particularly useful primitive would be a mergeable cryptocurrency consensus mechanism, allowing all members of two groups to agree on the state of a transaction ledger shortly after the first time the two groups are able to transfer any information.

• Hierarchical consensus: A horizontal scaling framework for blockchains
• Making CRDTs Byzantine Fault Tolerant
• Free2Shard: Adversary-resistant Distributed Resource Allocation for Blockchains

Stateless Consensus

Blockchains haven't yet solved efficiently the problem of growing state. In order to validate transactions, full-nodes need to store lots of data that is generally impractical for many nodes to keep in working memory, and is thus moved to slow permanent storage. In many cases, peers choose not to even attempt becoming a full-node because of the storage and hardware requirements involved. This can harm the level of decentralization of a network (only a few keep the full state), and prevents end-user devices with low hardware requirements from being active participants of the network. Building a stateless consensus algorithm could tackle this problem.

• Why Stateless?
• SoK: Vector Commitments
• Edrax: A Cryptocurrency with Stateless Transaction Validation
• Mina: Decentralized Cryptocurrency at Scale
• Light Clients for Lazy Blockchains

Data availability and retrievability

How can nodes with a partial view of a blockchain (eg, “light clients” downloading only the block header) be sure that when a new block is produced, all of the data (ie, transactions) in that block was actually stored in the network? How can these clients be sure that the state of their smart contract/transaction can still be retrieved from the network? This problem is linked directly with some of our projects: when a checkpoint is committed in hierarchical consensus (or in Bitcoin), how can we be sure that the subnet or data layer responsible for the storage checkpoints will provide us with the data we need? How can we be sure that we will have access to the state we need to create a fraud proof?

And regarding data retrievability, how can clients delegating data storage have the guarantee that the data can be retrieved at any moment (i.e., guaranteed retrieval)?

• Fraud and Data Availability Proofs Maximising Light Client Security and Scaling Blockchains with Dishonest Majorities
• Information Dispersal with Provable Retrievability
• Lazy Ledger
• Proof of Custody
• Data availability checks
• 2D data availability with Kate commitments
• Narwhal and Tusk: a DAG-based mempool and efficient BFT consensus

Sponsored transactions and alternative spam prevention mechanisms

Users need to have some currency in order to interact with any blockchain. There is no way to pay on FIAT and enjoy the decentralization traits of blockchain networks, as this service is only provided (or not even) by centralized services. This is a huge barrier of entry for end-users into the crypto-world. If, for instance, one wants to store some data in the Filecoin network by themselves, with their own identity, they need to have their account actor initialized, and pay some gas even if they are performing a free deal.

Big companies can’t own crypto, or they don’t want to deal with the overhead (in terms of regulation, taxes, or even technology), but they want to own their transactions and be “one more in the pack”. To lower the barrier of entry for these kinds of users, we need to provide a way to delegate gas payments to someone else. Gas main purpose is to: incentivize message validation in the very low congestion regime; align supply of transaction validation with demand as congestion increases; and as a spam prevention mechanism in the network. Finding alternative ways to achieve these goals without the need of gas could lower the barriers of entry to the web3.

• EIP3074
• Zcash discusssion on alternative gas models
• First and second price auctions
• Multidimensional gas

Resource commitment protocols

"There are systems where miners have on-chain submission requirements as part of the protocol. In Filecoin specifically, all miners must submit on-chain daily proofs of storage as part of their maintenance. Can we re-use those on-chain submissions for decentralized checkpointing?"

• Re-use existing protocol-specific messages for decentralized checkpointing #79
• Incentivize inclusion of stake update messages #81
• Storage based consensus without updates #86
• Formalization of Verifiable Resource Commitments #82

Pluggable consensus or Consensus as a Service

WIP

As the core function of the consensus system of a distributed ledger is to order transactions and ensure their availability, consensus participants do not necessarily need to be concerned with the contents of those transactions. There are already several proposals that decouple consensus from execution, but can we have a common consensus layer for share by several networks? Can several smart contract platforms share the same state and data layer, and execute transactions "their own way"? And if we decouple execution from ordering, and we can implement a clear interface and common runtime for consensus algorithms, can we have pluggable consensus (i.e. a single consensus implementation re-usable in several networks implementing this runtime)? What trust assumptions should be used in such architecture? Is it possible to design a system where consensus clients and the consensus server are decoupled and don't trust each other (consensus client and server don't share private keys)?

• Idea: FVM as a consensus runtime.
• Lazy Ledger
• Tendermint consensus as a service in Filecoin(spec, implementation)

Light consensus

WIP

• Narwhal and Tusk: a DAG-based mempool and efficient BFT consensus

Parallel execution

TODO: Description of the open problem here

• Rethinking serializable multiversion concurrency control
• An Overview of Deterministic Database Systems
• Caracal: Contention Management with Deterministic Concurrency Control
• Block-STM: Scaling Blockchain Execution by Turning Ordering Curse to a Performance Blessing

WIP
@quema, do you mind sharing a brief overview of your work exploring the state-of-the-art of parallel execution.

Verifiable computation, execution, and state changes

WIP

• Free2Shard: Adversary-resistant Distributed Resource Allocation for Blockchains

[LefKok]

This is a great list very close to what I have been reading and researching!
Let me add some comments:

On Hierarchical consensus, a natural step is to couple it with verifiable computation this reduces the problem of firewalling cross-net transactions (which can be done only at a limited fungible token level with the existing framework) to forcing consistency and optionally data availability.

What do I mean by this? I imagine an architecture where child chains only commit hashes of their blocks (similar to the sharding approach of free2shard (https://dl.acm.org/doi/10.1145/3508031)) and propagate aggregatable zk-proofs of correct execution as well.
Then at any point in time, there cannot be forks alive in the system (thanks to the single-source property of using a tree for the hierarchy) and there cannot be invalid transactions (thanks to the verifiable computation proofs). The only final open question is data availability. Thanks to the verifiable computation this is no longer a safety-critical problem but merely a liveness/censorship resistance issue.

How to make this architecture scalable is both an interesting systems problem (efficient communication and discovery of BFT P2P subnets) and a cryptography problem (efficient aggregation of verifiable computation)

Stateless consensus: Although interesting the consensus is not really stateless, instead it pushed the state to the client. I would be careful with this assumption and do a rigorous research on how clients can recover from failures

Data availability: I would add Narwhal to the list since the DAG is actually a causally ordered data-availability layer

Parallel Execution Papers:

https://arxiv.org/pdf/1412.2324.pdf
https://www.cs.umd.edu/~abadi/papers/abadi-cacm2018.pdf
https://dl.acm.org/doi/abs/10.1145/3477132.3483591
https://arxiv.org/abs/2203.06871

[adlrocha]

This is great, @LefKok. Thanks. I added your contributions to the top message.

What do I mean by this? I imagine an architecture where child chains only commit hashes of their blocks (similar to the sharding approach of free2shard (https://dl.acm.org/doi/10.1145/3508031)) and propagate aggregatable zk-proofs of correct execution as well.
Then at any point in time, there cannot be forks alive in the system (thanks to the single-source property of using a tree for the hierarchy) and there cannot be invalid transactions (thanks to the verifiable computation proofs). The only final open question is data availability. Thanks to the verifiable computation this is no longer a safety-critical problem but merely a liveness/censorship resistance issue.
How to make this architecture scalable is both an interesting systems problem (efficient communication and discovery of BFT P2P subnets) and a cryptography problem (efficient aggregation of verifiable computation)

Regarding the above, I completely agree. I feel this is the architecture we should pursue in hierarchical consensus. If we can complement this with a nice data availability solution, we could come up with the really nice system. I'll read the free2shard paper (I wasn't aware of it), and let's discuss your proposed architecture in the scope of the HC project.

[LefKok]

One thing we might want to keep in mind for a future paper on HC is the discussion on censorhsip-resitence for the consensus protocol.
Without it we might have no liveness for cross-shard transactions and even scarier no safety if we rely on fraud proofs instead of Lurk
This gives us a nice way to plug B1/B3 with Y3 if we want to write a full paper since censorship resistant consensus ideally resilient against an adaptive/mobile adversary becomes much more important in the Hierarchical Consensus framework

[adlrocha]

I agree. I think the most concerning issues are: parents censoring or prioritizing specific children, or even intermediate subnets choosing not to route messages from/to a specific one.

Making this its own discussion to discuss it further: #98