The Ultimate Hacking Bot™️ contains a bunch of useful hacking tools:

• LemmeKnow
• Ares
• Ciphey
• Search-That-Hash

The GitHub Link is below:

GitHub - bee-san/discord-bot: Discord bot for Ares & Lemmeknow in the http://discord.skerritt.blog discord server

Discord bot for Ares & Lemmeknow in the http://discord.skerritt.blog discord server - GitHub - bee-san/discord-bot: Discord bot for Ares & Lemmeknow in the http://discord.skerritt.blog disc…

GitHubbee-san

Using the bot

Go to http://discord.skerritt.blog , join and use the bot in the #bots channel with $help.

Installing on your own server

You can either use the docker image created autumnskerritt/discord_bot, or you could build your own Docker image or you could run cargo run . to run the bot.

You can also install my instance of the bot with the below link:

Discord - A New Way to Chat with Friends & Communities

Discord is the easiest way to communicate over voice, video, and text. Chat, hang out, and stay close with your friends and communities.

Discord

Over in my Discord we have a cool bot called ✨The Ultimate Hacking Bot✨

Really it's a bot that has a collection of pentesting tools one may find useful.

With many tools come many issues... Dependency issues...

If one of our many dependencies updated, our process was:

1. Update the dependency in Rust
2. Build the Docker image
3. Push it to a registry
4. Docker pull on the service
5. Docker compose up -d to run it.

Every. Single. Time.

Here's a quick guide on how we fixed this!

Automating the process away

The first step is updating the dependency.

We use Dependabot to automatically detect when packages update and create pull requests for them.

Bump serde from 1.0.151 to 1.0.158 by dependabot[bot] · Pull Request #28 · bee-san/discord-bot

Bumps serde from 1.0.151 to 1.0.158. Release notes Sourced from serde’s releases. v1.0.158 Fix “expected serde crate attribute to be a string” error when using macro_rules metavariable inside of…

GitHubbee-san

BUT we had to click "merge" every time. We wanted to automate that away too, so we built a GitHub action to do this:

name: Dependabot auto-approve
on: pull_request

permissions:
  pull-requests: write

jobs:
  dependabot:
    runs-on: ubuntu-latest
    if: ${{ github.actor == 'dependabot[bot]' }}
    steps:
      - name: Dependabot metadata
        id: metadata
        uses: dependabot/fetch-metadata@v1
        with:
          github-token: "${{ secrets.PERSONAL_TOKEN }}"
      - name: Approve a PR
        run: gh pr review --approve "$PR_URL"
        env:
          PR_URL: ${{github.event.pull_request.html_url}}
          GITHUB_TOKEN: ${{secrets.PERSONAL_TOKEN}}

This auto-approves and merges all Dependabot pull requests.

Second, we want to automatically build and publish the Docker image.

Again, we used GitHub actions here:

name: Publish Docker image

on:
  push:
    branches:
      - 'main'

jobs:
  push_to_registry:
    name: Push Docker image to Docker Hub
    runs-on: ubuntu-latest
    steps:
      - name: Check out the repo
        uses: actions/checkout@v3
      
      - name: Log in to Docker Hub
        uses: docker/login-action@f4ef78c080cd8ba55a85445d5b36e214a81df20a
        with:
          username: ${{ secrets.DOCKER_USERNAME }}
          password: ${{ secrets.DOCKER_PASSWORD }}
      
      - name: Extract metadata (tags, labels) for Docker
        id: meta
        uses: docker/metadata-action@9ec57ed1fcdbf14dcef7dfbe97b2010124a938b7
        with:
          images: my-docker-hub-namespace/my-docker-hub-repository
      
      - name: Build and push Docker image
        uses: docker/build-push-action@3b5e8027fcad23fda98b2e3ac259d8d67585f671
        with:
          context: .
          file: ./Dockerfile
          push: true
          tags: autumnskerritt/discord-bot:latest

Now we have the latest image pushed to Docker everytime a commit is merged to main branch!

Now we need to update and redeploy the image on our server.

I created a script which pulls the image down and runs Docker Rollout on it:

GitHub - Wowu/docker-rollout: 🚀 Zero Downtime Deployment for Docker Compose

🚀 Zero Downtime Deployment for Docker Compose. Contribute to Wowu/docker-rollout development by creating an account on GitHub.

GitHubWowu

cd ~/discord-bot
docker pull autumnskerritt/ultimate-hacking-bot:latest
docker rollout -f docker-compose.yml discord_bot

I turned this into a service:

[Unit]
Description=Discord Bot Updater
After=network.target
StartLimitIntervalSec=0
[Service]
Type=simple
Restart=on-failure
RestartSec=1
User=autumn
ExecStart=/usr/bin/env sh /home/autumn/discord-bot/daily_script.sh

[Install]
WantedBy=multi-user.target

Which runs at 4am every day:

[Unit]
Description=Ensures the execution of the Discord bot updater every day at 4:00 AM

[Timer]
OnCalendar=*-*-* 4:00:00
Unit=discord_bot_updater.service

[Install]
WantedBy=basic.target

🥳 And now our bot is automatically up to date with the latest and greatest hacking tools.

Hope you enjoyed this and can use parts of it in your own automated adventures :)

Fancy using the bot yourself? Come try it at:

Join the beesec Discord Server!

Programming & Cyber Security server | 1311 members

Discord

This is a very quick guide on running your own ChatGPT locally.

Why would you want to do this?

• You can use uncensored models

ChatGPT and the likes have an alignment that censors them.

For example, it's primarily aligned with Americans which means it's not very useful for most of the world.

It also has ethics / a moral code which prevents it from answering some questions.

As a security researcher, I often have to ask things which may be used for bad, like:

There are models out there we can use which are uncensored, the developers have attempted to remove this alignment and bias from their models.

This is a great blog post:

Uncensored Models

I am publishing this because many people are asking me how I did it, so I will explain. https://huggingface.co/ehartford/WizardLM-30B-Uncensored https://huggingface.co/ehartford/WizardLM-13B-Uncensored https://huggingface.co/ehartford/WizardLM-7B-Unc…

Eric HartfordEric's Code

• You do not have to trust OpenAI with your data

A local model means your data stays... local.

You do not have to upload private data to ChatGPT and risk them training a newer model on your data.

You do not have to trust them with customer information or whatnot when the data never, ever leaves your device.

• Always available

Unlike ChatGPT which has had issues staying online, a local model is always available s0 long as your computer is online.

🍾 Installing a model locally

We'll be using Kobold for this blog post.

GitHub - LostRuins/koboldcpp: A simple one-file way to run various GGML models with KoboldAI’s UI

A simple one-file way to run various GGML models with KoboldAI’s UI - GitHub - LostRuins/koboldcpp: A simple one-file way to run various GGML models with KoboldAI’s UI

LostRuinsGitHub

Kobold is a small application to run local models using a fancy UI.

We'll be running the LostRuins version because it's more up-to-date:

🔨 Installing

For Mac OS / Linux we need to:

$ git clone git@github.com:LostRuins/koboldcpp.git
$ cd koboldcpp
$ make

👾 Choosing a model

We need to download a model. These end in .bin usually (for binary).

For people with low RAM (you need at least 7gb to run this) we can use wizardlm-7b-uncensored.

You can choose any model you want, and if you have more RAM or a better GPU you might want to choose another model.

The subreddit LocalLLaMA regularly updates its wiki with the latest and greatest models:

models - LocalLLaMA

r/LocalLLaMA: Subreddit to discuss about Llama, the large language model created by Meta AI.

reddit

Once you find a model you like, download the .bin onto your computer.

I have made a folder /models which I store all my models in.

$ cd /models
$ wget https://huggingface.co/localmodels/WizardLM-7B-Uncensored-4bit/resolve/main/ggml/wizardlm-7b-uncensored-ggml-q4_1.bin

Now we run the Python file followed by the LLM and a port:

$ python3 koboldcpp.py /home/autumn/models/wizardlm-7b-uncensored-ggml-q4_1.bin.1 9057

Now go to localhost:9057 if you're running it locally and you should see...

We'll ask it a quick question to check it works.

Ok, that's not the current monarch of the UK but maybe the data doesn't go back that far 🤷‍♀️

If we check our terminal we can see it took around 20 seconds to run!

👮 Censorship test

Remember earlier when I tried to ask ChatGPT questionable things? Let's try it on WizardLM uncensored.

Ok, still American-centric.

Ay! This is exactly how I would exploit Eternal Blue.

📚 Scenarios

WizardLM features a neat scenarios tab.

ChatGPT is one specific scenario where you ask someone a question and get a reply. Most LLMs do not work like this off the bat, they need some sort of training or scenario to work in such a way.

For instance you can immerse yourself into your favourite Isekai or create your own ChatGPT.

Or you can talk to Special Agent Katia.

You can use any scenario on Aetherroom too:

/aids/ Prompts

/aids/ Prompts

Conclusion

That's... it!

It's super easy to run your own version of ChatGPT so long as you have the specs for it.

1. Generate your key.
2. Configure ssh to use the key.Your config file should have something similar to the following:You can add IdentitiesOnly yes to ensure ssh uses the specified IdentityFile and no other keyfiles during authentication.

Setting IdentitiesOnly prevents failed authentications from occurring, when ssh would otherwise attempt to login with multiple keys.

Setting this is also considered more secure, as you're not leaking information about other keys you have installed, and maintaining separation of your keys between different levels of access.

1. Copy your key to your server.

Solution 2 - Perms

Sometimes the issue comes from permissions and ownership. For instance, if you want to log in as root, /root, .ssh and authorized_keys must belong to root. Otherwise, sshd won't be able to read them and therefore won't be able to tell if the user is authorized to log in.

In your home directory:

chown -R your_user:your_user .ssh

As for rights, go with 700 for .ssh and 600 for authorized_keys

chmod 700 .ssh
chmod 600 .ssh/authorized_keys

Solution 3 - SSHing into the home directory

Also make sure that the user's home directory (on the server) actually belongs to the user ssh'ing into (was set to root:root in my case).

Should have been:

sudo chown username:username /home/username;

Solution 4 - if you have access to both machines

The following method might work if you can access machineA and machineB independently (e.g. from machineC).

If ssh-copy-id is not working, password authentication could be disabled. The following is a workaround.

Having machineA's public key in machineB's authorized keys (i.e. ~/.ssh/authorized_keys) will allow you to ssh from machineA. This also applies to scp.

After generating the key pairs using: ssh-keygen

On machineA, execute cat ~/.ssh/id_rsa.pub

Sample output:

ssh-rsa AAAAB3NzaSGMFZW7yB anask@mahineA

Copy the printed key (⌘ Command+C, or CRTL+C) then add it to the ~/.ssh/authorized_keys file on machineB.

For example, execute the following on machineB:

echo 'ssh-rsa AAAAB3NzaSGMFZW7yB anask@mahineA' >> ~/.ssh/authorized_keys

Tailscale SSH Permission denied

In my case, my Tailscale key had expired. I needed to go into the Tailscale UI and stop it from expiring or create another key.

I was looking to package my project, Ciphey, for operating systems and for managers that aren’t PyPi. Unfortunately, there seemed to be very little information on the web about this.

This is a guide on packaging your Python project for:

• PyPi
• HomeBrew
• Windows Package Manager
• Arch User Repository

Semantic Versioning

Semantic Versioning is a system defining how to write version numbers. The 3 numbers are:

Major.Minor.Bugs

If you have fixed some bugs, increment the bugs counter.

If you have added a minor feature, increment the minor counter.

If you have done something major, increment the major counter.

We can signify whether a release is still being rested or not by adding “rc” (release candidate) to the end of the version. “5.0.0rc1” signifies “release candidate 1” which means this is the first public testing release of version 5.0.0.

PyPi

The traditional method of using Setuptools is outdated and old. There’s a new cowboy in town, and their name is Poetry.

Poetry creates a pyproject.yml file, which is the successor to the 3-file Setuptools system.

You should use Poetry because:

• Instead of 3 files, it is now 1 file
• That 1 file is yaml, which means you don’t have to cry reading weirdly formatted Python code used as a replacement for yaml
• You can separate dev & normal dependencies, so users only install the dependencies they need to run the app
• It’s physically easier to build and upload to PyPi
• And a host of other things

Install poetry with pip3 install poetry.

Navigate to your projects directory and run the command poetry init.

This will generate a pyproject.toml file. This file contains everything PyPi needs to upload your project and allow other users to download it.

Let’s run through the sections in this new file, and fill them out as we go.

[tool.poetry]

This section relates to the metadata of your project.

The name, description, version etc.

To add a new variable to a .toml file, write it as if it were python name = "project name".

The most important ones we’ll want are:

• Name

What is the name of the project?

name = "Ciphey`

• Version

The semantic version number.

version = "5.0.0rc6"

• Description

Short one-line description.

description = "Automated decryption tool"

• Authors

A list containing the author's name and email address. In the format of authors = ["brandon <brandon@fake.com>"]

• License

What license does the project use?

license = "MIT"

• readme

The name of the README.md file, in the same directory, as pyproject.toml.

readme = "README.md"

Here is what Ciphey’s Pyproject looks like:

[tool.poetry]
name = "ciphey"
version = "5.0.0rc4"
description = "Automated Decryption Tool"
authors = ["Brandon <brandon@skerritt (dot) blog>"]
license = "MIT"
documentation = "https://docs.ciphey.online"
exclude = ["tests/hansard.txt"]
readme = "README.md"

To find out what else you can include, check out the Poetry documentation.

[tool.poetry.dependencies]

A list of all the dependencies your project uses. Don’t worry! You don’t have to manually add them to the list.

Run the command poetry add <dependency> to add a dependency to your project, and Poetry will automatically add it to your project.

For example, to add rich we would write poetry add rich.

[tool.poetry.dev-dependencies]

The dependencies the developers of your tool rely on. To add the testing library Pytest, write poetry add --dev pytest.

[tool.poetry.scripts]

This is the 2nd most important part! As it contains an entry point. When a user installs your package, you’d probably like them to be able to run package in their terminal and use your package.

For a folder called Ciphey with a file named Ciphey.py with a function called main(), we would write:

ciphey = 'ciphey.ciphey:main'

When the user runs the command ciphey, it actually runs the main function of the file ciphey of the folder ciphey.

For a more detailed explanation, check this out.

Poetry Run

poetry run runs our script but includes the pyproject.toml file. It executes the given command inside of a virtual environment, essentially it allows us to test our project in the same way a user might run our program.

Poetry Install

Poetry install installs our program and all its dependencies. Essentially, we can test exactly what our users will do when they install the project for themselves.

Poetry Update

poetry update updates our dependencies.

Poetry Build

Now onto the most important commands. Poetry build builds our project, which means it generates some files that other users can install and use on their system.

Poetry Publish

Poetry Publish will publish the package to PyPi for us. All we need to do is enter a username/password.

And just like that, our project is now on PyPi for the whole world to download!

Windows Package Manager (WinGet)

There are 3 steps to submitting your app to WinGet.

1. Turning your project into an EXE
2. Create a manifest file
3. Create a pull request on GitHub

Turning your project into an EXE

Windows requires an exe file for Python projects. Don’t fret! Turning your project into an exe file isn’t that difficult.

Download Pyinstaller, and then create an entry point in the root directory.

An entry point is a Python file that when run, will run the program. So for instance:

Ciphey/
|-entry_point.py
|-ciphey/
|----main.py

Here the project code is in ciphey/. To run the program, we’d have to run python3 ciphey/main.py.

This is the typical file structure of a project. We have README.md and similar in the root, and all the source code in a sub-directory.

We must create a program that calls our program using an entry point. The entry point is a function which runs the program.

If you have a setup.py or pyproject.yml, you may already have entry points defined in them.

In entry_point.py, we’d write:

from ciphey.__main__ import main

if __name__ == '__main__':
    main()

Or however, your entry point is defined.

Now, run Pyinstaller on the entry_point.py file. It will generate a new folder called dist/. If you are using the default Python .gitignore it will automatically disclude dist/. If not, please add it to the .gitignore!

Pyinstaller will also generate a entry_point.spec file in the root directory. This file contains a specification of how Pyinstaller should build your program.

Once built, run the program.

You will likely see some errors. Most likely bad imports. To fix this, define them in the spec file. There are a couple main lists in the spec file you should know about:

• Binaries

If you already hold a binary for a specific file/library (such as C++ compiled) then define the location here.

• Data

If your program relies on .txt data or anything that isn’t a Python file define it here.

• Hidden Imports

Hidden imports look like __import__.  These types of imports are not visible to Pyinstaller’s analysis, so to get around this define the imports in the Hidden imports section.

• Excludes

Exclude a package from Pyinstaller. I had an error with Setuptools, but since Setuptools isn’t needed to run Ciphey I told Pyinstaller to exclude the entire package.

If you have edited the .spec file, you may want to delete the line the .gitignore which states to ignore the file. Otherwise, all the hard work you’ve spent in getting Pyinstaller to work may be lost.

One thing to note. Pyinstaller only creates executables for the system you are on. You cannot build a Windows .exe from Linux. You have to be on the system you are trying to build. Pyinstaller can create these binaries (assuming you own the operating systems for them):

• Windows .exe
• Mac OS’ .app
• Linux’s Binary Files

Once built and packaged, running the executable on Windows / Mac will bring up the Terminal (assuming you do not have any GUI). If you do, it will bring up the GUI.

Pyinstaller packages an entire Python interpreter with the binary, So do not worry about the user having Python installed.

Manifest File

Now we have an exe. I would suggest converting to MSIX.

Exes are cool and all, but they’re not really package manager material. Winget with a .exe is a glorified Softonic / CNET Software. MSIX gives us the real power to:

• Automatically update the app
• Uninstall cleanly
• Understand what dependencies are required

So in short, if we use a .exe it is just a glorified Software downloader. If we use .msix it is more of a package manager.

Below is the manifest.yml file for Ciphey.

Id: Ciphey.Ciphey 
Publisher: Ciphey
Name: Ciphey 
Version: 5
AppMoniker: Ciphey
MinOSVersion: 10.0.0.0
Description: Automated Decryption Tool
Homepage: https://www.github.com/ciphey/ciphey
License: MIT
LicenseUrl: https://opensource.org/licenses/MIT 
InstallerType: exe
Installers:
  - Arch: x64
    Url: https://statics.teams.cdn.office.net/production-windows-x64/1.3.00.4461/Teams_windows_x64.exe
    Sha256: 712f139d71e56bfb306e4a7b739b0e1109abb662dfa164192a5cfd6adb24a4e1
ManifestVersion: 0.1.0

Ciphey’s manifest file Let’s walk through quickly what each potentially confusing part is. I’ll leave things like “Name” and “License” as they are self-explanatory.

• ID

This follows a publisher.package format. Your publisher's name, and then the package name.

• App Moniker

What’s the common name people search for your package with? For example “Visual Studio Code” can also be found with “vscode”.

If you have a long package name and your users often shorten it, this will be helpful to you.

• MinOSVersion

What is the minimum version of Windows the app supports? 10.0.0.0 means Windows 10 and above.

• InstallerType

What type of installer do you have? If you followed along, you should have a .exe file.

• Installers

This details how to install your package.

1. Architecture

What architecture does your project support? Examples include arm, arm64, x86, x64 and neutral.

The ones you’re probably after are either x86 or x64. x86 is for 32-bit operating systems, x64 is for 64-bit operating systems.

1. URL

What is the URL of the .exe installer for your project? Personally, I hosted this on GitHub.

1. SHA256

What is the SHA256 checksum of your .exe file? There’s an article here detailing how to calculate it.

• Manifest Version

Every time you update this file, update the manifest version numbering using Semantic Versioning.

If you’ve spent time on HackerRank or LeetCode, you might have noticed most of the optimal solutions use Set Theory. By reading this article, you will gain a deeper knowledge into set theory and how to use it to create optimal algorithms.

Set Theory was invented (or found, depending on how you view maths) by George Cantor.

It revolves around the idea of sets, as in collections of objects. Set theory is incredibly powerful and can be used to write some beautiful & elegant code.

🤔 What is a Set?

A set is simply a set of objects. They don’t have to be the same type or have any relation to one another.

set = (apples, pears, oranges)

Sets are denoted with parenthesis ( ). With the separation of elements being a comma. Or sometimes { }. Sets follow 2 rules:

• Only unique items.

Sets can only contain unique items. It cannot contain the same item twice or more.

• The set is unordered.

There is no order or structure to a set. The first rule is quite useful. Say, for example, we have a list of words from a book:

words = ["hello", "my",  "name", "is", "brandon", "and",
"your", "name", "is", "brandon"]

To find all the unique words, we put the words into a set:

words = ["hello", "my",  "name", "is", "brandon", "and",
"your", "name", "is", "brandon"]

unique = set(words)
# {'hello', 'is', 'and', 'brandon', 'my', 'your', 'name'}

The 2nd rule ties in nicely with the 1st rule. A set aims to replicate how we see things in our lives.

Imagine we are on a road trip with Jahan, Olivia, and Ryan.

Next year, we want to go on a field trip again. It doesn’t make much sense to invite Jahan, Olivia, Jahan, Ryan, and Jahan.

And it also doesn’t make sense to assign an “order” to them. They’re people, not elements in an array! There are other types of sets too. Such as a multiset which allows non-unique elements but no order.

🦁 Cardinality

The cardinality of a set is the length of the set. For the set:

$$A = \{1, 2, 3, 4, 5, 6\}$$

The cardinality is:

$$|A| = 6$$

🚴‍♀️ Equality of Sets

2 sets are equal when all the elements match.

$$a = \{1, 2, 3\}$$

$$b = \{3, 2, 1\}$$

$$a == b$$

Remember, the order doesn’t matter - so sets are equal despite being in the ‘wrong’ order!

🚇 Infinite Sets

Some sets are infinite. Such as the set containing all the natural numbers, or all the real numbers.

We can express infinite sets using a little bit of maths. Heard of list comprehensions? It looks the same syntactically but operates infinitely.

The set of all even numbers is:

$$A = \{2n: n \in \mathbb{Z}\}$$

Read this as "For each number, n, in the set of all integers, Z, multiply the number by 2". Which will give us the set of all even numbers.

Which will give us the set of all even numbers.

In a list comprehension, it would look like this:

[2 * n for n in naturalNumbers] 

However, this won’t work as Python doesn’t allow infinite sets.

🐈‍⬛ The Empty Set

The empty set is the set containing nothing at all. It is much like 0. It is nothing and serves the purpose of a negated value. We don’t have 0 apples, we have no apples.

The empty set serves the same purpose. We don’t have a set containing all the words, we have nothing.

Its symbol is ∅

🌌 The Universal Set

The Universal Set, U,  is the set which contains all objects, including itself. If our universe contains only integers, 1, 2, 3, …, then the universal set is the set of all integers.

🏥 Operations

Just like with other data types, sets have operations! Let’s start with some operations you may already know.

❌ Union

The union is combining 2 sets together (think addition). The symbol for the union is ∪. Let’s look at an example.

$$A = \{1, 2, 3\}$$

$$B = \{3, 4, 5\}$$

$$B \cup A = \{1, 2, 3, 4, 5\}$$

Notice how when we perform a union, we have two threes. Since sets only contain unique elements, we simply toss the extra 3 away. Also note, there is no order. So B ∪ A does not result in (3, 4, 5…) as the order doesn’t exist.

We can even say B ∪ A = {3, 5, 1, 4, 2}. What if we union an empty set with a non-empty set? Or an empty set with another empty set?

$$\varnothing \cup {1, 2, 3} = {1, 2, 3}$$

$$\varnothing \cup \varnothing = \varnothing$$

When we get onto subsets and the like we’ll learn to appreciate the empty set and this simplistic maths.

🦄 Intersection

The intersection of a set is every item in set A that is also in set B.

Think of it like the boolean operator AND. Its symbol is ∩.

$$A = \{1, 2, 3\}$$

$$B = \{3, 4, 5\}$$

$$A \cap B = \{3\}$$

Let’s say we have a list of flights with passengers on board. And we have a list of the people that took my daughter (Taken reference).

We can use the intersection operation to find the list of flights that contain the people who took my daughter.

Because sets only contain unique elements, it is very fast to calculate this. However, creating the set itself may take time. But, if we do not know all the names of the people in the child trafficking ring we can build the set first and use the intersection to query it.

💍 Belongs To

We can create sets which belong to other sets.11 belongs to set 1,2,31,2,3. In notation, this is:

$$1 \in {1, 2, 3}$$

We say that “1 is in the set {1, 2, 3}".

But don’t get caught out!

$$\{1\} \in \{1, 2, 3\}$$

That is not true. We say the element is not in ∉ the set.

$$\{1\} \notin \{1, 2, 3\}$$

It would be true if:

$$\{1\} \in \{\{1\}, 2, 3\}$$

This is a very, very useful feature. Let’s say we have the word “FLAG{” that we want to find in some text. We turn the text into a set, like so:

text = "FLAG{"
corpus = set("Hello",  "my", "name", "is")
if text in corpus:
	print("It's in there!")

Because sets do not contain unique items, this is rather fast. However, you have to take into account that turning it into a set is expensive.

🛩️ Subset

original = {1, 2, 3, 4}
subset1 = {1}
subset2 = {3, 4}
subset3 = {4, 3, 2, 1} 

The symbol for subset is \(\{1\} \subset \{1, 2\}\).

The empty set is a subset of all sets, but it is not an element of all sets.

Fun fact, we can do this:

$$ \mathbb{U} -  \varnothing$$

This equates to a new set, which contains all the elements of the set apart from the empty set. However, it is not the universal set - it’s a new set!

The power in subsets, in my opinion, comes from the power set.

🔋 Power Set

The Power set is the set of all subsets of a set, including the empty set and the set itself. For the set {2, 9} we have 4 subsets.

{}
{2}
{9}
{2, 9}

The power set will be:

$$\frak{P} (\mathbb{A}) = \emptyset, \{2\}, \{9\}, \{2, 9\}$$

Note: For home use or exams we can denote using P(a). For websites where we want to impress people with our fancy use of the alphabet, use LaTeX.

When building subsets, the element can either be included in the subset or not. This is binary. It’s either in it, or it isn’t.

That leads us to the formula for calculating how large a powerset is.

$$2^{s}$$

Where s is the size of the set and 2 is because elements are either in the set or not.

Let’s say we have a list of ingredients.

{cabbage, lettuce, tomato, chips, carrots}

It makes sense to use a set because the order doesn’t matter for a list of ingredients and we don’t want to have cabbage twice for some reason.

Now, how many combinations of food can we make with this?

$$2^{35} = 32$$

The empty set doesn’t count here (unless we want to starve), so we can reduce this to 31.

🥺 Infographic Cheat Sheet for Set Theory

I made this for you! Feel free to print and use it however you want. Personally, when I was studying for exams, the symbols section proved to be most useful!

💻 Sets in Programming Languages Are Often Sorted

Not only do sets in most programming languages are often automatically sorted. Take a look at this Python code:

>>> x = [9, 8, 7, 6, 5, 4, 3, 2, 1]
>>> set(x)
{1, 2, 3, 4, 5, 6, 7, 8, 9}

And that’s just the tip of the iceberg. Sets are implemented as hash maps in many programming languages. This means that we get O(1) lookup time. To perform 6 in x will take O(1) time. For more on Big O notation, check out my other article.

📖 Dictionary Checking

We have a text such as:

text = ["hello", "my", "name", "is", "lkmxjja", "brandon"]

And we want to find out how many words in text appear in another list, text_dict.

text_dict = ["hello", "hello", "my", "brandon", "name"]

The quickest way to do this without using sets is to sort both lists and then go through each one, one at a time to count how many times an item in text appears in text_dict.

In a real-world example, we could be checking to see if a text is English or not by counting how many times the words in the text appear in the English dictionary.

By using sets, we delete the repetitions in text_dict. It also automatically sorts the two sets, so it is much easier for us to search through them. Not to mention the O(1) lookup time.

3 birds with 1 stone!

>>> text = ["hello", "my", "name", "is", "lkmxjja", "brandon"]
>>> text_dict = ["hello", "hello", "my", "brandon", "name"]
>>> text = set(text)
>>> text_dict = set(text_dict)
>>> text.intersection(text_dict)
{'brandon', 'name', 'hello', 'my'}
>>> len(text.intersection(text_dict))
4

👋 Conclusion

Set theory is gnarly, and incredibly useful in not just competitive programming but all kinds of programming. We’ve not only learnt the theory behind set theory but also how programming languages such as Python have implemented it.

However, looping through both of them ourselves is unruly. We’d have to write a loop and keep track of it ourselves. Luckily, we can use set theories' intersection function to do this for us.

Fancy watching this as a video instead? Click below:

Introduction

I have around ~10k GitHub stars. I’ve come up with a bullet-pointed actionable list of how to make open-source projects popular.

One of the projects I created had 67 lines of code and had only existed for 3 days before it hit 1.7k stars.

Humans are predictable creatures when it comes to our attention. I’ll show you data-backed actionable insights that can help you create popular software.

Why Bother? Popular Projects = More Contributors = Better Project

What’s the point in getting more GitHub stars? They mean nothing. You can’t buy a coffee with exposure. If GitHub dies, so do the stars.

The problem with open source is the network effect. The more people that find your project, the more people that use it, the more that contribute to it and thus the better it becomes.

The better the project, the more popular it becomes. It’s a self-fulfilling cycle.

As this cycle continues, it becomes harder for it to continue. That’s a blog post for another day. But first, let’s talk about where we start.

To start us on this cycle we need popularity.

To get contributors to your project it has to be popular enough so people see it and contribute.

Creating a popular open-source project isn’t just a want but a need.

If a project has contributors but no popularity, it’s likely created by a company for internal use and was open-sourced.

Otherwise, only popular open-source projects have contributors.

Well Designed README

README.md is the first thing anyone sees. Make sure to catch their eyes right away.

It’s harder to gain traction based purely on the merit of the tool rather than on the presentation of the tool.

For frontend applications, you should focus more on the design of the frontend rather than the README. This is for CLI applications.

A well-designed README answers these questions succinctly:

• What does this do?
• Does it solve my problem?
• Does it solve my problem better than the competitors (if they exist) do?
• How do I install it?
• What are the basic commands I need to know?
• Where can I go for more help?

This is how a README answers these questions.

We’ll go through each of these.

Create a Header Summarising Your Project

The first thing they see is your README. The first thing they see on the README is the header. Make it good.

The header is the combination of:

• Logo
• Slogan (short description)
• Badges
• Quick Install
• Quick Links (not always needed)

Beautiful Logo as simple as Canva.com

The logo is the first thing users see and is the image used for social media sharing. When I first create a project, I’ll use something from Canva.

Canva allows you to quickly create a logo from a template for free.

Go to Canva and search for “Logo”

And then just select one of the many logos you come across. Edit it if you want.

Typically, there are 2 things I look for in a logo:

• Coolness factor 😎
• Slogan

I should look at the logo and think ”wow, that’s cool”.

It’s a gif! Isn’t that cool? I made it on Canva in about ~45 seconds. ~30 seconds were spent searching for it!

Secondly, the slogan. The first thing people see will be the logo which contains the name and slogan, instantly they will know what the project is about.

For some of my larger projects, I hire a designer, specifically Varg. Designers are great! Especially ones that can understand the project at hand, which aids in creating a well-conceived logo.

In short: don’t spend too long picking a logo. If you’re not hiring a designer, perhaps ~5 minutes playing around on Canva.

Slogan (description) of your project in 1 simple line

When thinking about the design of your project, think about how people found it. There are 2 major ways people can find your project:

1. Someone recommends it to them.
2. It’s posted on Twitter / HackerNews / LinkedIn / other social media or news aggregators.

When someone recommends something it’s because that something solves their problem. This means that they already have an idea of how this project solves their problem, of what the project does.

When posted, Twitter will make a social card for it. This card is the title, description, and image.

Both of the main methods of sharing your project include a description already. This means 2 things:

1. We don’t need to spend time describing what our project is in the README.
2. GitHub’s Description will be used everywhere and is the first thing people see.

One sentence or two will be adequate to explain our project in the README.

This is why I include the quick install section in the README. Users who come to your project already have an idea of what it is. Since they do, provide a way for them to quickly install it and try it out for themselves.

“Talk is cheap. Show me the code.” - Linus Torvalds

Good descriptions are hard to write. Very hard.

It needs to:

• Describe the project.
• Be eye-catching.
• Show why the user needs it.
• Show why it’s better than the rest.
• Be easy enough for someone that only knows the subject matter in passing to understand.

This is copywriting. It’s an important skill to learn as copywriting is:

Writing in such a way to convince someone to do something.

My favourite resource is Brian Dean’s Copywriting Guide.

GitHub - gohugoio/hugo: The world’s fastest framework for building websites.

The world’s fastest framework for building websites. - GitHub - gohugoio/hugo: The world’s fastest framework for building websites.

GitHubgohugoio

The world’s fastest framework for building websites.

This explains what the project is well. It is:

• Succinct.
• Answers the question “Why are you better than the rest?” with ”world’s fastest”.
• Answers what it does, ”framework for building websites.”
• Easy enough to understand for non-experts, ”building websites”.
• Uses eye-catching words such as ”worlds largest” and the succinctness imply “we can read this, it’ll only take a second of our time to process this.”

You should spend a few weeks experimenting with the description on-and-off.

Come up with many descriptions, about ~20. And continually improve upon it. When you lie down in bed, think ”If I had never seen my project before, what would I want to see to make me use it?”.

The description is the hardest, but most important part of the whole design. It’s the first thing people see. Invest time into this. Learn copywriting. Even when you think it’s perfect, it can always be improved.

Ask your users what they think of it. Iterate until you can no longer iterate.

Badges

Badges are links/images that sum up the project.

They explain where to find documentation, is the current branch stable? How clean is the code?

How active is the project? How many downloads? The license? Any chatrooms? Mostly, badges are just cool stickers you can include. I like reading them, but some people may not. You can find a list of badges on shields.io.

Quick Installation guide

The user understands what the application does from seeing it in the social cards or being told by a friend.

Sometimes, they want to install it as fast as possible to play around.

“Talk is cheap, show me the code.” - Linus Torvalds

The quick install guide allows users to install the software immediately.

Users do not need to scour the README for information on installation if they are already knowledgeable and want to use the project.

The style above is clean. The package manager’s name, the logo of the operating system and a short installation to copy/paste.

Quick Links

This isn’t required in all READMEs.

Linking to all the resources the user needs in one neat place allows the user to quickly understand anything they want.

The order of these matters. As the user reads left-to-right (assuming English README), the further away items are the less likely they will see it. You want them to see your Twitter first? Include that at the first item.

While this is a flat list separated by pipes, it is an ordered list in the sense that users will only read so far.

I include my quick links at the top of the page, above the fold (the logo).

The user will already have a rough idea of what the project is. They may only want 3 things from the README:

1. Documentation.
2. Support (the Discord link).
3. The Installation Guide.

By being at the top, we reduce the friction of finding them.

Example Images to show off your project

The header is also a great place to show how your project works. You can use gifs (discussed later in more depth) or images.

This depends on your project, but having images in your header may make sense.

Inspiration for designing your header Let’s look at some inspiration

What Is This? Describing Your Project Succinctly.

This section explains the features of your product.

Short explanations. A gif that demonstrates your project. Essential features you think someone would want to see.

Look at the Starship prompt.

They have a table with 2 columns but without borders. In the left column is the list of essential features. Each feature is bolded with a short explanation.

• Bold feature: I am explaining the feature

And in the right column is a gif showing how the program works, preferably detailing the features mentioned.

To create a gif of a CLI app, use Terminalizer. Clean up your terminal before you record, as it can look messy.

You can also use Asciienma:

1. Install asciinema and svg-term-cli.

2. Record with asciinema:

asciinema rec demo.cast

This records the session in the asciicast v2 plaintext file format.

3. Convert the .cast file to .svg with svg-term-cli:

svg-term --in demo.cast --out demo.svg --window --width 80 --height 22 --no-optimize

You probably want to play around with width and height. --window adds a fake OS window around the terminal session. I found that no-optimize fixed some weird font rendering issues on my macOS.

When thinking of what features to show, do not show them all. Only show the features that the user wants to see. And in words that a user can understand.

X vs Y, Comparisons With Competitors

If your project is competing with a lot of other projects, you’re going to need to show the user exactly why they should use your project over the competitors.

Convincing someone to leave their current tool for yours is hard. Make it as easy as possible for them to see the advantages over their current tooling.

In The Lean Startup the author talks about why at the beginning of a startup we should focus on the early adopters over the average customers.

“The point is not to find the average customer but to find early adopters: the customers who feel the need for the product most acutely. Those customers tend to be more forgiving of mistakes and are especially eager to give feedback.”

The early adopters are those that wouldn’t mind switching out their current tooling for a less tested, less mainstream option if it means it has better functionality.

The only way to get the average customer to use your product is:

• No competitors must exist.
• Their current solution to the problem is extremely convoluted compared to yours.

Otherwise, your best bet is to appeal to the early adopters and overtime slowly appeal to the average customer as your project becomes more mainstream.

The easiest way to compare your projects to others is to include a table of popular features. Use statistics here. It’s harder to believe words than it is numbers, even if the words are just as truthful as the numbers.

For Ciphey we compared our program to our largest possible competitor, CyberChef’s Magic function.

You can see we used gifs to demonstrate this. We explain how long each one takes and the setup of both, which can all be seen in the gifs.

We also leave footnotes on some things. Such as gifs loading at different times, the function (at the time) failing to decode.

Later on, we compare again with a table this time of features.

Create Great Documentation

Do not put all your documentation into your README because:

• It’s harder to update.
• It’s harder for users to find things.
• It makes the README unbearably long and ugly.

We don’t write all of our code in one file, why have all of our documentation in our README?

Don’t make the documentation section long. Since we have already explained how to install it quickly, we should show:

• How to run the program.
• How to find the documentation.
• How to find support.

I included a gif here showing all the different ways there are to run Ciphey. Gifs are magical and easy to make.

Contributing, Thanking & Welcoming Contributors

The final section is about contributing.

1. How to contribute.
2. Thanking past contributors.

We need contributors to our project to fulfil the cycle.

Therefore, our README needs to display how to contribute.

A short paragraph describing how to contribute, where to ask for help if they are stuck, the contributing.md file and any potential rewards for contributing (name added to the README and the chance to work on a growing project).

And then you want to thank your contributors. We use all-contributors which makes it easy to thank them. It shows their profile picture, a link to their websites along with emoji defining what they did.

Conclusion of Designing the README

Design is subjective and you may like something, or you may not. It’s down to you to decide on what looks good.

I hope the design principles I shared, along with the READMEs included here will inspire you to create something beautiful.

One thing I didn’t talk about here is creating documentation. It is your job as a programmer to create documentation. Your project is not done until it has documentation. You can use GitHub Wiki and DocStrings to automatically generate some documentation (you’ll still need to write documentation for installation, usage, etc).

Remember — the README is one of the most important parts of an open-source project (along with the documentation).

Creating Something People Want

A good README will get people interested, and a working project that solves their problems will get people talking.

This chapter is based on Zero to One by Peter Thiel, but will feature inspiration from other places.

“Every moment in business happens only once. The next Bill Gates will not build an operating system. The next Larry Page or Sergey Brin won’t make a search engine. And the next Mark Zuckerberg won’t create a social network. If you are copying these guys, you aren’t learning from them.”

Problem First, Product Second

For your project to grow, it has to solve a problem. It’s better to find a solution to a problem that people have rather than create a project for the sake of it.

Let’s compare 2 ideas.

1. A recipe app
2. A digital platform for artists to share their work, get feedback and start selling to gallery owners.

The first one doesn’t solve any problems. There are millions of recipe apps in the world and unless there is something truly unique it won’t take off.

The second one is a unique & novel idea that aims to solve the problem of:

“I’m an artist wanting to get paid for my work and improve.”

We have a problem, artists not getting paid, and we solve the problem.

Some people come up with the project first, but doing this means:

• We aren’t solving one specific problem from the start.
• We don’t have a well-defined target market.
• It’s likely already been done before.

As Walter Isaacson said in The Innovators:

“But the main lesson to draw from the birth of computers is that innovation is usually a group effort, involving collaboration between visionaries and engineers and that creativity comes from drawing on many sources. Only in storybooks do inventions come like a thunderbolt, or a lightbulb popping out of the head of a lone individual in a basement or garret or garage.”

It’s unlikely for our project to be innovative if we don’t solve a small problem first. In the same book, Isaacson says:

“Progress comes not only in great leaps but also from hundreds of small steps.”

Solving the problem will bring us closer to a unique & novel project.

Living With the Problem

You cannot solve a problem you do not have. In The Lean Startup, Eric Ries states:

“In my Toyota interviews, when I asked what distinguishes the Toyota Way from other management approaches, the most common first response was genchi gembutsu—whether I was in manufacturing, product development, sales, distribution, or public affairs. You cannot be sure you really understand any part of any business problem unless you go and see for yourself firsthand. It is unacceptable to take anything for granted or to rely on the reports of others.”

Unless you have the problem, you cannot effectively solve the problem.

It also helps with idea generation. Pay attention to the minor inconveniences in your life, in the lives of people around you and build products that solve those problems.

It’s a lot easier to observe the problems present in your own life than it is to generate random ideas that might work.

If you have a problem, you know 2 things:

1. The problem exists.
2. Other people have the problem.

The first point is important. Many people create solutions for problems that do not exist.

This product essentially injects the potato with oil and other foods. This problem does not exist. No one has ever had this problem. If you watch the video, you can see that the Potato Doctor cuts the potato open. What is the point? There isn’t one.

The second point is less obvious, but a good indicator. Humans are not unique. We mostly share the same problems. If the problem directly affects my life, I know that it must affect other people too.

Finding Problems in Communities

You don’t have to be the one to find the problem, others can too. If you pay attention to a community, these people will reveal the problems they are facing.

Listening to a community exponentially grows your rate of ideas vs being on your own.

The more people there are, the more you listen, the more ideas you can generate over time compared to thinking on your own.

Build a minimal viable product that solves the problem the community is facing.

A minimum viable product, or MVP, is a product with enough features to attract early-adopter customers and validate a product idea early in the product development cycle.

Share with the community. Measure its effectiveness, learn how to do better and re-build it (or add more) to improve upon it.

Over time, it will eventually leak out of the community into other similar communities.

You have around 2 weeks before you lose motivation to work on something. Create the smallest possible minimum viable product that the community can use. Their thanks, if provided, will give you the motivation to continue working on it.

Solving the Problem Well

Here’s the thing.

• You have a problem you can solve.
• You have a community that’ll help you solve this problem and provides feedback.

But that doesn’t mean your problem is solved well. Take a look at Juicero. Juicero solved a problem that many people have.

We want to create our juice drinks, but to do that we have to:

• Buy Fruit & Vegetables.
• Wash them.
• Cut them.
• Juice them.
• Clean up.

Juicero’s solution was to (ignoring hardware):

• Insert packet into Juicero to get the juice.

This is a good idea, but it was poorly executed.

There are many talks about why Juicero failed — all out of the scope of this article.

The point is that you could have a great idea, but if it’s poorly executed it may have too many downsides to be used as the solution.

The way to solve this is via the minimum viable product loop. Instead of spending 3 years creating a project, we release it as soon as possible, gather feedback, improve and loop.

We are continuously heading towards what people want, and each iteration will solve the problem better than the last. If it doesn’t, the next iteration we solve the problem differently and so on.

Getting the Word Out

If we never show off our project, why would we expect anyone to see it? It’s not good enough to build it and hope they come. We have to get the word out.

The good news is that if you’ve been following along in Creating Something People Want we already have the word out. The community we are in know about the project and use it.

That helps us immensely. Going from 10 GitHub stars to 100 is easy. Going from 0 to 1 is hard.

Once we get a few stars we will get more stars. Stars beget stars ⭐.

Sharing With a Community

If we have been following the Build, Measure, Learn loop and regularly publishing minimal viable products then we will already have the word out in our community.

When it comes time to publish, make sure your community knows that it’s the first real release. They’d be more likely to share with their friends this way.

News Aggregators

Your next port of call is news aggregators. These are places that collate news. You should post to:

• Subreddit of your choosing.
• HackerNews.
• Lobste.rs.

Do not read the comments. Those places are incredibly toxic and can’t see a good product even if it hit them in the face.

Awesome Lists

An Awesome list is a list of awesome things about some topic. There are lists such as:

• Rust
• Python
• Hacking
• Web

And more.

Find some lists that apply to you and submit PRs. In the worst case, they don’t accept it.

GitHub Trending

If all goes well, you should hit GitHub trending at some point. This will provide monumental traffic.

Once you hit trending, pay attention to social media and thank anyone that shares your project. If they follow you they may re-tweet your project again in the future.

This is the snowball effect. You need about ~50 stars to hit the trending page for your language, ~100 stars to hit the overall trending. Once you do this, trending will give you more stars and it will continually snowball.

Leverage an Existing Following or Past Popularity

The easiest way to gain stars is by leveraging your existing following. Post on social media, other GitHub repos and the likes.

Conclusion - Throw the Rule Book Away

Like all things, this is not an exact science, more like art. And you can’t become good at art by following other people's guidance. You’ve got to discover your unique style.

The Mona Lisa was painted once, but the thousands of people that painted the Mona Lisa afterwards were never recognised.

I suggest you throw some of the rules away, and experiment yourself. Create new rules and understand what works for you.

What works for me, won’t necessarily work for you. So go ahead, throw the rule book away!

Let’s go over some things we learnt.

• Well-designed READMEs are essential.
• Creating something people want.
• Get the word out there.
• Discover your unique style and what works for you.

I recently went through the trouble of distributing a Rust package. I wished that there was a simple guide on distributing one package to many platforms, so I wrote this guide.

Follow me as we publish my package, RustScan, to multiple distributions.

Semantic Versioning

Semantic Versioning is a system defining how to write version numbers. The 3 numbers are:

Major.Minor.Bugs

If you have fixed some bugs, increment the bugs counter.

If you have added a minor feature, increment the minor counter.

If you have done something major, increment the major counter.

We can signify whether a release is still being rested or not by adding “rc” (release candidate) to the end of the version. “5.0.0rc1” signifies “release candidate 1” which means this is the first public testing release of version 5.0.0.

Cargo

Cargo is a package registry system for Rust. Imagine it as PyPi (Pip for Python) or NPM (for JavaScript).

As a rustacean, you may have heard of this – and even used it to download packages yourself. So let’s skip right to the good part.

Before publishing to Cargo, we need to make sure our cargo.toml file has the required information.

There are 3 things we need:

• Name

The name of our project.

• Description

Describe what the project does.

• License

What license do you use? Specifically, we need to use a license identification code. View the Linux Foundation’s SPDX website for all the license identification codes.

However, you will probably want more than these for your package. Some good ones are:

• Readme

The location of your README file, which is used to fill out the README on the Cargo website.

• Keywords

These are tags for your project. When a user searches a keyword such as “sewing”, and your project has that keyword, your project will come up in the search results.

This is RustScan’sCargo.toml:

[package]
name = "rustscan"
version = "1.0.1"
authors = ["Autumn <my_email@skerritt.blog>"]
edition = "2018"
description = "Faster Nmap Scanning with Rust"
homepage = "https://github.com/bee-san/rustscan"
repository = "https://github.com/bee-san/rustscan"
license = "MIT"
keywords = ["port", "scanning", "nmap"]
categories = ["command-line-utilities"]
readme="README.md"

For more information on the manifest file, look here:

The Manifest Format - The Cargo Book

The Cargo Book

Now we’re ready to publish! Go to the Crates.io website and register an account. Then, go into the settings and create a new API key.

Now in a terminal, execute cargo login <API_KEY>. You’re now logged into Crates.io and can publish!

Build your Rust package using the release profile, which optimises it at the highest level Rust can provide:

cargo build --release

And then publish it.

cargo publish

Ta-da! Your package is now available on the Crates.io website, and can be installed with cargo <your_package_name>.

Windows (or any platform with binaries)

You can use Cargo Dist for this:

GitHub - axodotdev/cargo-dist: 📦 shippable application packaging for Rust

📦 shippable application packaging for Rust. Contribute to axodotdev/cargo-dist development by creating an account on GitHub.

GitHubaxodotdev

You can generate the CI using:

cargo dist init --ci=github

This creates a bunch of files (see pull request below)

Implement cargo dist by SkeletalDemise · Pull Request #226 · bee-san/Ares

Generated cargo dist workflow using cargo dist init --ci=github The workflow will draft a new release and automatically add binaries to it whenever we make a new GitHub tag that looks like a versi…

GitHubbee-san

It works, and it makes binaries for all of the major operating systems.

Homebrew

Homebrew is a package manager used by Mac OS users but can is also used on Linux.

Unfortunately, I found the documentation to be lacklustre in explaining how to get a package into Homebrew.

Let’s assume we are using GitHub to store our code.

Homebrew expects an TAR archive. To get this, we create a new release on GitHub.

On the GitHub repo’s homepage, click “Releases” on the right-hand side menu.

You should be taken to this page. Click “Draft a new release”.

Now create a new release.

Use semantic versioning to create the Tag Version. Create a new release title, and describe the release.

A good format for release descriptions is:

# Features

# Maintenance

# Bugs

Similar to the semantic versioning rules. I normally pull these from pull requests, or write them down as I merge commits.

Once we’ve entered some information, click Publish release. We now have a published release of our app!

Our code is now in .tar.gz format if we look on the releases page again. GitHub does it for us!

Right click Source code (tar.gz) and click on “get link”. Now we have the link to our tar.gz folder.

Go into a terminal, and type:

wget <link>

where <link> is replaced by the link you just copied.

We need the SHA256 Hash of the archive, so let’s calculate it:

shasum -a 256 rustscan.tar.gz

Where rustscan.tar.gz is the file you just downloaded with wget.

The GitHub Repository

Homebrew requires a separate GitHub repository for your project. Or you can change the name of your current repository.

Homebrew calls these taps. Taps are third-party GitHub repositories with specific names and configuration files.

Go to GitHub and create a new repository. Naming it:

homebrew-<project>

Where is the name of your project? Note it must start with the name “homebrew-".

In my case, it is:

homebrew-rustscan

GitHub - RustScan/homebrew-rustscan: RustScan’s HomeBrew repo

RustScan’s HomeBrew repo. Contribute to RustScan/homebrew-rustscan development by creating an account on GitHub.

GitHubRustScan

Now clone your new repo onto your machine:

git clone homebrew-<project>

Creating the formula

Homebrew requires a file called a formula. This is a Ruby file that details your project along with how to install the binary. You do not need to know Ruby to create this.

cd into our newly cloned repo, and create the following file structure:

- Formula/
    - <project>.rb

In my case:

- Formula/
    - rustscan.rb

Capitalise the folder name if it is not already.

Now copy and paste the following file into your rustscan.rb (or whatever your project is called).

# Documentation: https://docs.brew.sh/Formula-Cookbook
#                https://rubydoc.brew.sh/Formula
# PLEASE REMOVE ALL GENERATED COMMENTS BEFORE SUBMITTING YOUR PULL REQUEST!
class Rustscan < Formula
  desc "Faster Nmap Scanning with Rust" 
  homepage "https://github.com/bee-san/rustscan"
  url "https://github.com/RustScan/RustScan/archive/1.3.tar.gz"
  sha256 "3bbaf188fa4014a57596c4d4f928b75bdf42c058220424ae46b94f3a36b61f81"
  version "1.3.0"
  depends_on "rust" => :build

  def install
    system "cargo", "build", "--release", "--bin", "rustscan"
    bin.install "target/release/rustscan"
  end
end

Change the class name to match the name of your program:

class Rustscan < Formula

Then add a short description and link the homepage (in my case, the GitHub repo).

  desc "Faster Nmap Scanning with Rust" 
  homepage "https://github.com/bee-san/rustscan"

Now we need to fill out the download link and the SHA-256.

  url "https://github.com/RustScan/RustScan/archive/1.3.tar.gz"
  sha256 "3bbaf188fa4014a57596c4d4f928b75bdf42c058220424ae46b94f3a36b61f81"

Remember earlier when I told you to write down the link & the shasum? This is exactly where you’d place them!

Now insert your version number, the same one for the whole release:

version "1.3.0"

Our program relies on Rust to build the binary, we note this down here:

  depends_on "rust" => :build

The next step is to detail how to build the binary and install our program. We tell Homebrew to build the binary using cargo build, and then to install it with bin.install.

  def install
    system "cargo", "build", "--release", "--bin", "rustscan"
    bin.install "target/release/rustscan"
  end

And just like that, we’ve made the formula file.

Upload this to your homebrew-<project> repository like so:

git add .
git commit -m 'First release'
git push

Installing the Package

Let’s install the package to double check everything went well.

brew tap bee-san/rustscan 
brew install rustscan

Where bee-san/rustscan is your GitHub username combined with the project’s name.

My username is bee-san, and the project is called rustscan.

I created a one-command install for my users. which is just the 2 commands combined. You may find this helpful.

brew tap bee-san/rustscan && brew install rustscan

Debian

The easiest way to create Debian binaries is to use the crate cargo-deb. Cargo-deb is installed

cargo install cargo-deb

Once it is installed, run the command:

cargo-deb

And we now have a .deb file for our project on our system architecture.

But what if we wanted to package for other architectures?

Luckily I’ve created a (albeit badly made) Docker script to package for other architectures.

The script packages the project for:

• Amd64
• Arm64
• i386

It requires some editing (as it was made for RustScan), but once done it will automatically package your script for you.

Create a separate folder in your main project’s repo, such as rustscan-debbuilder.

Then place these 3 files in there:

entrypoint.sh

#!/bin/bash

cd /RustScan
git pull --force

#amd64
cargo deb

#arm64
rustup target add arm-unknown-linux-gnueabihf
cargo deb --target=arm-unknown-linux-gnueabihf

#i386
rustup target add i686-unknown-linux-gnu
cargo deb --target=i686-unknown-linux-gnu

find target/ -name \*.deb -exec cp {} /debs \;

Change cd /RustScan to your project name.

run.sh

#!/bin/bash
docker build -t rustscan-builder . || exit

# This creates a volume which binds your currentdirectory/debs to 
# the location where the deb files get spat out in the container.
# You don't need to worry about it. Just chmod +x run.sh && ./run.sh and
# you'll get yer .deb file in a few minutes. It runs faster after you've used it the first time.
docker run -v "$(pwd)/debs:/debs" rustscan-builder

Dockerfile

FROM rust:latest

RUN git clone https://github.com/bee-san/RustScan
WORKDIR "/RustScan"
RUN git pull --force
RUN cargo install cargo-deb

RUN apt update -y && apt upgrade -y
RUN apt install libc6-dev-i386 -y
RUN git clone --depth=1 https://github.com/raspberrypi/tools /raspberrypi-tools
ENV PATH=/raspberrypi-tools/arm-bcm2708/gcc-linaro-arm-linux-gnueabihf-raspbian-x64/bin/:$PATH
ENV CARGO_TARGET_ARM_UNKNOWN_LINUX_GNUEABIHF_LINKER=arm-linux-gnueabihf-gcc
RUN mkdir /root/.cargo
RUN echo "[target.arm-unknown-linux-gnueabihf]" >> /root/.cargo/config
RUN echo "strip = { path = \"arm-linux-gnueabihf-strip\" }" >> /root/.cargo/config
RUN echo "objcopy = { path = \"arm-linux-gnueabihf-objcopy\" }" >> /root/.cargo/config

COPY ./entrypoint.sh /entrypoint.sh
RUN chmod +x /entrypoint.sh
ENTRYPOINT ["/entrypoint.sh"]

Change RUN git clone [https://github.com/bee-sa/RustScan](https://github.com/bee-san/RustScan) to the git repository link of your choice.

Change WORKDIR "/RustScan to your project’s name.

The directory should look like:

- rustscan-debbuilder /
    Dockerfile
    run.sh
    entrypoint.sh

Now to run this builder:

cd rustscan-debbuilder
chmod +x run.sh
./run.sh

And it will build 3 Debian binaries for you.

Installation of .deb files

To install .deb files, you can run dpkg -i on the file, or you can double-click the file (on some systems).

Arch

The easiest way to distribute for AUR is to use the Cargo package cargo-aur.

The PKGBUILD file is similar to cargo.toml, or our Homebrew file.

Let’s open up the file and edit some fields (if we want to).

# Maintainer: Bee <bee@fake.com>
pkgname=rustscan
pkgver=1.4.1
pkgrel=1
pkgdesc="Faster Nmap Scanning with Rust"
url="https://github.com/bee-san/rustscan"
license=("MIT")
arch=("x86_64")
provides=("rustscan")
options=("strip")
source=("https://github.com/bee-san/rustscan/releases/download/v$pkgver/rustscan-$pkgver-x86_64.tar.gz")
sha256sums=("7bed834f5df925b720316341150df74ac2533cc968de54bb1164c95ea9b65db8")

package() {
    install -Dm755 rustscan -t "$pkgdir/usr/bin/"
}

The pkgname is the name of the package. Please see the Arch wiki for guidance on naming conventions.

pkgver is the semantic version of our package. This is automatically taken from cargo.toml.

pkgrel means “this package has updated”. Nothing more to it, but the Arch Wiki explains this concept in more detail.

pkgdesc is the description of our package.

arch is the architecture our package will compile on.

provides is an array of packages that the software provides the features are. Packages providing the same item can be installed side-by-side unless one of them has a conflicts array.

options per the Arch Wiki:

This array allows overriding some of the default behavior of makepkg, defined in /etc/makepkg.conf. To set an option, include the name in the array. To disable an option, place an ! before it.

Personally, I don’t know why this is needed. But it’s an automated generation, so we can’t complain too much.

source is the location of the release on GitHub, and sha256sums are the checksums of the package.

Finally, package() shows Arch how to install our package.

Uploading this package to the AUR

1. cargo aur built a tarball .tar file. Create a new release on GitHub and attach the .tar` file that was just created.
2. Create an account on the AUR https://aur.archlinux.org/
3. Upload your SSH public key to your account.

Check for SSH keys with:

ls -al ~/.ssh

And you’re likely looking for a file like *id_rsa.pub. *

If this doesn’t exist, generate a new SSH key with:

$ ssh-keygen -t rsa -b 4096 -C "your_email@example.com"

And follow the on-screen prompts. Or follow this guide if you are still confused.

Next, go to your account page on the AUR and upload your public SSH key.

1. In a new directory, git clone your repo on the AUR.

This is kind of confusing. But say the package name is rustscan (confirm there is no other package on the AUR using your projects name by searching here).

git clone ssh://aur@aur.archlinux.org/rustscan.git

I normally clone this in a folder format like:

- rustscan /
    - rustscan / # the rust package
    - rustscan / # the package we have git cloned
    - homebrew-rustscan /

Make sure to change the name of the package rustscan to the name you want.

1. Copy the PKGBUILD you built in stage 1 into the new Git repo.
2. Run makepkg --printsrcinfo > .SRCINFO in the repo.

Your directory should now look like:

• rustscan /
• rustscan / # the rust package
• rustscan / # the package we have git cloned
• PKGBUILD
• .SRCINFO
• homebrew-rustscan /

Now push these:

git add . git commit -m ‘initial release’ git push

And Ta-Da! We now have an Arch Linux AUR package!

Eventually, you may want to clean up the default Rust AUR package for whatever reason. This is the one RustScan uses. Feel free to copy & change it however you wish:

# Maintainer: Hao Last_name_emited_for_privacy <email_emited_for_privacy>

pkgname=rustscan
_pkgname=RustScan
pkgver=1.6.0
pkgrel=1
pkgdesc="Faster Nmap Scanning with Rust"
arch=("x86_64" "i686")
url="https://github.com/rustscan/RustScan"
license=("GPL3")
provides=('rustscan')
conflicts=('rustscan')
depends=("nmap")
makedepends=("cargo")
source=("${pkgname}-${pkgver}.tar.gz::${url}/archive/${pkgver}.tar.gz")
sha256sums=('a4ebe4b8eda88dd10d52d961578c95b5427cc34b3bf41e5df729a37122c68965')

build() {
  cd ${_pkgname}-${pkgver}
  cargo build --release --locked --all-features --target-dir=target
}

package() {
  cd ${_pkgname}-${pkgver}
  install -Dm755 target/release/${pkgname} ${pkgdir}/usr/bin/${pkgname}
}

Note: someone else made this for RustScan.

Often I’ll hear about how you can optimise a for loop to be faster or how switch statements are faster than if statements. Most computers have over 1 core, with the ability to support multiple threads. Before worrying about optimising for loops or if statements try to attack your problem from a different angle.

Divide and Conquer is one way to attack a problem from a different angle. Don’t worry if you have zero experience or knowledge on the topic. This article is designed to be read by someone with very little programming knowledge.

I will explain this using 3 examples. The first will be a simple explanation. The second will be some code. The final will get into the mathematical core of divide and conquer techniques. (Don’t worry, I hate maths too).

What Is Divide and Conquer? 🌎

Divide and conquer is where you divide a large problem up into many smaller, much easier-to-solve problems. The rather small example below illustrates this.

We take the equation “3 + 6 + 2 + 4” and cut it down into the smallest set of equations, which is [3 + 6, 2 + 4]. It could also be [2 + 3, 4 + 6]. The order doesn’t matter, as long as we turn this one long equation into many smaller equations.

Let’s say we have 8 numbers:

$$4+6+3+2+8+7+5+1$$

We want to add them all together. We first divide the problem into 8 equal sub-problems. We do this by breaking the addition up into individual numbers.

$$4 + 6 \; 3 + 2 \; 8 + 7 \; 5 + 1$$

We then add 2 numbers at a time.

Then 4 numbers into 8 numbers which is our resultant.

Why do we break it down to individual numbers at stage 1? Why don’t we just start from stage 2? Because while this list of numbers is even if the list was odd you would need to break it down to individual numbers to better handle it.

A divide and conquer algorithm tries to break a problem down into as many little chunks as possible since it is easier to solve with little chunks. It does this with recursion.

Recursion

Before we get into the rest of the article, let’s learn about recursion first.

Recursion is when a function calls itself. It’s a hard concept to understand if you’ve never heard of it before. This page provides a good explanation.

Matryoshka dolls are these cute little things:

We open up the bigger one and inside is a slightly smaller one. Inside that one is another slightly small doll. Let’s say, inside the last doll is a key. But we do not know how many dolls there are. How do we write a function that opens up the dolls until we find a key?

We could use a while loop, but recursion is preferred here.

To program this, we can write:

def getKey(doll):
    item = doll.open()
    if item == key:
        return key
    else:
        return getKey(item)
getKey(doll)

The function repeatedly calls itself until it finds a key, at which point it stops. The finding key point is called a break case or exit condition.

We always add a break case to a recursive function. If we didn’t, it’d just be an infinite loop! Never-ending.

Computer scientists love recursion. Because it’s so hard for normal people to understand, we have a schadenfreude sensation watching people struggle. Haha just kidding!

We love recursion because it’s used in maths all the time. Computer scientists are mathematicians first, and coders second. Anything that brings code closer to real-life mathematics is good.

Not just because some people love maths, but because it makes it easier to implement. Need to calculate the Fibonacci numbers? The maths equation for this is:

$$F(n) = \begin{cases} n, \text{If n = 0 or 1} \\ F(n - 1) + F(n - 2), \ \text{if n > 1} \end{cases}$$

A natural recurrence in our formula! Instead of translating it into loops, we can just calculate it:

def F(n):
    if n == 0 or n == 1:
        return n
    else:
        return F(n-1)+F(n-2)

This is one of the reasons why functional programming is so cool.

Also, as you’ll see throughout this article, recursion reads so much nicer than loops. And hey, maybe you can feel a little happier when your coworker doesn’t understand recursion but you do ;)

Back to Divide & Conquer

The technique, as defined in the famous Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, is:

1. Divide

If the problem is small, then solve it directly. Otherwise, divide the problem into smaller subsets of the same problem.

2. Conquer

Conquer the smaller problems by solving them recursively. If the sub-problems are small enough, recursion is not needed and you can solve them directly.

3. Combine

Take the solutions to the sub-problems and merge them into a solution to the original problem.

Let’s look at another example, calculating the factorial of a number.

n = 6

def recur_factorial(n):
    if n == 1:
        return n
    else:
        return n * recur_factorial(n-1)

print(recur_factorial(n))

With the code from above, some important things to note. The Divide part is also the recursion part. We divide the problem up at return n * recur_factorial(n-1).

The recur_factorial(n-1) part is where we divide the problem up.

The conquering part is the recursion part too, but also the if statement. If the problem is small enough, we solve it directly (by returning n). Else, we perform return n * recur_factorial(n-1).

Combine. We do this with the multiplication symbol. Eventually, we return the factorial of the number. If we didn’t have the symbol there, and it was return recur_factorial(n-1) it wouldn’t combine and it wouldn’t output anything similar to the factorial. (It’ll output 1, for those interested).

We’ll explore how to divide and conquer works in some famous algorithms, Merge Sort and the solution to the Towers of Hanoi.

One last time

1. Divide / Break. Break the problem into smaller sub-problems.
2. Conquer / Solve. Solves all the sub-problems.
3. Merge / Combine. Merges all the sub-solutions into one solution.

Merge Sort 🤖

Merge Sort is a sorting algorithm. The algorithm works as follows:

• Divide the sequence of n numbers into 2 halves
• Recursively sort the two halves
• Merge the two sorted halves into a single sorted sequence

In this image, we break down the 8 numbers into separate digits. Just like we did earlier. Once we’ve done this, we can begin the sorting process.

It compares 51 and 13. Since 13 is smaller, it puts it on the left-hand side. It does this for (10, 64), (34, 5), (32, 21).

It then merges (13, 51) with (10, 64). It knows that 13 is the smallest in the first list, and 10 is the smallest in the right list. 10 is smaller than 13, therefore we don’t need to compare 13 to 64. We’re comparing & merging two **sorted **lists.

In recursion, we use the term base case to refer to the absolute smallest value we can deal with. With Merge Sort, the base case is 1. That means we split the list up until we get sub-lists of length 1. That’s also why we go down all the way to 1 and not 2. If the base case was 2, we would stop at the 2 numbers.

If the length of the list (n) is larger than 1, then we divide the list and each sub-list by 2 until we get sub-lists of size 1. If n = 1, the list is already sorted so we do nothing.

Merge Sort is an example of a divide-and-conquer algorithm. Let’s look at one more algorithm to understand how divide and conquer works.

Towers of Hanoi 🗼

The Towers of Hanoi is a mathematical problem which compromises 3 pegs and 3 discs. This problem is mostly used to teach recursion, but it has some real-world uses. The number of pegs & discs can change.

Each disc is a different size. We want to move all discs to peg C so that the largest is on the bottom, the second largest on top of the largest, third largest (smallest) on top of all of them. There are some rules to this game:

1. We can only move 1 disc at a time.
2. A disc cannot be placed on top of other discs that are smaller than it.

We want to use the smallest number of moves possible. If we have 1 disc, we only need to move it once. For 2 discs, we need to move it 3 times.

The number of moves is a power of 2 minus 1. Say we have 4 discs, we calculate the minimum number of moves as \(2^4 = 16 - 1 = 15\).

To solve the above example we want to store the smallest disc in a buffer peg (1 move). See below for a gif on solving Tower of Hanoi with 3 pegs and 3 discs.

Notice how we need to have a buffer to store the discs.

We can generalise this problem. If we have n discs: move n-1 from A to B recursively, move largest from A to C, and move n-1 from B to C recursively.

If there is an even number of pieces the first move is always into the middle. If it is odd the first move is always to the other end.

Let’s code the algorithm for ToH, in pseudocode.

function MoveTower(disk, source, dest, spare):
    if disk == 0, then:
        move disk from source to dest

We start with a base case, disk == 0. source is the peg you’re starting at. dest is the final destination peg. spare is the spare peg.

FUNCTION MoveTower(disk, source, dest, spare):
IF disk == 0, THEN:
    move disk from source to dest
ELSE:
    MoveTower(disk - 1, source, spare, dest)   // Step 1
    move disk from source to dest              // Step 2
    MoveTower(disk - 1, spare, dest, source)   // Step 3
END IF

Notice that with step 1 we switch dest and source. We do not do this for step 3.

With recursion, we know 2 things:

1. It always has a base case (if it doesn’t, how does the algorithm know to end?)
2. The function calls itself.

The algorithm gets a little confusing with steps 1 and 3. They both call the same function. This is where multi-threading comes in. You can run steps 1 and 3 on different threads - at the same time.

Since 2 is more than 1, we move it down one more level again. So far you’ve seen what the divide and conquer technique is. You should understand how it works and what code looks like. Next, let’s learn how to define an algorithm to a problem using divide and conquer. This part is the most important. Once you know this, it’ll be easier to create divide and conquer algorithms.

How to identify Divide and Conquer problems

When we have a problem that looks similar to a famous divide & conquer algorithm (such as merge sort), it will be useful.

Most of the time, the algorithms we design will be most similar to merge sort. If we have an algorithm that takes a list and does something with each element of the list, it might be able to use divide & conquer.

For example, working out the largest item of a list. Given a list of words, how many times does the letter “e” appear?

If we have an algorithm that is slow and we would like to speed it up, one of our first options is divide and conquer.

There aren’t any obvious tell-tale signs other than “similar to a famous example”. But as we’ll see in the next section, we can check if it is solvable using divide & conquer.

How to solve problems using divide and conquer

Now we know how divide and conquer algorithms work, we can build up our own solution. In this example, we’ll walk through how to build a solution to the Fibonacci numbers.

Fibonacci Numbers 🐰

We can find Fibonacci numbers in nature. The way rabbits produce is in the style of the Fibonacci numbers. You have 2 rabbits that make 3, 3 rabbits make 5, 5 rabbits make 9 and so on.

The numbers start at 0 and the next number is the current number + the previous number. But by mathematical definition, the first 2 numbers are 0 and 1.

Let’s say we want to find the 5 Fibonacci numbers. We can do this:

# [0, 1]
0 + 1 = 1 # 3rd fib number
# [0, 1, 1]
1 + 1 = 2 # 4th fib number
# [0, 1, 1, 2]
2 + 1 = 3 # 5th fib number
# [0, 1, 1, 2, 3]

Now the first thing when designing a divide and conquer algorithm is to design the recurrence. The recurrence always starts with a base case.

We can describe this relation using a recursion. A recurrence is an equation which defines a function in terms of its smaller inputs. Recurrence and recursion sound similar and are similar.

As we saw, our base case is the 2 numbers at the start.

def f(n):
    if n == 0 or n == 1:
        return n

To calculate the 4th Fibonacci number, we do (4 - 1) + (4 - 2). This means (last number in the sequence) + (the number before the last).  Or in other words:

The next number is the current number + the previous number.

If our number is not 0 or 1, we want to add the last 2 Fibonacci numbers together.

Let’s take a look at our table quickly:

# [0, 1]
0 + 1 = 1
# [0, 1, 1]
1 + 1 = 2 
# [0, 1, 1, 2]
2 + 1 = 3 
# [0, 1, 1, 2, 3]
2 + 3 = 5
# [0, 1, 1, 2, 3, 5]

But what if we don’t have this list stored? How do we calculate the 6th number without creating a list at all? Well we know that the 6th number is the 5th number + the 4th number. Okay, what are those? The 5th number is the 4th number + the 3rd number. The 4th number is the 3rd number + the second number.

We know that the second number is always 1, as we’ve reached a base case.

Eventually, we break it down to the base cases. Okay, so we know our code calls itself to calculate the Fibonacci numbers of the previous ones:

def f(n):
    if n == 0 or n == 1:
        return n
    else:
        f(n-1) f(n-2)

Okay, how do we merge the Fibonacci numbers at the end? As we saw, it is the last number **added **to the current number.

def f(n):
    if n == 0 or n == 1:
        return n
    else:
        f(n-1) + f(n-2)

Now we’ve seen this, let’s turn it into recursion using a recurrence. Luckily for us, it’s incredibly easy to go from a recurrence to code or from code to a recurrence, as they are both recurrences!

$$ F(n) = \begin{cases} n, \text{If n = 0 or 1} \\  F(n - 1) + F(n - 2), \ \text{if n > 1} \end{cases} $$

We often calculate the result of a recurrence using an execution tree. We saw this earlier when exploring how to build it in code. For F(6) this looks like:

n is 4, and n is larger than 0 or 1. So we do f(n-1) + f(n-2). We ignore the addition for now. This results in 2 new nodes, 3 and 2. 3 is larger than 0 or 1 so we do the same. Same for 2. We do this until we get a bunch of nodes which are either 0 or 1.

We then add all the nodes together.

$$0 + 1 + 1 + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 0 + 1 = 8$$

When Should I Use Divide & Conquer? 🎇

When we have a problem that looks similar to a famous divide & conquer algorithm (such as merge sort), it will be useful.

Most of the time, the algorithms we design will be most similar to merge sort. If we have an algorithm that takes a list and does something with each element of the list, it might be able to use divide & conquer.

For example, working out the largest item of a list. Given a list of words, how many times does the letter “e” appear?

Big O Notation of Divide & Conquer Algorithms

Normally if our algorithm follows a famous divide & conquer (algorithm) we can infer our big o from that.

This is no different from calculating the big o notation of our own algorithms.

Divide & Conquer vs Dynamic Programming vs Greedy

Conclusion 📕

Once you’ve identified how to break a problem down into many smaller pieces, you can use concurrent programming to execute these pieces at the same time (on different threads) speeding up the whole algorithm.

Divide-and-conquer algorithms are one of the fastest and perhaps easiest ways to increase the speed of an algorithm and are useful in everyday programming. Here are the most important topics we covered in this article:

• What is divide and conquer?
• Recursion
• Merge sort
• Towers of Hanoi
• Coding a divide and conquer algorithm
• Recurrences
• Fibonacci numbers

The next step is to explore multi-threading. Choose your programming language of choice and Google, as an example, “Python multi-threading”. Figure out how it works and see if you can attack any problems in your own code from this new angle.

You can also learn about how to solve recurrences (finding out the asymptotic running time of a recurrence), which is the next article I’m going to write. If you don’t want to miss it, or you liked this article do consider subscribing to my email list 😁

I use RipGrep all the time, but sometimes when I want to do something I have to search the internet to find out.

GitHub - BurntSushi/ripgrep: ripgrep recursively searches directories for a regex pattern while respecting your gitignore

ripgrep recursively searches directories for a regex pattern while respecting your gitignore - GitHub - BurntSushi/ripgrep: ripgrep recursively searches directories for a regex pattern while respec…

GitHubBurntSushi

Well, no more! I made this cheatsheet for myself. Maybe it'll help you.

Ripgrep search for specific file types

Problem

You want to find out where the AWS ARN 123456789012 is used. You have a mono-repo with many file types in it. You're only interested in Terraform files.

Solution globbing for file types

rg '123456789012' -g '*.tf'

This globs through all files that end with .tf (the Terraform extension) for the ARN.

Problem

You want to search for the API endpoint "localhost:4531" through all Rust files.

Solution using Ripgrep's types

Ripgrep comes with a number of filetypes built in. You can do:

rg "localhost:4531" --type rust
# or more succinctly 
rg "localhost:4531" --trust

You can find the full list of file types with ripgrep --type-list.

Problem

You want to find where the ARN is used, but want to ignore all markdown files.

Solution using inverse type selection

rg '123456789012' --type-not markdown

Case insensitive

$ rg example

$ rg -i example
hello_blog
1:ExAmple

Regex support

Ripgrep supports regex search by default.

$ rg 'fast\w+' README.md
75:  faster than both. (N.B. It is not, strictly speaking, a "drop-in" replacement
119:### Is it really faster than everything else?

Literal string (no regex)

Ripgrep by default uses regex to search. Sometimes the word we want to find contains valid regex, so this is an issue.

$ rg 'hello*.'
hello_blog
3:hello.*
4:hello this is a test

We can search literally with:

$ rg -F 'hello.*'
hello_blog
3:hello.*

Show lines around the found text

Sometimes we want to search for something, and we'd like context on the found text in the file.

To find 1 line before our matched text:

$ rg "hello" -B 1
hello_blog
2-ThisIsATest
3:hello.*

To find 1 line after our matched text:

$ rg "hello" -A 1
hello_blog
3:hello.*
4-Disney

To find 1 line before and after our text:

$ rg "hello" -C 1
hello_blog
2-ThisIsATest
3:hello.*
4-Disney

Get statistics of a search

I use this to work out how much work it would be to go through my search.

So searching "crypto" would take a while. How about crypto in Python files? This helps me speed up finding things.

rg "crypto" --stats
.... (full output of the search)
1292 matches
1083 matched lines
232 files contained matches
36826 files searched
6296587 bytes printed
254562478 bytes searched
5.805867 seconds spent searching
1.559705 seconds

Exclude a directory

I do not want to search through our modules directory, only our code.

We can do this by:

$ rg crypto -g '!modules/' -g '!pypi/'

Find Files

Find all files that have the word "cluster" in them.

rg --files | rg cluster

By the end of this article, you’ll thoroughly understand Big O notation. You’ll also know how to use it in the real world, and even the mathematics behind it!

In computer science, time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.

Big O notation is a method for determining how fast an algorithm is. Using Big O notation, we can learn whether our algorithm is fast or slow. This knowledge lets us design better algorithms.

This article is written using agnostic Python. That means it will be easy to port the Big O notation code over to Java, or any other language. If the code isn’t agnostic, there’s Java code accompanying it.

❓ How Do We Measure How Long an Algorithm Takes to Run?

We could run an algorithm 10,000 times and measure the average time taken.

➜ python3 -m timeit '[print(x) for x in range(100)]'
100 loops, best of 3: 11.1 msec per loop 
➜ python3 -m timeit '[print(x) for x in range(10)]'
1000 loops, best of 3: 1.09 msec per loop
# We can see that the time per loop changes depending on the input!

Say we have an algorithm that takes a shopping list and prints out every item on the shopping list. If the shopping list has 3 items, it’ll execute quickly. If it has 10 billion items, it’ll take a long time.

What is the “perfect” input size to get the “perfect” measure of how long the algorithm takes?

Other things we need to consider:

• Different processor speeds exist.
• Languages matter. Assembly is faster than Scratch; how do we consider this?

For this reason, we use Big O (pronounced Big Oh) notation.

🤔 What Is Big O Notation?

Big O is a formal notation that describes the behaviour of a function when the argument tends towards the maximum input. It was invented by Paul Bachmann, Edmund Landau and others between 1894 and 1820s. Popularised in the 1970s by Donald Knuth. Big O takes the upper bound. The worst-case results in the worst execution of the algorithm. For our shopping list example, the worst-case is an infinite list.

Instead of saying the input is 10 billion, or infinite - we say the input is n size. The exact size of the input doesn’t matter, only how our algorithm performs with the worst input. We can still work out Big O without knowing the exact size of an input.

Big O is easy to read once we learn this table: The Big O Notation’s Order of Growth:

Where the further right they are, the longer it takes. n is the size of the input. Big O notation uses these functions to describe algorithm efficiency.

In our shopping list example, in the worst case of our algorithm, it prints out every item in the list sequentially. Since there are n items in the list, it takes O(n)O(n) polynomial time to complete the algorithm.

Other asymptotic (time-measuring) notations are:

Informally this is:

• Big Omega (best case)
• Big Theta (average case)
• Big O (worst case)

Let’s walk through every single column in our “The Big O Notation Table”.

🟢 Constant Time

No matter how many elements, it will always take x operations to perform. In this case, 2. Constant algorithms do not scale with the input size, they are constant no matter how big the input. An example of this is addition. 1+2 takes the same time as 500+700. They may take more physical time, but we do not add more steps in the algorithm for the addition of big numbers. The underlying algorithm doesn’t change at all.

We often see constant as O(1), but any number could be used and it would still be constant. We sometimes change the number to a 1, because it doesn’t matter at all about how many steps it takes. What matters is that it takes a constant number of steps.

Constant time is the fastest of all Big O time complexities. The formal definition of constant time is:

It is upper-bounded by a constant

An example is:

def OddOrEven(n):
    return "Even" if n % 2 else "Odd"

Or in Java:

boolean isEven(double num) { return ((num % 2) == 0); }

In most programming languages, all integers have limits. Primitive operations (such as modulo, %) are all upper-bounded by this limit. If we go over this limit, we get an overflow error.

Because of this upper-bound, it satisfies O(1).

🔵 Logarithmic Time

Here’s a quick explainer of what a logarithm is.

$$Log_{3}^{9}$$

What is being asked here is “3 to what power gives us 9?” This is 3 to the power of 2 gives us 9, so the whole expression looks like this:

$$Log_{3}^{9} = 2$$

A logarithmic algorithm halves the list every time it’s run.

Let’s look at binary search. Given the below-sorted list:

a = [1, 2, 3, 4, 5, 6 , 7, 8, 9, 10]

We want to find the number “2”.

We implement Binary Search as:

def binarySearch(alist, item):
    first = 0
    last = len(alist)-1
    found = False

    while first <= last and not found:
        midpoint = (first + last)//2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
            last = midpoint-1
            else:
                first = midpoint+1

    return found

In English, this is:

• Go to the middle of the list
• Check to see if that element is the answer
• If it’s not, check to see if that element is more than the item we want to find
• If it is, ignore the right-hand side (all the numbers higher than the midpoint) of the list and choose a new midpoint.
• Start over again, by finding the midpoint in the new list.

The algorithm halves the input every single time it iterates. Therefore it is logarithmic. Other examples include:

• Fibonacci number calculations
• Searching a Binary Search Tree
• Searching AVL trees

🟡 Linear Time

Linear time algorithms mean that every single element from the input is visited exactly once, O(n) times. As the size of the input, N, grows our algorithm’s run time scales exactly with the size of the input.

Linear running time algorithms are widespread. Linear runtime means that the program visits every element from the input. Linear time complexity O(n) means that as the input grows, the algorithms take proportionally longer to complete.2 Apr 2019

Remember our shopping list app from earlier? The algorithm ran in O(n) which is linear time!

Linear time is where every single item in a list is visited once, in a worst-case scenario.

To read out our shopping list, our algorithm has to read out each item. It can’t half the list, or add more items that we didn’t add. It has to list all n items, one at a time.

shopping_list = ["Bread", "Butter", "The Nacho Libre soundtrack from the 2006 film Nacho Libre", "Reusable Water Bottle"]
for item in shopping_list:
    print(item)

Let’s look at another example.

The largest item of an unsorted array

Given the list:

a = [2, 16, 7, 9, 8, 23, 12]

How do we work out what the largest item is?

We need to program it like this:

a = [2, 16, 7, 9, 8, 23, 12]
max_item = a[0]
for item in a:
    if item > max_item:
        max_item = item

We have to go through every item in the list, 1 by 1.

🔴 Polynomial Time

Notice how polynomial time dwarfs the others? Polynomial time is a polynomial function of the input. A polynomial function looks like n² or n³ and so on.

If one loop through a list is O(n), 2 loops must be O(n²). For each loop, we go over the list once. For each item in that list, we go over the entire list once. Resulting in n2 operations.

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for i in a:
    for x in a:
        print("x")

For each nesting on the same list, that adds an extra +1 to the powers.

A triple nested loop is O(n³).

Bubblesort is a good example of anO(n²) algorithm. The sorting algorithm takes the first number and swaps it with the adjacent number if they are in the wrong order. It does this for each number until all numbers are in the right order - and thus sorted.

def bubbleSort(arr):
    n = len(arr)
    
    # Traverse through all array elements
    for i in range(n):
    
        # Last i elements are already in place
        for j in range(0, n-i-1):
    
            # traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
    
# Driver code to test above
arr = [64, 34, 25, 12, 22, 11, 90]
    
bubbleSort(arr)

As a side note, my professor refers to any algorithm with a time of polynomial or above as:

A complete and utter disaster! This is a disaster! A catastrophe!

But the thing with large time complexities is that they often show us that something can be quickened.

For instance, a problem I had. Given a sentence, how many of those words appear in the English Dictionary? We can imagine the O(n²) method. One for loop through the sentence, another through the dictionary.

dictionary = ["a", "an"] # imagine if this was the dictionary
sentence = "hello uu988j my nadjjrjejas is brandon nanndwifjasj banana".split(" ")

counter = 0
for word in sentence:
    for item in dictionary:
        if word == item:
            counter = counter + 1

O(n²)! A disaster! But, knowing that this is a disaster means we can speed it up. Dictionaries are sorted by default. What if we sort our list of words in the sentence, and checked each word that way? We only need to loop through the dictionary once. And if the word we want to check is less than the word we’re on in the dictionary, we switch to the second word in the list.

Now our algorithm is O(n log n). We recognise that this isn’t a disaster, so we can move on! Knowing time complexities isn’t only useful in interviews. It’s an essential tool to improve our algorithms.

We can hasten many polynomial algorithms we construct using knowledge of algorithmic design.

❌ Exponential Time

Exponential time is 2ⁿ, where 2 depends on the permutations involved.

This algorithm is the slowest of them all. You saw how my professor reacted to polynomial algorithms. He was jumping up and down in furiosity at exponential algorithms!

Say we have a password consisting only of numbers (so that’s 10 numbers, 0 through to 9). we want to crack a password which has a length of n, so to brute force through every combination we’ll have 10ⁿ combinations to work through.

One example of exponential time is to find all the subsets of a set.

>>> subsets([''])
['']
>>> subsets(['x'])
['', 'x']
>>> subsets(['a', 'b'])
['', 'a', 'b', 'ab']

We can see that when we have an input size of 2, the output size is 22=422=4.

Now, let’s code up subsets.

from itertools import chain, combinations

def subsets(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

Taken from the documentation for itertools.

What’s important here is to see that it exponentially grows depending on the input size. Java code can be found here.

Exponential algorithms are horrific, but like polynomial algorithms we can learn a thing or two. Let’s say we have to calculate 10⁴. We need to do this:

$$10 * 10 * 10 * 10 = 10^2 * 10^2$$

We have to calculate 10² twice! What if we store that value somewhere and use it later so we do not have to recalculate it? This is the principle of Dynamic Programming, which you can read about here.

When we see an exponential algorithm, dynamic programming can often be used to speed it up.

Again, knowing time complexities allows us to build better algorithms.

Here’s our Big O notation graph where the numbers are reduced so we can see all the different lines.

😌 Simplifying Big O notation

Rarely will time complexity be as easy as counting how many for loops we have. What if our algorithm looks like \(O(n+n2)\)? We can simplify our algorithm using these simple rules:

Drop the constants

If we have an algorithm described as O(2n), we drop the 2 so it becomes O(n).

Drop the non-dominant terms

O(n²+n) becomes O(n²). Only keep the larger one in Big O.

If we have a sum such as O(b²+a) we can’t drop either without knowledge of what b and a are.

Is that it?

Yup! The hardest part is figuring out what our program’s complexity is first. Simplifying is the easy part! Just remember the golden rule of Big O notation:

“What is the worst-case scenario here?”

☁ Other Big O Times to Learn (But Not Essential)

🥇 O(n log n)

It falls between O(n) and O(n²). This is the fastest time possible for a comparison sort. We cannot get any faster unless we use some special property, like Radix sort. O(n log n) is the fastest comparison sort time.

It’s rather famous because Mergesort runs in O(n log n). Mergesort is a great algorithm not only because it sorts fast, but because the idea is used to build other algorithms.

Mergesort is used to teach divide & conquer algorithms. And for good reason, it’s a fantastic sorting algorithm that has roots outside of sorting.

Mergesort works by breaking down the list of numbers into individual numbers:

And then sorting each list, before merging them:

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] <= righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

Read more on Mergesort here.

👿 O(n!)

Notice the le10 at the top? This one is so large, it makes all other times look constant!

This time complexity is often used as a joke, referring to Bogo Sort. I have yet to find a real-life (not-a-joke) algorithm that runs in O(n!) that isn’t an algorithm calculating O(6!) or the likes.

🧮 How to Calculate Big O Notation for Our Own Algorithms with Examples

Our own algorithms will normally be based on some famous algorithm that already has a Big O notation. If it’s not, do not worry! Working out the Big O of our algorithm is easy.

Just think:

“What is the absolute worst input for my program?”

Take, for instance, a sequential searching algorithm.

def search(listInput, toFind):
    for counter, item in enumerate(listInput):
        if toFind == item:
            return (counter, item)
    return "did not find the item!"

The best input would be:

search(["apples"], "apples")

But the worst input is if the item was at the end of a long list.

search(["apples", "oranges", "The soundtrack from the 2006 film Nacho Libre", "Shrek"], "Shrek")

The worst-case scenario is O(n), because we have to go past every item in the list to find it.

What if our search algorithm was binary search? We learnt that binary search divides the list into half every time. This sounds like log n!

What if our binary search looks for an object, and then looks to find other similar objects?

# here we want to find the film shrek, find its IMDB rating and find other films with that IMDB rating. We are using binary search, then sequential search
toFind = {title: "Shrek", IMDBrating: None}
ret = search(toFind)
ret = search(ret['IMDBrating'])

We find Shrek with an IMDB score of 7.8. But we’re only sorted on the title, not the IMDB rating. We have to use a sequential search to find all other films with the same rating.

Binary search is O(log n) and sequential search is O(n), this makes our algorithm O(n log n). This isn’t a disaster, so we can be sure it’s not a terrible algorithm.

Even in instances where our algorithms are not strictly related to other algorithms, we can still compare them to things we know. O(log n) means halving. O(n2) means a nested for loop.

One last thing, we don’t always deal with n. Take this below algorithm:

x = [1, 2, 3, 4, 5]
y = [2, 6]
y = iter(y)
counter = 0
total = 0.0
while counter != len(x):
    # cycles through the y list.
    # multiplies 2 by 1, then 6 by 2. Then 2 by 3. 
    total = total + x[counter] * next(y)
    counter += 1
print(total)

We have 2 inputs, x and y. Our notation is then O(x + y). Sometimes we cannot make our notation smaller without knowing more about the data.

🤯 Big O Notation Cheat Sheet

I made this little infographic for you! The “add +1 for every nested for loop” depends on the for loop, as we saw earlier. But explaining that all over again would take up too much space 😅

🎓 How to Calculate Big O Notation of a Function (Discrete Maths)

Okay, this is where it gets hard. A lot of complaints against Big O notation is along the lines of:

“You didn’t really teach it, to really understand it you have to understand the maths!”

And I kinda agree. The surface-level knowledge above will be good for most interviews, but the stuff here is the stuff needed to master Big O notation.

Just as a reminder, we want to master asymptotic time complexity as it allows us to create better algorithms.

I’m going to be writing out the formal notation, and then explaining it simply. Over-simplification causes misinformation, so if you are studying for a test take your simplifications as generalities and not the truth. Mathematics is the whole truth, and you would be better off studying the maths rather than studying my simplifications. As I once read on the internet:

Shut up and calculate.

Is Big O Notation the Worst Case?

First things first, when I said:

Big O notation is the worst-case

That’s not true at all. It’s a white lie designed to help you learn the basics. Often used to get us to know enough to just pass interviews, but not enough to use it in the real world.

The formal definition of Big O notation is:

The upper-bounded time limit of the algorithm

Now, this often means “the worst-case” but not always. We can put upper bounds on whatever we want. But more often than not, we put upper bounds on the worst-case. In one of our examples, we’ll come across a weird formula where “the worst case” isn’t necessarily the one we choose for Big O.

This is an important distinction to make because some caveats will confuse us otherwise.

Given 2 positive functions, f(n) and g(n) we say f(n) is O(g(n)), written \(f(n) \in O(g(n))\), if there are constants c and n_0 such that:

$$f(n) \le c * g(n) \forall  \geq  n_o$$

Set Theory for Programmers

If you’ve spent time on HackerRank or LeetCode, you might have noticed most of the optimal solutions use Set Theory. By reading this article, you will gain a deeper knowledge into set theory and how to use it to create optimal algorithms. Set Theory was invented (or found, depending

Skerritt.blogAutumn Skerritt

Also, sometimes \(n_{0}\)​ is called k. But c stays the same.

This looks confusing but is just a fancy way of saying that the function (algorithm) is part of another function (the Big O notation used). Simplifying again: Our algorithm falls within the range of a Big O notation time complexity (O(n), O(log n), etc). So our algorithm is that time complexity (to simplify it).

Let’s see an example:

$$7n - 4 \in O(n)$$

Here we are claiming that 7n - 4 is in O(n) time. In formal Big O notation, we don't say it is that time. We say it falls within the range of that time.

We need to find constants c and n_0 such that \(7n-4 <= cn\) for all \(n >= n_{0}\). One choice is c = 7 and \(n_{o} = 1. 7 * 7 = 42 - 4 = 38\) and 7 * 1 = 7 so for all where n >= 7 this function holds true. This is just one of the many choices because any real number c >= 7 and any integer n_0 >= 1 would be okay. Another way to rephrase this is:

$$7n-4 \le 7n \; where \; n \geq 1$$

The left-hand side, 7n-4 is f(n). c = 10. g(n) = n. Therefore we can say f(n) =O(n) because g(n) = n. We say f(n) in O(n). All we have to do is substitute values into the formula until we find values for c and n that work. Let's do 10 examples now.

Example 1

$$f(n) = 4n^2 + 16n + 2$$

Is f(n) O(n4)?

We need to take this function:

$$f(n) = 4n^2 + 16n + 2$$

and say “is this less than some constant times n4?” We need to find out if there is such a constant.

$$n^2 + 16n + 2 \le n^4$$

Let’s do a chart. If n=0 we get:

$$0 + 0 + 2 = 2 \le 0$$

This isn’t true, so N = 0 is not true.

When n=1:

$$ 4 * 1 * 16 * 2 = 22 \le 1^4 = 22 \le 1$$

Is not true. Let’s try it again with n = 3.

$$50 \le 16$$

Not true, so let’s try another one. n=3.

$$86 \le 3^3 = 86 \le 81$$

Not true. Looks like the next one should work as we are approaching the tipping point. n=4.

$$ 130 \le 256$$

This is true. When n=4 or a greater number then this function where it’s less than N4 becomes True. When C=1, N≥4 this holds true.

The answer to the question “is this function, n2+16n+2n, Big O of n4 true?” Yes, when c=1 and n≥4.”

Note: I’m saying c=1 but I’m not writing \(c_n\) every time. Later on, using c will become important. But for these starter examples we’ll just assume c=1 until said otherwise.

Example 2

$$3n^2 + n + 16$$

Is this O(n²)?

We know that n <= n^2 for all n >= 1. Also, 16 <= n² for n >= 4.

So:

$$3n^2 + n + 16 \le 3n^2 + n^2 + n^2 = 5n^2$$

for all n >= 4. The constant C is 5, and n_0 = 3.

Example 3

$$13n^3 + 7n \log \; n + 3$$

is O(n³)

Because log n >= n² for all n >= 1, and for similar reasons as above we may conclude that: \(13n^3 + 6n ; n ; log ; n ; + 3 \le 21 n^3\) for all 'large enough' n. In this instance, c = 21.

Example 4

$$45n^5 - 10n^2 + 6n - 12$$

is O(n²)?

Any polynomial \(a_{k} n^k + ... + a_{2} n^2 + a_{1} n + a_{0}\) with \(a_{k} > 0\) is O(n^k).

Along the same lines, we can argue that any polynomial \(a_{k} n^k + ... + a_2 n^2 + a_1 n + a-0\) with \(a_k > 0\) is also O(n^j) for all j >= k. Therefore \(45n^5 - 10n^2 + 6n - 12\) is O(n²) (and is also O(n⁸) or O(n⁹) or O(n^k) for any n >= 5).

Example 5

$$\sqrt{n}$$

is O(n)?

This doesn't hold true. \(\sqrt{n} = n^{1/2}\). Therefore \(O(n^{1/2}) < O(n)\). I hope you appreciate the easy example to break up the hard maths 😉

Example 6

$$ 3 \log_{n} + \log \log n$$

is O(log n)?

First we have this equality that \(log n <= n\) for every n >= 1. We can put a double log here like so: \(log log n <= log n\). Log log n is smaller than log n. We replaced "n" with "log n" on both sides of log n <= n. So:

$$3 \; log \; n + \; log \; log \; n \le 4 \; log \; n$$

So:

$$c = 4, n_0 = 1$$

Example 7

$$log \; n$$

is \(log \; n < O(\sqrt{n})\)

Log n grows slower than any function where this holds:

\(log \ m \le m^\epsilon\) for every \(\epsilon > 0\) no matter how small it is, as long as it is positive.

Using this inequality if we plug in \(\epsilon = \frac{1}{2}\) and we plug that into our equation \(\sqrt{m} = m^{\frac{1}{2}}\).

Knowing that \(log \ m \le m^\epsilon\) we know that \(O(log \ n) < O(\sqrt{n})\)

Example 8

$$2n + 3$$

What is the Big O of this?

$$2n + 3 \le 10n, n  \geq 1$$

$$f(n) = O(n)$$.

This is because n is more than or equal to 1, it will always be larger than g(n) which is \(2n + 3\). Therefore, we have \(O(n)\).

Example 9

$$2n + 3 \le 10n$$

We don't have to write 10, it can be whatever we want so long as the equation holds true.

$$2n + 3 \le 2n + 3n$$

$$2n + 3 \le 5n, n \geq 1$$

Therefore \(f(n) = O(n)\).

Or we can write:

$$2n + 3 \le 5n^2 , n \geq 1$$

$$f(n) = 2n + 3$$

$$c = 5$$

$$g(n) = n^2$$

Can this same function be both \(O(n)\) and \(O(n^2)\)? Yes. It can be. This is where our definition of big o comes into play. It's the upper bound limit. We can say it is \(n^2, 2^n\) and any higher. But we cannot say it's lower.

When we write big o, we often want to use the closet function. Otherwise, we could say that every algorithm has an upper bound of \(O(2^n)\), which isn't true. Note: what we want to do (choose the closet function)  is just a personal preference for most courses. All functions which work, which are the upper bound, are true.

There's a fantastic video on this strange concept here (and I took this example from there).

Summary

Big O represents how long an algorithm takes but sometimes we care about how much memory (space complexity) an algorithm takes too. If you're ever stuck, come back to this page and check out the infographics!

Timsort: A very fast , O(n log n), stable sorting algorithm built for the real world — not constructed in academia.

Timsort is a sorting algorithm that is efficient for real-world data and not created in an academic laboratory. Tim Peters created Timsort for the Python programming language in 2001. Timsort first analyses the list it is trying to sort and then chooses an approach based on the analysis of the list.

Since the algorithm has been invented it has been used as the default sorting algorithm in Python, Java, the Android Platform, and in GNU Octave.

Timsort’s big O notation is O(n log n). To learn about Big O notation, read this.

Timsort’s sorting time is the same as Mergesort, which is faster than most of the other sorts you might know. Timsort actually makes use of Insertion sort and Mergesort, as you’ll see soon.

Peters designed Timsort to use already-ordered elements that exist in most real-world data sets. It calls these already-ordered elements “natural runs”. It iterates over the data collecting the elements into runs and simultaneously merging those runs together into one.

The array has fewer than 64 elements in it

If the array we are trying to sort has fewer than 64 elements in it, Timsort will execute an insertion sort.

An insertion sort is a simple sort which is most effective on small lists. It is quite slow at larger lists, but very fast with small lists. The idea of an insertion sort is as follows:

• Look at elements one by one
• Build up sorted list by inserting the element at the correct location

In this instance we are inserting the newly sorted elements into a new sub-array, which starts at the start of the array.

Here’s a gif showing insertion sort:

More about runs

If the list is larger than 64 elements than the algorithm will make a first pass through the list looking for parts that are strictly increasing or decreasing. If the part is decreasing, it will reverse that part.

So if the run is decreasing, it’ll look like this (where the run is in bold):

If not decreasing, it’ll look like this:

The minrun is a size which is determined based on the size of the array. The algorithm selects it so that most runs in a random array are, or become minrun, in length. Merging 2 arrays is more efficient when the number of runs is equal to, or slightly less than, a power of two. Timsort chooses minrun to try to ensure this efficiency, by making sure minrun is equal to or less than a power of two.

The algorithm chooses minrun from the range 32 to 64 inclusive. It chooses minrun such that the length of the original array, when divided by minrun, is equal to or slightly less than a power of two.

If the length of the run is less than minrun, you calculate the length of that run away from minrun. Using this new number, you grab that many items ahead of the run and perform an insertion sort to create a new run.

So if minrun is 63 and the length of the run is 33, you do 63–33 = 30. You then grab 30 elements from in front of the end of the run, so this is 30 items from run[33] and then perform an insertion sort to create a new run.

After this part has completed we should now have a bunch of sorted runs in a list.

Merging

Timsort now performs mergesort to merge the runs together. However, Timsort makes sure to maintain stability and merge balance whilst merge sorting.

To maintain stability we should not exchange 2 numbers of equal value. This not only keeps their original positions in the list but enables the algorithm to be faster. We will shortly discuss the merge balance.

As Timsort finds runs, it adds them to a stack. A simple stack would look like this:

Imagine a stack of plates. You cannot take plates from the bottom, so you have to take them from the top. The same is true about a stack.

Timsort tries to balance two competing needs when mergesort runs. On one hand, we would like to delay merging as long as possible in order to exploit patterns that may come up later. But we would like even more to do the merging as soon as possible to exploit the run that the run just found is still high in the memory hierarchy. We also can’t delay merging “too long” because it consumes memory to remember the runs that are still unmerged, and the stack has a fixed size.

To make sure we have this compromise, Timsort keeps track of the three most recent items on the stack and creates two laws that must hold true of those items:

1. A > B + C
2. B > C

Where A, B and C are the three most recent items on the stack.

In the words of Tim Peters himself:

What turned out to be a good compromise maintains two invariants on the stack entries, where A, B and C are the lengths of the three righmost not-yet merged slices

Usually, merging adjacent runs of different lengths in place is hard. What makes it even harder is that we have to maintain stability. To get around this, Timsort sets aside temporary memory. It places the smaller (calling both runs A and B) of the two runs into that temporary memory.

Galloping

While Timsort is merging A and B, it notices that one run has been “winning” many times in a row. If it turned out that the run A consisted of entirely smaller numbers than the run B then the run A would end up back in its original place. Merging the two runs would involve a lot of work to achieve nothing.

More often than not, data will have some preexisting internal structure. Timsort assumes that if a lot of run A’s values are lower than run B’s values, then it is likely that A will continue to have smaller values than B.

Image of 2 example runs, A and B. Runs have to be strictly increasing or decreasing, hence why these numbers were picked.

Timsort will then enter galloping mode. Instead of checking A[0] and B[0] against each other, Timsort performs a binary search for the appropriate position of b[0] in a[0]. This way, Timsort can move a whole section of A into place. Then Timsort searches for the appropriate location of A[0] in B. Timsort will then move a whole section of B can at once, and into place.

Let’s see this in action. Timsort checks B[0] (which is 5) and using a binary search it looks for the correct location in A.

Well, B[0] belongs at the back of the list of A. Now Timsort checks for A[0] (which is 1) in the correct location of B. So we’re looking to see where the number 1 goes. This number goes at the start of B. We now know that B belongs at the end of A and A belongs at the start of B.

It turns out, this operation is not worth it if the appropriate location for B[0] is very close to the beginning of A (or vice versa). so gallop mode quickly exits if it isn’t paying off. Additionally, Timsort takes note and makes it harder to enter gallop mode later by increasing the number of consecutive A-only or B-only wins required to enter. If gallop mode is paying off, Timsort makes it easier to reenter.

In short, Timsort does 2 things incredibly well:

• Great performance on arrays with preexisting internal structure
• Being able to maintain a stable sort

Previously, in order to achieve a stable sort, you’d have to zip the  items in your list up with integers, and sort it as an array of tuples.

Code

If you’re not interested in the code, feel free to skip this part. There’s some more information below this section.

# based off of this code https://gist.github.com/nandajavarma/a3a6b62f34e74ec4c31674934327bbd3
# Brandon Skerritt
# https://skerritt.tech

def binary_search(the_array, item, start, end):
    if start == end:
        if the_array[start] > item:
            return start
        else:
            return start + 1
    if start > end:
        return start

    mid = round((start + end)/ 2)

    if the_array[mid] < item:
        return binary_search(the_array, item, mid + 1, end)

    elif the_array[mid] > item:
        return binary_search(the_array, item, start, mid - 1)

    else:
        return mid

"""
Insertion sort that timsort uses if the array size is small or if
the size of the "run" is small
"""
def insertion_sort(the_array):
    l = len(the_array)
    for index in range(1, l):
        value = the_array[index]
        pos = binary_search(the_array, value, 0, index - 1)
        the_array = the_array[:pos] + [value] + the_array[pos:index] + the_array[index+1:]
    return the_array

def merge(left, right):
    """Takes two sorted lists and returns a single sorted list by comparing the
    elements one at a time.
    [1, 2, 3, 4, 5, 6]
    """
    if not left:
        return right
    if not right:
        return left
    if left[0] < right[0]:
        return [left[0]] + merge(left[1:], right)
    return [right[0]] + merge(left, right[1:])

def timsort(the_array):
    runs, sorted_runs = [], []
    length = len(the_array)
    new_run = [the_array[0]]

    # for every i in the range of 1 to length of array
    for i in range(1, length):
        # if i is at the end of the list
        if i == length - 1:
            new_run.append(the_array[i])
            runs.append(new_run)
            break
        # if the i'th element of the array is less than the one before it
        if the_array[i] < the_array[i-1]:
            # if new_run is set to None (NULL)
            if not new_run:
                runs.append([the_array[i]])
                new_run.append(the_array[i])
            else:
                runs.append(new_run)
                new_run = []
        # else if its equal to or more than
        else:
            new_run.append(the_array[i])

    # for every item in runs, append it using insertion sort
    for item in runs:
        sorted_runs.append(insertion_sort(item))
    
    # for every run in sorted_runs, merge them
    sorted_array = []
    for run in sorted_runs:
        sorted_array = merge(sorted_array, run)

    print(sorted_array)

timsort([2, 3, 1, 5, 6, 7])

The source code below is based on mine and Nanda Javarma’s work. The source code is not complete, nor is it similar to Python’s offical sorted() source code. This is just a dumbed-down Timsort I implemented to get a general feel of Timsort. If you want to see Timsort’s original source code in all its glory, check it out here. Timsort is offically implemented in C, not Python.

Timsort is actually built right into Python, so this code only serves as an explainer. To use Timsort simply write:

list.sort()

Or

sorted(list)

If you want to master how Timsort works and get a feel for it, I highly suggest you try to implement it yourself!

This article is based on Tim Peters’ original introduction to Timsort, found here.

Greedy algorithms aim to make the optimal choice at that given moment. Each step it chooses the optimal choice, without knowing the future. It attempts to find the globally optimal way to solve the entire problem using this method.

Why Are Greedy Algorithms Called Greedy?

We call algorithms greedy when they utilise the greedy property. The greedy property is:

At that exact moment in time, what is the optimal choice to make?

Greedy algorithms are greedy. They do not look into the future to decide the global optimal solution. They are only concerned with the optimal solution locally. This means that the overall optimal solution may differ from the solution the algorithm chooses.

They never look backwards at what they’ve done to see if they could optimise globally. This is the main difference between Greedy and Dynamic Programming.

To be extra clear, one of the most Googled questions about greedy algorithms is:

“What problem-solving strategies don’t guarantee solutions but make efficient use of time?”

The answer is “Greedy algorithms”. They don’t guarantee solutions but are very time efficient. However, in the next section, we’ll learn that sometimes Greedy solutions give us the optimal solutions.

What Are Greedy Algorithms Used For?

Greedy algorithms are quick. A lot faster than the two other alternatives (Divide & Conquer, and Dynamic Programming). They’re used because they’re fast.

Sometimes, Greedy algorithms give the global optimal solution every time. Some of these algorithms are:

• Dijkstra’s Algorithm
• Kruskal’s algorithm
• Prim’s algorithm
• Huffman trees

These algorithms are Greedy, and their Greedy solution gives the optimal solution.

We’re going to explore greedy algorithms using examples, and learning how it all works.

How Do I Create a Greedy Algorithm?

Your algorithm needs to follow this property:

At that exact moment in time, what is the optimal choice to make?

And that’s it. There isn’t much to it. Greedy algorithms are easier to code than Divide & Conquer or Dynamic Programming.

Counting Change Using Greedy

Imagine you’re a vending machine. Someone gives you £1 and buys a drink for £0.70p. There’s no 30p coin in pound sterling, how do you calculate how much change to return?

For reference, this is the denomination of each coin in the UK:

1p, 2p, 5p, 10p, 20p, 50p, £1

The greedy algorithm starts from the highest denomination and works backwards. Our algorithm starts at £1. £1 is more than 30p, so it can’t use it. It does this for 50p. It reaches 20p. 20p < 30p, so it takes 1 20p.

The algorithm needs to return a change of 10p. It tries 20p again, but 20p > 10p. It next goes to 10p. It chooses 1 10p, and now our return is 0 we stop the algorithm.

We return 1x20p and 1x10p.

This algorithm works well in real life. Let’s use another example, this time we have the denomination next to how many of that coin is in the machine, (denomination, how many).

(1p, 10), (2p, 3), (5p, 1), (10p, 0), (20p, 1p), (50p, 19p), (100p, 16)

The algorithm is asked to return a change of 30p again. 100p (£1) is no. Same for 50. 20p, we can do that. We pick 1x 20p. We now need to return 10p. 20p has run out, so we move down 1.

10p has run out, so we move down 1.

We have 5p, so we choose 1x5p. We now need to return 5p. 5p has run out, so we move down one.

We choose 1 2p coin. We now need to return 3p. We choose another 2p coin. We now need to return 1p. We move down one.

We choose 1x 1p coin.

Our algorithm selected these coins to return as change:

# (value, how many we return as change)
(10, 1)
(5, 1)
(2, 2)
(1, 1)

Let’s code something. First, we need to define the problem. We’ll start with the denominations.

denominations = [1, 2, 5, 10, 20, 50, 100]
# 100p is £1

Now onto the core function. Given denominations and an amount to give change, we want to return a list of how many times that coin was returned.

If our denominations list is as above, [6, 3, 0, 0, 0, 0, 0] represents taking 6x1p coins and 3x2p coins, but 0 of all other coins.

denominations = [1, 2, 5, 10, 20, 50, 100]
# 100p is £1

def returnChange(change, denominations):
    toGiveBack = [0] * len(denominations)
    for pos, coin in reversed(list(enumerate(denominations))):

We create a list, the size of denominations long and fill it with 0’s.

We want to loop backwards, from largest to smallest. Reversed(x) reverses x and lets us loop backwards. Enumerate means “for loop through this list, but keep the position in another variable”. In our example when we start the loop. coin = 100 and pos = 6.

Our next step is choosing a coin for as long as we can use that coin. If we need to give change = 40 we want our algorithm to choose 20, then 20 again until it can no longer use 20. We do this using a for loop.

denominations = [1, 2, 5, 10, 20, 50, 100]
# 100p is £1

def returnChange(change, denominations):
    # makes a list size of length denominations filled with 0
    toGiveBack = [0] * len(denominations)

    # goes backwards through denominations list
    # and also keeps track of the counter, pos.
    for pos, coin in enumerate(reversed(denominations)):
        # while we can still use coin, use it until we can't
        while coin <= change:

While the coin can still fit into change, add that coin to our return list, toGiveBack and remove it from change.

denominations = [1, 2, 5, 10, 20, 50, 100]
# 100p is £1

def returnChange(change, denominations):
    # makes a list size of length denominations filled with 0
    toGiveBack = [0] * len(denominations)

    # goes backwards through denominations list
    # and also keeps track of the counter, pos.
    for pos, coin in enumerate(reversed(denominations)):
        # while we can still use coin, use it until we can't
        while coin <= change:
            change = change - coin
            toGiveBack[pos] += 1
    return(toGiveBack)
            
print(returnChange(30, denominations))
# returns [0, 0, 0, 1, 1, 0, 0]
# 1x 10p, 1x 20p

The runtime of this algorithm is dominated by the 2 loops, thus it is O(n2)O(n2).

Is Greedy Optimal? Does Greedy Always Work?

It is optimal locally, but sometimes it isn’t optimal globally. In the change-giving algorithm, we can force a point at which it isn’t optimal globally.

The algorithm for doing this is:

• Pick 3 denominations of coins. 1p, x, and less than 2x but more than x.

We’ll pick 1, 15, 25.

• Ask for a change of 2 * second denomination (15)

We’ll ask for a change of 30. Now, let’s see what our Greedy algorithm does.

[5, 0, 1]

It choses 1x 25p, and 5x 1p. The optimal solution is 2x 15p.

Our Greedy algorithm failed because it didn’t look at 15p. It looked at 25p and thought “Yup, that fits. Let’s take it.”

It then looked at 15p and thought “That doesn’t fit, let’s move on”.

This is an example of where Greedy Algorithms fail.

To get around this, you would either have to create currency where this doesn’t work or brute-force the solution. Or use Dynamic Programming.

Dijkstra’s Algorithm

Dijkstra’s algorithm finds the shortest path from a node to every other node in the graph. In our example, we’ll be using a weighted directed graph. Each edge has a direction, and each edge has a weight.

Dijkstra’s algorithm has many uses. It can be very useful within road networks where you need to find the fastest route to a place. We also use the algorithm for:

• IP Routing
• A* Algorithm
• Telephone networks

The algorithm follows these rules:

1. Every time we want to visit a new node, we will choose the node with the smallest known distance.
2. Once we’ve moved to the node, we check each of its neighbouring nodes. We calculate the distance from the neighbouring nodes to the root nodes by summing the cost of the edges that lead to that new node.
3. If the distance to a node is less than a known distance, we’ll update the shortest distance.

Our first step is to pick the starting node. Let’s choose A. All the distances start at infinity, as we don’t know their distance until we reach a node that knows the distance.

We mark off A on our unvisited nodes list. The distance from A to A is 0. The distance from A to B is 4. The distance from A to C is 2. We updated our distance listing on the right-hand side.

We pick the smallest edge where the vertex hasn’t been chosen. The smallest edge is A -> C, and we haven’t chosen C yet. We visit C.

Notice how we’re picking the smallest distance from our current node to a node we haven’t visited yet. We’re being greedy. Here, the greedy method is the global optimal solution.

We can get to B from C. We now need to pick a minimum min(4, 2+1)=3.

Since A -> C -> B is smaller than A -> B, we update B with this information. We then add in the distances from the other nodes we can now reach.

Our next smallest vertex with a node we haven’t visited yet is B, with 3. We visit B.

We do the same for B. Then we pick the smallest vertex we haven’t visited yet, D.

We don’t update any of the distances this time. Our last node is then E.

There are no updates again. To find the shortest path from A to the other nodes, we walk back through our graph.

We pick A first, C second, B third. If you need to create the shortest path from A to every other node as a graph, you can run this algorithm using a table on the right-hand side.

Using this table it is easy to draw out the shortest distance from A to every other node in the graph:

Minimum Spanning Trees Using Prim’s Algorithm

Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. It finds the optimal route from every node to every other node in the tree.

With a small change to Dijkstra’s algorithm, we can build a new algorithm - Prim’s algorithm!

We informally describe the algorithm as:

1. Create a new tree with a single vertex (chosen randomly)
2. Of all the edges not yet in the new tree, find the minimum weighted edge and transfer it to the new tree
3. Repeat step 2 until all vertices are in the tree

We have this graph.

Our next step is to pick an arbitrary node.

We pick the node A. We then examine all the edges connecting A to other vertices. Prim’s algorithm is greedy. That means it picks the shortest edge that connects to an unvisited vertex.

In our example, it picks B.

We now look at all nodes reachable from A and B. This is the distinction between Dijkstra’s and Prim’s. With Dijkstra’s, we’re looking for a path from 1 node to a certain other node (nodes that have not been visited). With Prim’s, we want the minimum spanning tree.

We have 3 edges with equal weights of 3. We pick 1 randomly.

It is helpful to highlight our graph as we go along because it makes it easier to create the minimum spanning tree.

Now we look at all edges of A, B, and C. The shortest edge is C > E with a weight of 1.

And we repeat:

The edge B > E with a weight of 3 is the smallest edge. However, both vertices are always in our VISITED list. Meaning we do not pick this edge. We instead choose C > F, as we have not visited

The only node left is G, so let’s visit it.

Note that if the edge weights are distinct, the minimum spanning tree is unique.

We can add the edge weights to get the minimum spanning tree’s total edge weight:

$$2+3+3+1+6+9=24$$

Fractional Knapsack Problem Using Greedy Algorithm

Imagine you are a thief. You break into the house of Judy Holliday - 1951 Oscar winner for Best Actress. Judy is a hoarder of gems. Judy’s house is lined to the brim with gems.

You brought with you a bag - a knapsack if you will. This bag has a weight of 7. You happened to have a listing of  Judy’s items, from some insurance paper. The items read as:

The first step to solving the fractional knapsack problem is to calculate \(\frac{value}{weight}\) for each item.

And now we greedily select the largest ones. To do this, we can sort them according to \(\frac{value}{weight}\)

in descending order. Luckily for us, they are already sorted. The largest one is 3.2.

knapsack value = 16
knapsack total weight = 5 (out of 7)

Then we select Francium (I know it’s not a gem, but Judy is a bit strange 😉)

knapsack value = 19
knapsack weight = 6

Now, we add Sapphire. But if we add Sapphire, our total weight will come to 8.

In the fractional knapsack problem, we can cut items up to take fractions of them. We have a weight of 1 left in the bag. Our sapphire has weight 2. We calculate the ratio of:

$$\frac{weight\;of\;knapsack\;left}{weight\;of\;item}$$

And then multiply this ratio by the value of the item to get how much value of that item we can take.

$$\frac{1}{2} * 6 = 3$$

knapsack value = 21
knapsack weight = 7

The greedy algorithm can optimally solve the fractional knapsack problem, but it cannot optimally solve the {0, 1} knapsack problem. In this problem instead of taking a fraction of an item, you either take it {1} or you don’t {0}. To solve this, you need to use Dynamic Programming.

The runtime for this algorithm is O(n log n). Calculating \(\frac{value}{weight}\) is O(1). Our main step is sorting from largest \(\frac{value}{weight}\), which takes O(n log n) time.

Greedy vs Divide & Conquer vs Dynamic Programming

To learn more about Divide & Conquer and Dynamic Programming, check out these 2 posts I wrote:

• Divide & Conquer
• Dynamic Programming

Conclusion

Greedy algorithms are very fast, but may not provide the optimal solution. They are also easier to code than their counterparts.

No talk about downloading things on BitTorrent. Or the best clients to do so.

Just a deep dive into the technical side of it.

Anyone can read this article. Requires ZERO knowledge of networking or BitTorrent to read this.

BitTorrent is one of the most common protocols for transferring large files. In February 2013, BitTorrent was responsible for 3.35% of all worldwide bandwidth, more than half of the 6% of total bandwidth dedicated to file sharing.

Let’s dive right in.

💭 Who Created BitTorrent?

Bram Cohen invented the BitTorrent protocol in 2001. Cohen wrote the first client implementation in Python.

Cohen collected free pornography to lure beta testers to use BitTorrent in the summer of 2002.

🥊 BitTorrent vs Client-Server Downloading

In traditional downloading, the server uploads the file, and the client downloads the file.

For popular files, this isn’t very effective.

500 people downloading the same file will put the server under strain. This strain will cap the upload speed, so clients can not download the file fast.

Second, the client-server costs a lot of money. The amount we pay increases with how popular a file is.

Third, it’s centralised. Say the system dies, and the file no longer exists - no one can download it.

BitTorrent aims to solve these problems.

In a peer-to-peer network, every peer is connected to every other peer in the network.

Semi-centralised peer-to-peer networks possess one or more peers with higher authority than most peers.

📑 High-Level Overview

BitTorrent is a way to share files. It’s often used for large files. BitTorrent is an alternative to a single source sharing a file, such as a server. BitTorrent can productively work on lower bandwidth.

The first release of the BitTorrent client had no search engine and no peer exchange, users who wanted to upload a file had to create a small torrent descriptor file that they would upload to a torrent index site.

When a user wants to share a file, they seed their file. This user is called a seeder. They upload a torrent descriptor file to an exchange (we’ll talk about this later). Anyone who wants to download that file will download this torrent descriptor.

We call those who download peers. Their torrent client will connect to a tracker (discussed later) and the tracker will send them a list of IP addresses of other seeds and peers in the swarm. The *swarm *is all PC’s related to a certain torrent.

The torrent descriptor file contains a list of trackers and metadata on the file we’re downloading.

A peer will connect to a seed and download parts of the file.

Once the peer completes a download, they could function as a seed. Although, it is possible to function as a seed while also downloading (and is very common).

Once the seed has shared the file with a peer, that peer will act as a seed. Instead of the client-server model where only 1 server exists to upload the file, in BitTorrent, multiple people can upload the same file.

BitTorrent splits the file up into chunks called pieces, each of a certain size. Sometimes it’s 256KB, sometimes it’s 1MB. As each peer receives a piece, they become a seed of that piece for other peers.

With BitTorrent, we do not have a single source to download from. We could download a few pieces from your home country, then download a few that your home country doesn’t own from a faraway country.

The protocol hashes the pieces to make sure no seed has tampered with the original file. Then stores the hash in the torrent descriptor on the tracker.

This is how BitTorrent works at a very high level. We will now go into detail. We aim to answer these questions:

• What if a peer only downloads and never uploads?
• Who do we download from, or upload to?
• What is a magnet link?
• What is a torrent descriptor?
• What hashing algorithm is used?
• How does BitTorrent select what pieces to download?

And much more.

📁 What’s in a Torrent Descriptor File, Anyway?

It’s a dictionary (or hashmap) file.

The file is described as:

• Announce

The URL of the tracker. Remember earlier when we contacted the tracker server to find other peers using the same file? We found that tracker by using the announce key in the torrent descriptor file.

• Info

This maps to a dictionary whose keys depend on whether one or more files are being shared. The keys are:

Files (child of info, is a list)

Files only exist when multiple files are being shared. Files is a list of dictionaries. Each dictionary corresponds to a file. Each of these dictionaries has 2 keys.

Length - the size of the file in bytes.

Path -  A list of strings corresponding to subdirectory names, the last of which is the actual file name.

• Length

The size of the file in bytes (only when one file is being shared)

• Name

Suggested filename. Or the suggested directory name.

• Pieces length

The number of bytes per piece.

The piece’s length must be a power of two and at least 16KiB.

This is

$$2^8 \; KiB = 256 \; KiB = 262,144 \; B$$

• Pieces

A hash list.

A list of hashes calculated on various chunks of data. We split the data into pieces. Calculate the hashes for those pieces, and stores them in a list.

BitTorrent uses SHA-1, which returns a 160-bit hash. Pieces will be a string whose length is a multiple of 20 bytes.

If the torrent contains multiple files, the pieces are formed by concatenating the files in the order they appear in the files directory.

All pieces in the torrent are the full piece length except for the last piece which may be shorter.

Now, I can guess what you’re thinking.

“SHA-1? What is this? The early 2000s?”

And I agree. BitTorrent is moving from SHA-1 to SHA256.

Still confused? Not to worry! I designed this JSON file that describes what a torrent file looks like.

{
    "Announce": "url of tracker",
    "Info": {
        "Files": [
            {
                "Length": 16,
                "path": "/folder/to/path"
            },
            {
                "length": 193,
                "path": "/another/folder"
            }
        ]
    },
    "length": 192,
    "name":" Ubuntu.iso",
    "Pieces length": 262144,
    "Pieces": ["AAF4C61DDCC5E8A2DABEDE0F3B482CD9AEA9434D", "CFEA2496442C091FDDD1BA215D62A69EC34E94D0"]
}

🧀 The Piece Selection Algorithm of BitTorrent

One of the largest questions in BitTorrent is “what pieces should I select to download?”

With a traditional client-server model, we download the whole file. But now, we get to pick what pieces to download.

The idea is to download the pieces that no one else has - the rare pieces. By downloading the rare pieces, we make them less rare by uploading them.

🌆 What Are Sub-Pieces and the Piece Selection Algorithm?

BitTorrent uses TCP, a transmission protocol for packets. TCP has a mechanism called slow start.

Slow start is a mechanism which balances the speed of a TCP network connection. It escalates the amount of data transmitted until it finds the network’s maximum carrying capacity. cwdn stands for the Congestion Window.

TCP does this because if we send 16 connections at once, the server may not be used to the traffic and congestion will happen on the network.

If we’re not regularly sending data, TCP may cap our network connection at a slower speed than normal.

BitTorrent makes sure to always send data by breaking pieces down into further sub-pieces.

Each sub-piece is about 16KB in size. The size for a piece is not fixed, but it is somewhere around 1MB.

The protocol always has some number of requests (five) for a sub-piece pipe-lined. When a new sub-piece is downloaded, the client sends a new request. This helps speed things up.

Sub-pieces can be downloaded from other peers.

Two core policies govern the Piece Selection Algorithm.

1️⃣ Strict Policy

Once the BitTorrent client requests a sub-piece of a piece, any remaining sub-pieces of that piece are requested before any sub-pieces from other pieces.

In this image, it makes sense to download all the sub-pieces of this piece first rather than start downloading another piece.

2️⃣ Rarest First

The main policy in BitTorrent is to pick the rarest first. We want to download the piece that the fewest other peers own.

This is so we can make it ‘un-rare’. If only one peer has a piece and they go offline, no one will get the complete file.

A plethora of benefits exists for this policy.

Growing the seed

Rarest first makes sure that we download only new pieces from the seed.

The seed will begin as a bottleneck. The one peer with the file.

A downloader can see what pieces their peers possess, and the rarest first policy will cause us to fetch the pieces from the seed which have not been uploaded by other peers.

Let’s visualise this.

The list of nodes (peers) is interconnected. I cannot draw this as the diagram is unfavourable.

Each arrow is towards a sub-piece what that peer has downloaded. We downloaded a sub-piece that no one else has other than the seed. This means this sub-piece is rare.

Our upload rate is higher than that of the seed, so all peers will want to download from us. Also, they would want to download the rarest pieces first, and as we are one of 2 holders of the rarest piece.

When everyone downloads from us, we can download faster from them. This is the tit-for-tat algorithm (discussed later).

Increased download speed

The more peers that hold the piece, the faster the download can happen. This is because we can download sub-pieces from other peers.

Enable uploading

A rare piece is most wanted by other peers and getting a rare piece means peers will be interested in uploading from us. As we will see later, the more we upload, the more we can download.

Most common last

It is sensible to leave the most common pieces to the end of the download. As many peers hold common pieces, the probability of being able to download them is much larger than that of rare pieces.

Prevent the rarest piece missing

When the seed dies, all the different pieces of the file should be distributed somewhere among the remaining peers.

3️⃣ Random First Piece

Once we download, we have nothing to upload. We need the first piece, fast. The rarest first policy is slow. Rare pieces are downloaded slower because we can download its sub-pieces from only a few peers.

4️⃣ Endgame Mode

Sometimes a peer with a slow transfer rate will try to give us a sub-piece. Causing a delay in the download. To prevent this, there is “endgame mode”.

Remember the pipe-lining principle? There are always several requests for sub-pieces pending.

When all the sub-pieces a peer lacks are requested, they broadcast this request to all peers. This helps us get the last chunk of the file.

If a peer has the missing sub-piece, they will send that back to our computer.

Once a sub-piece arrives, we send a cancel message telling the other peers to ignore our request.

🌱 Resource Allocation Using Tit-For-Tat

No centralised resource allocation in BitTorrent exists. Instead, every peer maximises their download rate.

A peer will download from whoever they can. To decide who to upload to, they will use a variant of the “tit-for-tat” algorithm.

The tit-for-tat strategy comes from game theory. The essence is:

“Do onto others as they do onto you”

1. On the first move, cooperate
2. On each succeeding move do what your opponent did the previous move
3. Be prepared to forgive after carrying out just one act of retaliation

🎐 The Choking Algorithm

Choking is a temporary refusal to upload to another peer, but we can still download from them.

To cooperate peers upload, and to not cooperate they “choke” the connection to their peers. The principle is to upload to peers who have uploaded to us.

We want several bidirectional connections at the same time to achieve Pareto Efficiency.

We consider an allocation Pareto Efficient if there is no other allocation in which some individual is better off and no individual is worse off.

Thus the big question, is how to determine which peers to choke and which to unchoke?

A peer always unchokes a fixed number of its peers (the default is 4).

Current download rates decide which peers to unchoke. We use a 20-second average to decide this. Because of the use of TCP (slow-start) rapidly choking and unchoking is bad. Thus, this is calculated every 10 seconds.

If our upload rate is high more peers will allow us to download from them. This means that we can get a higher download rate if we are a good uploader. This is the most important feature of the BitTorrent protocol.

The protocol prohibits many “free riders” which are peers who only download and don’t upload.

For a peer-to-peer network to be efficient, all peers need to contribute to the network.

😎 Optimistic Unchoking

BitTorrent also allows an additional unchoked peer, where the download rate criteria aren’t used.

We call this optimistic unchoking. Checking an unused connection isn’t better than the one in use.

We shift the optimistic unchoke every 30 seconds. Enough time for the upload reaches full speed. Same for the upload. If this new connection turns out to be better than one of the existing unchoked connections, it will replace it.

The optimistic unchoke is randomly selected.

This also allows peers who do not upload and only download to download the file, even if they refuse to cooperate. Albeit, they will download at a much slower speed.

🤕 Anti-Snubbing

What happens if all peers uploading to another peer decide to choke it? We then have to find new peers, but the optimistic unchoking mechanism only checks one unused connection every 30 seconds. To help the download rate recover more, BitTorrent has snubbing.

If a client hasn’t received anything from a particular peer for 60 seconds, it will presume that it has been ‘snubbed’.

Following the mentality of tit-for-tat, we retaliate and refuse to upload to that peer (except if they become an optimistic unchoke).

The peer will then increase the number of optimistic unchokes to find new connections quicker.

🤔 What If We Upload Only?

We see that by using the choking algorithm implemented in BitTorrent we favour peers who are kind to us. If I can download fast from them, we allow them to upload fast from me.

What about no downloads? Then it’s impossible to know which peers to unchoke using this choking algorithm. When a download is completed, we use a new choking algorithm.

This new choking algorithm unchokes peers with the highest upload rate. This ensures that pieces get uploaded faster, and they get replicated faster.

Peers with good upload rates are also not being served by others.

🐝 What Is a Tracker?

Trackers are special types of servers that help in communication between peers.

Communication in BitTorrent is important. How do we learn what other peers exist?

The tracker knows who owns the file, and how much.

Once a peer-to-peer download has started, communication can continue without a tracker.

Since the creation of the distributed hash table method for trackerless torrents, BitTorrent trackers are largely redundant.

🗼 Public Trackers

These are trackers that anyone can use.

The Pirate Bay operated one of the most popular public trackers until disabling it in 2009, opting only for magnet links (discussed soon).

🔐 Private Trackers

Private trackers are private. They restrict use by requiring users to register with the site. The method for controlling registration is often an invitation system. To use this tracker we need an invitation.

🔢 Multi-Tracker Torrents

Multi-tracker torrents contain multiple trackers in a single torrent file. This provides redundancy if one tracker fails, the other trackers can continue to maintain the swarm for the torrent.

With this configuration, it is possible to have multiple unconnected swarms for a single torrent - which is bad. Some users can connect to one specific tracker while being unable to connect to another. This can create a disjoint set which can impede the efficiency of a torrent to transfer the files it describes.

🧲 Magnet Links - Trackerless Torrents

Earlier, I talked about how the Pirate Bay got rid of trackers and started using trackerless torrents.

When we download a torrent, we get a hash of that torrent. To download the torrent without a tracker, we need to find other peers also downloading the torrent. To do this, we need to use a distributed hash table.

Let’s explore Distributed Hash Tables.

🐍 Distributed Hash Tables

Distributed Hash Tables (DHT) give us a dictionary-like interface, but the nodes are distributed across a network. The trick with DHTs is that the node that gets to store a particular key is found by hashing that key.

In effect, each peer becomes a mini-tracker.

Each node (client/server implementing the DHT protocol) has a unique identifier known as the “node ID”. We choose node IDs at random from the same 160-bit space as BitTorrent info hashes.

Info hashes are a SHA-1 hash of:

1. ITEM: length(size) and path (path with filename)
2. Name: The name to search for
3. Piece length: The length(size) of a single piece
4. Pieces: SHA-1 Hash of EVERY piece of this torrent
5. Private: flag for restricted access

We use a distance metric to compare two node IDs or a node ID and an info hash for “closeness”.

Nodes must have a routing table containing the contact information for a few other nodes.

Nodes know about each other in the DHT. They know many nodes with IDs that are close to their own but few with far-away IDs.

The distance metric is XOR and is interpreted as an integer.

$$distance(A, B) = |A \oplus B |$$

Smaller values are closer.

When a node wants to find peers for a torrent, they use the distance metric to compare the info hash of the torrent with the IDs of the nodes in its routing table or the ID of one node with the ID of another node.

Then they contact the nodes in the routing table closest to the info hash and ask them for the contact information of peers downloading the torrent.

If a contacted node knows about peers for the torrent, they return the peer contact information with the response. Otherwise, the contacted node must respond with the contact information of the nodes in its routing table closet to the info hash of the torrent.

The original node queries nodes that are closer to the target info hash until it cannot find any closer nodes. After the node exhausts the search, the client then inserts the peer contact information for itself onto the responding nodes with IDs closest to the info hash of the torrent. In the future, other nodes can easily find us.

The return value for a query for peers includes an opaque value known as the “token.” For a node to announce that its controlling peer is downloading a torrent, it must present the token received from the same queried node in a recent query for peers.

When a node attempts to “announce” a torrent, the queried node checks the token against the querying node’s IP address. This is to prevent malicious hosts from signing up other hosts for torrents.

The querying node returns the token to the same node that they receive the token from. We must accept tokens for a reasonable amount of time after they have been distributed. The BitTorrent implementation uses the SHA-1 hash of the IP address concatenated onto a secret that changes every five minutes and tokens up to ten minutes old are accepted.

📌 Routing Table

Every node maintains a routing table of known good nodes. We use the routing table starting points for queries in the DHT. We return nodes from the routing table in response to queries from other nodes.

Not all nodes we learn about are equal. Some are “good” and some are not. Many nodes using the DHT can send queries and receive responses, but cannot respond to queries from other nodes. Each node’s routing table must contain only known good nodes.

A good node is a node has responded to one of our queries within the last 15 minutes. A node is also good if it has ever responded to our queries and has sent us a query within the last 15 minutes. After 15 minutes of inactivity, a node becomes questionable. Nodes become bad when they fail to respond to multiple queries in a row. Nodes that we see are good are given priority over nodes with an unknown status.

The routing table covers the entire node ID space from 0 to 2160. We subdivide the routing table into “buckets” that each cover a portion of the space.

An empty table has one bucket with an ID space range of min=0, max=2160.

An empty table has only one bucket so any node must fit within it. Each bucket can only hold K nodes, currently eight, before becoming “full.”

When a bucket is full of known good nodes, we may add no more nodes unless our node ID falls within the range of the bucket. The bucket is replaced by two buckets each with half of the old bucket. Nodes from the old bucket are distributed among the new buckets.

For a new table with only one bucket, we always split the full bucket into two new buckets covering the ranges 0..2¹⁵⁹ and 2¹⁵⁹..2¹⁶⁰.

When the bucket is full of good nodes, we simply discard the new node. When nodes in the bucket become bad (if they do) we replace them with a new node.

When nodes are considered questionable and haven’t been since, in the last 15 minutes, the least recently seen node is pinged. The node either responds or doesn’t respond. A response means we move to the next node. We do this until we find a node that fails to respond. If we don’t find any, then the bucket is considered good.

When we do find one, we try one more time before discarding the node and replacing them with a new good node.

Each bucket should maintain a “last changed” property to show how “fresh” the contents are.

When a node in a bucket is pinged and responds, or a node is added to a bucket or a node is replaced with another node, the bucket’s last changed property is updated.

Buckets are refreshed if the last changed property has not been updated in the last 15 minutes.

🤺 Attacks on BitTorrent

Few attacks on the BitTorrent network exist. Everything is public. Our IP address, what we’re downloading - everything. Why attack an open network?

Why attack a completely open network?

Only 7 entries are listed on Exploit-DB - a database of known exploits against a service. And most of them relate to specific clients.

The principal attack on the BitTorrent network is to stop piracy. We’ve gone this far without talking about piracy, but it is often synonymous with BitTorrent.

The main attack on BitTorrent is Torrent Poisoning.

Torrent Poisoning

This attack aims to get the IP addresses of peers pirating content or to poison the content in some way.

Madonna’s American Life album release is an example of content poisoning. Before the release, tracks were released of similar length and file size. The tracks featured a clip of Madonna saying:

“What the fuck do you think you’re doing?”

Followed by a few minutes of silence.

Here are some methods of poisoning a torrent.

Index Poisoning

The index allows users to locate the IP addresses of peers with the desired content. This method of attack makes searching for peers difficult.

The attacker inserts a large amount of invalid information into the index to prevent users from finding the correct information.

The idea is to slow down the download, by having the peer try to download pieces from an invalid peer.

Decoy Insertion

They insert corrupted versions of a file into the network.

Imagine 500 copies of a file and only 2 of them being the real file, this deters pirates from finding the real file.

Most websites with lists of torrents a voting system. This deters this attack, as the top of searches is filled with non-corrupted files However, most websites with lists of torrents a voting

This deters this attack, as the top of searches is filled with non-corrupted files.

In GameDevTycoon, the file was released before the initial upload to piracy sites. Unbeknownst to pirates, the file was corrupted. Winning the game is impossible in the pirated version. Everything else was perfect.

🧙🏼‍♂️ Defence Against the Dark BitTorrent Attack

Most popular torrents are released by individuals or groups who built up a rapport over many years. On private trackers, individuals can be pointed to. Poisoned torrents are quickly labelled and the poster can be banned.

Or, on public trackers, downloading torrents made by trusted groups is preferable. After all, would you prefer to download Ubuntu from the Ubuntu team, or the user xxx-HACKER-ELITE-GHOST-PROTOCOL-xxx?

On public trackers, if a torrent is poisoned the torrent is reported and removed.

The simplest way to defend against a BitTorrent attack is to use an IP address not associated with you. Whether this is through a VPN or some other service.

👋🏻 Conclusion

Here are the things we’ve learnt:

• What a Torrent Descriptor file is
• How BitTorrent chooses peers
• How BitTorrent chooses pieces
• Tit-For-Tat algorithms
• Trackers
• Attacks on the BitTorrent network

Here are some things you may choose to do:

• Build your own BitTorrent client
• Explore BitTorrent’s proposals (BEPs) to learn more about how it works, and what’s next for the algorithm
• Read the official BitTorrent specification

Diffie-Hellman-Merkle is a way to share a secret key with someone (or something) without actually sending them the key. Before we look into how we share keys let’s first look into what keys are and why we would want to invent a method to share keys without giving the other person the key.

Your front door is usually locked by a key. This key unlocks & locks your front door. You have one key which you use to unlock and lock things.

Only people with the key or a copy of the key can unlock the door. Now, imagine you’re going to be on holiday Friday, Saturday, Sunday in Bali. You want to invite your friend around to look after your cat 😺 while you’re on the beautiful beaches 🏖️.

Your only friend is unfortunately on holiday Wednesday, Thursday and Friday. They get back right as you leave for holiday. You can’t be there to physically give them the key, but hiding the key under a rock outside your door seems insecure. Anyone could lift up that rock and find the key, but you just want your friend to have the key.

This is where Diffie-Hellman comes in. Well, with Diffie-Hellman you’re not exchanging physical keys but rather digital keys. Let’s explore some basic cryptography to understand why digital key exchange sucks just as much as real life key exchange.

Julius Caesar used a cipher to send messages that no one else could read other than the intended recipient. Mainly because no one could read back in 100 BC, and those that could wouldn’t understand a random string of letters. That’s the whole point of cryptography. To create ways to communicate without third parties understanding the message. This cipher is Caesar*‘s Cipher*. Given an alphabet and a key (the key is an integer between 1 and 25), shift all of the alphabet letters by key.

With a shift of 3, as seen in the image above, A becomes D, B becomes E and so on until it wraps around with X = A. The original message is called the *plaintext *and the encrypted message is called the ciphertext.

The easiest way to perform Caesar’s Cipher is to turn all of the letters into numbers, a = 1, b = 2, c = 3 and so on.

To encrypt, E, you calculate this for every letter (where s is the shift):

$$ E_{s}(letter) = (letter + shift)$$

To decrypt Caesar’s cipher, D, you calculate this for every letter:

$$D_{s}(letter) = (letter - shift)$$

Something important to note is that this version of the cipher doesn’t support wraparound (for brevity).

As you can tell, it’s not very secure. With 25 total shifts you just have to shift the text 25 times until you find the decrypted code, this is called a brute force attack. You take the encrypted text and shift it all 25 times until you find the decrypted text. But let’s imagine for a second that this was a hard cipher - that brute force isn’t feasible.

The shift is the key to Caesar’s cipher. But the problem still persists, how do you tell your friend you’re using a shift of 9? Any and all forms of communication can be listened in on. It doesn’t matter if you’re writing a letter or going to a hidden forest in Switzerland 30 miles from the nearest town. If you communicate the key, it can be listened in on.

How do you tell your friend you’re using a shift of 9, for example? You have to communicate it to them somehow. Any and all forms of communication can be listened in on - whether that’s writing a letter or going to a hidden forest in Switzerland 30 miles from the nearest town and telling your friend.

The problem becomes even more apparent when you realise that communicating parties over the internet usually have no prior knowledge about each other and are thousands of miles apart. This is where the magic of Diffie-Hellman-Merkle key exchange comes in.

Diffie-Hellman-Merkle

Diffie-Hellman is a way to securely exchange keys in public. It was conceptualised by Ralph Merkle, and named After Whitfield Diffie and Martin Hellman. I have chosen to include Merkle’s name as the title because he put in just as much work as Diffie-Hellman and his name never appears when this algorithm is talked about.

U.S. Patent 4,200,770, from 1977, is now expired and describes the now-public-domain algorithm. It credits Hellman, Diffie, and Merkle as inventors.

Let’s go through how this algorithm works.

1. Pick two numbers, G and N.

For this algorithm, we will also walk through the colour mixing method for explaining how it works.

Alice and Bob publicly agree to use a modulus p = 23 and g = 5 (which is a primitive root modulo 23, explained later). Modulus is just the remainder of the division. Note: this example comes from Wikipedia.

It’s hard to describe the painting method in text, so if you want to know about this method I suggest watching this video:

We’ll colour G yellow. We have 2 copies of G (yellow) as seen above.

When Alice and Bob agree on these numbers, Eve knows they are using these numbers.

2. Alice needs to calculate a private key.

She does this by picking a secret number (a). She computes G^a mod p and sends that result to Bob.

Alice chooses a secret, random integer a = 4.

Alice computes A = 5⁴ mod 23 = 4 and sends the number 4 to Bob.

She colours this private key reddish-brown.

Eve doesn’t know Alice’s secret number is 4, only that the result of this equation is 4. It’s not feasible for Eve to calculate what Alice’s secret number is from the resultant of this equation.

3. Bob makes his own private key. Its colour is dark green.

He calculates this by picking a secret number (b) and computes g^b mod p. He then sends the result to Alice. Bob creates a random private key, for this example we’ll use 3.

Then Bob calculates b = 5³ mod 23 = 10 and sends 10 to Alice.

4. Now Bob takes the number Alice sent him and computes b^a mod p.

In the colour analogy, this is taking Alice’s paint colour and adding it to Bob’s paint colour.

Bob computes s = 4³ mod 23 = 18.

Bob doesn’t send this to Alice.

5. Alice computes a^b mod p.

In the paint analogy, this is Alice adding Bob’s paint (that Bob sent her) to her painting.

Alice calculates s = 10⁴ mod 23 = 18

The magic is that Alice and Bob now have the same number or the same paint colour.

Let’s discuss in detail the mathematics behind this cool algorithm.

Explanation of maths

Diffie-Hellman-Merkle works because of a cool modulus exponent principle. First, let’s explain what modulus is before we try to understand this principle.

Modular Arithmetic

Imagine a finite range of numbers, for example, 1 to 12. These numbers are arranged in a circle, much like a clock (modular arithmetic is sometimes called clock arithmetic because of this).

Count 13 around this clock. You get to 12 and then you need to count 1 more - so you go back to 1. Modular arithmetic is still defined as the remainder of division, however, it can also be defined (and is more commonly defined) as a clock.

Functions using modular arithmetic tend to perform erratically, which in turn sometimes makes them one-way functions. Let’s see this with an example by taking a regular function and seeing how it works when it becomes a modular arithmetic function.

$$3^x$$

When we insert 2 into this function, we get 3² = 6. Insert 3 and we get 3³ = 9.

This function is easy to reverse. If we’re given 9, we can tell that the function had an input of 3, because 3³ = 9.

However, with modular arithmetic added, it doesn’t behave sensibly.

Imagine we had this formula:

$$3^{x} mod 7$$

How would you find out what x is? You can’t put the mod on the other side, because there isn’t really an inverse of modular arithmetic. What about guessing? Let’s input 5:

$$3^{5} mod 7$$

Okay, that was too big. You might want to go lower, maybe 4 or 3 but actually this is the wrong direction. When x is 6, it is equal to 1.

In normal arithmetic, we can test numbers and get a feel for whether we are getting warmer or colder, but this isn’t the case with modular arithmetic.

Often the easiest way to reverse modular arithmetic is to compile a table for all values of x until the right answer is found. Although this may work for smaller numbers, it is computationally infeasible to do for much larger numbers. This is often why modular arithmetic is known as a one-way function.

If I gave you a number such as 5787 and told you to find the function for it, it would be infeasible. In fact, if I gave you the ability to input any number into the function it would still be hard. It took me a mere few seconds to make this function, but it’ll take you hours or maybe even days to work out what x is.

Diffie-Hellman-Merkle is a one-way function. While it is relatively easy to carry out this function, it is computationally infeasible to do the reverse of the function and find out what the keys are. Although, it is possible to reverse an RSA encryption if you know some numbers such as N.

Primitive root

The primitive root of a prime number, p, is a number, a, such that all numbers:

$$a \; mod \; p, a^2 mod p, a^3 \; mod \; p, a^4 \; mod \; p, ...$$

are different. There is a formula for counting what the indices are, but I think it’s far more intuitive to acknowledge “the second one is to the power of 2, the third one is to the power of 3” and so on.

Let's see an example where $p = 7$. Let's set $a_1 = 2$ and $a_2 = 3$.

$$2^0 = 1 ( mod \ 7) = 1$$  

$$2^1 = 2 ( mod \ 7) = 2$$  

$$2^2 = 4 ( mod \ 7) = 4$$  

$$2^3 = 8 ( mod \ 7) = 1$$

Uh oh! 20 is the same as 23. This means that 2 is not a primitive root of 7. Let’s try again with 3.

$$3^0 = 1 ( mod \ 7) = 1$$  

$$3^1 = 3 (mod \ 7) = 3$$  

$$3^2 = 9 (mod \ 7) = 2$$  

$$3^3 = 27 (mod \ 7) = 6$$  

$$3^4 = 81 ( mod \ 7) = 4$$  

$$3^5 = 243 ( mod \ 7) = 5$$  

$$3^6 = 1 (mod \ 7) = 1$$

Now let’s try a = 3.

$$3^0 = 1$$

$$3^1 = 3$$

$$3^2 = 2$$

$$3^3 = 6$$

$$3^4 = 4$$

$$3^5 = 5$$

$$3^6 = 1$$

Now we’ve got a cycle in these powers.

36 = 1, and 30 = 1. This is because we are using modulus it repeats into this cycle, so we can stop now. Unlike before where we reached 23 and it cycled, it's okay if it cycles here because for any prime number, p, and any number, a, such that \(a \ne 0 \ mod \ p\) and \(a \ne 1 \; mod \; p\) the consecutive powers of \(a\) may cover no more than p - 1 values modulo p. That is, we go from \(1, ..., p - 1\). When p is 7, the consecutive powers cover up to 6.

Discrete logarithms

$$a^b = c \; mod \; n$$

Such an equation means some numbers you can write it differently as:

$$log_a c = b \; mod \; n$$

Logarithms are the inverse of exponents, we’ve just inversed the sum here.

Now it’s a well-defined function, we can say in discrete terms that \(log_3 5 = 5 \ (mod \ 7)\) (looking at the table above).

if you use a non-primitive root number it becomes easier, as we have a smaller number of outcomes (because it repeats earlier), as seen below.

$$2^0 = 1 (mod \ 7) = 1$$  

$$2^1 = 2 ( mod \ 7) = 2$$  

$$2^2 = 4 ( mod \ 7) = 4$$  

$$2^3 = 8 ( mod \ 7) = 1$$

By using a primitive root, we get a much larger outcome, making it harder.

$$3^0 = 1 ( mod \ 7) = 1$$  

$$3^1 = 3 (mod \ 7) = 3$$  

$$3^2 = 9 ( mod \ 7) = 2$$  

$$3^3 = 27 ( mod \ 7) = 6$$  

$$3^4 = 81 ( mod \ 7) = 4$$  

$$3^5 = 243 ( mod \ 7) = 5$$  

$$3^7 = 1 ( mod \ 7) = 1$$

It is relatively easy to calculate exponentials modulo a prime, that is a, l, p calculate aⁱ mod p.

Exponentiation is a cheap operation. you can do it even for very large numbers while logarithm is a much more difficult function to calculate for large numbers.

To calculate exponentiation, you give number 2 and you respond to me what the answer is. that’s exponentiation, going from left to right.

$$3^0 = 1$$  

$$3^1 = 3$$  

$$3^2 = 2$$  

$$3^3 = 6$$  

$$3^4 = 4$$  

$$3^5 = 5$$

Logarithm is how to go back, from right to left. Logarithms are much harder than exponentiation.

Maths implemented

Let’s go back to seeing how Diffie-Hellman worked, but this time with a lot more knowledge of how mathematics works.

We have 2 people, Alice and Bob. Each of them has to agree in advance on some prime number q (publicly known number) and its primitive root a (publicly known).

1. Alice selects a random integer \(x_a < q\) and keeps it in secret

2. B selects a random integer \(x_b < q\) and keeps it in secret

3. Alice calculates the function left to right (exponentiation)

$$3^0 = 2$$  

$$3^1 = 3$$  

$$3^2 = 2$$  

$$3^3 = 6$$  

$$3^4 = 4$$  

$$3^5 = 5$$

and they choose one of the exponents, chosen randomly and kept in secret. Now Alice does \(y_a = a^{x a} mod q\) and sends it to Bob.

This example isn’t very impressive, and sometimes 3⁵ = 5 but for much larger numbers most things change everything, this is almost RSA encryption (the idea is the same, but it’s not quite the same as this is key exchange, not encryption).

Bob then does the same as Alice. Both Alice and Bob are now capable of calculating the shared key.

Alice calculates \(k = (y_b)^{x_a} \; mod \; q\)

Bob calculates \(k = (y_a)^{x_b} \; mod \; q\)

Now they have the same numbers, k is the common secret key.

$$(\alpha ^ {x_b})^{x_a} = (\alpha ^ {x_a})^{x_b}$$

This equation above is what makes it all work. The formulae are the same, but different. You get Alice to do one side of the formula, Bob does another side and they end up with the same number.

This really is the equation that puts it all together. Most of this blog post led up to this equation.

a and b are secret, and without these numbers, there is no easy way to repeat these computations because in to do it you need to know the secrets.

The above formula shows that the two methods are exactly equal. If you do the left equation, you get the same result as the right equation.

Conclusion

Diffie-Hellman-Merkle is a fascinating way of sharing a secret over an unsecured communications medium, by not sharing it at all over that medium.