98. Validate Binary Search Tree

98. Validate Binary Search Tree Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees....

October 6, 2023 Â· Yish

(譯) What Is Blockchain Network Congestion? 什麼是區塊鏈網路擁塞?

這篇文章是翻譯自 Binance academy,因為寫得相當清楚且好懂,可以從頭了解大概所謂的網路擁塞是如何發生的。 TL;DR 區塊鏈網路擁塞發生在提交到網路的交易量超過網路的處理量。 交易活動增加、小的區塊大小,以及產塊的時間都會造成網路擁塞。 區塊鏈網路擁塞結果會包含以下幾種狀況:增加交易手續費、緩慢的交易確認,以及糟糕的用戶體驗。 在2023 春天,比特網路由於 BRC-20 代幣交易活動量增加導致待處理交易跟交易手續費飆升。 網路擁塞到底是什麼? 網路擁塞發生在提交到網路的交易量超過網路的處理量。這種現象有幾種影響因素,像是外部因素,包含市場波動、既有網路特定像是區塊大小與產塊時間。 在我們深入細節之前,來看看如何將區塊添加到區塊鏈的過程。 區塊鏈是如何運作的? 區塊鏈由一系列的區塊組成,每個區塊包含使用者創建的交易數據。每當新的區塊被添加到鏈上時,它就是永久且不可改變的。 這些區塊在分散式節點網絡中傳播,每個節點都存儲著區塊鏈的副本。區塊鏈以加密和博弈理論為基礎,是比特幣和以太坊等加密貨幣的支柱。 要完全理解區塊鏈網絡為何會擁塞,我們需要探討幾個關鍵概念,這些概念對於網絡處理交易的能力起著重要作用:記憶池、候選區塊、確定性和最長鏈原則。 什麼是「記憶池」? 一個 mempool 指得是等待被包含到下一個區塊的未確認交易集合。 例如,當一筆交易在比特幣網絡上廣播時,它不會立即被添加到區塊鏈中。相反,它首先進入內存池(簡稱為mempool),這實際上是所有待處理交易的等待區域。一旦交易得到確認,它將從內存池中移除。 「候選區塊」是什麼? 候選區塊,也被稱為「提議區塊」,是礦工或驗證者提議添加到區塊鏈中的區塊。這些區塊包含尚未被納入區塊鏈的未確認交易,這些交易已經被廣播到網絡上。 要使候選區塊成為確認區塊,必須根據區塊鏈的共識機制進行挖礦或驗證。例如,比特幣的工作量證明(PoW)共識機制讓礦工們競爭解決一個複雜的數學問題。第一個解決問題的礦工可以將其候選區塊添加到區塊鏈並獲得獎勵。 在以太坊的權益證明(PoS)共識機制中,驗證者被隨機選擇來提出候選區塊。其他驗證者則對該區塊的有效性進行證明。當一個區塊獲得足夠的證明時,它從候選區塊轉變為確認區塊。 區塊鏈中的 “finality”(最終性) 是什麼? 當一筆交易或操作無法再被改變或撤銷時,我們稱之為「確定性」。一旦交易達到確定性,它將永久地被記錄在區塊鏈上,無法被修改或刪除。 在比特幣區塊鏈中,交易被廣播到網絡並添加到記憶池中。礦工從這個池子中選擇並驗證交易,將它們包含在新的區塊中,以添加到區塊鏈中。該區塊中包含的交易被認為是確認的,但其他礦工仍然有理論上的可能性挖掘出競爭的區塊。 交易的最終性會隨著確認區塊的增加而增加。比特幣交易通常是以額外的六個區塊被附加到交易區塊中而變成"最終"。由於以太坊有比較短的區塊時間,會建議使用較多的確認區塊來確保最終性。 「最長鏈原則」是什麼? 如之前所說,由於多個礦工可能會在相似時間產生新的有效區塊,這個可能會暫時的產生區塊鏈的臨時分叉。 「最長鏈」原則指的是區塊鏈中有效版本的規則,即投入最多計算工作的版本通常是具有最長區塊鏈的版本。因此,較短鏈上的「有效」區塊,通常被稱為孤立或過時區塊,將被丟棄,其交易將返回至記憶池。 以太坊在先前工作量證明(PoW) 時採用了最長鏈原則。在 2022 年升級至權益證明(PoS) 後,網路採用了更新分叉演算發來衡量鏈的"權重",即驗證者抵押以太幣加權驗證者投票總和。 什麼導致區塊鏈網絡擁塞? 區塊鏈網絡擁塞發生在提交到網絡的交易數量超過網絡處理能力的情況下。 區塊鏈網絡可能出現擁擠的原因有幾個: 需求增加 隨著越來越多的人將交易提交到區塊鏈,未確認交易在記憶池中的數量可能超過單個區塊所能包含的範圍。對於具有區塊大小和區塊時間固有限制的區塊鏈來說,這一點尤為重要。 另外交易量增加也可能由於價格突然波動或是大規模採用週期導致。 小區塊大小 每個區塊鏈都有一個區塊大小,它定義了一個區塊的最大尺寸。這個區塊大小限制了一個區塊可以包含多少筆交易。 例如,比特幣最初的設計是將區塊大小限制在 1M 字節。在2017年,比特幣實施了一項名為隔離見證(Segregated Witness)或 SegWit 的升級,以提高交易吞吐量。它將理論上的區塊大小限制增加到約 4M 字節。 如果交易數量超過此限制,將導致網絡擁塞。 產塊時間 產塊時間是指新區塊被添加到區塊鏈的頻率。比特幣大約每10分鐘添加一個新區塊。如果交易的創建速度和量遠高於此,將會出現交易積壓。 網絡擁塞的後果是什麼? 區塊鏈網絡擁塞可能導致多種負面後果,阻礙網絡順利運作。 交易手續費增加 礦工被激勵優先處理支付較高手續費的交易。因此,當區塊鏈網絡擁擠時,用戶通常需要支付較高的交易手續費,以激勵礦工優先處理他們的交易。這可能使使用區塊鏈比平常更加昂貴,尤其是對於較小的交易。 延遲的交易確認時間 網絡擁塞可能導致交易確認和最終確定的等待時間變長。在極端情況下,交易可能需要數小時、數天甚至更長時間才能確認。這可能會讓用戶體驗不佳。 用戶體驗不佳 高昂的手續費和緩慢的交易確認時間會導致極差的用戶體驗,進而影響區塊鏈的骰用率和可用性。 市場波動 擁塞可能會加劇不確定性並導致市場波動。如果有很多使用者試圖出售加密貨幣,但網絡過於擁塞以至於無法處理這些交易,使用者可能會恐慌並試圖迅速出脫他們的持有。...

August 25, 2023 Â· Yish

MYSQL 101

在網上找到一個不錯的 MYSQL 教學,把整個主要功能做了一次紮實的盤整,以下是我做的一些筆記跟內容: 教程 代碼 Repo 定義 DDL: 数据定义语言(Data Definition Language) DDL 用于定义数据库结构和模式,包括创建、修改和删除数据库、表、视图、索引等数据库对象。它不涉及实际数据的操作,而是定义了数据的结构。在MySQL中,常见的DDL命令包括CREATE、ALTER和DROP等。 DML: 数据操作语言(Data Manipulation Language) DML用于操作数据库中的数据,包括插入、更新和删除数据记录。它允许用户查询和修改数据库中的实际数据。在MySQL中,常见的DML命令包括SELECT、INSERT、UPDATE和DELETE等。 DQL: 数据查询语言(Data Query Language) DQL用于查询数据库中的数据,但不对数据进行修改。它主要包括SELECT命令,允许用户从数据库中检索所需的数据。在MySQL中,SELECT命令是最常用的DQL命令。 DCL: 数据控制语言(Data Control Language) DCL用于授权和权限管理,确定哪些用户有权访问数据库中的数据和对象,以及在何种方式访问。在MySQL中,常见的DCL命令包括GRANT和REVOKE,用于授予和撤销用户对数据库对象的权限。 基礎操作 # create table create table player ( id INT, name VARCHAR(100), level INT, exp INT, gold DECIMAL(10, 2) ) # 描述 table DESC player # 基本操作 alter table player modify column name VARCHAR(200) alter table player rename column name to nick_name alter table player add COLUMN last_login datetime alter table player drop column last_login insert into player (id, nick_name) values (2, 'hello'); insert into player (id, nick_name) values (3, 'hello'); insert into player (id, nick_name) values (5, 'hello'), (6, 'aaa'); update player set level = 1 WHERE nick_name = 'hello' SELECT * FROM player where level > 1 AND (level < 5 OR exp > 1) and exp < 5 SELECT * FROM player where level in (1, 3, 5) SELECT * FROM player where level BETWEEN 1 AND 10 SELECT * FROM player where name LIKE '王%' SELECT * FROM player where name LIKE '王_' #批配一字符 Regexp #REGEXP # ....

August 23, 2023 Â· Yish

貧血模型跟充血模型

軟體的「貧血模型」(Anemic Domain Model)和「充血模型」(Rich Domain Model)是兩種在軟體設計中常見的模型設計風格,特別是在使用面向對象編程(Object-Oriented Programming,簡稱OOP)時,這兩種模型風格對於如何處理領域邏輯(Domain Logic)有著不同的理念。 DDD 本身就是著名的充血模型實作,而分散式拆分則是為貧血模型,以下將會細節說明。 貧血模型(Anemic Domain Model): 在貧血模型中,對象(Object)通常只是包含資料的純資料結構,並且缺乏有效的行為(方法)。這種模型將領域邏輯(Domain Logic)主要放在服務(Service)或管理類別中,而不是在對象本身。這意味著對象只是資料的容器,而所有處理邏輯都放在外部。 貧血模型的優點是簡單且易於理解,因為領域邏輯都放在一個中央位置,容易進行修改和維護。然而,它也有一些缺點。例如,當領域邏輯變得複雜時,服務類別可能會變得過度龐大,造成程式碼不易維護和測試。此外,貧血模型也未完全利用面向對象編程的優點,如封裝和多型性。 充血模型(Rich Domain Model): 相比之下,充血模型是一種較為嚴格的面向對象設計風格,將領域邏輯嵌入到對象中。這意味著對象不僅包含資料,還包含了處理資料的相關行為和邏輯。這使得對象能夠自主管理自己的狀態和行為,更符合真實世界中物件的行為。 充血模型的優點是更好地利用了面向對象編程的特性,更容易理解,也更符合物件導向的設計原則,如封裝和單一職責原則。此外,由於領域邏輯分散在不同的對象中,這使得程式碼更容易擴展和維護。 然而,充血模型可能在某些情況下增加了複雜性。當領域邏輯變得非常複雜時,對象之間的交互可能變得複雜,需要更深入的設計和理解。 在選擇使用貧血模型還是充血模型時,開發者需要考慮項目的需求、複雜性和可擴展性等因素,以及團隊成員對於這兩種設計風格的熟悉程度。 當談到「貧血模型」和「充血模型」,這兩種模型風格涉及領域邏輯的處理方式。 貧血模型(Anemic Domain Model)範例: 在貧血模型中,對象只是包含資料的純資料結構,而大部分的領域邏輯則放在服務(Service)類別中。 // User.php (Entity) class User { private $id; private $name; private $email; // Getter and setter methods... } // UserService.php (Service) class UserService { public function sendWelcomeEmail(User $user) { // Send a welcome email to the user... } public function generateUsername(User $user) { // Generate a unique username based on user's name and ID....

August 22, 2023 Â· Yish

初探 Content-Security-Policy (CSP)

問題 原有 a.com/hello 當中嵌入 a.com/world iframe 本身沒問題,後來因為公司政策改變需要調整為 hello.a.com 與 world.a.com 而原有的 a.com/hello 以及 a.com/world 拜訪後會 redirect 到 hello.a.com 與 world.a.com 當中,而在這中間發現 iframe 失效並嘗試進行解決。 依照同源政策規則,調整為 hello.a.com 與 world.a.com 視為不同源,因此需要額外配置。 同源定義 所謂同源是指兩份網頁具備相同協定、埠號 (如果有指定) 以及主機位置,下表提供了一些例子展示那些來源和 http://store.company.com/dir/page.html 屬於同源: URL Outcome Reason http://store.company.com/dir2/other.html 同源 http://store.company.com/dir/inner/another.html 同源 https://store.company.com/secure.html 不同源 協定不同 http://store.company.com:81/dir/etc.html 不同源 埠號不同 http://news.company.com/dir/other.html 不同源 ✅ 主機位置不同 ✅ MDN 說明 出錯點 Refused to display 'https://world.a.com/' in a frame because it set 'X-Frame-Options' to 'sameorigin'. 問題思路與解法 X-Frame-Options MDN 說明...

August 22, 2023 Â· Yish

什麼是 RWA(Real World Assets)?

概念 RWA 是將實際世界中的實物資產引入區塊鏈,實現資產的數位化、交易和管理的過程。這些實物資產可以是房地產、貴金屬、工業資產等,通過區塊鏈技術,將其轉化為數位資產(通常是代幣)並在區塊鏈上建立對應的記錄。這種數位化的過程具有去中心化、不可篡改、透明等特點,有望提升資產流動性和交易效率。 流程 資產數位化:將實體資產進行數位化(tokenization),通常是通過發行代幣來代表實物資產的所有權。這些數位代幣會在區塊鏈上建立相應的記錄,確保數位資產的真實性。 驗證和授權:透過區塊鏈節點的驗證機制,確保資產的合法性和真實性。此外,可以實現特定的授權機制,只有經過授權的用戶才能進行某些操作,這可以通過智能合約實現。 交易:持有這些數位資產的人可以在區塊鏈上進行交易,交易記錄將被永久記錄在區塊鏈上,確保交易的透明性和可追溯性。 實時追蹤:區塊鏈上的資產數位化和交易記錄可以被實時追蹤,確保資產的歷史和流通記錄可以被準確追溯。 實際例子 房地產 藝術品 股票 債券 轉化為數位代幣,並在區塊鏈上進行交易。這可以使其更加流動,並降低交易成本。 目前 RWA 最佳化實例 USDT: 美元映射到鏈上代幣化 (Tether) USDC: 美元映射到鏈上代幣化 (Circle) PAXG: 黃金映射到鏈上代幣化 (Paxos) 好處 可以將數位代幣資產分割成非常小部分方便散戶與小資金進駐機構從中獲得收益與利潤,或是作為抵押或借貸透過其他用戶或機構所提供的流動性獎勵賺取利潤。 理想可以去各大認可機構隨時換回法幣或實際資產操作。 交易透明化,由於鏈上特性所有交易將會暴露不存在任何中間商手續費。 困境 需要由大型機構發起並且與真實世界資產作掛鈎與保證,一旦脫鉤蹦盤會有毀滅性的打擊。 風險極高,由於大型機構本身建立在中心化認可,一旦中心化機構現實有擠兌現象或是狀況連帶影響。 RWA 並不是新概念,只是最近又被拿出來講,是因為 Defi 項目收益率下降,而美債等低風險資產利率上升,沒道理冒著高風險僅享受 APY 5~10%。 RWA 目前發起大機構目的是希望透過 web3 這項技術來做融資割韭菜給空氣代幣,實際上能不能換回實際資產還是未知。 如果可以換回資產則是代幣證券化,則會經過各種審核,最終冒著高風險收益卻非常少。 結論 RWA 並不是一個新概念,只是透過另外一種方式在找東西與代幣做掛鉤,其次發起的機構背景需要是中心化金融機構才可以,現實資產並須與代幣做匹配。 ref: https://youtu.be/HExvz9d1JR8 https://research.binance.com/en/analysis/real-world-assets

August 11, 2023 Â· Yish