How to get "deep" values in javascript?

Question

I am currently building a project where the users can referr other persons. Now let's say I have a user who has only 2 referrals but those 2 also have another 2, then again 2 etc. and that for much more. Now I want to output those referrals/users and their users. To get a users referrals, the function getUser(uint _userId) is called. It returns some values and an array _referrals that contains the IDs of the users that specific user has referred. Now it's required to again call getUser for the 2 users until at one point it returns that a user has no referrals.

I currently am doing this via

struct User {
    mapping(uint => uint) directReferrals; // Referrals
    mapping(uint => uint) index; // ReferralId => ID in above
    uint directReferralsAmount;
}

User[] users;

function getUser(uint _userId) [...] public view returns(uint[] directReferrals) { [...] }

The problem is, that when for example a user has 100 levels of referrals (referrals of him, referrals of the referrals of him, etc.), it will call getUser (view only) 100 times (in the web interface through javascript and an ethereum node connection / MetaMask) which can result in a long waiting time.

Are there alternative ways of storing and getting of referrals? Or wouldn't 100 view-calls take that long?

What would be the best way to
1) Programm this in the solidity code and
2) Output this via javascript?
3) Is it possible to show those data in one page without a too long waiting time?

Answer 1

OK, basically, you have graph, where vertices are users and edges are references, and you need to find all vertices reachable from given vertex. This is well known problem that could be solved efficiently, i.e. in O(n) time, where n is the number of reachable vertices, like this:

function getAllReachable (v, getEdges) {
  var visited = new Set ();
  var result = [];
  for (var i = 0; v !== undefined; i++) {
    var edges = getEdges (v);
    for (var j = 0; j < edges.length; j++) {
      var edge = edges [j];
      if (!visited.has (edge)) {
        visited.add (edge);
        result.push (edge);
      }
    }
    v = result [i];
  }
  return result;
}

Now you need to implement getEdges that actually queries your smart contract. You may do something like this in Solidity:

struct User {
  uint [] referrals;
}

User [] private users;

function getReferrals (uint userID) public view returns (uint [] memory) {
  return users [userID].referrals;
}

And then something like this in Javascript:

var transitiveReferrals = getAllReachable (userID, myContract.methods.getReferrals);

Answer 2

Ok, apparently you have three problems.

The first one is the one you described (fetching ALL referrals from one user's tree of referrals); the second one is knowing if a given user is in that tree (without having to fetch the whole tree). You might need this eventually.

For the second problem, you could use Merkle Trees (and specially Merkle Pollards). Something in this direction: medium.com/@jgm.orinoco/understanding-merkle-pollards-1547fc7efaa

But the first problem actually demands that you fetch all descendants (you need to show them on screen). I believe you should have an off-chain system in order to optimize this. You could listen to referral events and update an off-chain database whenever an event is emitted. If something happens to your database, you can always rebuild it from the blockchain data.

The blockchain is still very young to be used as database, but MySQL would eat this problem for breakfast.

Ok, now the third problem? The one to rule them all, and even make the first two problems "obsolete"?

If you have 100 levels of referrals, and if each level has referred only two other users, you already have to show 2**100 names on screen. That's ~= 1,000,000,000,000,000,000,000,000,000,000 names. You don't want to do that, and MySQL will not help you here, either. Maybe you should reconsider your goals. If you have 7 levels of referral, as most schemes seem to use, you already have a lot on your plate.

I hope this helps you on your journey!

PS: That number is MUCH larger than the world's population, by the way. Maybe you should reconsider your expectations, too.

Answer 3

1) Programm this in the solidity code and

There could be many ways to implement that. I would take the mapping approach with the ethereum address.

address[] allUsers;

mapping(address => address[]) userReferal;

In allUsers I will store the address of all the users and for the referal of user I will map the address in userReferal with two more referal address.

While retrieving first I will get the length of allUsers and store it in a variable in the distributed application and run a loop according to that and access the address and reterive the referals.

2) Output this via javascript? 3) Is it possible to show those data in one page without a too long waiting time?

This will take time but to make it responsive you can use AngularJs and as the value is updated in array or any variable it will show the value on the page so you dont have to wait till all the data is fetched.