3

For a project I model a tree with each node having some data assosiated. A property of that tree is that under some circumstances a node can get deleted, which automatically makes the whole subtree it represents useless and it could be deleted as well.

Normally this trees are small, but occasionaly their are larger trees and especially could an adversarie force a large tree. Currently the tree nodes are represented as structs in a mapping from uint -> treeNode, the struct contains beside the data uints representing its children.

My problem now is, that when I recursively delete a whole subtree I get gas problems really fast, because the refound is only returned at the end and the biggest posible refound is half of the used gas.

As a solution I only delete one node and not its children and make sure that no two nodes get the same mapping key ever.

But I really do not like to leave that many garbage on the blockchain, but the way it is designed (max half used refound) I most of the time pay for removing the nodes instead of getting something back and for the really rare (except an advisory is involved) big tree branches I run Out Of Gas (gas limit), this thus is not an option because the adversary could render the contract useless.

Is their a way to get rid of the garbage in the blockchain, with out making the user paying huge fees and giving an adversary an attack opertunity?

2

(All of these examples assume some way of marking a node as "dead" without immediately deleting it.)

One possibility is to, during every "normal" transaction, delete just enough nodes to max out the refund. Thus, ordinary use will slowly remove bloat from the state. You would have to calculate the amount, and it's probably not going to be exact (even if it were, there's a future possibility gas prices will change.)

Another possibility is the same, except that you use the frontend to calculate which nodes to delete. This might slightly complicate your code, but it would be more efficient.

Yet another (and this may be simplest) is to keep track of dead nodes on a list, then reuse them. Specifically, when you no longer need a node, push it onto the dead list. When you need a new node, first check the dead list, then try to overwrite it. You can handle now-orphaned children by pushing them on the dead list, too. Essentially, you recursively delete over time, rather than all at once.

  • Thanks, the last was easy to implement and solves the problem, I probably will try out one of the first two, to see how they compare gas wise. – Markus Knecht Feb 17 '17 at 21:39
2

Any iterative process will imply a limit to tree width. Similarly, any recursive process will imply a limit to tree depth. Most algos will involve a little bit of both. If such logic is included in the contract then it will be hard to estimate how large the tree can be before trouble starts. But, we'll be sure that transaction cost increases with scale. At the block gas limit and/or stack limit, important processes won't work at all.

It's also worth noting that there really isn't any way to delete information from the blockchain, so I wouldn't dwell on the actual destruction of leaves and branches that are pruned away. It's sufficient (and about the same) to logically remove them.

In the code below, the nodes include some simple structures:

  1. Each node has one parent.
  2. Each node has an unordered list of the children.

We can add new nodes wherever they belong. A client can obtain the length of the children list and iterate over the children. That makes exploring the tree possible.

Delete is a little tricky.

The basic principle is a pruned branch has no parent. We ignore what's below the pruned branch, since a top-down exploration won't lead to pruned nodes.

To facilitate deletion, the children get an additional pointer; their position in the list of children in the parent. We note that as we add nodes.

To delete a node,

  1. Move the parents last child to the row to delete in the children list.
  2. Update the parent position pointer in the child that moved.
  3. Shorten the children list by one.

So, if the parent has children:

  • A, B, C, D, E, F

and we want to delete D.

  • Move F to the 4th position, where D is.

We make it easy to locate D's position with another pointer:

In D:

  • parent is X
  • parentIndex is 3 (position in the parent's list)

Having done so, parent's list reads:

  • A, B, C, F, E, F

Make the list one row shorter with --.

  • Don't forget to update F's parentIndex pointer. Was 5. Now 3, because it moved.
  • Zero out the deleted nodes' parent pointers.

Any node can be seen to be attached to the root by following it's ancestry all the way to the tree root. It should be an unbroken chain of parents. If a 0 parent is encountered before the treeRoot, then the node lives in a pruned branch. Logically deleted.

I've included a recursive process to show the simplicity of the logic, but it's better to do that process client-side because it's recursive.

A dishonest client may be able to muck about in pruned branches when the recursive check is absent. If the values set are of any consequence, then it's better to sweep up "pending" changes with a trusted client using a restricted "onlyOwner" process. A client can crawl wide and deep, up and down without ever running out of gas because it will be calling tiny functions as it goes. The contract functions that change state should always zero out pending so state integrity is maintained at each atomic step.

An honest front-end will be able to provide dependable tree navigation at any scale.

Quickly sketched out with minimal testing. Hope it helps:

pragma solidity ^0.4.6;

contract ObjectTree {

bytes32 public treeRoot;

struct NodeStruct {
    bytes32 parent; // the id of the parent node
    uint parentIndex; // the position of this node in the Parent's children list
    bytes32[] children; // unordered list of children below this node
    // add useful node properties here
}

mapping(bytes32 => NodeStruct) nodeStructs;

event LogNewNode(bytes32 nodeId, bytes32 parentId);
event LogDelNode(bytes32 nodeId);

function ObjectTree() {
    treeRoot = newNode(0);
}

function newNode(bytes32 parent) 
    public
    returns(bytes32 newNodeId)
{
    // very tempting to call isActiveNode(parent) here
    // to prevent insertion in pruned branches. Not scalable. 

    newNodeId = sha3(parent, msg.sender, block.number);
    NodeStruct memory node;
    node.parent = parent;
    if(parent>0) {
        node.parentIndex = registerChild(parent,newNodeId);
    }
    nodeStructs[newNodeId] = node;
    LogNewNode(newNodeId, parent);
    return newNodeId;
}

function registerChild(bytes32 parentId, bytes32 childId)
    private
    returns(uint index)
{
    return nodeStructs[parentId].children.push(childId) - 1;
}

// to remove a node, 
// we'll zero the parent and parent index.
// we'll remove the node from the parent's children list
// To do that, we'll 
// 1. move the list child into the row to delete
// 2. update the index of the node that moved
// 3. shorten the parent's children list by one

function pruneBranch(bytes32 nodeId)
    public
    returns(bool success)
{
    bytes32 parent = nodeStructs[nodeId].parent;
    uint rowToDelete = nodeStructs[nodeId].parentIndex;
    uint rowToMove = nodeStructs[parent].children.length-1; // last child in the list
    // move the last child into the row to delete
    nodeStructs[parent].children[rowToDelete] = nodeStructs[parent].children[rowToMove];
    // maintain pointer integrity ... pointer in the child that moved
    nodeStructs[nodeStructs[parent].children[rowToMove]].parentIndex = rowToMove;
    // parent has one less children now
    nodeStructs[parent].children.length--;
    // zero out the node that was pruned
    nodeStructs[nodeId].parent=0;
    nodeStructs[nodeId].parentIndex=0;
    LogDelNode(nodeId);
    return true;
}

// This following recursive process puts an upper bound on the tree depth the contract can handle. 
// Therefore, better to implement similar logic on the client side and recursively call nodeStructs
// until a node can be confirmed attached to the treeRoot in an unbroken chain. 
// Shown here for illustration only since it won't scale infinately.

function isActiveNode(bytes32 nodeId)
    public
    constant
    returns(bool isIndeed)
{
    if(nodeId==treeRoot) return true;
    if(nodeStructs[nodeId].parent==0) return false;
    return isActiveNode(nodeStructs[nodeId].parent);
}

function getNodeChildCount(bytes32 nodeId)
    public
    constant
    returns(uint childCount)
{
    return(nodeStructs[nodeId].children.length);
}

function getNodeChildAtIndex(bytes32 nodeId, uint index) 
    public 
    constant
    returns(bytes32 childId)
{
    return nodeStructs[nodeId].children[index];
}


}
  • Quick note: Pruning the current state cannot reduce the blockchain's size, but it reduces the amount of data a light(er) client needs to deal with. So it's potentially worth doing. – Matthew Schmidt Feb 22 '17 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.