You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Recent exploration into the implementation of an index of "recently seen" kernels led us down the path of maintaining an "undo" list per block. This way we can robustly handle duplicate kernels, maintaining the pos of the most recent instance of the kernel in the index, while being able to handle rewind scenarios involving previous instances of the kernel.
We do something similar to this for the output_pos index currently where we track a bitmap of spent output pos per block. And during rewind we use this per-block bitmap to ensure the UTXO set is consistent with rewound chain state. Note that this allows the utxo set to be rewound reliably but leaves "false-positives" in the output_pos index as we do not rewind the index itself.
So we have always used the output_pos index as non-authoritative. During rewind we can (and will expect to) encounter "false-positive" results from the index. We may find an entry in the index for a given output, but we do not yet know for sure if this index entry is accurate. So we go to the PMMR itself for authoritative view of chain state.
The process is roughly -
look in output_pos for possible result
if nothing in index then output is spent
if we find a result in the index, look in the output PMMR
compare output commitment between index and PMMR
if match then output is unspent
otherwise output is spent
It became apparent during the kernel index exploration that there is a better way to do this that can also be applied to the output_pos index.
Rather than storing a bitmap of spent output positions which is by definition unsorted, we can store a vec of output positions where the sort order is consistent with the inputs to the block.
This provides the ability to map positions to input commitments themselves. Rewind can now take advantage of this to ensure the output_pos index remains consistent with the rewound chain state. The output_pos index can be maintained transactionally alongside block processing, in both regular (apply new block) and rewound directions.
This eliminates the possibility for "false positives" in the index lookup. If we find an entry in the index then we know the output is unspent. If we do not find an entry, the output is spent, or never existed.
This involves a change to what we store in the db. We need to store a vec of output_pos (and associated block heights) rather than the existing serialized bitmap per block.
This also involves changes to both apply_block() and the rewind_block impls to update the output_pos as necessary, within the txhashset extension (and therefore transactionally).
Reworking the output_pos index to handle transactional rewind in this way gives us a clear path forward to use the same approach for the kernel_pos index. Rather than "spending" outputs we replace kernels with more recent instances (in the "recently seen" index).
We have this working on a branch. PR coming shortly for these changes. Ideally we can get this into 3.1.0-beta and allow it to be sufficiently tested and released as part of 3.1.0.
Tracking this here so we can tag it as scheduled for inclusion in 3.1.0.
The text was updated successfully, but these errors were encountered:
Recent exploration into the implementation of an index of "recently seen" kernels led us down the path of maintaining an "undo" list per block. This way we can robustly handle duplicate kernels, maintaining the pos of the most recent instance of the kernel in the index, while being able to handle rewind scenarios involving previous instances of the kernel.
Related - #3228
We do something similar to this for the
output_pos
index currently where we track a bitmap of spent output pos per block. And during rewind we use this per-block bitmap to ensure the UTXO set is consistent with rewound chain state. Note that this allows the utxo set to be rewound reliably but leaves "false-positives" in theoutput_pos
index as we do not rewind the index itself.So we have always used the
output_pos
index as non-authoritative. During rewind we can (and will expect to) encounter "false-positive" results from the index. We may find an entry in the index for a given output, but we do not yet know for sure if this index entry is accurate. So we go to the PMMR itself for authoritative view of chain state.The process is roughly -
It became apparent during the kernel index exploration that there is a better way to do this that can also be applied to the
output_pos
index.Rather than storing a bitmap of spent output positions which is by definition unsorted, we can store a vec of output positions where the sort order is consistent with the inputs to the block.
This provides the ability to map positions to input commitments themselves. Rewind can now take advantage of this to ensure the output_pos index remains consistent with the rewound chain state. The
output_pos
index can be maintained transactionally alongside block processing, in both regular (apply new block) and rewound directions.This eliminates the possibility for "false positives" in the index lookup. If we find an entry in the index then we know the output is unspent. If we do not find an entry, the output is spent, or never existed.
This involves a change to what we store in the db. We need to store a vec of output_pos (and associated block heights) rather than the existing serialized bitmap per block.
This also involves changes to both
apply_block()
and therewind_block
impls to update theoutput_pos
as necessary, within the txhashset extension (and therefore transactionally).Reworking the
output_pos
index to handle transactional rewind in this way gives us a clear path forward to use the same approach for thekernel_pos
index. Rather than "spending" outputs we replace kernels with more recent instances (in the "recently seen" index).We have this working on a branch. PR coming shortly for these changes. Ideally we can get this into
3.1.0-beta
and allow it to be sufficiently tested and released as part of3.1.0
.Tracking this here so we can tag it as scheduled for inclusion in
3.1.0
.The text was updated successfully, but these errors were encountered: