index.md (10191B)
1 --- 2 title: "Let’s Make a Hash Chain in SQLite" 3 date: 2021-06-30T00:00:00+00:00 4 draft: false 5 canonical_url: https://www.viget.com/articles/lets-make-a-hash-chain-in-sqlite/ 6 references: 7 - title: "How Blockchains Work | data Blog = Blog { me :: Programmer, posts :: [Opinion] }" 8 url: https://asthasr.github.io/posts/how-blockchains-work/ 9 date: 2024-03-07T04:43:24Z 10 file: asthasr-github-io-s0ebht.txt 11 --- 12 13 I'm not much of a cryptocurrency enthusiast, but there are some neat 14 ideas in these protocols that I wanted to explore further. Based on my 15 absolute layperson's understanding, the "crypto" in 16 "cryptocurrency" describes three things: 17 18 1. Some public key/private key stuff to grant access to funds at an 19 address; 20 2. For certain protocols (e.g. Bitcoin), the cryptographic 21 puzzles[^1] that miners 22 have to solve in order to add new blocks to the ledger; and 23 3. The use of hashed signatures to ensure data integrity. 24 25 Of those three uses, the first two (asymmetric cryptography and 26 proof-of-work) aren't that interesting to me, at least from a technical 27 perspective. The third concept, though --- using cryptography to make 28 data verifiable and tamper-resistant --- that's pretty cool, and 29 something I wanted to dig into. I decided to build a little 30 proof-of-concept using [SQLite](https://www.sqlite.org/index.html), a 31 "small, fast, self-contained, high-reliability, full-featured, SQL 32 database engine." 33 34 A couple notes before we dive in: these concepts aren't unique to the 35 blockchain; Wikipedia has good explanations of [cryptographic hash 36 functions](https://en.wikipedia.org/wiki/Cryptographic_hash_function), 37 [Merkle trees](https://en.wikipedia.org/wiki/Merkle_tree), and [hash 38 chains](https://en.wikipedia.org/wiki/Hash_chain) if any of this piques 39 your curiosity. This stuff is also [at the core of 40 git](https://initialcommit.com/blog/git-bitcoin-merkle-tree), which is 41 really pretty neat. 42 43 ## Onto the code 44 45 Implementing a rudimentary hash chain in SQL is pretty simple. Here's 46 my approach, which uses "bookmarks" as an arbitrary record type. 47 48 ```sql 49 PRAGMA foreign_keys = ON; 50 SELECT load_extension("./sha1"); 51 52 CREATE TABLE bookmarks ( 53 id INTEGER PRIMARY KEY, 54 signature TEXT NOT NULL UNIQUE 55 CHECK(signature = sha1(url || COALESCE(parent, ""))), 56 parent TEXT, 57 url TEXT NOT NULL UNIQUE, 58 FOREIGN KEY(parent) REFERENCES bookmarks(signature) 59 ); 60 61 CREATE UNIQUE INDEX parent_unique ON bookmarks ( 62 ifnull(parent, "") 63 ); 64 ``` 65 66 This code is available on 67 [GitHub](https://github.com/dce/sqlite-hash-chain) in case you want to 68 try this out on your own. Let's break it down a little bit. 69 70 - First, we enable foreign key constraints, which aren't on by 71 default 72 - Then we pull in SQLite's [`sha1` 73 function](https://www.i-programmer.info/news/84-database/10527-sqlite-317-adds-sha1-extension.html), 74 which implements a common hashing algorithm 75 - Then we define our table 76 - `id` isn't mandatory but makes it easier to grab the last entry 77 - `signature` is the SHA1 hash of the bookmark URL and parent 78 entry's signature; it uses a `CHECK` constraint to ensure this 79 is guaranteed to be true 80 - `parent` is the `signature` of the previous entry in the chain 81 (notice that it's allowed to be null) 82 - `url` is the data we want to ensure is immutable (though as 83 we'll see later, it's not truly immutable since we can still 84 do cascading updates) 85 - We set a foreign key constraint that `parent` refers to another 86 row's `signature` unless it's null 87 - Then we create a unique index on `parent` that covers the `NULL` 88 case, since our very first bookmark won't have a parent, but no 89 other row should be allowed to have a null parent, and no two rows 90 should be able to have the same parent 91 92 Next, let's insert some data: 93 94 ```sql 95 INSERT INTO bookmarks (url, signature) VALUES ("google", sha1("google")); 96 97 WITH parent AS (SELECT signature FROM bookmarks ORDER BY id DESC LIMIT 1) 98 INSERT INTO bookmarks (url, parent, signature) VALUES ( 99 "yahoo", (SELECT signature FROM parent), sha1("yahoo" || (SELECT signature FROM parent)) 100 ); 101 102 WITH parent AS (SELECT signature FROM bookmarks ORDER BY id DESC LIMIT 1) 103 INSERT INTO bookmarks (url, parent, signature) VALUES ( 104 "bing", (SELECT signature FROM parent), sha1("bing" || (SELECT signature FROM parent)) 105 ); 106 107 WITH parent AS (SELECT signature FROM bookmarks ORDER BY id DESC LIMIT 1) 108 INSERT INTO bookmarks (url, parent, signature) VALUES ( 109 "duckduckgo", (SELECT signature FROM parent), sha1("duckduckgo" || (SELECT signature FROM parent)) 110 ); 111 ``` 112 113 OK! Let's fire up `sqlite3` and then `.read` this file. Here's the 114 result: 115 116 ``` 117 sqlite> SELECT * FROM bookmarks; 118 +----+------------------------------------------+------------------------------------------+------------+ 119 | id | signature | parent | url | 120 +----+------------------------------------------+------------------------------------------+------------+ 121 | 1 | 759730a97e4373f3a0ee12805db065e3a4a649a5 | | google | 122 | 2 | 64633167b8e44cb833fbfa349731d8a68e942ebc | 759730a97e4373f3a0ee12805db065e3a4a649a5 | yahoo | 123 | 3 | ce3df1337879e85bc488d4cae129719cc46cad04 | 64633167b8e44cb833fbfa349731d8a68e942ebc | bing | 124 | 4 | 675570ac126d492e449ebaede091e2b7dad7d515 | ce3df1337879e85bc488d4cae129719cc46cad04 | duckduckgo | 125 +----+------------------------------------------+------------------------------------------+------------+ 126 ``` 127 128 This has some cool properties. I can't delete an entry in the chain: 129 130 ``` 131 sqlite> DELETE FROM bookmarks WHERE id = 3; 132 Error: FOREIGN KEY constraint failed 133 ``` 134 135 I can't change a URL: 136 137 ``` 138 sqlite> UPDATE bookmarks SET url = "altavista" WHERE id = 3; 139 Error: CHECK constraint failed: signature = sha1(url || parent) 140 ``` 141 142 I can't re-sign an entry: 143 144 ``` 145 sqlite> UPDATE bookmarks SET url = "altavista", signature = sha1("altavista" || parent) WHERE id = 3; 146 Error: FOREIGN KEY constraint failed 147 ``` 148 149 I **can**, however, update the last entry in the chain: 150 151 ``` 152 sqlite> UPDATE bookmarks SET url = "altavista", signature = sha1("altavista" || parent) WHERE id = 4; 153 sqlite> SELECT * FROM bookmarks; 154 +----+------------------------------------------+------------------------------------------+-----------+ 155 | id | signature | parent | url | 156 +----+------------------------------------------+------------------------------------------+-----------+ 157 | 1 | 759730a97e4373f3a0ee12805db065e3a4a649a5 | | google | 158 | 2 | 64633167b8e44cb833fbfa349731d8a68e942ebc | 759730a97e4373f3a0ee12805db065e3a4a649a5 | yahoo | 159 | 3 | ce3df1337879e85bc488d4cae129719cc46cad04 | 64633167b8e44cb833fbfa349731d8a68e942ebc | bing | 160 | 4 | b583a025b5a43727978c169fe99f5422039194ea | ce3df1337879e85bc488d4cae129719cc46cad04 | altavista | 161 +----+------------------------------------------+------------------------------------------+-----------+ 162 ``` 163 164 This is because a row isn't really "locked in" until it's pointed to 165 by another row. It's worth pointing out that an actual blockchain would 166 use a [consensus 167 mechanism](https://www.investopedia.com/terms/c/consensus-mechanism-cryptocurrency.asp) 168 to prevent any updates like this, but that's way beyond the scope of 169 what we're doing here. 170 171 ## Cascading updates 172 173 Given that we can change the last row, it's possible to update any row 174 in the ledger provided you 1) also re-sign all of its children and 2) do 175 it all in a single pass. Here's how you'd update row 2 to 176 "askjeeves" with a [`RECURSIVE` 177 query](https://www.sqlite.org/lang_with.html#recursive_common_table_expressions) 178 (and sorry I know this is a little hairy): 179 180 ```sql 181 WITH RECURSIVE 182 t1(url, parent, old_signature, signature) AS ( 183 SELECT "askjeeves", parent, signature, sha1("askjeeves" || COALESCE(parent, "")) 184 FROM bookmarks WHERE id = 2 185 UNION 186 SELECT t2.url, t1.signature, t2.signature, sha1(t2.url || t1.signature) 187 FROM bookmarks AS t2, t1 WHERE t2.parent = t1.old_signature 188 ) 189 UPDATE bookmarks 190 SET url = (SELECT url FROM t1 WHERE t1.old_signature = bookmarks.signature), 191 parent = (SELECT parent FROM t1 WHERE t1.old_signature = bookmarks.signature), 192 signature = (SELECT signature FROM t1 WHERE t1.old_signature = bookmarks.signature) 193 WHERE signature IN (SELECT old_signature FROM t1); 194 ``` 195 196 Here's the result of running this update: 197 198 ``` 199 +----+------------------------------------------+------------------------------------------+-----------+ 200 | id | signature | parent | url | 201 +----+------------------------------------------+------------------------------------------+-----------+ 202 | 1 | 759730a97e4373f3a0ee12805db065e3a4a649a5 | | google | 203 | 2 | de357e976171e528088843dfa35c1097017b1009 | 759730a97e4373f3a0ee12805db065e3a4a649a5 | askjeeves | 204 | 3 | 1b69dff11f3e8ffeade0f42521f9e1bd1bd78539 | de357e976171e528088843dfa35c1097017b1009 | bing | 205 | 4 | 924660e4f25e2ac8c38ca25bae201ad3a5b6e545 | 1b69dff11f3e8ffeade0f42521f9e1bd1bd78539 | altavista | 206 +----+------------------------------------------+------------------------------------------+-----------+ 207 ``` 208 209 As you can see, row 2's `url` is updated, and rows 3 and 4 have updated 210 signatures and parents. Pretty cool, and pretty much the same thing as 211 what happens when you change a git commit via `rebase` --- all the 212 successive commits get new SHAs. 213 214 --- 215 216 I'll be honest that I don't have any immediately practical uses for a 217 cryptographically-signed database table, but I thought it was cool and 218 helped me understand these concepts a little bit better. Hopefully it 219 gets your mental wheels spinning a little bit, too. Thanks for reading! 220 221 [^1]: [Here's a pretty good explanation of what mining really is](https://asthasr.github.io/posts/how-blockchains-work/), but, in a nutshell, it's running a hashing algorithm over and over again 222 with a random salt until a hash is found that begins with a required number of zeroes.