Thread by @alephium

Hi @Twitter! Today is TTT (tech-thread tuesday).

We’ll explain how Blockflow prevents double-spending using #UTXO, #PoW and #DAG!

We are going deep-nerdy, so strap-on!

This 🧵is inspired from a convo between @wachmc & @programmargorp in our Discord discord.com/channels/74774…

This started well, but while writing it, it took on a life of its own as we went further down the rabbit-hole, so it’s a bit of a monster thread! Please bear with us!

First, some definitions! You can skip that if you’re already an expert!

Double-spending is the risk that a digital currency can be spent twice or more. It’s a big problem that you have when you remove the central authority (think:bank) that ensures that you don’t spend more than you have.

An Unspent Transaction Output (UTXO) is the technical term to describe the ownership of an amount of digital currency (like #Bitcoin or Alephium). It’s one of the two main record keeping models of blockchains, the other one being the account model (used by #Ethereum & Co).

PoW is a consensus mechanism allowing the #Bitcoin and other blockchains to propose blocks grouping, ordering and timestamping transactions without a central authority. In Alephium’s case it’s a variant called #PoLW (Proof of Less Work), but that is a story for another day!

DAG (for “Directed Acyclic Graph”) is a method to organize the complexity of multiple parallel nodes (in our case each node represents a block) in a directional coherent flow of data.

Think about it as a way to optimize a complicated tree-like structure into a simpler flow.

So, let’s get to our question! Starting with how does Bitcoin prevent double-spending?

In Bitcoin, double-spending is prevented by the combination of two technologies: #UTXO & #PoW.

The UTXOs are ordered into chained & timestamped blocks (eg. block-chain) rendering them nearly impossible to change/double-spend without controlling 51% of the energy spent by the entire Bitcoin network (PoW)...

And the more blocks are added (~ every 10 minutes), the harder it gets. That is why finality in #Bitcoin takes a few blocks: the more blocks are mined, the more energy it would take to rewrite history.

Transactions are usually considered final after 6 blocks (~60min).

If you think managing UTXOs securely on one chain (ie #Bitcoin) is complicated, think how hard it becomes when you have multiple, parallel chains, all producing blocks at the same time and trying to maintain that in a coherent ledger!

To be able to manage more transactions per second than #Bitcoin, Alephium is a sharded blockchain.

As of today, it runs on 4 groups of 4 shards each, meaning 16 shards running in parallel (shards ~ internal chains).

Blockflow, our consensus & sharding algorithm, defines the rules on how, on each shard, transactions get mined into blocks every 64 seconds.

16 simultaneous blocks every minute or so!

How do we maintain coherence among those blocks? We create dependencies!

A dependency describes the relationship of UTXOs across blocks and specifies the particular relationships between inputs and outputs across these blocks.

For example in #Bitcoin, a block contains a hash of the previous block, that’s a dependency across time!

In Alephium, on top of the time dependency (like in #Bitcoin), each block includes the hash of the latest blocks of all the other shards from its group, and the blocks from the intra-shards of all the other groups!

E.g. for a block in shard (0,0), there are dependencies to shards (0,0) (0,1) (0,2) (0,3) and to the other groups 1, 2, 3!

And if we generalize, if we have G groups, each block in a shard will include the hash of the blocks from 2G - 1 shards.

Wanna read more about the math stuff, reach out to our whitepaper!

github.com/alephium/white…

This is awesome, because first it means that effectively the security is accumulated across all shards.

The more mining on any shards, the more security on the whole network: what an elegant mechanism!

But this is also precisely what gives us scalability, which is the point of having sharding in the first place!

More shards, more blocks, more transactions!

But there’s a complication!

How do the miners know which transactions to include in which block and when?

And how do they know which dependency needs to come first, to where and in general maintain a single path forward across so many shards?

And here #Blockflow algorithm comes in!

It is the mechanism allowing only the correct dependencies to be mined, in the correct order, so that there’s only one legitimate version of events!

It allows miners to know which are the good dependencies and pack valid transactions.

A new block is mined when this block together with its dependencies has the heaviest accumulated weight (intuitively most accumulated difficulties).

With the 2G-1 dependencies for each of the blocks described above, the #BlockFlow algorithm knows just enough information to ensure that no UTXO can be double spent even across shards.

And this is how you ensure double-spending prevention in a sharded #PoW blockchain like Alephium!

If you’re a dev, join us on GitHub, discover our code, and contribute! github.com/alephium

Join us also on Discord and ask questions! The team is there to answer almost all of the time.
discord.gg/JErgRBfRSB

If you went through that complete thread, thank you! Let us know if you have subjects you’d be interested about in the comments! And please retweet the first post to help us spread the nerdiness!

https://twitter.com/alephium/status/1541711510178758658