如何在操统课 Bitcoin 大作业组间比赛歇菜

交叉信息研究院的本科生操作系统课程的大作业很奇特，并不是 4 个 NachOS 作业，而是两次 NachOS、两次分布式数据库。最后一次大作业是要写一个 Bitcoin 挖矿程序，而且还有组间比赛，各个小组的矿机和客户端会一起运行一段时间，最终获得最高手续费的矿机会获胜。

以下内容摘抄自大作业文档：

… You may also reorder transactions within a block. However, please note that the ordering of transactions is very important and reversing the order may cause some transactions to become illegitimate, and you must ensure the sequence of transactions in every block is legitimate…

……

Special Notes about Cross-Testing

As a tradition of IIIS OS course, the final project includes a cross-testing phase in which students test each other’s implementation and find weird bugs. For this project, it contains two parts:

…

The mining test, where one server of each group runs against each other. In this mode, some clients will generate some “random” transactions, and your server is busy mining and compete with others.

…

You will get bonus points if you win the mining contest, e.g. at the end of the day your miner’s account balance is top 2 out of all groups. Think carefully! (Note that each block may contain ~50 mining fee.)

……

先忘记大四狗已经没有理想（除了平凡理想，我们都是单环）的事实，注意到：

只有挖矿能带来 miner account 的收益，因为其他的交易是（应该是这个测试专用）客户端生成的，为了保证公平肯定不会主动转入收益到矿机，即使是自己的客户端在运行，因为矿机的帐户名不能被预知，所以仍然不能给自己转账；
挖矿的时候可以合理重排交易的顺序；
一个区块的大小是有限的（在我们的作业中是 1 到 50 个交易），假设只能随机碰撞 SHA-256，优先把交易费高的交易放进待解区块更划算。

一个自然的想法是，如果我们有多于 50 个交易可以选择，应该如何选择一部分交易并合理设置顺序，使我们挖出来的收益最大？几秒钟，没什么思路，或许（该问题的一般化版本）是 NP 困难的？确实是。

实际上还可以限制交易的手续费都是 1（单位是最小不可分割单位），问题是从这些交易中最多可以选几个出来组成一个合理的区块。考虑有向图的 $s\text{-}t$ Hamiltonian 道路问题，构建如下的钱包和交易：

对每个节点创建一个钱包， $s$ 的初始余额是 2， $t$ 的初始余额是 0，其他节点对应的钱包初始余额是 1；
对每条边 $\left({u,v}\right)$ 创建一个交易，它从 $u$ 扣除 2 余额，支付 1 手续费并支付 1 余额给 $v$ 。

容易发现，可以从交易中选择 $\left({n-1}\right)$ 个并按一定顺序组成合理的区块当且仅当原来的图里面含有一个 $s\text{-}t$ Hamiltonian 道路。

结论：还是别在选择交易的方式上耍小聪明为妙，歇菜！

P.S. 我发现这个大作业的 deadline 推迟了一天，所以今天可以写一篇博文来说这个事儿。