accumulator: PolNode remember doesn't work as intended

[kcalvinalvin]

The way we currently have implemented the remember functionality is to have the niece[0] be itself. However, this property doesn't hold the way we currently have implemented addOne().

https://github.com/mit-dci/utreexo/blob/3f55cb12f16dec7f9d8919b020a6f5d7bf636ced/accumulator/pollard.go#L151-L154

In this code snippet, we point the niece[0] to to itself to prevent the node from being pruned.

Example:

02
|---\
00  01

Here the leaf count is 2 and is 10 in binary. There is a 0 immediately so we can just simply append. The result is:

03
|---\
00  01  02

Adding one more leaf is where things go wrong. The leaf count is now 3 and is 11 in binary. So we must start destroying roots now. We add a leaf to the root 02 and have this midstate:

04      05
|---\   |---\
00  01  02  03

If 03 was to be remembered, 03.niece[0] would be a pointer to 03. But because of this code here: https://github.com/mit-dci/utreexo/blob/3f55cb12f16dec7f9d8919b020a6f5d7bf636ced/accumulator/pollard.go#L168

02.niece[0] now points to 03. Not at all what we're intending. I haven't yet tracked down where these leaves get forgotten but there's def some random leaves that stick around because of this.

EDIT:

I've added this snippet in TestCache() and the test fails.

                        if !l.Remember && n != nil {
                                fmt.Println(p.ToString())
                                t.Fatal("leaf at", pos, "exists but it was added with remember=false")

                        }

EDIT EDIT:

I've just realized that the leaf could have been remembered as a proof for its sibling. This test is correct I believe:

                        if !l.Remember && n != nil {
                                if nsib != nil {
                                        sibling := leaves[nsib.data]
                                        if !sibling.Remember {
                                                fmt.Println(p.ToString())
                                                t.Fatal("leaf at", pos, "exists but it was added with remember=false")
                                        }
                                } else {
                                        fmt.Println(p.ToString())
                                        t.Fatal("leaf at", pos, "exists but was added with remember=false"+
                                                "and it's sibling isn't remembered")
                                }
                        }

[kcalvinalvin]

Mostly trying to get a GetSize function working for pollard for debugging so we can see how many bytes the pollard is taking up really.

func (n *polNode) GetSize(size int) int {
        // n.niece[0] is set to itself to be remembered in addOne()
        if n.niece[0] != nil {
                // hash and two pointers
                size += 32 + 16

                if n.niece[0] != n {
                        n.niece[0].GetSize(size)
                }
        }
        if n.niece[1] != nil {
                // hash and two pointers
                size += 32 + 16

                n.niece[1].GetSize(size)
        }

        return size
}

I think this function should work but since n.niece[0] isn't really n, it causes infinite recursion when following niece[0] polNodes (since the leave will point back up).

[dergoegge]

I actually think that the current approach works as intended but may lead to some extra memory usage is some cases.

If 03 was to be remembered, 03.niece[0] would be a pointer to 03.

We want to remember the proof for a leaf but not necessarily the leaf itself. If 03 points to itself we would prune 02 which is part of the proof for 03.

02.niece[0] now points to 03

In your example this is what we want, 02 pointing to 03 means that the proof for 03 will not be pruned.

Lets assume we have this

12
|-------\
08      09      10
|---\   |---\   |---\
00  01  02->03  04  05   06

what happens if the proof for 03 (02, 08) changes because 02 gets deleted?

We swap 02 and 06 resulting in:

12
|-------\
08      09      10
|---\   |---\   |---\
00  01  06->03  04  05   02

now 02 is just dropped, resulting in the modified forest. Since now 06 still points to 03 we have what we want, the proof for 03 (06, 08) is still cached.

what happens if 03 itself moves? lets assume we are deleting 00 and 02 from this forest:

12
|-------\
08      09      10
|---\   |---\   |---\
00  01  02->03  04  05   06

We first swap 00 and 03 resulting in:

12
|-------\
08      09      10
|---\   |---\   |---\
03  01  02  00  04  05   06
     |______^

now 01 points to 00 which is great since the proof for 03 (01, 09) is still cached. In both of the two cases above the proof for a leaf that is supposed to be memorable remains cached.

Extra memory usage

I think this approach might waste memory through chains of deleted nodes:

12
|-------\
08      09      10
|---\   |---\   |---\
00  01  02<>03  04  05   06

Here both 02 and 03 are marked as memorable, so they point to each other. If we delete 00 and 02 then we get the following after the first swap:

12
|-------\
08      09      10
|---\   |---\   |---\
03  01  02<-00  04  05   06
     |______^

and after the transform is complete:

12
|-------\
08      10
|---\   |---\
03  01  04  05  06
     |
     00
     |
     02

Since 00 and 02 were deleted we get a dead chain of 01 -> xx -> xx. I don't know if these chains can get longer than 2 but i don't see why not.