Things I Wish I Knew Before Building a Ledger

Sequence was open-sourced.

We created ledgers 7000 years ago. Double-entry accounting 500 years ago. But we failed to replicate them in software. When you write something in stone, you can’t update it. But most software ledgers are using database updates to record value movements.

Public ledgers (blockchains) are good software ledgers. They are immutable. Distributed in storage. Cryptographically verifiable. But their goal is to distribute trust. And this brings big trade-offs. Getting rid of the need for trust distribution results in a strong private ledger.

Why database updates are evil

Immutability and traceability. Immutable means you don’t change things after they got written. Traceable means you link things such that you know how they ended up in their current state. Simple in concept. Hard in practice. When you represent money, new values depend on the previous. You can’t spend 10 dollars if you only have 5 in your balance.

Using these concepts is critical, but not enough. Another pitfall of existing ledgers is the database engine. Most of them use relational databases. These engines do too much work, making them less scalable. They are not distributed, making them less reliable. No-SQL databases solve most of these problems.

So we will use accounting, cryptography, and No-SQL databases. It should be fun.

How to avoid updates

A Hash Chain is a data structure that links data using a hash function. We use it to link the asset movements:

  1. Get the unique id of the last transaction with a hash function.
  2. Use the result as the id for the next transaction.

With the lastest transaction storing the balances. Our Hash Chain can trace all movements and check integrity. For this, we compute hashes for all transactions. When the id of a transaction is not the hash of the previous, integrity is broken. But it is expensive. Merkle Trees are more efficient at checking integrity. We group the individual transactions ids into sub-hashes. Then we check groups of transactions with a single string of data.

No-SQL is consistent

Say you have 10 dollars in your balance. And you make 100 concurrent requests to transfer it. Only one should work. Remember the relational database? It will try doing this for you. But with the efficiency of a combustion engine. Limited to the power of a single machine.

Anything touching money should go into the relational database for consistency.

— Someone that doesn’t understand No-SQL.

No-SQL databases rely on a lighter mechanism. Leaving the work to the application layer. This is good because we can spin up 1 million instances of our application. And 1 million nodes of our No-SQL database.

We use our Hash Chain ids to make conditional puts. Most No-SQL databases support them. This makes our balances consistent. And the ledger extremely scalable.

Availability and scale

Decimals reached 100 thousand transactions per second on a simple test, completely autoscaled. Deployed on Kubernetes, using DynamoDB. The limiting factor for scalability is transactions on the same balance. Using 20 milliseconds for disk writing and network latency, we can make 50 transactions per second on the same balance.

Considering that we make 5 transactions a day. Decimals is ready to process transactions for the 8 billion people on earth. And even support new use cases. Like a real-time car insurance app making one transaction every 100 milliseconds. Consistently.

Perform computations asynchronously

We need the last transaction hash to insert a new one into our Hash Chain. But not the Merkle Tree root hash. So we don’t compute it. Decimals is not decentralizing trust. It is making it easier to check data. So we compute the Merkle Tree asynchronously. Enabling real-time applications and keeping efficient integrity checks.

For comparison, AWS Quantum Ledger DB computes the whole Merkle Tree on every request. A simple insert takes seconds to complete. And there are big limitations to the size of the ledger.

Things to avoid on your ledger

If you get into the journey of writing your ledger. Here are the key things to avoid:

  1. Updating balance fields or database updates in general
  2. Avoiding No-SQL for consistency reasons
  3. Performing expensive computations synchronously
  4. Using relational databases when availability or scale are concerns

Thanks for reading. Subscribe to receive new articles about Decimals engineering.

We will write in-depth posts about each piece of Decimals. Let us know which one should be first.

References

No-SQL Design

Square Ledger

Uber Ledger

QLDB Data Verification