Race OTV

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.


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

d_{i,x}(t):= Speed_x * {(t- st_{i,x})}


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

x_{win}:=argmax\{x: d_{i,x}(t)\}

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”

\omega_{i,x}(t) = \frac{d_{i,x}(t)}{max\{x \in X_{i,n}(t): d_{i,x}(t)\}},

where X_{i,n}(t) is the conflict set known to node i at time t.


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,

\omega_{i,x}(t) \to \frac{Speed_x}{Speed_{x_{win}}}.

In addition, we introduce a “time modifier”:

\tau_{i,x}(t) = \min\{ \frac{t- st_{i,x}}{\delta}, 1\},

for some \delta >0.

We now can define the modified Approval Weight \widetilde{AW}_{i,x}(t):

\widetilde{AW}_{i,x}(t) = (1 - (1- \omega_{i,x}(t)) * \tau_{i,x}(t)) * {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

\xi_{i}(t) := \left\{ \begin{array}{cc} 1 & \mbox{ if } gap_i(t) > 0.5, \cr 2 gap_i(t) &\mbox{ if } gap_i(t) \le 0.5. \end{array} \right.

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

\widehat{AW}_{i,x}(t_1):= \widetilde{AW}_{i,x}(t_1)

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}

\widehat{AW}_{i,x_{lead}}(t_j) = \xi_{i}(t_{j-1}) * (1- (1- \omega_{i,x_{lead}}(t_j)) * \tau_{i,x_{lead}}(t_j)) * {AW}_{i,x_{lead}}(t_j),

and for all other transactions x\neq x_{lead}:

\widehat{AW}_{i,x}(t_j) = (1- \xi_{i}(t_{j-1}) )* (1- (1-\omega_{i,x}(t_j)) * \tau_{i,x}(t_j)) * {AW}_{i,x}(t_j),

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.

this distance will become negative as t increases?

Can the attacker mine PoWs of his 100 conflicts to be very close to each other, so that T may become really large (due to local differences in solidification times)?

yes it should be the other way round, thanks

yes, he could, but this can be made expensive, as PoW contains also the parents, this may be an effect that we can control.

The conflict set is dynamic and the attacker can keep mining conflicts with higher speeds that would eventually outweigh the former favorites? How does that combine with O3 above?

Yes, he can, But If we assume that he has a bounded ressource of PoW, he can only send a finite number of conflicts with increasing speed/pow

He can keep mining faster transactions but for a transaction to be able to catch up with the current leader it needs to have a PoW that is at least reasonably faster.

In addition, the new transaction will start with a traveled distance of 0 while the others already had a head start which means that it will take some time to pass the already racing transactions. In addition a new transaction might be able to catch up regarding its weight modifier but it will start with an approval weight of 0.

Nobody would attach to this conflict as its resulting AW will be close to 0. If the attacker switches to this new faster Transaction to give it some AW then he implicitly removes his influence from the other conflicts which would increase their chance for tipping.

It is also important to note that creating Transactions with a higher PoW has exponential cost while the speed benefits only rise linear, so he can only do that for some time.

well, he can also premine the conflicts (and then even release them gradually, if needed), since we allow referencing rather old msgs

OK, so, in the limit (as t\to\infty), the (new) approval weight is anyway proportional to the speed, correct? What if I (as an attacker with, say, 1% voting power) issue two conflicts with 0.001 speed and watch them resolved; then, I issue another one with 0.999 speed and give it the necessary weight myself?

1 Like

If they are resolved then one will already be 0.5 AW ahead and the modifiers will be removed from the equasion.

wait, I thought that, for the purposes of this discussion, “PoW” was just something uniformly random \in (0,1)? If not, which probability distribution would it have then?

0…0 is mapped to speed 1
1…1 is mapped to speed 0.
The more leading zeros the higher the speed

Ah, I see. But I’m not convinced that this removal cannot be tricked (some nodes remove them, others don’t just barely, and then the attacker weighs in).

This would help against mining high-speed txs, but, on the other hand, would facilitate mining conflicts with very close speeds (since the distribution would be more concentrated).

No wait I think that is not correct.

A hash of

00A… has 2,07 POW
00B… has 2,125 POW
000A… has 3,07 POW

and so on.

For this reason I wrote \Phi since I don t know atm which could be a good function for this tradeoff.

the hope/idea was that the smoothness of this factors might limited this effect. So there is no hard on-off of this modifier. However, at the end of the day a node needs to take a binary decision…
In any case “attacker weighing” in becomes more and more expensive, due to the distance of the farthest travelled transaction.

Also I believe that the “gap modifier” (definition of \xi and how it enters into \widehat{AW}) is not the best way to do it, probably only the first step in an iteration of improvements

Yeah I think it should also be a smooth transition like the time modifier.

Yeah, but it’s unclear if there is a “sweet spot” at all. I would try to choose some natural candidates, and estimate how large is T (from O3) that the attacker can achieve (with pre-mining) under natural conditions (e.g., discrepancies in st_{i,x} of the order of a few seconds for different nodes).