How can one node lwoer someone else’s score? Its parameters dont reference any other transaction?
The score is not lowered. you - as the adversary - just need to make sure you have a smaller score. I.e. the wrapping txs, need to be “placed” such that their score is lower than the one that should be censored.
Oh, I see what you mean. Its like taking a bet on a random integer 1 through 10. If I bet on 5 and 6, and you bet on 4 and 7, then I only have an 80% chance of being closest to the randomly selected integer. This is an interesting point!
I took some of the ideas we discussed above and wrote something which incorporated the voting on candidates. What do you guys think?
From simulations we know there is a small probability that some nodes may come rarely but occassionaly to a different opinion even in an honest setting in FPC. This probability increases, when there is a proportion of adversaries. Hence individual nodes may come to a different checkpoint and it is therefore necessary to clearly mark each checkpoint. Since we assume here that the majority of nodes come to the right conclusion the following should work:
A node keeps locally two lists of tips that are and are not in the trunk-future cone of the last milesone k, labeled C_k and \bar{C_k}, respectively. Trunk-future cone here means we only consider the trunk edges. The first tip is then selected from C_k, while the branch is selected from \bar{C_k} or {C_k}\cup\bar{C_k}. This is very similar to the approach in the Secure-and-swipe technique in “IOTA-based Directed Acyclic Graphs without Orphans” by Ferraro, King, and R. Shorten. However, here |C_k| grows exponentially. Also, since nodes do not need to easily give up on their belief on a particular checkpoint this seems difficult to attack with spam attacks as long as the majority of honest nodes agree on the same checkpoints …
Individual nodes that have chosen the wrong checkpoint will therefore, naturally learn about the correct one by simply observing the Tangle, at no additional message cost.
Ok, now I understand now why nodes dont have to to have the same list of candidates: the nodes use colored voting (voting on multiple options not just 1 and 0) in FPC to choose which milestone they like the best.
However to implement this, we would need to study how FPC behaves with colored voting. Indeed, if the honest nodes are divided up into several equal strength “factions” that initially support different transactions, it may be easier for an attacker then to dictate the outcome. Indeed, when voting on multiple options, extracomplications might arise.
Let me explain why. First, after the random number is revealed, a node can lie about the timestamp, and the mine a transaction with an optimal score. Thus, when deciding milestone k, there is a time t_k such that a node will not consider any transaction arriving after t_k for milestone k. Time t_k is sometime before the X_k is revealed.
Because the network is asynchronous, transactions issued around time t_k will be considered by some nodes, and not other nodes. And so we must understand if:
- These differences will naturally lead to several different “factions” of nodes who initially believe in different milestone candidates.
- If an attacker spams transactions on the boarder, they can further fragment node’s view of the tangle. In this manner, how well can the attacker proliferate factions?
I think colored voting is not necessary here and can be circumvented; for example in the following way: A node i proposes to vote on a list C_i of what it considers to be possible checkpoint candidates. Effectively the voting will then take place on some set C_\cup=\cup C_i of which some subset close to C_\cap = \cap C_i will survive with the status liked (or 1). As long as the voting protocol is safe all nodes should agree on the survivers and can choose the one with the e.g. lowest hash.
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.
After some thought I want to make my recent point more strong . FPC will not work on colored voting.
This leaves us with the latter modificiation. I.e. vote binary on every single candidate. And then after making everyone agree on the candidate list, choose the lowest Hash-distance.
I disagree. OK, the vanilla FPC is for binary voting, but it is not difficult to modify it for colored voting.
Interesting. How would that be done?
It’s common wisdom by now: finite-state voter models are usually similar to two-state voter models (okay, this sentence is an exageration since, iirc, they have also non-consensus invariant measures, but the consensus ones are still there and you can reason about them kinda using similar intuition).
In the specific case of the FPC, you treat other’s opinions as 1s if they agree with your particular choice and 0s otherwise. If you get “majority” of 0s, you see if among those there is an opinion that “prevails”. If there is one, you switch to it. If not, you adopt a special opinion called “nothing to choose” 
(You can even adopt a convention that if “nothing to choose” wins, this means that some pre-defined opinion k_0 has to be chosen; that’s an option, at least.)
What you describe sounds like random-majority-consensus on colors. My intuition says that in particular in the beginning phase when nodes have to decide on the “prevailing” colors the random threshold might be counter-productive or has no effect. Maybe this can be resolved by gradually introducing the random threshold (\beta=.5 \rightarrow \beta=.3) based on how close an opinion is to a super-majority but this might be attackable. In general if there are more states than nodes then the convergence times might become very large so it may well be that colored voting only works if there is a guarantee that the amount of colors is small.
It sounds like if CA can make a super-majority with colored voting in a byzantine environment so does this, albeit at the cost of potentially much slower convergence times (FPC cannot come to agreement locally because there is no locality). However, the former is not clear.
What will happen already on the first step (where the threshold is nonrandom), is that it will become “favorite color” vs. “nothing to choose” for essentially all nodes (or “nothing to choose” will just win in case the initial votes are more or less evenly distributed). In view of this, I don’t agree with you remark that
Isnt all nodes adopting “nothing to choose” a problem? Would we skip issuing a check point?
Skipping checkpoints very occasionally doesn’t seem to be a problem (as long as there is consensus on the fact that it was skipped). Now, the very idea of the checkpoint selection protocol (with RNs) is that, with high probability, there will be a favorite candidate from the beginning.
Btw, on the first step, you can even define this “prevails” more freely; for example, choose it if it has at least 3x more votes than the next one (in the decreasing order). This way, even if there is initially a popular opinion that doesn’t have supermajority but the others are very split, that popular opinion will still win.
In general, it is clear that “inpopular” opinions will be eliminated very quickly (mostly on the 1st step), regardless of the number of them.
This is the idea we developed in dRNG group during the discussion with @sebastian.mueller and @andreas.penzkofer on committee selection. We use the fact that all of the transactions are going to have timestamps. Then you can use the following to find checkpoints:
Assume that we want to have a checkpoint every t_0 units of time and ‘‘reasonable’’ bound on network delay is \Delta. Assume that at the time n \cdot t_0 random beacon released random number r_n. Then the checkpoint is the first transaction with a timestamp smaller than
n\cdot t_n - \Delta - r_n
Then assuming that \Delta is big enough that no honest node at the time n \cdot t_0 will accept the transaction with a timestamp smaller than n\cdot t_n - \Delta we have decentralized checkpoints.
1 Like