Overview

There are two crypto based sections to the Seed system. The DAG and the Blockchain. The DAG is what Seed relies on for validation and short-term malleable storage, while the blockchain portion is used for long term storage.

Once transactions in the DAG become fully validated and certain conditions are met, they will become condensed into blocks in a fully deterministic fashion.

This design document will be focused on transactions and the entanglement of transactions into the Seed DAG.

---

Seed Entanglement vs IOTA Tangle

The concept of entanglement is not a new one. IOTA was the first popular crypto to utilize entanglement and DAGs.

The Tangle allows for IOTA to be very lean, allows IOTA to require only knowing a portion of the complete DAG to send transactions, and allows for true offline transactions.

Differences

Proof-of-Work vs Proof-of-Execution

The Tangle uses Proof-of-works and a complicated validation system to prove transactions are valid. The simplified explanation is that every transaction does "work" to prove itself, and the amount of work done can be as much or little as a user wants. Transactions then nominate two other transactions that they consider valid. Children transactions inherit their family tree's work. Therefore, by having your transaction be validated by other users, your transaction inherits the "work" of the others. Once a transaction has enough parents, or the parents are trusted enough, the transaction becomes "validated".

Similar to the idea of "work" in Proof-of-Work, the concept of "work" is required for Seed transactions. However, instead of "work" being the act of finding a nonce, our "work" is simulating the execution of a transaction and verifying that the outputs given match what should be stored on the ledger.

Essentially, instead of solving a puzzle as proof, we execute the same code and validate the same output as proof.

The goal of Proof-of-Work in DAGs is to prove users have the right to make changes. This is a type of built-in spam repellent. Proof-of-Execution works similarly, where "spamming" the network requires validating other transactions. If a user attempted to maliciously spam the network, they would be pushing the network forward in doing so and using plenty of processing power in the process.

For "work" to function in concept, the work being done must be hard (but feasible) to do, while being easy to check. The type of execution Seed requires does not fit this definition perfectly, hence why it is not simply being called
"Proof-of-Work". A functions execution may be complicated, or it may be simple, making the amount of processing required unknown until execution. There is no easy way to check without trusting other 3rd party users. For
a user to validate another user's work, they must also invoke the execution themselves. So users re-execute code the transactions they are validating did in order to confirm they executed it properly to get the right result.

To summarize, instead of the spam repellent being a hard problem which is easy to validate, it's a easy-to-hard problem that the validator puts equal effort into solving as well.

Offline vs Online Transactions

IOTA's Tangle has a large positive over other cryptocurrencies, in that it allows for offline transactions.

In blockchains, transactions are appended into new blocks, so a user must be online to learn about the newest block. Users must be online to submit transactions, despite not needing to be online to view known history. Therefore, users who are connected to the network must stay connected in order to send transactions.

Pure DAG implementations like IOTA are different in this regard. Transactions can be appended anywhere in the DAG, not some arbitrary "end" point. The entire DAG is present at all times, never pruned. We always have all transactions. As long as other users have the transactions your transaction references in their DAG, we can guarantee that all children are the same, and thus we are looking at the same "history" relative to the given transactions. Essentially, a user can know of only a small part of history, create a transaction, and at a later date, broadcast it to the network. This transaction was offline upon creation, but can still be validated once the network discovers it.

Seed is different from other DAG implementations in this regard. Seed is a hybrid approach crypto, utilizing both DAGs and blockchains. Seed inherits the "online only" flaw from its blockchain portion, since transactions are eventually squashed into the blockchain. Once a transaction is discarded, it cannot be used as a validation point for incoming transactions. In short, the Seed DAG is pruned very often, making old knowledge of the DAG state outdated rather quickly. Users must be online in order to know which transactions are currently available in the DAG.

Coordinator vs Relay Nodes

The Tangle is arguably not truly decentralized due to being dependent on the coordinator, a master node of sorts.

The Coordinator is required due to DAGs needing new transactions to always be published in order to validate transactions that are becoming stagnant.

In Seed, there is no central master node. Instead, open source relay nodes are publicly available for users to use. These relay nodes can be hosted by anyone, help users broadcast their transactions to the world, and can periodically send out empty transactions that simply validate existing tips.

Once large benefit of relay nodes will be the routing functionality they will offer. Relay nodes will know how to not only communicate with each other, but they will also be able to be personalized for module developers, allowing module developers to route their users together in more efficient ways. For example, suppose there is a low latency video game created in Seed. The module developer could run their own relay node which chooses to validate all users of their games, guaranteeing the transactions never stagnate when waiting to be validated. On top of that, the relay node could pair users together based on in-game x/y coordinates, making users who are near each other directly send transactions to one-another, in order to keep the latency as low as possible.

The primary goal of the coordinator is to keep IOTA moving, refusing to allow transactions to become stagnant. We believe our relay nodes will achieve the same goal, however by doing so in a decentralized way which benefits the network.

---

Transactions

Transactions are a statement given by a user declaring what changes they made to the Seed ledger. Cryptographic signatures are used to confirm consent and prove that the real sender is the one signing a given transaction.

A transaction's structure looks like the following:

Transaction:
    Transaction Hash (SHA256(Sender + Execution + Validated Transactions))
    Sender Public Address
    Execution:
        Module Name
        Function Name
        Arguments
        Module Code Checksum
        Function Code Checksum
        ChangeSet
    Validated Transactions Array:
        Transaction Hash
        Module Checksum, Function Checksum, ChangeSet
    Signature:
        Signature consents that Sender agrees to Transaction Hash's integrity

Execution

The execution of module code that this transaction represents, including which function is executed on which module, passing what arguments, and stating what the sender believes happened to the ledger.

---

Validation Rules

A transaction is only valid if it follows the following rules. All Seed implementations must follow these agreed upon rules.

A transaction which meets all rules except for Rule #10 is deemed "Proper" and given a small degree of trust. As the children it validated become valid, it is given a confidence coefficient on a scale of 0 to 1 regarding how validated the children are. Once a Proper transaction has all its children validated, it becomes "Valid" as well with a full confidence coefficient

Rule #1: Prove the Transaction.Sender, Transaction.Execution and Transaction.ValidatedTransactions are the content that creates the Transaction.TransactionHash

Verify the SHA256 hash of (Transaction.Sender + Transaction.Execution + Transaction.ValidatedTransactions) equals Transaction.TransactionHash

Rule #2: Prove that the Transaction.Sender is a valid public key, and therefore was derived from a valid private key

As Seed uses elliptic cryptography based on the secp256k1 curve, verify that Transaction.Sender is a vapid key that can be derived from the curve.

Rule #3: Prove that the Transaction.Sender is the public key consenting to the transaction

Verify that the cryptographic signature found in Transaction.Signature can be verified by the Transaction.Sender key

Rule #4: Prove that the validated transactions are in our DAG

Verify the Transaction.ValidatedTransactions only contains transaction hashes that are found in our DAG

Rule #5: Prove that this transaction does not cause a cycle

As the "A" in DAG stands for "acyclic", there cannot be cycles. Verify that this DAG can be added to the graph without a cycle appearing.

Rule #6: Prove that we agree on the module code being executed

Verify that the Transaction.Execution.ModuleName and Transaction.Execution.ModuleChecksum matches the version of the module our client is using.

Rule #7: Prove that we agree on the function code being executed

Verify that the Transaction.Execution.FunctionName and Transaction.Execution.FunctionChecksum matches the version of the function we're using

Rule #8: Prove that we get the same changes when executing the transactions code

Using the Seed Virtual Machine, simulate the transaction and then compare the results. We must have the same results to confirm they are being honest about how they modified the ledger.

Rule #9: Prove that the transactions validated work matches what they validated

Verify that the claimed changes found in Transaction.ValidatedTransactions matches what those transactions originally claimed to the DAG.

Rule #10: Prove that their validated transactions were honest

A transaction cannot be validated until all of its children become validated.

NOTE: We can't simply execute these on our SVM, as they happened in the past, our ledger may have changed, and there is no "clock" we can effectively used to rollback and rebuild the ledger into a matching state.
Instead, we need other transactions to validate this transaction. That makes rule #10 one that cannot be fully trusted until these transactions are fully validated by other DAG users.
IF the rest of this transaction was valid, we act as if this transaction is valid when determining if those transactions were valid. Essentially, we assume this is honest, and wait for others to become honest.

---

The Entanglement

Adding Transactions

The first transaction added into the entanglement is the Genesis Transaction, which has no validated transaction array data.

When a transaction is to be added to the DAG, it is first checked against the validation rules. If it is deemed a Proper transaction, it is added to the DAG.

When a transaction is deemed valid, its parents are re-checked to update whether they are still "Proper" or now "Valid" as well.

Transactions do not modify the ledger until they are considered valid. Proper transactions can therefore conflict, where they are only Proper assuming the other transaction does not get validated.

Managing Conflicts

When validating conflicting transactions, the transaction with the lower hash is selected. This is not enforcable and therefore simply a courtesy rule, however if a transaction selects the wrong one to validate,
then their transaction will never get validated.

Double-Spend Attack

A double spend attack in the cryptocurrency world is when a users manages to spend the same money twice. If Bob has $10 and sends $10 to Bill and $10 to Jane, he has attempted to spend the money twice. If both of Bob's transactions get validated, he has successfully invoked a double-spend attack.

In Bitcoin and traditional blockchains, a double spend can only be executed when controlling 51% of the network hashrate. It is extremely expensive to modify the history of a Proof-of-Work blockchain implementation.

In IOTA, a double spend has two requirements. First, they must have a majority hashpower, which is must easier to obtain. The second requirement is that your transaction must have enough neighbours to get the transaction confirmed. This second requirement is a concept known as omnipresence, where nodes must be neighbours with the majority of the network in order to have a transaction become confirmed. It is very difficult to do a double spending attack on IOTA as the network topology is nearly impossible to know.

A double spend attack can, effectively, only be done in IOTA by creating a "parasite" chain, building enough work on this parasite chain that it rivals the main chain, and then merging the parasite chain into the main chain while being in control of the coordinator.

In Seed, pure Proof-of-Work has been abandoned. Instead, users explain the execution they did and the causal results it had on the network. This removes the first tangle requirement regarding acquiring a majority hashpower, making it slightly easier to execute a double spend. Seed also does not have the coordinator, and Seed nodes also do not require mutual tethering (though a similar concept is in place). This means double spends are possible unless a separate mechanism is added.

Avoiding Parasite Chains

The core problem which results in double-spends is parasite chains. A parasite chain occurs when transactions validate each other while never re-syncing up to the main chain. A new entanglement forms with its own variation of history, which may not be compliant with transactions on the main chain.

Once a parasite chain is large enough, the older transactions are intrinsically confirmed, despite potentially conflicting with transactions on the main chain. Once the parasite chain decides to merge back with the main chain, they simply need their tips and recent transactions to be honest. These honest transactions are validated against the main chain, found proper, and merged in. The ledger now contains the history of both chains, despite the conflicts.

Protocol Defence

Seed naturally has an extra defence against parasite chains becoming too large due to the block formation mechanism. In Seed, the main chain will deterministically squash groupings of validated transactions into blocks. Once a transaction invokes the block creation process, it and all its validated children get squashed.

If a parasite chain has a transaction occur which triggers the block creation mechanism, the block of changes from the parasite chain cannot be merged with the main chain. Only DAG transactions can be merged, not blocks. The parasite chain now has transactions being created which can never be merged with the main chain, poisoning the parasite chain and killing it. This forces the parasite chains to synchronize with the main chain in a short amount of time, preventing it from ever getting too large.

Implementation Defence

Through the use of relay nodes handling transaction routing, no transactions can cause a parasite chain. Although relay nodes do not directly participate in the validation process, they act as a filter for spam and malicious transactions. If a parasite chain transaction is sent to a honest relay node, the relay node will refuse to relay it. This enforces on an implementation basis that only honest transactions are propagated to the main chain.

Because the majority of users will either be communicating through relay nodes or directly to users who are communicating with relay nodes, the only transactions that will arrive on the main chain, and therefore the only transactions which will be on the chain when the block creation mechanism is triggered, are ones that go through a relay node at some point.

---