Monero subaddresses

Monero has a way of generating new addresses analogous to the way HD wallets generate new addresses for Bitcoin. In both cases, the recipient’s software can generate new addresses to receive payments that others cannot link back to the recipient.

Monero users have two public/private keys pairs: one for viewing and one for spending. Let Ks and ks be the public and private spending keys, and let Kv and kv be the public and private viewing keys. Then the user’s ith subaddress is given by

\begin{align*} K^s_i &= K^s + H(k^v, i) G \\ K^v_i &= k^v K^s_i \end{align*}

Here G is a generator for the elliptic curve Ed25519 and H is a hash function. The hash function output and kv are integers; the public keys, denoted by capital Ks with subscripts and superscripts, are points on Ed25519. The corresponding private keys are

\begin{align*} k^s_i &= k^s + H(k^v, i) \\ k^v_i &= k^v + k^s_i \end{align*}

As with hierarchical wallets, the user scans the blockchain to see which of his addresses have received funds.

A user may choose to give a different subaddress for each transaction for added security, or to group transactions for accounting purposes.

Note that in addition to subaddresses, Monero uses stealth addresses. An important difference between subaddresses and stealth addresses is that recipients generate subaddresses, and senders generate stealth addresses. Someone could send you money to the same subaddress twice, failing to create a new stealth address. This is not possible if you give the sender a different subaddress each time.

Related posts

A triangle whose interior angles sum to zero

Spherical geometry

In spherical geometry, the interior angles of a triangle add up to more than π. And in fact you can determine the area of a spherical triangle by how much the angle sum exceeds π. On a sphere of radius 1, the area equals the triangle excess

Area = E = interior angle sum − π.

Small triangles have interior angle sum near π. But you could, for example, have a triangle with three right angles: put a vertex on the north pole and two vertices on the equator 90° longitude apart.

Hyperbolic geometry

In hyperbolic geometry, the sum of the interior angles of a triangle is always less than π. In a space with curvature −1, the area equals the triangle defect, the difference between π and the angle sum.

Area = D = π − interior angle sum.

Again small triangles have an interior angle sum near π. Both spherical and hyperbolic geometry are locally Euclidean.

The interior angle sum can be any value less than π, and so as the angle sum goes to 0, the triangle defect, and hence the area, goes to π. Since the minimum angle sum is 0, the maximum area of a triangle is π.

The figure below has interior angle sum 0 and area π in hyperbolic geometry.

Strictly speaking this is an improper triangle because the three hyperbolic lines (i.e. half circles) don’t intersect within the hyperbolic plane per se but at ideal points on the real axis. But you could come as close to this triangle as you like, staying within the hyperbolic plane.

Note that the radii of the (Euclidean) half circles doesn’t change the area. Any three semicircles that intersect on the real line as above make a triangle with the same area. Note also that the triangle has infinite perimeter but finite area.

Related posts

A circle in the hyperbolic plane

Let ℍ be the upper half plane, the set of complex real numbers with positive imaginary part. When we measure distances the way we’ve discussed in the last couple posts, the geometry of ℍ is hyperbolic.

What is a circle of radius r in ℍ? The same as a circle in any geometry: it’s the set of points a fixed distance r from a center. But when you draw a circle using one metric, it may look very different when viewed from the perspective of another metric.

Suppose we put on glasses that gave us a hyperbolic perspective on ℍ, draw a circle of radius r centered at i, then take off the hyperbolic glasses and put on Euclidean glasses. What would our drawing look like?

In the previous post we gave several equivalent expressions for the hyperbolic metric. We’ll use the first one here.

d(z_1, z_2) = 2\, \text{arcsinh}\left( \frac{|z_1 - z_2|}{2\, \sqrt{\Im z_1\, \Im z_2}} \right)

Here the Fraktur letter ℑ stands for imaginary part. So the set of points in a circle of radius r centered at i is

\{ x + iy \mid d(x + iy, i) = r \}

Divide the expression for d(xiyi) by 2, apply sinh, and square. This gives us

\sinh^2\left(\frac{r}{2}\right) = \frac{x^2 + (y-1)^2}{4y}

which is an equation for a Euclidean circle. If we multiply both sides by 4y and complete the square, we find that the center of the circle is (0, cosh(r)) and the radius is sinh(r).

Summary so far

So to recap, if we put on our hyperbolic glasses and draw a circle, then switch out these glasses for Euclidean glasses, the figure we drew again looks like a circle.

To put it another way, a hyperbolic viewer and a Euclidean viewer would agree that a circle has been draw. However, the two viewers would disagree where the center of the circle is located, and they would disagree on the radius.

Both would agree that the center is on the imaginary axis, but the hyperbolic viewer would say the imaginary part of the center is 1 and the Euclidean viewer would say it’s cosh(r). The hyperbolic observer would say the circle has radius r, but the Euclidean observer would say it has radius sinh(r).

Small circles

For small r, the hyperbolic and Euclidean viewpoints nearly agree because

cosh(r) = 1 + O(r²)

and

sinh(r) = r + O(r³)

Big circles

Note that if you asked a Euclidean observer to draw a circle of radius 100, centered at (0, 1), he would say that the circle will extend outside of the half plane. A hyperbolic observer would disagree. From his perspective, the real axis is infinitely far away and so he can draw a circle of any radius centered at any point and stay within the half plane.

Moving circles

Now what if we looked at circles centered somewhere else? The hyperbolic metric is invariant under Möbius transformations, and so in particular it is invariant under

zx0 + y0 z.

This takes a circle with hyperbolic center i to a circle centered at x0i y0 without changing the hyperbolic radius. The Euclidean center moves from cosh(r) to y0 cosh(r) and the radius changes from sinh(r) to y0 sinh(r).

Equal things that don’t look equal

The previous post described a metric for the Poincaré upper half plane. The development is geometrical rather than analytical. There are also analytical formulas for the metric, at least four that I’ve seen.

\begin{align*} d(z_1, z_2) &= 2\, \text{arcsinh}\left( \frac{|z_1 - z_2|}{2\, \sqrt{\Im z_1\, \Im z_2}} \right) \\ &= \text{arccosh}\left(1 + \frac{|z_1 - z_2|^2}{ 2\, \Im z_1 \, \Im z_2} \right) \\ &= 2 \, \text{arctanh}\left| \frac{z_1 - z_2}{z_1 - \overline{z}_2}\right| \\ &= 2\, \log\left( \frac{|z_2 - z_1| + |z_2 - \overline{z}_1|}{2\, \sqrt{\Im z_1\, \Im z_2}} \right) \\ \end{align*}

It’s not at all obvious that the four equations are equivalent, or that any of them matches the expression in the previous post.

There are equations for expressing arcsinh, arccosh, and arctanh in terms of logarithms and square roots. See the bottom of this post. You could use these identities to show that the metric expressions are equal, but I don’t know of a cleaner way to do this than lots of tedious algebra.

Before diving into the calculations, you might want some assurance that you’re trying to prove the right thing. Here’s some Python code that generates random pairs of complex numbers and shows that the four expressions give he same distance.

import numpy as np

def d1(z1, z2):
    return 2*np.arcsinh( abs(z1 - z2) / (2*(z1.imag * z2.imag)**0.5) )
def d2(z1, z2):
    return np.arccosh(1 + abs(z1 - z2)**2 / (2*z1.imag * z2.imag) )
def d3(z1, z2):
    return 2*np.arctanh( abs( (z1 - z2)/(z1 - np.conjugate(z2)) ) )
def d4(z1, z2):
    return 2*np.log( (abs(z2 - z1) + abs(z2 - np.conjugate(z1)))/(2*np.sqrt(z1.imag * z2.imag)) )

np.random.seed(20251127)
for n in range(100):
    z1 = np.random.random() + 1j*np.random.random()
    z2 = np.random.random() + 1j*np.random.random()
    assert( abs(d1(z1, z2) - d2(z1, z2)) < 1e-13 )
    assert( abs(d2(z1, z2) - d3(z1, z2)) < 1e-13 )
    assert( abs(d3(z1, z2) - d4(z1, z2)) < 1e-13 )

Perhaps you’re convinced that the four expressions are equal, but why should any of them be equivalent to the definition in the previous post?

The previous post pointed out that the metric is invariant under Möbius transformations. We can apply such a transformation to move any pair of complex numbers to the imaginary axis. There you can see that the cross ratio reduces to the ratio of the two numbers.

More generally, if two complex numbers have the same real part, the distance between them is the log of the ratio of their imaginary parts. That is, if

\begin{align*} z_1 &= x + iy_1 \\ z_2 &= x + iy_2 \end{align*}
then

d(z_1, z_2) = \log \frac{y_2}{y_1}

if x, y1, and y2 are real and y2 > y1 > 0.

Here’s a little Python code that empirically shows that this gives the same distance as one of the expressions above.

def d5(z1, z2):
    assert(z1.real == z1.real)
    return abs( np.log( z1.imag / z2.imag ) )

for n in range(100):
    x = np.random.random()
    z1 = x + 1j*np.random.random()
    z2 = x + 1j*np.random.random()
    assert( abs(d1(z1, z2) - d5(z1, z2)) < 1e-13 )

So now we have five expressions for the metric, all of which look different. You could slug out a proof that they’re equivalent, or get a CAS like Mathematica to show they’re equivalent, but it would be more interesting to find an elegant equivalence proof.

Update: Although the four expressions at the top of the post are analytically equal, they are not all equally accurate for numerical evaluation. I did a little testing and found the arctahn method to be the least accurate and the rest roughly equally accurate.

Hyperbolic metric

One common model of the hyperbolic plane is the Poincaré upper half plane ℍ. This is the set of points in the complex plane with positive imaginary part. Straight lines are either vertical, a set of points with constant imaginary part, or arcs of circles centered on the real axis. The real axis is not part of ℍ. From the perspective of hyperbolic geometry these are ideal parts, infinitely far away, and not part of the plane itself.

We can define a metric on ℍ as follows. To find the distance between two points u and v, draw a line between the two points, and let a and b be the ideal points at the end of the line. By a line we mean a line as defined in the geometry of ℍ, what we would see from our Euclidean perspective as a half circle or a vertical line. Then the distance between u and v is defined as the absolute value of the log of the cross ratio (u, v; ab).

d(u, v) = |\log (u, v; a, b) | = \left| \log \frac{|a - u|\,|b - v|}{|a - v|\,|b - u|} \right|
Cross ratios are unchanged by Möbius transformations, and so Möbius transformations are isometries.

Another common model of hyperbolic geometry is the Poincaré disk. We can use the same metric on the Poincaré disk because the Möbius transformation

z \mapsto \frac{z - i}{z + i}

maps the upper half plane to the unit disk. This is very similar to how the Smith chart is created by mapping a grid in the right half plane to the unit disk.

Update: See the next post for four analytic expressions for the metric, direct formulas involving u and v but not the ideal points a and b.

TV tuned to a dead channel

The opening line of William Gibson’s novel Neuromancer is famous:

The sky above the port was the color of a television, tuned to a dead channel.

When I read this line, I knew immediately what he meant, and thought it was a brilliant line. Later I learned that younger readers didn’t know what he was saying.

TV tuned to a dead channel circa 1960

My mind went to an old black-and-white television, one that received analog broadcasts, and that displayed “snow” when tuned to a channel that had no broadcast signal. Someone whose earliest memories of television are based on digital color broadcast might imagine the sky above the port was solid blue rather than crackly gray.

Gibson discusses how his book has aged in a preface to a recent edition. He says that science fiction that is too prescient would be received poorly.

Imagine a novel from the sixties whose author had somehow fully envisioned cellular telephony circa 2004, and had worked it, exactly as we know it today, into the fabric of her imaginary future. Such a book would have seemed highly peculiar in the sixties … in ways that would quickly overwhelm the narrative.

He then goes on to say

I suspect that Neuromancer owes much of its shelf life to my almost perfect ignorance of the technology I was extrapolating from. … Where I made things up from whole cloth, the colors remain bright.

I find it odd that many judge a work of science fiction by what it “got right.” I don’t read science fiction as a forecast;  read it to enjoy a story. I don’t need a book to be prescient, but until reading Gibson’s remarks it hadn’t occurred to me that fiction that is too prescient might not be enjoyable fiction, at least for its first readers.

How stealth addresses work in Monero

Suppose Alice runs a confidential restaurant. Alice doesn’t want there to be any record of who visited her restaurant but does want to get paid for her food. She accepts Monero, and instead of a cash register there are two QR codes on display, one corresponding to her public view key A and the other corresponding to her public spend key S.

How Bob buys his burger

A customer Bob walks into the restaurant and orders a burger and fries. When Bob pays Alice, here’s what’s going on under the hood.

Bob is using software that generates a random integer r and multiplies it by a point G on an elliptic curve, specifically ed25519, obtaining the point

R = rG

on the curve. The software also multiplies Alice’s view key A, a point on the same elliptic curve, by r, then runs a hash function H on the produce rA that returns an integer k.

kH(rA).

Finally, Bob’s software computes the point

PkGS

and sends Alice’s cash register, i.e. her crypto wallet, the pair of points (PR). The point P is a stealth address, an address that will only be used this one time and cannot be linked to Alice or Bob [1]. The point R is additional information that helps Alice receive her money.

How Alice gets paid

Alice and Bob share a secret: both know k. How’s that?

Alice’s public view key A is the product of her private view key a and the group generator G [2]. So when Bob computes rA, he’s computing r(aG). Alice’s software can multiply the point R by a to obtain a(rG).

rAr(aG) = a(rG) = aR.

Both Alice and Bob can hash this point—which Alice thinks of as aR and Bob thinks of as rA—to obtain k. This is ECDH: elliptic curve Diffie-Hellman key exchange.

Next, Alice’s software scans the blockchain for payments to

PkGS.

Note that P is on the blockchain, but only Alice and Bob know how to factor P into kGS because only Alice and Bob know k. And only Alice can spend the money because only she knows the private key s corresponding to the public spend key S where

SsG.

She knows

PkGsG = (ks)G

and so she has the private key (ks) corresponding to P.

Related posts

[1] Bob sends money to the address P, so there could be some connection between Bob and P on the Monero blockchain. However, due to another feature of Monero, namely ring signatures, someone analyzing the blockchain could only determine that Bob is one of 16 people who may have sent money to the address P, and there’s no way to know who received the money. That is, there is no way, using only information on the blockchain, who received the money. A private investigator who saw Bob walk into Alice’s restaurant would have additional information outside the blockchain.

[2] The key assumption of elliptic curve cryptography is that it’s computationally infeasible to “divide” on an elliptic curve, i.e. to recover a from knowledge of G and aG. You could recover a by brute force if the group were small, but the elliptic curve ed25519 has on the order of 2255 points, and a is some integer chosen randomly between 1 and the size of the curve.

Weddle integration rule

I was reading about Shackleton’s incredible expedition to Antarctica, and the Weddell Sea features prominently. That name sounded familiar, and I was trying to remember where I’d heard of Weddell in math. I figured out that it wasn’t Weddell exactly but Weddle I was thinking of.

The Weddell Sea is named after James Weddell (1787–1834). Weddle’s integration rule is named after Thomas Weddle (1817–1853).

I wrote about Weddle’s integration rule a couple years ago. Weddle’s rule, also known as Bode’s rule, is as follows.

\begin{align*} \int_{x_0}^{x_6} f(x)\, dx = \frac{h}{140}&\Big(41 f(x_0) + 216f(x_1) + 27 f(x_2) +272 f(x_3) \\ &+ 27 f(x_4) + 216 f(x_5) + 41 f(x_6) \Big) \\ &-\frac{9 f^{(8)}(\xi) h^9}{1400} \end{align}

Let’s try this on integrating sin(x) from 1 to 2.

If we divide the interval [1, 2] into 6 subintervals, h = 1/6. The 8th derivative of sin(x) is also sin(x), so it is bounded by 1. So we would expect the absolute value of the error to be bounded by

9 / (69 × 1400).

Let’s see what happens in practice.

import numpy as np

x = np.linspace(1, 2, 7)
h = (2 - 1)/6
weights = (h/140)*np.array([41, 216, 27, 272, 27, 216, 41])
approx = np.dot(weights, np.sin(x))
exact = np.cos(1) - np.cos(2)
print("Error:          ", abs(approx - exact) )
print("Expected error: ", 9/(1400*6**9))

Here’s the output:

Error:           6.321198009473505e-10
Expected error:  6.379009079626363e-10

Related posts

Solving H_n = 100

The previous post includes code for solving the equation

Hn = m

i.e. finding the value of n for which the nth harmonic number is the closest to m. It works well for small values of m. It works for large m in the sense that the solution is very close to m, but it’s not necessarily the best solution.

For example, set m = 100. The code returns

n = 15092688622113830917200248731913020965388288

and indeed for that value of n,

Hn − 100 ≈ 3 × 10−15

and that’s as much as we could hope for with IEEE 754 floats.

The approximation

n = exp(m −γ)

is very good for large values of m. Using Mathematica we can find the exact value of n.

f[n_] := Log[n] + EulerGamma + 1/(2 n) - 1/(12 n^2)
n = Floor[Exp[100 - EulerGamma]];
N[f[n], 50]
100.00000000000000000000000000000000000000000000900
N[f[n - 1], 50]
99.999999999999999999999999999999999999999999942747

So

n = 15092688622113788323693563264538101449859497

A similar process can find the solution to

Hn = 1000

is

n = 110611511026604935641074705584421138393028001852577373936470952377218354575172401275457597579044729873152469512963401398362087144972181770571895264066114088968182356842977823764462179821981744448731785408629116321919957856034605877855212667092287520105386027668843119590555646814038787297694678647529533718769401069269427475868793531944696435696745559289326610132208504257721469829210704462876574915362273129090049477919400226313586033

For this calculation you’ll need to increase the precision from 50 digits to something like 500 digits, something more than 435 because n is a 435-digit number.

In case you’re wondering whether my function for computing harmonic numbers is accurate enough, it’s actually overkill, with error O(1/120n4).

Closest harmonic number to an integer

I mentioned in the previous post that the harmonic numbers Hn are never integers for n > 1. In the spirit of that post, I’d like to find the value of n such that Hn is closest to a given integer m.

We have two problems to solve. First, how do we accurately and efficiently compute harmonic numbers? For small n we can directly implement the definition. For large n, the direct approach would be slow and would accumulate floating point error. But in that case we could use the asymptotic approximation

H_n \approx \log n + \gamma + \frac{1}{2n} - \frac{1}{12n^2}

from this post. As is often the case, the direct approach gets worse as n increases, but the asymptotic approximation gets better as n increases. Here γ is the Euler-Mascheroni constant.

The second problem to solve is how to find the value of n so that Hn comes closest to m without trying too many possible values of n? We can discard the higher order terms above and see that n is roughly exp(m − γ).

Here’s the code.

import numpy as np

gamma = 0.57721566490153286

def H(n):
    if n < 1000:
        return sum([1/k for k in range(1, n+1)])
    else:
        n = float(n)
        return np.log(n) + gamma + 1/(2*n) - 1/(12*n**3)
    
# return n such that H_n is closest harmonic number to m
def nearest_harmonic_number(m):
    
    if m == 1:
        return 1

    guess = int(np.exp(m - gamma))    
    if H(guess) < m:
        i = guess
        while H(guess) < m: guess += 1 j = guess else: j = guess while H(guess) > m:
            guess -= 1
        i = guess
        
    x = np.array([abs(H(k) - m) for k in range(i, j+1)])
    return i + np.argmin(x)

We can use this, for example, to find the closest harmonic number to 10.

>>> nearest_harmonic_number(10)
12366
>>> H(12366)
9.99996214846655

I wrote the code with integer values of m in mind, but the code works fine with real numbers. For example, we could find the harmonic number closest to √20.

>>> nearest_harmonic_number(20**0.5)
49
>>> H(49)**2
20.063280462918804

Related posts