Seed - Development Design - Transaction Squashing
Overview
The following design article is based upon two previously written discussion articles. These previous articles are Transaction Squashing Proposition and Transaction Squashing Considerations For Jitter.
Transaction squashing is the simple concept of merging sequential changes into one single change. We are trying to prove this concept in order to keep the size of our DAG and Blockchain lean. As a high throughput, low latency blockchain product, a major fear is the sheer size of our system growing at an unsustainable rate. Transaction squashing is our attempt at keeping the growth size sustainable.
The hope is that we can make our blockchains size grow at a much slower rate. We want it to grow logarithmically, rather than linearly.
Transaction Squashing
Transaction squashing is the simple concept of merging sequential changes into one single change. In Github, a technology created to allow for open source code contributions, they use a directed acyclic graph (DAG) to manage their user code changes commits, and have proven the ability to squash multiple sequential commits into one merged commit, while still being done from a DAG. Without going into the specifics, transaction squashing would be very different under the hood in its implementation, however the general idea is the same.
In our implementation, a validated transaction which meets certain criteria will trigger a squashing mechanism to activate. This will take a group of validated transactions and deterministically squash them into a condensed block.
Who Get's Squashed
When a lucky transaction triggers the squashing mechanism, it and all upwardly connected transactions in the DAG will be squashed. That is, if isolate the transaction triggering the squashing, and only look upwardly at the transactions it validated or helped validate, we get a tree of nodes to be squashed.
Below is a diagram to explain this relationship.
In the diagram, the blue node represents a newly validated transaction that is triggering the squashing mechanism. The green nodes represents the other transactions that are being squashed. They were validated by the blue node and, by the blue node being valid, they are already considered valid.
The green nodes would continue upwards until they either hit the first node of the entire DAG, or until they hit a block hash. All green transactions will become squashed.
The orange nodes represents transactions which would not be squashed in the mechanism. These may be valid and may validate transactions which are being squashed, however they are not themselves squashed.
What Happens To Entanglement
All squashed transactions are removed from the DAG once the block is fully formed. They will be stripped from the entanglement, with the lucky transaction which started the process being replaced with the hash of the newly created block.
When To Squash
The squashing mechanism is triggered when a transaction become valid, where that transactions hash started with a certain amount of leading zero's.
How Does Squashing Work
When a transaction triggers the squashing mechanism, it and all validated parents (and grandparents, great grandparents, etc.) are pulled from the Entanglement, and an empty Block is created. The transactions' "sender" and "signature" properties are stripped from the transactions, stored in a mapping of { address => signature } inside the block. When a user verifies a signature with their sender, it results in a transaction hash as output, so storing these two pieces of data also stores the third.
Next, all changes effected to the world are squashed. If user "A" send user "B" 10 SEED over ten separate transactions, these ten changes are squashed into one change, which is that "A" sent "B" 100 SEED.
The validation information and execution are both removed from each transaction. These validation portions were needed for execution and validating other transactions, however those other transactions are already stored in this block as well, and already considered valid. We store what is needed to recreate history, not what is needed to re-validate history.
Once the block is finished being created, it is considered a "first generation block" and added to the Blockchain. The selected transactions are removed from the Entanglement, with the one who triggered the mechanism being replaced by the newly created block's hash.
Block
A "Block" in Seed is not the same as a traditional Block. In regular blockchain systems, blocks are fully verifiable, as they are a key component of the validation system. In Seed, transactions are already valid once they enter a block. In traditional blockchain systems, a miner creates the block, finding a nonce and doing a computationally heavy problem solving activity known as "mining". In Seed, blocks are fully deterministic in their creation, with miners being excluded from the picture.
Therefore, in Seed, a block is simply an organized way to store historical data, and is not really a part of the validation process.
In order to highlight these differences, a "Block" in Seed is referred to as a "Testament Block", in order to represent that it is a condensed change of state.
What Is Stored In A Testament Block
Each block stores the sender of each transaction which makes up the block, as well as that transactions signature. It also stores a squashed version of all these transactions changes.
For example, lets say we had three transactions. Two where user "ABC" sent user "DEF" 10 SEED, and a third where DEF sent ABC 10 SEED. A simplified view of the block created of the three transactions may look like the following:
{
transactions : {
"ABC" : "Signature1",
"DEF" : "Signature2",
"ABC" : "Signature3"
},
changeSet : {
"Seed" : {
"ABC" : {
"balance" : "-20"
},
"DEF" : {
"balance" : "+20"
}
}
}
}
Blockchain
How Our Blockchain Is Different
In traditional blockchains, a "blockchain" is simply a cryptographically secured variation of a data structure known as a linked list. Each block is a node on this list, who knows only of the node before it. In Seed, blocks do not know of the blocks which come before it, and are stored in multiple lists rather than one.
Multiple Chains Of Generations
In Seed, the structure is quite different. Rather than having one list, there is a list for each generation of block. When transactions get squashed into a block, that is known as a "first generation testament block" and stored in a list with other first generation testament blocks.
Once a block is created, who's hash has a certain about of leading zero's, it will trigger the same squashing mechanism as transactions go through. A list of first-generation testament blocks are condenced into a second generation testament block.
How Ledger Is Built From Both
When rebuilding the ledger, users will apply the oldest testament blocks to the ledger. For example, they may apply all 2nd generation blocks to the ledger. Afterwards, they will apply all first generation blocks. After that, they will apply all validated transactions in the active DAG. Once these have all been applied, the ledger has successfully been rebuilt.
Squasher
The "Squasher" will the object which wraps the logic regarding the "squashing mechanism" mentioned above. The file which contains the Squasher will have two exports, one for squashing Transactions into a block, and another for squashing Blocks into a more condensed block.
Export for Transaction Squashing
The transaction squashing export will take in a group of Transactions and squash them. The "sender" and "signature" variables of each transaction will be added to a mapping called "transactions" inside the block. All of the transaction ChangeSet's (the object inside a transaction which describes how it affected the world) will be condensed into one, with similar changes being added together.
Export for Block Squashing
The block squashing export will take in a group of Blocks and squash them. Their "transactions" will be squashed together, becoming a much larger mapping. Each block's ChangeSet will also be squashed together, similarly to how the Transactions had their ChangeSet's squashed.
Squashing
The act of squashing is taking multiple ChangeSet's and condensing them. For example, the following two ChangeSets:
{
"Seed" : {
"ABC" : {
"balance" : "+10"
},
"DEF" : {
"balance" : "-10"
}
}
}
and
{
"Seed" : {
"ABC" : {
"balance" : "+10"
},
"GHI" : {
"balance" : "-10"
}
}
}
Will look like the following after squashing
{
"Seed" : {
"ABC" : {
"balance" : "+20"
},
"DEF" : {
"balance" : "-10"
},
"GHI" : {
"balance" : "-10"
}
}
}
Conclusion
Transaction squashing is a requirement of the Seed project needed to keep the size of the DAG as small as possible. This will be the next portion of the project to be focused on.
In short, a Squasher export will be created to handle condensing Transactions and Blocks. A "Block" will be created to represent a grouping of squashed transactions, with a "Blockchain" equivalent being created to hold the linked blocks together.