Repository
https://github.com/Cajarty/Seed
Overview
The following development changes were based upon the design article Transactions And Entanglement. This pull request includes the implementation of Transactions, the Entanglement (the DAG of Seed), transaction validation, a messaging system to notify DApp UIs on function calls/changes to state data, as well as updating the scenario tests & virtual machine to account for these changes.
Transactions
A transaction is a cryptographically signed message regarding how the sender intends on changing the ledger. Because it is cryptographically signed, it allows us to prove the intent of the sender, and confirm their consent to any changes this message causes. In Seed, a transaction represents code execution, and therefore must describe exactly which code to execute. These messages and their executable code must be fully deterministic.
Execution
Each transaction include data regarding what code execution this transaction represents. This execution has a few requirements, namely representing code, and can be both validated and proved by others.
For other users to be able to validate code execution, the execution structure must contain certain pieces of data. It includes the module and function name that are being executed on, as well as the checksums of the code for a given module and function. As explained more thoroughly in this article previous written about provable execution, we can prove that users are executing the same code by comparing the checksum hashes.
The execution structure must also contain the arguments, which act as inputs into the function, and the change set, which is the output of executing these functions.
Validation Rules
A transaction is only valid if it follows the following rules. All Seed implementations must follow these agreed upon rules.
| Rule | Description |
|---|---|
| #1 | Validate that the hash of all the transaction data creates the same hash as the claimed transaction hash |
| #2 | The transaction sender must be a valid public key format and be derived from a valid private key |
| #3 | The transaction's cryptographic signature must be verifiable by the transaction sender, proving consent |
| #4 | The transactions which are validated by the incoming transaction must be verified by other users |
| #5 | This new transaction and its validate transactions cannot create a cycle in the DAG when added |
| #6 | Prove that we agree on the module code being executed, so we're using the same versions |
| #7 | Prove that we agree on the function code being executed, so we're using the same versions |
| #8 | Prove that, when we simulate the execution, we get the same ChangeSet, and therefore agree on how it changed the ledger |
| #9 | The validation work done must match the transactions they attempt to validate |
| #10* | Prove that, when we simulate the execution of their validated transactions, their execution was also right (Prove their "work" was right). |
| #11 | Prove that a user does not validate them-self |
*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.
Implementation
transaction.js
The entire implementation, including the transaction class, transaction validator class, helper functions and exports can all be found in transaction.js
class Transaction
The Transaction class wraps the Transaction structure. It adds helper methods regarding stringifying the structure and determining hashes. It is primarily a structure of data representing a transaction with minimal logic.
Transaction Schema:
Transaction Hash
Sender Address
Execution:
ModuleName
FunctionName
Arguments
ModuleChecksum
FunctionChecksum
ChangeSet
Trusted Transactions:
Transaction Hash
Module Checksum
Function Checksum
ChangeSet
Signature
class TransactionValidator
The TransactionValidator class contains methods regarding the implementation of all 11 rules. It is used when validating transactions.
Helper Functions
There are two helper functions used by Transaction, TransactionValidator and the exports. These are the functions isProper and isValid.
isProper proves that a transaction is well-formed and proper, meeting all rules except for Rule #11.
isValid proves that a transaction meets all rules
Exports
The functions accessible through the exports are as follows
createNewTransaction(sender, execution, trustedTransactions )
- Creates a new transaction object
createExistingTransaction(sender, execution, trustedTransactions, transactionHash, transactionSignature )
- Creates a new transaction object based on an existing transactions data
isTransactionValid(transaction)
- Determines if the transaction is considered valid or not
isTransactionProper(transaction)
- Determines if the transaction is "Proper", meaning well-formed with its validated transactions being proper as well
notifyTransactionValidation(transactionHash)
- Notifies all Proper transactions awaiting Validation that transactionHash is now valid, therefore retest if we were dependant on it
waitToBeNotified(transaction)
- A Proper transaction starts awaiting for its dependant transactions to be validated. Will be retested upon "notifyTransactionValidation" being invoked
createTransactionValidator()
- Creates a new transaction validator
Entanglement
The entanglement is the directed acyclic graph (DAG) data structure used by Seed as an alternative to a traditional blockchain for transaction storing. This structure allows transactions to be stored out of order, joining the graph asynchronously, and giving us a unique validation mechanism for determining how must trust we have in a given transaction.
Trust
The act of validating a transaction is traditionally done by the validation mechanism of any system. In Bitcoin and other blockchain systems, this mechanism is referred to as Proof-of-Work. Seed's validation is done through trust earned by having transactions validate each other. The more trusted a transaction is, the more transactions it validated are considered trusted. After a certain threshold of accumulated trust from validating parents, a transaction itself eventually becomes trusted.
Implementation
entanglement.js
The entire implementation, including the entanglement class, helper functions and exports can all be found in entanglement.js
class Entanglement
The entanglement class is a directed acyclic graph (DAG) data structure, used to store transactions. The class is mostly used for data storage, however contains helper methods for accessing the data, and methods for adding to the data structure in a logical manner.
Helper Functions
There are two helper methods used by the Entanglement class and the exported methods. These functions are a tryTrust function used for applying a transactions ChangeSet to a ledger upon being trusted, as well as a visit function used when traversing the DAG.
Exports
The functions accessible through the exports are as follows
getEntanglement()
- Returns the current Entanglement, creating one if none exists
tryAddTransaction(transaction)
- Adds the incoming transaction to the entanglement
doesTransactionCauseCycle(transaction)
- Checks if adding this transaction would cause a cycle to occur, as DAG's are acyclic by nature
getTipsToValidate(sender, numberOfTips)
- Returns a list of transaction hashes for transactions that need to be validated. These are transactions with zero or few validations
hasTransaction(transactionHash)
- Returns whether or not the given transaction exists in the entanglement yet
isValid(transactionHash)
- Returns whether or not the given transaction is considered valid or not
Messaging
A large DApp requirement is being able to have user interfaces react to live changes in the \entanglement. This is the goal of the Messaging system. The messaging system is a subscription based model which allows code execution to plug in for certain events, namely function executions or specific data changes.
Implementation
messaging.js
The entire implementation for messaging is found in messaging.js, including the message structure and exports.
class Message
The Message class is a simple structure representing a message, which will be given to subscribed callbacks as the input. The message includes the name of the module which was just effected, the function which was invoked, the hash of the transaction, and a ChangeSet structure depicting how this transaction affected the ledger.
Exports
The functions accessible through the exports are as follows
subscribeToFunctionCallback(moduleName, functionName, callback)
subscribeToDataChange(moduleName, key, user?, callback)
unsubscribe(moduleName, funcNameOrDataKey, receipt, optionalUser?)
invoke(moduleName, functionName, transactionHash, changeSet)
Honourable Mentions
The following are meaningful changes that also occurred in this pull request, which may not deserve their own section.
Feature - ModuleTester Update
The ModuleTester class, used for unit testing and scenario testing modules, has been updated in order to properly test modules now that transactions go through the Entanglement. Specifically, the ability to create "relay" transaction was added, used to push validation forward by simulating external transactions which validate the important transactions being tested upon.
Bug - Pushed Dependencies Now Ignored
The .gitignore now ignores all NodeJS dependencies, and previously pushed dependencies have now been removed from the Seed repository.
Bug - Unused npm Package Now Removed
The broken npm package found in this repositories root directory has been removed. The only packages should be found in the /seedSrc folder and the /clientSrc folder's respectively.
GitHub
https://github.com/CarsonRoscoe