2017年12月9日 星期六

DAG - 有向無環圖 - Directed Acyclic Graph

最近想要研究一下 IOTA 在幹嘛,看到有中文翻譯白皮書 :https://hackmd.io/c/rkpoORY4W/https%3A%2F%2Fhackmd.io%2Fs%2FryriSgvAW

裡面提到 DAG 有向無環圖 - Directed Acyclic Graph

先看一下定義:

在圖論中,如果一個有向圖從任意頂點出發無法經過若干條邊回到該點,則這個圖是一個有向無環圖(DAG圖)。

https://zh.wikipedia.org/wiki/%E6%9C%89%E5%90%91%E6%97%A0%E7%8E%AF%E5%9B%BE

就是出去後就沒辦法繞回來的意思,這張圖很明顯:





常見的「拓墣排序」好像就跟這個有關,有人提到 ETH 好像也有用到這個概念

拓扑排序,我们可以从寻找图中节点之间的路线,最短,以及最长的路线。通过动态规划,无论这张网多么庞大,都能以较快速度将结果正确计算出来。

比如闪电网络,ETH智能合约,为了找到正确的交易线路,使用DAG,拓扑来寻找路线


關於拓撲排序:

https://songlee24.github.io/2015/05/07/topological-sorting/


2017年12月7日 星期四

網路安全相關 - JWT

JSON Web Token

https://jwt.io/

現在很流行用 JWT 當作 HTTP basic auth 的 token

通常會長這樣

```
header["Authorization"] = "Bearer <YOUR_JWT>"
```

什麼是 HTTP basic auth? 參考 這篇文章


為什麼呢? 要先簡單介紹 JWT 才能回答這個問題


JWT 其實就是一個協定告訴你怎麼產生 token

要產生 JWT 的 token 必須包含三個部分

1. header
2. payload
3. signature

header 裡面描述了想要加密用的演算法,用來產生 signature
payload 就是一些想要讓 client 可以解析的數據
signature 就是把 header 和 payload 用 server side 才知道的 secret key 加密產生出的一串字串,用來驗證資料正確性。  可以參考 摘要算法和對稱加密算法


把 header+payload+signature 分別用 Bas64 encode 之後就變成了 JWT token

格式長這樣

encoded_header.encoded_payload.encoded_signature

那回到一開始的問題,為什麼要用 JWT 呢?

主要原因就在於這個 token 是自帶資訊的,因為我們把 加密方式、想要傳達的訊息 都存在 token 裡面了,而且還加上了 簽名 用來確保訊息的正確性。

來看看實際面吧,假設我有個前端頁面想要跟 sever 溝通,以前的作法前端跟 server 拿 token 的時候, server 亂數產生一個 uniq 的 token 給前端,之後的每個 request 就帶這個 token 作為驗證的方式

流程一樣,但我們把「server 亂數產生一個 uniq 的 token 給前端」這件事改成「server 產生一個 JWT token 給前端」會發生什麼事(以及應該怎麼做)呢?

首先定義我的 paylaod

```json
{
  user_id: 1,
  name: "Wayne",
  permissions: [
    "read_account", "write_account"
  ]
  expired_at: 1512624558 // unix time,
  token: "my-uniq-token-from-server"
}
```

然後加密成 JWT token,把這個 token 傳給前端

有什麼好處呢?

1. 前端可以用 Base64 decode payload,這樣前端就可以直接從 token 就知道我提供給他的各種資訊,例如此例前端就可以知道這個 token 有哪些權限、什麼時候過期等等
2. Server 在收到帶有這個 token 的 request 的時候,也可以從 payload 直接判斷 token 過期了沒、有沒有操作權限
3. Server 不用擔心 payload 是不是被改動過,因為只要把 payload decode 出來並用依樣的加密方式加密比對 sinature 是否一樣就知道 paylaod 是否正確




















HTTP basic auth

HTTP Basic access authentication

簡單版:

加一個 Authorization 的 Header,


解釋版:



https://zh.wikipedia.org/wiki/HTTP%E5%9F%BA%E6%9C%AC%E8%AE%A4%E8%AF%81

安全性相關 - CSRF

CSRF
跨站請求偽造,也被稱為 one-click attack 或者 session riding,通常縮寫為 CSRF 或者 XSRF

假設 User A 已經登入了 X 站,因為 A 的瀏覽器有存了 X 站相關的登入紀錄,當 A 進入 Y 站時,Y 站可以偷拿 A 的登入紀錄來訪問 X 站,這就是跨站請求偽造

rails 對這個的解法是加上 authenticate token,就是添加校驗 token,加 token 的方式是把 token 存在 session 裡,default 就是瀏覽器的 cookie (加密過的),然後在 form 裡面靠 `csrf_meta_tags` 這個 view helper 解密塞到 form 裡面,那麼後端就可以藉由比對:「塞在 form 裡面的 token 是不是跟 session 裡面解密後的 token 一樣」來驗證


所以說 CSRF:

1. 在同一個 session 內, token 都是一樣的,所以如果被知道了還是可以通過驗證
2. 但其他站很難知道,因為 cookie 是加密的,其他站不知道怎麼解出 cookie 找到 token


這篇文章解釋得滿清楚的:
https://medium.com/rubyinside/a-deep-dive-into-csrf-protection-in-rails-19fa0a42c0ef

那怎麼破解呢?

最先想到的方法是(未證實)

1. 使用者進來我的 Y 站的時候,我拿使用者的資訊送 GET request 訪問有包含 CSRF token 的 form 頁面
2. 想辦法把這個頁面截下來(html dom 之類的)
3. 解析這個頁面的 dom 找到 csrf token
4. 在使用者在 Y 站做其他操作時把剛剛解析到的 csrf token 加上並做跨站請求偽造



補上 wiki 對 CSRF 的解釋:

https://zh.wikipedia.org/wiki/%E8%B7%A8%E7%AB%99%E8%AF%B7%E6%B1%82%E4%BC%AA%E9%80%A0




2017年12月6日 星期三

Bitfinex Margin 懶人做空範例

範例:


做空 IOTA

步驟

1. 2.92 (當時的價格) 買進 100 顆
2. 下一個 stop limit buy 在 3.199 時觸發用 3.22 買進確保最多虧 10% 左右
3. 下一個 limit buy 在 2.62 在賺 10% 時收割

如果是 margin order,則是三倍槓桿,所以 10% 虧損或是利潤 = 10% * 3 = 30% 的真實虧損或是利潤






2017年12月5日 星期二

做空與做多的方式

最簡單的做空做多操作方式與解釋:


## 若認為會跌:做空

現在價格先賣出,然後開低價買進的單
若要停損就再開一個高價買進的單



## 若認為會漲:做多

現在價格買進,然後開高價賣出的單
若要停損就再開一個低價賣出的單




交易所的 Margin 其實就是讓你三倍槓桿操作而已,跟 Exchange 沒什麼兩樣

2017年12月2日 星期六

終於在工作中實際用到了紅黑樹 - 交易所配對引擎

首先了解紅黑樹跟一般的二分查找樹的區別可以看下面連結中的漫畫,清楚明瞭:

https://mp.weixin.qq.com/s/0RKuO0Pk7R09wGzgyA43mw

簡單來講最大的差別在於

二分查找樹有可能會左右極度不平衡,造成查找時效率變慢
而紅黑樹有自平衡系統,可以確保樹的深度是平衡的,缺點是增加或是減少節點時會比較耗資源


最近在開發交易所,研究了 Peatio 的交易所撮合引擎,其中有一段就有用到紅黑樹

確切的 code 在這:https://github.com/peatio/peatio/blob/master/app/models/matching/order_book.rb#L11

所以不禁就想問為什麼這邊要用紅黑樹呢?

原因就是因為在這個演算法中我們是根據 order 的 price 來當排序,假設交易所的 orders 中我們第一個 laoding 進來的 order 是最便宜的或是最貴的,那麼用 binary tree 就會變成左右極不平衡的情況,造成搜尋效率低落,相對的如果用紅黑樹就可以讓整個樹長成左右平衡的大樹,這樣搜尋效率就比較高。

其實 base on 演算法的實作,在 peatio 的演算法中是把 orders 一次 load 進 memory 裡面,所以只有在第一次 loading orders 的時候會花很多資源在紅黑樹自平衡,但一但 loading 完之後大部分的時候都會是在查找 order 而不是新增刪除 order,所以這樣的設計是比較合理的。

查找 order 的部分:https://github.com/peatio/peatio/blob/master/app/models/matching/order_book.rb#L44