Matching in the Tuplespace- The Core issue:
Because the data on the channel is not ordered (we explictly shuffle) and we look for the first data that matches the pattern, and we want to charge for every action we take in the system.
Tuplespace contents are non-deterministic when a match is attempted. Costs are non-deterministic depending on the number of failed matches. Costs to execute a given contract from validator to validator will vary.
{code}
for (y1 <- x){ P} | for (y2 <- x){ Q} | x!(d1) | x!(d2)
{code}
* d1 matches y1
*
d2 matches y2
Charging for failed matches, given the shuffle will result in non-deterministic costs.
- It's the fact that when you go to produce on x, what data happens to be on y affects your cost if there is a join waiting between x and y. There isn't anything to force the order.
We checked the following things along the way, but we ultimately succeeded. - Issue is the cost of failure. Not the cost of success.
Not charging for failure becomes a source of DoS. Can we come up with a skeleton that is deterministic for failure, but non-deterministic for success.
DoS vectors:
* Put in a bunch of filters for someone that wants data that are nonsense, and if it is on a channel where you are allowing people to write whatever kinds of filter they want.
* Make the cost of failure constant (may not work)
* Because of the current relation rholang <-> rpsace, and how the match is done inside RSpace, we have to use available phloLimit for each and every (bind pattern, data candidate) pair. Meaning that if I have 100 phlos left and I need to do a consume on join then each pattern will get all 100 phlos. This means that it's possible to construct a rholang program that would go into the rspace with n phlos left and each match cost n-1 phlos. In the end, once we leave RSpace we will fail this deploy but the attacker might have just expolited the node
Solutions:
- Order the matches by complexity. Sort the potential productions, sort the potential consumptions.
Sort the input data at the time of insertion. Data in a channel is in an order at insertion.
Construct the smallest piece of Rholang that demonstrates the problem
Different threads may run in different orders:
- Matches on different parts of the join
{code}
for (y <- x) {P} | for (y <- x; b <- a) { Q } | x!(0) | a!(1)
{code}
Solution:
Order terms when they land in the tuplespace
* non-joins before joins
* Simple before complicated
Cost accounting in the Replay RSpace relating to the matcher