Blockstack is not a DAG

#1

There has been a recent flurry of questions about why Blockstack does not operate on top of a DAG. This forum post is meant to address these questions in one place.

Please direct any further questions on this topic to this forum post, instead of starting a new topic.

DAGs are only useful if you have commutative and associative transactions

Representing state-transitions as a DAG while benefiting from having a DAG in the first place requires that some operations be associative and commutative. This lets different nodes process a set of transactions in a different order, and still arrive at the same chain state. In doing so, nodes do not need to coordinate as much.

In token-based networks, the DAG structure allows different nodes to process the same transactions in different orders in some cases, since a + (b + c) == (a + b) + c and a + b = b + a for any numbers. For example, if Alice has 4 tokens, then it’s okay in a DAG network for two transactions ("alice" pays "bob" 1 token) and ("alice" pays "charlie" 2 tokens) to occur in different orders – the final balances of alice, bob, and charlie will be the same regardless of the order applied. Similarly, if Bob and Charlie also have 4 tokens, then the transactions ("alice" pays "bob" 1 token), ("bob" pays "charlie" 2 tokens), and ("charlie" pays "dan" 1 token) can safely be applied in any order – Alice can pay Bob, Bob can pay Charlie, and then Charlie can pay Dan, or Bob can pay Charlie, Charlie can pay Dan, and Alice can pay Bob.

Not all such transactions are commutative and associative, however. For example, if Alice has 0 tokens, and Bob submits a transaction to send her 4 tokens, then Alice’s transaction to send Charlie 3 tokens cannot be processed before Bob sends Alice tokens. These transactions are not commutative – there is a dependency between the Bob-pays-Alice and Alice-pays-Charlie transactions. This would be represented in the DAG by a directed edge ("bob" gives "alice" 4 tokens) --> ("alice" gives "charlie" 3 tokens), and all nodes will need to process two transactions in the same order.

Name-ownership operations are neither commutative nor associative

What if you had a blockchain network where state-transitions were neither commutative nor associative? If this was true, then all transactions would need to be processed in the same order for two nodes to arrive in the same state. The transactions would be in a total order instead of a partial order, removing any benefit from using a DAG to represent state transitions.

This is true for name registration operations. If Alice and Bob both race to register alice.id, then there can be at most one winner, and that winner must be the first person to register it. The state of the chain after applying two operations ("alice" registers "alice.id") and ("bob" registers "alice.id") is not the same as the state of the chain had we applied ("bob" registers "alice.id") and then ("alice" registers "alice.id"). Therefore, all nodes must apply all register transactions in the same order to correctly decide who owns alice.id (or any name).

Name operations on the same name are neither commutative nor associative

The same applies to transfers and renewals on the same name (since renewals can transfer a name to a new owner). If Alice submits a transaction to transfer foo.id from herself to Bob, and Bob submits a transaction to transfer foo.id from himself to Charlie, and Charlie submits a transaction to transfer foo.id from himself to Dan, then all of these transfers must be applied in the same order to preserve the safety property only the name’s owner is able to transfer a name.

This also applies to name updates on the same name. In Blockstack, your name is tied to some storage routing state that points to where your data is hosted. If you change where you store your data, then all nodes must process your changes in the same order so they know where your latest storage location is. This requirement imposes a total ordering of name updates on a specific name.

Name operations on different names may be reordered

The only operations that are commutative and associative in Blockstack are token transfers and name updates/transfers/renewals/revokes on different names. Token transfers are commutative and associative for the same reasons a DAG network’s tokens are. Alice and Bob can modify their own names independently of one another (these operations would be concurrent), so nodes can process these transactions in a different order and arrive at the same state.

Will Blockstack be ported to a DAG?

Not by us. There are not enough benefits to be realized from doing so.

Will you help me port Blockstack to a DAG?

No.

Are DAGs a viable alternative to blockchains?

I have yet to see one. All systems that call themselves DAG networks that I know of fail on at least one of these required tasks.

  • Preventing Sybils from flooding the network with garbage or splitting the network state
  • Allowing anyone to “mine” on the network – i.e. support open-membership consensus
  • Allowing nodes to actually process commutative and associative transactions in different orders (i.e. there are systems that call themselves DAGs that implicitly force a total ordering on transactions).

Fascinating! Can I reach out to you privately for more information?

No. Ask it here. Private requests will be ignored.

Can I shill my favorite DAG on this forum?

If you do, I will delete your account and block your IP address. We take a very dim view of shilling.

2 Likes
Total ordering of transactions
Why again blockchain?
Which are the cases where transactions happens in blockstack?
Blockstack with Blockchain
#2

Not to jump on the DAG bandwagon, but I am curious…

Could proof-of-burn still work on a DAG, and therefore the STACKS (sub-)blockchain still work with a DAG chain as the root instead of, say, BTC as the root?

I saw people talking about how they want to port it to a DAG but if Blockstack itself is switching to it’s own STACKS/sub-chain form of doing things, then it seems trying to port it is a wasted effort.

#3

Hey Jude,

Thanks for your reply and creating a forum specifically for this query

Really appreciate jude

So I’ll address any kind of issues on this forum instead of
Why again blockchain?
and
Which are the cases where transactions happens in blockstack?

Thank you.

#4

Could proof-of-burn still work on a DAG, and therefore the STACKS (sub-)blockchain still work with a DAG chain as the root instead of, say, BTC as the root?

In theory? Probably, but it would be more difficult since it would make it harder to build light clients (which is going to be vital for supporting app chains). Since DAGs don’t have blocks, it’s not clear to me how to efficiently represent the validation work done by a full node in space and time complexity that a light client can handle.

In practice? No. I have yet to see a DAG network that actually works as claimed.

1 Like