Race OTV
We describe a version of OTV (proposed by Hans) that is robust against “metastability-attacks”. It does not contain a metastability breaking mechanism but makes these attacks expensive.
To every transaction x there is an associated PoW, PoW_x \in \{0, 1 \}^{256}. Every value in \{0, 1 \}^{256} is naturally mapped to a value in (0,1). We define the speed of a transaction x as
Speed_x = \Phi(PoW_x),
where \Phi(s) is a strictly decreasing function from (0,1) \mapsto (0,1). For instance, we could use \Phi(s)=1-s.
Observations:
O1. the higher the PoW the higher the speed of a transaction.
O2. no two transactions have the same PoW (this holds with very high probability).
For every node i \in \mathcal{N} there is a solidification (or arrival, booking ?) time st_{i,x} of a transaction x. We also define the travelled distance of a transaction x seen by node i at (local) time t=t_i as
Observation:
O3. For any given set of conflicting transactions X and st_{i,x}, i\in \mathcal{N}, x\in X there is a time T such that
does not depend on i and is constant (in t) for all t>T. In other words, after some time T all nodes have the same perception of the farthest travelled transaction. And this winner x_{win} will never change again.
We now have to add the approval weights. So we suppose that OTV is going on and nodes add their messages (or votes) to the “heaviest” branch. The approval weight AW_{i,x}(t) at time t of a transaction x seen by a node i will be weighted by the travelled distance of the transaction d_{i,x}(t).
One way to this is to define the “weight modifier”
where X_{i,n}(t) is the conflict set known to node i at time t.
Observation
O4. For any given set of conflicting transactions X and set of solidification times \{ st_{i,x}: i\in \mathcal{N}, x\in X\}, we have that there exists a unique x_{win}\in X such that, as t \to \infty,
In addition, we introduce a “time modifier”:
for some \delta >0.
We now can define the modified Approval Weight \widetilde{AW}_{i,x}(t):
where {AW}_{i,x}(t) is the standard Approval Weight.
The time modifier serves that for small time the original AW plays the main role, while if the conflicts goes on for a longer time “weight modifier” obtains a larger weight. It might well be that the time modifier is not needed, but may offer some degree of freedom for better control.
We see that as long as the “fastest” transaction has some AW, this fastest transaction will eventually have the highest modified AW. (All other transactions’ modified AWs go to 0). As honest nodes can never be sure if a faster conflicting transaction is issued at a later point, we need a finality criterion.
To this end we consider for every node the ordered statistic (ordered decreasingly) of (\widehat{AW}_{i,x}(t), x \in X_{i,n}) denoted by Y=(Y_1, Y_2, \ldots). (\widehat{AW} is defined below, for the moment you can take \widetilde{AW}) We denote by
x_{i,lead}(t) the transaction with the highest modified AW and by gap_i(t):=Y_1-Y_2 the gap between the leader and its pursuers.
We define
This is just an example, other smooth versions of \xi could be better options.
We now obtain the final formula for the AW \widehat{AW}. Denote by t_1, t_2, \ldots the times when a given node updates the AWs. We set
Now inductively, for j>1 let x_{lead}=x_{i,lead}(t_{j-1}) be the leader at time t_{j-1} of \widehat{AW}, and define for
x= x_{lead}
and for all other transactions x\neq x_{lead}:
Let us see how this “resolves” two previously discussed attack scenarios.
Example 1. An attacker issues two conflicting transactions and try to keep them in a metastable situation. In the new model, the fastest transaction will have its \omega weight converging to 1, this will happen for all nodes. To compensate this effect an attacker needs more and more AW and finally will loose the control.
Example 2. An attacker issues a sequence of conflicts, and tries to prevent that one particular transaction will win. Observe that the fact that the travelled is essential implies that new transactions need some time to build some AW. To make the attack successfull an attacker has to issue faster and faster transactions, because only these will have a chance to finally become the next winner. But faster transaction means more PoW and more time between consecutively issued transactions. This implies that an attacker can perform this attack only to some point and will run out of hashing power.