In the following, we describe a simple idea that aims at providing “banking-style finality” in IOTA.
Constructing checkpoints on the Tangle in a decentralized way (dashed lines indicate indirect approval). Here, \ell=2.
We assume that there is a sequence (X_k,k\geq 1) of random numbers (say, uniformly distributed in [0,1]), produced in a decentralized way. As in the FPC paper, we do not need a lot from this sequence, we only need that a majority of nodes (not necessarily everybody!) agree on most of them. We assume that X_k appears (approximately) at time kt_0, where t_0>0 is a parameter. The goal now is that the nodes agree on a sequence of checkpoints (m_k,k\geq 1), such that the k th checkpoint m_k appears roughly at time (k-\frac{1}{2})t_0.
Let \ell\in\{1,2,3,\ldots\} and \gamma,\delta\in (0,\infty) be parameters (typically, \gamma should be large and \delta should be small). Let us also denote by t(v) the timestamp of the transaction v (or, say, the central point of the timestamp interval). The candidate for the k th checkpoint is chosen in the following way (among strongly liked transactions):
- it must (indirectly) approve m_{k-\ell};
- the score
S_k(v) = |X_k - \mathtt{hash}(v)| \times
\exp\big(\gamma|t(v)-(k-\tfrac{1}{2})t_0-\delta X_k|\big)
is minimized on v=m_k (the term \delta X_k in the above expression is needed to make the target time less predictable).
(Of course, one may consider other candidates for the score function.) The nodes then vote (using one of our voting protocols) on the checkpoint candidates; since, normally, most of them will agree on a specific candidate, this candidate would normally win.
The role of the parameter \ell is to allow more frequent checkpoints; requiring approval of the
previous checkpoint may be too restrictive (maybe not; we can just take \ell=1 for the start).
Why do we need decentralized randomness here? This is to avoid attacks of the type “let me create too many checkpoint candidates, and let them fight to decide which one is better”; or “let me create a good checkpoint candidate at the last moment, so that some node will like it already, and some not yet”. When the attacker does not yet know the next random number, he is unable to create (probable) checkpoint candidates, since he does not yet know the exact decision rule.
Also, an attacker can issue a “better” checkpoint candidate after time kt_0 (so knowing X_k already) but with the timestamp close to (k-\tfrac{1}{2})t_0+\delta X_k (which therefore would be “old”). The nodes won’t vote for it as a checkpoint (because that transaction won’t become strongly liked immediately), but maybe it is a good idea to dislike it anyway, since it is clearly an offensive behavior. This way, those ``fake checkpoints’’ would become orphaned and won’t confuse the newcomers.
Link to overleaf: Making decentralized checkpoints with FPC and DRNG
Question:
The timestamp is the subjective arrival timestamp (which makes less sense because it will cause variance in score)? Or it is an objective signed timestamp that must adhere to certain bounds?
Or maybe it is a logical timestamp?
It’s an objective signed timestamp, of course (otherwise all nodes would choose different transactions as minimizers).
Does the equation somehow incentivize you to put a low or high timestamp?
Or it is unclear how to maximize your score with timestamps with the current equation?
The idea about using the DRNG is exactly that: make it unclear how to maximize your score.
How do we know, while voting on milestones that we are looking at the same set? We only want milestone candidates that are issued before the random number is released (otherwise a set of FPGAs can easily create a transaction with the highest score), so we need some sort of cutoff point. But any cutoff point will be subjective…
I suppose we could use voting to sort out the differences.
I have another question: how do we do binary voting on milestones? Traditionally, we have been voting 1 or 0 on whether or not to accept a particular time stamp.
For timestamps, we vote yes or no on each timestamp. Its fine if multiple transactions have the same time stamp as long as each one individually is valid.
For voting on conflicts, the FCoB rule for setting the initial opinion is set so that no two conflicts can will ever survive voting. This is possible, because we can reject both transactions.
Suppose there exists two transactions x and y which are have roughly equal support to be the next milestone. On the one hand, we need to a milestone, thus we need to say yes to one of them. On the other hand, we cannot choose both. However, if we vote individually on each one, FPC and CA could output “yes” on both of them.
Perhaps the solution is to vote to establish a list of milestone candidates, and then the candidate with the best score wins.
When maximizing the score, you use the timestamps; so it’s objective.
We didn’t yet decide if we will vote on timestamps at all; iirc, there were good arguments pro and contra.
This is really an unlikely outcome (since, to manipulate this, have to know the RN in advance). And …
… in any case, this would work indeed.
When maximizing the score, you use the timestamps; so it’s objective.
If the only thing that prevents the ability to maximize the score of a transaction is the timestamp, then we will need to vote on the timestamps to enforce them.
Moreover, if we vote to establish a list of candidate transactions seems very close in principal on just voting on time stamps. (The candidates for milestone number i effectively have time stamp i).
So what benefits do we have here of adding milestones with this method over just doing any ordering with time stamps? Do we just want milestones here to introduce finality?
No, we don’t necessarily need to vote on timestamps. Because if the timestamp is really off, then the grand majority of nodes will already consider it invalid and exclude from the list of candidates.
- The milestones are not so frequent so the attacker cannot trigger too many votes.
- As far as I remember, we needed them also for other stuff, like dealing with reattachments (within the approach “reattachments-are-not-conflicts”).
As far as I remember, we needed them also for other stuff, like dealing with reattachments (within the approach “reattachments-are-not-conflicts”).
Well we need some sort of generalized time stamps (whether or not time stamps, or milestones or something else) to deal with some of these issues.
No, we don’t necessarily need to vote on timestamps. Because if the timestamp is really off, then the grand majority of nodes will already consider it invalid and exclude from the list of candidates.
Ah I see. So another way of viewing this is that we are voting on timestamps, but we vote on several transactions at once by voting on a single milestone, so we dont need to vote on every transaction. This could work well for FPC.
However, this wouldnt work for CA. As I wrote in the “when to vote” document, you can only use CA to vote on objective criterion. But that is ok.
It may be that with the term |X_k−hash(v)| the tx hash may be mineable in such a way that txs can be prevented from becoming milestones by wrapping two txs around it: For any tx v that should be censored from becoming a milestone create 2 wrapping txs v_1 and v_2 with
|hash(v)-hash(v_1)|<|hash(v)-hash(v_2)|<\epsilon_h
t(v)-t(v_1)=t(v_2)-t(v)<\epsilon_t
where \epsilon_h and \epsilon_t are sufficiently small.
But I think using hash(hash(v)+X_k) for the distance term might solve this issue? I considered that X_k maps onto the interval that is produced by the hash function.
That would mean mining quite a lot of transactions, no?
Yes, this would probably work indeed.
If the adversary wants to set one of his tx as the checkpoint yes. however if - for whatever reason - the aim is to just prevent a specific “honest” tx from becoming a checkpoint than the above wrapping should be sufficient.
I am not sure I understand. Your score isnt affected by your approvers or your approvees, so what good is wrapping a transaction?
I had another thought: perhaps the score function should take in account the number of transactions between it and the last milestone or something.
If an attacker has 10% of the mana, then they will issue 10% of the transactions, and about 10% of the time, their transaction will be chosen as a milestone.
If they are free to put their milestones in a silly place, (say just approving just the last milestone), then this would be bad.
This is not related to approvers or approvees. This is a matter of issuing txs with a similar time stamp and similar hash in order to minimise the probability for an honest tx to have the lowest score. Using hash(X_k+hash(v)) makes your hash-space distance unpredictable.
Nevertheless, although it makes wrapping difficult, censoring is still possible by spaming txs with the same time stamp, because these tx would be spread randomly in the hash space and therefore whp will have a smaller score than the to-be-censored tx. But I don’t know if the latter brute-force actually poses any threat.