Volonbolon

Standard Nerd

[iamvolonbolon]

What's a Dynamic framework

All standard iOS libraries are dynamic frameworks, and they They are handled in Xcode in a bundle with the extension .framework. Although they are directories, Xcode recognizes them as special cases, and treat them as files. Is easier to move them between projects.

They are usually shared across multiple applications, but because they are loaded dynamically, at runtime, the system can store only one copy, and let different process access it on demand

Inside a framework, you will find a bunch of files, mostly metadata, two of them are especially interesting.

Module Map

It is a file that tells Xcode where to find headers for relevant objects. We can edit it to add functionalities from other frameworks.

framework module Volonbolon { umbrella header "Volonbolon.h" export * module * { export * } } module Volonbolon.Swift { header "Volonbolon-Swift.h" requires objc }

Share Object

It is an executable that has the same name as the framework. It is compiled when the framework is created and is the object that can be shared amongst multiple applications. Because it can be shared across multiple apps and platforms, we end up with a leaner package. In fact, when linking the actual binary (.dylib) is not accepted, we need to link against text-based .dylib stubs (.tbd).

A .tbd is a YAML that contains the name of all the symbols and the location of the binary, but not the implementation. As a result, its size is smaller.

A typical .tbd would be something like

--- !tapi-tbd tbd-version: 4 targets: [ x86_64-ios-simulator ] uuids: - target: x86_64-ios-simulator value: 3DF443DB-F355-321D-9A25-F240AAD0B145 flags: [ not_app_extension_safe ] install-name: '@rpath/Volonbolon.framework/Volonbolon' swift-abi-version: 7 exports: - targets: [ x86_64-ios-simulator ] symbols: [ '_$s10VolonbolonAAV10volonbolonABSS_tcfC', '_$s10VolonbolonAAV10volonbolonSSvg', '_$s10VolonbolonAAV10volonbolonSSvpMV', '_$s10VolonbolonAAVMa', '_$s10VolonbolonAAVMn', '_$s10VolonbolonAAVN', _VolonbolonVersionNumber, _VolonbolonVersionString ] ...

This is a very simple framework containing a struct.

To generate the .tbd, we can use tapi from the Xcrun toolchain

xcrun -r tapi stubify [lib]

[iamvolonbolon]

RSA explained

One of the oldest asymmetric cryptosystems, develop in the 70s and still used today. The story goes that, one night in 1977, Ron Rivest drank a few glasses of wine, and, unable to sleep, found a trap door function that was alluding him, and his partners Adi Shamir and Leonard Adleman. It is a great achievement of 20th-century math, and yet, technically, is not really hard to follow. Let's try it.

Key Generation

First, we need to choose two prime numbers. In a real-world scenario, we would be using huge prime numbers, hundreds of digits long, but as an illustration, let's pick two small primes, 5 and 13.

p = 5, q = 13

Now, we compute the product of these two numbers

modulus = 65

The modulus length, usually expressed in bits, is the key length. It is distributed as part of the public key.

Now, we compute [Carmichael function](the https://en.wikipedia.org/wiki/Carmichael_function). Which is, basically, the number of caprimes with modulus in the range 1 < n < modulus. Instead of just listing all the caprimes with modulus, and and since p and q are prime, λ(p) = φ(p) = p − 1 and likewise λ(q) = q − 1. Hence λ(modulus) = lcm(p − 1, q − 1).

In our case, the least common multiple, and thus, our λ for our modulus is 65.

The lambda is kept private.

Now, we need to pick an integer, which we are going to call e such that 1 < e < λ(modulus) and is coprime with `λ(modulus)

We can use Python to produce a list of candidates:

>>> from math import gcd >>> def coprime(a, b): ... return cgd(a, b) == 1 ... >>> p = 5 >>> q = 13 >>> phi = (p-1) * (q-1) >>> e_candidates = [e for e in range(2, phi) if coprime(e, phi)] [5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47]

We can produce any number from that list as e, which, along with modulus is part of the public key.

Finally, we need to produce our private key, an integer (d) that should solve:

d * e = 1 (mod λ(modulus))

If, for instance, in our example, we pick 35 as our public e, then we can generate the following list of candidates for d

[11, 59, 107, 155, 203, 251, 299, 347, 395, 443, 491, 539, 587, 635, 683, 731, 779, 827, 875, 923, 971]

We can pick any d from the list, and we should keep it to ourselves.

Key Distribution

The beauty of the system is that the key can be distributed through a reliable, although not necessarily a secret channel.

The public keys will allow anyone to encrypt messages that will be only readable for the one holding the private key. It would be unfeasible to either guess or derive the private key from the public key.

Encryption / Decryption

If Alice wants to share with me the "Answer to the Ultimate Question of Life, the Universe, and Everything", but doesn't want Charlie to know, I will need her to know my public key, composed from e and the modulus

>>> from collections import namedtuple >>> public_struct = namedtuple("public", "e mod") >>> public = public_struct(35, 65) >>> public public(e=35, mod=65)

Then she will be able to encrypt the message, by multiplying itself as many times as indicated by e, mod modulus.

>>> t = 42 >>> c = (t ** public.e) % public.mod >>> c 48

48 is our cipher text, Charlie has no way to know anything about the "answer to the ultimate question of life", only me, holding the private key

>>> private_struct = namedtuple("private", "d mod") >>> private = private_struct(587, 65)

Would be able to decrypt it:

>>> decrypted = (c ** private.d) % private.mod >>> decrypted 42

[iamvolonbolon]

Error detection in Ethereum Address

Sometimes, you find beauty in the simplest thing. Let's consider how Vitalik Buterin and Alex Van de Sande introduced a checksum in Ethereum addresses.

First, let's remember that, unlike Bitcoin, Ethereum addresses do not incorporate a checksum. It was considered unnecessary. With ICAP support, and Ethereum Name Service, humans were not supposed to interact with raw hexadecimal strings. These two techniques (ICAP, a convention compatible with IBAN and ENS), are far better than the Base58 + checksum approach used in Blockchain, nevertheless, the transitional checksum method introduced by Buterin is brilliant.

In a typical hexadecimal representation of an address, we will have an average of 15 letters.

Let's consider this address:

0x8da82fcc73cbf2fb1a8c627ec2f0e3fcc3f06748

It contains 20 letters. Old wallets are case insensitive. 8da is not different from 8DA. That's important, because, it will allow us to modify the address to introduce a checksum without breaking these wallets.

First, we will take the Keccak256 hash from the lowercased address without the 0x prefix.

>>> keccak_256(b'8da82fcc73cbf2fb1a8c627ec2f0e3fcc3f06748').digest().hex()[:40] # We only need the first 20 bytes of the hash 'bfc2e364e7ddd96192c76f7fd3d6816e4cafbf96'

Now, we put the original address and the Keccak hash together, and whenever we found a letter in the address, we check the corresponding character in the hash. If it happens to greater than 8, we capitalize the letter, otherwise, we keep the lowercase.

8da82fcc73cbf2fb1a8c627ec2f0e3fcc3f06748 bfc2e364e7ddd96192c76f7fd3d6816e4cafbf96

For instance, the second and the third character in our original address are letters, and the corresponding characters in the hash are both greater than 8, which means that we should uppercase these two characters. 8DA…. The final checksum encoded address would be:

8DA82fcc73CBF2fb1a8c627EC2F0E3fCc3F06748

Detecting Errors

Let us now introduce a tiny mistake to simulate a misread. For instance, the 6th character right to left in the checksum encoded version of our address is F, easy to confuse with, let's say, E.

Fortunately, our wallet is EIP-55 complaint and seeing that the address contains both, lower and uppercase chars, it will create the checksum to compare. Because the hash function is highly sensitive to changes in the input, the hash itself is completely different (we changed only one bit, E and F are one bit apart)

25d14f3dff97d80217264e3de353a2cb0fde9add

And the checksum produced is all wrong:

8dA82FcC73CbF2fb1a8c627EC2f0E3FCc3E06748

You can take a look at a simple python implementation here

[iamvolonbolon]

CGD Barrier to prevent race conditions

We all been there:

Terminating app due to uncaught exception 'NSInternalInconsistencyException', reason: 'The number of rows contained in an existing section after the update must be equal to the number of rows contained in that section before the update, plus or minus the number of rows inserted or deleted from that section and plus or minus the number of rows moved into or out of that section (0 moved in, 0 moved out).'

The table view data is backed in an ivar (an array), which is asynchronously updated in a separate thread. But swift objects are not thread safe, writing to an instance variable is not atomic. Two threads can write at the same time, and that might cause memory corruption, or in a more benign case, to break the synchronization with other threads.

The ideal situation to avoid this behavior is that reads happen synchronously and concurrently, whereas writes can be asynchronous and must be the only thing happening to the reference.

That's exactly what GCD introduces when marking an execution block with the .barrier flag. When dispatching a block with such a flag, the queue will wait for all the running blocks to finish before starting the one marked, and if it receives any new block, it will wait until finishing the barrier block before starting with them.

First, we need to define a private queue to mediate access to the ivar

private let accessQueue = DispatchQueue(label: "me.volonbolon.isolation.queue", attributes: .concurrent)

Then, we can use it safely read from our ivar

var books: [Book] { get { accessQueue.sync { return self._books } } }

We wait for the queue to give us the ivar. Because the access queue is concurrent (private queues are serial by default, but we instantiate it as .concurrent), many reads can be performed simultaneously.

On the other hand, when writing, we want to block the thread, and thus, we dispatch the execution block asynchronously to free the caller quickly, and we mark it with the .barrier flag to make sure it will be run alone.

self.accessQueue.async(group: nil, qos: .userInitiated, flags: .barrier) { // update books // And the reload appropriate cells DispatchQueue.main.async { self.tableView.performBatchUpdates({ self.tableView.insertRows(at: indices, with: .automatic) }, completion: nil) } }

[iamvolonbolon]

DispatchWorkItem

Dispatch Queues are great, but sometimes, the Fire-and-forget approach is not quite right. We do have NSOperation, to encapsulate complex tasks, but what if we are dealing with something simple, something we can handle with Dispatch Queues, and yet, we need to cancel or create a simple dependency hierarchy? In that case, DispatchWorkItem might save the day.

A DispatchWorkItem encapsulates work to be performed on a dispatch queue or within a dispatch group. You can also use a work item as a DispatchSource event, registration, or cancellation handler.

Cancellation

The canonical example of DispatchWorkItem is retrieval of suggestions for a search bar. We have a search bar, and the user starts typing. We will wait for the user to stop typing, at least for a while, to query the backend.

class SearchController { var pendingWorkItem: DispatchWorkItem? func getSearchResults(query: String) { if !(pendingWorkItem?.isCancelled ?? false) { pendingWorkItem?.cancel() } let pending = DispatchWorkItem(qos: .userInitiated, flags: .assignCurrentContext) { print("Querying for '\(query)'") } pendingWorkItem = pending DispatchQueue.global().asyncAfter(deadline: .now() + .milliseconds(30), execute: pending) } } let search = SearchController() search.getSearchResults(query: "q") search.getSearchResults(query: "qw") sleep(UInt32(Int.random(in: 1...3))) search.getSearchResults(query: "qwe") // Querying for 'qw' // Querying for 'qwe'

Here we ignore the first query because, even before activating the work item, it got cancelled.

Dependency

We can also build a simple dependency structure. Let say we need two task, one after the other has been finished. Perhaps, we want to signal in the UI the end of a large computation. In that case, we can link work items with notify

let userQueue = DispatchQueue.global(qos: .userInitiated) func task1() { print("Task 1 started") sleep(2) print("Task 1 finished") } func task2() { print("Updating UI") } let backgroundWorkItem = DispatchWorkItem { task1() } let updateUIWorkItem = DispatchWorkItem { task2() } backgroundWorkItem.notify(queue: userQueue, execute: updateUIWorkItem) userQueue.async(execute: backgroundWorkItem) // Task 1 started // Task 1 finished // Updating UI

We can also block the thread until the workItem is done calling wait. In that case the system, if necessary/possible, will increase the priority of other tasks in its queue.

let userQueue = DispatchQueue.global(qos: .userInitiated) func task1() { print("Task 1 started") sleep(2) print("Task 1 finished") } func task2() { print("Updating UI") } let backgroundWorkItem = DispatchWorkItem { task1() } userQueue.async(execute: backgroundWorkItem) backgroundWorkItem.wait() print("We've passed the work item") // Task 1 started // Task 1 finished // We've passed the work item

[iamvolonbolon]

GitHub Codespaces and Swift

Are you waiting for Xcode on your iPad?. Relax, Microsoft is on it. GitHub announced Codespaces, a new tool presented as "your instant dev environment". How GitHub is going to give us Xcode on Mobile, thanks to this

We at Apple have decided to switch focus from supporting the libclang-based tooling infrastructure in order to join forces on the Clangd development efforts.

Clangd is a Language Server. It helps editors improve the support for different languages. Instead of having to recreate language support for each editor, you can deploy a server that editors can query to have a deeper awareness of the language. The analogy with a Web-based API is more than appropriate because the protocol does resemble HTTP:

Client and server communicate with each other exchanging messages. The messages are composed of a header and a content part. The content is encoded as JSON.

Whenever something happens in the editor, it sends a request message to the server, the server then processes the request, and return with an appropriate response. That way, the editor doesn't need to anything about the language. Autocomplete? Sure, no problem, let me ask the Language Server for the name of the vars, and I will show them to you.

Xcode 11.4 includes sourcekit-lsp in its toolchain. LSP stands for Language Server Protocol, and that's good news because it allows third party editors to gain access to a huge corpus of knowledge about ObjC and Swift. For instance, Visual Studio Code can leverage Clang knowledge about Swift without breaking a sweat.

Visual Studio Code

As said before, Xcode 11.4 introduced sourcekit-lsp We can check that running

❯ xcrun -f sourcekit-lsp /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/sourcekit-lsp

Since VSCode extensions are written in Javascript, we will Node:

Although Homebrew do have a node package, we will be using nvm, a Node manager that can swap different versions of NPM, is required.

To install it, we need to download

curl -o- https://raw.githubusercontent.com/creationix/nvm/v0.33.0/install.sh | bash

Let's check nvm installation by checking its version

❯ nvm --version 0.32.1

Now, we can install the latest LTS (Long-Term Support) with

❯ nvm install --lts Installing latest LTS version. VERSION_PATH='' ######################################################################### 100.0% Computing checksum with shasum -a 256 Checksums matched! Now using node v14.15.1 (npm v6.14.8)

And make it the active Node release with

❯ nvm use --lts Now using node v14.15.1 (npm v6.14.8)

Now, we need to build and install the SourceKit-LSP Extension for Visual Studio Code. Let's clone the sourcekit-lsp and use NPM to build the extension.

❯ git clone https://github.com/apple/sourcekit-lsp.git Cloning into 'sourcekit-lsp'... remote: Enumerating objects: 47, done. remote: Counting objects: 100% (47/47), done. remote: Compressing objects: 100% (36/36), done. remote: Total 6847 (delta 19), reused 22 (delta 11), pack-reused 6800 Receiving objects: 100% (6847/6847), 1.52 MiB | 3.13 MiB/s, done. Resolving deltas: 100% (5117/5117), done. ❯ cd sourcekit-lsp/Editors/vscode ❯ npm run createDevPackage > [email protected] createDevPackage /Users/arielrodriguez/Documents/sourcekit-lsp/Editors/vscode > npm install && ./node_modules/.bin/vsce package -o ./out/sourcekit-lsp-vscode-dev.vsix added 73 packages from 62 contributors and audited 73 packages in 3.693s 2 packages are looking for funding run `npm fund` for details found 0 vulnerabilities Executing prepublish script 'npm run vscode:prepublish'... > [email protected] vscode:prepublish /Users/arielrodriguez/Documents/sourcekit-lsp/Editors/vscode > npm run compile > [email protected] compile /Users/arielrodriguez/Documents/sourcekit-lsp/Editors/vscode > tsc -p ./ DONE Packaged: ./out/sourcekit-lsp-vscode-dev.vsix (104 files, 169.8KB) INFO The latest version of vsce is 1.81.1 and you have 1.79.5. Update it now: npm install -g vsce

And finally, we can install the extension with

❯ code --install-extension out/sourcekit-lsp-vscode-dev.vsix Installing extensions... (node:40702) [DEP0005] DeprecationWarning: Buffer() is deprecated due to security and usability issues. Please use the Buffer.alloc(), Buffer.allocUnsafe(), or Buffer.from() methods instead. Extension 'sourcekit-lsp-vscode-dev.vsix' was successfully installed.

Back to the beginning, I've mentioned that GitHub was working to give us Xcode on Mobile. Microsoft is touting Codespaces as "the full Visual Studio Code experience without leaving GitHub" That's why LSP is important.

[iamvolonbolon]

Merkle Tree

They are a hash based data structure that generalize the concept of a hash list. Each leaf node is a hash of a block of data, and each non-leaf node is a hash of the concatenation of its children. Usually, they are build as binary trees, although thats not a requirement.

With them we can efficiently validate data across a network.

At the most basic level, we can compare two trees for identity by comparing the root. The root is a representation of the whole data set. The change of any single leaf at the bottom bubbles up to the root. This is not only wonderful because it reduces the number of comparisons we need to perform, it is even better because it reduces the amount of data we need to dispatch over a network. Typically 32 bytes, instead of, perhaps, GBs worth of content.

But wait, if all we want is to check the integrity of a potentially huge file, why bother with a tree data structure. We can hash the file, are we are done.

That's correct. If we only want to check the integrity of a data set, a hash is enough. We do build the tree because it is convenient to perform partial verifications. In a peer to peer network, we can verify subsets as we receive them. Even further, we might be interested only in a a subset, and we the tree structure, we can validate the portion we need.

If we receive the root from a trusted source, then we can ask for the pieces from any source. We can later verify the integrity of the whole or a subset later.

Proof of membership

Let's pretend we want to check if D is part of a tree.

First, we need to get the path to the leaf we want to evaluate. Once we have that path, we need to produce a proof. Essentially, a road map to traverse the tree, rebuilding the portions that we need.

Proof

To build up the proof, we can move down from the root, following the path to the leaf, and annotating our journey. We will find three types of nodes.

A leaf

A node in our path

A sibling of a node in our path

A simple algorithm would demand a bitfield to annotate information about the node we are visiting, and a list to save node data that we will need later to compute the tree.

If the node we are visiting is a leaf, we enter a 1 into the bitfield and we add the node to the list

If the node is in our path, we push a 1 to the bitfield, and we calculate its value traversing left and right.

Otherwise we introduce a 0 to our bitfield, and we move back to the parent.

Starting at the root ABCDEEEE, which obviously is in our path, we have:

Bitfield = 0b1 Hashes = []

ABCD is in our path:

Bitfield = 0b11 Hashes = []

AB is not in our path, let's add a zero to the bitfield and save AB to the hashes list

Bitfield = 0b110 Hashes = [`AB`]

Back to ABCD, we traverse to the right. CD is in the path.

Bitfield = 0b1101 Hashes = [`AB`]

Now we are at the leaves level, let's add both to the hashes

Bitfield = 0b110111 Hashes = [`AB`, `C`, `D`]

Since we completed the left branch of the root, we should go right, were we find a node which is not part of our path.

Bitfield = 0b1101110 Hashes = [`AB`, `C`, `D`, `EEEE`]

Membership validation

We have our proof, and we know that, since we have 5 leaves, the height of our tree is four1.

Now we can build a partial tree, and hopefully, find out that the root is the same (and thus, we will verify the integrity of the actual tree, and that the leaf under evaluation is, actually, part of it).

If the bit extracted from the bitfield is 1, and we are not at the leaf level, we append an empty node (which value would be computed later) to the tree. If we found a 1, but we are at the leaves level, we pop the value from the hashes array. If the bit is zero, we also pop the value from the hashes list, and move back to the parent. All the way back until we find a node with a null right node, and then, we traverse that branch. In our case, we will end up with something like this.

And by filling the empty nodes, we end up calculating the root to validate the entire tree.

Use cases

Git use Merkle Trees to check for consistency across multiple repos.

Blockchain also use Merkle Trees to preserve block integrity. Each transaction is hashed, and a tree is computed. Altering a single transaction is unfeasible.

Merkle trees can be used to check for inconsistencies in more than just files and basic data structures like the blockchain. Apache Cassandra and other NoSQL systems use Merkle trees to detect inconsistencies between replicas of entire databases.

We can accommodate five leaves in a tree that will fit 8 leaves when perfectly balanced, and with that many leaves, we will have 15 nodes, and four levels ↩︎

[iamvolonbolon]

Exploring Databases

A requirement of almost any program is to persist data and retrieve data. That’s why we have Databases. A Database is usually designed to store and manages a large amount of data. A database has to be accurate, with all sorts of internal checks, giving integrity to the data it manages. Since they are a solution to a pervasive problem, it is easy to see why they have been developed since the early days of CS, and why we have different flavors, for different needs. Let's review them.

Key-Value

The most simple approach is a hash pairing keys and values. Fast and easy to use, they are popular to build caches. Because they hold data in memory, there is a limitation to the amount of data at their disposal, but at the same time, by avoiding round trips to slow second memory, they are super fast. They are also limited in the interface. No fancy queries, JOINs, or anything like that. Just read and write. Let's see an example in Redis

# redis-cli > 127.0.0.1:6379> SET maurice_moss reynholm OK > 127.0.0.1:6379> GET maurice_moss "reynholm"

Best for: Reduce data latency. Usually deployed on top of some other database used to persist data. Popular alternatives: Redis, MemCache

Wide Column

We can stretch the value part of a key-value DB, to store a set of ordered rows, and then we have a wide column DB. That way we can group data together and associate it with the same key. These databases don't have a schema, and they can easily handle unstructured data I know, I know, Cassandra does have a schema. That's true. It is also true that it was developed schemaless. Schemas were added later. We can interact with them with some languages (like CQL), that usually are similar to the most popular SQL, but limited (still no fancy operations like JOINs) Because of its nature, they are easy to replicate and scale-up. And no, the reason they are easy to replicate is not that they are NoSQL, it is because they relax on the ACID requirements. You see, read scaling is not that hard. Bottlenecks appear only when introducing JOINs and that kind of operations, which can be opt-out even in RDBMS. The problem is to scale up writes. If you want to speed up writes, then you will need to relax on atomicity by shorten the time tables are locked (like MongoDB), consistency which let's scale-up in a cluster of nodes (like Cassandra) or durability holding everything on memory and avoiding round trips to disk (as we saw already, Redis). In fact, these types of databases are popular in applications where writing is much more frequent than reading. Let's imaging a system that persist readings from a vast array of wheather stations:

cqlsh> CREATE KEYSPACE IF NOT EXISTS mycassandra WITH REPLICATION = {'class': 'SimpleStrategy', 'replication_factor': 1}; cqlsh> USE mycassandra; cqlsh:mycassandra> CREATE TABLE IF NOT EXISTS wheather (temp float, pressure int, humidity float, location varchar, time timestamp, PRIMARY KEY(location)); cqlsh:mycassandra> INSERT INTO wheather (temp, pressure, humidity, location, time) VALUES (23, 1016, 90, 'Buenos Aires', toTimestamp(now())); cqlsh:mycassandra> INSERT INTO wheather (temp, pressure, humidity, location, time) VALUES (18, 1030, 72, 'Lisbon', toTimestamp(now())); cqlsh:mycassandra> SELECT * FROM wheather; location | humidity | pressure | temp | time --------------+----------+----------+------+--------------------------------- Lisbon | 72 | 1030 | 18 | 2020-09-24 22:25:44.563000+0000 Buenos Aires | 90 | 1016 | 23 | 2020-09-24 22:24:36.110000+0000 (2 rows)

Best for: Backing IoT Popular alternatives: Apache Cassandra, Apache HBase, Cloud Bigtable

Document DB

They are based on documents, where each document is a container of key-value pairs. They are unstructured and don't require a schema. Documents are group together in collections, and fields within collections can be indexed. Collections can be organized in hierarchies, allowing some kind of relational modeling. Still no JOINs. Denormalization is encouraged, because of this, write operations could be a little slower, but, as we saw earlier, they relax on ACID requirements to achieve better performance.

root@7747c048549d:/# mongo MongoDB shell version v4.4.1 > use reynholm_employees; switched to db reynholm_employees > db.it.save({first: "Maurice", last: "Moss"}); WriteResult({ "nInserted" : 1 }) > db.it.save({first: "Roy", last: "Trenneman"}); WriteResult({ "nInserted" : 1 }) > db.it.save({first: "Jen", last: "Barber"}); WriteResult({ "nInserted" : 1 }) > db.it.find({first: "Maurice"}); { "_id" : ObjectId("5f6d2a4ced7dc6a9061ed522"), "first" : "Maurice", "last" : "Moss" } >

Best for: They are very popular in IoT and content management. They are also great to start if not sure about how data is structured. Popular alternatives: MongoDB, Apache CouchDB

RDBMs

Very popular, and one of the older paradigms. They are a collection of multiple data sets organized in tables with a well-defined relationship between them. Each table is a relation, each table record (row), contains a unique data instance defined for a corresponding column category. One or more data or record characteristics relate to one or many records to form a functional dependency (normalization). *One to One: One table record relates to another record in another table. *One to Many: One table record relates to many records in another table(s). *Many to One: More than one table record relates to a record in a different table. *Many to Many: More than one record relates to other records in different tables. We can interact with them with SQL (Structured Query Language) languages. Normalization requires a schema, which can be tricky if the data structure is not known in advance. The flip side is that we finally get to play with JOINs

mysql> CREATE TABLE orders ( -> order_id INT AUTO_INCREMENT PRIMARY KEY, -> timestamp TIMESTAMP DEFAULT CURRENT_TIMESTAMP -> ); Query OK, 0 rows affected (0.02 sec) mysql> CREATE TABLE details ( -> product_id INT AUTO_INCREMENT PRIMARY KEY, -> name VARCHAR(100), -> qty INT, -> order_id INT -> ); Query OK, 0 rows affected (0.02 sec) mysql> INSERT INTO orders (order_id) VALUES (NULL); Query OK, 1 row affected (0.00 sec) mysql> INSERT INTO orders (order_id) VALUES (NULL); Query OK, 1 row affected (0.00 sec) mysql> INSERT INTO details VALUES (NULL, 'Apricots', 4, 1); Query OK, 1 row affected (0.00 sec) mysql> INSERT INTO details VALUES (NULL, 'Bananas', 2, 1); Query OK, 1 row affected (0.00 sec) mysql> INSERT INTO details VALUES (NULL, 'Eggfruit', 1, 2); Query OK, 1 row affected (0.00 sec) mysql> INSERT INTO details VALUES (NULL, 'Blueberries', 3, 2); Query OK, 1 row affected (0.00 sec) mysql> SELECT o.order_id, o.timestamp, d.name, d.qty FROM orders o INNER JOIN details d ON o.order_id = d.order_id; +----------+---------------------+-------------+------+ | order_id | timestamp | name | qty | +----------+---------------------+-------------+------+ | 1 | 2020-09-25 12:32:02 | Apricots | 4 | | 1 | 2020-09-25 12:32:02 | Bananas | 2 | | 2 | 2020-09-25 12:32:06 | Eggfruit | 1 | | 2 | 2020-09-25 12:32:06 | Blueberries | 3 | +----------+---------------------+-------------+------+ 4 rows in set (0.00 sec)

Best for: Perhaps the most popular family of DBs, and essentials when data integrity is a must (financial). Popular alternatives: MySQL, PostgreSQL

Graph

In graph DB, the relationships between elements are first-class citizens, they are treated exactly the same as the elements. From a mathematical point of view, the relations are edges of a graph where the elements are nodes. Edges are always directed. It is far more efficient to traverse the data. We can specify edges, or move across the entire graph. Because the graph is already built, there is no need to compute JOINs and the performance is thus greatly improved. neo4j is perhaps the most popular graph database out there. In the sandbox it provides, there is a database with movies, actors, and directors. To compute the Tom Hanks number two we can do something like

MATCH (a:Person{name: "Tom Hanks"})-[:ACTED_IN]->(m:Movie)<-[:ACTED_IN]-(b:Person) MATCH (b:Person)-[:ACTED_IN]->(n:Movie)<-[:ACTED_IN]-(c:Person) WHERE c <> a AND NOT (a)-[ACTED_IN]->()<-[:ACTED_IN]-(c) -> RETURN c.name

Best for: Anything that can be expressed as a graph. Very popular with engine recommendations, and fraud detection. Popular alternatives: MongoDB, Apache CouchDB

[iamvolonbolon]

Protocols with Associated Type

Swift is type-safe, all types must be defined at compilation time.

We can easily define a protocol that requires a given type.

protocol MyProtocol { var myProperty: String { get set } }

And then, we can then adopt the protocol in other types.

struct MyStruct: MyProtocol { var myProperty = "this is my property" }

So far so good. We have a type that adopts a protocol. The compiler knows exactly what to do. Everyone is happy.

We can leverage the power of generics announcing the compiler that we are going to define the actual type later, at use time. For that, we use associatedtype.

protocol MyGenericProtocol { associatedtype myType var myProperty: myType { get set } }

Here, myType is a placeholder that will be defined by the type implementing the protocol.

Let's use it to feed some animals.

protocol Food {} protocol Animal { associatedtype FoodType: Food func eat(food: FoodType) }

Here we are telling the compiler that animals eat food. We don't know yet the actual type of food each animal eats, we are going to define that later. Or now.

struct Grass: Food {} struct Cow: Animal { func eat(food: Grass) { print(food) } }

Grass is a concrete implementation of Food, Cow is a concrete implementation of Animal, and, as we can see, it happens to eat Grass.

First-class citizen

In swift, protocols are first-class citizens. We can pass them around as return type, or as function attributes. But, if we try something like

func feed(animal: Animal) { }

We get the following error:

error: protocol 'Animal' can only be used as a generic constraint because it has Self or associated type requirements

The thing is that we can pass protocols as types, as long as they don't contain an associated type.

But we can use strait generics to let the compiler knows that we want to feed animals.

func feed<A: Animal>(animal: A) { if let cow = animal as? Cow { let grass = Grass() cow.eat(food: grass) } }

Here we just define a generic, requiring it to be a concrete instantiation of Animal, and that's that.

[iamvolonbolon]

The Builder Pattern

Sometimes building complex objects requires a lot of boilerplate code. Sometimes is just a matter of adjusting a large amount of parameters.

There is a design pattern that let us abstract away the construction of such objects, by using an intermediate representation.

Lets pretend we need to pack for a short trip. We can compile a list of things. We can encode such list in a struct.

Struct in Swift have, among many other benefit, a constructor automatically generated for us. Lets leverage that, and the fact that they are value type to build our PackingList

struct PackingList { let heavyCoat: Int let rainJacket: Int let pullover: Int let activewearCoat: Int let thermalUnderwear: Int let leggins: Int let darkJean: Int let sweater: Int let waterproofSnowBoots: Int let socks: Int let mittens: Int let beanie: Int let sunglass: Int let hat: Int let bathingSuit: Int let sunscreen: Int let handSanitizer: Int }

Creating a new list would be labour intensive, we will need to gather all the params at a creation point. We could, also, let our type to be mutable, and define default values for every parameter. That would defeat the intrinsic safety that unmutability grant us. Builder is there to help us.

We are going to add an extension to our PackingList to prevent polluting the interface.

In this extension, we are going to define a helper class, called Builder.

extension PackingList { class Builder { } }

We use a class here to chain setters, as we are going to see shortly.

Inside our helper class we define, our ivars, with a default value.

private var heavyCoat: Int = 0

And the setters:

func set(heavyCoat: Int) -> Builder { self.heavyCoat = heavyCoat return self }

As we can see, the setter, returns self, so we can chain a bunch of them at once. That's why we use a reference type here.

builder.set(heavyCoat: 0).set(rainJacket: 1)

Let's now consider the case of default packing, for summer. We can easily set default values in a helper function like:

func packForSummer() { self.set(heavyCoat: 0) .set(rainJacket: 1) .set(pullover: 0) }

We can even go a setp further, define an enum to properly instruct default packing:

enum Weather { case summer case winter } func pack(for weather: Weather = .summer) { switch weather { case .summer: self.packForSummer() case .winter: self.packForWinter() } }

These two are just helpers, but now, let's define the most important one, the actual point where we build the PackingList:

func build() -> PackingList { let packingList = PackingList(heavyCoat: self.heavyCoat, rainJacket: self.rainJacket, pullover: self.pullover, activewearCoat: self.activewearCoat, thermalUnderwear: self.thermalUnderwear, leggins: self.leggins, darkJean: self.darkJean, sweater: self.sweater, waterproofSnowBoots: self.waterproofSnowBoots, socks: self.socks, mittens: self.mittens, beanie: self.beanie, sunglass: self.sunglass, hat: self.hat, bathingSuit: self.bathingSuit, sunscreen: self.sunscreen, handSanitizer: self.handSanitizer) return packingList }

Now, we can easily construct a PackingList, either for winter or summer:

let summerBuilder = PackingList.Builder() summerBuilder.pack(for: .summer) let summerPackingList = summerBuilder.build() assert(summerPackingList.bathingSuit == 1) let winterBuilder = PackingList.Builder() winterBuilder.pack(for: .winter) let winterPackingList = winterBuilder.build() assert(winterPackingList.bathingSuit == 0)

Or we can easily customise the builder to properly build the list we want:

let customSummerBuilder = PackingList.Builder() customSummerBuilder.pack(for: .summer) customSummerBuilder.set(bathingSuit: 2) let customSummerPackingList = customSummerBuilder.build() assert(customSummerPackingList.bathingSuit == 2)

A full implemetation can be found in Gist

[iamvolonbolon]

Associated values in Enums

In Swift, Enumerations are much more flexible than in other languages like C. We Can define them not just as a set of integers, but as anything, provided we gave each case a raw value.

More importantly, cases can specify associated values of any type to be stored along with each value, much as unions or variants in other languages.

Swift enumerations can store associated values of any given type, including other enums. The values can be different for each case in the enumeration.

enum Support: String { case vynil = "Vynil" case mp3 = "MP3" case cd = "Audio CD" } enum Product { case book(String, String, Double, Int, Int) case album(String, String, Double, Int, Support) } let theIliad: Product = .book("The Iliad", "Homer", 14.99, -1184, 190) let blackstar: Product = .album("David Bowie", "Blackstar", 22.34, 2016, .vynil) let products = [theIliad, blackstar] products.forEach { (product: Product) in switch product { case .book(let title, let author, let price, let year, let pages): print("\(title) by \(author) was published in \(year). It cost $\(price), and contains \(pages)") case .album(let artist, let name, let price, let year, let support): print("\(artist) published \(name) in \(year). It cost $\(price) and it is distributed as \(support.rawValue)") } } /* The Iliad by Homer was published in -1184. It cost $14.99 and contains 190 David Bowie published Blackstar in 2016. It cost $22.34 and it is distributed as Vynil */

You have to choose

Unfortunately, in Swift enums, we can either have Associated Values or Raw Values, not both. The raw value of an enumeration is formalized with the RawRepresentable protocol which states:

With a RawRepresentable type, you can switch back and forth between a custom type and an associated RawValue type without losing the value of the original RawRepresentable type.

With a raw value, we are guaranteed to be able to reconstruct the original case.

let support: Support = .vynil let vynilRawValue = support.rawValue // "Vynil" let reconstructedSupport = Support(rawValue: vynilRawValue) // .vynil

In contrast, with associated values, we cannot reconstruct the original value from its raw value, because there is no way to tell which associated value to choose, breaking the promise of RawRepresentable.

[iamvolonbolon]

Proof-of-Work Algorithm

To prevent rogue miners to spoof blocks and bend the chain in its favor, blockchain requires miners to satisfy a computational task hard enough that renders the whole doctoring increasingly expensive. Such a task is the proof of work.

Hashcash

Many cryptocurrencies, including Bitcoin, implements a proof of work system inspired by Hashcash.

At any given point, the network is configured with a certain level of difficulty. Each miner competing to generate a block will need to compute a hash that satisfies this difficulty.

Now, we should remember that it is computationally unfeasible to produce two hashes with different inputs that produce the same output (a collision). An thus, it is also impossible to select and input in such a way to produce the desired hash, we should rely on brute force. And that's the core of the algorithm. Miners are required to come up with a value, known as nonce, that when combined with the rest of the block data, will produce a hash with the expected patron. In cryptography, a nonce is a value that can be used just once per communication. Since any unique nonce, when combined with the block data, will generate a unique hash, it is effectively used only once.

Specifically, the task is to find a hash that starts with as many zeros as required by the difficulty level, ie. if the difficulty level is 8, then miners will need to come up with a hash that starts with eight 0.

Finding such a hash becomes exponentially harder as difficulty increases.

To come up with the nonce is hard, but, given the data and the nonce, is really cheap to compute the hash to validate it.

What's in a name

From the perspective of an observer, to come up with a hash with a given fingerprint can be assumed as the amount of work the miner devoted to the task. For instance, if the output of the hash function is evenly distributed (and it should be), we should expect to find a result that satisfies a difficulty level 1 (a hash that starts with a 0) once every 16 hashes. The miner would need to produce, on average, 16 different nonces to come out with the required hash. The input (the block data plus the nonce), constitutes the proof that a certain amount of work has been done.

For instance the python code

import hashlib for nonce in range(16): input = f"proof of work {nonce}" hash = hashlib.sha256(input.encode()).hexdigest() print(f"{input} => {hash}")

Would produce

proof of work 0 => b0140183875afe8cb70aeb28768df900141496872fb80ddedc46867795a59c85 proof of work 1 => ca326d08692767df1ebaabd7110b2a20ef4a44b98357ab0064cb6512d4fdeb82 proof of work 2 => b8b980a3e0208bccdbeedcf3de82264e8b347e3682a2be00e2ee22accd95c8d6 proof of work 3 => 0f824adceeb31e9be937a58ef921bc716d9b9e31268547957f250cc11c5210ca proof of work 4 => bfe6cda02cffd7571b0761e0a5fbc241ecf032d44223b70e855a6f4e62799299 proof of work 5 => f23fac3c20bac4142274ad9fbd147b6b9fcb9639f67890b1cb5e14c3a170b63f proof of work 6 => 541dc25f1cfb360165399290bff83ec6a225b485db7fcebac5d8fec164364459 proof of work 7 => 93ea67585c69f22745eb2d462395e05ba6e8653654503967cf3f2e4de7ce9c9b proof of work 8 => eedb1e8764c539d3ef0ef542bf5b966d8c68607aff7cf43f0140a35ff8e4e07c proof of work 9 => 16e6a5f62cfc73d738c72e472de9b409a3209095243a45b4d030d848051963a2 proof of work 10 => 8352873cfcd2983c148cfe926bcd8cbfd3b16e861e6b0b95d3a042c504068234 proof of work 11 => 823de40d3c9cda98e8d5370c0e0a85ead14f71670dd61c9eedbcc2d33dd80939 proof of work 12 => d8657230b0aa16bd54caf922b71c0e9b6e7d48cb410bf0593a797ee68d3230c2 proof of work 13 => 32ff5b1a19605085000d8e4e12063b87bd6575558de9c9bec0157737891843b7 proof of work 14 => bd2bc7af1d6d45015cc808a10e5103f1bf823c7a1d9f96339833dbc9dc0f7ae3 proof of work 15 => ef82efc88dac6b50fd992bf9223ad67fdecd1aa279457cbb2bfaf5a7872ee533

In this particular case, the winning nonce would be 3.

Difficulty

By adjusting the difficulty level the system can fix the rate of mining. Too many nodes competing? Let's increase the difficulty level. For example, Bitcoin network is configured to let miners create a new block every 10 minutes in average, and to keep the rate, constantly adjusts the difficulty level.

Fifty-one percent attack

If a rogue node has at least 51% of the computational power of the network, in theory, can replace the chain with a doctored version, long enough for other nodes to accept, including all the required proof of work puzzles. That's the theory, in reality, such a scenario would be so expensive that it would be absolutely ridiculous to try to manipulate the chain that way.

Controlling 51% of the computation power of the network does not guarantee success to a malicious attack, it is just the point where the event is likely to happen.

As Satoshi Nakamoto summarize in the bitcoin original whitepaper

Proof-of-work is essentially one-CPU-one-vote. The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it. If a majority of CPU power is controlled by honest nodes, the honest chain will grow the fastest and outpace any competing chains.

On top of that, the attacker would be ruining the system he is trying to benefit from. After all, the confidence in the system would be forever lost, and, in the case of a cryptocurrency, its value would decline rapidly. Back to the bitcoin seminal whitepaper, Nakamoto explains:

If a greedy attacker is able to assemble more CPU power than all the honest nodes, he would have to choose between using it to defraud people by stealing back his payments or using it to generate new coins. He ought to find it more profitable to play by the rules, such rules that favor him with more new coins than everyone else combined, than to undermine the system and the validity of his own wealth.

For a brief period in 2014 Ghash.io achieved 51% of the computational power of Bitcoin. Obviously, the entire network was much smaller back then. To Ghash.io credit, they almost immediately relinquished 10 percent and asked the community to voluntary limit themselves to 40 percent.

Code

[iamvolonbolon]

Keys in Python

We already saw the basic concepts behind the creation of keys and address creation. Let’s try to implement them. I’m going to use Python because it’s easier to follow.

Following the Standards for Efficient Cryptography, we define the constants. In the document, please look for “Recommended 256-bit Elliptic Curve Domain Parameters over Fp“ (secp256k1)

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # Remember the equation we are using is `y^2 % p == x^3 + 7 a = 0x0000000000000000000000000000000000000000000000000000000000000000 b = 0x0000000000000000000000000000000000000000000000000000000000000007 # This is the generator point defined in the standard g = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

For pedagogical reasons, I’ve chosen python-ecdsa. It’s a pure python library, really easy to understand. In production settings, it might be worth to explore C alternatives for speed, but more importantly, this library should NOT be used in systems where os.urandom() is weak. Once installed the library, and imported to the Python unit, we can create a curve like this

# First, let's define the curve elliptic_curve_secp256k1 = ecdsa.ellipticcurve.CurveFp(p, a, b) # And, from the curve, extract the generator generator_secp256k1 = ecdsa.ellipticcurve.Point(elliptic_curve_secp256k1, g[0], g[1], order) # Now, we need to define the object identifiers for the elliptic curve domain parameters certicom_arc_oid = (1, 3, 132, 0, 10) #Finally, the curve secp256k1 = ecdsa.curves.Curve("SECP256k1", elliptic_curve_secp256k1, generator_secp256k1, certicom_arc_oid)

As we know, the private key is only a random number in the range [0, 2^256], we can pick it with a simple python function. The key here is to grab as many entropy as possible for the random draft. the os.urandom function is described in the documentation as capable of “Return a string of n random bytes suitable for cryptographic use”. The documentation also points to SystemRandom as an easy-to-use interface.

def private_key(): key = sum([(SystemRandom().randrange(2) * 2 ** idx) for idx in range(256)]) return key

Once we have the secret key, we compute the public key by performing the multiplication. Remember, the public key is a point in the curve, in other words, it’s an ordered pair.

public_key_point = secret_key * generator_secp256k1

When exposed, the public key is prefixed with 04, and then, the value of the x and y coordinates expressed as hex numbers:

04[hex(x)hex(y)]

But, as discussed before, since you can retrieve the value of y given x (and the sign of y), the compressed format is gaining popularity all the time. The sign of y is indicated by the prefixes 02 (positive ~ even) or 03 (negative ~ odd).

def produce_public_compressed_key_from_point(point): point_y_is_odd = point.y() & 1 if point_y_is_odd: key = '03' + '%064x' % point.x() else: key = '02' + '%064x' % point.x() return key

Gist

[iamvolonbolon]

Blockchain Public Key Representations

As we already saw, the public key is nothing but a point in the curve. The one we get after multiplying the generator the number of times defined by the secret.

Now, it seems a waste of space to save the x and y coordinates when we know it is the solution to the equation y^2 % p == (x^3 + 7) If we know x, we can calculate y. Public keys are present in most transactions, and since each block can contain several hundred transactions, by cutting the required space for each public key, we are saving a lot of storage (and network traffic). That’s the reason for the compressed public keys. They are basically, just the x coordinate of the point.

By basically, well, because since in the equation we have y squared, and the curve is symmetrical with respect to the x-axis, we need to somehow be able to know if y is positive or negative. We will use a prefix to distinguish positive and negative y. 02 indicates a positive y value. 03 a negative one.

But remember, we defined the curved not over the Euclidean plane, but on the finite field of prime order p. Here, the y coordinate is always positive. We distinguish between odd and even. Even values correspond to positive values when working over the Euclidean plane. Which means, 02 is used for even values, while 03 is reserved for odd values.

The old, uncompressed public keys are identified by the prefix 04.

To sum this up. The public key, by definition, is an ordered pair representing a point in the curve. Old, uncompressed public keys are identified with the prefix 04 and contain both coordinates. The newer form to represent the public key is to use just the x coordinate, and the prefix is used not just to identify the key as a “compressed key“, but also to inform whether y is positive or negative.

[iamvolonbolon]

Blockchain Keys

In the blockchain, there is nothing encrypted, but still, asymmetric cryptography is heavily used. Each wallet contains at least a pair of keys, a private one used to sign transactions (and to claim ownership of UTXO), and a public key, generated from the private one, and used to receive funds.

Just the holder of the private key can produce the numerical signature of a transaction from its fingerprint. But anyone can verify the signature with the public key and the fingerprint.

Private Key

A blockchain private key is nothing but a random number in the range [0, 2^256]. And here, random is paramount. Basic pseudo random generators are not enough. Remember, this random number is the only required proof to claim ownership (and to spend) associated funds. Obviously, Hardware Random Number Generator where entropy is obtained on some physical phenomena are better than Pseudo-random Number Generator, but even them might be good enough. They key here is that the generated number should be unpredictable1.

Elliptic Curve

An elliptic curve is a plane algebraic curve. In other words, is the set of points on the Euclidean plane whose coordinates are zeros of a polynomial in two variables.

The standard used in bitcoin is secp256k1, and choose a particular polynomial, y2 = x3 + 7. When evaluated in the real plane, you get a smooth curve symmetrical with respect to the x-axis. However, secp256k1 is defined over the field of prime order p2. That means you can kiss your smooth curve goodbye, now you are dealing with what seems to be a pattern of dots scattered through two dimensions. But that’s just a matter of representation, remember the definition, we just need a set. The mathematical properties we can find are associated with the object and not with the representation.

For a pedagogical purpose, let’s reduce the prime order of the field to 11. We end up with a pattern like this one.

Addition

One of the properties of the elliptic curve is that if we draw a line between two points in the curve, the line will intersect the curve in exactly an additional point. This operation is called addition. If P1 and P2 have the same x coordinate, and different y coordinate, then the line joining them will be parallel to the y axis, and P3 is defined as a point at infinity. Now, if either P1 or P2 are defined as points at infinity, then we have P1+P2=P2 (iff P1 is the point at infinity), or P1+P2=P1 (when P2 is a point at infinity). That’s the reason a point at infinity is sometimes called zero over additions.

Multiplication

Now that we have defined addition, we can extend the definition to multiplication pretty easily. From classic arithmetic, we know that to multiple a value V by K means to add V to itself K times. Then, let’s take a point P on the elliptic curve, and add P to itself K times and we have ‘k*P’.

To visualize the process, we can go back to the smooth representation of the curve over the real plane. To add a point to itself is equivalent to draw a tangent line to that point, find where the tangent intersects the curve, and then, reflect that point over the x-axis. The reflection point is the result of the multiplication. By performing the operation once, we will be adding P1 to itself, meaning, the result is equivalent to 2*P.

Back to our field of prime order 11, we can multiply (6,5) * 2, and the result is going to be (3, 1)

Public Key

We have a number chosen randomly in the range [0, 2^256], and we have defined such number our private key. We have also defined the multiplication operation over elliptic curves. And the standard defines a point in the elliptic curve called a Generator Point. We can then compute

K = k * G

Where k is the the private key, G is the generator point, and K is defined as the Public Key.

Because G is provided by the standard, given k, will always result in the same value for K, and the computation is pretty straightforward. But to find k given K and G is unfeasible (basically, you have to try every possible value, which on a field so vast as the one defined by the standard is unfeasible). Thus, we have defined a function with a wonderful property, is fairly easy to calculate in one direction, and almost impossible in the other one. A trap door.

Unpredictability is the property found in systems that prevent attackers to guess its output, even knowing previous results. ↩︎

p = 2^256-2^32-2^9-2^7-2^6-2^4-1 = 1.15792089×10^77 ↩︎

[iamvolonbolon]

[iamvolonbolon]

Find the start of a loop in a singly linked list

We already know how to detect loops in a singly linked list. Now, we are going to detect the node where the loop starts.

It’s easy to see that if we have two pointers moving one at twice the speed than the other, and if they start at the same time at the beginning of the loop, then they will found each other again at the very same point (with the faster point completing two laps and the slower just one).

What happens if, instead, the head of the singly linked list is not where the loop start. In that case, the slower pointer will give the faster one an advantage of k nodes, where k is the number of nodes from the head to the loop start. But where will the two pointers meet? They will meet k nodes before the end of the loop. Why? Well, by then, the slower pointer would have to walk n - k steps into the loop, and the fast one would have done k + 2(n - k)

Once we get the two pointers at the same node, and because we know they are k nodes away from the finish/start of the loop, all we need to do is to reset one of the pointers to the head of the linked list and move the two at the same speed these time. They will meet again at the start of the loop.

A complete implementation of the algorithm is in Gist