這篇是 HITCON CMT 2023 的演講
今天就來解讀一下這篇在講什麼。我在現場聽的時候，被突如其來的數學打得頭昏眼花，事後看懂才寫了這篇xD

背景

丁特事件中，遊戲橘子公告的機率與實際上抽的機率不符合，但消費者又無法驗證，所以作者就想知道能不能設計出一個，可以在不開源的情況下驗證官方公告的機率是否為真的系統。以下是幾個重要事件的時間線。

• 2021/06 → 轉蛋法聯署
• 2021/08 → 丁特事件
• 2023/01 → 轉蛋法生效，參考日本、韓國的轉蛋法

值得注意的是日本有限制保底抽數、金額。
而大家在意的是怎麼驗證機率。

Related Works

這邊提到了兩篇 related works，但有一些各自的問題

• gacha.gamelab.com.tw
  • 第三方驗證平台(壞掉了?)，玩家自行上傳抽獎紀錄
• (PDF) Bringing transparency and trustworthiness to loot boxes with blockchain and smart contracts (researchgate.net)
  • 嘗試用 smart contract 來解決這個問題，但是這樣就是 open source 了
  • 而且在 smart contract 上還有 random source 的問題

怎麼做

轉蛋主要由兩個部分組成，隨機來源 + 轉蛋函式。
所以要可以驗證轉蛋的機率代表我們需要，可以驗證的隨機來源 + 可以驗證的轉蛋函式

Verifiable Random Source

簡單作法

所有人提供一個 random number，把大家的 xor 起來
但是這樣做可能會有 Last Contribution Attack，也就是最後一個人 C 可以暴力的嘗試不同的 c 值，選一個可以中獎的，等於最後一個人可以操控結果

HeadStart

所以這邊他們改良了前面的作法，這個作法叫做 HeadStart，這也是作者同一個實驗室他們發的論文。
這個作法主要改動了兩個部分

• 把大家的 random number 做成 Merkle Tree
• 最後會經過 Verifiable Delay Function (VDF) 的運算得到最後結果

做成 Merkle Tree 的主要好處是，驗證只需要 O(logN) 的時間和空間

VDF 則是一個需要一定的時間計算，但是可以被迅速驗證 (有點像是 Blockchain 的 POC，但是 VDF 不能被 parallelized)，因為計算需要一定的時間，所以就可以避免 Last Contribution Attack

Verifiable Function

接著有了 Verifiable Random Source 之後，我們還需要 Verifiable Function。
這邊作者直接採用了一種 Zero Knowledge Proof 叫做 PLONK。原本我們的函式長這樣 f(x) = y，那加上這個 PLONK 之後，他就會多吐出一個 proof 讓我們驗證，f(x) = y + proof。這邊其實不需要理解數學的細節，總之可以在不公開函式的情況下驗證你是用同一個函式去算出 x 的結果 y，而不是我給你輸入你才又偷偷換了另一個每次都抽不到的函式。如果真的想了解的同學可以看一下 Vitalik 大神的 ZKP 系列。

實際的流程

前面介紹了必要的元件之後，我們就可以來看實際的抽卡流程是怎麼個樣子

Probability Verification Protocol

今天我想測一下這個遊戲的機率是不是唬爛的，我就可以發起這個驗證的流程 (沒有真的抽卡，只是模擬抽卡)。
可以想像函式 f 就是一個下面這樣的函式，吃兩個參數，random source r 和遊戲參數 o。
遊戲參數裡面會有像是 VIP 等級、抽卡次數等，比如抽卡次數就很有用，可以根據抽獎次數計算要不要保底。

1
2
3
4
5
6
7
8
9
10
11
12
13

def loot(seed, params):
    random.seed(seed)
    num = random.randint(0, 999)
    
    # 20 抽保底
    if params["抽獎次數"] >= 19:
        return 1
    
    # 機率 10%
    if num < 100:
        return 1
    else:
        return 0

1. 首先，會有一個 Random Beacon 收集大家貢獻的 randomness，收集滿了之後，吐出 100 個 test data (模擬 100 次抽卡)
   • 假設是 m = 100 的話 (方便想像)
2. 這些 test data 就會丟進去函式裡面運算，最後吐出 100 個 (抽卡結果, 證明)，這些都會放在公告欄裡面
3. 最後，玩家們就可以拿 test data 和公佈欄裡面的 (抽卡結果, 證明) 去驗證函式 (透過 PLONK 的 ZKP 證明)
4. 驗證正確代表函式沒有被動手腳，所以就可以直接來算算看這 100 個抽卡結果的中獎機率是多少啦
   • 論文中還有計算說，如果官方說是 0.3 的機率，哪麼驗證出來的機率要小於多少就有很高機率他在說謊

Loot Box Opening Protocol

最後是真的要抽卡的時候的流程 (作者畫的圖好複雜，不貼了xD)

• Setup
  • (Server) 先算出一個 Hash Chain，然後把 a_n 給玩家
    • a_i = H(a_i-1)
    • a_0 -> a_1 -> a_2 -> ... -> a_n
• 以下步驟可以重複多次
  • Evaluation (開抽)
    • (Player) 隨機選一個 random 數 B，還有一些遊戲參數 O (比如 VIP 等級、抽獎次數等)，傳給 Server
    • (Server) 上次 Hash Chain 選到 a_i，這次就挑 a_i-1。 計算 random source 等於 a_i-1 || B (合併雙方的 random source)，帶入抽卡函式 f(a_i-1 || B, O) = y + proof。最後把結果 (y, proof, a_i-1) 傳回去給玩家
  • Verification
    • (Player) 拿到 proof 可以驗證是同一個函式
    • (Player) 拿到 a_i-1 可以驗證 H(a_i-1) = a_i (代表 Server 不是隨心所欲的亂選一個隨機數而是在玩家選出 B 之前就已經決定好 a_i-1 了)

這邊的重點其實是 Hash Chain 的部分，可以確保 Server 不是在收到玩家選的 random source B 之後，才挑一個抽不到卡的 random source。

結論

就是因為不想開源，所以才需要 ZKP，但仔細思考一下，其實 ZKP 的部分跟其他 Protocol 可以完全切開，ZKP 在這裡扮演的就是確保遊戲廠商至始至終都是用同一個函式，不會在模擬抽卡和真正抽卡的時候用不同的函式，這樣就可以用模擬抽卡來驗證機率了。把 ZKP 的部分去掉之後看，就會發現其實沒這麼複雜xD (不要上來就貼數學式RRR)

再來的問題就只是 Random Source 怎麼來

• 模擬抽卡: 用 HeadStart 讓大家貢獻 Random Source
• 真的開抽: Server 和 Player 雙方各貢獻一個 Random Source，然後 Server 用 Hash Chain 來證明他在 Player 選 Random Source 之前就已經選好了，不是拿到 Player 的 Random Source 才挑的

要開源的話，其實只要抽卡部分的程式碼可以開源就好了吧，這樣就完全不用 ZKP，實作就只剩 Hash Chain 那邊要實作，其他通通不需要了，模擬抽卡什麼的也不用了，都已經有 source code 看就知道機率是多少，要驗證函式的話，你只要把輸入丟進去看輸出是不是一樣的就好。

References

• 他們的簡報: 打造公平的遊戲轉蛋_在不洩漏原始碼的前提下驗證虛擬轉蛋的機率.pdf
• 他們的論文: ntu-111-2.pdf
• 他們的原始碼: WangJ509/LootBoxVerification (github.com)

這個項目算是很新的項目，去年的 9/22 - 10/3 才在第一波 ICO，每人限購 1000 USDC，當時 ICO 的價格是一顆 FLOW 要價 0.1 USDC，到現在也漲了 200 倍了吧，只恨沒有買更多啊 Orz 不過要鎖倉一年，所以要到今年底才拿的回來，但是光是產生的利息就已經回本好幾倍了xD
好了，廢話不多說，下面來介紹一下 flow 的特點。

資源

這邊先放幾個連結，有興趣入門的可以看一下

• 官方寫的入門文章
• 官方的文檔
• 國外大佬的入坑指南

特點

Flow 是專門為應用程式以及遊戲所開發的一條新的區塊鍊
在鍊上面可以用 Cadence 這個程式語言撰寫 smart contract，對比隔壁棚的 Ethereum 用 Solidity 寫 smart contract

Cadence 這個程式語言有什麼特點呢

• Resource-Oriented Programming
  • 聽說是參考 facebook 的 Libra 用的 Move 語言
  • 跟 Rust 的 ownership 很像
  • 可以看看下面兩篇 papers，在講怎麼樣設計一個適合用在 smart contract 上的語言
    • Obsidian: A Safer Blockchain Programming Language
    • Resource-Aware Session Types for Digital Contracts
• Upgradable Smart Contract
  • 多了一個 beta state 可以讓你盡情的 upgrade，在這個階段，如果使用這要用就要自行承擔風險囉，話是這樣說的
  • 等到都測試完後，就可以正式 release 了，之後就跟隔壁棚 Ethereum 的 smart contract 一樣就不能再改他了
• Built-in Logging Support
  • 只會在 transaction 上標記一個記號，你想要看 log 就自己在離線執行一次就可以看到了，不像隔壁棚 Ethereum 把 log 儲存在鍊上面
  • 在 Cadence 語言中就直接 log("hi") 就可以印 log 了，不像隔壁棚 Ethereum 還要先定義 event 再 emit

Flow 這條區塊鍊有哪些特點呢

• 垂直分工 ( pipeline )，把問題切成四份，某種問題會有一種專門的節點負責處理
  • 不像隔壁棚 Ethereum 尋求 sharding 的解決方式，用平行分工把所有交易切成很多子鍊，多了很多問題
  • 分下面四種工作
    • Consensus Nodes : 共識機制在此發功，Flow 使用 HotStuff 共識機制
    • Verification Nodes : 檢查正確性，取締違規者
    • Execution Nodes : 執行交易附帶的那些計算工作，也就是 smart contract 裡面的程式
    • Collection Nodes : 負責包裝交易們處理些雜事，再丟給 Consensus Nodes，用來提昇整體區塊鍊的效率
  • 總而言之
    • Consensus 和 Verification 這兩種 Node 是安全守門員負責讓 Flow 更安全
    • Execution 和 Collection 這兩種 Node 是瘋狂機器人負責讓 Flow 更有效率跑得更快
• 每個帳號裡面都可以有多個 smart contract，不像隔壁棚 Ethereum 的 smart contract 和 address 是一對一的關係
• 內建支援 multi-signature，每個 key 會有一個 weight，只有你提供的 key 們的 weight 加起來有 1000 就可以做事情了
• 聽官網介紹是說有帳號恢復機制，不清楚細節
• 強調說他遵守了資料庫系統的 ACID ( Atomic, Consistent, Isolated, and Durable ) 原則，因為根本上區塊鍊就是一個去中心化的資料庫

如何成為節點

官方的文檔 - Setting Up a Flow Node

Make sure you have a sufficiently fast connection; we recommend at least 1Gbps, and 5Gbps is better.

硬體要求還行，我的桌機好像還能跑，但是這個網速要求有點高啊
而且還要填表單申請，太中心化了啊
然後這裡有寫每種 node 要跑得話要 stake 多少顆 flow，最便宜也至少要 stake 135000 顆 flow，以目前的價格來看大概是 270 萬美金吧，我去

Flow 目前的一些問題

目前 Flow 還在初期階段，有些東西還沒搞好
下面一些資訊是我在 discord 群看到的

we still have a lot of things locked down in mainnet right now. The ability to create accounts is one of them. At this time only partnered wallets can create accounts. This will obviously be opened up in the future. At a minimum it won’t happen until fees are in place on mainnet.

• qvvg on discord

主網路還沒好啊，不能隨意創帳號
需要他們合作的夥伴像是 blockto 才能創，可以用 https://port.onflow.org/ 這個創帳號的樣子
還不夠去中心化啊

Flow’s fee model is still under development, but will have transaction fees. The payer of a transaction can be separate from the authorizer, so dapps can easily pay for their users transactions. Flow keeps tx fees affordable and accessible for all.

• Flow Assistant Bot on discord

手續費的機制也還沒弄好啊

Flow is an decentralized protocol being built in an open ecosystem - there is no formal roadmap but if you’d like to see areas people are currently expending effort you can take a look at issues currently in the GitHub repo https://github.com/onflow/flow/issues and feel free to create or comment on issues for anything that you think should exist on Flow.

• Flow Assistant Bot on discord

沒有正式的 roadmap

Flow 的應用

• NBA Top Shot: NBA 主題的 NFT，可以讓你收藏你最愛的球員，以及他們得分的片段等
• VIV3: 買賣 NFT 的平台
• MotoGP™ Ignition: 類似 Ethereum 上的 F1® Delta Time，同一批開發人員的樣子，只是從 F1 賽車改成 MotoGP 摩托車，可以組裝自己的車車然後跟別人比賽，下個月 3/26 開賣
• CryptoKitties: 還在計畫從 Ethereum 遷移到 Flow，不知道是哪時候

總結

Flow 提出了很多方案來改進去中心化應用面臨到的問題，接下來就要靜待時間的考驗，等潮水退了就知道 Flow 有沒有穿褲子了

Flow to the Moon 🚀

Can you decrypt RSA? I’ll give a hint value, XOR.
ここにRSAの暗号文がありますが、XORをあげるので、代わりに平文をください。

Writeups

題目很簡單，RSA 加密，多給了 $p \oplus q$ 的值

$$
\begin{align}
&p \oplus q = x \\
&p \times q = n \\
\end{align}
$$

已知 $x, n$ 求 $p, q$

假設 $x$ 的第一個 bit 是 0，那麼 $p, q$ 的第一個 bit 只有 $(0, 0)$ 或 $(1, 1)$ 兩種可能
假設 $x$ 的第一個 bit 是 1，那麼 $p, q$ 的第一個 bit 只有 $(0, 1)$ 或 $(1, 0)$ 兩種可能

所以就直接爆搜加剪枝就過了，驚不驚喜，意不意外

Final Exploit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#!/usr/bin/env python3
from Crypto.Util.number import *
from tqdm import tqdm

class Solver:
	def __init__(self, x, n):
		self.x = x
		self.n = n
		self.pq = [(0, 0)]

	def add(self, b, p, q):
		if p * q <= n and (p | (b - 1)) * (q | (b - 1)) >= n:
			self.pq.append((p, q))

	def solve(self):
		for shift in tqdm(range(4095, -1, -1)):
			b = 1 << shift
			pq, self.pq = self.pq, []
			for p, q in pq:
				if self.x & b:
					self.add(b, p | b, q)
					self.add(b, p, q | b)
				else:
					self.add(b, p, q)
					self.add(b, p | b, q | b)
		return self.pq[0]

exec(open('flag.enc').read().lower())
solver = Solver(x, n)
p, q = solver.solve()
r = (p - 1) * (q - 1)
d = inverse(e, r)
m = pow(c, d, n)
print(long_to_bytes(m))

Flag

1

TSGCTF{Absolutely, X should be 'S' in 'OPQRX'.}

1. https://furutsuki.hatenablog.com/entry/2019/05/05/163313#Crypto-497pts-10-Solves-OPQRX

有一個奇合數 $n$ ，是兩個奇質數的乘積 $n = pq$
令 $a = \frac{p + q}{2}, b = \frac{p - q}{2}$ 那麼 $n = (a + b)(a - b) = a^2 - b^2$
但是今天我們不知道 $p, q$ ，而我們想要分解 $n$
那我們就猜 $a = \lceil \sqrt{n} \rceil$ ，測試 $a^2 - n$ 是不是完全平方數
猜到的話可以從 $a, b$ 反推回 $p, q$
沒猜到就把 $a$ 加一繼續猜

使用條件

當 $|p-q|$ 很小，可以有效的分解合數 $n$

程式碼 ( python )

1
2
3
4
5
6
7
8
9
10
11

import math
import gmpy2

def fermat(n):
    a = math.ceil(math.sqrt(n))
    b2 = a * a - n
    while not gmpy2.iroot(b2, 2)[1]:
        a = a + 1
        b2 = a * a - n
    b = math.sqrt(b2)
    return [a + b, a - b]

有一個合數 $n$，有一個質因數 $p$
Pollard’s p - 1 algorithm 可以在 $p-1$ 的最大質因數很小的情況下，有效的分解合數 $n$
可以用在分解 RSA 產生的公鑰 $n$，以此破解 RSA，常見於一些 CTF 的題目中

根據費馬小定理
當 $a$ 不是 $p$ 的倍數
$a^{p-1} \equiv 1 \pmod{p} \to a^{k(p-1)} \equiv 1 \pmod{p} \to a^{k(p-1)} - 1 \equiv 0 \pmod{p}$ for some $k$
所以 $gcd(a^{k(p-1)} - 1, n)$ 一定會是 $p$ 的倍數

Pollard’s p - 1 algorithm 就是嘗試去構造出 $k(p-1)$ ，並且令 $a = 2$ ( 只要 $p \ne 2$ 上面的推論就是對的 )
也就是測試 $gcd(2^{1} - 1, n), gcd(2^{1 \times 2} - 1, n), gcd(2^{1 \times 2 \times 3} - 1, n), …$
當 $1 \times 2 \times 3 \cdots$ 是 $p-1$ 的倍數，我們就成功分解 $n$

使用條件

當 $p-1$ 最大的質因數很小，可以有效的分解合數 $n$

程式碼 ( python )

1
2
3
4
5
6
7
8
9

import math

def pollard(n):
    a, b = 2, 2
    while True:
        a, b = pow(a, b, n), b + 1
        d = math.gcd(a - 1, n)
        if 1 < d < n:
            return d