📜 [專欄新文章] Uniswap v3 Features Explained in Depth
✍️ 田少谷 Shao
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
Once again the game-changing DEX 🦄 👑
Image source: https://uniswap.org/blog/uniswap-v3/
Outline
0. Intro1. Uniswap & AMM recap2. Ticks 3. Concentrated liquidity4. Range orders: reversible limit orders5. Impacts of v36. Conclusion
0. Intro
The announcement of Uniswap v3 is no doubt one of the most exciting news in the DeFi place recently 🔥🔥🔥
While most have talked about the impact v3 can potentially bring on the market, seldom explain the delicate implementation techniques to realize all those amazing features, such as concentrated liquidity, limit-order-like range orders, etc.
Since I’ve covered Uniswap v1 & v2 (if you happen to know Mandarin, here are v1 & v2), there’s no reason for me to not cover v3 as well ✅
Thus, this article aims to guide readers through Uniswap v3, based on their official whitepaper and examples made on the announcement page. However, one needs not to be an engineer, as not many codes are involved, nor a math major, as the math involved is definitely taught in your high school, to fully understand the following content 😊😊😊
If you really make it through but still don’t get shxt, feedbacks are welcomed! 🙏
There should be another article focusing on the codebase, so stay tuned and let’s get started with some background noise!
1. Uniswap & AMM recap
Before diving in, we have to first recap the uniqueness of Uniswap and compare it to traditional order book exchanges.
Uniswap v1 & v2 are a kind of AMMs (automated market marker) that follow the constant product equation x * y = k, with x & y stand for the amount of two tokens X and Y in a pool and k as a constant.
Comparing to order book exchanges, AMMs, such as the previous versions of Uniswap, offer quite a distinct user experience:
AMMs have pricing functions that offer the price for the two tokens, which make their users always price takers, while users of order book exchanges can be both makers or takers.
Uniswap as well as most AMMs have infinite liquidity¹, while order book exchanges don’t. The liquidity of Uniswap v1 & v2 is provided throughout the price range [0,∞]².
Uniswap as well as most AMMs have price slippage³ and it’s due to the pricing function, while there isn’t always price slippage on order book exchanges as long as an order is fulfilled within one tick.
In an order book, each price (whether in green or red) is a tick. Image source: https://ftx.com/trade/BTC-PERP
¹ though the price gets worse over time; AMM of constant sum such as mStable does not have infinite liquidity
² the range is in fact [-∞,∞], while a price in most cases won’t be negative
³ AMM of constant sum does not have price slippage
2. Tick
The whole innovation of Uniswap v3 starts from ticks.
For those unfamiliar with what is a tick:
Source: https://www.investopedia.com/terms/t/tick.asp
By slicing the price range [0,∞] into numerous granular ticks, trading on v3 is highly similar to trading on order book exchanges, with only three differences:
The price range of each tick is predefined by the system instead of being proposed by users.
Trades that happen within a tick still follows the pricing function of the AMM, while the equation has to be updated once the price crosses the tick.
Orders can be executed with any price within the price range, instead of being fulfilled at the same one price on order book exchanges.
With the tick design, Uniswap v3 possesses most of the merits of both AMM and an order book exchange! 💯💯💯
So, how is the price range of a tick decided?
This question is actually somewhat related to the tick explanation above: the minimum tick size for stocks trading above 1$ is one cent.
The underlying meaning of a tick size traditionally being one cent is that one cent (1% of 1$) is the basis point of price changes between ticks, ex: 1.02 — 1.01 = 0.1.
Uniswap v3 employs a similar idea: compared to the previous/next price, the price change should always be 0.01% = 1 basis point.
However, notice the difference is that in the traditional basis point, the price change is defined with subtraction, while here in Uniswap it’s division.
This is how price ranges of ticks are decided⁴:
Image source: https://uniswap.org/whitepaper-v3.pdf
With the above equation, the tick/price range can be recorded in the index form [i, i+1], instead of some crazy numbers such as 1.0001¹⁰⁰ = 1.0100496621.
As each price is the multiplication of 1.0001 of the previous price, the price change is always 1.0001 — 1 = 0.0001 = 0.01%.
For example, when i=1, p(1) = 1.0001; when i=2, p(2) = 1.00020001.
p(2) / p(1) = 1.00020001 / 1.0001 = 1.0001
See the connection between the traditional basis point 1 cent (=1% of 1$) and Uniswap v3’s basis point 0.01%?
Image source: https://tenor.com/view/coin-master-cool-gif-19748052
But sir, are prices really granular enough? There are many shitcoins with prices less than 0.000001$. Will such prices be covered as well?
Price range: max & min
To know if an extremely small price is covered or not, we have to figure out the max & min price range of v3 by looking into the spec: there is a int24 tick state variable in UniswapV3Pool.sol.
Image source: https://uniswap.org/whitepaper-v3.pdf
The reason for a signed integer int instead of an uint is that negative power represents prices less than 1 but greater than 0.
24 bits can cover the range between 1.0001 ^ (2²³ — 1) and 1.0001 ^ -(2)²³. Even Google cannot calculate such numbers, so allow me to offer smaller values to have a rough idea of the whole price range:
1.0001 ^ (2¹⁸) = 242,214,459,604.341
1.0001 ^ -(2¹⁷) = 0.000002031888943
I think it’s safe to say that with a int24 the range can cover > 99.99% of the prices of all assets in the universe 👌
⁴ For implementation concern, however, a square root is added to both sides of the equation.
How about finding out which tick does a price belong to?
Tick index from price
The answer to this question is rather easy, as we know that p(i) = 1.0001^i, simply takes a log with base 1.0001 on both sides of the equation⁴:
Image source: https://www.codecogs.com/latex/eqneditor.php
Let’s try this out, say we wanna find out the tick index of 1000000.
Image source: https://ncalculators.com/number-conversion/log-logarithm-calculator.htm
Now, 1.0001¹³⁸¹⁶² = 999,998.678087146. Voila!
⁵ This formula is also slightly modified to fit the real implementation usage.
3. Concentrated liquidity
Now that we know how ticks and price ranges are decided, let’s talk about how orders are executed in a tick, what is concentrated liquidity and how it enables v3 to compete with stablecoin-specialized DEXs (decentralized exchange), such as Curve, by improving the capital efficiency.
Concentrated liquidity means LPs (liquidity providers) can provide liquidity to any price range/tick at their wish, which causes the liquidity to be imbalanced in ticks.
As each tick has a different liquidity depth, the corresponding pricing function x * y = k also won’t be the same!
Each tick has its own liquidity depth. Image source: https://uniswap.org/blog/uniswap-v3/
Mmm… examples are always helpful for abstract descriptions 😂
Say the original pricing function is 100(x) * 1000(y) = 100000(k), with the price of X token 1000 / 100 = 10 and we’re now in the price range [9.08, 11.08].
If the liquidity of the price range [11.08, 13.08] is the same as [9.08, 11.08], we don’t have to modify the pricing function if the price goes from 10 to 11.08, which is the boundary between two ticks.
The price of X is 1052.63 / 95 = 11.08 when the equation is 1052.63 * 95 = 100000.
However, if the liquidity of the price range [11.08, 13.08] is two times that of the current range [9.08, 11.08], balances of x and y should be doubled, which makes the equation become 2105.26 * 220 = 400000, which is (1052.63 * 2) * (110 * 2) = (100000 * 2 * 2).
We can observe the following two points from the above example:
Trades always follow the pricing function x * y = k, while once the price crosses the current price range/tick, the liquidity/equation has to be updated.
√(x * y) = √k = L is how we represent the liquidity, as I say the liquidity of x * y = 400000 is two times the liquidity of x * y = 100000, as √(400000 / 100000) = 2.
What’s more, compared to liquidity on v1 & v2 is always spread across [0,∞], liquidity on v3 can be concentrated within certain price ranges and thus results in higher capital efficiency from traders’ swapping fees!
Let’s say if I provide liquidity in the range [1200, 2800], the capital efficiency will then be 4.24x higher than v2 with the range [0,∞] 😮😮😮 There’s a capital efficiency comparison calculator, make sure to try it out!
Image source: https://uniswap.org/blog/uniswap-v3/
It’s worth noticing that the concept of concentrated liquidity was proposed and already implemented by Kyper, prior to Uniswap, which is called Automated Price Reserve in their case.⁵
⁶ Thanks to Yenwen Feng for the information.
4. Range orders: reversible limit orders
As explained in the above section, LPs of v3 can provide liquidity to any price range/tick at their wish. Depending on the current price and the targeted price range, there are three scenarios:
current price < the targeted price range
current price > the targeted price range
current price belongs to the targeted price range
The first two scenarios are called range orders. They have unique characteristics and are essentially fee-earning reversible limit orders, which will be explained later.
The last case is the exact same liquidity providing mechanism as the previous versions: LPs provide liquidity in both tokens of the same value (= amount * price).
There’s also an identical product to the case: grid trading, a very powerful investment tool for a time of consolidation. Dunno what’s grid trading? Check out Binance’s explanation on this, as this topic won’t be covered!
In fact, LPs of Uniswap v1 & v2 are grid trading with a range of [0,∞] and the entry price as the baseline.
Range orders
To understand range orders, we’d have to first revisit how price is discovered on Uniswap with the equation x * y = k, for x & y stand for the amount of two tokens X and Y and k as a constant.
The price of X compared to Y is y / x, which means how many Y one can get for 1 unit of X, and vice versa the price of Y compared to X is x / y.
For the price of X to go up, y has to increase and x decrease.
With this pricing mechanism in mind, it’s example time!
Say an LP plans to place liquidity in the price range [15.625, 17.313], higher than the current price of X 10, when 100(x) * 1000(y) = 100000(k).
The price of X is 1250 / 80 = 15.625 when the equation is 80 * 1250 = 100000.
The price of X is 1315.789 / 76 = 17.313 when the equation is 76 * 1315.789 = 100000.
If now the price of X reaches 15.625, the only way for the price of X to go even higher is to further increase y and decrease x, which means exchanging a certain amount of X for Y.
Thus, to provide liquidity in the range [15.625, 17.313], an LP needs only to prepare 80 — 76 = 4 of X. If the price exceeds 17.313, all 4 X of the LP is swapped into 1315.789 — 1250 = 65.798 Y, and then the LP has nothing more to do with the pool, as his/her liquidity is drained.
What if the price stays in the range? It’s exactly what LPs would love to see, as they can earn swapping fees for all transactions in the range! Also, the balance of X will swing between [76, 80] and the balance of Y between [1250, 1315.789].
This might not be obvious, but the example above shows an interesting insight: if the liquidity of one token is provided, only when the token becomes more valuable will it be exchanged for the less valuable one.
…wut? 🤔
Remember that if 4 X is provided within [15.625, 17.313], only when the price of X goes up from 15.625 to 17.313 is 4 X gradually swapped into Y, the less valuable one!
What if the price of X drops back immediately after reaching 17.313? As X becomes less valuable, others are going to exchange Y for X.
The below image illustrates the scenario of DAI/USDC pair with a price range of [1.001, 1.002] well: the pool is always composed entirely of one token on both sides of the tick, while in the middle 1.001499⁶ is of both tokens.
Image source: https://uniswap.org/blog/uniswap-v3/
Similarly, to provide liquidity in a price range < current price, an LP has to prepare a certain amount of Y for others to exchange Y for X within the range.
To wrap up such an interesting feature, we know that:
Only one token is required for range orders.
Only when the current price is within the range of the range order can LP earn trading fees. This is the main reason why most people believe LPs of v3 have to monitor the price more actively to maximize their income, which also means that LPs of v3 have become arbitrageurs 🤯
I will be discussing more the impacts of v3 in 5. Impacts of v3.
⁷ 1.001499988 = √(1.0001 * 1.0002) is the geometric mean of 1.0001 and 1.0002. The implication is that the geometric mean of two prices is the average execution price within the range of the two prices.
Reversible limit orders
As the example in the last section demonstrates, if there is 4 X in range [15.625, 17.313], the 4 X will be completely converted into 65.798 Y when the price goes over 17.313.
We all know that a price can stay in a wide range such as [10, 11] for quite some time, while it’s unlikely so in a narrow range such as [15.625, 15.626].
Thus, if an LP provides liquidity in [15.625, 15.626], we can expect that once the price of X goes over 15.625 and immediately also 15.626, and does not drop back, all X are then forever converted into Y.
The concept of having a targeted price and the order will be executed after the price is crossed is exactly the concept of limit orders! The only difference is that if the range of a range order is not narrow enough, it’s highly possible that the conversion of tokens will be reverted once the price falls back to the range.
As price ranges follow the equation p(i) = 1.0001 ^ i, the range can be quite narrow and a range order can thus effectively serve as a limit order:
When i = 27490, 1.0001²⁷⁴⁹⁰ = 15.6248.⁸
When i = 27491, 1.0001²⁷⁴⁹¹ = 15.6264.⁸
A range of 0.0016 is not THAT narrow but can certainly satisfy most limit order use cases!
⁸ As mentioned previously in note #4, there is a square root in the equation of the price and index, thus the numbers here are for explantion only.
5. Impacts of v3
Higher capital efficiency, LPs become arbitrageurs… as v3 has made tons of radical changes, I’d like to summarize my personal takes of the impacts of v3:
Higher capital efficiency makes one of the most frequently considered indices in DeFi: TVL, total value locked, becomes less meaningful, as 1$ on Uniswap v3 might have the same effect as 100$ or even 2000$ on v2.
The ease of spot exchanging between spot exchanges used to be a huge advantage of spot markets over derivative markets. As LPs will take up the role of arbitrageurs and arbitraging is more likely to happen on v3 itself other than between DEXs, this gap is narrowed … to what extent? No idea though.
LP strategies and the aggregation of NFT of Uniswap v3 liquidity token are becoming the blue ocean for new DeFi startups: see Visor and Lixir. In fact, this might be the turning point for both DeFi and NFT: the two main reasons of blockchain going mainstream now come to the alignment of interest: solving the $$ problem 😏😏😏
In the right venue, which means a place where transaction fees are low enough, such as Optimism, we might see Algo trading firms coming in to share the market of designing LP strategies on Uniswap v3, as I believe Algo trading is way stronger than on-chain strategies or DAO voting to add liquidity that sort of thing.
After reading this article by Parsec.finance: The Dex to Rule Them All, I cannot help but wonder: maybe there is going to be centralized crypto exchanges adopting v3’s approach. The reason is that since orders of LPs in the same tick are executed pro-rata, the endless front-running speeding-competition issue in the Algo trading world, to some degree, is… solved? 🤔
Anyway, personal opinions can be biased and seriously wrong 🙈 I’m merely throwing out a sprat to catch a whale. Having a different voice? Leave your comment down below!
6. Conclusion
That was kinda tough, isn’t it? Glad you make it through here 🥂🥂🥂
There are actually many more details and also a huge section of Oracle yet to be covered. However, since this article is more about features and targeting normal DeFi users, I’ll leave those to the next one; hope there is one 😅
If you have any doubt or find any mistake, please feel free to reach out to me and I’d try to reply AFAP!
Stay tuned and in the meantime let’s wait and see how Uniswap v3 is again pioneering the innovation of DeFi 🌟
Uniswap v3 Features Explained in Depth was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
同時也有667部Youtube影片,追蹤數超過6萬的網紅Herman Yeung,也在其Youtube影片中提到,HKDSE Mathematics 數學天書 訂購表格及方法︰https://www.sites.google.com/view/HermanYeung 課程簡介︰ https://youtu.be/KKTtzLkpyO8 --------------------------------------...
「logarithm」的推薦目錄:
- 關於logarithm 在 Taipei Ethereum Meetup Facebook 的精選貼文
- 關於logarithm 在 มติพล ตั้งมติธรรม Facebook 的最讚貼文
- 關於logarithm 在 Taipei Ethereum Meetup Facebook 的精選貼文
- 關於logarithm 在 Herman Yeung Youtube 的精選貼文
- 關於logarithm 在 Herman Yeung Youtube 的精選貼文
- 關於logarithm 在 Herman Yeung Youtube 的最佳貼文
- 關於logarithm 在 Logarithms... How? (NancyPi) - YouTube 的評價
- 關於logarithm 在 Logarithms - Basics | What are Logs? | Don't Memorise 的評價
logarithm 在 มติพล ตั้งมติธรรม Facebook 的最讚貼文
คณิตศาสตร์ของ "หวย"
"หวย" น่าจะเรียกได้ว่าเป็น "กิจกรรมประจำชาติ" ของไทยอย่างหนึ่งที่เรามาร่วมกันโอดครวญกันเป็นประจำกับการถูกหวยแ-ก หวยไม่เพียงแต่เป็น national pastime ประจำชาติเพียงเท่านั้น แต่ยังมีอิทธิพลเป็นอย่างมากต่อวัฒนธรรม ศาสนา และความเชื่อของเรา และเนื่องจากนี่เป็นเพจวิทยาศาสตร์จึงไม่สามารถปฏิเสธได้ว่าหวยนั้นมีส่วนที่เหนี่ยวรั้งความพัฒนาสู่ scientific literacy ในประเทศเราไม่มากก็น้อย ดั่งที่เราทุกคนน่าจะคุ้นเคยกันดีกับลูกหมูพิการ ต้นกล้วยงอกกลางต้น รวมไปถึงท่อน้ำทิ้งจากส้วมที่แตกและผุดขึ้นมาบนดิน ที่แทบทุกเหตุการณ์ ทุกอุบัติเหตุ ทุกข่าว ทุกปรากฏการณ์ที่เกิดขึ้นในบ้านเมืองนี้จะถูกตีความไปเป็น "ตัวเลข" เสียทั้งหมด
ในวันนี้เราจะมาลองดู "หวย" จากในแง่มุมของคณิตศาสตร์กันดูบ้าง โดยเฉพาะในเรื่องของรางวัล "เลขท้ายสองตัว"
รางวัลเลขท้ายสองตัวนั้นมีความเป็นไปได้ทั้งหมดอยู่ด้วยกัน 100 แบบ โอกาสที่จะถูก จึงมีเพียงแค่หนึ่งในร้อย (ในขณะที่โอกาสที่จะถูกแดกกลับมีถึง 99%) ทั้งนี้ทั้งนั้น นี่มาจากสมมติฐานว่าหวยทุกเลขนั้นมีโอกาสออกเท่ากันหมด ว่าแต่ว่าสมมติฐานนี้เป็นจริงหรือไม่?
จากกราฟบนในภาพ แสดงถึงการกระจายตัวของหวยเลขท้ายสองตัวตลอด 20 ปีที่ผ่านมา[1] ทั้ง "ตัวบน" และ "ตัวล่าง" รวมกันทั้งสิ้น 477 งวด จากการดูคร่าวๆ เราจะพบว่ารางวัลนั้นมีการกระจายตัวที่ค่อนข้างสม่ำเสมอ ไม่มีตัวเลขใดที่เด่นกว่าอย่างเห็นได้ชัดอาจจะมีบางตัวเลขที่ออกเยอะกว่าเลขอื่นบ้างเล็กน้อย แต่ก็ดูเหมือนจะไม่ได้มากจนเกินไป
ในทางสถิตินั้น หากเราต้องการจะทราบว่าข้อมูลชุดหนึ่งมีการกระจายตัวที่สอดคล้องกับการกระจายตัวอย่างสม่ำเสมอ (uniform distribution) หรือไม่ เราสามารถทำได้โดยการคำนวณค่า Pearson's chi-squared test ซึ่งหากเรานำข้อมูลรางวัลเลขท้ายสองตัวตลอด 20 ปีนี้มาคำนวณดู เราจะพบว่า ข้อมูลที่ได้นั้น มีค่า chi-squared อยู่ต่ำกว่า Upper-tail critical values of chi-square distribution ทั้งที่ 95% และ 99% confidence interval สำหรับทั้งตัวบนและตัวล่าง นี่หมายความว่า เราไม่สามารถ reject null hypothesis ได้ และไม่มีหลักฐานเพียงพอที่จะยืนยันว่าข้อมูลชุดนี้มีการกระจายตัวที่ต่างออกไปจาก uniform distribution ด้วยความมั่นใจกว่า 99%
ทั้งนี้ทั้งนั้น นี่ไม่ได้เป็นการยืนยันหรือปฏิเสธว่าหวยมีการล๊อคหรือไม่ เราบอกได้เพียงแค่ว่า เลขที่ออกนั้นมีการกระจายตัวที่ค่อนข้าง uniform และมีโอกาสลงทุกเลขอย่างใกล้เคียงกัน อยู่ที่ว่าเราจะเลือกเลขที่ถูกหรือเปล่า
วิธีหนึ่งที่เราอาจจะเลือกเลขที่จะแทง "หวย" ก็คือการ "สุ่ม" ด้วยตัวเราเองโดยการนึกเลขมั่วๆ ขึ้นมาหนึ่งตัวเลข อย่างไรก็ตาม วิธีนี้นั้นมีปัญหาเป็นอย่างมาก เนื่องจากมีการศึกษามายืนยันเป็นอย่างมาก ว่าสมองของมนุษย์นั้นทำการสุ่มตัวเลขได้ค่อนข้างแย่ และตัวเลขที่เรา "สุ่ม" ขึ้นมาจากหัวนั้น ไม่สามารถเป็นเลขที่เกิดจากการ "สุ่ม" ได้อย่างแท้จริง
กราฟล่างซ้ายของภาพ เป็นกราฟที่ได้มาจาก reddit ที่เก็บข้อมูลที่ผู้เข้าร่วมมา "สุ่ม" ตัวเลขลงบนโซเชียลมีเดียกว่า 6750 ครั้ง จากกราฟเราจะพบว่ากราฟนี้ไม่ได้มีการกระจายตัวที่สม่ำเสมอทุกตัวเลขเท่ากัน ตัวเลขที่ได้รับการ "สุ่ม" มากที่สุดนั้นได้แก่เลข "69" (ด้วยเหตุผลบางประการ) "77" และ "7" ตามลำดับ ซึ่งมากกว่าตัวเลขอื่นอย่างเห็นได้ชัด นอกไปจากนี้ ตัวเลขระหว่าง 1-10 ถูกเลือกมากกว่าตัวเลขอื่นอย่างมีนัยะสำคัญ ซึ่งนี่สอดคล้องกับการศึกษาทางจิตวิทยา และอีกการเก็บข้อมูลหนึ่งที่พบว่าเลข 7 จะถูกเลือกบ่อยที่สุดถึงกว่า 28% เมื่อเราให้คน "สุ่ม" เลขระหว่าง 1-10 ขึ้นมากว่า 8500 ครั้ง[5] เนื่องจากสมองของเรานั้นมีความรู้สึกว่าเลข "7" นั้นควรจะเป็นเลขที่ "สุ่ม" ที่สุด เราจึงเลือกกันแต่เลข 7 จนกลายเป็นเลขที่ไม่สุ่มอีกต่อไป
ซึ่งหากเรานำ Pearson chi-square test มาทดสอบกับข้อมูลชุดนี้ เราจะพบว่าค่า chi-square ที่ได้นั้นเกิน Upper-tail critical values of chi-square distribution ที่ระดับความเชื่อมั่น 90% ไปอย่างไม่เห็นฝุ่น ซึ่งเป็นการแสดงให้เห็นว่าเลขท้ายสองตัวที่ได้จากสมองมนุษย์นั้น ไม่ได้มีการกระจายตัวอย่างสม่ำเสมอเหมือนอย่างที่หวยออกมาจริงๆ
แล้วการที่สมองมนุษย์ไม่สามารถ random เลขออกมาได้อย่างสม่ำเสมอนั้นมันสำคัญตรงไหน? เมื่อสมองมนุษย์ไม่สามารถ generate distribution แบบเดียวกันกับหวยได้ ก็ย่อมหมายความว่าต่อให้คนที่เชื่อว่ามี "สัญชาติญาณ" ดีที่สุดในการ "เดา" หวย ก็เป็นไปไม่ได้ที่จะถูกหวยอย่างต่อเนื่อง เพราะว่าเราไม่มีทางที่จะเดาหวยได้ถูกอย่างต่อเนื่องอย่างสม่ำเสมอ ในเมื่อหวยนั้นออกทุกเลขอย่างสม่ำเสมอ แต่สมองของเรานั้นไม่สามารถสม่ำเสมอได้
ซึ่งนี่นำไปสู่กลวิธีทุดท้ายที่เรามักจะนำมาเป็น "แรงบรรดาลใจ" ในการแทงหวย นั่นก็คือ การมองหาตัวเลขรอบๆ ข้างที่ไม่เกี่ยวกับตัวเราเอง ไม่ว่าจะเป็นจำนวนผู้เสียชีวิต ลำดับประธานาธิปดี เวลาท้องถิ่นขณะที่นายกทุ่มโพเดี้ยม ฯลฯ
อย่างไรก็ตาม วิธีนี้ก็มีปัญหาอีกเช่นกัน.... โดยเจ้าปัญหาที่ว่านี้ รู้จักกันในนามของ Benford's Law[6]
Benford's Law นั้นถูกค้นพบโดยบังเอิญโดย Simon Newcomb ในปี 1881 และอีกครั้งโดย Frank Benford ในปี 1938 โดยในยุคก่อนที่จะมีเครื่องคิดเลขของพวกเขานั้น การหาค่า Logarithm ทำได้โดยการเปิดสมุดเล่มหนาๆ เพื่อหาค่าจากในตาราง โดยนายทั้งสองคนนี้พบว่าหน้าแรกๆ ของสมุด logarithm table ของพวกเขานั้นเปื่อยเร็วกว่าหน้าหลังๆ เป็นอย่างมาก นาย Benford จึงตั้งสมมติฐานว่า ตัวเลขหลักหน้าของค่าที่พบในธรรมชาตินั้นอาจจะมีการกระจายตัวที่ไม่สม่ำเสมอกัน โดยที่ตัวเลขน้อยๆ ควรจะมีการพบได้บ่อยกว่า ตามกราฟแท่งสีน้ำเงินที่ด้านล่างขวาของภาพ และเขาได้ทดสอบกับตัวเลขในธรรมชาติที่ไม่ควรจะมีความเกี่ยวข้องกัน ตั้งแต่ พื้นที่ผิวของแม่น้ำ 335 สาย, ประชากรของเมืองในสหรัฐ 3259 เมือง, ค่าคงที่สากลทางฟิสิกส์กว่า 104 ค่า มวลโมเลกุลกว่า 1800 โมเลกุล, ตัวเลขที่ได้จากคู่มือคณิตศาสตร์กว่า 5000 ตัวเลข, ตัวเลขที่พบในนิตยสาร Reader's Digest กว่า 308 เลข, บ้านเลขที่ของคนกว่า 342 คนที่พบใน American Men of Science และอัตราการเสียชีวิตกว่า 418 อัตรา รวมทั้งหมดนาย Benford ได้นำตัวเลขที่ได้มาแบบสุ่มกว่า 20,229 เลข และพบว่าเลขเหล่านั้นมีตัวเลขหลักหน้ากระจายตัวตาม Benford's Law
กราฟด้านล่างขวา แสดงถึง Benford's Law เทียบกับการกระจายตัวของตัวเลขหลักหน้าของค่าคงที่ทางฟิสิกส์ ซึ่งจะเห็นได้ว่ามีการกระจายตัวสอดคล้องกับ Benford's Law เป็นอย่างมาก นอกไปจากนี้ Benford's Law ยังใช้ได้อยู่ ไม่ว่าเราจะแปลงค่าต่างๆ ที่พบไปเป็นเลขฐานใดๆ หรือหน่วยใดๆ ก็ตาม ตัวอย่างเช่น Benford's Law ทำนายเอาไว้ว่า ตัวเลขกว่า 30.1% จะขึ้นต้นด้วยเลข 1 ซึ่งหากเรานำความสูงของตึกที่สูงที่สุดในโลก 58 ตึก เราจะพบว่าตึกกว่า 41% นั้นมีความสูงในหน่วยเมตรขึ้นต้นด้วยเลข 1 และแม้ว่าเราจะเปลี่ยนหน่วยเป็นหน่วยฟุต เราก็ยังจะพบว่าตึกกว่า 28% นั้นมีความสูงในหน่วยฟุตขึ้นต้นด้วยเลข 1 ซึ่งมากกว่าเลขอื่นใดๆ
แล้วเพราะเหตุใดเราจึงไม่พบเลขในธรรมชาติในจำนวนที่เท่าๆ กันทุกเลข? คำอธิบายที่ง่ายที่สุดก็คงจะเป็นเพราะว่า สิ่งต่างๆ หลายสิ่งในธรรมชาตินั้นมีความสัมพันธ์เชิง logarithm ซึ่งหากเราแปลงเลขในฐานสิบให้อยู่ในสเกลของ logarithm เราจะได้เส้นจำนวนดังภาพล่างขวาในภาพ จากเส้นจำนวนนี้ เราจะพบว่าหากเราจิ้มตำแหน่งโดยสุ่มบนเส้นจำนวนนี้ โอกาสส่วนมากที่สุดนั้นจะตกอยู่ในเลขที่มีหลักนำหน้าเป็น 1 ตามด้วย 2,3,4 ลดหลั่นลงไป ตาม Benford's Law
Benford's Law นี้มีประโยชน์เป็นอย่างยิ่ง ในการตรวจจับการโกง เนื่องจากสมองของมนุษย์นั้นมีความคาดหวังที่จะให้ทุกตัวเลขตกลงเท่าๆ กัน ตัวเลขที่ได้จากการเมคข้อมูลของคนจึงไม่เป็นไปตาม Benford's Law ซึ่งสามารถใช้เป็นหลักฐานบ่งบอกว่ามีอะไรบางอย่างตุกติกเกิดขึ้นในข้อมูล
ตัวอย่างที่ชัดเจนที่สุดตัวอย่างหนึ่งก็คือ ข้อมูลของจำนวนผู้ติดเชื้อ COVID-19 เนื่องจากการติดเชื้อนั้นมีการแพร่กระจายตัวแบบ exponential ตัวเลขจำนวนผู้ติดเชื้อนั้นจึงควรจะเป็นไปตาม Benford's Law ทีมนักวิจัยจึงได้มีการนำตัวเลขจำนวนผู้ติดเชื้อที่รายงานในแต่ละประเทศมาเปรียบเทียบกับ Benford's Law[7] และพบว่าข้อมูลจากประเทศรัสเซียและอิหร่านนั้นไม่เป็นไปตาม Benford's Law ในขณะที่จำนวนผู้ติดเชื้อจาก สหรัฐ บราซิล อินเดีย เปรู อาฟริกาใต้ โคลอมเบีย เม็กซิโก สเปน อาร์เจนตินา ชิลี อังกฤษ ฝรั่งเศส ซาอุ จีน ฟิลิปปินส์ เบลเยี่ยม ปากีสถาน และอิตาลี เป็นไปตาม Benford's Law ไม่ผิดเพี้ยน
ทั้งหมดนี้ก็วกกลับมาที่ปัญหาหลักของการนำค่าที่พบในธรรมชาติมาทำนายหวย: ค่าที่พบในธรรมชาตินั้นไม่ได้มีการกระจายตัวอย่างสม่ำเสมอ แต่หวยนั้นกระจายตัวอย่างสม่ำเสมอ (ซึ่งยังไม่นับกรณีเช่นเอาวันที่ซึ่งไม่มีทางเกิน 31 มาแทง) ตัวเลขที่เราพบในธรรมชาตินั้นจึงเปรียบได้กับลูกเต๋าที่ถูกถ่วงน้ำหนักเอาไว้ให้ได้ค่าต่ำๆ คำถามก็คือ ลูกเต๋าที่ถ่วงน้ำหนักเอาไว้นั้น จะเป็นตัวแทนที่จะทำนายผลของลูกเต๋าที่มาตรฐานได้แม่นจำจริงหรือ?
ทั้งนี้ทั้งนั้น การเล่นหวยหรือไม่เป็นเรื่องของแต่ละบุคคล และถึงแม้ว่าส่วนตัวในฐานะนักวิทยาศาสตร์นั้นจะไม่เห็นด้วยกับเรื่องงมงาย แต่การลงทุนหวยเพียงไม่กี่ร้อย และกับเสี้ยวเวลาเล็กๆ ที่จะได้ลุ้นถึงอนาคตที่ดีขึ้น บางทีก็อาจจะเป็นการลงทุนที่คุ้มค่าสำหรับคนหลายๆ คนก็ได้
หมายเหตุ: บทความนี้เราไม่ได้พูดถึง "โต๊ด" และ Benford's Law นั้นมีผลกับเลขหลักหน้าๆ มากกว่าหลักท้ายๆ แต่คำเตือนนี้ไม่ใช่การใบ้หวย...
อ้างอิง/อ่านเพิ่มเติม:
[1] https://horoscope.thaiorc.com/lottery/stats/lotto-years20.php
[2] https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test
[3] https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3632045/
[4] https://www.reddit.com/r/dataisbeautiful/comments/88m2mj/pick_a_number_from_1100_results_from_6750/
[5] https://www.reddit.com/r/dataisbeautiful/comments/acow6y/asking_over_8500_students_to_pick_a_random_number/
[6] https://en.wikipedia.org/wiki/Benford%27s_law
[7] https://www.researchgate.net/publication/344164702_Is_COVID-19_data_reliable_A_statistical_analysis_with_Benford's_Law
logarithm 在 Taipei Ethereum Meetup Facebook 的精選貼文
📜 [專欄新文章] [ZKP 讀書會] Trust Token Browser API
✍️ Yuren Ju
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
Trust Token API 是一個正在標準化的瀏覽器 API,主要的目的是在保護隱私的前提下提供跨站授權 (Cross-domain authorization) 的功能,以前如果需要跨站追蹤或授權通常都使用有隱私疑慮的 Cookies 機制,而 Trust Token 則是希望在保護隱私的前提下完成相同的功能。
會在 ZKP (Zero-knowledge proof) 讀書會研究 Trust Token 主要是這個 API 採用了零知識證明來保護隱私,這也是這次讀書會中少見跟區塊鏈無關的零知識證明應用。
問題
大家應該都有點了一個產品的網頁後,很快的就在 Facebook 或是 Google 上面看到相關的廣告。但是產品網頁並不是在 Facebook 上面,他怎麼會知道我看了這個產品的頁面?
通常這都是透過 Cookie 來做跨網站追蹤來記錄你在網路上的瀏覽行為。以 Facebook 為例。
當使用者登入 Facebook 之後,Facebook 會透過 Cookie 放一段識別碼在瀏覽器裡面,當使用者造訪了有安裝 Facebook SDK 來提供「讚」功能的網頁時,瀏覽器在載入 SDK 時會再度夾帶這個識別碼,此時 Facebook 就會知道你造訪了特定的網頁並且記錄下來了。如此一來再搭配其他不同管道的追蹤方式,Facebook 就可以建構出特定使用者在網路上瀏覽的軌跡,從你的瀏覽紀錄推敲喜好,餵給你 Facebook 最想給你看的廣告了。
不過跨站追蹤也不是只能用在廣告這樣的應用上,像是 CDN (Content Delivery Network) 也是一個應用場景。CDN 服務 Cloudflare 提供服務的同時會利用 Captcha 先來確定進入網站的是不是真人或是機器人。而他希望使用者如果是真人時下次造訪同時也是採用 Cloudflare 服務的網站不要再跳出 Captcha 驗證訊息。
雖然 Cloudflare 也需要跨站驗證的功能來完成他們的服務,但是相較於 Google 或 Facebook 來說他們是比較沒那麼想知道使用者的隱私。有沒有什麼辦法可以保護使用者隱私的狀況下還能完成跨站驗證呢?
這就是今天要講的新 API: Trust Token。
Trust Token API - The Chromium Projects
Trust Token / Privacy Pass 簡介
Trust Token 其實是由 Privacy Pass 延伸而來。Privacy Pass 就是由 Cloudflare 所開發的實驗性瀏覽器延伸套件實作一個驗證機制,可以在不透漏過多使用者隱私的前提下實作跨站驗證。而 Trust Token 則是標準化的 Privacy Pass,所以兩個運作機制類似,但是實作方式稍有不同。
先看一下 Privacy Pass 是如何使用。因為這是實驗性的瀏覽器延伸套件所以看起來有點陽春,不過大致上還是可以了解整個概念。
以 hCaptcha 跟 Cloudflare 的應用為例,使用者第一次進到由 Cloudflare 提供服務的網站時,網站會跳出一些人類才可以解答的問題比如說「挑出以下是汽車的圖片」。
當使用者答對問題後,Cloudflare 會回傳若干組 blind token,這些 blind token 還會需要經過 unblind 後才會變成真正可以使用的 token,這個過程為 issue token。如上圖所示假設使用者這次驗證拿到了 30 個 token,在每次造訪由 Cloudflare 服務的網站時就會用掉一個 token,這個步驟稱為 redeem token。
但這個機制最重要的地方在於 Cloudflare 並無法把 issue token 跟 redeem token 這兩個階段的使用者連結在一起,也就是說如果 Alice, Bob 跟 Chris 都曾經通過 Captcha 測試並且獲得了 Token,但是在後續瀏覽不同網站時把 token 兌換掉時,Clouldflare 並無法區分哪個 token 是來自 Bob,哪個 token 是來自 Alice,但是只要持有這種 token 就代表持有者已經通過了 Captcha 的挑戰證明為真人。
但這樣的機制要怎麼完成呢?以下我們會透過多個步驟的例子來解釋如何達成這個目的。不過在那之前我們要先講一下 Privacy Pass 所用到的零知識證明。
零知識證明 (Zero-knowledge proof)
零知識證明是一種方法在不揭露某個祕密的狀態下,證明他自己知道那個秘密。
Rahil Arora 在 stackexchange 上寫的比喻我覺得是相對好理解的,下面簡單的翻譯一下:
假設 Alice 有超能力可以幾秒內算出樹木上面有幾片樹葉,如何在不告訴 Bob 超能力是怎麼運作並且也不告訴 Bob 有多少片葉子的狀況下證明 Alice 有超能力?我們可以設計一個流程來證明這件事情。
Alice 先把眼睛閉起來,請 Bob 選擇拿掉樹上的一片葉子或不拿掉。當 Alice 睜開眼睛的時候,告訴 Bob 他有沒有拿掉葉子。如果一次正確的話確實有可能是 Alice 幸運猜到,但是如果這個過程連續很多次時 Alice 真的擁有數葉子的超能力的機率就愈來愈高。
而零知識證明的原理大致上就是這樣,你可以用一個流程來證明你知道某個秘密,即使你不真的揭露這個秘密到底是什麼,以上面的例子來說,這個秘密就是超能力運作的方式。
以上就是零知識證明的概念,不過要完成零知識證明有很多各式各樣的方式,今天我們要介紹的是 Trust Token 所使用的零知識證明:DLEQ。
DLEQ (Discrete Logarithm Equivalence Proof)
說明一下以下如果小寫的變數如 c, s 都是純量 (Scalar),如果是大寫如 G, H則是橢圓曲線上面的點 (Point),如果是 vG 則一樣是點,計算方式則是 G 連續相加 v 次,這跟一般的乘法不同,有興趣可以程式前沿的《橢圓曲線加密演算法》一文解釋得比較詳細。
DLEQ 有一個前提,在系統中的所有人都知道公開的 G 跟 H 兩個點,此時以下等式會成立:
假設 Peggy 擁有一個秘密 s 要向 Victor 證明他知道 s 為何,並且在這個過程中不揭露 s 真正的數值,此時 Victor 可以產生一個隨機數 c 傳送給 Peggy,而 Peggy 則會再產生一個隨機數 v 並且產生 r,並且附上 vG, vH, sG, sH:
r = v - cs
所以 Victor 會得到 r, sG, sH, vG, vH 再加上他已經知道的 G, H。這個時候如果 Victor 計算出以下兩個等式就代表 Peggy 知道 s 的真正數值:
vG = rG + c(sG)vH = rH + c(sH)
我們舉第二個等式作為例子化簡:
vH = rH + c(sH) // 把 r 展開成 v - csvH = (v - cs)H + c(sH) // (v - cs)H 展開成 vH - csHvH = vH - c(sH) + c(sH) // 正負 c(sH) 消掉vH = vH
這樣只有 Peggy 知道 s 的狀況下才能給出 r,所以這樣就可以證明 Peggy 確實知道 s。
從簡易到實際的情境
Privacy Pass 網站上透過了循序漸進的七種情境從最簡單的假設到最後面實際使用的情境來講解整個機制是怎麼運作的。本文也用相同的方式來解釋各種情境,不過前面的例子就會相對比較天真一點,就請大家一步步的往下看。
基本上整個過程是透過一種叫做 Blind Signature 的方式搭配上零知識證明完成的,以下參與的角色分為 Client 與 Server,並且都會有兩個階段 issue 與 redeem token。
Scenario 1
如果我們要設計一個這樣可以兌換 token 來確認身分的系統,其中有一個方法是透過橢圓曲線 (elliptic curve) 完成。Client 挑選一個在橢圓曲線上的點 T 並且傳送給 Server,Server 收到後透過一個只有 Server 知道的純量 (scalar) s 對 T 運算後得到 sT 並且回傳給 Client,這個產生 sT 的過程稱為 Sign Point,不過實際上運作的原理就是橢圓曲線上的連續加法運算。
SignPoint(T, s) => sT
等到 Client 需要兌換時只要把 T 跟 sT 給 Server,Server 可以收到 T 的時候再 Sign Point 一次看看是不是 sT 就知道是否曾經 issue 過這個 token。
Issue
以下的範例,左邊都是 Client, 右邊都是 Server。 -> 代表 Client 發送給 Server,反之亦然。
// Client 發送 T 給 Server, 然後得到 sT
T -> <- sT
Redeem
// Client 要 redeem token 時,傳出 T 與 sT
T, sT ->
問題:Linkability
因為 Server 在 issue 的時候已經知道了 T,所以基本上 Server 可以透過這項資訊可以把 issue 階段跟 redeem 階段的人連結起來進而知道 Client 的行為。
Scenario 2
要解決上面的問題,其中一個方法是透過 Blind Signature 達成。Client 不送出 T,而是先透過 BlindPoint 的方式產生 bT 跟 b,接下來再送給 Server bT。Server 收到 bT 之後,同樣的透過 Sign Point 的方式產生結果,不一樣的地方是情境 1 是用 T,而這邊則用 bT 來作 Sign Point,所以得出來的結果是 s(bT)。
Client:BlindPoint(T) => (bT, b)
Server:SignPoint(bT, s) => sbT
而 Blind Signature 跟 Sign Point 具備了交換律的特性,所以得到 s(bT) 後可以透過原本 Client 已知的 b 進行 Unblind:
UnblindPoint(sbT, b) => sT
這樣一來在 Redeem 的時候就可以送出 T, sT 給 Server 了,而且透過 SignPoint(T, s) 得出結果 sT’ 如果符合 Client 傳來的 sT 就代表確實 Server 曾經簽過這個被 blind 的點,同時因為 T 從來都沒有送到 Server 過,所以 Server 也無法將 issue 與 redeem 階段的 Client 連結在一起。
Issue
bT -> <- s(bT)
Redeem
T, sT ->
問題:Malleability
以上的流程其實也有另外一個大問題,因為有交換律的關係,當 Client 透過一個任意值 a 放入 BlindPoint 時產生的 a(sT) 就會等於 s(aT):
BlindPoint(sT) => a(sT), a// a(sT) === s(aT)
此時如果將 aT 跟 s(aT) 送給 Server Redeem,此時因為
SignPoint(aT, s) => s(aT)
所以就可以兌換了,這樣造成 Client 可以無限地用任意數值兌換 token。
Scenario 3
這次我們讓 Client 先選擇一個純數 t,並且透過一種單向的 hash 方式來產生一個在橢圓曲線上的點 T,並且在 redeem 階段時原本是送出 T, sT 改成送出 t, sT。
因為 redeem 要送出的是 t,上個情境時透過任意數 a 來產生 s(aT) 的方法就沒辦法用了,因為 t 跟 sT 兩個參數之間並不是單純的再透過一次 BlindPoint() 就可以得到,所以就沒辦法無限兌換了。
Issue
T = Hash(t) bT -> <- sbT
Redeem
t, sT ->
問題:Redemption hijacking
在這個例子裏面,Client 其實是沒有必要傳送 sT 的,因為 Server 僅需要 t 就可以計算出 sT,額外傳送 sT 可能會導致潛在的 Redemption hijacking 問題,如果在不安全的通道上傳輸 t, sT 就有可能這個 redemption 被劫持作為其他的用途。
不過在網站上沒講出實際上要怎麼利用這個問題,但是少傳一個可以計算出來的資料總是好的。Client 只要證明他知道 sT 就好,而這可以透過 HMAC (Hash-based Message Authentication Code) 達成。
Scenario 4
步驟跟前面都一樣,唯一不一樣的地方是 redeem 的時候原本是傳 t, sT,現在則改傳 t, M, HMAC(sT, M),如果再介紹 HMAC 篇幅會太大,這邊就不解釋了,但可以是作是一個標準的 salt 方式讓 Hash 出來的結果不容易受到暴力破解。
這樣的特性在這個情境用很適合,因為 Server 透過 t 就可以計算出 sT,透過公開傳遞的 M 可以輕易地驗證 client 端是否持有 sT。
Issue
T = Hash(t) bT -> <- sbT
Redeem
t, M, HMAC(sT, M) ->
問題:Tagging
這邊的問題在於 Server 可以在 issue 階段的時候用不一樣的 s1, s2, s3 等來發出不一樣的 sT’,這樣 Server 在 Redeem 階段就可以得知 client 是哪一個 s。所以 Server 需要證明自己每次都用同樣的 s 同時又不透漏 s 這個純亮。
要解決這個問題就需要用到前面我們講解的零知識證明 DLEQ 了。
Scenario 5
前面的 DLEQ 講解有提到,如果有 Peggy 有一個 s 秘密純量,我們可以透過 DLEQ 來證明 Peggy 知道 s,但是又不透漏 s 真正的數值,而在 Privacy Pass 的機制裡面,Server 需要證明自己每次都用 s,但是卻又不用揭露真正的數值。
在 Issue 階段 Client 做的事情還是一樣傳 bT 給 Server 端,但 Server 端的回應就不一樣了,這次 Server 會回傳 sbT 與一個 DLEQ 證明,證明自己正在用同一個 s。
首先根據 DLEQ 的假設,Server 會需要先公開一組 G, H 給所有的 Client。而在 Privacy Pass 的實作中則是公開了 G 給所有 Client,而 H 則改用 bT 代替。
回傳的時候 Server 要證明自己仍然使用同一個 s 發出 token,所以附上了一個 DLEQ 的證明 r = v - cs,Client 只要算出以下算式相等就可證明 Server 仍然用同一個 s (記住了 H 已經改用 bT 代替,此時 client 也有 sbT 也就是 sH):
vH = rH + c(sH) // H 換成 bTvbT = rbT + c(sbT) // 把 r 展開成 v - csvbT = (v - cs)bT + c(sbT) // (v - cs)bT 展開成 vbT - csbTvbT = vbT - c(sbT) + c(sbT) // 正負 c(sbT) 消掉vbT = vbT
這樣就可以證明 Server 依然用同一個 s。
Issue
T = Hash(t) bT -> <- sbT, DLEQ(bT:sbT == G:sG)
Redeem
t, M, HMAC(sT, M) ->
問題:only one redemption per issuance
到這邊基本上 Privacy Pass 的原理已經解釋得差不多了,不過這邊有個問題是一次只發一個 token 太少,應該要一次可以發多個 token。這邊我要跳過源文中提到的 Scenario 6 解釋最後的結果。
Scenario 7
由於一次僅產生一個 redeem token 太沒效率了,如果同時發很多次,每次都產生一個 proof 也不是非常有效率,而 DLEQ 有一個延伸的用法 “batch” 可以一次產生多個 token, 並且只有使用一個 Proof 就可以驗證所有 token 是否合法,這樣就可以大大的降低頻寬需求。
不過這邊我們就不贅述 Batch DLEQ 的原理了,文末我會提及一些比較有用的連結跟確切的源碼片段讓有興趣的人可以更快速的追蹤到源碼片段。
Issue
T1 = Hash(t1) T2 = Hash(t2)T3 = Hash(t3)b1T1 ->b2T2 ->b3T3 -> c1,c2,c3 = H(G,sG,b1T1,b2T2,b3T3,s(b1T1),s(b2T2),s(b3T3)) <- sb1T1 <- sb2T2 <- sb3T3 <- DLEQ(c1b1T1+c2b2T2+c3b3T3:s(c1b1T1+c2b2T2+c3b3T3) == G: sG)
Redeem
t1, M, HMAC(sT1, M) ->
結論
Privacy Token / Trust Token API 透過零知識證明的方式來建立了一個不需要透漏太多隱私也可以達成跟 cookie 相同效果的驗證方式,期待可以改變目前許多廣告巨頭透過 cookie 過分的追蹤使用者隱私的作法。
不過我在 Trust Token API Explainer 裡面看到這個協議裡面的延伸作法還可以夾帶 Metadata 進去,而協議制定的過程中其實廣告龍頭 Google 也參與其中,希望這份協議還是可以保持中立,盡可能地讓最後版本可以有效的在保護隱私的情況下完成 Cross-domain authorization 的功能。
參考資料
IETF Privacy Pass docs
Privacy Pass: The Protocol
Privacy Pass: Architectural Framework
Privacy Pass: HTTP API
Cloudflare
Supporting the latest version of the Privacy Pass Protocol (cloudflare.com)
Chinese: Cloudflare支持最新的Privacy Pass扩展_推动协议标准化
Other
Privacy Pass official website
Getting started with Trust Tokens (web.dev)
WICG Trust Token API Explainer
Non-interactive zero-knowledge (NIZK) proofs for the equality (EQ) of discrete logarithms (DL) (asecuritysite.com) 這個網站非常實用,列了很多零知識證明的源碼參考,但可惜的是 DLEQ 這個演算法講解有錯,讓我在理解演算法的時候撞牆很久。所以使用的時候請多加小心,源碼應該是可以參考的,解釋的話需要斟酌一下。
關鍵源碼
這邊我貼幾段覺得很有用的源碼。
privacy pass 提供的伺服器端產生 Proof 的源碼
privacy pass 提供的瀏覽器端產生 BlindPoint 的源碼
github dedis/kyber 產生 Proof 的源碼
[ZKP 讀書會] Trust Token Browser API was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
logarithm 在 Herman Yeung Youtube 的精選貼文
HKDSE Mathematics 數學天書 訂購表格及方法︰https://www.sites.google.com/view/HermanYeung
課程簡介︰ https://youtu.be/KKTtzLkpyO8
------------------------------------------------------------------------------
DSE 數學 Core 天書 A 第1堂 (共2小時45分鐘) https://www.youtube.com/playlist?list=PLzDe9mOi1K8p2A7HMhwz4udhLJTQt9p2b
DSE 數學 Core 天書 A 第2堂 (共2小時8分鐘) https://youtu.be/SGeMFO9tips?list=PLzDe9mOi1K8p2A7HMhwz4udhLJTQt9p2b
DSE 數學 Core 天書 A 第3堂 (共2小時4分鐘) https://youtu.be/-z_sjshGWEs?list=PLzDe9mOi1K8p2A7HMhwz4udhLJTQt9p2b
DSE 數學 Core 天書 A 第4堂 (共3小時17分鐘) https://youtu.be/1yWKUMSE5fU?list=PLzDe9mOi1K8p2A7HMhwz4udhLJTQt9p2b
Past Paper Demo (太多,無法估計) https://youtu.be/41cdF_BqxME?list=PLzDe9mOi1K8p2A7HMhwz4udhLJTQt9p2b
舊制 HKCEE Maths Past Paper Solution (All) https://www.youtube.com/playlist?list=PLzDe9mOi1K8qthFpSv8ZLVajrHM_9TvZx
舊制 HKCEE Additional Maths Past Paper Solution (All) https://www.youtube.com/playlist?list=PLzDe9mOi1K8pv5NrsmraFHphqAFHaxtaD
Past Paper (香港公共圖書館): https://mmis.hkpl.gov.hk/web/guest/hkcee-and-hkale-papers-collection
------------------------------------------------------------------------------
DSE 數學 Core 天書 A 的內容:
1 -- Number system 數系
2 -- Estimation and Error 估算及誤差
3 -- Quadratic Equation 二次方程
4 -- Function and Graph 函數及圖像
5 -- Exponential (Index) and Logarithm 指數及對數
6 -- More about Graphs 進階圖像
7 -- Numeral systems 進制系統
------------------------------------------------------------------------------
DSE 數學 Core 各天書 的內容︰ https://www.sites.google.com/view/hermanyeung/bookcontent
訂購表格及方法︰https://www.sites.google.com/view/HermanYeung
------------------------------------------------------------------------------
Herman Yeung HKDSE Maths 數學 Core 課程:
超過 100 小時 YouTube 免費課程
共 12 本天書完成整個 HKDSE 數學 Core
(中一至中六) 要考的所有課題,
適合任何考 HKDSE 的同學上課 (中四至中六都合適)
(p.s. Herman Yeung 所有天書,中英對照)
------------------------------------------------------------------------------
Please subscribe 請訂閱︰ https://www.youtube.com/hermanyeung?sub_confirmation=1
------------------------------------------------------------------------------
Blogger︰ https://hermanutube.blogspot.hk/2016/02/herman-yeung-main-menu.html
Facebook︰ https://www.facebook.com/hy.page
YouTube︰ https://www.youtube.com/HermanYeung
Instagram︰ https://www.instagram.com/hermanyeung_hy
------------------------------------------------------------------------------
logarithm 在 Herman Yeung Youtube 的精選貼文
HKDSE Mathematics 數學天書 訂購表格及方法︰https://www.sites.google.com/view/HermanYeung
課程簡介︰ https://youtu.be/KKTtzLkpyO8
(e-Book) DSE Maths 數學 Past Paper Solution︰ https://hermanutube.blogspot.com/2021/05/hkdse-maths-10-past-paper-solution-2021.html
------------------------------------------------------------------------------
DSE 數學 Core 天書 A 第1堂 (共2小時45分鐘) https://www.youtube.com/playlist?list=PLzDe9mOi1K8p2A7HMhwz4udhLJTQt9p2b
DSE 數學 Core 天書 A 第2堂 (共2小時8分鐘) https://youtu.be/SGeMFO9tips?list=PLzDe9mOi1K8p2A7HMhwz4udhLJTQt9p2b
DSE 數學 Core 天書 A 第3堂 (共2小時4分鐘) https://youtu.be/-z_sjshGWEs?list=PLzDe9mOi1K8p2A7HMhwz4udhLJTQt9p2b
DSE 數學 Core 天書 A 第4堂 (共3小時17分鐘) https://youtu.be/1yWKUMSE5fU?list=PLzDe9mOi1K8p2A7HMhwz4udhLJTQt9p2b
Past Paper Demo (太多,無法估計) https://youtu.be/41cdF_BqxME?list=PLzDe9mOi1K8p2A7HMhwz4udhLJTQt9p2b
HKDSE Maths (Core) Past Paper Solution (All) https://www.youtube.com/playlist?list=PLzDe9mOi1K8qUwsow09TJIjFcaTCdmnSB
------------------------------------------------------------------------------
DSE 數學 Core 天書 A 的內容:
1 -- Number system 數系
2 -- Estimation and Error 估算及誤差
3 -- Quadratic Equation 二次方程
4 -- Function and Graph 函數及圖像
5 -- Exponential (Index) and Logarithm 指數及對數
6 -- More about Graphs 進階圖像
7 -- Numeral systems 進制系統
------------------------------------------------------------------------------
DSE 數學 Core 各天書 的內容︰ https://www.sites.google.com/view/hermanyeung/bookcontent
訂購表格及方法︰https://www.sites.google.com/view/HermanYeung
------------------------------------------------------------------------------
Herman Yeung HKDSE Maths 數學 Core 課程:
超過 100 小時 YouTube 免費課程
共 12 本天書完成整個 HKDSE 數學 Core
(中一至中六) 要考的所有課題,
適合任何考 HKDSE 的同學上課 (中四至中六都合適)
(p.s. Herman Yeung 所有天書,中英對照)
------------------------------------------------------------------------------
Please subscribe 請訂閱︰ https://www.youtube.com/hermanyeung?sub_confirmation=1
------------------------------------------------------------------------------
Blogger︰ https://hermanutube.blogspot.hk/2016/02/herman-yeung-main-menu.html
Facebook︰ https://www.facebook.com/hy.page
YouTube︰ https://www.youtube.com/HermanYeung
Instagram︰ https://www.instagram.com/hermanyeung_hy
------------------------------------------------------------------------------
logarithm 在 Herman Yeung Youtube 的最佳貼文
HKDSE Mathematics 數學天書 訂購表格及方法︰https://www.sites.google.com/view/HermanYeung
課程簡介︰ https://youtu.be/KKTtzLkpyO8
(e-Book) DSE Maths 數學 Past Paper Solution︰ https://hermanutube.blogspot.com/2021/05/hkdse-maths-10-past-paper-solution-2021.html
------------------------------------------------------------------------------
DSE 數學 Core 天書 A 第1堂 (共2小時45分鐘) https://www.youtube.com/playlist?list=PLzDe9mOi1K8p2A7HMhwz4udhLJTQt9p2b
DSE 數學 Core 天書 A 第2堂 (共2小時8分鐘) https://youtu.be/SGeMFO9tips?list=PLzDe9mOi1K8p2A7HMhwz4udhLJTQt9p2b
DSE 數學 Core 天書 A 第3堂 (共2小時4分鐘) https://youtu.be/-z_sjshGWEs?list=PLzDe9mOi1K8p2A7HMhwz4udhLJTQt9p2b
DSE 數學 Core 天書 A 第4堂 (共3小時17分鐘) https://youtu.be/1yWKUMSE5fU?list=PLzDe9mOi1K8p2A7HMhwz4udhLJTQt9p2b
Past Paper Demo (太多,無法估計) https://youtu.be/41cdF_BqxME?list=PLzDe9mOi1K8p2A7HMhwz4udhLJTQt9p2b
HKDSE Maths (Core) Past Paper Solution (All) https://www.youtube.com/playlist?list=PLzDe9mOi1K8qUwsow09TJIjFcaTCdmnSB
------------------------------------------------------------------------------
DSE 數學 Core 天書 A 的內容:
1 -- Number system 數系
2 -- Estimation and Error 估算及誤差
3 -- Quadratic Equation 二次方程
4 -- Function and Graph 函數及圖像
5 -- Exponential (Index) and Logarithm 指數及對數
6 -- More about Graphs 進階圖像
7 -- Numeral systems 進制系統
------------------------------------------------------------------------------
DSE 數學 Core 各天書 的內容︰ https://www.sites.google.com/view/hermanyeung/bookcontent
訂購表格及方法︰https://www.sites.google.com/view/HermanYeung
------------------------------------------------------------------------------
Herman Yeung HKDSE Maths 數學 Core 課程:
超過 100 小時 YouTube 免費課程
共 12 本天書完成整個 HKDSE 數學 Core
(中一至中六) 要考的所有課題,
適合任何考 HKDSE 的同學上課 (中四至中六都合適)
(p.s. Herman Yeung 所有天書,中英對照)
------------------------------------------------------------------------------
Please subscribe 請訂閱︰ https://www.youtube.com/hermanyeung?sub_confirmation=1
------------------------------------------------------------------------------
Blogger︰ https://hermanutube.blogspot.hk/2016/02/herman-yeung-main-menu.html
Facebook︰ https://www.facebook.com/hy.page
YouTube︰ https://www.youtube.com/HermanYeung
Instagram︰ https://www.instagram.com/hermanyeung_hy
------------------------------------------------------------------------------
logarithm 在 Logarithms - Basics | What are Logs? | Don't Memorise 的必吃
What are Logarithms or logs? How are they related to Exponents? Watch this video to know the answers. To ... ... <看更多>
logarithm 在 Logarithms... How? (NancyPi) - YouTube 的必吃
MIT grad introduces logs and shows how to evaluate them. To skip ahead: 1) For how to understand and ... ... <看更多>