Telegram Channel
记录和分享有趣的信息。

Record and share interesting information.

contact: [email protected]
Laisky's Notes
https://laisky.notion.site/Anonymous-Credential-Part-2-Selective-Disclosure-and-CL-Signature-4e88462949764a579222d810c614842a 想象这么一个场景,政府给你签发了身份证,政府为这个证件背书上面的信息都是真实有效的。 然后你为了上某 X 网站,需要证明你已经年满 18 岁。于是你把身份证信息加密后上传给网站,然后选择只披露其中的姓名和年龄属性。网站通过签名验证这个身份信息确实是由政府…
简单粗暴地理解椭圆曲线算法(Elliptic Curve Cryptography)。

首先,绘制一个扭曲的曲线。然后在这个曲线上定义一种名为加法的运算:

1. P 点和 Q 点相加: 绘制直线 PQ,得到和曲线的第三交点为 R,R 的 x 轴镜像点为结果。
2. P 点自己和自己相加: 绘制 P 点的切线,得到和曲线的交点 R,其镜像点为结果。
3. 定义零值为 y 轴的无穷远处,和零相加等于画一条垂直线。

如上我们定义了运算规则,接下来就是从曲线的点中选取一些点构成一个循环群。群就是一组满足相同规律的数的集合。循环群(cycle group)中存在一些本原元(primitive element),这些原元通过不断累加,可以遍历整个群。

形象地说,你找到一个本原元点(primitive element),然后不断地累加这个点,利用前文我们所介绍的加法运算,你其实就是在曲线上不断地跳跃,并最终会跳回起点。

ECC 加密算法中,就是构建这么一个曲线,它的循环群内的成员数量达到 2^100 次方,我们认为这个量级的数是无法靠暴力遍历破解的。这个曲线的每一个值是根据一个大素数的模的方程构建的,成员数量约等于这个素数的位数,一个 160-bits 的素数可以构建一个包含 2^160 个点的群。

然后给出这么一个公式 dP = T。P 是一个 primitive element,它累加 d 次后会得到 T 点。P、T 是公钥,d 是私钥。这也是为什么 ECC 的私钥可以很短。

也就是说,我公开展示最终的 T 点,但是不告诉你我跳跃了多少次。你是难以通过暴力遍历去求解 d 的。这个 dP = T 就是构建了一个离散对数问题(DLP),计算 dP 很简单,但是逆运算求算 d 很复杂,需要暴力搜索 2^100 的空间。

既然利用 ECC 构建了 DLP,那么就可以利用 ECC 替换传统 DLP 问题,比如 Diffie-Hellman 密钥交换算法,现在可以重构为基于 ECC 的 ECDH 算法。

Alice 和 Bob 都确认一个曲线和一个 primitive element P。然后双方各自生成一个 d,然后交换计算结果 dP。拿到对方的 dP 后再乘上自己的 d,就会得到一个相同的 T。窃听者能拿到曲线、P、d_alice*P 和 d_bob*P,但是他无法逆向求解 d_alice 和 d_bob,所以无法破解最终的 T。

PS: 所有的 DHKX 算法,都难以防御中间人攻击(MITM attack),即攻击者可以篡改通信,同时和双方握手。解决办法是引入数字证书,对对方的公钥进行签名。
PS: 安全的椭圆曲线是很难绘制的,一般参考 NIST 的推荐。 #crypto

next: https://t.me/laiskynotes/173
https://youtu.be/x_isZHaZjcU?si=fUVBFw_FvrkqJi63

通过访谈和讲述几位以色列人和巴勒斯坦人的真实故事,非常简明扼要的阐明了自 1948 年以色列建国以来的 60 年动荡历史。

先是在战争中从周围的阿拉伯国家里获取领土,通过大驱逐建立了一个犹太国家。然后是与周边国家的艰难和谈,经过以色列 Meir 夫人、埃及 Anwar El-Sadat 总统、巴勒斯坦武装领袖 Yasser Arafat、以色列总理 Yitzhak Rabin 等人的不懈努力,曾一度取得了和平的希望。

可惜激进派的火苗从不曾熄灭,Sadat、Rabin 被暗杀,加沙地区信奉原教旨主义的哈马斯崛起,Arafat 被边缘化。以色列的鹰派 Netanyahu 上台,奥斯陆协议(Oslo Accord)被抛弃。巴以之间陷入了漫长的袭击与报复的循环,迄今看不到任何和解的希望。

next: https://t.me/laiskynotes/204
https://youtu.be/r0Ji7KqqEqg?si=Dobd3qPl8BW8zZHm Hostomel 之战的详细解释。实际上俄军 VDV 强袭机场得手后,当天下午就被包围了。乌军的炮击破坏了机场设施,使得 18 架次的后续增援部队无法降落。
我觉得降落了估计也不会有特别大的影响,毕竟俄军主力很快就从北方推进到了此处,然而除了搞个 bucha 大屠杀外再也无所作为。
https://laisky.notion.site/Anonymous-Credential-Part-2-Selective-Disclosure-and-CL-Signature-4e88462949764a579222d810c614842a

想象这么一个场景,政府给你签发了身份证,政府为这个证件背书上面的信息都是真实有效的。

然后你为了上某 X 网站,需要证明你已经年满 18 岁。于是你把身份证信息加密后上传给网站,然后选择只披露其中的姓名和年龄属性。网站通过签名验证这个身份信息确实是由政府颁发的,其中的信息真实可靠,而且证件上的年龄显示你已经年满 18 岁,而证件上的其他信息都对网站不可见。

在上述流程中,政府(issuer)为你(holder)签发了信息,你选择将部分信息披露给网站(verifier)。这就是 Anonymous Credential(Anoncred)或称为 Attribute-based Credential(ABC)。

这一算法的特点包括:

1. issuer 可以使用一对公私钥,签发 K 组信息。
2. holder 可以选择性地披露 N 组信息(N<=K)。
3. verifier 可以通过 issuer 的公钥验证 holder 所披露的信息的有效性。

穿插提一下密码学中的 Commitment Schema。Alice 可以对一个未披露的 Message 声明 Commitment,Bob 可以保留这一 Commitment,直到 Alice 披露 Message 后,Bob 可以验证这一 Message 是否与 Commitment 一致。结合前面所提的 ABC,其实就是一个 Commitment Schema,Issuer 为 Holder 的信息背书(statement signature),Verifier 需要 Holder 披露信息后才能验证真实性。

最简单的实现就是基于 RSA 的 CL Signature,更多细节可点击查看: https://telegra.ph/CL-Signature-02-26-2 #crypto

next:
- ECC & ECDSA & ECDH
- AC & ZKP
Laisky's Notes
https://laisky.notion.site/How-Hype-Will-Turn-Your-Security-Key-Into-Junk-ac50dfbc44354bdfab17ef76e72ece13 非常不错的文章,介绍了目前 passkey 领域可能正在走的一条歧路。 补充:关于 yubikey 是什么,以前写过一篇文章 https://blog.laisky.com/p/yubikey/ 众所周知,FIDO、WebAuthn 等正在推动 passwordless,也就是放弃让用户记忆…
此前讨论过 passkey 的一个缺陷(https://t.me/laiskynotes/64 ),就是需要客户端存储太多数量的 resident keys,这对于如 Yubikey 这样的 security keys 设备非常不友好,因为消费级 security keys 往往只有 10~20 个 private key slots。

https://laisky.notion.site/HD-Wallets-Explained-From-High-Level-to-Nuts-and-Bolts-44d109ed89e04bb79f993234f185848e?pvs=4

最近学习了 Hierarchical Deterministic Keys 结构。HD Keys 本质上是一种面向非对称密钥的 KDF(key derivation function)。它可以从一个 root private key 为根节点,通过添加一些 key material 生成新的 child key。

KDF 是一个确定性(deterministic)的函数,也就是相同的输出,始终能得出一样的结果。这一概念对于熟悉 KMS 的人而言并不陌生,其实所有的 KMS 都是只存储 master key 的。HD Keys 的主要特点就是支持了非对称密钥。

那么我们是否可以把 HD 和 passkey 结合起来,让用户只需要存储一个(或多个,增强安全性)root key,然后服务端存储 key derivation materials,这样用户依然可以做到不同网站使用不同的 child key,而同时又不需要存储大量的 resident keys?

#crypto Laisky's Notes
早上一来就修了个 bug。

Azure OAI 的响应格式有变化,以前可以通过 choices 为空来判定对话已结束。而现在 azure oai 会首先返回一个 choices 为空的响应(只包含 content filters 结果),会导致老程序误判会话已结束。

你需要 skip 这些 empty response,然后把有内容的响应拼接起来。我的套皮站最近可能遇到会话卡住没有响应的问题,就是这个原因,已修复。

如果各位有 azure oai 项目发现响应突然变成空了可以排查下…
https://laisky.notion.site/GPL-_-_-_-1222f285a5f04fc98af34b10614feb7e?pvs=4

很多人转这篇《最高人民法院:这份判决给软件开发者吃了定心丸》,稍微去看了下,感觉有点标题党。

原告基于 GPLv2 的开源项目二次开发了闭源商业软件,使用 socket/commandline 规避了 GPLv2 感染。被告窃取了原告的非开源商业代码,狡辩称这是 GPL 代码,可以使用。法院支持了原告的诉求,认定侵权事实成立。

侵权是发生于非开源商业代码,其实感觉和 GPLv2 没啥关系,又不是支持了开源代码的权利声明,而只是支持了软著的权利,没什么说服力,跟各位开源开发者也没什么关系。
https://laisky.notion.site/SwissMap-A-smaller-faster-Golang-Hash-Table-DoltHub-Blog-2fd1a48ab8a24e13ab9614409252ab9c?pvs=4

学习了一下 SwissTable,号称更快更轻的下一代 hash table。

一开始被 DoltHub 的这张 benchmark 图唬住了,内存接近于 array,吞吐居然还比 built-in map 快,太神奇了。仔细研究了一下源码后发现果然是幻觉,benchmark 的代码作弊了,因为频繁 rehash,把内存占用压缩到了极致,而 bench 中忽略了最耗时的 Put 操作,然后只呈现了 Get 的性能😓

hashmap 的结构大同小异,底层都是一个固定长度的 array,key 通过哈希函数定位到 array 的地址,然后取得值。Go built-in map 使用的是开地址法(open-hashing),即不同的 key 可能会被映射到同一个 array 地址,然后这些不同的 item 通过一组以链表串联的 bucket 来存储,每个 bucket 存放 8 个 item。

而 swisstable 使用闭散列法(closed-hashing),即每个 key 都会有一个唯一的地址,不会有冲突。拿 Find 来解释 swissTable 的原理:

1. 计算 key 的 hash 值,前 56-bits 称为 H1、后 8-bits 称为 H2
2. 通过 H1 计算得到 array 的 index,array 的每一个 item 为 128-bits 长,由 16 个 8-bits H2 组成
3. 使用 SIMD 指令,并行比较 16 个 8-bits 地址,可以得知 key 是否存在于当前桶
a. 如果 key 存在,完成查找
b. 如果 key 不存在,且这 16 个地址都非空,说明 key 可能溢出到了下一个桶,index+1,继续循环(probing)
c. 如果 key 不存在,且这 16 个地址中存在空,说明 key 不存在

总的来说,swissTable 最大的亮点就是利用了 SIMD 的并行计算能力,实际上它和 open-hashing 类似也有 buckets,只是每个 bucket 的容量是固定的 16 个(取决于 SIMD 指令的宽度),而且不像拉链法那样可以串联,这样可以用 SIMD 一次性比对完 bucket 内的全部 keys,提高了性能,而且还能充分利用缓存的局部性。

至于说它省内存,我倾向于认为只是因为它的 load factor 略高一些所带来的些微优势,而没有本质区别,要注意不要被一些第三方的虚假宣传骗了。 #algorithm
https://youtu.be/WXuK6gekU1Y?si=KnJ-WTTVCpgvEgT3

前阵子和人讨论 GPT 时聊到了 AlphaGo,我意识到我对 AlphaGo 不太了解,所以最近打算学习一下。而要了解 AlphaGo,首先都推荐观看这部纪录片。

2014 年深度学习(AlexNet)的论文发表,DeepMind 开始利用深度神经网络处理视频游戏,并很快转向了对围棋的研究。2015 年,DeepMind 邀请欧洲围棋冠军 Fan Hui 来到英国与 AlphaGo 对弈并全胜,这是围棋程序第一次战胜专业人类选手,Fan Hui 也以顾问的身份加入 AlphaGo。2016 年 DeepMind 前往韩国挑战世界冠军 Lee Sedol,并取得了四胜一负的成绩。这一系列的胜利引起了全球的关注,也让人们开始认识到了深度学习的威力。

值得注意的是,围棋的特色在于其近乎无穷的可能性,这也对应着近乎无穷的计算量,这使得围棋其实是一个直觉游戏(intuitive game),而不是一个需要深思熟虑的策略游戏(logic based game),毕竟任何所谓的深思熟虑在这无穷的可能性面前都是无谓的。专业棋手其实是通过记忆数以万计的棋谱来训练自己的直觉,然后使用直觉来对弈,这一训练方式和神经网络的工作原理非常相似,这也是深度神经网络最终能够击败人类的原因。

更多关于神经网络信息可以参考此前发过的介绍 GPT 的文: https://t.me/laiskynotes/144

我还在学习 AlphaGo 的论文,更多笔记日后再更新。
前几日逛宁波博物馆时看到纪念戚继光的文字,称他为“守护沿海居民的英雄”。

但其实明朝时期的倭寇主要都是由中国人组成的海商(海盗)集团,因为明朝实施海禁,东南亚地区庞大的海商集团失去了生存空间,其身份也就从海商变成了海盗。

戚继光执行的是中央王朝实施海禁的政策,实际上是妨碍了沿海居民与外界互通有无的贸易往来,而这肯定会让沿海居民的生活受到损害。做个不恰当的比喻,拿前几年的疫情来说,戚继光就是一个执行铁血封城的大白,而倭寇就是那些顶着风险跑外卖的黑骑手。戚继光杀伐果断地执行了封锁,中央王朝当然会把他当成英雄来纪念,但是作为普通居民,恐怕会有完全不同的感受。

网上搜一下有很多对“倭寇主要是中国人”这一说法的攻讦,但是列举的论点多为万历朝鲜战争(庆长文禄之役),这是在混淆视听,因为朝鲜战争是丰臣秀吉发起的侵略战争,性质和东南沿海的倭寇是完全不同的。此外,还有人列举日本浪人侵扰朝鲜的例子,这一点在《倭寇:海上历史》一书中有提及。朝鲜率先实施海禁,然后遭到了日本海商集团的侵扰,“倭寇”这一词也来自于此。后来明朝也实施海禁,然后也遇到了中国海商集团的侵扰,而且直接沿用了“倭寇”这一称谓。但实际上“倭寇”是一个泛称,并不特指日本人,洋人来华也被称为“倭寇”。

《倭寇:海上历史》这书就是详细追述了倭寇史在历史上的出现与变迁。
https://youtu.be/EpMLAQbSYAw?si=t5IxWdWqSh0S9szH

《Age of Easy Money》对美国近数十年来的 easy money 政策的反思。

自次贷危机后,美国联邦储备局(FED)实行了大规模的量化宽松政策(Quantitative Easing, QE),即疯狂印钞,为大银行注资使其免于倒闭,这一政策在当年也被称为 Too Big to Fail。

这一政策的指导思想是政府可以在短期上发挥对经济的逆调控作用,当经济下行时,可以通过 QE 为市场注入血液;当经济过热时,可以通过加息来收紧货币。但是从过去二十年的经历来看,FED 的 QE 政策实际上无限制地鼓励了投机客的冒险行为,一旦大型投机客因为投机失败导致资金链紧张,FED 就会通过 QE 为其注资。这种政策导致了市场的不断泡沫化,也导致了美国经济的不断失衡。

更糟糕的是,如今回顾过去数十年的量化宽松,虽然为市场注入了大量低息甚至零息贷款,但是这些贷款并没有流入实体经济和基础设施,事实上几乎没有为美国带来任何实质性的建设。这些钱的很大部分实际上在金融市场空转,各个机构互相购买债券,互相借贷,互相投机,一场狂欢过后,除了通胀什么也没剩下。这也是当时美国人反感银行业,反对华尔街的主要原因之一,华尔街拿了 FED 救市的钱,却只管套利,而不是为美国经济做出实质性的贡献。这在片尾被称为“美国的政治缺陷,FED 可以印钞,却无法决定怎么花掉这些钱,华尔街可以花这些钱,但是华尔街的唯一目标就是套利”。

最后,Easy Money 的狂欢时代终将结束,接下来可能泡沫破灭的漫长回调。
话说前阵子每晚和家人吃晚饭时重看了火影忍者《Naruto》的主线剧情(700 集为止),也算是了却一个童年(青年?)时代的情怀。

实际上岸本齐史的剧本还是很有功底的,我觉得有一些值得称赞的地方:

1. 全剧没有精神失常的反派,甚至于没有严格意义上的反派。所有人都是出于自己的境遇,做出了自以为最好的选择。
2. 战力基本没有通货膨胀,至少 700 集以前基本维持了战力的平衡。
3. 这是一部基片,所有的 CP 都被拆了(甚至包括路人配角的夫妇),没有建立任何男女角色的感情线。(所有的感情线都是 700 集以后硬加的)。而且很容易看出来,作者不知道除了跪舔以外的男女关系…
4. 作者是个弟/兄控,每个人都有个深爱的兄弟。鼬对佐助的爱情表白在最后几十集里重放了大概有十次。
5. 鸣人感觉是个双相情感障碍

Ps. 哥哥早已洞察了一切,伊莲老师看完后去买了件鼬的体恤…
如果各位假日期间剧荒,又想看点有深度的东西,推荐一下《The Problem With Jon Stewart》,有两季,一共 14 集。

在美剧《The Newsroom》第一季的第一集里有一个经典片段,主角 Will McAvoy 抛出了一大段“惊世骇俗”的关于舆论误人和教化世人的理想。

我个人觉得,在美国的大牌主持人中,形象最接近 Will 这个理想的就当属囧司徒(Jon Stewart)了。尤其是他前些年在 Apple Tv 上主持的《The Problem With Jon Stewart》,非常深刻尖锐地揭露和讽刺美国当下的社会问题,每集挑选一个矛盾点,广泛采访各方的实权人士,然后用幽默辛辣的嘉宾对谈将这些问题揭露得淋漓尽致。

尤其是因为 Jon Stewart 的地位和影响力,他真的能直接访谈到那些手握大权的重要人物。这和 Youtube 上那些小成本纪录片经常被实权人物吃闭门羹完全不同,你能直接听到这些事情在最初的计划者眼中是如何被诠释的。
看完《Return To Space》,讲述 Elon Musk 关于让人类成为多星球文明(multi-planetary societies)的远景,以及 SpaceX 早期的挫折。

尤其重点讲述了 2020 年 5 月 30 日年龙飞船首次载人飞行的背后故事。这是自 2011 年 7 月 20 日 Atlantis 号航天飞机执行完 STS-135 号任务后,美国终于再次具备载人航天能力。(龙飞船的乘员中就有 STS-135 的成员)

希望能早日看到人类重归月球,甚至登陆火星。就算 Musk 有一万个缺点,但是空间探索的这个人类的边境上,这世上多如牛毛的富豪,确实只有他在拓展人类的疆域。
Laisky's Notes
实际上特德姜的《你一生的故事》讲述的就是这个观点。(特德姜的特色就是运用数学原理写科幻小说)。 当主角学会了七肢桶的语言后,就觉醒了时空意识。这也是为什么她会对女儿的死无动于衷,因为所有的事情都会发生,你只是观察到了时空的一个切面。 但这并不是说平行时空或世界线,因为不同事件的发生概率是不一样的。这个概率不是用来区分必然性和偶然性(所有事情都是必然),而是用来计算和结局的相似度,最相似的概率会作为过程显现出来。光会遍历所有的路径,但是你只能观测到最短路径。然而它确实遍历了所有的路径,因为你能观测到干涉现象。…
反正快放假了,且容许我继续就这个话题聊一聊。

《Stories of Your Life and Others》(你一生的故事)是一本非常好的书,然而改编的电影《Arrival》(降临)完全背离了原著的精神。但是这并不能说电影不好,实际上这电影在豆瓣上还有 7.8 分,并不低。

同样类似的不得不提菲利普·迪克(Philip K. Dick,简称 PKD)的《Do Androids Dream of Electric Sheep?》(仿生人会梦到电子羊吗?)所改编的《Blade Runner》(银翼杀手)。《Blade Runner》在近代取得了非常高的口碑,但是它的整个故事其实也完全背离了原著的精神内核。

《Blade Runner》以赛博朋克而闻名,但是 PKD 的一系列科幻小说的核心内核,我认为和《Stories of Your Life and Others》有着异曲同工之妙。都是在探讨世界的多面性,世界上各种各样的可能性都在同步发生,而我们只看到了其中的一小部分。

特德姜笔下的主角升华了,可以从超脱的角度看待这一切。而 PKD 的主角深陷其中,甚至于它自身的存在都在世界的多面性中变得模糊不清,世界似乎变成了一团浓雾,不同的可能性在其中交织,这座大楼上一会儿挂着纳粹的旗帜,一会儿又是美利坚的旗帜(《The Man in the High Castle》(高堡奇人))。

实话说,PKD 是唯一一个经常能把我惊吓到夜不能寐的作者,虽然他的故事并不恐怖,只是描述他所看见的世界破裂的缝隙。
Telegram Channel