Author: John

Impedance and Triangular Numbers

Posted on by John

A few days ago I wrote two posts about how to create a Smith chart, a graphical device used for impedance calculations. Then someone emailed me to point out the connection between the Smith chart and triangular numbers.

The Smith chart is the image of a rectangular grid in the right half-plane under the function

f(z) = (z − 1)/(z + 1).

If you subtract the values of f at consecutive integers, you get the reciprocal of a triangular number.

f(n) − f(n − 1) = 2/(n(n + 1)) = 1 / Tn

Or to put it another way,

f(n) − f(n − 1) = 1 / (1 + 2 + 3 + … + n).

In the first post on the Smith chart we showed that the function f maps vertical lines

in the z plane to circles in the w plane all touching at w = 1.

The circles are symmetric about the real axis and the diameter runs from f(n) to 1. The separation between the circles on the left side is thus

f(n) − f(n − 1) = 1 / Tn.

Number the circles starting from the outermost as 0, 1, 2, …. Then the maximum distance between circle n and circle n − 1 is 1 / Tn. You can see in the graph above that the distance between circle 0 and circle 1 is 1. It’s a little harder to see that the distance between circle 1 and circle 2 is 1/3. It looks like the distance between circles 2 and 3 is about half of that between circles 1 and 2, so it would be 1/6.

Related posts

Cross ratio

Posted on by John

The cross ratio of four points A, B, C, D is defined by

(A, B; C, D) = \frac{AC \cdot BD}{BC \cdot AD}

where XY denotes the length of the line segment from X to Y.

The idea of a cross ratio goes back at least as far as Pappus of Alexandria (c. 290 – c. 350 AD). Numerous theorems from geometry are stated in terms of the cross ratio. For example, the cross ratio of four points is unchanged under a projective transformation.

Complex numbers

The cross ratio of four (extended [1]) complex numbers is defined by

(z_1, z_2; z_3, z_4) = \frac{(z_3 - z_1)(z_4 - z_2)}{(z_3 - z_2)(z_4 - z_1)}

The absolute value of the complex cross ratio is the cross ratio of the four numbers as points in a plane.

The cross ratio is invariant under Möbius transformations, i.e. if T is any Möbius transformation, then

(T(z_1), T(z_2); T(z_3), T(z_4)) = (z_1, z_2; z_3, z_4)

This is connected to the invariance of the cross ratio in geometry: Möbius transformations are projective transformations on a complex projective line. (More on that here.)

If we fix the first three arguments but leave the last argument variable, then

T(z) = (z_1, z_2; z_3, z) = \frac{(z_3 - z_1)(z - z_2)}{(z_3 - z_2)(z - z_1)}

is the unique Möbius transformation mapping z1, z2, and z3 to ∞, 0, and 1 respectively.

The anharmonic group

Suppose (a, b; c, d) = λ ≠ 1. Then there are 4! = 24 permutations of the arguments and 6 corresponding cross ratios:

\lambda, \frac{1}{\lambda}, 1 - \lambda, \frac{1}{1 - \lambda}, \frac{\lambda - 1}{\lambda}, \frac{\lambda}{\lambda - 1}

Viewed as functions of λ, these six functions form a group, generated by

\begin{align*} f(\lambda) &= \frac{1}{\lambda} \\ g(\lambda) &= 1 - \lambda \end{align*}

This group is called the anharmonic group. Four numbers are said to be in harmonic relation if their cross ratio is 1, so the requirement that λ ≠ 1 says that the four numbers are anharmonic.

The six elements of the group can be written as

\begin{align*} f(\lambda) &= \frac{1}{\lambda} \\ g(\lambda) &= 1 - \lambda \\ f(f(\lambda)) &= g(g(\lambda) = z \\ f(g(\lambda)) &= \frac{1}{\lambda - 1} \\ g(f(\lambda)) &= \frac{\lambda - 1}{\lambda} \\ f(g(f(\lambda))) &= g(f(g(\lambda))) = \frac{\lambda}{\lambda - 1} \end{align*}

Hypergeometric transformations

When I was looking at the six possible cross ratios for permutations of the arguments, I thought about where I’d seen them before: the linear transformation formulas for hypergeometric functions. These are, for example, equations 15.3.3 through 15.3.9 in A&S. They relate the hypergeometric function F(a, b; c; z) to similar functions where the argument z is replaced with one of the elements of the anharmonic group.

I’ve written about these transformations before here. For example,

F(a, b; c; z) = (1-z)^{-a} F\left(a, c-b; c; \frac{z}{z-1} \right)

There are deep relationships between hypergeometric functions and projective geometry, so I assume there’s an elegant explanation for the similarity between the transformation formulas and the anharmonic group, though I can’t say right now what it is.

Related posts

[1] For completeness we need to include a point at infinity. If one of the z equals ∞ then the terms involving ∞ are dropped from the definition of the cross ratio.

Text case changes the size of QR codes

Posted on by John

Let’s make a QR code out of a sentence two ways: mixed case and upper case. We’ll use Python with the qrcode library.

>>> import qrcode
>>> s = "The quick brown fox jumps over the lazy dog."
>>> qrcode.make(s).save("mixed.png")
>>> qrcode.make(s.upper()).save("upper.png")

Here are the mixed case and upper case QR codes.

The QR code creation algorithm interprets the mixed case sentence as binary data but it interprets the upper case sentence as alphanumeric data.

Alphanumeric data, in the context of QR codes, comes from the following alphabet of 45 characters:

0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:

Since 45² = 2025 < 2048 = 211 two alphanumeric characters can be encoded in 11 bits. If text contains a single character outside this alphabet, such as a lower case letter, then the text is encoded as ISO/IEC 8859-1 using 8 bits per character.

Switching from mixed-case text to upper case text reduces the bits per character from 8 to 5.5, and so we should expect the resulting QR code to require about 30% fewer pixels. In the example above we go from a 33 × 33 grid down to a 29 × 29 grid, from 1089 pixels to 841.

Application to Bitcoin addressess

Bech32 encoding uses an alphabet of 32 characters while Base58 encoding uses an alphabet of 58 characters, and so the former needs about 17% more characters to represent the same data. But Bech32 uses a monocase alphabet, and base 58 does not, and so Bech32 encoding requires fewer QR code pixels to represent the same data as Base58 encoding.

(Bech32 encoding uses a lower case alphabet, but the letters are converted to upper case before creating QR codes.)

Related posts

An ancient generalization of the Pythagorean theorem

Posted on by John

Apollonius of Perga (c. 262 BC – c. 190 BC) discovered a theorem that generalizes the Pythagorean theorem but isn’t nearly as well known.

Let ABC be a general triangle, and let D be the midpoint of the segment AB. Let a be the length of the side opposite A and b the length of the side opposite B. Let m be the length of AD and h the length of the mediant, the line CD.

Apollonius’s theorem says

a² + b² = 2(m² + h²).

To see that this is a generalization of the Pythagorean theorem, apply Apollonius’ theorem to an isosceles triangle. Now a = b and ACD is a right triangle.

Apollonius’ theorem says

2b² = 2m² + 2h²

which is the Pythagorean theorem applied to ACD with each term doubled.

Mentally compute logs base 2

Posted on by John

The previous post required computing

\frac{128}{\log_2 5}

After writing the post, I thought about how you would mentally approximate log2 5. The most crude approximation would round 5 down to 4 and use log2 4 = 2 to approximate log2 5. That would be good enough for an order of magnitude guess, but we can do much better without too much more work.

Simple approximation

I’ve written before about the approximation

\log_2 x \approx 3\frac{x - 1}{x + 1}

for x between 1/√2 and √2. We can write 5 as 4 (5/4) and so

\begin{align*} \log_2 5 &= \log_2 4 (5/4) \\ &= \log_2 4 + \log_2 (5/4) \\ &\approx 2 + 3\frac{5/4 - 1}{5/4 + 1} \\ &= 2 + 3 \frac{1/4}{9/4} \\ &= 7/3 \end{align*}

How accurate is this? The exact value of log2 5 is 2.3219…. Approximating this number by 7/3 is much better than approximating it by just 2, reducing the relative error from 16% down to 0.5%.

Origin story

Where did the approximation

\log_2 x \approx 3\frac{x - 1}{x + 1}

come from?

I don’t remember where I found it. I wouldn’t be surprised if it was from something Ron Doerfler wrote. But how might someone have derived it?

You’d like an approximation that works on the interval from 1/√2 to √2 because you can always multiply or divide by a power of 2 to reduce the problem to this interval. Rational approximations are the usual way to approximate functions over an interval [1], and for mental calculation you’d want to use the lowest order possible, i.e. degree 1 in the numerator and denominator.

Here’s how we could ask Mathematica to find a rational approximation for us [2].

Simplify[
    N[
        ResourceFunction["EconomizedRationalApproximation"][
            Log[2, x], { x, {1/Sqrt[2], Sqrt[2]}, 1, 1}]]]

This returns

(2.97035 x − 2.97155) / (1.04593 + x)

which we round off to

(3 x − 3) / (1 + x).

The N function turns a symbolic result into one with floating point numbers. Without this call we get a complicated expression involving square roots and logs of rational numbers.

The Simplify function returns an algebraically equivalent but simpler expression for its argument. In our case the function finishes the calculation by removing some parentheses.

Related posts

[1] Power series approximations are easier to compute, but power series approximations don’t give the best accuracy over an interval. Power series are excellent at the point where they’re centered, but degrade as you move away from the center. Rational approximations spread the error more uniformly.

[2] I first tried using Mathematica’s MiniMaxApproximation function, but it ran into numerical problems, so I switched to EconomizedRationalApproximation.

Physical Keys and Encryption Keys

Posted on by John

A physical key, such as a house key, is a piece of metal with cuts of differing depths. Typically there may be around 6 cuts, with five different possible depths for each cut. This allows 56 = 15,625 possible keys.

Encryption keys, such as AES keys, are a string of bits, often 128 bits, for a total of 2128 possible keys.

How long would a physical key have to be to have the same level of security as an encryption key? We’d need to solve

5n = 2128

which means

n = 128 / log25 = 55.12.

So we’d need a key with around 55 notches.

metal key with 55 notches

This only takes into account combinatorial possibilities, not the difficulty of attacking a physical key or a binary key. There are incomparably more possibilities for binary keys, but encryption attacks can be automated and carried out remotely (unless a computer is air gapped). A physical lock can only be attacked in person. It takes a lock picker orders of magnitude more time to try a key than a password cracking program. On the other hand, locks aren’t picked by trying thousands of keys.

Related post: Measuring cryptographic strength in liters of boiling water

Freshman’s dream

Posted on by John

The “Freshman’s dream” is the statement

(x + y)p = xp + yp

It’s not true in general, but it is true mod p if p is a prime. It’s a cute result, but it’s also useful in applications, such as finite field computations in cryptography.

Here’s a demonstration of the Freshman’s dream in Python.

>>> p = 5
>>> [((x + y)**p - x**p - y**p) % p for x in range(p) for y in range(p)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Here’s an example using a prime too large for verify the results by looking at the output.

>>> import numpy as np
>>> p = 103
>>> v = [((x + y)**p - x**p - y**p) % p for x in range(p) for y in range(p)]
>>> np.all( np.array(v) == 0 )
True

You can use the same code to show that the Freshman’s dream is not true in general if p is not a prime, and it’s not true in general if p is a prime but the exponent is less than p.

Why and how Bitcoin uses Merkle trees

Posted on by John

Yesterday’s post looked at a recently mined Bitcoin block, the 920,994th block in the blockchain, and verified that it contains the hash of the previous block. This post will look at the same block and verify its Merkle tree root.

Before getting down to the bytes, we’ll back up and say what a Merkle tree is and why Bitcoin uses one.

What is a Merkle tree?

A Merkle tree is a binary tree. The leaves of the tree are labeled with a hash of the data associated with each leaf. The label of each interior node is the hash of the concatenation of the two child hashes. The label of the root of the tree is the Merkle tree root.

The smallest change to any data in the tree will change the Merkle tree root [1]. If you weren’t concerned with efficiency, you wouldn’t need a Merkle tree. You could simply concatenate all the data in the leaves and compute a hash. But the Merkle tree makes it possible to verify a node without having to verify the whole tree.

To see this, imagine starting at the bottom of the tree and working your way up to compute the Merkle root. You need the hash value of the node you’re interested in and its sibling. Then you can compute the label of the parent node. If you know the label of the parent’s sibling node (you could call it the aunt or uncle) then you can compute the label of the grandparent node, and so forth until you get to the root. If you get the expected value for the root, the data is correct.

How Bitcoin uses Merkle trees

Bitcoin makes a Merkle tree with the data for each transaction being a leaf node. Simple Payment Verification (SPV) lets you verify a transaction knowing only the hash of the transaction, the hash of its sibling, and the hashes of the siblings moving up the tree: the aunts, great aunts, great great aunts etc.

If a block has 2n transactions, you only need n hash values to verify a single transaction. The binary tree has n levels, and you need two hashes at the bottom, and one hash for each of the levels between the bottom and the top. So in a block of 1024 transactions, you need 10 hash values. Note that this saves space two ways: you don’t need transaction data per se, only hashes of transaction data, and the number of hashes you need is log2 of the number of transactions.

What if the number of transactions is not a power of 2? If there is an odd number of nodes at a given level of the Merkle tree, the last node is paired with itself.

For example, the block that we’ll examine in detail contains 1279 transactions. At the bottom of our Merlke tree there are effectively 1280 nodes, with the 1280th node being a duplicate of the 1279th. Moving up the tree we have 640 nodes, 320 nodes, 160 nodes, … 10 nodes, and 5 nodes. The 5th node is paired with itself, and no the next level up has 3 nodes. The third node is paired with itself, making 2 nodes on the next level, and then the root above that.

Down to the bytes

The command

xxd -l 80 920994.dat

gives a hex dump of the block header:

0000 002e c2df b57e f582 75c2 7a64 33c5
edfd dfc1 af6a b9ae 708c 0000 0000 0000
0000 0000 bb15 accc 8940 3811 0b9b e1cf
b125 c0fa a65e fb1b 2fa4 61ed 989f 8d6f
e41e 04cf 5522 ff68 21eb 0117 f2bc ab1a

This time we’re looking at bytes 37 through 68, highlighted in orange. This is the Merkle tree root.

A miner verifying the block would recompute the Merkle tree root and confirm that it matches the value given in the header.

A Bitcoin block does not contain a Merkle tree per se, only its root. The hash of the data for each transaction, what Bitcoin calls a txid, is redundant since it can be computed. And if it were included in the block, a miner would need to recompute it to verify that it is correct.

We can fetch a list of txids for a block by calling

https://blockstream.info/api/block/{block_hash}/txids

with the hash of the block we want, which in our case is

00000000000000000001c2f89cee9f8c2fe88b4a93c2c2b75192918fc438ca32

This returns a JSON string with 1279 hash values:

fc1d784c62600565d4b4fbfe9cd45a7abc5f1c3273e294fd2b44450c5c9b9e9a
d4bce41744156a8f0e6588e42efef3519904a19169212c885930e908af1457ec
7bc6428c7d023108910a458c99359a2664de7c02343d96b133986825297e518d
…
c9132f178830d0c7a781e246bb5c2b3f4a9686c3d2b6f046b892a073d340eaff

Note that the API call did not pull the txids from the block; it computed them. Presumably the server computed the list of txids once and cached the results rather than computing them when we called the API.

We can compute the Merkle tree root by concatenating pairs of txids and hashing the results. Since the number of transactions is odd, the last txid is paired with itself. So moving one level up the tree, the first node is labeled with the hash of

fc1…e9ad4b…7ec

and the last node is labeled with the hash of

c91…affc91…aff

We continue this process until we compute the Merkle tree root. Then we can confirm that it matches the value given in the header. As with the block hash in the previous post, the Merkle tree root is stored in the header in little endian form.

Related posts

[1] There is a vanishingly small chance that a change in the data would not change the root. With a 256-bit hash, the chances of a change in the data not changing the root are 1 in 2256.

How blocks are chained in a blockchain

Posted on by John

The high-level explanation of a blockchain says that each block contains a cryptographic hash of the previous block. That’s how the blocks are chained together.

That’s not exactly true, and it leaves out a lot of detail. This post will look in full detail at how Bitcoin blocks are chained together by inspecting the bits of two consecutive blocks. Looking at the low-level details reveals that some statements, like the paragraph above, are simplifications and half-truths.

For the purpose of this post, I downloaded two blocks that were added to the blockchain overnight, blocks 920993 and 920994, and saved the blocks in the binary files 920993.dat and 920994.dat.

Hashing headers

According to the simplistic description, the hash of block 920993 should be contained in block 920994. That’s not correct. We will see that the hash of the header of block 920993 is contained in block 920994 [1].

What exactly is the header?

You may hear that the header of a Bitcoin block is the first 80 bytes. That’s also not quite true. The first 4 bytes of a (production) Bitcoin block are the magic number 0xf9beb4d9. This is number chosen by Satoshi with no apparent significance, a random number unlikely to conflict with anything else. Blocks used in test versions of the blockchain begin with different magic numbers.

The next 4 bytes represent the size of the block as an unsigned integer in little endian layout. The magic number and the block size form a sort of pre-header 8 bytes long.

The API that I used to download the blocks does not include the pre-header, so the header is the first 80 bytes of the files I downloaded, though strictly speaking headers are bytes 9 through 89 of the full block.

We can see a hex dump of the header of block 920993 by running

xxd -l 80 920993.dat

which shows us the following.

00e0 ff3f e31d 6937 0e1c dba2 5321 5546
0ecc 00bf 678c a2e1 255e 0100 0000 0000
0000 0000 996f 2b91 fefc dc17 e530 6c70
9672 af27 4361 7608 1ded fde3 1157 10a5
200f 0f83 7022 ff68 21eb 0117 96f2 fbb6

How to hash?

OK, so we’re supposed to hash the header. What hash function should we apply? Bitcoin uses double SHA256,

SHA256²(header) = SHA256( (SHA256(header) )

We can compute this with openssl by running

head -c 80 920993.dat | openssl dgst -sha256 -binary | openssl dgst -sha256

Note that the first invocation of openssl dgst uses the option -binary, instructing the software to pass the raw bytes to the rest of the pipeline rather than display a text representation. The last part of the pipeline does not have that option because we want a human-readable representation at the end. The output is

c2dfb57ef58275c27a6433c5edfddfc1af6ab9ae708c00000000000000000000

Note that there are a lot of zeros on the end of the hash. That’s not a coincidence. More on that later.

Header of the next block

In the previous section we found the hash of block 920993, and we expect to see it inside the header of block 920994.

xxd -l 80 920994.dat

we can see that the header of block 920994 contains the following.

0000 002e c2df b57e f582 75c2 7a64 33c5
edfd dfc1 af6a b9ae 708c 0000 0000 0000
0000 0000 bb15 accc 8940 3811 0b9b e1cf
b125 c0fa a65e fb1b 2fa4 61ed 989f 8d6f
e41e 04cf 5522 ff68 21eb 0117 f2bc ab1a

The first 4 bytes (8 hex characters) are a version number, and following the version number we see the hash we were looking for.

Byte order

Why all the zeros in the hash of the block header? That’s a result of the proof of work problem that had to be solved in order to add block 920993 to the blockchain. Bitcoin miners tweak the details of the block [2] until they create a block whose hash begins with the required number of 0 bits [3].

But the hash value above doesn’t begin with zeros; it ends with zeros. What’s up with that?

The Bitcoin header and openssl dgst both display hashes in little endian order, i.e. the reverse of what you’d expect from a positional number system.

Related posts

[1] But if you only hash the header, couldn’t someone change the rest of the block? No, because the header contains the Merkle tree root. If someone changed a bit in the body of the block, that would change the Merkle tree root, which would change the header, which would change its hash.

[2] They don’t change the substance of the transactions, but they can change the order in which the transactions are included. And there’s a nonce value that they can change too. The only known way to produce a given number of zeros is by trial and error, and so this takes a lot of work. Having a block with the right leading zeros in its hash proves that you’ve put in the work, hence proof of work.

[3] This is another simplified half-truth. You don’t need to produce a certain number of leading zeros per se; you need to find a hash value less than a target value, and the target value is not in general an exact power of 2.

987654321 / 123456789

Posted on by John

I recently saw someone post [1] that 987654321/123456789 is very nearly 8, specifically 8.0000000729.

I wondered whether there’s anything distinct about base 10 in this. For example, would the ratio of 54321six and 12345six be close to an integer? The ratio is 4.00268, which is pretty close to 4.

What about a larger base? Let’s try base 16. The expression

0xFEDCBA987654321 / 0x123456789ABCDEF

in Python returns 14. The exact ratio is not 14, but it’s as close to 14 as a standard floating point number can be.

For a base b, let denom(b) to be the number formed by concatenating all the digits in ascending order and let num(b) be the number formed by concatenating all the digits in descending order.

\begin{align*} \text{num}(b) &= \sum_{k=1}^{b-1} kb^{k-1} \\ \text{denom}(b) &= \sum_{k=1}^{b-1} (b-k)b^{k-1} \end{align*}

Then for b > 2 we have

\frac{\text{num}(b)}{\text{denom}(b)} = b - 2 + \frac{b-1}{\text{denom}(b)}

The following Python code demonstrates [2] that this is true for b up to 1000.

num = lambda b: sum([k*b**(k-1) for k in range(1, b)])
denom = lambda b: sum([(b-k)*b**(k-1) for k in range(1, b)])

for b in range(3, 1001):
    n, d = num(b), denom(b)
    assert(n // d == b-2)
    assert(n % d == b-1)

So for any base the ratio is nearly an integer, namely b − 2, and the fractional part is roughly 1/bb−2.

When b = 16, as in the example above, the result is approximately

14 + 16−14 = 8 + 4 + 2 + 2−56

which would take 60 bits to represent exactly, but a floating point fraction only has 53 bits. That’s why our calculation returned exactly 14 with no fractional part.

 

[1] I saw @ColinTheMathmo post it on Mastodon. He said he saw it on Fermat’s Library somewhere. I assume it’s a very old observation and that the analysis I did above has been done many times before.

[2] Why include a script rather than a proof? One reason is that the proof is straight-forward but tedious and the script is compact.

A more general reason that I give computational demonstrations of theorems is that programs are complementary to proofs. Programs and proofs are both subject to bugs, but they’re not likely to have the same bugs. And because programs made details explicit by necessity, a program might fill in gaps that aren’t sufficiently spelled out in a proof.