最近有人在我的 SolVantityCL 的项目里 提了一个 Issue ，说了一个很有意思的问题：某字符串在分别作为前缀和后缀时，找到满足要求的地址耗费的时间是不一样的，差距还很大。

我一开始没太把这个问题当一回事，只是简单回复了一下他，说这个是算法的问题，因为 Solana 即使私钥连续递增，但公钥的变化仍然是无序的，因此按照概率去预估耗费的时间可能会有误差。但是他又回复说他使用 Solana 的官方 Keygen 命令发现同样的字符串在前缀和后缀的难易程度的差距并没有使用我的工具表现的差距这么大。

这就有很有意思了，也引起了我的兴趣。所以我专门花了点时间研究了一下这个问题的背后原因。因为我很确认，我使用的 ED25519 密钥生成的算法是正确的，不然的话公钥也不会和 Solana 的 Cli 算出相同的结果了。正因如此，这才是我感觉到奇怪的地方。

所以我去翻了一下 Solana-Keygen 的源码，有收获，但和我预想的并不一样。我以为是它的随机数种子获取的方式的和我不一样，但查看之后我发现它用的仍然是从系统的随机数种子取的字节（rand_os::OsRng）；不过我发现它还额外包括了 剪枝操作 。这个操作本身是在用户指定某些前缀的情况下，在匹配前缀前，就过滤掉某些非法的地址。这样能稍微省略掉一些前缀 / 后缀模式匹配的时间。但是，这仍然无法省略掉通过私钥派生出公钥的过程。

举个例子：当用户指定的前缀是 a 时，那么如果私钥生成的公钥的地址是 44 位的，那么就意味着不需要进行后面的前缀匹配操作了，因为用户指定的前缀是 a 时，生成的公钥地址一定是 43 位的——很神奇对吧？接下来本文就深入分析一下，看看究竟是什么原因影响了不同字符前缀匹配的概率。

在此之前，我想先列一下 base58 所用到的所有字符集合：123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz

公钥中隐藏的规则限制

ED25519 所使用的公钥是 32 字节的长度，那么它理论最大值就是所有字节全部都是 255 的情况：

Pj4+IGZyb20gYmFzZTU4IGltcG9ydCBiNThlbmNvZGUKPj4+IG1heF9ieXRlcyA9ICgyKioyNTYtMSkudG9fYnl0ZXMoMzIsICdsaXR0bGUnKQo+Pj4gYjU4ZW5jb2RlKG1heF9ieXRlcykKYidKRUtOVm5rYm8zam1hNW5SRUJCSkNEb1hGVmVLa0Q1NlYzeEtydlJtV3hGRycKPj4+IGxlbihiNThlbmNvZGUobWF4X2J5dGVzKSkKNDQ=

这个公钥坐标经过 base58 编码之后地址长度是 44 位，首字符是 J，这意味着在 44 位长度的地址里，不会出现 J 往后的字符了：K，L,…,Z。因为如果出现了 J 之后的字符，那么 44 地址的长度通过 base58 解码之后的字节数就要超过 32 了。

这也意味着，在 K-Z，a-z 的字符里，如果你想要它在地址的首字符出现，那么只能是 43 位长度的地址。

Base58 字符总长度	数值区间	占 32 字节全集合的概率
44 字符	$$58^{43} \leq N < 2^{256}$$	≈ 94.20 %
43 字符	$$58^{42} \le N < 58^{43}$$	≈ 5.70 %
≤ 42 字符	$$N < 58^{42}$$	≈ 0.10 %

而 43 位长度的地址空间，与 44 位的地址空间相比，占比只有 44 位的 6%。至于 J —— 理论最大值正好是 J 开头的，所以它会比 43 字符的地址多一部份的空间，但是又比 44 字符的地址少一部份空间，因为这个理论最大的地址第二位是 E，所以也不能取到 E 之后的字符空间，也就只能取 0 到 E 之间的 14 个字符，因为首字符 J 的概率是也就是其他的 44 字符空间的 14 / 58 = 24.1% 左右。

实际的测试

接下我会用代码实际模拟一下各字符的出现频率。毕竟刚刚所说的公钥理论最大值其实并不在椭圆曲线上，因此还是需要结合实际的测试结果来具体分析。

ZnJvbSBuYWNsLmJpbmRpbmdzIGltcG9ydCBjcnlwdG9fc2lnbl9zZWVkX2tleXBhaXIKaW1wb3J0IGJhc2U1OCwgc2VjcmV0cywgY29sbGVjdGlvbnMKCmNvdW50ZXJfc3RhcnRzID0gY29sbGVjdGlvbnMuQ291bnRlcigpCmNvdW50ZXJfc2Vjb25kcyA9IGNvbGxlY3Rpb25zLkNvdW50ZXIoKQpjb3VudGVyX2JvdGggICAgPSBjb2xsZWN0aW9ucy5Db3VudGVyKCkKY291bnRlcl9lbmRzICAgID0gY29sbGVjdGlvbnMuQ291bnRlcigpCgpkZWYgaW5jcmVhc2Vfa2V5MzIocHJpdmF0ZV9rZXkpIC0+IGJ5dGVzOgogICAgY3VycmVudF9udW1iZXIgPSBpbnQoYnl0ZXMocHJpdmF0ZV9rZXkpLmhleCgpLCAxNikKICAgIG5leHRfbnVtYmVyID0gY3VycmVudF9udW1iZXIgKyAxCiAgICBuZXdfa2V5MzIgPSBsaXN0KG5leHRfbnVtYmVyLnRvX2J5dGVzKDMyLCAiYmlnIikpCiAgICByZXR1cm4gYnl0ZXMobmV3X2tleTMyKQoKcHJpdmF0ZV9rZXkgID0gc2VjcmV0cy50b2tlbl9ieXRlcygyOSkgKyBiJ1x4MDAnICogMwpmb3IgXyBpbiByYW5nZSg1XzAwMF8wMDApOgogICAgcGssIF8gPSBjcnlwdG9fc2lnbl9zZWVkX2tleXBhaXIocHJpdmF0ZV9rZXkpCiAgICBhZGRyICA9IGJhc2U1OC5iNThlbmNvZGUocGspLmRlY29kZSgpCiAgICBjb3VudGVyX3N0YXJ0c1thZGRyWzBdXSAgKz0gMQogICAgY291bnRlcl9zZWNvbmRzW2FkZHJbMV1dICs9IDEKICAgIGNvdW50ZXJfZW5kc1thZGRyWy0xXV0gICArPSAxCiAgICBpZiBhZGRyWzBdID09IGFkZHJbMV06CiAgICAgICAgY291bnRlcl9ib3RoW2Yne2FkZHJbMF19e2FkZHJbMV19J10gKz0gMQogICAgcHJpdmF0ZV9rZXkgPSBpbmNyZWFzZV9rZXkzMihwcml2YXRlX2tleSk=

至于在 43 的地址空间里，想要判断首字符落在 K - z 的概率也要先除开落在 1 - J 的里面的情况，首字符概率大概就是 5.7% / 58 = 0.1%， 而首字符在 2 - J 的概率分两种情况：

1. 44 地址空间里，字符 1 的概率是固定的 1 / 256，那么其他字符的平均就是$$\frac{0.942 - \frac{1}{256}}{16.241}$$，分母是 16.241 是因为 J 开头的地址空间与其他的字符相比并不完整；
2. 43 地址空间里，大概也是 5.7% / 58 = 0.1%。

因此首字符落在 K - z 区间的概率理论上相当于是 2 - J 区间里的 1.70%。

Pj4+IHByaW50KGNvdW50ZXJfc3RhcnRzKQpDb3VudGVyKHsnOSc6IDI5NjcxMCwgJ0MnOiAyOTU3NDMsIC4uLiwgJzInOiAyODk3MjQsICdKJzogNzE4MjMsICcxJzogMTk1NDEsICdyJzogNTE5MiwgIC4uLiwgJ1QnOiA0ODk0fSk=

比如我们这里选用 r 和 C 做对比：5192 / 295743 = 1.76 %，非常接近我们对于概率的计算了。

而对于 J 和 C 对比：71823 / 295743 = 24.3%，同样非常符合我们的期望。

非首字符的情况

Pj4+IHByaW50KGNvdW50ZXJfc2Vjb25kcykKQ291bnRlcih7JzMnOiA5NTM1OCwgLi4uLCAnMSc6IDg5ODIxLCAuLi4sICdtJzogODM4NjF9KQ==

对于非首字符的情况，比如第二个字符，出现的频率都是近似相同的，这也说明了 ED25519 的公钥分布还是挺均匀的。

也就是说，地址前缀的碰撞难易程度只和首字符有关——其实根本原因就是 32 字节能表达的数（$$2^{256}$$）和 44 位长度的 base58 编码能表达的数（$$58^{44}$$）不对等而已。如果这俩能表达的数正好相等的话，那么也不存在不同前缀的字符难易程度在 J 前后出现分水岭的情况了。

counter_ends 的结果我就不放出来了，大家可以自己测试一下看看，结果是和 counter_seconds 类似的，每个字符出现频率都是接近的。

字符 1 不一样吗？

你可能注意到了，首字符是 1 出现的次数其实远比 K - z 出现的次数要多，但是又远小于 2 - H。如果通过统计数据来计算频率的话 19541 / 5000000 = 0.0039082，正好是和 1 / 256 = 0.00391 的概率接近。

这也是 base58 编码里的特殊情况，base58 编码就是把字节转化成字符，而一个字节对应的是 [0, 255] 一共 256 种情况，转化成字符之后只有 58 种情况了。所以对于单字节的 base58 编码结果的首字符来看，一定是有字符是会出现多次的。但是 1 不一样，1 只有当待编码的字节是 0 的时候，首字符才会是 1，这也是 1 的概率正好是 1 / 256 的原因。

我们继续看首字符和第二个字符相等的情况：

Pj4+IHByaW50KGNvdW50ZXJfYm90aCkKQ291bnRlcih7J0JCJzogNTI3NSwgLi4uLCAnODgnOiA0ODg1LCAndnYnOiAxMDUsIC4uLiwgJzExJzogNjUsICdaWic6IDY1fSk=

在首字符的统计数据里，1 是明显比 K - z 多的，但是前两位字符都是 1 的次数却突然变少了这么多。计算频率的话：65 / 5000000 = 0.000013，正好又是和 1 / (256 * 256) 接近。

因此对于前缀是 1 的情况，确实与其他的字符不一样：前缀是 1，只能意味着待编码的字节前缀为 0，而如果相同字符的前缀长度大于 2 的话，那么它就是概率最小的情况。

最终结论

假设你想匹配的前缀或者后缀长度为 $$L$$。

对于后缀匹配来说，不同字符理论上是均匀分配的，如果你只是想进行后缀匹配，那么整个后缀命中一次的概率是：$$(\frac{1}{58}) ^ L$$。

前缀匹配则更加复杂：

区间	具体字符	区间总概率	区间内的单个字符的概率 $$p(C)$$
1	只有 1	0.39%	0.39%
2 - H	2…9 和 A…H 共 16 个	94.15%	5.88%
J	只有 J	1.45%	1.45%
K - z	K…Z, a…z 共 40 个	4.0%	0.1%

整个前缀命中一次的概率需要分类讨论：

1. 如果前缀全为字符 1，概率 $$P() =(\frac{1}{256}) ^{L} $$；
2. 如果前缀首字符不为 1，概率 $$P() = p(C)\frac{1} {58} ^{L - 1}$$；

声明：以上所有概率分析均建立在“ED25519 公钥对应的整数在 $$[0,2^{256}-1]$$ 上均匀分布”这一前提之上。此外，文中给出的数值均为理论概率，在实际运行中并不意味着只要尝试相应次数就一定能获得匹配结果。