# Cairo 教學 (cont.)
###### tags: `Cairo` `StarkNet`
---
:::warning
（Last edited on 2022.10.14）很抱歉，Cairo 迭代速度太快，這份文件的內容已經過期。請參考官方網站：
- https://www.cairo-lang.org/docs/hello_starknet/index.html#
:::
---
➡ link to [First part](https://hackmd.io/w690dpAQTsKeKZv3oikzTQ)
___
[TOC]
___
**目前裡面一部分是中文，一部分是英文，請見諒**
## Dive in
### ❥ references
References 是用來紀錄並追蹤 pointers.
透過使用 reference，多項式取值的範例可以修改成:
```python=
func main():
[ap] = 100; ap++ # x
let x = ap - 1
[ap] = [x]*[x]; ap++ # x^2
let x2 = ap - 1
[ap] = [x]*[x2]; ap++ # x^3
let x3 = ap - 1
[ap] = [x] * 45; ap++ # 45x
let x_45 = ap - 1
[ap] = [x2] * 23; ap++ # 23x^2
let x2_23 = ap - 1
[ap] = [x3] + [x2_23]; ap++ # x^3 + 23x^2
let x3_p_x2_23 = ap - 1
[ap] = [x3_p_x2_23] + [x_45]; ap++ # x^3 + 23x^2 + 45x
let x3_p_x2_23_p_x_45 = ap - 1
[ap] = [x3_p_x2_23_p_x_45] + 67; ap++ # x^3 + 23x^2 + 45x + 67
ret
end
```
reference 不一定要用來存 pointer，它也可以存任何表達式:
```python=
let x = [[fp + 3] + 1]
[ap] = x # This will compile to [ap] = [[fp + 3] + 1].
```
### ❥ variables
#### 1. temporary variables
- 使用 temporary variable:
- `tempvar var_name = <expr>`
- 如果等號的右邊是個簡單的表達式，那這個宣告等價於:
```python=
let var_name = [ap]
var_name = <expr>; ap++
```
- 這邊可以看到，temporary variable 是基於 `ap` 的，相對於以下將介紹的 local variable。
- 而基於 `ap` 的 reference 因為 `ap` 改動的不確定性，該 reference 有可能被 revoke（也就是它的值被抹去、修改了： [revoked references](#revoked-reference)），也就是說 temporary variable 的值有可能變成不可用
:::spoiler 透過使用 temporary variable，多項式取值可以修改成:
```python=
func main():
[ap] = 100; ap++ # x
let x = ap - 1
tempvar res = [x]*[x]*[x] + 23*[x]*[x] + 45*[x] + 67
ret
end
```
:::
#### 2. local variables
不像基於 `ap` 的 temporary variable 會因為 `ap` 改動的不確定性導致被 revoke, local variables 是基於 `fp` 所以不會被 revoke，這表示你用 local variable 存的值在那個函式的 scope 裡面都是可以安全使用的。
- 在一個函式的 scope 裡，第一個宣告的 local variable 會儲存在 `[fp + 0]`, 第二個在 `[fp + 1]` 並以此類推.
- 但不像 temporary variable 的宣告會自動更新 `ap` 的值，local variable 的宣告沒有這個功能
- 所以如果有使用到 local variable，則你必須要手動去更新 `ap` 的值
- Cairo 編譯器會自動幫你算出一個常數 `SIZEOF_LOCALS` 來使用，這個值等於該函式裡所宣告的 local variable 數量。例如:
```python=
func main():
ap += SIZEOF_LOCALS
local x # x will be a reference to [fp + 0].
local y # y will be a reference to [fp + 1].
x = 5
y = 7
[ap] = 11
ret
end
```
或是你可以使用同樣效用的 `alloc_locals` 語法糖，其等價於 `ap += SIZEOF_LOCALS`.
- 注意：你必須要使用這兩個手動更新 `ap` 的方法之一，否則 `ap` 和 `fp` 會因為重疊而導致意外（因為在一個函式剛開始執行時，`ap` 和 `fp` 的值是一樣的，也就是會指向同一個地址）
:::spoiler click for illustration:
✅
| register | value |
| -------- | ----- |
| fp | 5 |
| | 7 |
| ap | 11 |
❎
| register | value |
| -------- | ----- |
| ap, fp | 5 != 11|
| | 7 |
:::
### ❥ compound expression and assert statement
前面的例子都是基本的表達式（兩個運算元配上一個運算子或是 double dereference），那要怎麼使用複雜的表達式呢？（不能直接使用，例如 `[ap] = [ap - 1] * [ap - 1] * [ap - 1]`）
複合表達式（compound expression）包含一個以上的表達式，例如 `[ap] * [ap] * [ap]`, `[[[ap]]] + [ap]`, …)
Cairo compiler 支援以下的語法，利用 assert 來檢查兩個複合表達式的結果是否一樣:
`assert <compound-expr> = <compound-expr>`
舉例：
```python=
let x = [ap - 1]
let y = [ap - 2]
assert x * x = x + 5 * y
```
注意，複合表達式實際上會被拆解成多個基本表達式，因此過程中 `ap` 會往前移動多個位置（要看複合表達式多複雜），所以不要以為複合表達式只有一行所以只會有一個指令、`ap` 只會 +1 而已。
也因此，要盡量避免在複合表達式裡直接去用到 `ap` 或是 `fp`，改成用 reference 或是 temporary/local variables。
:::spoiler 多項式取值範例可以用複合多項式簡化成...
```python=
func main():
[ap] = 100; ap++ # x
let x = ap - 1
let ans = ap
ap += 1
assert [x]*[x]*[x] + 23*[x]*[x] + 45*[x] +67 = [ans]
ret
end
```
:::
#### writing to empty cell
如果 `assert` 其中一邊的 memory cell 是空的話，其作用等於賦值給空的 memory cell，例如:
```python=
func main():
[ap] = 100; ap++
let x = ap - 1 # x = 100
let y = ap # y points to an empty cell
assert [x] * [x] = [y] # write 10000 to the cell
ret
end
```
### ❥ struct and typed reference
假設你用 `fp` 宣告了一組三個變數 `x`, `y` 和 `z`，它們可以分別用 `[[fp] + 0]`, `[[fp] + 1]` and `[[fp] + 2]` 的方式來讀取，但如果數量一多，管理依然麻煩。
你可以透過定義一個 `struct` 的方式來更方便取用這一組變數:
```python=
struct MyStruct:
member x : felt
member y : felt
member z : felt
end
```
如此讀取 `y` 就變成 `[[fp] + MyStruct.y]`
- 把 `MyStruct.y` 看作是 offset 而不是實際去讀取 `y`
另外 `struct` 的大小也可以利用 `Mystruct.SIZE` 來讀取
- 假設你有一個 `struct` 陣列，你可以利用 `struct` size 來讀取下一個 struct，例如 `[ptr + MyStruct.SIZE]`
#### typed local variable
和 Reference 一樣，local variable 也可以有型別宣告。注意，在目前的 Cairo 版本，local variable 的型別必須是 explicitly stated，它沒辦法從賦值的值來自動推斷型別（沒有宣告就會用 `felt`）。
以下是兩種宣告 local variable 型別的方式（`x` 和 `y`）：
```python=
# Suppose we declare a struct T
struct T:
member a : felt
member b : felt
end
func main():
alloc_locals
local x : T* = <expr>
local y : T = <expr>
...
ret
end
```
注意這兩種宣告方式是不一樣的：
- 第一種（第九行）宣告的是一個指向型別 `T` 的指標，也因為是一個指標，所以他只會佔用一個 memory cell
- 但實際的 `T.a` 和 `T.b` 呢？它們會被 allocate 在其他（和 `fp` 無關的） memory cell，而 `x` 的值就是它們的 memory cell 位置
- `x.a` 實際上會等於 `[[fp + 0] + T.a]`
- 第二種（第十行）宣告的是 `T` 型別，也就是 `T` 的 member 有幾個，就會佔用幾個 memory cell
- 所以 `y.a` 和 `y.b` 的位置就會分別是在 `fp + 1 + T.a` 及 `fp + 1 + T.b`
- 所以 `x.a` 會等於 `[fp + 1 + T.a]` 而不是 `[[fp + 1] + T.a]`
- 但要注意的是 `y` 會是 `struct` 的地址（`fp + 1` 而不是 `[fp + 1]`），所以你直接拿 `y` 值來用的話有可能會噴錯
- 例如 `tempvar z = y` 會噴錯，因為這會編譯成 `[ap] = fp + 1`，而這不是一個合法的 Cairo 指令
:::spoiler `x`、`y` memory cell 示意圖:
| memory cell address | value |
| -------- | ----- |
| fp | x* |
| fp + 1 + T.a | y.a |
| fp + 1 + T.b | y.b |
| ... | ... |
|[fp + 0] + T.a | x.a |
|[fp + 0] + T.b | x.b |
假設 `fp = 100`，`x = 133`
| memory cell address | value |
| -------- | ----- |
| 100 | x* |
| 101 | y.a |
| 102 | y.b |
| ... | ... |
|133 | x.a |
|134 | x.b |
:::
### ❥ function
```python=
# Declare a function
func function_name():
# Your code here.
return ()
end
# Call a function in either two ways
call function_name
function_name()
```
注意，目前還不支援 nested function call，也就是不能寫成 `foo(bar())`
#### function arguments
假設你有一個 `foo` 函式:
```python=
func foo(x, y) -> (z, w):
[ap] = x + y; ap++ # z.
[ap] = x * y; ap++ # w.
ret
end
```
以下這兩種呼叫函式的方式是一樣的:
```python=
# With syntactic sugar:
foo(x=4, y=5)
# Using call, but then you have to write
# the arguments to the stack beforehand
[ap] = 4; ap++ # x.
[ap] = 5; ap++ # y.
call foo
```
#### return values
如同你在上面看到的，function argument 在傳入的方式是把 argument 先寫進 `ap` 裡，然後再跳轉到 `foo` 裡，在 `foo` 裡就可以用 `[ap - 1]`、`[ap - 2]` 來讀取 argument。
而 return 的方式也是一樣，在 return 前先把 return 值寫進 `ap` 裡，然後再 return。caller function 就可以用 `[ap - 1]`、`[ap - 2]` 來讀取到 return 值。
```python=
# For example, to use the values returned by foo you may write:
foo(x=4, y=5)
[ap] = [ap - 1] + [ap - 2]; ap++ # Compute z + w.
```
##### syntatic sugar for return values
像是上面 `struct` 裡講到的 `Mystruct.x`、`Mystruct.y`，Cairo 編譯器也會自動為 return 值生成一樣的 offset 值，例如 `foo.Return.z` 及 `foo.Return.w` 分別代表 `-1` and `-2`。所以你可以透過 `[ap + foo.Return.z]` 來讀取 `foo` 的 return 值 `z`。
你也可以用 typed reference 來代表 return 值：`let foo_ret : foo.Return = ap`。
如此 `foo_ret.z` 就會回傳 `z` 的值。
```python=
# With syntactic sugar:
let foo_ret = foo(x=4, y=5)
# foo_ret is implicitly a reference to ap with type foo.Return.
[ap] = foo_ret.z + foo_ret.w; ap++ # Compute z + w.
```
##### unpacking return values
你也可以直接用 tuple 的方式來 unpack return values：
```python=
let (z, w) = foo(x=4, y=5)
[ap] = z + w; ap++
```
在很多情況中，你會希望用 local variable 來存下 return value，避免 reference 之後被 revoke（下面馬上會講到）：
```python=
let (local z, local w) = foo(x=4, y=5)
[ap] = z + w; ap++
```
在函式內，你也可以直接回傳一個 tuple：
```python=
func foo() -> (a, b):
return (<expr0>, b=<expr1>)
end
```
這會等同於：
```python=
func foo() -> (a, b):
[ap] = <expr0>; ap++
[ap] = <expr1>; ap++
ret
end
```
#### entry point of Cairo program: main
每一個 Cairo 程式的進入點都是 `main` 函式，所以一定要宣告 `main` 函式。
註（2021/7/3）：在 StarkNet 裡的 Cairo 程式就不需要特地寫 `main`，因為沒有進入點，任何宣告為 `external` 的函式都能被直接呼叫。
### ❥ revoked reference
如果在一個基於 `ap` 的 reference 宣告及使用該 reference 的 insturction 中間，有出現 jump label 或是 function call 的話，這個 reference 的值可能會被 revoke，因為 compiler 沒辦法算出這中間`ap` 的改動（你有可能在這之間呼叫了某個函式，而該函式把 `ap` 的值加了 `100` 上去）。
不是基於 `ap` 的 reference (例如, `let x = [[fp]]`) 則不會被 revoke, 但同樣的，如果你試圖在函式之外的範圍使用該 reference，則一樣會非預期的結果產生（因為 `fp` 的 scope 是綁函式的）。
:::spoiler example 1
嘗試在本地端編譯以下代碼，並指定 `--steps=32 --print_memory`：
```python=
func main():
let x = [ap]
[ap] = 1; ap++
[ap] = 2; ap++
[ap] = x; ap++
jmp rel -1 # Jump to the previous instruction.
end
```
:::
:::spoiler example 2
對 reference 做 re-binding 是可以的，例如：
```python=
let x : T* = cast(ap, T*)
x.a = 1
# ...
# Rebind x to the address fp + 3 instead of ap.
let x : T* = cast(fp + 3, T*)
x.b = 2
```
Reference 不是變數：reference 是按照靜態分析的結果，去算出依照每個 instruction 執行的順序，其所使用到的 reference 的相對參照。
它可以在有 jump 的條件下運作，但如果因為 jump 導致有重複宣告的 reference 出現，則 reference 一樣會被 revoke。
例如下方範例，jump 之前有一個 reference `y` 的宣告（`let y = 1`），但 jump 後也有一模一樣的 reference 宣告（`let y = 2` or `let y = 3`）。
如果你嘗試在第 16 行以後再去使用 y 的值，那 compiler 就會噴錯
```python=
func foo(x):
let y = 1
jmp x_not_zero if x != 0
x_is_zero:
[ap] = y; ap++ # y == 1.
let y = 2
[ap] = y; ap++ # y == 2.
jmp done
x_not_zero:
[ap] = y; ap++ # y == 1.
let y = 3
[ap] = y; ap++ # y == 3.
done:
# Here, y is revoked, and cannot be accessed.
# `Reference 'y' was revoked.` error will be thrown if trying to access
ret
end
```
This code will return either `[1, 2]`, or `[1, 3]`.
:::
### ❥ built-ins
Builtins 包含一組經過優化的底層執行單元，例如 range-checks、Pedersen hash、ECDSA 等等，這些功能如果直接用 Cairo 來實現的話效率很低。
每個使用到的 builtin 都會有一段連續的 memory 劃分給它，並針對裡面的 memory cell 加上額外的檢查和限制。例如 range-checks builtin 就會對它的 memory cell 的值做大小範圍的檢查。
使用 builtin 的方式即是透過寫進這些 builtin 的 memory cell。例如下面這個例子使用 Pedersen hash 來算出 `hash(x, y) == z`：
```python=
x = [p] # Write the value of x to [p + 0].
y = [p + 1] # Write the value of y to [p + 1].
z = [p + 2] # The builtin enforces that
# [p + 2] == hash([p + 0], [p + 1]).
```
因為這些也都是 memory cell，所以 `[p + 0]`, `[p + 1]`, `[p + 2]` 寫過後便不能再使用，而要接著使用 `[p + 3]`, `[p + 4]`, `[p + 5]`，以此類推。所以這表示我們在使用 builtin 的過程也要用指標來追蹤尚未使用的 builtin 的 memory cell。
習慣是，一個函式若使用了 builtin，則它會以 builtin 的指標當參數，並回傳更新後的 builtin 指標，例如：
```python=
func hash2(hash_ptr, x, y) -> (hash_ptr, res):
# Invoke the hash function.
x = [hash_ptr]
y = [hash_ptr + 1]
# Return the updated pointer (increased by 3 memory cells)
# and the result of the hash.
return (hash_ptr=hash_ptr + 3, res=[hash_ptr + 2])
end
```
Cairo 有為部分的 builtin 製作 Typed references，方便使用。例如
`starkware.cairo.common.cairo_builtins` 裡的 [`HashBuiltin`](https://github.com/starkware-libs/cairo-lang/blob/544523567d16d22c5c423fcccabedd4715e391a6/src/starkware/cairo/common/cairo_builtins.cairo#L2):
```python=
from starkware.cairo.common.cairo_builtins import HashBuiltin
func hash2(hash_ptr : HashBuiltin*, x, y) -> (
hash_ptr : HashBuiltin*, res):
let hash = hash_ptr
# Invoke the hash function.
hash.x = x
hash.y = y
# Return the updated pointer (increased by 3 memory cells)
# and the result of the hash.
return (hash_ptr=hash_ptr + HashBuiltin.SIZE, res=hash.result)
end
```
#### implicit arguments
Cairo 有提供一個方便管理 builtin 的指標的語法糖，叫做 **“Implicit arguments”**。 透過大括號 (`{}`) 來把 builtin 指標宣告為 implicit arguments。這會自動把指標加為函式參數和回傳值，所以你就不必自己再寫一個回傳指標的指令:
```python=
from starkware.cairo.common.cairo_builtins import HashBuiltin
func hash2{hash_ptr : HashBuiltin*}(x, y) -> (res):
# Create a copy of the reference and advance hash_ptr.
let hash = hash_ptr
let hash_ptr = hash_ptr + HashBuiltin.SIZE
# Invoke the hash function.
hash.x = x
hash.y = y
# Return the result of the hash.
# The updated pointer is returned automatically.
return (res=hash.result)
end
```
Cairo 編譯器會自動幫你回傳 `hash_ptr` 所 binding 的值，但這不表示編譯器會自己幫你更新指標，指到下一個沒使用到的 memory cell，你還是得自己更新：`let hash_ptr = hash_ptr + HashBuiltin.SIZE`（這稱作 reference rebinding）。
implicit argument 還有一些複雜的小細節，請見：
- Some [notes](https://www.cairo-lang.org/docs/how_cairo_works/builtins.html#calling-a-function-that-gets-implicit-arguments) on passing implicit arguments to called function.
- [Save pointer to prevent getting revoked](https://www.cairo-lang.org/docs/how_cairo_works/builtins.html#revoked-implicit-arguments)
#### range-check builtin
因為 Cairo 裡的數字運行在質數域裡，所以直接的大小比較是缺乏清楚定義的。例如假設質數為 `p`，則 `p + 1` 和 `2` 誰比較大？
因此 Cairo 裡不支援 `<` 或 `>` 等等的指令，而是另外提供一個 builtin - range-check builtin 和建構於其上的 library 讓你來做數值的比較。
range-check builtin 會檢查一個值是否介於 [0, 2^128^) 之間：
```python=
# ptr 是 range-check builtin 的指標
0 <= [ptr + 0] < 2^128
0 <= [ptr + 1] < 2^128
0 <= [ptr + 2] < 2^128
...
```
如果你要檢查一個值 `x` 是否在一個更小的範圍 `BOUND` 內（也就是 `BOUND` 小於 2^128^），你必須使用兩次 range-check builtin
1. 第一次先檢查 0 <= x < 2^128^
2. 第二次檢查 0 <= BOUND - x < 2^128^
⭐️exercises
- 為什麼單純檢查 0 <= BOUND - x < 2^128^ 是不夠的?
- 如果要檢查 0 <= x < 2^200^ 要怎麼做到？ (會需要用到一次以上的 range-check builtin)
:::spoiler Ans:
- 為什麼單純檢查 0 <= BOUND - x < 2^128^ 是不夠的?
- 如果 x 小於，0 <= BOUND - x < 2^128^ 的檢查也會通過
- 如果要檢查 0 <= x < 2^200^ 要怎麼做到？ (會需要用到一次以上的 range-check builtin)
- 2^200^ = 2^128^ * 2^72^
- 所以我們把 x 拆成 a * 2^128^ + b
- 然後檢查 a 介於 [0, 2^72^) 及 b 介於 [0, 2^128^)
:::
#### integer division
如同在基礎介紹那篇講到的，盡量避免直接使用除法 `/` 來做除法運算，你可能會得到意料之外的結果。
除法的介紹部分在開發者文件裡有詳細介紹該怎麼實作除法運算： [Integer division](https://www.cairo-lang.org/docs/how_cairo_works/builtins.html#integer-division)
或是你可以直接從 [math library](https://github.com/starkware-libs/cairo-lang/blob/v0.1.0/src/starkware/cairo/common/math.cairo) import 你需要的除法運算來用。
### ❥ layout
Cairo 裡提供不同種的 builtins 可以使用，你可以在你的 Cairo 檔案開頭用 `%builtins XXX YYY` 來指定要使用到哪些 builtin。
但有一個要求是你在執行 `cairo-run` 時要透過 `--layout` flag 來指定要哪一種 layout，Cairo 裡有規定不同 layout 裡包含了哪些 builtin。
預設（也就是沒有指定 `--layout`）不包含任何 builtin，所以如果你的代碼會需要 output 或是做 hash 運算的話，你就需要指定 layout，例如 `--layout=small`。
但當前只有 `small` 可以選擇。
每一個透過 `%builtins` 指定的 builtin 都會在 `main()` 函式裡新增屬於自己的參數和回傳值。你也可以把它們變成 implicit argument：
```python=
%builtins output pedersen
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.hash import hash2
# Implicit arguments: addresses of the output and pedersen
# builtins.
func main{output_ptr, pedersen_ptr : HashBuiltin*}():
# The following line implicitly updates the pedersen_ptr
# reference to pedersen_ptr + 3.
let (res) = hash2{hash_ptr=pedersen_ptr}(1, 2)
assert [output_ptr] = res
# Manually update the output builtin pointer.
let output_ptr = output_ptr + 1
# output_ptr and pedersen_ptr will be implicitly returned.
return ()
end
```
### ❥ recursion instead of loops
Cairo 的設計裡，memory 是 immutable 的。這類似於 functional programming 語言，裡面的物件也是 immutable 的。這也造成 Cairo 和那類語言一樣，會偏好使用 recursion 而非 loop。
```python=
# Computes the sum of the memory elements at addresses:
# arr + 0, arr + 1, ..., arr + (size - 1).
func array_sum(arr : felt*, size) -> (sum):
if size == 0:
return (sum=0)
end
# size is not zero.
let (sum_of_rest) = array_sum(arr=arr + 1, size=size - 1)
return (sum=[arr] + sum_of_rest)
end
```
但真的要寫 loop [也不是不行](https://github.com/starkware-libs/cairo-lang/blob/8a7f04feecbd51bf70366fc542456d32ad848d59/src/starkware/cairo/common/hash_chain.cairo#L8)
不過有一些限制，例如在 loop 裡你不能呼叫其他函式。
### ❥ hint
在前一份文件裡有提到 Cairo 沒辦法做原生的模數運算（像是 `[ap] = x % y`）。 那要怎麼做模數運算？
先看以下例子：
```python=
[ap] = 25; ap++
[ap - 1] = [ap] * [ap]; ap++
```
這對 Verifier 來說是一段很正常的代碼，但是對 Prover 來說並非如此(`[ap - 1]` 的值可以是 `5` 或是 `-5`，那到底是 `5` 還是 `-5`？)。因此我們要明白的指示它這個值（也就是這個平方根）要怎麼算出來的
這就要藉由所謂的 **hints**。一個 hint 是一段 python 代碼，這一段代碼會是由 **Prover** 在**下一個 instruction 執行之前**來執行
範例如下：
```python=
[ap] = 25; ap++
%{
import math
memory[ap] = int(math.sqrt(memory[ap - 1]))
%}
[ap - 1] = [ap] * [ap]; ap++
```
為了要在 hint 裡取用到 memory 的值，例如 `[ap]`，我們使用 `memoery[ap]` 這樣的語法（因為 `[ap]` 在 python 裡不是一個合法的語法）。
或如果要取用某個常數值 `x`，語法會是 `ids.x`.
- 函式的參數或是 reference 都是使用一樣的 `ids` 語法來取用
:::spoiler hint is not instruction
注意：hint 是附加於它的下一個 instruction 上，並且是在該 insturction 執行之前所執行的。
**hint 本身不是一個 instruction**
所以下面這個範例
```python=
%{ print("Hello world!") %}
jmp rel 0 # This instruction is an infinite loop.
```
會進入一個不斷印出 `Hello world!` 的無窮迴圈（而不是印出一次 `Hello world!` 然後才進去無窮迴圈）
:::
#### hint is a helper for prover
Verifier 是看不到 hint 的代碼的。所以 Verifier **必須要驗證 input**。
### ❥ program input
在 Cairo 中要怎麼提供 program input 呢？假設你想證明你知道某個 hash digest 的 pre-image
`hash_digest = SomeHashFunction(pre_image)`
```python=
%builtins pedersen
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.hash import hash2
func main():
# Prove that you know a pre-image PREIMAGE
# that would result in a digest of value
# 0xaabbccdd...
let (digest) = hash2{hash_ptr=pedersen_ptr}(PREIMAGE, 0)
assert digest == %[ 0xaabbccdd... %]
return()
end
```
首先，將你的 program input 寫在一個 json 檔裡頭，然後透過 `cairo-run --program_input=INPUT_FILE.json ...` 的參數將它傳入 Cairo program。
```json=
{
preimage: 1234
}
```
接著你便可以透過 hint 來取用到該 json 檔的內容。語法是 `program_input[XXX]`
```python=
%builtins pedersen
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.hash import hash2
func main{pedersen_ptr : HashBuiltin*}():
alloc_locals
local preimage
%{ ids.preimage = program_input['preimage'] %}
let (digest) = hash2{hash_ptr=pedersen_ptr}(preimage, 0)
assert digest == %[ 0xaabbccdd... %]
return ()
end
```
:::spoiler example: create dict of account state from program input
```python=
from starkware.cairo.common.dict import (
DictAccess, dict_new)
func get_account_dict() -> (account_dict : DictAccess*):
alloc_locals
%{
account = program_input['accounts']
initial_dict = {
int(account_id_str): balance
for account_id_str, balance in account.items()
}
%}
# Initialize the account dictionary.
let (account_dict) = dict_new()
return (account_dict=account_dict)
end
```
- [dict_new](https://github.com/starkware-libs/cairo-lang/blob/8a7f04feecbd51bf70366fc542456d32ad848d59/src/starkware/cairo/common/dict.cairo#L5)
```python=
func init_state(account_dict: DictAccess*):
alloc_locals
local state : State
assert state.account_dict_start = account_dict
assert state.account_dict_end = account_dict
end
```
- [dict_update](https://github.com/starkware-libs/cairo-lang/blob/8a7f04feecbd51bf70366fc542456d32ad848d59/src/starkware/cairo/common/dict.cairo#L52)
```python=
func update_account(state: State, account_id, prev_value, new_value):
alloc_locals
let account_dict_end = state.account_dict_end
dict_update{dict_ptr=account_dict_end}(
key=account_id,
prev_value=prev_value,
new_value=new_value)
local new_state: State
assert new_state.account_dict_start = (
state.account_dict_start)
assert new_state.account_dict_end = account_dict_end
end
```
illustration:
⬇
⬇
⬇
⬇
:::
### ❥ no public input
如果 hint 是只有 Prover 可見的，從 hint 把 program input 讀進來也只有 Prover 才看得到。在 Cairo 裡是沒有 public input 的選項的。
那要怎麼樣達到 public input 的效果呢？例如假設我是一個 L2 Dapp 的 Operator，我要把我 Dapp 的 state 更新到下一個 state，要怎麼做？
首先，L1 上合約儲存的 state root 會是原本預期的 public input，那我要怎麼把 state root 更新為下一個 state 的 state root？
在 Cairo 裡因為沒有 public input 的選項，所以我們改用 public output 來達成我們的目的。
我們把原本預期要是 public input 的值從 program input 讀進來，然後我們 output 這個值。在這個範例中，就是把 old state root 讀進來並且 output 出來。
接著我們會對 state 做一些運算，例如驗算交易並更新使用者餘額。運算完後會得到一個新的 state，我們也把這個 state root output 出來，如下：
```python=
func main{output_ptr: felt*}():
%{
# read from program_input
%}
# commit them
let (local pre_state_root) = compute_merkle_root(...)
process_xxx(...)
let (local post_state_root) = compute_merkle_root(...)
# output both state root
[output_ptr] = pre_state_root
[output_ptr + 1] = post_state_root
let output_ptr = output_prt + 2
return()
end
```
重點來了，Cairo program 所 output 出來的值，都會被 commit，這些被 commite 的值會被一並送到鏈上去。等到鏈上合約驗證完 proof，就會把相對應的 commit 的值寫進一個合約。
- 這些值會被集合 commit 成一個值，稱做 [fact](#fact)
- fact 會被寫進 fact registry 合約，任何人都可以去查詢某個 fact 有沒有被寫進去
等到 fact 被寫進去以後，我就可以送交易到我 L1 上的 Dapp 合約，這個交易指示 Dapp 合約去更新 state root，而在這筆交易裡我會提供這次 state 更新所用到的值，例如處理了哪些交易（所以其實剛剛上面的代碼也要從 program input 讀取交易內容並 output 交易內容），以及新的 state root。
接著合約會把這些交易和它本身所存的 (old) state root 集合起來然後 commit，算出它們相對應的 fact 值，然後再去 fact registry 合約查詢這個 fact 值是否有被註冊。
- 如果有被註冊，表示這個 state transition 已經被驗證，所以可以放心更新 stat root。
- 如果我提供的 public input 和實際的 public input 有出入，則 Cairo program 算出並寫入的 fact 不會等於 Dapp 合約自己算出的 fact。因此 Dapp 合約查詢 fact 時會發現它算出的 fact 沒有被寫入，也就不會完成 state 更新。
- 如果 Cairo program 運算得到一個不一樣的 state（也就是我故意給 Dapp 合約一個假的 state root），那 Dapp 合約一樣會算出不一樣的 fact，結果同上。
### ❥ Fact
#### how is the fact computed?
在基礎介紹裡有提到，fact 就像 proof 的 id，那實際上 fact 是怎麼算出來的呢？
fact 是組合兩個部分再拿去 hash 的[結果](https://github.com/starkware-libs/cairo-lang/blob/8a7f04feecbd51bf70366fc542456d32ad848d59/src/starkware/cairo/bootloader/generate_fact.py#L37)：
1. 第一部分是[程式的 hash](https://github.com/starkware-libs/cairo-lang/blob/8a7f04feecbd51bf70366fc542456d32ad848d59/src/starkware/cairo/bootloader/hash_program.py#L10)
- 實際上是你 Cairo 代碼本身、及使用到的 bultin 等等拼湊後所拿去 hash 得到的結果
2. 第二部分是[output 的 hash](https://github.com/starkware-libs/cairo-lang/blob/8a7f04feecbd51bf70366fc542456d32ad848d59/src/starkware/cairo/bootloader/compute_fact.py#L40)
所以如果你的代碼一樣，output 值也都一樣，那算出來的 fact 就會一樣。
Sign in with Wallet
Connect another wallet