2017q3 Homework1 (ternary)

contributed by <vonchuang>

已列出 IOTA 中以python 實作 ANY、full adder 以及 ripple-carry adder 的程式碼列表，但沒有 IRI 的部分

尚未尋得

「效率更好的加法器應為 Carry Lookahead ，然其在 Balanced ternary 實作上結構複雜」 => 著手實驗了嗎？

待補

「在上方程式法第 21 行處可看出，IOTA 使用於 Transaction 的 Hash Function 為 Curl，是 IOTA團隊為了解決問題而建立的新 Hash Function」 => 描述正確嗎？

已改善

光有程式列表，但沒有實際測試和評估，怎知道實際狀況？

待補

為何近五天都沒進展?00
課程助教

先去研究phonebook…
vonchuang

摘要簡介：Balanced Ternary
原理
- Radix Economy
- 十進位、二進位、三進位比較
- 加減運算
- bal3 to dec ( 數字系統轉換 )
- dec to bal3 ( 數字系統轉換 )
- Half Adder(電路實作)
- Full Adder(電路實作)
- 歷史
應用：IOTA
- IOTA 簡介
- Balanced Ternary 應用
- IOTA 架構
- Curl
- Kerl
- IRI
參考資料

摘要簡介：Balanced Ternary

Donald Knuth 在其名著 the art of computer programming中提及：

"Perhaps the pretties number system of all is the balance ternary notation."

本篇欲探討 Balanced Ternary 的原理及表示、從數學上證明三進位的經濟ㄧ性，並研究如何以電路實作其半加器及全加器，最後嘗試從多篇參考資料及原始碼中找出 Balanced Ternary 如何應用在 IOTA 中，以及為什麼會選擇使用 Balanced Ternary。

原理

TODO：檢查、歷史待補、實作

在二進位，我們用0與1表達 False 和 True。而在三進位，則用0、1、2表示 False、Unknown 和 True；平衡三進位（Balanced Ternary）則用-1、0、1表示，其又可簡寫為T、0、1。
由於平衡三進位有負數，因此不用額外的位元即可直接表達負數。
若要表達某數之相反數，則只需把T與1相互調換即可。
如

{24.8}_{d e c} = 10 T 1. T 11 T_{b a l 3}

，則

- {24.8}_{d e c} = T 01 T .1 T T 1_{b a l 3}

Radix Economy

在二進位，每一個位數叫做一個bit，三進位下每一個位數叫做一個trit。
一個位數在基數為 b 的數字下能負載

l o g_{2} b

個 bit。故在三進位，一個 trit 能負載大約 1.58 bits；十進位下的一個位數則能負載約莫 3.32 bits。然相對的，十進位的每個位數皆有十種不同可能的值，遠比二進位及三進位複雜。
而將以上兩種比較方式綜合考量，即為基需（Radix Economy）的概念。

簡單來說，基需係指在一個固定基數下，表示一個數所需的開銷。比如，若欲表示 1000 以下的數，在十進位制需 3 位數，在八進位制需 4 位數，在二進位制下則需 10 位數。
已知對於任意數 N，在基數 b 下表示數字 N 需要

l o g_{b} N + 1

位數。故基需的精確定義為：

E (b, N) = b \times (l o g_{b} N + 1)

舉例來說，表示999時，十進位下的基需是

10 \cdot 3 = 30

，八進位下的基需是

8 \cdot 4 = 32

，二進位下的基需是

2 \cdot 10 = 20

。

那麼，在何時基需為最小？
由

E (b, N) = b \times (l o g_{b} N + 1) \approx b \times l o g_{b} N = (b / l n (b)) \times l n (N)

可知在

b = e

時，基需為最小。

The base
$e$ is the most economical choice of radix β>1 (Hayes 2001), where the radix economy is measured as the product of the radix and the length of the string of symbols needed to express a given range of values.

而3是最接近

e

的整數，故我們從數學上證明了三進位是最經濟的。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

圖片出處：三生萬物

參考資料：

十進位、二進位、三進位比較

十進位	1	2	3	4	5	6	7	8	9	10
二進位	1	10	11	100	101	110	111	1000	1001	1010
三進位	1	2	10	11	12	20	21	22	100	101
平衡三進位	1	1T	10	11	1TT	1T0	1T1	10T	100	101

加減運算

與十進位、二進位依樣，逐位做加減法即可。如：

1 T T 1 T T .1 T T 1 \underset{―}{+ 11 T 1. T} 1 T 0 T 10.0 T T 1 \underset{―}{+ 1 T} 1 T 1110.0 T T 1 \underset{―}{+ T} 1 T 0110.0 T T 1

bal3 to dec ( 數字系統轉換 )

各位的數字和位權相乘然後疊加起來，即為該數的數值。
範例：

\begin{aligned} 1 T T 1. T T & = 1 \cdot 3^{3} + (- 1) \cdot 3^{2} + (- 1) \cdot 3^{1} + 1 \cdot 3^{0} + (- 1) \cdot 3^{- 1} + (- 1) \cdot 3^{- 2} \\ = 15 \frac{5}{9} \end{aligned}

dec to bal3 ( 數字系統轉換 )

可由以下公式完成轉換：

(a_{n} a_{n - 1} . . . a_{1} a_{0} . c_{1} c_{2} c_{3} . . .)_{b} = \sum_{k = 0}^{n} a_{k} b^{k} + \sum_{k = 1}^{\infty} c_{k} b^{- k}

其中

a_{n} a_{n - 1} . . . a_{1} a_{0} . c_{1} c_{2} c_{3} . . .

為原數字系統之表示。
b 為原基數，如若原數字系統為十進位，b 則為10。

a_{k}

和

c_{k}

分別為整數和小數部分之數字。
範例：

\begin{aligned} {24.8}_{d e c} & = 1 T \cdot (101)^{1} + 11 \cdot (101)^{0} + 10 T \cdot (101)^{T} \\ = 1 T 1 T + 11 + 10 T / 101 \\ = 10 T 1. {\overset{―}{T 11 T}}_{b a l 3} \end{aligned}

參考資料

Wikipedia:Balanced ternary

Half Adder(電路實作)

若欲更了解 Balanced Ternary 的原理及基礎運算操作，可回到最原本的電路上。
以下以電路實作出 Balanced Ternary 的半加器，首先須先列出其 Truth Table：

$i n p u t s a_{i} c_{i}$	$o u t p u t s c_{i + 1} s_{i}$
$- -$	$- +$
$- 0$	$0 -$
$- +$	$0 0$
$0 -$	$0 -$
$0 0$	$0 0$
$0 +$	$0 +$
$+ -$	$0 0$
$+ 0$	$0 +$
$+ +$	$+ -$

$c_{i + 1}$	$c_{i} - 0 +$
$- a_{i} 0 +$	$- 0 0 0 0 0 0 0 +$

$s_{i}$	$c_{i} - 0 +$
$- a_{i} 0 +$	$+ - 0 - 0 + 0 + -$

為了實現加法器，在此先設計出一 ternary multiplexer，共五個 pin 腳，依據 sel之數值（-1、0、1）選擇輸出 out 之值（inN、inO、inP）
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
圖片出處：Ternary computing: basics
而此 ternary multiplexer，可依需求輸入不同的inN、inO、inP，使作出所需效果。在此，為了實做出加法器，我們分別做出計算A+1、A-1、min(A,0)、max(A,0)之 ternary multiplexer：
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
圖片出處：Ternary computing: basics
有了以上的 multiplexers，現在可以分別實作出半加器的
$S$ 和
$C_{o u t}$ 。
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
圖片出處：Ternary computing: basics
最後，將以上二者結合起來，即做出 Balanced Ternary 的半加器。
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
圖片出處：github:ternary-logisim
其中，以上之電路有又可用更為簡單的方式表示。
$S$ 和
$C_{o u t}$ 可分別記為：
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
圖片出處：Standard Ternary Logic
在此列出 IOTA 的 open source code 中以 python 實作 SUM 和 CONS 的部分：
























function sum( a, b ) {

    var s = a + b;

    switch( s ) {

        case 2: return -1;
        case -2: return 1;
        default: return s;

    }
}

function cons( a, b ) {

    if( a === b ) {

        return a;

    }

    return 0;
}

故 Balanced Ternary 的半加器可以以下之圖示表示：

圖片出處：Fast Ternary Addition

Full Adder(電路實作)

欲做出 Balanced Ternary 的全加器，一樣是先列出 True Table：

圖片出處：Fast Ternary Addition
當
$C_{i n} = 0$ 時，全加器即與半加器無異，故可知全加器可由半加器組成。
先分別實作出全加器的
$S$ 和
$C_{o u t}$ （以下圖之綠色部分即為半加器）：

圖片出處：Ternary computing: basics
最後，將二者和一，即為 Balanced Ternary 全加器。

圖片出處：github:ternary-logisim
Balanced Ternary 全加器的簡易圖示為：

圖片出處：Fast Ternary Addition
其中的 ANY 為：

圖片出處：Standard Ternary Logic

在此列出 IOTA 的 open source code 中以python 實作 ANY、full adder 以及 ripple-carry adder 的部分：
















































function any( a, b ) {

    var s = a + b;

    if ( s > 0 ) {

        return 1;

    } else if ( s < 0 ) {

        return -1;

    }

    return 0;
}

function full_add( a, b, c ) {

    var s_a     =   sum( a, b );
    var c_a     =   cons( a, b );
    var c_b     =   cons( s_a, c );
    var c_out   =   any( c_a, c_b );
    var s_out   =   sum( s_a, c );

    return [ s_out, c_out ];

}

function add( a, b ) {

    var out = new Array( Math.max( a.length, b.length ) );
    var carry = 0;
    var a_i, b_i;

    for( var i = 0; i < out.length; i++ ) {

        a_i = i < a.length ? a[ i ] : 0;
        b_i = i < b.length ? b[ i ] : 0;
        var f_a = full_add( a_i, b_i, carry );
        out[ i ] = f_a[ 0 ];
        carry = f_a[ 1 ];

    }

    return out;

}

在上述全加器之 True Table 中，共有27種可能，在經過優化之後，可以一定程度上的減少，但在效率上仍舊不夠好。因以上之實作皆為 ripple-carry adder，一個 trit 的 balanced adder 分別需要 10 minterms 和 18 minterms 計算
$C_{o u t}$ 和
$S$ ，比起 unsigned 或 3's complement adder 多出大約 50% 的複雜度。故若以 ripple-carry adder 實作加法器，並以加法的複雜度為考量，balanced ternary 並非最佳選擇。
效率更好的加法器應為 Carry Lookahead ，然其在 Balanced ternary 實作上結構複雜，在此不詳述。更詳細的說明可參考 Fast Ternary Addition

參考資料

歷史

TODO：待補
TODO：參考nienzu評論：這裡打出來的參考資料在這篇 Reddit 的文章中的留言有人提到 Setun is a victim of complicated politics… ，然後在這篇俄文的文章提到當時發展 Setun 的歷史背景(感謝 google 翻譯)，另外則是俄羅斯的電腦博物館的文獻，兩者對於理解當時的情況很有幫助 Development of ternary computers at Moscow State University，最後Ternary Computers: The Setun and the Setun 70這篇整理的很完整

應用：IOTA

IOTA 簡介

IOTA（一種用於物聯網行業的無區塊鍊加密貨幣系統），其中的 IOT 代表 Internet of Things，最後的 A 則有幾個意思：

Applications，物聯網的應用
Apocalyse，物聯網的啟事
Asset，物連往就是財富
字母A，代表最小可能的事情，暗含著 IOTA 的輕量級、零交易費、微交易等特性

過去，比特幣的興起和成功正名了區塊練的價值，但這種技術也有許多缺點，其中之一即是無法進行小額支付，而小額支付在迅速發展的物聯往行業中的重要性不斷增加。在 IOTA_Whitepaper 中提及：

Specifically, in the currently available systems one must pay a fee for making a transaction; so, transferring a very small amount just makes no sense since one would have also to pay the fee which is many times larger.

Balanced Ternary

IOTA 是基於 Balanced Ternary(base 3)而非 Binary(base 2)。可在 iota.lib.py/iota/types.py 找到其以 python 實作 trits 和 int 相互轉換的程式碼：







































def trits_from_int(n, pad=None):
  # type: (int, Optional[int]) -> List[int]
  """
  Returns a trit representation of an integer value.
  :param n:
    Integer value to convert.
  :param pad:
    Ensure the result has at least this many trits.
  References:
    - https://dev.to/buntine/the-balanced-ternary-machines-of-soviet-russia
    - https://en.wikipedia.org/wiki/Balanced_ternary
    - https://rosettacode.org/wiki/Balanced_ternary#Python
  """
  if n == 0:
    trits = []
  else:
    quotient, remainder = divmod(n, 3)

    if remainder == 2:
      # Lend 1 to the next place so we can make this trit negative.
      quotient  += 1
      remainder = -1

    trits = [remainder] + trits_from_int(quotient)

  if pad:
    trits += [0] * max(0, pad - len(trits))

  return trits


def int_from_trits(trits):
  # type: (Iterable[int]) -> int
  """
  Converts a sequence of trits into an integer value.
  """
  # Normally we'd have to wrap ``enumerate`` inside ``reversed``, but
  # balanced ternary puts least significant digits first.
  return sum(base * (3 ** power) for power, base in enumerate(trits))

在 IRI（IOTA Reference Implementation）中，則可在 Converter.java 中找到 trits 和 trytes 的設定。
此外，IOTA 亦使用 Ternary JINN-Processors
JINN
IOTA 的創辦人之一 David Sønstebø：

JINN is a custom made Polymorphic Processing Unit which utilizes asynchronous circuits and trinary logic gates, a component of this is the ‘Curl Hasher’ (essentially a tiny ASIC), this ‘Curl Hasher’ component will be made open source so that any chip manufacturer can add it to their chips trivially. We’re talking a completely negligible amount of logic gates here, so zero extra cost, size trade off or implementation issues

But Why Ternary?

在 The Balanced Ternary Machines of Soviet Russia 提及，因 Balanced Ternary 有正有負，因此不用額外的位元即可直接表達負數。也因此在做減法時，只需將減數正負反轉並將被減數及減數相加即可，可提升空間使用率（觀察上方所列程式碼的第 10 行注釋可知，IOTA 團隊亦是參考這篇文章）。
另外，在 THE TECH BEHIND IOTA EXPLAINED 中提及另一個選擇 Balanced Ternary的原因：

These 3 states perform transaction very balanced, which is quite helpful to build a self-organizing and self-sustaining network like the tangle.

參考資料：
- The Balanced Ternary Machines of Soviet Russia
- THE TECH BEHIND IOTA EXPLAINED

IOTA 架構

IOTA 的中心架構為 DAG（Directed Acyclic Grapgh），稱之為 Tangle。其一個新的交易產生，必須有以下步驟：

選擇兩個交易驗證（這兩比交易可能會一樣）
檢查這兩筆交易有無衝突，且有無驗證到衝突的交易
要讓一筆交易合法（valid），發起交易者必須解出一道加密的問題（耗費計算力），與比特幣挖礦相似

it needs to find a nonce such that the hash of that nonce together with some data from the approved transactions has a particular form, for instance, has at least some fixed number of zeros in front.

根據 IOTA open source code 的 git commit，在 IOTA Python API Library 中，nonce 是在 2017/9/25 新增的 type，宣告在 iota.lib.py/iota/transaction/types.py 中：





















class Nonce(TryteString):
  """
  A TryteString that acts as a transaction nonce.
  """
  LEN = 27

  def __init__(self, trytes):
    # type: (TrytesCompatible) -> None
    super(Nonce, self).__init__(trytes, pad=self.LEN)

    if len(self._trytes) > self.LEN:
      raise with_context(
        exc = ValueError('{cls} values must be {len} trytes long.'.format(
          cls = type(self).__name__,
          len = self.LEN
        )),

        context = {
          'trytes': trytes,
        },
      )

在 iota.lib.py/iota/transaction/base.py 的 class Transaction 中即包含 nonce（下方程式碼的第 43 行、第48~51行處）：



















































class Transaction(JsonSerializable):
  """
  A transaction that has been attached to the Tangle.
  """
  @classmethod
  def from_tryte_string(cls, trytes, hash_=None):
    # type: (TrytesCompatible, Optional[TransactionHash]) -> Transaction
    """
    Creates a Transaction object from a sequence of trytes.
    :param trytes:
      Raw trytes.  Should be exactly 2673 trytes long.
    :param hash_:
      The transaction hash, if available.
      If not provided, it will be computed from the transaction trytes.
    """
    tryte_string = TransactionTrytes(trytes)

    if not hash_:
      hash_trits = [0] * HASH_LENGTH # type: MutableSequence[int]

      sponge = Curl()
      sponge.absorb(tryte_string.as_trits())
      sponge.squeeze(hash_trits)

      hash_ = TransactionHash.from_trits(hash_trits)

    return cls(
      hash_ = hash_,
      signature_message_fragment = Fragment(tryte_string[0:2187]),
      address = Address(tryte_string[2187:2268]),
      value = int_from_trits(tryte_string[2268:2295].as_trits()),
      legacy_tag = Tag(tryte_string[2295:2322]),
      timestamp = int_from_trits(tryte_string[2322:2331].as_trits()),
      current_index = int_from_trits(tryte_string[2331:2340].as_trits()),
      last_index = int_from_trits(tryte_string[2340:2349].as_trits()),
      bundle_hash = BundleHash(tryte_string[2349:2430]),
      trunk_transaction_hash = TransactionHash(tryte_string[2430:2511]),
      branch_transaction_hash = TransactionHash(tryte_string[2511:2592]),
      tag = Tag(tryte_string[2592:2619]),
      attachment_timestamp = int_from_trits(tryte_string[2619:2628].as_trits()),
      attachment_timestamp_lower_bound = int_from_trits(tryte_string[2628:2637].as_trits()),
      attachment_timestamp_upper_bound = int_from_trits(tryte_string[2637:2646].as_trits()),
      nonce = Nonce(tryte_string[2646:2673]),
    )
        
    ...
        
    self.nonce = nonce # type: Optional[Nonce]
    """
    Unique value used to increase security of the transaction hash.
    """

在 iota/iri/hash/ 可看到，IOTA 主要使用的 Hash Function 為 Curl 和 Kerl，是由 IOTA 團隊基於 Keccak 建立新 Hash Function，以下分別介紹之。

Curl

在 The Transparency Compendium，IOTA 團隊如此介紹 Curl：

As IOTA was the first distributed ledger project that took the inevitable threat of scalable quantum computers seriously, we had to move away from standard elliptic curve cryptography. A few months later NSA validated our concerns by announcing official concern over the ‘quantum threat’. Since then there has been numerous quantum leaps in quantum computing, further validating this engineering decision we made. Beyond this concern we also had to follow a path that is optimized for the future landscape of Internet of Things. Curl is a new kind of hash function optimized precisely for these two things, it is based on well-studied sponge construction invented by the Keccak creators (SHA-3) and strictly conforms to all requirements described in their official paper. Though Curl has gone through reviews, it is naturally not as explored as older ones yet. Curl, like the rest of IOTA, is continuously being audited by more and more cryptographers and security experts. IOTA currently uses Keccak (SHA-3) for signing as a security precaution.

目前 IOTA 將 Curl 用於 transaction ID grnrration 和 proof of work 上。同樣在 iota.lib.py/iota/transaction/base.py 中皆可找到（在上方程式碼第 28 行、第 36~38 行及以下）：




























    self.hash = hash_ # type: Optional[TransactionHash]
    """
    Transaction ID, generated by taking a hash of the transaction
    trits.
    """

    self.bundle_hash = bundle_hash # type: Optional[BundleHash]
    """
    Bundle hash, generated by taking a hash of metadata from all the
    transactions in the bundle.
    """

    self.trunk_transaction_hash = trunk_transaction_hash # type: Optional[TransactionHash]
    """
    In order to add a transaction to the Tangle, you must perform PoW
    to "approve" two existing transactions, called the "trunk" and
    "branch" transactions.
    The trunk transaction is generally used to link transactions within
    a bundle.
    """

    self.branch_transaction_hash = branch_transaction_hash # type: Optional[TransactionHash]
    """
    In order to add a transaction to the Tangle, you must perform PoW
    to "approve" two existing transactions, called the "trunk" and
    "branch" transactions.
    The branch transaction generally has no significance.
    """

Curl 原理及實作

在 ccurl/src/lib/curl.c 中可找到以 C 實作 Curl 的程式碼：

在程式開頭先定義 Balanced Ternary 的 True table 和 Hash table

























































#define __TRUTH_TABLE 1, 0, -1, 2, 1, -1, 0, 2, -1, 1, 0

#define __INDEX_TABLE \
    0,   364, 728, 363, 727, 362, 726, 361, 725, 360, 724, 359, 723, 358, 722,\
    357, 721, 356, 720, 355, 719, 354, 718, 353, 717, 352, 716, 351, 715, 350,\
    714, 349, 713, 348, 712, 347, 711, 346, 710, 345, 709, 344, 708, 343, 707,\
    342, 706, 341, 705, 340, 704, 339, 703, 338, 702, 337, 701, 336, 700, 335,\
    699, 334, 698, 333, 697, 332, 696, 331, 695, 330, 694, 329, 693, 328, 692,\
    327, 691, 326, 690, 325, 689, 324, 688, 323, 687, 322, 686, 321, 685, 320,\
    684, 319, 683, 318, 682, 317, 681, 316, 680, 315, 679, 314, 678, 313, 677,\
    312, 676, 311, 675, 310, 674, 309, 673, 308, 672, 307, 671, 306, 670, 305,\
    669, 304, 668, 303, 667, 302, 666, 301, 665, 300, 664, 299, 663, 298, 662,\
    297, 661, 296, 660, 295, 659, 294, 658, 293, 657, 292, 656, 291, 655, 290,\
    654, 289, 653, 288, 652, 287, 651, 286, 650, 285, 649, 284, 648, 283, 647,\
    282, 646, 281, 645, 280, 644, 279, 643, 278, 642, 277, 641, 276, 640, 275,\
    639, 274, 638, 273, 637, 272, 636, 271, 635, 270, 634, 269, 633, 268, 632,\
    267, 631, 266, 630, 265, 629, 264, 628, 263, 627, 262, 626, 261, 625, 260,\
    624, 259, 623, 258, 622, 257, 621, 256, 620, 255, 619, 254, 618, 253, 617,\
    252, 616, 251, 615, 250, 614, 249, 613, 248, 612, 247, 611, 246, 610, 245,\
    609, 244, 608, 243, 607, 242, 606, 241, 605, 240, 604, 239, 603, 238, 602,\
    237, 601, 236, 600, 235, 599, 234, 598, 233, 597, 232, 596, 231, 595, 230,\
    594, 229, 593, 228, 592, 227, 591, 226, 590, 225, 589, 224, 588, 223, 587,\
    222, 586, 221, 585, 220, 584, 219, 583, 218, 582, 217, 581, 216, 580, 215,\
    579, 214, 578, 213, 577, 212, 576, 211, 575, 210, 574, 209, 573, 208, 572,\
    207, 571, 206, 570, 205, 569, 204, 568, 203, 567, 202, 566, 201, 565, 200,\
    564, 199, 563, 198, 562, 197, 561, 196, 560, 195, 559, 194, 558, 193, 557,\
    192, 556, 191, 555, 190, 554, 189, 553, 188, 552, 187, 551, 186, 550, 185,\
    549, 184, 548, 183, 547, 182, 546, 181, 545, 180, 544, 179, 543, 178, 542,\
    177, 541, 176, 540, 175, 539, 174, 538, 173, 537, 172, 536, 171, 535, 170,\
    534, 169, 533, 168, 532, 167, 531, 166, 530, 165, 529, 164, 528, 163, 527,\
    162, 526, 161, 525, 160, 524, 159, 523, 158, 522, 157, 521, 156, 520, 155,\
    519, 154, 518, 153, 517, 152, 516, 151, 515, 150, 514, 149, 513, 148, 512,\
    147, 511, 146, 510, 145, 509, 144, 508, 143, 507, 142, 506, 141, 505, 140,\
    504, 139, 503, 138, 502, 137, 501, 136, 500, 135, 499, 134, 498, 133, 497,\
    132, 496, 131, 495, 130, 494, 129, 493, 128, 492, 127, 491, 126, 490, 125,\
    489, 124, 488, 123, 487, 122, 486, 121, 485, 120, 484, 119, 483, 118, 482,\
    117, 481, 116, 480, 115, 479, 114, 478, 113, 477, 112, 476, 111, 475, 110,\
    474, 109, 473, 108, 472, 107, 471, 106, 470, 105, 469, 104, 468, 103, 467,\
    102, 466, 101, 465, 100, 464, 99,  463, 98,  462, 97,  461, 96,  460, 95,\
    459, 94,  458, 93,  457, 92,  456, 91,  455, 90,  454, 89,  453, 88,  452,\
    87,  451, 86,  450, 85,  449, 84,  448, 83,  447, 82,  446, 81,  445, 80,\
    444, 79,  443, 78,  442, 77,  441, 76,  440, 75,  439, 74,  438, 73,  437,\
    72,  436, 71,  435, 70,  434, 69,  433, 68,  432, 67,  431, 66,  430, 65,\
    429, 64,  428, 63,  427, 62,  426, 61,  425, 60,  424, 59,  423, 58,  422,\
    57,  421, 56,  420, 55,  419, 54,  418, 53,  417, 52,  416, 51,  415, 50,\
    414, 49,  413, 48,  412, 47,  411, 46,  410, 45,  409, 44,  408, 43,  407,\
    42,  406, 41,  405, 40,  404, 39,  403, 38,  402, 37,  401, 36,  400, 35,\
    399, 34,  398, 33,  397, 32,  396, 31,  395, 30,  394, 29,  393, 28,  392,\
    27,  391, 26,  390, 25,  389, 24,  388, 23,  387, 22,  386, 21,  385, 20,\
    384, 19,  383, 18,  382, 17,  381, 16,  380, 15,  379, 14,  378, 13,  377,\
    12,  376, 11,  375, 10,  374, 9,   373, 8,   372, 7,   371, 6,   370, 5,\
    369, 4,   368, 3,   367, 2,   366, 1,   365, 0


static const size_t TRUTH_TABLE[11] = {__TRUTH_TABLE};
static const size_t INDEX[STATE_LENGTH+1] = {__INDEX_TABLE};

Curl 如上所述，是基於 Sponge function ，故與結構與其相似，主要分為兩部份：absorb（吸收）和squeeze（擠出）
absorb 的程式碼如下：























void transform(curl_t* ctx);

void absorb(curl_t* ctx, char* const trits, int length) {
  int offset = 0;
  do {
    memcpy(ctx->state, trits + offset,
           (length < HASH_LENGTH ? length : HASH_LENGTH) * sizeof(char));
    transform(ctx);
    offset += HASH_LENGTH;
  } while ((length -= HASH_LENGTH) > 0);
}

void transform(curl_t* ctx) {
  int round, stateIndex;
  char scratchpad[STATE_LENGTH];
  for (round = 0; round < NUMBER_OF_ROUNDS; round++) {
    memcpy(scratchpad, ctx->state, STATE_LENGTH * sizeof(char));
    for (stateIndex = 0; stateIndex < STATE_LENGTH; stateIndex++) {
      ctx->state[stateIndex] = TRUTH_TABLE[scratchpad[INDEX[stateIndex]] +
                                           (scratchpad[INDEX[stateIndex+1]]<<2) +5 ];
    }
  }
}

一開始先將 offset 設為 0 後，將輸入(trits)和 offset 相加並複製前段一定長度到 type 為 curl_t 的 ctx 中（其中 curl_t 的定義可在 ccurl/src/lib/curl.h 中找到）。
而後將 ctx 傳入填充函式（即transform）進行 Hash 處理。若填充後輸入還有剩餘，則進行下一區段的填充，直到所有輸入都用完為止（在海棉的譬喻裡面，被函式「吸收」了）。

而 squeeze 的程式碼如下：









void squeeze(curl_t* ctx, char* trits, int length) {
  int offset = 0;
  do {
    memcpy(&(trits[offset]), ctx->state,
           (length < HASH_LENGTH ? length : HASH_LENGTH) * sizeof(char));
    transform(ctx);
    offset += HASH_LENGTH;
  } while ((length -= HASH_LENGTH) > 0);
}

先將 ctx 前一定長度的位元複製到 trits 中，並一樣將 ctx 傳到 transform 中進行 Hash 轉換，此時 trits 會隨著 ctx 一起進行轉換，重複此步驟直到滿足輸出所需要的長度為止（「擠出」內容）。

可在 iota.lib.py/iota/crypto/pycurl.py 及 iota.crypto.js/lib/crypto/curl/curl.js 中分別找到以 python 和 js 的程式碼（在此不詳述），但其實作方式與 C 不大相同，程式開發者在 python 檔案中的解釋是：

This code looks significantly different from the C implementation because it has been optimized to limit the number of list item lookups (these are relatively slow in Python).

Kerl

事實上，在 2017 年 8 月前，IOTA 亦將 Curl 使用在 Signature message hashing 中，但在 2017 年 7 月 14 日，有一團隊告知 IOTA 已找出有效的攻擊方式。

該團隊成員有： Ethan Heilman (Boston University, Paragon Foundation, Commonwealth Crypto), Neha Narula (MIT Media Lab), Thaddeus Dryja (MIT Media Lab, Lightning Network Dev), Madars Virza (MIT Media Lab, Zcash)

他們宣稱：

We have developed practical attacks on IOTA’s cryptographic hash function Curl, allowing us to quickly generate short colliding messages. These collisions work even for messages of the same length. Exploiting these weaknesses in Curl, we break the EU-CMA security of the IOTA signature scheme. Finally we show that in a chosen message setting we can forge signatures of valid spending transactions (called bundles in IOTA).

而後兩方經過約半個月的討論，IOTA 在 2017 年 8 月 8 日將此部份的 Hash function 改為另一個由他們創立的，稱為 Kerl 的 Hash function（詳細改動部份可參考Merged Kerl Implementation 這份 git commit），並在官方網站發表 Upgrades & Updates 的聲明。在 2017 年 9 月 8 日的Curl disclosure, beyond the headline 中亦有提及此事：

As part of an on-going conversation between the IOTA Team and security researchers from Boston University and MIT DCI, the teams published their report on a vulnerability in Curl today. On August 8th, the IOTA Team implemented a safety precaution by switching Curl with Keccak-384 (wrapped as “Kerl”, as a tongue-in-cheek homage to what it was replacing).

文中所提及的 report 在此：IOTA Vulnerability Report: Cryptanalysis of the Curl Hash Function Enabling Practical Signature Forgery Attacks on the IOTA Cryptocurrency
其中有說明雙方討論的時間線，以及該團隊是以何種方式攻擊，並在 IOTA 完成 Upgrades & Updates 後在 github 釋出原始碼（在此不詳述）。

IOTA 並在 2017 年 8 月 22 日及 23 日將 iota.lib.py 中的部份 Hash 改 Curl 成 Kerl，更改部份可參考 Key/Addy gen now uses kerl. 及 s/Curl/Kerl/g 這兩份 git commit。
從這兩份 git commit 中可以看出，Kerl 主要是實作在 address 及 signing 的部份（~~以及，IOTA 的工程師之一 todofixthis 似乎沒有遵守 How to Write a Git Commit Message 關於 git commit 的第四點建議，時常在 commit 的標題句末加了句號…->證據~~）
在 iotaledger/kerl 中有以多種程式語言實作 Kerl 的程式碼。因為都是基於 Sponge function，故 Kerl 亦主要是由 absorb 和 squeeze 兩種 function 組成，但在 function 內部 Kerl 稍較複雜，以下列出以 python 3 實作的 absort 和 squeeze：



















































    def absorb(self, trits, offset=0, length=None):
        if length == None:
            length = len(trits)

        if length % 243 != 0:
            raise Exception("Illegal length") 

        while offset < length:
            stop = min(offset + TRIT_HASH_LENGTH, length)

            # If we're copying over a full chunk, zero last trit
            if stop - offset == TRIT_HASH_LENGTH:
                trits[stop - 1] = 0

            signed_nums = conv.convertToBytes(trits[offset:stop])

            # Convert signed bytes into their equivalent unsigned representation
            # In order to use Python's built-in bytes type
            unsigned_bytes = bytes([conv.convert_sign(b) for b in signed_nums])

            self.k.update(unsigned_bytes)

            offset += TRIT_HASH_LENGTH

    def squeeze(self, trits, offset=0, length=None):
        if length == None:
            length = TRIT_HASH_LENGTH

        if length % 243 != 0:
            raise Exception("Illegal length") 

        while offset < length:
            unsigned_hash = self.k.digest()

            signed_hash = [conv.convert_sign(b) for b in unsigned_hash]

            trits_from_hash = conv.convertToTrits(signed_hash)
            trits_from_hash[TRIT_HASH_LENGTH - 1] = 0

            stop = TRIT_HASH_LENGTH
            if length < TRIT_HASH_LENGTH:
                stop = length
            trits[offset:stop] = trits_from_hash[0:stop]

            flipped_bytes = bytes([conv.convert_sign(~b) for b in unsigned_hash])

            # Reset internal state before feeding back in
            self.__init__()
            self.k.update(flipped_bytes)

            offset += TRIT_HASH_LENGTH

IRI

在 IRI（IOTA Reference Implementation）中，則是先宣告 interface Sponge 在 Sponge.java 中





public interface Sponge {
    void absorb(final int[] trits, int offset, int length);
    void squeeze(final int[] trits, int offset, int length);
    void reset();
}

Curl 和 Kerl 再分別繼承它，並 override absorb, squeeze 和 reset。
其原理與上述相似，故此處便不再墜述。

Curl.java












































































public class Curl implements Sponge {

    public static final int HASH_LENGTH = 243;
    public static final int NUMBER_OF_ROUNDSP81 = 81;
    public static final int NUMBER_OF_ROUNDSP27 = 27;
    private final int numberOfRounds;
    private static final int STATE_LENGTH = 3 * HASH_LENGTH;
    private static final int HALF_LENGTH = 364;

    private static final int[] TRUTH_TABLE = {1, 0, -1, 2, 1, -1, 0, 2, -1, 1, 0};

    private final int[] state;
    private final long[] stateLow;
    private final long[] stateHigh;

    private final int[] scratchpad = new int[STATE_LENGTH];


    protected Curl(SpongeFactory.Mode mode) {
        switch(mode) {
            case CURLP27: {
                numberOfRounds = NUMBER_OF_ROUNDSP27;
            } break;
            case CURLP81: {
                numberOfRounds = NUMBER_OF_ROUNDSP81;
            } break;
            default: throw new NoSuchElementException("Only Curl-P-27 and Curl-P-81 are supported.");
        }
        state = new int[STATE_LENGTH];
        stateHigh = null;
        stateLow = null;
    }

    public void absorb(final int[] trits, int offset, int length) {

        do {
            System.arraycopy(trits, offset, state, 0, length < HASH_LENGTH ? length : HASH_LENGTH);
            transform();
            offset += HASH_LENGTH;
        } while ((length -= HASH_LENGTH) > 0);
    }


    public void squeeze(final int[] trits, int offset, int length) {

        do {
            System.arraycopy(state, 0, trits, offset, length < HASH_LENGTH ? length : HASH_LENGTH);
            transform();
            offset += HASH_LENGTH;
        } while ((length -= HASH_LENGTH) > 0);
    }

    private void transform() {

        //final int[] scratchpad = new int[STATE_LENGTH];
        int scratchpadIndex = 0;
        int prev_scratchpadIndex = 0;
        for (int round = 0; round < numberOfRounds; round++) {
            System.arraycopy(state, 0, scratchpad, 0, STATE_LENGTH);
            for (int stateIndex = 0; stateIndex < STATE_LENGTH; stateIndex++) {
                prev_scratchpadIndex = scratchpadIndex;
                if (scratchpadIndex < 365) {
                    scratchpadIndex += 364;
                } else {
                    scratchpadIndex += -365;
                }
                state[stateIndex] = TRUTH_TABLE[scratchpad[prev_scratchpadIndex] + (scratchpad[scratchpadIndex] << 2) + 5];
            }
        }
    }
    public void reset() {
        Arrays.fill(state, 0);
    }
    
    ...
}

Kerl.java








































































public class Kerl implements Sponge {

    public static final int HASH_LENGTH = 243;
    public static final int BIT_HASH_LENGTH = 384;
    public static final int BYTE_HASH_LENGTH = BIT_HASH_LENGTH / 8;

    private byte[] byte_state;
    private int[] trit_state;
    private final Keccak.Digest384 keccak;

    protected Kerl() {

        this.keccak = new Keccak.Digest384();
        this.byte_state = new byte[BYTE_HASH_LENGTH];
        this.trit_state = new int[HASH_LENGTH];
    }

    @Override
    public void reset() {

        this.keccak.reset();
    }

    @Override
    public void absorb(final int[] trits, int offset, int length) {

        if (length % 243 != 0) throw new RuntimeException("Illegal length: " + length);

        do {

            //copy trits[offset:offset+length]
            System.arraycopy(trits, offset, trit_state, 0, HASH_LENGTH);

            //convert to bits
            trit_state[HASH_LENGTH - 1] = 0;
            byte[] bytes = bytesFromBigInt(bigIntFromTrits(trit_state, 0, HASH_LENGTH), BYTE_HASH_LENGTH);

            //run keccak
            keccak.update(bytes);
            offset += HASH_LENGTH;

        } while ((length -= HASH_LENGTH) > 0);
    }

    @Override
    public void squeeze(final int[] trits, int offset, int length) {

        if (length % 243 != 0) throw new RuntimeException("Illegal length: " + length);

        do {

            byte_state = this.keccak.digest();
            //convert to trits
            trit_state = tritsFromBigInt(bigIntFromBytes(byte_state,0,BYTE_HASH_LENGTH), HASH_LENGTH);

            //copy with offset
            trit_state[HASH_LENGTH - 1] = 0;
            System.arraycopy(trit_state, 0, trits, offset, HASH_LENGTH);

            //calculate hash again
            for (int i = byte_state.length; i-- > 0; ) {

                byte_state[i] = (byte) (byte_state[i] ^ 0xFF);
            }
            keccak.update(byte_state);
            offset += HASH_LENGTH;

        } while ((length -= HASH_LENGTH) > 0);
    }
    
    ...
}

2017q3 Homework1 (ternary)

目錄

摘要簡介：Balanced Ternary

原理

Radix Economy

參考資料：

十進位、二進位、三進位比較

加減運算

bal3 to dec ( 數字系統轉換 )

dec to bal3 ( 數字系統轉換 )

參考資料

Half Adder(電路實作)

Full Adder(電路實作)

參考資料

歷史

應用：IOTA

IOTA 簡介

Balanced Ternary

But Why Ternary?

IOTA 架構

Curl

Curl 原理及實作

Kerl

IRI

參考資料