前两天在用 WireGuard 将两个分别在不同路由器后面的局域网连起来，结果发现有一款穿墙神器 Tailscale 不仅将 WireGuard 设置大大简化，而且巧妙的用到数学知识进行穿墙，实现不同局域网直连。不得不大赞。

WireGuard 是一个基于 UDP的极为简单高效的点对点加密通信与转送协议 （https://www.wireguard.com/）。我最初的设置是在互联网服务器上安装 WireGuard作为中转站，两个局域网都用 WireGuard 与这个中转站建立通道，这样两个局域网就通过中转相连了。看起来相当不错，缺点数据都得经过一个中转站。在网上搜索时发现有一个以 WireGuard 作为数据面的称为 TAILSCALE 的控制系统可以实现局域网不通过中转直连。而为了实现穿墙直连，TAILSCALE 开发者可谓绞尽脑汁。

WireGuard 通道建立的前提是点对点之间能够互相发送-接收 UDP 数据包。UDP数据包从局域网节点发出去时，路由器会进行数据包网络源地址进行翻译，将数据包的IP转换成路由器的公开IP，将数据包的源端口进行替换。这叫做 NAT。NAT又分两种，一种是源端口替换只取决于源IP与端口，这是一种容易穿透的墙 --- 通讯双方通过一个第三方进行端口信息交换即可，且让我们称之为软墙。一种是源端口的替换不仅取决于源IP与端口，还取决于目标IP与端口，这要穿透就难了--这是一堵硬墙。难道这种情况下由只能回到通过中转进行通讯了吗？TAILSCALE 开发者们没有轻易放弃。他们给出了一端是软墙、一端是硬墙的穿透方案。那就是随机猜测硬墙一端的端口。而这里面用到了所谓“生日悖论”的数学知识。

一个人生日有365种可能性，从1月1日，到12月31日（不考虑特殊年份）。一个班有  n 名学生，至少有两个同学生日相同（同月同日）的几率是多少呢？我们可以计算没有任何两个同学生日相同的几率（也就是所有同学生日都不同），然后用100%减去它，就是至少有两个同学生日相同的几率了。

以班上只有5人为例，第二个同学与第一个同学生日不同的几率是 364/365, 第三名同学与前二人生日不同的几率是 353/364。以此类推，5人生日完全不同的几率是 364/365 * 363/365 * 362/365*361/365 ~ 0.97，也就是说 5人中至少两人生日相同的几率是 3%。稍作推算，如果是 n 个学生，其生日完全不同的几率是（365-1)!/(365-n)!/(365)^(n-1) 。如果是50人，这是 364!/315!/365^49 ~ 2.95% 。也就是说 一个50人的班里，至少有两个同学生日相同的几率是 97%。

受生日问题的启发，TAILSCALE 为了解决软墙-硬墙的穿透问题采取的方法是，在硬墙内部一端，随机选择 P 个源端口，向软墙一端发送UDP数据包，同时软墙内部则随机挑选 G 个目标端口向硬墙发送UDP数据包，如果两者正好对上了，软墙发出的数据包就能被硬墙内的一端收到，从此实现穿墙。现在让我们计算一下两个随机选择正好有一组对上的几率。

设端口数的范围是 N （对于现有协议来说，端口是16比特数，N是从1到 2^26-1 = 65535）。软墙一段第一次碰对的几率是 (N-P)/N。第二次尝试时，可能目标减少了一个，变成 N-1，因此第二次碰对的几率是 (N-1-P)/(N-1)。G 次尝试全部没有碰对的几率 是 p =（N-P）/N * (N-1-P) / (N-1) * (N-2-P)/(N-2) ...* (N-G+1-P) /(N-G+1)。

也就是  p= (N-P)! * (N-G)! /N! / (N-P-G)! 。假设 P = 256, G=1024，也就是一段随机选择 256 端口，另一端进行 1024次随机猜测，全部猜错的几率是 （65535-256)!*(65535-1024)!/65535! /(65535-256-1024)! = 0.0176，也就是说猜对端口的几率是 98.24%。TAILSCALE 的开发人员写了一个Python 程序，用随机模拟的方法得到了这个几率，具体来说就是随机选择P个端口，然后随机进行G次猜测，这样反复多次，看碰对的成功率 （https://github.com/danderson/nat-birthday-paradox/blob/master/paradox.py）。但这有点小学生而且浪费CPU，我们应该给出一个解析公式。

由于N 相当大，而 P, G,相对较小，我们可以使用斯特林近似。$\ln n! \approx \int_1^n \ln x dx = [x \ln x -x ]_1^n = n \ln n -n +1 $

$\ln p= \ln \frac{(N-P)! (N-G)! }{N! (N-P-G)! } \\ \approx (N-P) \ln (N-P) -(N-P) + (N-G) \ln (N-G) - (N-G) - N \ln N +N - (N-P-G) \ln (N-P-G) +(N-P-G) \\ = N \ln \frac{N-P}{N} -P \ln (N-P) +（N-G) \ln \frac{N-G}{N-P-G} +P \ln (N-P-G)\\ \approx -P +P -P \ln \frac{N-P}{N-P-G} \\ \approx -\frac{P \ G}{N-P-G} $

上面利用  ln(1+x) = x 的近似进行了简化，我最终得到 

$\ln p = - P G /(N-P-G) $

也就是说  $p = e^{-\frac {P \ G}{N-P-G}}$

最后，我们得到随机对碰成功几率为 

$S = 1-p = 1- e^{-\frac {P \ G}{N-P-G}}$

JavaScript 代码为  

function collisionProbability ( P,G, N=65535) { 

return  1- Math.exp ( - P*G /(N-G-P)) ;

}

下面是S公式的代入不同P,G值的数据，与 TAILSCALE 开发人员模拟出的结果一致 （tailscale.com/blog/how-nat-traversal-works/）：

P=256, G = 174, S = 0.495

P=256, G = 256, S = 0.635

P=256, G =1024, S = 0.983

P=256, G =2048, S = 0.999