Swap nodes issue

[kcalvinalvin]

I'm getting an error with swapNodes() when implementing caching for multi-block proofs. It works fine when the pollard remembers everything and just prunes everything but the roots for every range (ex: remember every utxo created between the blocks 10-19. Then prune to the roots right after modification at block 19).

However, when trying to specify what to cache, I'm getting an error like so:

26929 |-------------------------------------------------------------------------------------------------------------------------------\                                                                                                                                                                          
26930 60:02d1                                                                                                                                                                                                                                                                                                    
26931 |---------------------------------------------------------------\                                                               |---------------------------------------------------------------\                                                                                                          
26932 56:7ec8                                                         57:d831                                                                                                                                                                                                                                    
26933 |-------------------------------\                               |-------------------------------\                               |-------------------------------\                               |-------------------------------\                                                                          
26934 48:f0b6                         49:b62a                         50:321f                         51:7f87                                                                                                                                                                                                    
26935 |---------------\               |---------------\               |---------------\               |---------------\               |---------------\               |---------------\               |---------------\               |---------------\                                                          
26936 32:ccc2         33:d09e         34:1738         35:e65d         36:397d                         38:0268         39:0753         40:f73e                                                                                                                                                                    
26937 |-------\       |-------\       |-------\       |-------\       |-------\       |-------\       |-------\       |-------\       |-------\       |-------\       |-------\       |-------\       |-------\       |-------\       |-------\       |-------\                                                  
26938 00:4cd3 01:fe8a 02:9515 03:87ac 04:bfb5 05:e2d9 06:f4e3 07:d43e                 10:0004 11:b1b9 12:1294 13:b311 14:7810 15:fcbe 16:090b 17:a3a5

For the above forest, the targets are [1 2 5 7 10 11 12 14 17]. During modification, I'm getting an error with swapNodes():
swapNodes 38 37 node not found.

Would the position 37 have to be remembered in the forest for the above deletion to work properly?

[dergoegge]

AFAICT 37 (parent of targets 10 and 11) will exist in the pollard after verifying the proof, so you shouldn't have to explicitly remember it.

[kcalvinalvin]

With multi-block proof you only validate once when you ingest the multi-block proof.

Ex: Before verifying block 10, you ingest the accumulator proof for blocks 10-19. You don't receive any other accumulator proof until block 20.

Maybe something is messing up with that part. This error is happening on block 18 after ingesting the multi-block proof before modifying block 10.

[kcalvinalvin]

Ok I think the issue is with the remembering with additions. I'm able to reproduce a simple example.

before block 7 modification:

|-------------------------------\
12:6ef3
|---------------\               |---------------\
08:a7cb         09:0936         10:3859
|-------\       |-------\       |-------\       |-------\
00:c4fb 01:d9f0 02:cb14 03:b41c 04:cfde 05:543a 06:689f

We have the above forest before doing any modifications at block 7.

We'll delete the following:

block 7 dels:
b41c22a675e03ef17a8c1887ffff00d31873c0a1880c2e52b310eb993fd62914
cb140802f7f0e4c86f85822d8f7782f9cae7fc48b18d6d07c7441fdc320bdd1e
cfde4fb7d474502701121705a6f41fc0b94cb6c5b1ec80f06b81019e8ca3eff3

targets: [2 3 4]

We delete 2, 3, and 4 and get the below.

|-------------------------------\
12:dirt
|---------------\               |---------------\
08:a7cb         09:cc75
|-------\       |-------\       |-------\       |-------\
00:c4fb 01:d9f0 06:689f 05:543a 

Now that we're finished with deletions, we add the following:

block 7 adds:
59dd3e6e430e9485fb9a8d52a16887982bf80c98925fe681d580d6b161607f1f - Remember
d2a6f1c7affe5867f0646c5b2466cea7cae33d5f5c8a326f60d173e8b29451fc - Remember
8bf4282de6c25c2f3da866827033a37682b5904c61a8faddc46e97a15f9fed7e
671fe1e1cdede2678749f69d19723ba864066c5ca1692c4599b123a383d1e484

Since 8bf4 and 671f isn't marked to be remembered, we don't remember 10. We get the following pollard:

14:8ea4
|-------------------------------\
12:df76                         13:97eb
|---------------\               |---------------\
08:a7cb         09:cc75                         11:a1d4
|-------\       |-------\       |-------\       |-------\
00:c4fb 01:d9f0 02:689f 03:543a 04:59dd 05:d2a6

Since this is multi-block proofs and we don't ingest/verify before each modification, the pollard does not change.

Then at block 8 we have the following deletions but we result in an error because we forgot 10.

block 8 dels:
d2a6f1c7affe5867f0646c5b2466cea7cae33d5f5c8a326f60d173e8b29451fc
d9f05438473034429f45dc85fca65993a4767afb7d1f5eb33bb871c0e8ddfc34
543a3389b2eb466cd36b92b21cd2ca2be57ae6ab699f46d599722b1080fcb583
59dd3e6e430e9485fb9a8d52a16887982bf80c98925fe681d580d6b161607f1f

targets: [1 3 4 5]

--- FAIL: TestMultiBlockProof (0.20s)
    indexers_test.go:825: ProcessBlock fail at block height 8 err: swapNodes 11 9 sibling not found

I'm not quite sure how to go about it but it's seems to me that the way we're remembering leaves now won't work when you don't ingest/verify before every modification.

One thing you could do is just have a populateWithoutProof() function that just tries to fill in what was forgotten but this seems inefficient.

[adiabat]

Cool find and interesting that this hasn't come up before, I guess multi-block is what's triggering it.
The problem seems to be in swapNodes() and I'll make a branch that fixes it to test.

What's happening in your example:

14:8ea4
|-------------------------------\
12:df76                         13:97eb
|---------------\               |---------------\
08:a7cb         09:cc75                         11:a1d4
|-------\       |-------\       |-------\       |-------\
00:c4fb 01:d9f0 02:689f 03:543a 04:59dd 05:d2a6

at this point 6 and 7 are unknown as well as 10. That makes sense & the remembering / pruning seems OK. The problem is when you delete 1, 3, 4, 5, then the deletion process wants to swap 11 and 9. The code currently won't let this happen and complains "sibling not found".

When it swaps 9 and 11, it also needs to swap (2, 3) and (6, 7). (2, 3) is 9.niece, which is OK. (6, 7) is 10.niece, which would be a nil pointer crash, so swapNodes() catches this and says no. But really, it's still possible; we just need code that says "10 is nil, so 6 and 7 must be nil. Therefore when I swap 9 and 11, 8.niece becomes nil."

This probably / hopefully won't break anything else.

[adiabat]

OK I made a branch "nilswap" and uploaded it here. I'm getting a different problem, because the deletion algorithm doesn't try to swap 9, 11, but instead just swaps 1, 2. Which means 12 isn't recomputed, which is should be!

Will look at fixing that which may also fix the bug you had here. If you link to test code which gives the "sibling not found" error I can make sure.

[kcalvinalvin]

@adiabat The below code snippet recreates the error I had while testing the multi-block stuff.

func TestPollardNoSiblingFound(t *testing.T) {
        var p Pollard

        // Create the starting off pollard.
        adds := make([]Leaf, 7)
        for i := 0; i < len(adds); i++ {
                adds[i].Hash[0] = uint8(i)
                adds[i].Hash[20] = 0xff
                adds[i].Remember = true
        }
        adds[6].Remember = false

        p.Modify(adds, nil)
        fmt.Println(p.ToString())

        // Create the next adds and dels that gets us to the stage right
        // before the swapNodes error.
        newAdds := make([]Leaf, 4)
        for i := 0; i < len(newAdds); i++ {
                newAdds[i].Hash[0] = uint8(i)
                newAdds[i].Hash[1] = uint8(2)
                newAdds[i].Hash[2] = uint8(7)
                newAdds[i].Hash[20] = 0xff
        }

        newAdds[0].Remember = true
        newAdds[1].Remember = true

        dels := []uint64{3, 2, 4}
        err := p.Modify(newAdds, dels)
        if err != nil {
                t.Fatal(err)
        }
        fmt.Println(p.ToString())

        // Then cause the error by deleting 1,3,4,5
        newDels := []uint64{1, 3, 4, 5}
        err = p.Modify(nil, newDels)
        if err != nil {
                t.Fatal(err)
        }
}

[kcalvinalvin]

One line change of

n.remember = remember

in the function addOne() makes all the tests pass (including the new test). Not sure if this is correct so I'll play around with it a bit more.

	for ; (p.numLeaves>>h)&1 == 1; h++ {
		// grab, pop, swap, hash, new
		leftRoot := p.roots[len(p.roots)-1]                        // grab
		p.roots = p.roots[:len(p.roots)-1]                         // pop
		leftRoot.niece, n.niece = n.niece, leftRoot.niece          // swap
		nHash := parentHash(leftRoot.data, n.data)                 // hash
		n = &polNode{data: nHash, niece: [2]*polNode{leftRoot, n}} // new
                n.remember = remember
		p.hashesEver++


		n.prune()
	}

[adiabat]

The code I had was actually producing the same error, I just was not catching any errors from Modify(), oops. So I've got the same thing happening on the 1-shot code. Well, 2 Modify() calls: add 8, remove 4.

Seems fixable