# Pseudo-deterministically compute a P2P private key to match a target set of custody subnets.

## Motivation
With PeerDAS, each node custodies a specific set of columns subnets.
The subnets to be custodied are determined based on the node's ID using the [get_custody_columns](https://github.com/ethereum/consensus-specs/blob/dev/specs/_features/eip7594/das-core.md#get_custody_columns) function.

The [get_custody_columns](https://github.com/ethereum/consensus-specs/blob/dev/specs/_features/eip7594/das-core.md#get_custody_columns) function can be divided into two parts:
1. Deterministically derive column subnets from the (randomly generated) node ID. For reference, see the [Prysm implementation](https://github.com/prysmaticlabs/prysm/blob/peerDAS/beacon-chain/core/peerdas/helpers.go#L74-L110), and
2. Deterministically derive columns from column subnets. For reference, see the [Prysm implementation](https://github.com/prysmaticlabs/prysm/blob/peerDAS/beacon-chain/core/peerdas/helpers.go#L48-L72).

The complete chain is as follows:

Private key (random number) ==> Public key ==> Node ID ==> Custody subnets

In order to ensure some privacy, a new private key is randomly chosen at each node start.

Assume the following:

- At start $n$, private key is $K_n$ and custody subnets are $S_n$.
- At start $n+1$, private key is $K_{n + 1}$ and custody subnets are $S_{n+1}$.

It's possible that $S_{n+1}$ has nothing in common with $S_n$. In such cases, the node must backfill all the columns corresponding to the new subnets it now custodies for the entire retention period. This can result in a massive amount of data that needs to be backfilled from the network, potentially at every restart.

To avoid pulling such a significant amount of data from peers, one strategy is:

- At the very first node start, choose a random private key and store the corresponding custody subnets.
- On subsequent starts, load the previously stored custody subnets and then attempt to find (using brute force) a private key that matches the target custody subnets.

## Amount of work needed for brute force
Among $s$ subnets, there are $\binom{s}{k} = \frac{s!}{k!(s-k)!}$ possible combinations for selecting a subset of k subnets.

Assuming each private key is sampled independently, and given:

- $s$ as the total number of subnets,
- $k$ as the number of custody subnets,
- $n$ as the number of trials, and
- $p$ as the probability of finding a private key matching the target custody subnets

we obtain the following formula:

$$
1 - \left(1-\binom{k}{s}\right)^n = p
$$

Extracting $n$, we get:

$$
n = \frac{ln(1 - p)}{ln\left(1-\binom{k}{s}\right)}
$$

In our model, we assume that the order does not matter.

Consider the following scenario:
- We aim to custody 4 subnets.
- The subnets returned by the [get_custody_columns](https://github.com/ethereum/consensus-specs/blob/dev/specs/_features/eip7594/das-core.md#get_custody_columns) function are in the order $[5, 10, 12, 4, ....]$ and
- Our brute force algorithm for 4 subnets finds private keys that, when used to compute the node ID and subsequently run the [get_custody_columns](https://github.com/ethereum/consensus-specs/blob/dev/specs/_features/eip7594/das-core.md#get_custody_columns) function, return the subnets in the order $[10, 4, 5, 12, ...]$

We consider this result acceptable because the set of subnets to custody matches our expectations, regardless of the order.

If we needed to ensure the specific order of subnets, we would replace $\frac{s!}{k!(s-k)!}$ with $\frac{s!}{k!}$, which would significantly increase the required brute force computation power.

## Results with $s=32$

How to read the following table?
- With 32 subnets, we need 3,438 brute-force iterations to have a 50% chance of finding a private key that matches 3 given subnets.
- With 32 subnets, we need 927,368 brute-force iterations to have a 99% chance of finding a private key that matches 27 given subnets.

| Custody count | Combinations count | 50% | 90% | 95% | 99% |
| ------------- | ------------------ | ----------- | ------------- | ------------- | ------------- |
| 0 | 1 | N/A | N/A | N/A | N/A |
| 1 | 32 | 22 | 73 | 94 | 145 |
| 2 | 496 | 343 | 1,141 | 1,484 | 2,282 |
| 3 | 4,960 | **3,438** | 11,420 | 14,857 | 22,839 |
| 4 | 35,960 | 24,925 | 82,800 | 107,725 | 165,600 |
| 5 | 201,376 | 139,583 | 463,684 | 603,267 | **927,368** |
| 6 | 906,192 | 628,124 | 2,086,583 | 2,714,707 | 4,173,166 |
| 7 | 3,365,856 | 2,333,033 | 7,750,169 | 10,083,202 | 15,500,337 |
| 8 | 10,518,300 | 7,290,730 | 24,219,280 | 31,510,009 | 48,438,559 |
| 9 | 28,048,800 | 19,441,946 | 64,584,748 | 84,026,694 | 129,169,495 |
| 10 | 64,512,240 | 44,716,477 | 148,544,921 | 193,261,398 | 297,089,841 |
| 11 | 129,024,480 | 89,432,955 | 297,089,845 | 386,522,799 | 594,179,689 |
| 12 | 225,792,840 | 156,507,670 | 519,907,225 | 676,414,895 | 1,039,814,451 |
| 13 | 347,373,600 | 240,781,035 | 799,857,286 | 1,040,638,321 | 1,599,714,572 |
| 14 | 471,435,600 | 326,774,263 | 1,085,520,606 | 1,412,294,869 | 2,171,041,211 |
| 15 | 565,722,720 | 392,129,120 | 1,302,624,741 | 1,694,753,861 | 2,605,249,481 |
| 16 | 601,080,390 | 416,637,177 | 1,384,038,744 | 1,800,675,920 | 2,768,077,487 |
| 17 | 565,722,720 | 392,129,120 | 1,302,624,741 | 1,694,753,861 | 2,605,249,481 |
| 18 | 471,435,600 | 326,774,263 | 1,085,520,606 | 1,412,294,869 | 2,171,041,211 |
| 19 | 347,373,600 | 240,781,035 | 799,857,286 | 1,040,638,321 | 1,599,714,572 |
| 20 | 225,792,840 | 156,507,670 | 519,907,225 | 676,414,895 | 1,039,814,451 |
| 21 | 129,024,480 | 89,432,955 | 297,089,845 | 386,522,799 | 594,179,689 |
| 22 | 64,512,240 | 44,716,477 | 148,544,921 | 193,261,398 | 297,089,841 |
| 23 | 28,048,800 | 19,441,946 | 64,584,748 | 84,026,694 | 129,169,495 |
| 24 | 10,518,300 | 7,290,730 | 24,219,280 | 31,510,009 | 48,438,559 |
| 25 | 3,365,856 | 2,333,033 | 7,750,169 | 10,083,202 | 15,500,337 |
| 26 | 906,192 | 628,124 | 2,086,583 | 2,714,707 | 4,173,166 |
| 27 | 201,376 | 139,583 | 463,684 | 603,267 | 927,368 |
| 28 | 35,960 | 24,925 | 82,800 | 107,725 | 165,600 |
| 29 | 4,960 | 3,438 | 11,420 | 14,857 | 22,839 |
| 30 | 496 | 343 | 1,141 | 1,484 | 2,282 |
| 31 | 32 | 22 | 73 | 94 | 145 |
| 32 | 1 | N/A | N/A | N/A | N/A |

Currently, a Prysm beacon node either custodians one subnet (full node) or 32 subnets (supernode), so there is no issue.

:::info
**NOTE:**

No iterations are needed when there are 0 custody subnets, as well as when we want to custody all existing subnets.

It can be observed that custodianship of a low or high number of subnets requires only a small number of iterations. However, custodying half of the subnets requires a significant number of iterations.
:::

## Issue #1: Increase custody requirement and subnet count
There is 128 data columns. With $s=32$, each subnet corresponds to $128/32=4$ columns. The current configuration requires custody of 1 subnet, which corresponds to 4 columns.

In the future, we may switch from 32 subnets to 64 or 128 subnets ([source](https://notes.ethereum.org/sFGCCOhYTjGbVH_lzItJnA?view#Increase-custody-requirement-and-subnet-count)).
To maintain the same custody ratio, with 64 subnets, we would need to custody 2 subnets, and with 128 subnets, we would need to custody 4 subnets.

| Subnet count | Minimum custody count | Combinations count | 50% | 90% | 95% | 99% |
| -------------| --------------------- | ------------------ | ----------- | ------------- | ------------- | ------------- |
| 32 | 1 | 32 | 22 | 73 | 94 | 145 |
| 64 | 2 | 2,016 | 1,397 | 4,641 | 6,038 | 9,282 |
| 128 | 4 | 10,668,000 | 7,394,494 | 24,563,977 | 31,958,470 | 49,127,953 |

- With the current configuration of 32 subnets and a minimum of 1 subnet to custody, we need 145 brute force operations to have a 99% chance of finding a matching private key.
- With a potential future configuration of 128 subnets and a minimum of 4 subnets to custody, we would need almost 50 million brute force operations to have a 99% chance of finding a matching private key.

## Issue #2: Introducing validator custody

With validator custody, the number of subnets to be custodied will depend on the number of validators attached ([source](https://notes.ethereum.org/sFGCCOhYTjGbVH_lzItJnA?view#Introducing-validator-custody)).

The first implication is that we will start to explore the entire range of custody counts from the previous tables. For example, with a configuration of 32 subnets and 16 subnets to be custodied, we need almost 3 billion brute force operations to have a 99% chance of finding a matching private key. This number increases significantly with configurations of 64 or, even worse, 128 subnets.

The second implication is that the number of validators attached can change after the beacon node has already started, because the beacon node does not know in advance how many validator clients will be attached or how many validators will be included in these clients.

This implies that from the start, we need to find a private key that matches all the subnets returned by the [get_custody_columns](https://github.com/ethereum/consensus-specs/blob/dev/specs/_features/eip7594/das-core.md#get_custody_columns) of the previous private key / node ID **in order**.

| Subnet count | Combinations count for all subnets in order |
| ------------ | ------------------------------------------- |
| 32 | $32! = 2^{117}$ |
| 64 | $64! >> 2^{256}$ |
| 128 | $128! >> 2^{256}$ |

We compare to $2^{256}$ because there are a total of $2^{256}$ possible private keys.

:::warning
**WARNING:**

For $s=64$ and $s=128$, the number of in-order subnet combinations exceeds the total number of possible private keys. This means that, regardless of the available computational power, most of the given in-order subnet combinations are associated with at most one private key. Consequently, if we have a private key that corresponds to a particular in-order set of subnets, it is highly likely that no other private key will produce the same in-order set of subnets.
(*Corollary*: Most in-order subnet combinations are not associated with any private key whatsoever.)

In my view, this poses a significant obstacle, preventing us from generating a new random private key with each reboot.
:::