2017q3 Homework1 (ternary)

contributed by <HMKRL>

---

TODO:

• 為甚麼 IOTA seed 是 81 characters?
• IOTA　為甚麼使用 tryte?
  

解釋 Balanced Ternary 原理

• 解釋 Balanced Ternary 原理

Balanced ternary 是一種數值表示系統，每個位數可以有三種狀態：

• -
• 0
• +

將

$n$ 位 Balanced Ternary 數值

$T$ 轉為 Base10 的方法如下 (T[0] is the least significant digit)：

$$\sum _{i=0}^{n}T[i]\times 3^i$$

考慮以下 Ternary 加法運算真值表：

sum	+	0	-
+	-	+	0
0	+	0	-
-	0	-	+

carry	+	0	-
+	+	0	0
0	0	0	0
-	0	0	-

參考 Fast Ternary Addition, Balanced ternary 加法運算可以透過以下半加器實作：

$$\begin{gathered} s_i=(a_i+c_i) \\ {c}_{i+1}=cons(a_i,c_i) \end{gathered}$$

其中

$cons(a,b)$ 為 Ternary Logic 的一種邏輯運算子，其真值表如下

cons	+	0	-
+	+	0	0
0	0	0	0
-	0	0	-

再以此為基礎完成全加器：

其中 ANY 為 另一種邏輯運算子，其真值表如下

cons	+	0	-
+	+	+	0
0	+	0	-
-	0	-	-

---

Balanced Ternary 的設計要解決的問題類型

考慮 4 bit unsigned integer 能表達的數值範圍：

binary: 0 ~ 15 共

$2^4$ 個不同數值
ternary: 0 ~ 80 共

$3^4$ 個不同數值

由於每個位元能儲存的資料量較多，因此 ternary 系統本身能儲存的資料量較多

此時再考慮 4 bit signed integer, 比較 ternary 及 balanced ternary 的差異：

ternary: -27 ~ 26 共 54 個不同數值
balanced ternary: -40 ~ 40 共 81 個不同數值

可以發現在考慮正負的情況下，比起 balanced ternary, ternary 系統僅能提供

$\frac{2}{3}$ 的數值範圍，原因是表示正負號必須佔用一位，但正負僅有兩種狀態，因此一部份空間無法使用

在使用 balanced ternary 時，每個位元儲存各自的正負資料，可以帶來兩個優點：

1. 方便運算： 不需額外處理正負，直接取 not 即可完成變號：

$$\begin{gathered} {39}_{10}=+++0_{bt} \\ -{39}_{10}=---0_{bt} \end{gathered}$$

2. 節省空間，增加儲存密度

現代硬體採用"開"與"關"兩種狀態代表 0 與 1
但若能製造一種硬體能儲存 + - 0 三種狀態（猜想：利用電壓具有正負或磁極做儲存），即能更有效率的利用空間

---

在 GitHub 裡頭可找到的應用案例

在 iotaledger/kerl 專案的說明中敘述：

IOTA Kerl:
IOTA is adding an additional hashing function, based on Keccak, with conversion to ternary.

The following document describes the functionality and specification to be implemented.

觀察此段程式碼

tryte_table = {
        '9': [ 0,  0,  0],  #   0
        'A': [ 1,  0,  0],  #   1
        'B': [-1,  1,  0],  #   2
        'C': [ 0,  1,  0],  #   3
        'D': [ 1,  1,  0],  #   4
        'E': [-1, -1,  1],  #   5
        'F': [ 0, -1,  1],  #   6
        'G': [ 1, -1,  1],  #   7
        'H': [-1,  0,  1],  #   8
        'I': [ 0,  0,  1],  #   9
        'J': [ 1,  0,  1],  #  10
        'K': [-1,  1,  1],  #  11
        'L': [ 0,  1,  1],  #  12
        'M': [ 1,  1,  1],  #  13
        'N': [-1, -1, -1],  # -13
        'O': [ 0, -1, -1],  # -12
        'P': [ 1, -1, -1],  # -11
        'Q': [-1,  0, -1],  # -10
        'R': [ 0,  0, -1],  #  -9
        'S': [ 1,  0, -1],  #  -8
        'T': [-1,  1, -1],  #  -7
        'U': [ 0,  1, -1],  #  -6
        'V': [ 1,  1, -1],  #  -5
        'W': [-1, -1,  0],  #  -4
        'X': [ 0, -1,  0],  #  -3
        'Y': [ 1, -1,  0],  #  -2
        'Z': [-1,  0,  0],  #  -1
        }

可以發現採用 3-bit balanced ternary 來表示 hash 結果

參考 Creating a new Seed / Wallet

A - Z + 9 就是組成 seed 的字元

而 convertBaseToBigint(array, base) 則用於計算一開始提到轉換為十進位的方法：

def convertBaseToBigint(array, base):
    bigint = 0

    for i in range(len(array)):
        bigint += array[i] * (base ** i)

    return bigint