无偏冲突终端机:一种和谐利器用于公平抽签
Smallcup@NEWSMTH

=== 概要 ===
本文介绍了一种全国范围随机抽签算法--无偏冲突终端机。本算法基于字符串散列和不可控随机数种子，使得结果的有效性可以被每一个参与抽签个体以简单方法验证，而无人可以影响其公平性。本算法解决了绝大部分随机抽签分配利益的不公平性，给和谐社会提供极大的技术保证。

=== 背景 ===
随机抽签是解决少量资源在大量潜在使用者中分配的方法。经济适用房、彩票、小学入学等等场合都是随机抽签的应用点。更多潜在的应用点包括户口分配、医疗、就业、生育控制等无数方向。但是缺乏有效的公平（特别是可验证的公平）抽签方法造成大量社会矛盾。很多情况即使抽签是公平的，也会被未入选者指摘为不公平。此时抽签组织者和抽签获益者均无法提供可信服的公平性的证明。这样的矛盾极大的影响了社会分配效率，因为不但有权者可能出卖抽签机会，而且即使抽签本身是公平的，也无法说服抽签失败者信服，从而使得抽签结果难以付诸实施。
基于这方面考虑，本文提出一个绝对公平和可验证的抽签算法，可以一举解决上述问题。本方法利用公钥体系、SHA1算法和世界股市报价系统，为每一个抽签事件生成一系列抽签结果。抽签事件规模和结果的数量均可由主办者决定，而其结果可以被任何参与者——包括受益者和败者——以极低成本验证。

=== 模型 ===
设参与者集合U={u_i}包含m个成员。抽签目的在于从中抽取n个成员，使每个成员被抽中的概率均为1/m。模型中另两个元素为抽签组织者和国家抽签局。每个抽签事件在启动前给于一个独立的随机数字N，长度至少160位。

=== 算法 ===
抽签过程分为6个不重叠步骤：预备、报名、构造集合、静默、抽签、结果发布

0，预备
抽签过程6个阶段的日期必须在抽签之前就向全体潜在报名者公式，并用主办者私钥签署。

1，报名
期间，报名人员可以随意增减。我们假设报名者的标示(id_i)是身份证号码（或学生号码、社会安全号码等等，不失一般性），报名结束时，集合U将包含m个元素。特别注意的是，报名过程的公正性不是本算法重点。组织单位可能通过不对称的信息传递使得某些潜在人群无法参与报名或者报名无效。每个参与报名者在报名时均需要提供一个较长（160位或以上）的随机数r_i。报名成功瞬间，由组织者给报名者颁发一个用自己私钥签署的收据，证明的内容为id_i和r_i以及N。

2，报名结束后构造抽签集合，采用以下公式：
   u_i = SHA_1(id_i, r_i, N)
由于u_i足够长，可以忽略冲突的情况。即使出现冲突，在报名期间可以提醒报名者更换r_i解决冲突。

3，静默期
静默期，组织者必须将抽签集合向匿名用户完全开放。所有人可以下载、保存抽签集合U。组织者必须用公钥签署集合U。因为下载是匿名的，组织者无法针对不同下载者提供不同集合，而每个下载者i可以验证SHA_1(id_i, r_i, N)是否在U中。如果不然，他可以很容易举证抽签造假（因为在报名时他拿到了主办者私钥签署的收据）

4，抽签
政府抽签局每天早晨6点30分向社会发布当天的随机数种子S。随机数种子S由8个全球主要股指最后收盘点数的字符串连接。例如香港恒生+美国道琼斯+纳斯达克+日经+法兰克福+伦敦金融等等。由于这些点数均由大量股票价格构成，任何一方均无法精确影响其结果。另一方面，这些指数的运算方法和基础数据均公开，所以不可能出现指数结果造假。实际上政府抽签局并非必要环节，任何人可以从网络直接取得各个指数并构造S。

每一个抽签组织者得到S后，计算
  R = SHA_1(S, N)
如上所述，N为本抽签的特定随机数。
然后对每个代选择成员分别计算
  x_i = SHA_1(R, u_i)
如上所述，m为本抽签的参与人数。抽签最终结果将选去x_i数值最大的n个人。由于x_i足够长，不可能出现x_i重复现象。即使出现，可以按照u_i顺序选择。

5，结果发布
抽签主办者将抽签结果(最高的m个u_i)公布，所有参与者均可验证。实际上，以上2-4步可以被任何抽签者以很低的计算成本重复进行，结果必然相同。如果有人发现结果不准确（前n个x_i中，有的没有出现在结果中），可以轻易举证造假，因为第二步中的U是用主办者私钥签署的。
报名成功者可以用在报名期间得到的签署过的回条(id_i, r_i, N)领取抽签利益。

=== 讨论 ===
1, 隐私
由于报名期间要求用户提供随机数r_i，无人可以通过u_i反推id_i。组织者甚至可以不保存id_i和r_i，而用签署的u_i作为回条，从而彻底保证参与的隐私。

2，攻击
由于抽签的任何环节均可被任何参与者轻易重复并得到相同结果，而且错误结果可以轻易举证造假，所以不存在明显的攻击方式，除了主办方用假身份稀释报名者。这种情况可以用id_i代替u_i，以牺牲隐私的代价，换来身份的真实性。
随机树种子可能是最容易被攻击的环节，但是影响它到特定值的代价极大，超过了绝大多数抽签者的获利。

3，部署方式
可以开源开发全国通用的抽签客户端，用以帮助不具备计算机能力的参与者，验证抽签的有效性。开源的代码可以被任何人检查有无漏洞。

=== 结论 ===
本文的贡献在于提出了一套行之有效而且完全安全的随机抽签算法。这种算法必将促使和谐社会早日到来。

=== 感谢 ===
感谢绿坝的原作者。你们的脸皮给了我足够的勇气把这篇文章完成并发表。

王小波 <未来世界>
 "我正在街上游荡，天已经很晚了。我应该活下去，但是这个决心很难下。但是假如我下定了这个决心，那么我作为一个知识分子，就算是改造好了。万事开头难，第 一回羞愧、疼痛，但是后来没准会喜欢——只要不在生人面前。我应该回家，但是这个决心很难下。假如家里没有F就好了。但是假如我下定了这个决心，我作为一 个男人，也算是改造好了。"

"我现在又回到原来的生活里了，我得回了失去的姓名、执照、赛车、信用卡，得回了原来的住房——这间房子和原来那间一模一样，但不是原来的那间，那间被别人买走了，只好另买一所一模一样的。而且我又开始发胖。"

<Transpotting>
"但那会改变，我要改变，这是最后一件坏事，我要洗心革面，向前走，选择人生，我已经在期望了。我会跟你一样，工作，家庭，大电视机，洗衣机，汽车，CD播放机，电动开罐器，健康，低胆固醇，牙医保险，贷款，购屋，休闲服，行李箱，三件式的西装，DIY，猜谜节目，垃圾食物，孩子，公园散步，朝九晚五，高尔夫球，洗车，运动衫，阖家过耶诞，养老金，免税，清水沟，只往前看，直到你死掉那天为止"

赫胥黎 <A Brave New World>
"因为形成社会脊梁的并不是哲学家，而是细木工和玩集邮的人。 "

Pixar跑到墨尔本来办展览，主要表现他们制作3D动画片的过程——特别是初期的过程。

展厅外面可以照相，但是展厅里面没法照相，凭印象记了以下几点：

1，Pixar的动画片虽然全是电脑动画，但是它的创作过程和传统动画电影区别不大。主要的区别，在于对人物进行三维建模的过程。

2，在作品的最初立意和简单的脚本完成后(通过Storyboard,一种随意绘画的叙事风格)，以下三部分工作将启动：

   a,对人物形象进行详细设计。先按照传统动画的习惯，用铅笔或油画棒画出人像的正面站立草图，讨论确定后，对其不同表情、常见动作画出多幅草图。这部分草图完成后，对于主要人物，用胶泥或石膏，塑造出立体的全身像或者头像。对于特别重要的人物，甚至要塑造多樽不同表情、姿态的塑像。之后，在塑像表面用纵横线画出方格，进行三维模型化转换。结构复杂或者观众关注的部位，比如脸部正面，方格会画的非常密集，按照真人比例，纵横线的间距最小2-3毫米；后脑等部位则很粗略，线间距3-4厘米。然后对三位模型的动作进行定义，可能采用真人表演，采集各个关节的三位运动信息；也可能用软件工具简单构造动作。

   b,对主要场景进行设计。与人物造型设计基本相同，但一般不通过塑像进行三维转换。而是直接通过二维草稿创建三维模型。

   c,用最少的祯数，绘制情节（与后面的ColoredScript不同) 的关键祯。因为此时人物和背景均未定型，所以可以与最后设定较大出入。这部分主要是为了完成剧情到视觉的初步转换，以及确定各个情节的大概长度、表现形式和大概构图，为下一步作准备。

3,在以上三步完成并讨论定稿后，绘制ColoredScript。这一步将运用设计好的场景和人物，绘制主要的情节。需要注意，ColoredScript的张数可能比上一步的关键祯少一些，而且以全景图为主。因为这一步的目的是为了确定最后拍摄的视觉效果，构图可能会有一些调整，但是情节基本不会变了。精彩的情节的关键祯，在这一步将重绘以便确定每一个精彩镜头的最终视觉效果。

以上完成，即可进入正式的拍摄过程，也就是根据关键祯，建立每一个镜头的三维运动过程，并且进行大运算量的渲染。

从以上看来，除了导演、行政人员、三维建模人员和拍摄支持人员外，Pixar的创作队伍还需要以下人员：
1，二维设计人员，绘制人物和场景的草稿
2，立体造型人员，根据草稿塑造雕塑

人物最初草稿、关键祯都是一个紧密团结在导演周围的很小的群体构造的。而导演的思路可以直接贯彻到每一张草稿和关键祯。这样后期拍摄依靠的内容骨架就被导演牢牢掌握。导演的意图可以通过这两个手段，贯彻到最后的成品。

而ColoredScript则可以看作项目的中期报告，在项目正中间，也是最关键的时刻，统一所有人员的思想，并且给他们以最直观的概念，让他们清晰理解最后拍摄完成的影片的人物形象、情节、构图、用色和精彩镜头所在。

以上内容可以引起各位项目带头人的思考，怎样将自己的思路贯彻到项目最后的每一个细节；以及怎样在项目中期统一所有人的思想，包括团队内部的、领导的和客户的。

3月份无聊做的板子

LPC 213X和214X都支持，为214X的USB口子预留了插座。
把RS232的CTS和RTS线搞反了，所以飞了两根线对调过来。
手里有一块非常便宜的SIMCOM110的GSM模块，所以板子上设计一个插模块的口。
另外还有一个口专门插GPS模块，一个口专门插LCD液晶。

用这个做了一个车载GPS跟踪器，可惜车已经送人了。只留下几个开车出去的跟踪的记录。用Google Earth直接打开URL：

http://www.da-quan.com/ge/in10.txt.kml
http://www.da-quan.com/ge/in11.txt.kml
http://www.da-quan.com/ge/in12.txt.kml
http://www.da-quan.com/ge/in15.txt.kml
http://www.da-quan.com/ge/in16.txt.kml
http://www.da-quan.com/ge/in20.txt.kml

周易是中国传统思想的重要基础，趁着这几天准备雅思考试的时间，对此进行一些思辨。希望对此有兴趣者能够读一读。

http://www.taijimgx.com/Article/UploadFiles/200410783937138.jpg

什么是太极？太极图就是一个圆形内的正弦曲线。正弦曲线的二阶导数为其负数的特性（sin(x)'' = - sin(x)），正符合了周易物极必反，阴中有阳的规律。三角函数是控制论中频率时间变换的基础。而且绝大部分事物的发展（人口数量、粮食产量、股票价格、机械运动等等）都是符合这个规律的，而且绘出图像往往看上去就是正弦波。所以说太极中的正弦曲线很可能是当时的人对事物的发展进行统计、归纳总结后绘出的曲线。

太极外面的圆形也很重要。我们知道正弦函数和圆形的关系——简单地讲，从圆心引直线，以直线和某固定参考线的夹角为横坐标，以直线和园的交点到参考线的距离为纵坐标绘图，画出来的就是正弦曲线。每一本讲到三角函数的教科书都有这个化园为正弦曲线的图示。而在控制论中我们知道，圆心的那个夹角往往就是和时间相关的。因此，太极图的完整含义就是：一个点在圆周上运行，它到参考线的距离与时间的函数就是正弦曲线，而这曲线，就是绝大多数事务的发展规律。点在圆周上一圈一圈不断地运动产生的不断延续的正弦曲线，正符合了绝大多数事物长期运转的特性，也就是周而复始，阴阳永不间断转换，无始无终的意思。

再看看八卦，八卦均匀画在太极图之外，不妨把它想作三角函数的离散化——把一个正弦函数周期离散成8个阶段。再用3个爻来代表8各阶段，也就是所谓二进制化。说到这里我想向每个人都会想到离散余弦变换(DCT)这个词，这也正是我想说的。离散余弦变化可以对某些曲线进行拟合，阶数越高就越准确。在当年没有数学工具的前提下，不太可能作太高阶的转换，但是周易的发明人可能做到了二阶。于是我们有了6爻，64卦。而这64卦就可以用来对事物的曲线和相位进行简单的拟合。

正如最开始所讲，大部分事物都有控制论的特性，因此可以用频时域变换来进行建模。如果当年周易的创造者利用以上说的余弦变换，对天气、人口、食物产量、河水流量等等当时的人非常关心的数值规律，成功地进行了二阶拟合，并且用拟合结果进行了预测，就会被当时的人——不理解频时域变换的人——看作神奇的预言家。在一个没有任何科学预言方法的时代，这样的预言精度已经相当高了。所以周易自古被用来预测，而且被传地神乎其神。其实它所作的事情和现在股票分析软件做的事情基本相同。


但是没有足够的数学工具，导致第一个创造者——当年大家心目中神奇的预言家——不可能把以上这些，写成从中学到大学用的数十本教科书，而只能用中国习惯的做法，将其人文化、神秘化。很可能第二代传人就不太了解创造者的思想了，更不要说一两千年后的人。所以人们只知道，周易能够神奇地预测，而且可能很准确，但不知道它的创始和实际含义，也不知道它的适用范围和局限性，于是对一些频时域变换的经验公式过分地崇拜，想了无数神秘主义的手段来解释之。看了这篇思辨，也许大家会对周易的本质有更加清晰和实际的认识。另外，也对我国当年没有产生欧里几那样的思想家而遗憾。天不生数学，万古常如夜。

   由上个定理可以看出，在没有外界刺激的情况下，群体里的个体总是趋于保持稳定的。但是如果外界刺激发生，又会有怎样的情况出现呢？

   例如由于突然的变故，群体的头领被天敌杀伤而失去领导能力，群体陷入群龙无首的状态。此时，如果长期没有新的首领出现，群体将会非常容易被杀伤。因此，群体进化会赋予群体中的各个个体，在头领突然丧失领导能力时能够迅速补位的能力，避免群体由于没有组织而遭到毁灭。

   这种群体应激性不仅仅体现在群体突然失去头领的情况。当个体或群体遇到更强的个体后，会自觉将更强大的个体奉为头领。这是群体行为通过进化优胜劣汰得到的特性。如果没有这样的应激特性，群体将难以通过提升头领的能力来提升自己的竞争力。而且新旧头领或者个体和新头领之间的过度斗争将使得群体遭受很大损失。

   斯德哥尔摩综合症 正是这种特性在人身上的表现。在人质被绑匪扣押一段时间后，人质对于绑架者竟然会出现依存感，人质在本来能够获救时也会主动保护绑匪。这正是人质的个体或群体在遇到更强大个体后，自觉将其树立为群体的头领，并按自己在群体中的地位，对其产生依存感并主动保护之。虽然人质们很清楚地知道，这种绑匪的臣服即不利于个人也不利于群体和社会，但由于群体进化的特性已经积淀了几亿年，所以人类的理智也没能克服这种特性。

   正如引理中所谈到的，为了保证物种群体的相对稳定，群体进化会使得个体在群体中的地位是基本稳定的。而且个体不会经常主动去变换自己的位置。正如定理二所谈到的，个体地位的稳定是因为个体内部因素导致的。这些因素包括：对自己当前地位的认同趋向、求稳趋向，以及挑战与安稳的平衡点的把握。这些因素会使得个体在群体中的地位主动地趋于收敛。

   正如赫胥黎《美妙的新世界》中谈到的，不论个体在群体中的地位是高还是低，个体的幸福感都是相近的，甚至地位低的个体会比地位高的个体更加感到幸福，更加愿意稳住自己的地位。

   客观地说，个体的求稳特性是种群能够延续的最基本保障。一旦这个特性丧失，正如《美妙的新世界》中描述的“塞浦路斯试验”那样，整个种群会因为内部的激励斗争在几代时间内迅速消亡。

      自然界的竞争是非常残酷的，竞争的失败就是灭种。正如引理2中提到的，群体的胜利才是真正的进化胜利。
      动物的社会性行为正是为了实现进化胜利，被一次次的淘汰所塑造出的。一个动物群体时时刻刻面临各种危险。对于食草动物，危险来自于食肉动物，而食肉动物的威胁则来自于更强大的食肉动物和由于食物匮乏带来的饥饿。正因为有了这些危险，所以动物群体会自然而然的朝着能够抵御危险的方向发展。
      我们很容易理解，一个群体集体行动的力量，会远远大于每个个体独自行动。而想要集体行动，必然需要群体有一个或几个首领。而群体的中层领导会更多一些。最多数量的就是群体的底层成员。而下级的个体在大多数时间需要严格执行上级的命令。

      一个动物群体，不论拥有多差的领导，也比没有领导一团散沙要强得多。而拥有高明的领导的群体，其生存的可能性要比拥有差劲的领导的群体也会高得多。因此，进化会使得动物群体产生最适合的结构。这包括群体的规模、领导的数量、领导的产生方式、群体的分工，以及同一物种各个群体之间的竞争与平衡。而进化会采用最科学的办法来让没有形成文明的动物们能够遵照最优的组合来构建群体。这些团队的结构和其构建、存续的方法是深深刻在动物的基因中的。

      我们一提到进化，往往会立即想到长颈鹿脖子变长的例子。一批鹿到了非洲，那里的树特别高，要吃到树叶很困难。因此，突变后脖子变长的鹿比普通鹿有更多的生 存机会，更能繁殖后代。于是，随着不断的淘汰和固定，长颈鹿的物种就产生了。好像进化就是指的生物个体适应环境变化而产生相应特性的过程。
      但广义的看，进化是无处不在的。从生物出现之前的化学进化，到文明出现之后的文化进化、社会结构进化等等。凡是存在突变、繁殖、遗传和淘汰的过程，均可以视作进化。

      这个道理很简单，动物存在社会行为这一点，已经被无数科普书籍和电视节目说明了无数遍。例如狮王争霸、蜂王役使工蜂等等。在动物的世界中，虽然没有成型的 等级意识，但却有着森严的等级社会。不同级别的分工、生殖的机会、统帅种群中其它动物的权力，是明确而截然不同的。