Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: deprecated: topos theory

Topic: Blockdags

view this post on Zulip Mike Stay (Apr 03 2020 at 22:01):

There are a bunch of recent consensus algorithms that build a directed acyclic graph of blocks rather than a chain of blocks. Casanova is one of these, named for Geoffrey Rush's character Casanova Frankenstein in Mystery Men. There's a scene where he's confronted by Captain Amazing in which they have this exchange:

Capt. Amazing: I knew you couldn't change.
Casanova Frankenstein: I knew you'd know that.
Capt. Amazing: Oh, I know that. AND I knew you'd know I'd know you knew.
Casanova Frankenstein: But I didn't. I only knew that you'd know that I knew. Did you know THAT?
Capt. Amazing: (Frowns, decides to fake it.) Of course.

By watching to see which validators issue blocks that refer to other blocks, validators gain knowledge about who knew who knew what:

  1. When a validator sees that a fault-tolerant majority has built on top of a block, it knows that the transactions in the block will eventually become accepted by all other behaving validators.
  2. When a validator sees that a fault-tolerant majority sees that a fault-tolerant majority has seen the block, the block is finalized: no other message can change the network's mind. This true finalization prevents the kind of 51% attack we've seen recently on networks like Ethereum classic.
  3. When a validator sees that everyone has seen that everyone has seen a block, the block will never be referenced again by a behaving validator and the block can be archived. This gets rid of the need to store the entire history of the network to be a contributing validator.

These kinds of eventual knowledge seem amenable to modeling with a truth object in a topos. A dag is a "skeletal" graph in much the same way that a poset is a skeletal preorder. A dag whose blocks are labeled with validators is a mashup of the theory of graphs and the theory of multisets. On this topic I'd like to work out a category whose category of presheaves is a topos in which we can reason about what validators know about what other validators know about, and so on.

view this post on Zulip Morgan Rogers (he/him) (Apr 03 2020 at 22:49):

That's a lot to take in with no diagrams and with a limited knowledge of blocks, but if you break it down for me a bit I can very likely contribute to the building of a relevant topos.

view this post on Zulip Morgan Rogers (he/him) (Apr 03 2020 at 22:51):

First, I need to understand what the entities involved are. There are validators and blocks; how are new blocks generated/added to this system? Are the majorities you refer to out of the population of validators? Is that population fixed or constrained somehow?

view this post on Zulip Mike Stay (Apr 03 2020 at 23:43):

I added a link to the paper above.

The theory of labeled graphs has three objects E (directed edges), B (blocks, the vertices of the graph), and V (validators). It has three morphisms s, t: E -> B for source and target of each edge, and l:B -> V labeling the block with the validator that created it.

view this post on Zulip Mike Stay (Apr 03 2020 at 23:45):

In the Casanova protocol, there's a fixed population of validators, all known to each other. It's possible to add stuff to the protocol to kick out validators that are misbehaving and to allow new validators to join, but that's not critical for finding consensus.

view this post on Zulip Mike Stay (Apr 03 2020 at 23:48):

Validators all issue a block once every time step; they all keep time independently, so there may be drift between them. The network is not reliable, but the liveness proof assumes that there is some upper bound (it doesn't need to be known, just exist) on the time that it takes for a message to be delivered. Essentially that means people will notice when the network is down and it'll eventually get fixed. Each block has to refer to the latest block that validator has received from each of the other validators.

view this post on Zulip Mike Stay (Apr 03 2020 at 23:49):

Blocks contain transactions, but that's an optimization. We can imagine that each transaction lives in its own block.

view this post on Zulip Mike Stay (Apr 03 2020 at 23:51):

Transactions have "conflict domains"; that is, there's a way to tell when two transactions conflict with each other. A useful case to keep in mind is when users have accounts and payments out of the accounts are totally ordered; you can think of each account as having a series of check numbers. If Alice tries to pay both Bob and Carol with the same check number, that is a conflict. None of Alice's payments conflict with Bob's or Carol's.

view this post on Zulip Mike Stay (Apr 03 2020 at 23:54):

I mentioned the theory of labeled directed graphs, but that doesn't capture the time-dependent aspect of the system. The blockdag that a validator v sees at any time is a subdag of all future blockdags. And it is not so much subdags that we care about as much as the n-level witnessing of blocks.

view this post on Zulip Morgan Rogers (he/him) (Apr 08 2020 at 16:31):

@Mike Stay this looks like a Hard Problem. I'm currently thinking about classifying spaces of monoids (discussion in the category theory stream), but perhaps there will come a time in the not too distant future where I'll put some serious thought into this. Good luck in the mean time!