dergoegge
commented
2 years ago 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.
Open kcalvinalvin opened 2 years ago
dergoegge
commented
2 years ago 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
commented
2 years ago 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
commented
2 years ago 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:689fWe 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
671fe1e1cdede2678749f69d19723ba864066c5ca1692c4599b123a383d1e484Since 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:d2a6Since 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 foundI'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
commented
2 years ago 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:d2a6at 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
commented
2 years ago 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
commented
2 years ago @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)
}
}
One line change of
n.remember = rememberin 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()
}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
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:
For the above forest, the targets are
[1 2 5 7 10 11 12 14 17]. During modification, I'm getting an error withswapNodes():swapNodes 38 37 node not found.Would the position
37have to be remembered in the forest for the above deletion to work properly?