asthasr-github-io-s0ebht.txt (7719B)
1 data Blog = Blog { me :: Programmer, posts :: [Opinion] } 2 [1]Posts [2]RSS 3 4 How Blockchains Work 5 6 Chances are, you know what Bitcoin is. After all, it’s valued at over $47,000 7 per Bitcoin right now. This post isn’t about the business side of things, 8 though, or the BTC speculative bubble. I want to explain how it works.^[3]1 9 10 Foundations: Hashes and Ledgers 11 12 First, a hash algorithm is a way to convert a given string into an 13 unpredictable string of a fixed length, called a digest. 14 15 A diagram illustrating that a hash algorithm produces a digest from a string. 16 17 Here’s a small Python program to demonstrate: 18 19 #!/usr/bin/env python3 20 from argparse import ArgumentParser 21 from hashlib import md5 22 23 24 def hash_string(string): 25 hash = md5() 26 hash.update(string.encode("utf-8")) 27 return hash.hexdigest() 28 29 30 if __name__ == "__main__": 31 parser = ArgumentParser() 32 parser.add_argument("STRING", help="The string to be hashed") 33 args = parser.parse_args() 34 print(hash_string(args.STRING)) 35 36 Running this with different string arguments will give you digests of the 37 arguments: 38 39 $ ./hash ninja 40 3899dcbab79f92af727c2190bbd8abc5 41 42 $ ./hash samurai 43 99b1983cf3ee09bbaf6f43ac7b4c8748 44 45 Hashes of this type are used to check passwords—you can check whether a 46 password matches without storing the password itself.^[4]2 47 48 Blockchains are a kind of ledger: they have entries added to them over time. 49 Hashes can help with that by protecting the ordering and contents of messages. 50 51 A diagram illustrating that blockchains capture the previous digest and the 52 current message to produce a digest. 53 54 Here’s a brief implementation: 55 56 def hash_ledger_entry(string, previous_digest=None): 57 """Hashes a string with the hash of previous entries in the ledger, if any.""" 58 hash = md5(string.encode("utf-8")) 59 60 if previous_digest: 61 hash.update(previous_digest.encode("utf-8")) 62 63 return hash.hexdigest() 64 65 66 def generate_ledger(*strings): 67 """Generates the entries in a ledger consisting of a set of strings.""" 68 digest = None 69 70 for string in strings: 71 digest = hash_ledger_entry(string, digest) 72 yield digest, string 73 74 75 if __name__ == "__main__": 76 parser = ArgumentParser() 77 parser.add_argument("STRINGS", help="The ledger entries", nargs="+") 78 args = parser.parse_args() 79 80 for digest, string in generate_ledger(*args.STRINGS): 81 print(f"{digest}\t{string}") 82 83 With this script, providing a set of strings will generate a unique and ordered 84 ledger: 85 86 $ ./hash ninja samurai 87 3899dcbab79f92af727c2190bbd8abc5 ninja 88 6bf8d2cadde40af53d7f0fef95d4ec2c samurai 89 90 These hash ledgers are tamper-resistant because the digests of later entries 91 depend on the earlier entries. Modifying or adding entries will change the 92 digest of later entries. 93 94 $ ./hash ninja pirate samurai 95 3899dcbab79f92af727c2190bbd8abc5 ninja 96 7ec21dcf528e12036b04774754ecc4e0 pirate 97 636730d86709d03fed9ba64f84fc9be6 samurai 98 99 We can also add a known ending entry to the ledger to protect the last entry 100 from tampering: 101 102 $ ./hash ninja pirate samurai 103 3899dcbab79f92af727c2190bbd8abc5 ninja 104 7ec21dcf528e12036b04774754ecc4e0 pirate 105 636730d86709d03fed9ba64f84fc9be6 samurai 106 b233d566fe677d394aafb5eaf149e453 END 107 108 Validation 109 110 To validate a ledger, you can replay the transactions and make sure that you 111 get the same hashes at each step: 112 113 our_digest = None 114 115 for line in fileinput.input(): 116 file_digest, word = line.strip().split("\t") 117 our_digest = hash_ledger_entry(word, our_digest) 118 119 if our_digest != file_digest: 120 sys.exit(f"The digest for {word} does not match.") 121 122 print("All entries match.") 123 124 With a tamper-resistant ledger where each entry depends on the previous 125 entries, we’ve effectively implemented a very simple blockchain. This is not 126 the same as the blockchain, though; for that we need… 127 128 Proofs without Authority 129 130 The novelty of Bitcoin is that it is a distributed system with no owner. This 131 is what enthusiasts mean when they say that the blockchain is trustless: 132 instead of central authority, like a bank, many “miners” compete to 133 successfully write a new message to the blockchain. They do this by means of a 134 proof-of-work algorithm, which we can implement in our ledger as well. 135 136 # Add this to your imports. 137 from secrets import token_bytes 138 139 140 def hash_ledger_entry_with_salt(salt, string, previous_digest=None): 141 """Hashes a string with the hash of previous entries in the ledger, if any.""" 142 hash = md5(string.encode("utf-8")) 143 hash.update(salt) 144 145 if previous_digest: 146 hash.update(previous_digest.encode("utf-8")) 147 148 return hash.hexdigest() 149 150 151 def generate_ledger(difficulty, *strings): 152 # Difficulty determines how many zeroes we require at the beginning of a digest. 153 prefix = "0" * difficulty 154 155 digest = None 156 previous_digest = None 157 158 for string in strings: 159 # We re-hash a string over and over, with random salts, until it matches the 160 # prefix determined by our difficulty. 161 while digest is None or not digest.startswith(prefix): 162 salt = token_bytes(16) 163 digest = hash_ledger_entry_with_salt(salt, string, previous_digest) 164 165 # We yield back the digest and entry, as before, but we need the salt, too. 166 # Without that, we can't replay the entries and verify them. 167 yield digest, salt.hex(), string 168 previous_digest = digest 169 digest = None 170 171 yield hash_ledger_entry_with_salt(salt, "END", previous_digest), salt, "END" 172 173 174 if __name__ == "__main__": 175 parser = ArgumentParser() 176 parser.add_argument( 177 "DIFFICULTY", help="The difficulty of confirming a ledger entry.", type=int 178 ) 179 parser.add_argument("STRINGS", help="The ledger entries", nargs="+") 180 args = parser.parse_args() 181 182 for digest, salt, string in generate_ledger(args.DIFFICULTY, *args.STRINGS): 183 print(f"{digest}\t{salt}\t{string}") 184 185 The new utility accepts an additional argument, difficulty, and tries to 186 generate a salt value that generates a hash which matches the expected number 187 of zeroes: 188 189 $ ./hash 5 ninja pirate samurai 190 00000ad72553509e6c197e45ab7fa436 af0dce7ac4c87c2b9d9eafb6561c09f4 ninja 191 000000f556426cfa894ba2ce57383b1d b9d51e0e8ea977ba004e7c30be757144 pirate 192 000006373b2b336d6dac403a5fa90a73 dd9c6ad89f5014a0901bcb142e04e28b samurai 193 fa35b5a39bc0318015620684d60a27f0 dd9c6ad89f5014a0901bcb142e04e28b END 194 195 The “mining” process can require a lot of calculations. The example required, 196 on average, around 2.5 million attempts. That’s why Bitcoin mining consumes [5] 197 more electricity than many countries: on the “real” blockchain, miners are 198 calculating and recalculating quadrillions of hashes per bitcoin mined. 199 200 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 201 202 1. If you want to read about the bubble, I recommend [6]David Gerard. [7]↩︎ 203 204 2. Note that md5 should not be used for this purpose in real applications. I 205 chose it here for the brevity of its digests, but it isn’t secure. [8]↩︎ 206 207 208 References: 209 210 [1] https://asthasr.github.io/ 211 [2] https://asthasr.github.io/index.xml 212 [3] https://asthasr.github.io/posts/how-blockchains-work/#fn:1 213 [4] https://asthasr.github.io/posts/how-blockchains-work/#fn:2 214 [5] https://www.bbc.com/news/technology-56012952 215 [6] https://davidgerard.co.uk/blockchain/ 216 [7] https://asthasr.github.io/posts/how-blockchains-work/#fnref:1 217 [8] https://asthasr.github.io/posts/how-blockchains-work/#fnref:2