2c:null 2d:["$","title",null,{"children":"Functional Blockchain - part 2 | Lance Galletti | Observable"}] 32:T524,md` If you have not yet read part 1, you can do so [here](https://beta.observablehq.com/@galletti94/functional-blockchain). In this article we will see yet another Blockchain use-case involving databases and database security. We will build a query language on the blockchain to create and query a database while utilizing the immutability of the blockchain to ensure 1. the possibile recovery of the database from the blockchain 2. the incorruptibility of data in the database The query language we create here is deliberately simple. I want to be as general here as possible so as to avoid limiting the breadth of applications of our database. By simply extending the query language, the reader will be able to construct more interesting and domain specific queries. Our language will allow the following: * CREATE a table with attributes * INSERT records into a table * SELECT records from a table My hope is to encourage the extension of the language and the testing of this blockchain database to evaluate the compatibility with the needs of an application. Speaking of, "blockchain database" seems like I just concatenated two buzzwords so before we dive into the nitty gritty details of the implementation, let's discuss the kind of database we will be implement along with its pros and cons. `33:Tbb7,md` Suppose we have a private blockchain owned by company C.inc. In this setting, we find two types of users/ entities. User A, who has constructed a local copy of the database (by executing all queries on the blockchain), user B who has not. Both user A and B have a copy of the blockchain and wish to execute queries. Just like in the smart contract setting, user A and user B will send the code to be executed during mining accross the network. Sending user A's code will be the side-effect of executing it locally so that no lag is encountered. In this way, user A can have, locally, a fully functioning database system that serves requests from an application in the typical server-client model, while backing up queries on the blockchain. User B can reconstruct the database from the blockchain and, were user A's database to crash for some reason, user B could take over with only perhaps a small lag to resolve the last submitted queries. Interesting parameters, such as block size and mining time, can be tuned to optimize for the semantics of the application. For example, holding mining time fixed, a small block size combined with a high query rate may result in a drastic lag between the database user A has, and the one user B is constructing. But a larger block size with a slow query rate may mean a longer time to resolve the last blocks when user B takes over. Similarly to smart contracts, each query will have a cost - also called gas - associated with it. We want to include the scenario where C.inc decides to make their blockchain (or a version of their blockchain) public and a user C wishes to gain access to C.inc's data. In this way, user C can help C.inc by mining blocks in exchange for data (by the intermediary of some currency). I hope the reader will appreciate the breadth of applications this blockchain has. To sum up, each block, here, in addition to the smart contracts and transactions, will contain the queries executed by the miners and their returned records, if any. Arguably, we can seperate the pros and cons of our database as follows: **Pros** 1. Data cannot be corrupted (immutability) 2. In a decentrilized setting, anyone can rebuild the database from the blockchain 3. Concurrency and other database access issues can be abstracted away (taken care of) by the blockchain 4. Decentrilized, trust-free data sharing 5. Can do provenence validation for asset management (more about this below) **Cons** 1. Proof of work means all queries have overhead if the user does not have a copy of the database 2. The blockchain can become too large to download by certain users I plan to focus on cons 2. in part 3 - depending on the intended queries we may need only download a subset of the blockchain that contains relevent tables etc. For now, we can say for sure that the main disadvantage of this database is potentially significant overhead on queries. This may be terrible for certain applications and irrelevent for others as discussed. `34:T6a9,md` **Integers** ${html`1 is represented as (Qint 1), 2 as (Qint 2) ...etc.`} **String** ${html`"hello, world!" is defined as (Qstr hello, world!)`} **Records** ${html`a tuple (t0, t1, t2) for example is defined as (Qrec t0 t1 t2)`} **Condition** 1 > 0 is encoded as ${html`(Qopr > (Qint 1) (Qint 0))`} **Create** A create statement, for example to construct a table "mytable" with attributes "col1" and "col2", can be encoded as ${html`(Qcrt mytable (Qrec (Qstr col1) (Qstr col2))) `} **Insert** Inserting into the above table can be done as such: ${html`(Qins mytable (Qrec (Qstr col1) (Qstr col2)) (Qrec (Qstr hello) (Qstr world!))) `} **Select** Selecting from the above table can be done as such: ${html`(Qsel mytable (Qrec (Qstr col1) (Qstr col2))) `} For convenience we implemented a lisp2sql function that will turn our queries into SQL-like syntax and will display those when viewing the blockchain. `35:T435,md` What are other ways this database can be used in practice? We have the seen the possibility of a backup or log. In this case, recall that all queries made are recorded on the blockchain and distributed for others to view and replicate but are executed locally for increased performance. As such, should the local system crash, other replicas of the database can be constructed, or other nodes that have been replicating the database can take over as the main database. As such the interaction with the database would still be centralized but its backup would follow the decentralized, trust-free model of the blockchain. Another possible use is for supply chain, or asset management, to provide, for example, transparency about provenance of goods for customers. To achieve this, we simply extend the query language to include transactional constructors such as: * CREATE object * COMBINE objects * SPLIT object * CONSUME object Please see the following [repository](https://github.com/mbestavros/SupplyChain) for more information and an actual implementation in Go. `36:[] 30:{"id":"81357b6d4eb2fded","slug":"functional-blockchain-part-2","title":"Functional Blockchain - part 2","thumbnail":"2cc74d41405b44fb7f246644d9c3a9d9058d5bb235104eb0381ebe29d4b43f11","access_level":"public","create_time":"$D2018-05-03T20:07:37.934Z","update_time":"$D2018-06-03T13:58:10.573Z","view_time":null,"first_public_time":"$D2018-05-03T23:24:16.881Z","has_unpublished_edits":null,"fork":false,"stars":5,"starred":false,"owner":{"type":"team","id":"791792a5343379f7","login":"galletti94","name":"Lance Galletti","avatar_url":"https://avatars-next.observableusercontent.com/e2e4b1ce10cf5bb72cfe2694371c020ca4d5f76e844e1f20aa2585ecd4fcc75d","tier":"starter_2024","bio":"Passionate about AI safety and Typed Functional Programming."},"version":77,"publish_version":77,"role":null,"authored":false,"authors":[{"type":"individual","id":"2c1e218ff962bf94","login":"galletti94","name":"Lance Galletti","avatar_url":"https://avatars-next.observableusercontent.com/e2e4b1ce10cf5bb72cfe2694371c020ca4d5f76e844e1f20aa2585ecd4fcc75d","tier":null,"bio":"Passionate about AI safety and Typed Functional Programming."}],"members":[{"type":"individual","id":"2c1e218ff962bf94","login":"galletti94","name":"Lance Galletti","avatar_url":"https://avatars-next.observableusercontent.com/e2e4b1ce10cf5bb72cfe2694371c020ca4d5f76e844e1f20aa2585ecd4fcc75d","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Functional Blockchain - part 2","cells":[{"id":0,"value":"md`# Functional Blockchain - part 2`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"md`## Introduction`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"md`## Blockchain DB`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"md`## Query Language`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"md`\nSimilarly to our lambda language, we define the operators of our query language as such\n\n${html ``}\n\nNotice that Qrec will be used to represent both a tuple and a collection of tuples in order to facilitate parsing of Qins. I hope notation is intuitive enough to understand which constructors refer to which query statement. As with our lambda language we will use a lisp-like syntax to facilitate parsing:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"md`## Interpreter`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":49,"value":"md`\nBelow is the skeleton of our interpreter. I will leave it up to the reader's interest to look at the full implementation, or imagination to implement the helper functions.\n\n${html ``}\n\nI will omit the parser here as it is very similar to the parser for our lambda language.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":52,"value":"md`## What it looks like`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":57,"value":"md`![](https://raw.githubusercontent.com/galletti94/ATS-blockchain/master/gif/tty.gif)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":64,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"md` ## Closing Note`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":69,"value":"md`\nIf you liked this article and would like to buy me coffee, feel free to donate \n**BTC** at 3QRRJu7ZHpegrBUMPmJw4pvcexH7qjvdyn \nor \n**ETH** at 0x13792d38f5E89bc0dE64Ccb9005A86B3574CB3f5 \n\nThanks and stay tuned for part 3!`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1"}} 31:"$30:body"