commit 501b0cf2cde97b394552a0d3fdacb22b9eefefd3
parent 0d2bd0c01825a92ae238ee2927a67e68108614cb
Author: Antoine A <>
Date: Thu, 5 May 2022 16:48:41 +0200
report progress
Diffstat:
2 files changed, 31 insertions(+), 30 deletions(-)
diff --git a/docs/figures/reorg.tex b/docs/figures/reorg.tex
@@ -5,7 +5,7 @@
]
% Common
\node[block](1){};
- \node[block,right=5mm of 1](2){$D_0$};
+ \node[block,right=5mm of 1](2){};
\node[block,right=5mm of 2](3){};
\draw[ar] (1) -- (2);
\draw[ar] (2) -- (3);
@@ -13,14 +13,14 @@
% Current
\node[block,right=5mm of 3](4){};
\node[block,right=5mm of 4](5){};
- \node[block,right=5mm of 5](6){$D_1$};
+ \node[block,right=5mm of 5](6){};
\draw[ar] (3) -- (4);
\draw[ar] (4) -- (5);
\draw[ar] (5) -- (6);
% Fork
\node[block,above=7mm of 4](4p){};
- \node[block,right=5mm of 4p](5p){$D_2$};
+ \node[block,right=5mm of 4p](5p){};
\node[block,right=5mm of 5p](6p){};
\node[block,right=5mm of 6p](7p){};
\draw[ar] (3.east) -- (4p.west);
diff --git a/docs/report.tex b/docs/report.tex
@@ -55,7 +55,7 @@ To achieve this goal, we need to understand how the distributed ledgers of block
Blockchain reorganization prevents the finality of blockchain transactions, which is unacceptable for a settlement layer. By using a confirmation delay, we can create a semblance of finality. However, we still have to handle extreme cases where our delay is insufficient by suspending operations and gracefully recovering when possible.
-We have created a depolymerizer, which acts as an adapter between GNU Taler and a \ac{DLT}, allowing their use as a settlement layer. By using official DLT clients, and separating Taler specific from \ac{DLT} specific components, we achieved a simple and maintainable design.
+We have created a depolymerizer, which acts as an adapter between GNU Taler and a \ac{DLT}, allowing their use as a settlement layer. By using official DLT clients, and separating Taler specific components from \ac{DLT} specific components, we achieved a simple and maintainable design.
By proving that blockchains can be used as a settlement layer for GNU Taler, we show that it is not only capable of handling bank money, but also widely used cryptocurrencies.
@@ -81,7 +81,7 @@ Bitcoin is the first cryptocurrency to achieve a successful public rollout. Inve
\subsubsection*{Ethereum}
-Bitcoin is focused on currency transfer transactions and some people wanted to do more with cryptocurrencies, to be able to execute smart contracts (programs) with the same guarantee as a currency transfer transaction. Ethereum is that cryptocurrency. After eighteen months of crowdfunded development, Ethereum launched in July 2015.
+Bitcoin is focused on currency transfer transactions and some people wanted to do more with cryptocurrencies, to be able to run smart contracts (programs) with the same guarantee as a currency transfer transaction. Ethereum is built to meet this expectation. After eighteen months of crowdfunding-funded development, Ethereum was launched in July 2015.
\subsection{Blockchain}
@@ -101,13 +101,13 @@ Another problem is that miners are incentivized to invest more and more computin
\subsubsection*{Proof of stake}
-This mechanism replaces the use of computing power with the stacking of money. Validators (who replace miners) stake large sums of money to be allowed to verified blocks and be randomly selected to propose them. In case of malicious behaviour, the stacked money is burned by other validators.
+This mechanism replaces the use of computing power with the stacking of money. Validators (who replace miners) stake large sums of money to be allowed to verify blocks and be randomly selected to propose them. In case of malicious behaviour, the stacked money is burned by other validators.
The effectiveness and security of this mechanism have yet to be proven, but Ethereum plans to adopt it in the summer of 2022.
\subsubsection*{Block time}
-Achieving consensus within the peer-to-peer network requires broadcasting the state of the blockchain to most nodes. This coordination takes some time, and we do not want blocks to be mined faster than the network can keep up. An adaptive difficulty algorithm is used to keep the block time close to a constant, by changing the amount of computation required to mine a block. On Ethereum, the block time is about 12 to 14 seconds \footnote{https://ethereum.org/en/developers/docs/blocks/\#block-time}. On Bitcoin, the block time is about 10 minutes. This limitation combined with a block size limit creates a transaction rate and a blockchain size growth limit that is difficult to change without disrupting the security of the system.
+Achieving consensus within the peer-to-peer network requires broadcasting the state of the blockchain to most nodes. This coordination takes some time, and we do not want blocks to be mined faster than the network can keep up. An adaptive difficulty algorithm is used to keep the block time close to a constant, by changing the amount of computation required to mine a block. On Ethereum, the block time is about 12 to 14 seconds \footnote{https://ethereum.org/en/developers/docs/blocks/\#block-time}. On Bitcoin, the block time is about 10 minutes. This limitation combined with a block size limit, creates a transaction rate and a blockchain size growth limit that is difficult to change without disrupting the security of the system.
\subsubsection*{Reorganization}
@@ -130,7 +130,7 @@ A minimum amount of mining power is required for the cryptocurrency to work. Wit
Rewards are of two kinds:
\begin{itemize}
\item \textbf{Coin generation} While mining a block, the miner creates money in it that he can use as he pleases. Bitcoins use this type of reward but to reach a constant amount of 21 million bitcoins, this reward decreases over time.
- \item \textbf{Transaction fee} Transactions may contain a tip for the miner to encourage mining. Miners will not mine transactions that cost them money and will mine the most profitable transaction first. Transaction fees are then market-based values, the more transactions that are waiting to be mined, the higher the fee you have to pay be in the next block. When a transaction is sent with a fee too small, it may not be mined in a timely fashion. Since transaction fees are unpredictable, transactions sometimes end being stuck for a long time.
+ \item \textbf{Transaction fee} Transactions may contain a tip for the miner to encourage mining. Miners will not mine transactions that cost them money and will mine the most profitable transaction first. Transaction fees are then market-based values, the more transactions that are waiting to be mined, the higher the fee you have to pay to be in the next block. When a transaction is sent with a fee too small, it may not be mined in a timely fashion. Since transaction fees are unpredictable, transactions sometimes end being stuck for a long time.
\end{itemize}
\subsection{Blockchain-based cryptocurrencies limitations}
@@ -264,7 +264,7 @@ Incoming transaction metadata contains a reserve public key, which is a 32B hash
\subsubsection*{Outgoing transaction}
-Outgoing transactions can be of two types credit or bounce. Credit metadata contains the wire transfer ID which is a 32B hash and the exchange base URL which is of variable size and encoded using uri-packing (Section \ref{uri-packing}). Bounce metadata contains the bounced transaction ID which is implementation-dependent but is 32B for Bitcoin and Ethereum. A prepended versioning byte differentiates the two types, 0 being a credit and 254 a bounce.
+Outgoing transactions can be of two types: credit or bounce. Credit metadata contains the wire transfer ID which is a 32B hash and the exchange base URL which is of variable size and encoded using uri-packing (Section \ref{uri-packing}). Bounce metadata contains the bounced transaction ID which is implementation-dependent but is 32B for Bitcoin and Ethereum. A prepended versioning byte differentiates the two types, 0 being a credit and 254 a bounce.
\begin{figure}[h]
@@ -286,15 +286,15 @@ Outgoing transactions can be of two types credit or bounce. Credit metadata cont
There are many documented ways to encode metadata in a bitcoin transaction \cite{bartoletti2019journey}. In the early days of this cryptocurrency, users abused the transaction format to store metadata, and some of these techniques result in ecosystem pollution. For example, bitcoin clients keep a list of all addresses that currently have money to spend (UTXO), with fake addresses wasting space there indefinitely. To allow storage of a reasonable amount of metadata without polluting the blockchain, a new opcode script OP\_RETURN was created, allowing up to 80B of storage per transaction.
-Debits are performed from code using OP\_RETURN to store metadata, but credits are done from common wallet clients, and they do not yet support custom metadata. We had to find another format using fake addresses.
+Debits are performed from our code using OP\_RETURN to store metadata, but credits are done from common wallet clients, and they do not yet support custom metadata. We had to find another format using fake addresses.
-We use the latest address type, segwit addresses, which can contain 20B of chosen data. The reserve pub key being 32B, we need two addresses. Therefore, we use two fake addresses consisting of the two key halves prepended with the same random pattern, except for the first bit, which must be 0 for the first half and 1 for the second. We then send a single transaction with three addresses as recipients.
+We use the latest address type, segwit addresses \cite{BIP173}, where we can embed 20B of chosen data. Since the reserve pub key is a 32B hash, we need two addresses. Therefore, we use two fake addresses each containing one half of the key prepended by a common random prefix, except for the first bit, which must be 0 for the first half and 1 for the second. We then send a single transaction with three addresses (the exchange address and the two fake) as recipients.
\begin{figure}[h]
\centering
\begin{tikzpicture}
- \draw[dotted,thick] (-6.4,1.13) -- (-6.4,0.185);
- \draw[dotted,thick] (-5.055,1.13) -- (4.23,0.185);
+ \draw[dotted,thick] (-6.33,1.13) -- (-6.33,0.185);
+ \draw[dotted,thick] (-5,1.13) -- (4.3,0.185);
\node {
\begin{bytefield}[rightcurly=., rightcurlyspace=0pt]{32}
\bitheader{0,3,4,19} \\
@@ -303,11 +303,11 @@ We use the latest address type, segwit addresses, which can contain 20B of chose
\end{rightwordgroup} \\ \\
\bitheader{0,1,31} \\
\begin{rightwordgroup}{First ID}
- \bitbox{1}{\tiny 0} & \bitbox{31}{Random ID}
+ \bitbox{1}{\tiny 0} & \bitbox{31}{Common random prefix}
\end{rightwordgroup} \\
\bitbox[]{32}{or} \\
\begin{rightwordgroup}{Second ID}
- \bitbox{1}{\tiny 1} & \bitbox{31}{Random ID}
+ \bitbox{1}{\tiny 1} & \bitbox{31}{Common random prefix}
\end{rightwordgroup}
\end{bytefield}
};
@@ -315,15 +315,15 @@ We use the latest address type, segwit addresses, which can contain 20B of chose
\caption{Outgoing metadata format}
\end{figure}
-Having a common random ID allows us to distinguish real addresses from fake ones. The first bit then allows us to rearrange the two halves, the order of the addresses being randomized on purpose by the clients to improve privacy.
+Having a common random prefix allows us to distinguish real addresses from fake ones, since it is very unlikely that two addresses share the same 32 bits. Since the Bitcoin client randomizes the order of the addresses for privacy reasons, the first bit allows us to distinguish the first half of the key from the second.
\subsection{Ethereum}
-Ethereum is designed around the concept of smart contracts. Logging inside a smart contract is the recommended way to add metadata, but it is expensive (additional storage and execution costs) and adds an avoidable attack surface. We chose to use the transaction field typically used to call smart contracts to store our raw metadata.
+Ethereum is designed around the concept of smart contracts. Logging inside a smart contract is the recommended way to add metadata\footnote{https://ethereum.org/en/developers/docs/smart-contracts/anatomy/\#events-and-logs}, but it is expensive (additional storage and execution costs) and adds an avoidable attack surface. We chose to use the transaction field typically used to call smart contracts to store our raw metadata.
\subsection{Friendly behaviour on format error}
-When we receive a transaction without any metadata or with an incompatible format (bogus wallet), we want to return the money to its owner (bounce). However, this is dangerous because we have created a potential attack loophole as anyone can now make Depolymerizer do a transaction, by sending a malformed transaction. Depolymerizer takes a bounce fee to make a potential \ac{DOS} attack too costly and charges the recipient the transaction fee to ensure it can not lose money on a bounce.
+When we receive a transaction without any metadata or with an incompatible format (bogus wallet), we want to return the money to its owner (bounce). However, this can be dangerous because it creates a potential attack loophole as anyone can now make Depolymerizer do a transaction, by sending a malformed transaction. Depolymerizer takes a bounce fee to make a potential \ac{DOS} attack too costly. There is another issue, making a transaction has a cost, and if the transaction fee is higher than our bounce fee, malicious bounces could bankrupt us. We also need to charge the recipient the transaction fee to ensure we never lose money on a bounce.
\clearpage
@@ -331,7 +331,7 @@ When we receive a transaction without any metadata or with an incompatible forma
Each cryptocurrency uses a different \ac{DLT} with its own format and rules, which evolve over time. We do not want to manage the \ac{DLT} logic ourselves, nor do we want to rely on third-party dependencies to implement their support properly and be maintained. The simplest solution is to rely on the official clients and communicate with them via \ac{RPC}.
-\begin{figure}
+\begin{figure}[h]
\begin{center}
\input{figures/depolymerizer_arch.tex}
\end{center}
@@ -364,7 +364,7 @@ During a \ac{DLT} reconciliation, we first list all new transactions and any tra
\subsubsection*{Reconciliation inconsistency}
-When we issue a transaction (debit or bounce), it is possible for the database or \ac{DLT} request to fail. Since a \ac{DLT} request error does not mean that the cryptocurrency transaction was not successful, and since the database may not record a successful transaction, it is possible to have an inconsistency between the DLT and the database where a successful transaction is not recorded as such. This is very problematic because we must perform each transaction once.
+When we issue a transaction (debit or bounce), it is possible for the database or \ac{DLT} \ac{RPC} request to fail. Since a \ac{DLT} \ac{RPC} request error does not mean that the cryptocurrency transaction was not successful, and since the database may not record a successful transaction, it is possible to have an inconsistency between the DLT and the database where a successful transaction is not recorded as such. This is very problematic because we must perform each transaction only once.
This is also problematic because, even if we used a status machine state in the database to detect this inconsistency, the only way to resolve it is to make another \ac{DLT} reconciliation, which is slow and does not play well with database locking.
@@ -378,13 +378,13 @@ Since we know that blockchain-based cryptocurrencies have low throughput, we do
The Taler amount format comes from RFC 8905 \cite{RFC8905}. It allows up to $2^{53}$ unit and 8 decimal digits. This format is perfectly suited for Bitcoin where the maximal amount is 21 million bitcoins and the minimum amount is the satoshi, one satoshi being worth $10^{8}$ bitcoin. However, the minimum amount of Ethereum is the wei, with one ether being worth $10^{18}$ wei. The amount of ether in circulation continues to grow without a cap, with over 119,000,000 ether in circulation at the time of writing those lines. Therefore, it is not possible to represent all Ethereum amounts with the current format.
-A standard Ethereum transaction requires 21 000 units of gas\footnote{https://ethereum.org/en/developers/docs/gas/\#post-london}. The average gas price is currently around 30 Gwei. Therefore, a standard transaction cost about $63.10^{18}$ wei in transaction fees. Since the transaction fee is so high, even if we truncate Ethereum value to $10^{-8}$ eth ($10^{10}$ wei), we can still represent any amount you can send whiteout losing money on the transaction fee.
+A standard Ethereum transaction requires 21 000 units of gas\footnote{https://ethereum.org/en/developers/docs/gas/\#post-london}. The average gas price is currently around 30 Gwei. Therefore, a standard transaction cost about $63.10^{18}$ wei in transaction fees. Since the transaction fee is so high, even if we truncate Ethereum value to $10^{-8}$ eth ($10^{10}$ wei), we can still represent any amount you can send without losing money on the transaction fee. In Depolymerizer, all Ethereum amounts are truncated as such.
\subsection*{Replaceable bitcoin transaction}
When some merchants wanted to allow instant payments with Bitcoin, they chose to consider a transaction final when it is announced. Although wrong, this choice works most of the time because many nodes do not accept conflicting transactions in their mempool, making it difficult to replace or cancel a transaction that has already been announced.
-This becomes problematic when you want to make a legitimate replacement, to unstuck a transaction by increasing its transaction fee for example. At the same time, it is always dangerous to give an easy way to attackers and scammers to change the content of a pending transaction.
+This becomes problematic when you want to make a legitimate replacement, to unstuck a transaction by increasing its transaction fee for example. At the same time, it is dangerous to give an easy way to attackers and scammers to change the content of announced transaction.
We use the solution has been adopted in \ac{BIP} 125 \cite{BIP125}, adding the possibility to encode the replaceability of a bitcoin transaction at its creation. It can thus be replaced by a new transaction within certain rules: you cannot send less money to existing recipients, and you must pay a replacement fee as a countermeasure to a \ac{DOS} attack.
@@ -413,10 +413,7 @@ We would normally encode the URL using ASCII, but we knew only a few ASCII chara
\subsection*{5 or 11 encoding}
-Our idea is to encode the most commonly used characters using five bits, and the
-remaining characters using eleven bits. As an ASCII character is seven bits and are commonly encoded using height,
-we gain on size if more than half of the characters composing the URI are
-encodable using less bits (Table~\ref{table:uri-packing}). You can find the detailed encoding table in appending \ref{5-11}.
+Our idea is to encode the most commonly used characters using five bits, and the remaining characters using eleven bits. As ASCII characters are seven bits wide and are commonly encoded using height, we gain on size if more than half of the characters composing the URI are encodable using fewer bits (Table~\ref{table:uri-packing}). You can find the detailed encoding table in appending \ref{5-11}.
\begin{table}[h]
\centering
@@ -465,7 +462,7 @@ Then we chose an aggressive memory budget of 4kB, as all request bodies should b
% Move testing to its own section
-The Taler exchange has a taler-exchange-wire-gateway-client CLI that allowed me to test that my implementation not only conforms to the \ac{API} documentation but also with how the official client handles it. I found confusion in the documentation where it was specified that timestamp should consist of time in milliseconds in epoch, but the client will reject timestamps that are not rounded to second.
+The Taler exchange has a taler-exchange-wire-gateway-client CLI that allowed me to test that my implementation not only conforms to the \ac{API} documentation but also with how the official client handles it. I found confusion in the documentation where it was specified that timestamp should consist of time in milliseconds since epoch, but the client will reject timestamps that are not rounded to second.
\clearpage
@@ -475,16 +472,20 @@ The Taler exchange has a taler-exchange-wire-gateway-client CLI that allowed me
We have shown that is it possible to use Bitcoin and Ethereum \ac{DLT} as a settlement layer for GNU Taler enabling payment with blockchain-based cryptocurrencies using Depolymerization. Depolymerization act as a middleware between Taler exchange and a \ac{DLT} mitigating their inconsistency especially chain reorganization and stuck transactions.
+In this project, we have not addressed the legal challenges of running GNU Taler with Depolymerization. In some countries, the use of cryptocurrencies is prohibited or restricted, and in most countries, payment systems are regulated and may require a licence. We therefore advise against deploying it without checking that you are authorized to do so.
+
+Depolymerization has many attractive features for cryptocurrency users at one cost, the centralization of trust in the exchange. This problem is partially solved with the use of auditors that federate trust. In contrast, blockchain-based cryptocurrencies are generally public, with their entire state subject to public scrutiny. For GNU Taler to convince users who expect this level of openness, we would have to find a way to make enough information public that any client could do the auditors' job.
+
+
\subsection*{Future work}
\subsubsection*{Paying for reorganization loss}
-We could allow the administrator to pay for the missing transactions to resume operations, as sometimes the loss caused by the non-functioning depolymerizer exceeds the cost of the missing transactions.
+When a reorganization removes a confirmed credit indefinitely (conflicting transaction) we suspend operation indefinitely. We could allow exchange administrators to pay for the missing transactions to resume operations, as sometimes the loss caused by the non-functioning Depolymerizer exceeds the cost of the missing transactions.
\subsubsection*{Smarter analysis}
-There is an opportunity for a more intelligent analysis of network behaviours to adjust the confirmation delay to an estimated risk factor. For example, a brute force attack on a DLT is very expensive, when we receive an important credit, we could apply a longer delay to it to make attacks harder to sustain.
-
+More intelligent analysis of network behaviors can be performed to tailor the confirmation time to an estimated risk factor. Brute force attacks on a DLT are very expensive, and one can expect that attackers have an economic incentive to attack through double spending for example. When we receive a large credit or when a considerable amount of currency is exchanged on the network, this can be the preparation for such attacks. We could monitor these indicators, and we could apply a longer temporary delay to make the attacks harder to sustain.
\clearpage
