Tech note: Spend-Time in Monero and Renewal Reward Processes

[b-g-goodell]

We model a single node's view of the blockchain to attain an estimate of expected spend-time of a given output on the Monero blockchain. We use the inter-transaction timing together with the number of spendable outputs to construct this estimate.

Preliminary stuff

We assume that transactions in the confirmed part of have non-negative real-valued timestamps consistent with the block ordering imposed on those transactions T[0] < T[1] < T[2] < ... and we define the inter-transaction or inter-renewal times S[i] = T[i] - T[i-1] for i >= 1. Assume inter-renewal times S[i] are independent and identically distributed by some cumulative distribution function F, and we assume without loss of generality that T[0] = 0 (by merely re-aligning our clocks).

For each real t > 0, define N(t) as the total number of transactions in the confirmed part of the blockchain that have ever been broadcast and confirmed before time t. Denote the number of outputs created in the transaction with time T[i] as P[i]. Denote the number of key images published in that transaction as Q[i]. We treat the sequence of T[i] as a renewal process and the sequences P[i], Q[i] as reward renewal processes.

Meat and potatoes results

The following is then justifiable using some starting theorems from Serfozo (Basics of Applied Stochastic Processes):

1. For a large i, T[i]/i converges to m almost surely.
2. For a large t, N(t)/t converges to 1/m almost surely.
3. The total number of outputs that were placed on the blockchain and confirmed before time t is PP(t) = P[1] + P[2] + ... + P[N(t)]. The total number of key images is QQ(t) = Q[1] + ... + Q[N(t)]. The total number of spendable outputs is R(t) = PP(t) - QQ(t). All of these are easily and publicly computable.
4. For large i, (P[1]+P[2]+...+P[T[i]])/i converges to the number of outputs per transaction, w, almost surely.
5. For large t, PP(t)/t converges to w/m almost surely, the number of outputs per unit time.
6. For large i, (Q[1] + ... + Q[T[i]])/i converges to the number of key images per transaction, v, almost surely.
7. For large t, QQ(t)/t converges to v/m almost surely, the number of key images per unit time.

One application of these ideas: Let's try to estimate expected spend-time. Set a sample size, k = 1, 2, .... Say confirmed transactions have timestamps T[0] = 0, T[1], T[2], ..., T[i], T[i+1], ..., say N(t) is the number of T[i] in the interval 0 <= T[i] < t, say the number of outputs created in transaction i is P[i], say the number of key images published in transaction i is Q[i], and say R(t) = P[1] + ... + P[N(t)] - Q[1] - ... - Q[N(t)] = PP(t) - QQ(t). A simple empirical estimate of expected spend-time in Monero is R(t)(T[i]-T[i-k])/k for sufficiently large k and t.

A wallet dev that wishes to mitigate the bias between ring member ages and empirical estimates of spend-times by tweaking their distribution could do the following:

1. Look at the amount of time T[i] - T[i-k] that has elapsed between the last k transactions, where k is some large number perhaps indicating several weeks worth of transactions.
2. Look at the number of spendable outputs at this moment, R(t).
3. Compute U = R(t)(T[i] - T[i-k])/k.
4. Generate ring members from some distribution with the same expectation as the value U computed in step 3.

Better and different estimates can and should be derived from the above information, but this is an okay first-order approximation. For example, replacing R(t) in step 3 with an average may improve the precision of this estimate. See below.

Problems with the above: We assume that the ordering of transactions imposed by timestamps T[i] coincides with the ordering of transactions imposed by the blockchain topology. In reality, transactions may be confirmed on the blockchain in one order while their timestamps provide a distinctly different order. I sort of implicitly assume we are willing to re-arrange transaction timestamps using the minimal number of moves in order to obtain two consistent orderings. Timestamps are in general not trustworthy and if we did not reject transactions with unusual timestamps, this method would have no merit. Due to our rejection of unusual timestamps, this method is rather robust for large values of k (where "large" is subjective).

Detection of Bloat Attack: Unfortunately, we cannot detect a bloat attack solely by tracking U. In the event of a bloat attack, transaction outputs become more and more numerous. This can occur either (i) due to more transactions per second but with the same number of inputs and outputs, (ii) due to transactions producing more outputs than they destroy inputs but with the same number of transactions per second, or (iii) a mix of these two.

A typical spam attack may combine these two by broadcasting a lot of transactions that create more outputs than key images. In this case, T[i] - T[i-k] begins to decrease while R(t) increases; this estimate of spend-time may be held constant by a careful attacker.

Note that in case (i), R(t) is roughly constant, the same number of outputs are being produced as are being destroyed, and so the only way that a bloat attack can be occurring is if transactions are more and more numerous, and therefore more tightly spaced: the k-inter-renewal time T[i] - T[i-k] decreases so our estimate of spend-time decreases. In this case, it appears that the economy is picking up. In case (ii), then the number of outputs being produced exceed the number of inputs being destroyed: R(t) is growing. In this case, the inter-renewal time roughly constant while the spend-time gets longer and longer; it appears that the economy is slowing down.

More notes to come but I wanted to get my thoughts down in a single location.