Bitcoin full node and query server
March 2025
Archive of the libbitcoin Slack #general channel.
Saturday, March 1, 2025
evoskuil05:11
I just completed the couple items I mentioned I had remaining. Cleaning up for the lack of xcode
std::atomic_ref<T> workaround. Also rewrote the store serialization for tx. This allocates all inputs and all outputs in one chunk each, and writes them contiguously, as opposed to iterating over the allocation. Given that input/output both cache size during wired deserialization there's no cost to computing the variable offsets. I also found that I was using the script and witness size methods previously, to store the size prefixes. But those aren't cached, so that was a bit wasteful - iteration over all opcodes. So allocations are reduced by around 5 billion or so, and those impose an exclusive lock over respective tables, which is the only material source of lock contention, so that's really good.evoskuil05:23
That was the end of my performance list, apart from updating store tests. So I'm going to work on my test bench, and get some runs at various memory sizes as we discussed yesterday. It's time for me to do a little clean up on the confirmation step reorganization, which was previously implemented and removed for concurrent confirmation testing.
Once that's back in place the basic node is complete. Basic node meaning headers first w/block sync (no tx relay, no blocks out, no compact blocks, etc.), just building the chain. The remaining protocols are not at all performance critical, and are easily reimplemented from v3.
So I think after I button this up I might move over to server and get the build working. That way we can start updating the endpoints and maybe get some performance testing going on.
🚀 3
Looking at the recent changes running and the maxi is now beating the record run on the avx512 mini, that's a huge improvement. In fact I'm gonna stop it and switch to the mini to see if this will give us a record run.
(edited)evoskuil06:34
Mini is tracking very close (within a few seconds) of the record run, which is great. I think that there's a more significant benefit on the maxi because of much slower memory. The single allocation blocks and contiguous writes end up with a bigger benefit. If that's holds up, the maxi looks like it would go from 60 minutes to 39, like the mini - even without shani/avx512.
evoskuil07:52
Pretty good, 50 minutes on the maxi, 40 on the mini, and maxi memory only reached 40%, which I've never seen. It has always hit 100% for a full sync. That tells me paging should be significantly reduced.
🔥 1
Sunday, March 2, 2025
C
cguida03:24
ok there are apparently used 128gb machines for $677 and 256gb for $1400. just needed to search for "workstation" instead of "desktop" xD
at this rate 256GB machines will be accessible to everyone in like 5-10 years
👍🏻 1
Full validation run on the maxi is almost done. Looks like it will finish about 5% faster than the record run, so around 4.4 hours.
That's with the linear memory allocator turned off, count be a little faster with it enabled. Given download alone is 50 minutes, and validation alone (before I moved the pre-confirmation queries into validation) is 3.5 hours, it implies that all combined, confirmation is adding a net of just 6 minutes.
Generally on a big machine, download is going to be bandwidth limited, and validation/confirmation is going to be CPU limited, but overall fully scalable apart from a few minutes of necessary linearity.
👍 2👌🏻 1
C
cguida21:29
Ok this is definitely the cheapest 256gb box https://www.newegg.com/dell-precision-t5820-tower/p/2NS-0008-6WK00
US$762
tempted to buy it just to experience the 4.4-hour full-validation sync
of course, the CPU is crappy, but i'm not sure how much that matters? https://www.cpubenchmark.net/cpu.php?cpu=Intel+Xeon+W-2102+%40+2.90GHz&id=3276
(edited)cpubenchmark.net
Performance and price comparison graphs for Intel Xeon W-2102 @ 2.90GHz
@evoskuil what's the CPU on your maxi box?
CPU matters.
validation is primarily a funiiton of CPU, if there is enough RAM to prevent thrashing.
evoskuil21:37
Basically, take the thread count and multiply by the block speed to compare. Also shani is significant.
My maxi base clock is 2.1GHz
maxi is 5.7x faster
👍 1
hmm ok. in that case this box would do the sync in like 20 hours or so?
is it shani?
C
cguida21:39
your cpu has a score 3.5x higher https://www.cpubenchmark.net/cpu.php?cpu=Intel+Xeon+E5-2683+v4+%40+2.10GHz&id=2908
cpubenchmark.net
Performance and price comparison graphs for Intel Xeon E5-2683 v4 @ 2.10GHz
not sure about shani, checking..
So...
pmienk21:40
Xeons don't get sha until for awhile past e5v4s, gold Gen 1+2 don't have it. Not sure when it shows up
👍 1
C
cguida21:44
@evoskuil this one's really close to yours, just needs a 1tb ssd added on https://www.newegg.com/p/2NS-0006-3HEM8?Item=9SIBYWEKDT3382
probably like $900 total
(edited)it appears to have two xeons, is yours the same? https://www.cpubenchmark.net/cpu.php?cpu=Intel+Xeon+E5-2680+v4+%40+2.40GHz&id=2779&cpuCount=2
cpubenchmark.net
Performance and price comparison graphs for [Dual CPU] Intel Xeon E5-2680 v4 @ 2.40GHz
evoskuil21:52
Same bus and memory (PCIe3/2400), same no shani, CPU 1/2 as much, so 9 hour full validation sync.
(edited)Assuming a fast SSD.
maybe a bit lower
evoskuil21:54
I don't know what Core would be on that machine, but it is heavily dependent upon shani.
On my maxi on Windows Core taxes about 24 hours to validate.
👀 1
So maybe 48 hours.
C
cguida23:29
ok final build for fast full validation https://pcpartpicker.com/user/cguida/saved/kbZvbv
$872
I think it might be faster than your maxi box @evoskuil since it has sha-ni
inconvenient because it involves buying used parts, but i think it will work
still needs a case and a psw but those are probably cheap haha
Monday, March 3, 2025
evoskuil00:30
If it has the same
(edited)cpu-speed x threads and shani and sufficient RAM/SSD speed it will be faster. shani would save about 5-10% on the maxi (80% of the tx and signature hashing cost).avx2 or avx512 save mainly on Merkle hashing, maybe 5%.
I don't think it has as many threads as yours, so maybe a bit slower. Still a great deal if it syncs libbitcoin faster than core
gahh, this website is super annoying. here's the new one https://pcpartpicker.com/user/cguida/saved/BMKdxr
definitely public this time, i validated from a different device
👍🏻 1
It'll be listed under Extensions & Technologies
🙏 1
evoskuil02:11
Just guessing, but it might be possible to get comparable perf at half the RAM. I'll check soon.
👀 1
i'm noticing that all the cheapest cpus that do SHA are AMD, Intel doesn't seem to like putting that in their server cpus 😕
evoskuil02:58
Mostly affects Merkle tree hashing, and with shani instead it's pretty close.
Notice how avx512 is ever so slightly faster than shani, for Merkle hashes at 16 or above.
👍 1
evoskuil04:43
I dropped the maxi to 128GB and it’s now running full validate/confirm with full RAM and minimal disk activity. Time is only 10% the 256GB record run. Still early, but great start.
👀 1
Also it seems to be catching up to the record run. Only 5% behind now.
(edited)100% CPU, 98% RAM, almost no disk activity.
Dropping into a download period (validation gaps), close to max bandwidth utilization, while validating what's available. Periodic disk flushing.
(edited)
C
cguida18:40
if 128gb works then we can go a lot cheaper https://www.ebay.com/itm/226623279790?var=525803295279
(edited)eBay
Model Number:T5820. Graphics Card : RTX 4060 / RTX 2070 / K620. RAM :DDR4 ECC 32GB/ 64GB / 128GB. Series:Dell Precision.
evoskuil18:42
I think 128 is going to be okay. 64 probably not. I ran into a failure resulting from the hashmap header memory fencing last night, so am restarting.
👍 1
I blame the failure on Grok3 😂
😄 2
evoskuil18:49
I also have a failure somehow relating to the serialization of witness data to the store. I’ve been chasing this issue for about a year now. I can avoid it by not using the custom memory allocator, but I do not believe it is caused by it (I had it prior). It’s just that reallocation is orders of magnitude faster with it, and I think the witness object is getting rugged by premature deallocation in general (specifically a premature shared pointer release).
I blame this on the very stupid decision made by the community in the serialization format of tx witnesses. 🤨
(edited)🤔 1
evoskuil21:25
Grok fixed its memory fence design, with a little prodding. Giving it another go on 128.
It's running faster than the 256GB record run so far. 🔥
👀 1
I disabled the linear allocator, which adds a few points. The updated memory fencing appears to be correct.
Tuesday, March 4, 2025
evoskuil03:27
200% time now, at block 700k. Still not thrashing. SSD at ~50%. Half the RAM twice the time (at least).
(edited)
evoskuil15:30
Well, once the point hashmap got large the double spend lookups started heavily pages-swapping, and it finished up at 16.3 hrs (365% of 256GB runs). Still 8 hours faster than Core on this machine (with twice the memory, though that wouldn't make a difference), but not what I was expecting.
🫤 1
Also, the memory fencing fix is certainly correct now.
evoskuil19:31
The above 128GB run game me some good insight into where costs were going, as it wasn't fully thrashing as with the mini. At about 800k almost 50% of time during validation was spent on the single query to obtain potential double spends (which we never actually encounter), in the point table. As the table contains 40 bytes per input, it grows to about 100GB, and table heads take about 16 GB, leaving only 12GB for block and previous output query and validation.
(edited)Since every spend actually exists in the table, every one of the 2.5B spends results in a read from the table body, even without hashmap conflicts. Of course this excessive paging also slows the block/prevout queries, but even so that only amounts to about 11% of time. Final confirmation about 5%, and validation takes up the rest. Without heavy paging, validation is about 90%.
But if it keeps blowing out to hundreds of GB or TB then at that point it won't really be an improvement, even (and especially) for lower ram configurations
(edited)evoskuil21:58
Not reasonable at all. No matter how much RAM you have, it will always keep getting slower. Furthermore its assume valid is even more slow, even on cheap machines.
👍 1
You are making the assumption that the chain will grow making libbitcoin slower. The opposite is true, the hardware grows exponentially faster than the chain. So this is exactly the problem with Core's UTXO set and not with libbitcoin. It has gotten much slower despite hardware growth, and no matter how much hardware you throw at it, it's still very slow. On my 256GB machine, Core takes 24hrs.
Given no material benefit from faster bandwidth, RAM, SSD, or CPU, assume valid will continue to get slower linearly as the chain grows. Improvements up to the past few years have all focused on optimizing this single strand of execution (like SHANI, which was significant), but that well is tapped.
And given sequential-by-block validation, it's the same story there. Double the thread count and memory, and validation time is easily cut in half. Double the network bandwidth and milestone is cut in half. That's what scalability means.
💯 1
it's relieving to discover that 256gb machines can be found for <$1000
if that's indeed the minimum
evoskuil22:05
There is a minimum resource requirement for the current chain, for validation and for milestone. Even the 128GB validation was much faster than Core. But Core won't get too far on 1KB RAM - it has a minimum too.
👍 1
evoskuil22:06
Our minimum is higher, for sure. But that's just where we are intercepting the Moore's Law curve.
(edited)👍 1
And keep in mind, this is just IBD. Core has no query perf or scale to speak of, and doesn't even provide spend or address indexing.
Pretty soon every machine will have at least 32GB and it will not matter that they are functional on 8, it will matter that they take 10 more than hours on 8 or 32 or 256 for assume valid, and all machines can do that with libbitcoin in < 1.
(edited)💯 1
Thursday, March 6, 2025
evoskuil16:48
I just isolated the two parts of the confirmation query, from each other and from validation. The one that necessarily runs sequentially, filling in gaps on the tail of the total run, takes just 15 minutes on the mini, from a cold store start.
evoskuil16:56
The other is the double spend query, which can run entirely concurrent across blocks (except for the rare encountered possible double spend). This is heavily store intensive (SSD/RAM) with very low CPU, which is why it runs so cheaply on the maxi. However completing it on the mini with nothing else running, sequentially by block, still maxes out SSD from the start. The reason it starts hard is the isolated run starts with tables fully populated, so all queries are max paging cost due to max conflicts. There are only three tables involved, the tx table (to get the hash, no search required), the point table (search for point matches), and the prevout table (which is read in sequential chunks by block, and contains all point indexes and parent tx ids). I can't imagine isolating resources any further for this query. So we'll see how long it takes in isolation. To get to its starting point on the mini requires 7.8 hours of download and validation, and 15 minutes of final confirmation. So it's starting from under 9 hours with a 15 hour Core baseline (11 on Linux). It looks possible that it could complete in a few hours, hard to say just yet.
I didn't mention that on the mini, there is no benefit to running the query concurrently across blocks, because the store is already at capacity when running sequentially by block and concurrently by tx.
👀 1
evoskuil17:10
Rough very early projection (5% complete) is that this completes at 9.7 hours, making a full run about 19 hours.
evoskuil17:18
The above lack of benefit to concurrency at this resource level is why Core does better, because it is performing an entirely sequential run anyway, and has the confirmation advantage of the ordered output accumulator. We can't get the advantage of confirmation parallelism, due to limited memory.
However, the total table size of all three of the necessary tables for this query is 181GiB, though the 25GiB prevout table is read totally sequentially, so doesn't page swap. So I think this method might do quite well on 128 or even 64GiB RAM.
👀 1
Huddle with pmienk, evoskuil, Marnix, parsevalbtc, cguida · 123 min20:54
10 replies · cguida, parsevalbtc, evoskuil · last Mar 06, 2025
C
cguida21:11
there was a Node failed to start with error 'seeding unsuccessful'.
but again, no segfault. built tables, tried for seeds, shutdown
You can drop this in as a shortcut.
ton of outbound traffic
note, i didn't force it to rebuild the tables
was there supposed to be an immediate segfault?
1 reply · cguida · last Mar 07, 2025
a few block hash rejected by checkpoint
I think he built with avx2.
✅ 1
Friday, March 7, 2025
evoskuil01:18
The 256GB maxi baseline run of isolated sequential spend checks was 3.1 hours. To put it in perspective, the entire download, validate, and (mostly parallel) confirm run on the maxi is 4.4 hours. So concurrency and data locality are major factors.
C
cguida01:41
there's gotta be a way to speed that up, right? do we really need to check every single spend in the whole blockchain? is there no way to reduce the search space?
I think you missed the last part of the discussion. Phillip and I went through the theory and constraints. Earlier on there were a lot of performance unknowns, but we have those answers now.
The above test could be run in parallel, and does run in parallel on the maxi, which is why it's so fast. But the memory constraints of the mini are the issue. Performance tuning is a significant part of anything like this, and the strides we've made are truly extraordinary - and this is the very last open issue. We settled on what feels like the best next attempt, which I'm going to try now.
That approach is to ensure that any duplicates in the point table are recorded in a sidecar table. In a typical run there are none, so everything after that is trivial. There are only 2 costs to doing this, and I did one of them in the first implementation. That's to search each hashmap for the existing item before inserting it. The problem with this is that the performance cost is far worse than the space saved.
This was not intended to ensure no duplicates, just to minimize them. A race remains which must be guarded. That's a lock over any search while an insert is pending. That's very, very expensive - basically linearizing all inserts into the point hashmap, which is 2.5 billion entries. But it may still be cheaper than the alternative.
(edited)Basically if we are going to search the entire table for every entry, we want to do that upon insertion, which cuts the conflicts and paging in half - since the file is much empty at the outset and full at the end. And it also eliminates the need to search up the search key from the tx table, since it's presently already at hand for the insert. Those are significant benefits. If every duplicate in the table can be identified then there is no other cost to the operation. It's also a very simple implementation.
(edited)👀 1
evoskuil03:30
I just realized that another major advantage of the approach is that for each insert we must only identify existence (i.e. the first match found). In the current model we always find one (own spend) and must ALWAYS search for a second at least (potential double spends). Even though a second is never found, this means walking the iterator over the same conflict list (which could have any number of non-matching conflicts). So we do two searches for every one point. This approach is upon insert, so the first existing match is a potential conflict. All we need to do is flag that and later in the confirmation phase we can scan for all spends of that point and check confirmation state. So this cuts the paging in half again.
(edited)👀 1
evoskuil04:45
Another benefit I just realized while implementing is that the duplicates sidecar is not an accumulator - we do not need to track duplicates of spends that have occurred prior to the need to validate a given spend. So milestone and checkpoint entries do not require search/lock.
evoskuil08:09
Ok, running this thing now. Not writing the (empty) sidecar table. Just will fault out if a duplicate is found upon insert. Bypassing the search when it comes to coinbase txs (since there are lots of duplicates but they aren't spends). Coinbase points are only written because it's more compact and more efficient to make them positionally aligned with input records than to link them to each other.
The updated code is limited to this, plus a define for the boost mutex (std is not upgradeable)...
evoskuil08:28
// Expand synchronizes keys with ins_fk, entries dropped into same offset.
// Allocate contiguous points (at sequential keys matching ins_fk).
if (!store_.point.expand(ins_fk + inputs))
return error::tx_point_allocate;
const auto ptr = store_.point.get_memory();
if (tx.is_coinbase())
{
for (const auto& in: *ins)
if (!store_.point.put(ptr, ins_fk++,
table::point::compose(in->point()), table::point::record{}))
return error::tx_point_put;
}
else
{
// Write all table elements (row not linked).
auto fk = ins_fk;
for (const auto& in: *ins)
if (!store_.point.set(ptr, fk++,
table::point::compose(in->point()), table::point::record{}))
return error::tx_point_set;
// Exclusive search and index commit.
std::unique_lock lock{ mutex_ };
// TODO: write a record for every match found.
fk = ins_fk;
for (const auto& in: *ins)
if (store_.point.exists(ptr,
table::point::compose(in->point())))
return error::confirmed_double_spend;
// Link all table elements (row linked).
fk = ins_fk;
for (const auto& in: *ins)
if (!store_.point.commit(ptr, fk++,
table::point::compose(in->point())))
return error::tx_point_commit;
}Search is grouped independent of writes, to reduce paging, since writes are contiguous.
evoskuil08:43
As predicted, the performance impact is significant, on the maxi it's hard to say if that would translate to thrashing on the mini. But could certainly be better than others.
evoskuil16:59
So here's a data point. After 7.6 hours, basically the same amount of the it takes the mini to download and validate 100% of the chain, the above change has resulted in the mini downloading and validating 15% of the chain, and this will likely slow dramatically as the point table grows.
95% of all time is spend storing blocks, and 92% is spent checking the point table for existence. Of that time, basically all of it is spent paging.
evoskuil18:12
It seems like there’s always some other option to try.
A sufficient requirement is that we need to know if a second point exists for any point that we validate, when we validate it, even if we validate blocks out of order. This is because of the partial order constraint that all prior blocks in the validating branch are archived. So the possible double could not be missed. False positives are ok and expected.
During validation we read the entire block and all of its prevouts. Each prevout attachment requires that we search the point table to find the tx of the previous output, so we can obtain the output. This is the only way inputs are associated to outputs. For some reason, this is reasonably performant on the mini. Download and validation/confirmation completes in under 8 hours, without the spent query.
So to determine the existence of a potential double, we can iterate past the first match to any second. This doubles the input point search cost. But since points are already scattered across a hashmap it seems that this shouldn’t produce a non-linear increase in cost. The cost is no more than 5 or 10% of the run presently.
Once a positive discovery is made the result can just be captured as a bool on prevout metadata, something we already do. That allows us to then write the potential conflict’s first point id to the prevout cache table, for later inspection during final confirmation, also something we already do, but have been doing it from an independent point table scan.
C
cguida18:56
that sounds like it reduces the search space? we look for double spends in a cache table instead of an independent point table?
not sure i'm following
evoskuil19:01
It piggybacks on the existing validation spend search to find a second (in the conflict list). Search along the hashmap conflict list is how we implement multimap. A second discovery implies a possible double spend. Adding that to the cache table is necessary so that it can be processed under the total confirmation order, but there are so few (normally zero) to subsequent determination is inconsequential.
(edited)C
cguida19:08
ah interesting. so during validation you just make a cache of all possible double spends, then search only that cache during confirmation?
evoskuil19:10
That's what I've been doing, but computing the cache is the real cost. The cache would typically be 0 entries.
Since all previous blocks are stored by the time we validate blocks, even though we are doing them out of order this identifies any potential.
they allow you to quickly find relevant transactions for a set of output scripts...
and prevouts actually, the way bip158 is implemented
That's precisely what the address index does, and much faster.
ah right yeah
can we leverage the address index then?
no, it's huge and costly. We already have the minimal hashmap of points. We don't need the outputs, just duplicated points (spenders of the same output).
👍 1
It's just that when we are validating, we need the output, which is identified by the point.
However, I just realized, that when obtaining the prevout we don't search the point table. We navigate to it from the input and search the tx table for the hash of the point, to find its output from the point index. So this means my above approach wouldn't help.
The data model was designed to make block/tx/prevout storage and retrieval as efficient as possible.
(edited)We would still have to search the point table to find self (the current spender), and then iterate to find a possible second. And this is what is already being done during validation in the most efficient implementation on the maxi.
(edited)evoskuil19:21
2.5 billion hash:index values in a hashmap - plus a 4 byte link per row. that's 2.5B x 39 bytes.
(edited)i guess that's what the 4-byte link is?
The link is for the hashmap conflicts lists.
👍 1
hashmaps are linked lists of keys that have the same hash (in the header bucket).
(edited)evoskuil19:23
Paging is the only issue. It's very fast on the maxi, as the hashmap is constant time and the queries are parallel by block.
evoskuil19:25
the hashmap head. the hash function for the point table is a std::hash combine of the tx.hash and the index. the hash of the tx.hash is the first 4 bytes.
35 replies · cguida, evoskuil · last Mar 07, 2025
C
cguida19:33
When you say "the first 4 bytes", do you mean the first 4 bytes of the txid (which i think you are calling tx.hash here)?
evoskuil19:35
For the tables that have a sha hash (or a point .... hash:index) as the natural key (search key), the hashmap's hash function doesn't do math on the sha hash, it just takes the low order bytes from the sha hash in the length it requires. all that is necessary for a hashmap hash function is evenness, and sha satisfies this, apart from high order bytes in header hashes.
evoskuil19:36
We found that this is by far the most efficient and evenly distributed hash function, it's basically perfect, or at least ideal (normal distribution).
(edited)👍 1
evoskuil19:37
For hashmaps that key off of the surrogate key (store id) of another table, the hash function is just the key value, since keys are sequential and therefore perfectly evenly distributed. even better than the sha normal distribution.
👍 1
evoskuil19:38
These values are then shifted in the header domain, which is determined by desired load factor.
C
cguida19:38
ok so for a point that looks like
aabbccdd.......:0, in the point table the hashmap key is aabbccdd?evoskuil19:39
These are stored in link-sized values (3, 4, 5, 6 bytes currently) in the head buckets and table rows. The head provides the list (actually stack) top and the links provide the reset.
👍 1
C
cguida19:39
sorry i'm not that familiar with hashmap internals, i just stick in a hash and out comes a value haha
evoskuil19:39
The link value sizes are determined by the size of the table (so they don't overflow the restricted integer domains).
evoskuil19:40
The load fact (bucket count) is configured to balance average search conflicts against header size.
evoskuil19:41
The key for a point is the combination of the
aabbccdd and the 0 . This requires a mathematical operation called hash combination.evoskuil19:43
The ideal hash function is no function, just truncate the natural key and shift into bucket domain.
👍 1
evoskuil19:44
namespace std
{
template<>
struct hash<bc::system::chain::point>
{
size_t operator()(const bc::system::chain::point& value) const NOEXCEPT
{
return bc::system::hash_combine(value.index(),
bc::system::unique_hash(value.hash()));
}
};
template<>
struct hash<bc::system::chain::point_cref>
{
std::size_t operator()(
const bc::system::chain::point_cref& value) const NOEXCEPT
{
return std::hash<bc::system::chain::point>{}(value.get());
}
};evoskuil19:44
// Combine hash values, such as a pair of djb2_hash outputs.
INLINE constexpr size_t hash_combine(size_t left, size_t right) NOEXCEPT
{
return left ^ shift_left(right, one);
}evoskuil19:45
template <size_t Size>
INLINE constexpr size_t unique_hash(const data_array<Size>& key) NOEXCEPT
{
constexpr auto size = std::min(Size, sizeof(size_t));
// This optimization breaks data portability (by endianness).
// Could be modified to use an endian conversion vs. simple copy.
size_t value{};
std::copy_n(key.begin(), size, system::byte_cast(value).begin());
return value;
}evoskuil19:46
This is a typical good hash function. It was dramatically less efficient than our "unique hash" for sha values.
// Objectives: deterministic, uniform distribution, efficient computation.
INLINE constexpr size_t djb2_hash(const data_slice& data) NOEXCEPT
{
// Nothing special here except that it tested well against collisions.
auto hash = 5381_size;
// Efficient sum of ((hash * 33) + byte) for all bytes.
for (const auto byte: data)
hash = (shift_left(hash, 5_size) + hash) + byte;
return hash;
}
C
cguida20:01
does hash_combine produce adjacent hashes by numerical order, for different outputs of the same tx?
evoskuil20:09
Ideally all hashes are evenly distributed, but "completely different" is a bit hopeful.
evoskuil20:12
If you are thinking that clustering by tx.hash would be beneficial, that's not the case. It would result in long conflict chains with no benefit. Outputs of the same tx are not consistently spent by the same tx. But in any case all outputs of a tx are in fact clustered into contiguous rows in the point table.
(edited)👍 1
C
cguida20:18
Okay that's what I was asking. It does sound like if you xor the vout to the left-shifted txid, then you would end up with contiguous rows by txid
evoskuil21:04
All table bodies are append only, and rows are allocated in a batch for a given tx. So they are inherently contiguous. Even if the allocation was not contiguous due to individual allocation (as previously) data locality wouldn't be materially affected, and that's the only real cost (paging).
(edited)the store would be 5 TB
😅 1
SHA hashes and scripts make up most of the store.
evoskuil19:32
every tx gets hashed twice (segwit) just for commitment to the block. then there's merkle hashing of all txs, twice (segwit), all headers are hashed, and all signatures require another (unique) hash of the tx, and for segwit this requires hashing inputs, outputs and witnesses first.
(edited)The trick is to never hash the same thing twice, and never unnecessarily serialize to produce a hash. We achieve this.
💥 1
evoskuil20:28
Here's an example of hash reserialization avoidance (header deserialization from wire):
https://github.com/libbitcoin/libbitcoin-network/blob/master/src/messages/headers.cpp#L44-L63
(edited)evoskuil20:36
The witness hash is never needed again after block.check which confirms the witness commitment. But the block.hash and tx.hash are stored to the database as search keys for the header and tx tables respectively. So they are never computed again, since they can be read directly. Point hashes are tx hashes (if valid) but must be redundantly stored in order to allow for correlation to the spent tx.output given concurrent download. A sequential store (like Core) could correlate valid point hashes to txs and replace the point hash with a tx surrogate (store) key. But it Core doesn't do this, because it doesn't really have a database.
(edited)evoskuil21:34
Just made a minor optimization, allocate all tx table records for block contiguously. Reduces tx table allocator lock contention and eliminates std::vector heap allocation for all tx links - for setting into txs and strong_tx tables during block storage. Could also compress the txs table by not storing the full set of tx links when the association is created from a block (vs. compact block).
🔥 1
Saturday, March 8, 2025
evoskuil19:18
Ok, so I'm out of ideas again. So At this point I'm going to move on, with current times standing at 37 minutes for mini milestone sync, 50 minutes for maxi milestone, 100 minutes with address index, and 4.5 hours with full validation/confirmation. I don't yet have a minimum RAM spec for milestone or validation to avoid thrashing.
🎉 1👍 1
Sunday, March 9, 2025
evoskuil22:08
I just realized that the change the point table from "foreign point" - a 7 byte search key consisting of the point.hash primary key and the 3 byte point.index, resulted in a dramatic increase in hashmap collisions in the point table. The new point table search key is the full 32 byte sha256 hash and the 3 byte index. Since the original pk's were guaranteed to be unique, point table collisions were almost zero. Now they are more normally distributed. However, previously to obtain the fp, one had to search the input table for the sha256 hash.
So it's ultimately better, but there is an aspect of it that I hadn't measured before. Combining the dual key previously was effective, because of the uniqueness of the pk. But combining the lower 8 bytes of the sha256 hash and the sequential point index for identical point.hashes was not previously measured, and it's very weak. Which means one of the issues has been long collision chains. I'll measure the actual rate with the old combiner and a more effective one. Since the combiner is only used in this one table, it can pay to have more computation and reduce the rate. Prob not huge, but definitely material.
👀 1
Monday, March 10, 2025
evoskuil18:58
I ran the collision check and it turns out to not be so bad. Just needed to excluded that as a potential major issue. The hash combiner is only used for points, as all other values are single natural hashes. I ran this and the commented out algorithm:
INLINE constexpr size_t hash_combine(size_t left, size_t right,
size_t) NOEXCEPT
{
////constexpr auto prime1 = possible_narrow_cast<size_t>(0x9e3779b97f4a7c15_u64);
////constexpr auto prime2 = possible_narrow_cast<size_t>(0x517cc1b727220a95_u64);
////auto first = left;
////first ^= shift_right(first, 23);
////first *= prime1;
////first ^= shift_right(first, 19);
////auto second = right;
////second ^= shift_right(second, 13);
////second *= prime2;
////second ^= shift_right(second, 31);
////first ^= second;
////first += seed;
////first ^= shift_right(first, 17);
////first *= prime1;
////first ^= shift_right(first, 29);
////return first;
return left ^ shift_left(right, one);
}Bucket population was 70.4% and 70.6% respectively, which is comparable to all sha256 "no-hash" tables (where we take the lower order bytes of the sha256 hash only. Those are 72%. Mixing in the index field definitely loses some uniformity, but that's pretty good especially for the simple shift/or.
evoskuil19:12
That's for a load factor of 1.22, and for the 72% sample data the load factors were 1.94, so it's really pretty good. This is the conflict distribution, apart from one outlier in the complex scenario, which ended up in the 850,001 length coinbase list (which is not good). The simple combiner makes it very unlikely that an actual spend will conflict with the coinbases.
Log10 plot:
So I'll stick with the existing hash combiner for now. These distributions are more normal than even, but still great and cheap. The use of a primary from another table as a search key is perfectly even, those look more like this:
👀 1
evoskuil22:55
I hinted the other day that I have another idea. For the first time however this one does not require searching the list of points either upon creation (concurrent-by-download duplicate detection, requiring locks), validation (lock-free concurrent-by-block duplicate checks, which is fast on the maxi), or confirmation (sequential lock-free concurrent within block duplicate checks, also pretty good on the maxi). It also does not require building an accumulator of utxo state (utreexo), which is ultimately sequential by block (slow), increasing in size, costly to compute, and unnecessarily complex for the objective.
As I mentioned in the last meeting, the fundamental problem reduces to duplication detection of all spends in the point table (all ~2.5B
hash:index values excluding coinbases). There is no need to maintain an accumulation of utxos or even the unspent points, just to know what are the points that have more than one entry in the table (typically there are none). There is no need to search the table to know this, because in theory it's most efficiently done upon insertion. At that point (download phase) we have the most free CPU available. But the point table is over 100GB and it's totally not feasible to search it for every insert, or at any other point, for every spend, on a low memory machine, due to paging cost.evoskuil23:05
So it's been nagging me that this should be doable with positive (no delete) accumulation during download, across download threads, in a lock-free manner, without having to search the point table at all. So I worked through some statistical accumulation options, and had Grok do some sizing. I also pulled out the actual conflict rates in the point table, as this is critical for the estimation. I looked at Bloom and Cuckoo filtering, and settled on Bloom because it's far more space efficient because it doesn't support deletion - which we don't need. Either can be performed concurrently in a lock free manner, though Bloom is a little more complex to do so. Cuckoo would be basically using our hashmap header template, and its memory fencing. Bloom requires striping the filter by thread (basically independent filters, sharding the space). Bloom also requires more computation, but that's pretty trivial.
evoskuil23:12
So going with Bloom, it comes down to a straightforward tradeoff between filter size and false positive rate. There are no false negatives, but false positives are like hash conflicts and increase as the filter saturates. These can only be resolved by querying the main point table, which of course we want to avoid. Increasing filter size is like increasing table headers. Headers and the filter are randomly accessed and therefore consume most of their size in RAM. Currently the total header set is 16GB, and I'm looking at 4GB more for the initial filter sizing. That eats about 20GB RAM. The reset is preserved for working and paging space as blocks are downloaded, read, populated, and validated. But these aspects are very efficient, not requiring hashmap query and therefore conflict paging, except in the smaller tables, like
transaction and bk_validate, and is_strong, even to obtain points - as those are navigated from the prevout parent tx and point index.evoskuil23:32
Given our actual hashmap conflicts (posted above), filter size, and bloom
k value (e.g. 7), we can project the false positive rate. The actual hash function values present almost a perfect Poisson distribution (based on the use of sha256 values), but not perfectly (due to mixing in the point index). And in fact the uniformity is better than Poisson:
Tuesday, March 11, 2025
evoskuil00:06
The "ideal" (Poisson) hash function distribution false positive rate for the given Bloom parameters is 0.4026% and our trivial hash function's rate yields 0.396% - better than ideal 🙂. Though the implementation requires 7 hash functions, and to achieve this FP rate they all must be at this level. We take 8 bytes of the point's sha256 hash to get this result, and we should be able to get sufficient independence at the same uniformity by just using other half-overlapping segments of the sha256 hash.
evoskuil00:16
The hash function computation is negligible - the additional header mmap and the false positive conflict resolution searches are the real cost. I set up a simulation to measure these. The header cost is simulated by doubling the 4GB tx header bucket count. This reduce conflicts in that table, but while fully keeping the additional 4GB in RAM. Performance improvement from the reduced conflicts in that table is minimal, as previously measured. So that handles the filter. Then the false positive searches are simulated by using the hash table hash function result for the point table write, and modulo to make an existence check call for 0.29% of all inserts to the point table. If that performs well, this should certainly do the same.
evoskuil03:45
65% through the simulation and the run is holding a constant projection (8hrs) since 20%.
That's barely over the validation only (with no confirmation) run time.
(edited)evoskuil05:45
About 90% complete and holding. This is about 1/3 the time of previous attempts, because we are not querying the 100+GB point table for every spend (only about 1 in 380). So looks like this is worth implementing, and should end up outperforming bitcoind on the mini.
(edited)👀 1
Thursday, March 13, 2025
evoskuil05:32
I’ve spent some time on design while traveling. In the above test run I extended the tx bucket count from2^30 to 2^31, to increase active header RAM by 4GiB. I also performed a point duplicate search for 1 in 350 points during insert, with the above very successful result.
The actual implementation will extend the point hashmap header from 4 byte buckets to 6, with links remaining at 4 bytes and the additional two bytes for identifying buckets with potential duplicates. Since the map is 2^31 buckets, this will increase it from 8GiB to 12GiB, or an increase of 4GiB active headers, as included in the test.
However I’ve determined that this level of increase will dramatically reduce the duplicate search rate below the sampled 1/350. Out of 2.5 billion points 1/350 causes 2.5B/350 point hashmap body searches (these are costly and have been the central problem in confirmation all along). That’s stil ~7.7 million searches. However, the adjusted design will call for only about 30,000 searches total. Basically it’s like eliminating the search altogether.
1 reply · evoskuil · last Mar 13, 2025
evoskuil08:01
I just realized there’s an error here, so for the 4GiB header increase we’re going to hit about 1/350 when the table is full and 1/650 on average during population (still better than the simulation).
evoskuil05:36
I had looked at Bloom and Cuckoo, but it turns out that even tho B is more compact, C is much better given concurrency requirements, since it stores its filter in one a bucket, not bits all over the header.
I modified the Cuckoo design to store the filter in the hashmap bucket, and avoided a secondary kick of the filter in the case where it is populated, as given this amount of space and the Poisson nature of the hash functions, the simpler approach if much more efficient.
evoskuil05:42
I also took a close look at hash function behavior, specially the effect of the hash[23-31]:index[0-3] combiner to produce the hashmap hash, and use of hash[21-22] for the filter. These are both at least Poisson (the former is slightly better due to index or sequentiality), because of the nature of sha256. So this makes it easy to model the math. I also took the actual hash function distribution to verify its uniformity. It’s essential that the hashmap function and the filter hash function are independence, and these are perfectly so.
evoskuil08:01
replied to a thread: view
I just realized there’s an error here, so for the 4GiB header increase we’re going to hit about 1/350 when the table is full and 1/650 on average during population (still better than the simulation).
evoskuil15:37
I looked again at a monolithic 4GiB Bloom filter vs 4GiB of Cuckoo filtering at 2 per hashmap bucket, within each bucket. Bloom gave a good false positive rate and not good concurrency design, while Cuckoo had good concurrency design but poor FP rate. I finally realized we might be able to do mini Blooms in each bucket and get the best of both.
It seemed counterintuitive, but a single byte of Bloom filter per bucket, and a single Bloom function per element was as good as a 2 byte per element (on average) monolithic 4GiB filter using 7 hash functions.
(edited)evoskuil15:51
The filter is Poisson distributed by simply selecting the count of bits from any byte in the insert key (point) sha256 hash. Mod 7 of any sha256 byte should obtain positions 0,1,2,3,4,5,6,7 with Poisson distribution. Given that this is filtering only a single bucket, and bucket lengths don’t exceed 14, and are are massively weighted toward 0, 1, 2, 3 lengths, this gives us and excellent false positive rate, and still ensures no false natives across the bucket elements (conflict stack).
1 reply · evoskuil · last Mar 13, 2025
evoskuil15:54
The FP for Bloom is the rate at which we may have a duplicate and need to resolve the potential using the costly body search. This filter gives a 1 in 400 FP rate with the table “full” at 2.5 billion entries, and an average of 1 in 833 during table construction.
This is accomplished with 2GiB extra header. The trial run I did used 4GiB extra header and assumed a constant average FP rate of 1 in 350 while building the table (performing a search at that constant rate). This approach is half the size at significant less paging cost.
evoskuil16:02
So if the math holds up, this is a simple and very efficient complete solution to the confirmation problem. We retain a tiny list of double spent points and search them for each spend. Absent a tx pool this is almost always simply empty. At some point it may be necessary to make this table a hashmap itself, to control this search cost. So I’ll start with that but just use a trivial header.
evoskuil16:07
The Bloom implementation is a minor modification to the hashmap header, returning a Boolean on element insert (FP), casing the table to search the body on insert, and returning a Boolean as well (duplicate inserted). When the caller gets this positive result, it inserts the point into the duplicates hashmap. Synchronization in this aspect is already controlled by the block downloaded result transitioning into validate and confirm only when the points and block are fully written. Unconfirmed duplicate points cannot have been confirmed so will not interfere.
The FP can be cut in half by doubling the dedicated filter byte, or adding individual bits can increase it, so the table can be resized naturally over time as the chain grows.
Friday, March 14, 2025
C
cguida19:28
Have you looked at the filters used in bip157/8? My experience is that these are blazing fast and very accurate (they are the fastest way to do wallet rescans, by far), but they may not work as well for libbitcoin's doublespend detection as they do for finding transactions relevant to a set of output descriptors: https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki#specification
"Golomb-Coded Sets"
24 replies · cguida, evoskuil · last Mar 14, 2025
C
cguida21:03
If you could build some kind of index like that, but for spends, it could massively reduce the amount of data needed to be scanned on the first pass
(edited)C
cguida21:05
then if you hit a positive, you can check whether it's real or false. in my experience the false positive rate is configurable but can be very low, at the expense of a bit more computation.
again, not sure if any of this is helpful, but i'm just throwing out ideas
evoskuil21:07
You may not be aware but we already implement this, and support an index for it in the store.
evoskuil21:14
Populating the compact filters requires a total ordering by block for filter combination. Also population of the block portion requires all prevouts populated. Keep in mind that a duplicate detection for points must run during milestone as well, this type of solution would kill milestone sync.
(edited)evoskuil21:16
While it may be quick for a wallet, when reading the index, wallets don’t have 2.5 billion spends, and the cost to wallets doesn’t include the filter construction cost by the node/server.
👍 1
evoskuil21:17
The problem definition boils down to detecting (not preventing) duplicate points on tx insert to the store. It’s easily done, doing it while not thrashing by searching the point index is the challenge.
evoskuil21:19
This problem reduces to detecting a duplicate upon insert within a single bucket’s conflict list. These lists are 0-14 elements long, with 6-14 being irrelevant due to small quantity of them. 0 and 1 element lists are trivial, so it’s the 2-5 range that is the real cost.
evoskuil21:20
The 0-14 is probabilistic, and this expected outcome supported by a full scan of the table.
(edited)evoskuil21:27
Hashmap heads are randomly accessed during read and write. So they must be memory resident or head paging becomes an issue. During a milestone run it’s all write, no table lookups. During validation we are reading all tables, but the design lints hashmap searching to a very limited amount. Neither block population nor prevout population search the massive point table. So validation in a 5k block window operates efficiently within the remaining 16GB, completing in 7.5 hrs without double spend checks.
evoskuil21:28
But as soon as we add a constant paging through a 100GB table into the mix, it all goes sideways. Yet if we have detected all duplicates upon insert, there is no need to even access the table during confirmation.
evoskuil21:34
We can get away with another 4GB of random access header (I tested with this), which pushes the total to 20GB. But 8GB would put us at 24GB, leaving only 8 for block/prevout population and validation table searches. Even if that was sufficient, building the table is likely a major cost, especially since the final stage requires a total ordering by block. So to confirm a block we would have to construct all prior filters in order, and that means even for all milestone blocks (filters are cumulative).
evoskuil21:40
If not then that means also running every input in the block against the filter to detect the double spend.
evoskuil19:41
It’s already very fast, until we get to lower memory, and then paging is the issue. Large accumulators create the problem that we already have.
evoskuil22:59
Actually the compact filters would not be accessed like hashmap heads, they are more like the prevouts cash, which is accumulated with location (ie relative to the concurrency window) and would be read similarly. They can be block-associated using an array map as opposed to a hash map (I need to do this for the txs table as well, already done for the prevouts cache). This eliminates arbitrary paging to obtain the filter, just direct access from the header pk in an array head.
evoskuil23:04
So the total size isn’t nearly as much of an issue as with hashmap heads. And if it’s 8GB for the full chain is then pretty reasonable, like the prevout cache.
Ordering is the next big consideration. A block of filters can be created once all previous blocks are populated, same as validate, so I previously moved this aspect into the validation stage. The filter heads must be computed in order by block, like confirmation, so this was split into an independent table and integrated into the confirmation chaser.
evoskuil23:11
If the filter heads are required, then this would add a costly ordering constraint to confirmation. But I’m not even sure that the filters can actually aid in double spend detection. @pmienk do you recall enough about it to say?
Saturday, March 15, 2025
pmienk00:00
The existing filters as I recall don't solve the problem and a similar approach would require a linear scan through each block header for detection. Doesn't mean a formulation can't be made, but then you still need to either fragment the accumulator and linear scan or it'll necessarily become a massive memory cost.
I don't see where the fragmentation points are natural. The per block use case for bip157/8 helps with a pretty severe size restriction
👍 1
evoskuil00:17
If by linear scan you are referring to acquiring all of the spends to check against the accumulator, that’s already the case in the existing implementation. Even in the duplicate detection case we have to check every spend against the duplicate set (unless of course it’s empty).
(edited)pmienk01:08
No, bip157/8 generates an accumulator per block. Linear scan would be checking each block accumulator, an effective linear header scan (while parallelizable, not efficient).
(edited)👍 1
evoskuil17:33
Looking at the most optimal filtering of the point table for duplicates, it appears that Bloom filtering, while logically the simplest approach - basically what its designed for, is very inefficient. This is because the data is necessarily stored in a hashmap (for at least allowing efficient resolution of false positives), and a global bloom filter would not be taking advantage of the prefiltering by hashmap bucket. Using bloom filters within a bucket, for the same overall size of the filters, is also functional and inefficient. The filter becomes quickly saturated at higher k values and at lower values has a very high false positive rate.
The other approach I’ve looked at is more like a Cuckoo filter, where there is a hash function result stored in the header bucket. This takes advantage of the pre-filtering by hashmap bucket. For a single 32 byte hash result, using key data independent of the hashmap hash function, it is also very inefficient, since probability of matching independent conflicts with a bucket is very low. The filter is applied to the first element in the list (and any other that matches it, which is 1 in 2^32 and no others. So false positives are around 1 in 2.5.
evoskuil17:44
However, using a smaller hash digest for the Cuckoo filter, and associating multiple of these to the conflict list, the efficiency per filter bye is much higher. For example, four one byte filters, each with a sentinel value, allows match of 4 independent conflicts in each conflict stack. Also a small number of distinct values that hash to the same value (1 in 255). This allows capture of slightly more than all values in conflict lists of 1,2,3 and 4 elements. Zero elements doesn’t require a filter. Above 4 elements is very small. This allows us to avoid conflict resolution for all but 1 in 255 single value lists, 2 in 255 for 2 element lists, 3 in 255 for 3, 4 for 4. No exclusion for 5 and above. This gives us a search rate of 1% for a full table, and 1 in almost 200 on average for table population from zero.
This requires twice the filter size as I tested with and averages 1/200 vs a constant rate of 1/350. However I may be able to increase hashmap load factors without affecting sync and validation rates, offsetting the head memory increase.
And the search rate is higher, so this will have an impact, but the previous run had almost no cost, so this may still be sufficient.
I’ve also noticed that I can change the txs, bk_validated, and strong_tx hashmaps can be converted to array maps, eliminating hashmap traversal during validation.
This also reduces table memory cost, since arraymap heads aren’t accessed randomly.
(edited)Monday, March 17, 2025
evoskuil16:02
I believe I have an efficient build of a (generally empty) duplicate table now, which can populate during milestone sync on the mini and very small cost, and allows full validation on the mini in under 10 hours (Core is 15). This is based on runs simulating the point table search load and head size, as it's not implemented yet. But the simulation should be sufficient for modeling the behavior.
I've figured out a general technique to reduce the body search cost of false positive duplicate resolution during insert as a function of head size, from (for example) 40% of the full table down to 0.15%, for a load factor 1.5 hashmap, by just doubling the head size and performing some magic in the head template. So for a modest head size increase we can detect all duplicates upon insert, and the time cost is negligible, for milestone and full validation on the mini, around 10%.
(edited)👀 1
It'll take me several days for the implementation, but I think this longstanding issue finally has an answer.
🔥 1
evoskuil21:35
Here's a plot of the simulated cost at various search rates lower rate means higher head size. The lowest (1 in 1000 with no validation window) is 48 minutes for the full sync. 1 in 500 is probably more realistic.
This is the simulation with effect on full validation. I'm going to run 1 in 100 again until completion. 1 in 1 is searching every table entry for duplicates (the first attempt) - so without the fancy new filtering. These are adding about 1-1.5 hrs to full validation. The remaining confirmation cost is small. Whole thing should def complete full download validate/confirm in under 10 hrs on the mini. Maxi is currently 4.5 hrs.
🙌 2
evoskuil22:32
Also, this could be bypassed in the case of milestone sync on the mini (or altogether on the maxi). It's really just an optimization for mini full validation sync.
👍 1
Wednesday, March 19, 2025
evoskuil05:56
I've discovered that the point table hash function was not as expected, but that the previous bucket scans were reporting results as expected. The proper distribution is shown in green, actual distribution in orange. I haven't had a chance to measure the cost yet, but I expect it was significant. In other words, fixing this should yield a significant improvement - before even applying the above hashmap optimization.
👀 1
Also I've updated the previous tables. I re-reran the validation 1/100 (to complete it) and 1/550 (because it was anomalous) runs, added a couple more runs, and organized a bit. The behavior is consistent and expected.
👀 1
The above runs were processed against the point table with its flawed hash function. The cost of table searches is significantly higher than necessary as a result.
(edited)Thursday, March 20, 2025
evoskuil08:26
I resolved the point table hash function issue, and have been running additional simulations of the search function. Performance is materially improved by that fix. Roughly it means the cost of 1 point search in 500 (during download writing to the store) is now about the same cost as 1 in 1000 previously.
(edited)evoskuil08:40
The test runs I've been doing are with header expansion of 4GiB, and with a certain number of table searches per insert. It looks the impact of 500 searches per insert is about a 10% additional time cost for both milestone and validation sync. The new hashmap filter design can achieve an average search rate across the whole table build, of 1 in 670 at a net header size increase of 4GiB (1 in 355 when the table is full).
evoskuil08:45
Confirmation is additional execution beyond this, but it's very small, and there's no additional cost for this double spend check unless a duplicate is found, and that never happens on a typical run. I think we should be able to hit 8-9 hours full validate/confirm on the mini, and time should go down slightly from 4.4 hrs on the maxi.
(edited)
Huddle with pmienk, evoskuil, cguida, Marnix · 190 min19:54
14 replies · cguida, evoskuil · last Mar 20, 2025
C
cguida21:28
This looks great! Looks like ~10 hours for full validation/confirmation on the mini?
👍🏻 1
C
cguida21:48
Yeah core is working on cluster mempools, to provide a better solution to generating block templates
evoskuil22:32
Clustering mempools is just a weird way to say, search the graph for the most valuable mine-able subset(s).
Saturday, March 22, 2025
This shows the projected hashmap filtering efficiencies for a LF 1.5 table, for filters of 1-4 bytes, as a function of fingerprint vs. sentinel bits. At this load factor, 3 sentinel bits is most efficient, with a very slight advantage for 4 bits in the 32 bit filter. The optimal configuration varies slightly by load factor, and of course search rate will increase with load factor and/or decrease with filter size.
evoskuil23:28
As we are filtering in the construction of the table, the LF starts at 1 and progresses (e.g. to 1.5) as the table populates. Given the presumption of almost no duplicates ("true positives"), the FP rate indicates the ratio of body searches to inserts while building the table. The FP rate is a non-linear monotonically increasing function of the LF. Basically like any hash function, an increasing load factor increases the search cost from constant toward linear.
Given the presumption that nearly all searches will be negative, it follows that each search exhausts a bucket's conflict list - where the LF is the average conflict list length. So search cost (i.e. paging) is the product of the LF and FP rate or x * y on the above graph.
👀 1
1 reply · evoskuil · last Mar 23, 2025
Relative to an arbitrary LF 1 table, the cost when the table is empty is smaller, and higher as it gets bigger. This is of course managed over long periods of time by increasing configured hashmap bucket count and/or filter size.
evoskuil23:42
The most significant of these plots is the first, showing how dramatically search cost of a Poisson distribution can be reduced using cascading filters. This is dramatically more efficient than both Bloom filtering (and Cuckoo filtering), and preserves the ability to use memory fencing to protect inserts. This is because it does not waste any bits, and aligns the filter rate closely to the Poisson distribution - staving off saturation much longer.
(edited)💥 1
Monday, March 24, 2025
N
noah.308:03
“A visual representation of the Ulam spiral, also known as the prime spiral. It's a graphical depiction of the prime numbers in a spiral arrangement on a grid.”
🤓 1
evoskuil17:24
Take a 32 bit word. Split into a 4 bit counter (y axis) and a 28 bit field (x axis). For each row divide x into y equal length segments (identified by color), with larger segments (due to rounding) aligned to the left. Segments may be disjoint horizontally. A segment must descend vertically from an ancestor, with only one originating segment per row. Origins are selected greedily from right-to-left. Segments are numbered for the color-blind. The choices of alignment (e.g. left, right-to-left above) are arbitrary, having no effect on function.
(edited)
evoskuil18:47
This produces the following matrix:
using screen_t = std_array<uin32_t, 16>;
using matrix_t = std_array<screen_t, 16>;
constexpr matrix_t matrix
{
screen_t
{
// 1
0b0000'1111111111111111111111111111
},
{
// 2
0b0000'1111111111111100000000000000,
0b0000'0000000000000011111111111111
},
{
// 3
0b0000'1111111111000000000000000000,
0b0000'0000000000000011111111100000,
0b0000'0000000000111100000000011111
},
{
// 4
0b0000'1111111000000000000000000000,
0b0000'0000000000000011111110000000,
0b0000'0000000000111100000000011100,
0b0000'0000000111000000000001100011
},
{
// 5
0b0000'1111110000000000000000000000,
0b0000'0000000000000011111100000000,
0b0000'0000000000111100000000011000,
0b0000'0000000111000000000001100000,
0b0000'0000001000000000000010000111
},
{
// 6
0b0000'1111100000000000000000000000,
0b0000'0000000000000011111000000000,
0b0000'0000000000111100000000010000,
0b0000'0000000111000000000001100000,
0b0000'0000001000000000000010000110,
0b0000'0000010000000000000100001001
},
{
// 7
0b0000'1111000000000000000000000000,
0b0000'0000000000000011110000000000,
0b0000'0000000000111100000000000000,
0b0000'0000000111000000000001000000,
0b0000'0000001000000000000010000110,
0b0000'0000010000000000000100001001,
0b0000'0000100000000000001000110000
},
{
// 8
0b0000'1111000000000000000000000000,
0b0000'0000000000000011110000000000,
0b0000'0000000000111100000000000000,
0b0000'0000000111000000000001000000,
0b0000'0000001000000000000010000100,
0b0000'0000010000000000000100001000,
0b0000'0000100000000000001000100000,
0b0000'0000000000000000000000010011
},
{
// 9
0b0000'1111000000000000000000000000,
0b0000'0000000000000011100000000000,
0b0000'0000000000111000000000000000,
0b0000'0000000111000000000000000000,
0b0000'0000001000000000000010000100,
0b0000'0000010000000000000100001000,
0b0000'0000100000000000001000100000,
0b0000'0000000000000000000000010011,
0b0000'0000000000000100010001000000
},
{
// 10
0b0000'1110000000000000000000000000,
0b0000'0000000000000011100000000000,
0b0000'0000000000111000000000000000,
0b0000'0000000111000000000000000000,
0b0000'0000001000000000000010000100,
0b0000'0000010000000000000100001000,
0b0000'0000100000000000001000100000,
0b0000'0000000000000000000000010011,
0b0000'0000000000000100010000000000,
0b0000'0001000000000000000001000000
},
{
// 11
0b0000'1110000000000000000000000000,
0b0000'0000000000000011100000000000,
0b0000'0000000000111000000000000000,
0b0000'0000000111000000000000000000,
0b0000'0000001000000000000010000100,
0b0000'0000010000000000000100001000,
0b0000'0000100000000000001000000000,
0b0000'0000000000000000000000010010,
0b0000'0000000000000100010000000000,
0b0000'0001000000000000000001000000,
0b0000'0000000000000000000000100001
},
{
// 12
0b0000'1110000000000000000000000000,
0b0000'0000000000000011100000000000,
0b0000'0000000000111000000000000000,
0b0000'0000000111000000000000000000,
0b0000'0000001000000000000010000000,
0b0000'0000010000000000000100000000,
0b0000'0000100000000000001000000000,
0b0000'0000000000000000000000010010,
0b0000'0000000000000100010000000000,
0b0000'0001000000000000000001000000,
0b0000'0000000000000000000000100001,
0b0000'0000000000000000000000001100
},
{
// 13
0b0000'1110000000000000000000000000,
0b0000'0000000000000011100000000000,
0b0000'0000000000110000000000000000,
0b0000'0000000110000000000000000000,
0b0000'0000001000000000000010000000,
0b0000'0000010000000000000100000000,
0b0000'0000100000000000001000000000,
0b0000'0000000000000000000000010010,
0b0000'0000000000000100010000000000,
0b0000'0001000000000000000001000000,
0b0000'0000000000000000000000100001,
0b0000'0000000000000000000000001100,
0b0000'0000000001001000000000000000
},
{
// 14
0b0000'1100000000000000000000000000,
0b0000'0000000000000011000000000000,
0b0000'0000000000110000000000000000,
0b0000'0000000110000000000000000000,
0b0000'0000001000000000000010000000,
0b0000'0000010000000000000100000000,
0b0000'0000100000000000001000000000,
0b0000'0000000000000000000000010010,
0b0000'0000000000000100010000000000,
0b0000'0001000000000000000001000000,
0b0000'0000000000000000000000100001,
0b0000'0000000000000000000000001100,
0b0000'0000000001001000000000000000,
0b0000'0010000000000000100000000000
},
{
// 15
0b0000'1100000000000000000000000000,
0b0000'0000000000000011000000000000,
0b0000'0000000000110000000000000000,
0b0000'0000000110000000000000000000,
0b0000'0000001000000000000010000000,
0b0000'0000010000000000000100000000,
0b0000'0000100000000000001000000000,
0b0000'0000000000000000000000010010,
0b0000'0000000000000100010000000000,
0b0000'0001000000000000000001000000,
0b0000'0000000000000000000000100001,
0b0000'0000000000000000000000001100,
0b0000'0000000001001000000000000000,
0b0000'0010000000000000000000000000,
0b0000'0000000000000000100000000000
},
{
// 16
0b0000'1100000000000000000000000000,
0b0000'0000000000000011000000000000,
0b0000'0000000000110000000000000000,
0b0000'0000000110000000000000000000,
0b0000'0000001000000000000010000000,
0b0000'0000010000000000000100000000,
0b0000'0000100000000000001000000000,
0b0000'0000000000000000000000010010,
0b0000'0000000000000100010000000000,
0b0000'0001000000000000000001000000,
0b0000'0000000000000000000000100001,
0b0000'0000000000000000000000001100,
0b0000'0000000001000000000000000000,
0b0000'0010000000000000000000000000,
0b0000'0000000000000000100000000000,
0b0000'0000000000001000000000000000
}
};A
Antoine Poinsot20:15
Does libbitcoin enforce transactions' locktime since genesis or since block 31,000?
11 replies · Antoine Poinsot, evoskuil · last Mar 25, 2025
A
Antoine Poinsot20:56
evoskuil22:16
Absolute height locktime ("finality") was implemented in Satoshi's first release ("First commit" in GitHub/bitcoin dated 29 AUG 2009).
class CTransaction
{
public:
...
int nLockTime;
...
bool IsFinal() const
{
if (nLockTime == 0 || nLockTime < nBestHeight)
return true;
foreach(const CTxIn& txin, vin)
if (!txin.IsFinal())
return false;
return true;
}
...
};
class CTxIn
{
public:
...
bool IsFinal() const
{
return (nSequence == UINT_MAX);
}
...
};
This was modified to include absolute timestamp locktime in a commit on 18 OCT 2009 and subsequently released as v0.2.0 on 13 DEC 2009. It also included a change of
nLockTime type to unsigned.
class CTransaction
{
public:
...
unsigned int nLockTime;
...
bool IsFinal(int64 nBlockTime=0) const
{
// Time based nLockTime implemented in 0.1.6,
// do not use time based until most 0.1.5 nodes have upgraded.
if (nBlockTime == 0)
nBlockTime = GetAdjustedTime();
if (nLockTime == 0)
return true;
if (nLockTime < (nLockTime < 500000000 ? nBestHeight : nBlockTime))
return true;
foreach(const CTxIn& txin, vin)
if (!txin.IsFinal())
return false;
return true;
}
...
};
Block 31,000 was mined on 22 DEC 2009. This is nine days after the tag applied to v0.2.0, and between the tags of v0.2.5 and v0.2.6. So it seems you are referring to enforcement of time-based absolute locktime (block time, as MTP didn't arrive until BIP113) around this approximate block height.
Libbitcoin doesn't implement activation for various forks during this period, as they were just released without activation and themselves applied to all blocks. We do have plans to do so at some point, and have stubbed in several, for historical/educational purposes. To my knowledge bitcoind has also never applied these forks conditionally.
So absolute block locktime was always active, it was forked in v0.2.0 to include time, and that was immediately applied to all blocks. At the time time the integer was also forked from signed to unsigned comparisons (and a validation failure introduced to support it).
// To help v0.1.5 clients who would see it as negative number. please delete this later.
if (nLockTime > INT_MAX)
return error("AcceptTransaction() : not accepting nLockTime beyond 2038");evoskuil22:20
Of course Satoshi could not have made these changes because he has no idea what a signed integer is.
A
Antoine Poinsot13:39
So absolute block locktime was always active, it was forked in v0.2.0 to include time
No it was not. 🙂 The block locktime was not enforced by consensus in the first release. It was only enforced when creating a block, not when validating it. In other words this was mining policy, not consensus.
The enforcement by consensus was made at the same time the field was repurposed to also optionally consider time, in commit
cc0b4c3b62367a2aebe5fc1f4d0ed4b97e9c2ac9 . This change was a soft fork which activated on block 31,000. Had it been enforced by consensus before, the change to include time would have been a hard fork.A
Antoine Poinsot15:38
Turns out Satoshi even later shifted the soft fork height to a later one in commit
b075bbf9862df41cdf5265026ba787b7d0fecb07. Technically a hard fork, but at this time all new releases were hard forks due to OP_VER anyways.A
Antoine Poinsot15:42
and that was immediately applied to all blocks.
Bitcoin Core started validating it from the genesis block in commit
cb420a1dfc23d3c11c5281ed8f7ae003c2f61594 (February 2010). Before that it was only applied from block 36,001, starting with commit b075bbf9862df41cdf5265026ba787b7d0fecb07. Before that it was only applied from block 31,001.evoskuil16:10
Thanks for the additional info. I hadn’t looked into it before. Libbitcoin started in 2011 so we were well past the point that it had been retroactively applied to all blocks, so I wasn’t aware of the prior variations. As I mentioned, I have tasks to implement various lost forks (all of our forks are conditionally applied via config). Though digging through the code to isolate them can be a challenge. Just setting the limit at v0.2.0 is a lot.
A
Antoine Poinsot16:14
And in my BIP i write that all implementations i'm aware of enforce this since genesis, so i wanted to check first.
👍🏻 1
evoskuil22:16
replied to a thread: view
Absolute height locktime ("finality") was implemented in Satoshi's first release ("First commit" in GitHub/bitcoin dated 29 AUG 2009).
class CTransaction
{
public:
...
int nLockTime;
...
bool IsFinal() const
{
if (nLockTime == 0 || nLockTime < nBestHeight)
return true;
foreach(const CTxIn& txin, vin)
if (!txin.IsFinal())
return false;
return true;
}
...
};
class CTxIn
{
public:
...
bool IsFinal() const
{
return (nSequence == UINT_MAX);
}
...
};
This was modified to include absolute timestamp locktime in a commit on 18 OCT 2009 and subsequently released as v0.2.0 on 13 DEC 2009. It also included a change of
nLockTime type to unsigned.
class CTransaction
{
public:
...
unsigned int nLockTime;
...
bool IsFinal(int64 nBlockTime=0) const
{
// Time based nLockTime implemented in 0.1.6,
// do not use time based until most 0.1.5 nodes have upgraded.
if (nBlockTime == 0)
nBlockTime = GetAdjustedTime();
if (nLockTime == 0)
return true;
if (nLockTime < (nLockTime < 500000000 ? nBestHeight : nBlockTime))
return true;
foreach(const CTxIn& txin, vin)
if (!txin.IsFinal())
return false;
return true;
}
...
};
Block 31,000 was mined on 22 DEC 2009. This is nine days after the tag applied to v0.2.0, and between the tags of v0.2.5 and v0.2.6. So it seems you are referring to enforcement of time-based absolute locktime (block time, as MTP didn't arrive until BIP113) around this approximate block height.
Libbitcoin doesn't implement activation for various forks during this period, as they were just released without activation and themselves applied to all blocks. We do have plans to do so at some point, and have stubbed in several, for historical/educational purposes. To my knowledge bitcoind has also never applied these forks conditionally.
So absolute block locktime was always active, it was forked in v0.2.0 to include time, and that was immediately applied to all blocks. At the time time the integer was also forked from signed to unsigned comparisons (and a validation failure introduced to support it).
// To help v0.1.5 clients who would see it as negative number. please delete this later.
if (nLockTime > INT_MAX)
return error("AcceptTransaction() : not accepting nLockTime beyond 2038");Tuesday, March 25, 2025
evoskuil07:06
I've completed a test implementation of the fancy filter. I went with 28 bits of filter and 4 bits of sentinel in a 32 bit word. Generated some test data and ran it in constexpr and runtime tests all the way to 10 fingerprints populated (out of 16 possible). Behavior correct and implementation very simple and low computation. The above matrix was an effort to prevent the need to shift values as the filter grows, which works nicely.
The insert function code is mostly:
// Both indexes are screen selector, as each new screen adds one mask.
const auto mask = matrix[selector][selector];
// Merge incremented selector, current sieve, and new fingerprint.
sieve = bit_or
(
shift_left(selector, screen_bits),
bit_and
(
selector_mask,
bit_or
(
bit_and(print, mask),
bit_and(sieve, bit_not(mask))
)
)
); (edited)The main check function code is mostly:
// Compare masked fingerprint to masked sieve, for all masks of the screen.
for (auto mask = zero; mask <= selector; ++mask)
if (bit_and(print, matrix[selector][mask]) ==
bit_and(sieve, matrix[selector][mask]))
return true;I've already done most of the work in the node to allow this to drop in, at least with byte alignment. We can get some more efficiency (one more bit on the point table) by allowing bit-alignment within the hashmap head - which will allow the filter to share a byte with the bucket link. But this will provide a good perf test one integrated. Hopefully I can get that done tomorrow.
The implementation uses a two dimensional table of one word masks, which is 16x16 for a 4 bit sentinel, 50% populated. Should be able to hang this off an implementation template and generate at compile time. For this run I produced it manually from the spreadsheet (in the thread above). I also put a bunch of test cases against the data to make sure it's kosher.
A
Antoine Poinsot13:39
replied to a thread: view
So absolute block locktime was always active, it was forked in v0.2.0 to include time
No it was not. 🙂 The block locktime was not enforced by consensus in the first release. It was only enforced when creating a block, not when validating it. In other words this was mining policy, not consensus.
The enforcement by consensus was made at the same time the field was repurposed to also optionally consider time, in commit
cc0b4c3b62367a2aebe5fc1f4d0ed4b97e9c2ac9 . This change was a soft fork which activated on block 31,000. Had it been enforced by consensus before, the change to include time would have been a hard fork.A
Antoine Poinsot15:42
replied to a thread: view
and that was immediately applied to all blocks.
Bitcoin Core started validating it from the genesis block in commit
cb420a1dfc23d3c11c5281ed8f7ae003c2f61594 (February 2010). Before that it was only applied from block 36,001, starting with commit b075bbf9862df41cdf5265026ba787b7d0fecb07. Before that it was only applied from block 31,001.evoskuil16:10
replied to a thread: view
Thanks for the additional info. I hadn’t looked into it before. Libbitcoin started in 2011 so we were well past the point that it had been retroactively applied to all blocks, so I wasn’t aware of the prior variations. As I mentioned, I have tasks to implement various lost forks (all of our forks are conditionally applied via config). Though digging through the code to isolate them can be a challenge. Just setting the limit at v0.2.0 is a lot.
Wednesday, March 26, 2025
evoskuil03:02
Clean implementation as a class complete, with full test coverage using generated vectors. Still need to write code to generate the mask matrix based on template arguments (current matrix is manually generated for 32:4. https://github.com/evoskuil/libbitcoin-database/blob/master/include/bitcoin/database/impl/primitives/sieve.ipp
👀 1
evoskuil22:28
I just completed the
(edited)consteval function to generate the mask table for the fancy filter, and compressed the table by ~50%, as it is a sparsely-populated 2 dimensional matrix. The final implementation matches exactly the manually-generated table (below), though it also adapts based on template arguments for the filter size. Extensive text coverage also. The implementation is simple and performant. Hopefully it does what I think it will do, integrating into the hashmap template and the adding to the point table now.
🙌 2
Thursday, March 27, 2025
evoskuil06:23
Integrating the fancy filter into the hashmap means that any extra (pad) bytes in the head buckets of any hashmap table will automatically get used for filtering. Eventually I'll increase this to any pad bits, with the ability of the filter to share a byte with the bucket links. Currently they are isolated on a byte boundary, but at most this is wasting one bit across all tables. The current point filter can then go from 32 bits to 33, doubling it's efficiency. Assuming it works at all ;).
evoskuil06:34
I've just completed final integration into the hashmap template, with a couple updates to test cases that map full memory layout to the test. Just required adding the filter value to the header, validated_bk, and txs tables, which now have 1, 1 and 3 byte filters respectively. There should be no impact to unfiltered hashmaps (ones which are bucket-aligned on word boundaries without padding), since code should drop out entirely as consequence of conditioning execution on template args.
I don't expect there to be material performance advantages for the other three affected headers above, as the filtering only reduces cost for expected negative search results. We don't do much of that in sync/validation, apart from the
(edited)point table. There is some in the validated_bk table, as we check block state for validation/confirmation. However this is minor, and I am planning to replace this and the validated_tx and txs tables with the new arraymap (which was devised for prevout caching, but will advantage any other table indexed search-indexed with another table's surrogate key - since these are sequential). However the filtering will significantly reduce negative search cost for general purpose hashmap queries.evoskuil06:51
I haven't yet changed the bucket function back to modulo from the base2 sizing and bit mask (vs. mod) truncation. So I can't yet offset any of the the head size increase with an increase in load factor. So it will go from 8 to 16 GiB, which is 4 GiB more than I simulated with. This won't affect the maxi though, and I'll soon have a measure of actual point table search reduction.
evoskuil09:43
I was just running some tests, after adding some good instrumentation to measure hit rates. The rates were much lower than I expected. Then I realized that I used the same hash function for buckets and filters (I had a TODO to change it). But even so was getting a significant search reduction. Was around 1% of inserts, up to 25% now as about half done. Still, with identical hash functions that's pretty good... Everything that lands in a bucket is re-filtered on that landing criteria - which are all identical. So basically it's only applying one filter out of the 16 possible. I'll fix it up and run again in the morning.
evoskuil16:56
I realized that the above isn't even using one filter, since the matching hash results in 100% collision with the first filter, so as if no filter at all. Got a good baseline though, the average search rate over the build of the table is 42.4% (of all inserts result in a body search). That's not 100% because all buckets are empty initially, and the search is only performed on the pre-insert conflict list. Also, on the maxi, the filter computations plus the high search rate, did not measurably affect the milestone run (50 minutes).
(edited)👀 1
Huddle with pmienk, evoskuil, cguida, Marnix · 142 min19:54
Friday, March 28, 2025
evoskuil06:46
@pmienk and I did some pair programming today on the fancy hashmap filter. We made two minor changes, one that was reverted after testing (with a slight refactor and to make it more obvious) and the other that slightly improved the efficiency of the filter.
I mentioned that I was planning to refactor the
(edited)sieve class into a static class (basically a templatized namespace) because it holds no dynamic state. I've completed that, which simplified the code and maybe gave tiny perf boost. I also updated tests, refactored, and added better runtime instrumentation to measure the filter perf.
I then got into the runtime debugger and quickly confirmed that the filter was not actually having an effect (which was nice to confirm). I was not returning the right value from the header updating method. I also handled an error condition that I mentioned had been commented out. These required a minor refactor of the hashhead and hashmap templates. This made things pertaining to the filter quite a bit simpler.
It's now all together and checked in, and I'm running for the first time at full milestone speed and concurrency on the maxi and with good instrumentation. Passing block 450k I've got a couple quick data points:
369 / (322040940 + 369) <= this is ratio of point searches to total point writes passing block 400k. That's 1.14 / 1,000,000 = 0.00014% . Passing 450k it's 1757 / (484908338 + 1757) or 0.00036% . And 450k the baseline time is generally around 650 seconds, and with this change (which includes 8 GiB of extra header), we're at 656 seconds. Well within typical deviations.500k, on time at
(edited)0.0013% search rate. CPU 28% which is also typical.550k, on time (1123 vs. 1112 baseline secs) at
0.0022% search rate.evoskuil07:01
The parameters for this are a 32 bit sieve, with a 4 bit screen selector (leaving 28 bits of screen). The load factor upon completion is
1.223, with 2,627,207,611 points therefore 2,147,471,459 hashmap buckets. The sieve doubles the hashhead cell size from 4 bytes to 8, and therefore uses an extra 8GiB of header. This should be reduceable by up to half without a huge hit, just by increasing the table load factor, though I need to revert to modulo bucket selection to get this. The sieve can then also get twice as efficient by adding one more screen bit, by borrowing it from the bucket link.Under these parameters the spreadsheet predicts a search probability - when the table is full - of
0.21% and estimates half that for average probability across the build of the table. The above ratios are comparable to that halving, or a target of 0.1%.700k, on time (within 5 secs) at
0.014% search rate.evoskuil07:16
750k, on time (within 4 secs) at
(edited)0.024% search rate - about 75% of points written. CPU still 28%.800k, on time at
0.037% search rate - about 85% of points written.evoskuil07:33
850k, 54 minutes,
1,552,144 point searches (duplicate detection) out of 2,626,357,610 non-coinbase points, for an actual average false positive rate of 0.0591%. Not too far off the ballpark estimate of cutting the full table calculation of 0.21% in half. Given that we know the actual buck distributions, and know that the sieve hash function is both independent and even, the full table calculation should be exact, but currently I'm only able to measure the cumulative rate, not the rate when the table is full.Also there are a couple minor filter advantages that aren't accounted for in the spreadsheet. (1) there is now a 16th useful screen (reserved for sentinel in the spreadsheet), and (2) there are efficiencies from values items that may overlap independent masks in a given screen.
evoskuil07:48
I'm about to give it a go on the mini (despite the header memory being about twice what I would like). Give the above numbers previous simulations, this already looks better than what I was hoping for.
👀 1
evoskuil08:17
Running on the mini it became apparent that something was off. Despite the exact same search rate, performance was very slow due to disk thrashing. Turns out I hadn't actually reduced the actual searches, I was just reporting the reduction. So I just made that simple change. But all the great numbers above on the maxi are based on execution of search for every point insert. So that time will get a little better on the maxi, even though it was close to typical.
evoskuil09:00
Mini was slower than I'd expect given the search rate is much lower than I simulated, but the head size was increased by double what I simulated (+8 vs. +4GiB). This means a 24GiB total head size, which is clearly too big for the 32GiB machine, since the heads are almost always memory resident. So To easily get it down I dropped a bit from the point table buckets, which cue the entire table down to its original size (+0) at the cost of doubling the load factor. But because the LF only affects search, and our search rate is so low, it seemed like a good test.
Comparing it to the 1/1000 and +4GiB head search simulation, it's beating it, and that's a 51 minute total run - about as good as it gets without changing to an open window. Passing 500k it's a minute ahead of the benchmark and searching at
0.0083% (vs. 0.0013% at half the LF).That's a tremendously good rate still, and the run looks maximal, passing 500k at
(edited)0.02% search rate, and still ahead of benchmark.
evoskuil09:09
With deduplication, the LF really only affects this one search. There's only trivial point table lookups once it's de-duped. So if this holds through the run, it should be a win. It's passing 650k a couple minutes now ahead of baseline, and at
0.077% search rate.evoskuil09:31
Passing 750, about 75%, with a
(edited)0.22% search rate, which is about 1 in 500 average (much higher immediate). But still a minute ahead of the 1 in 1000 simulation. Also, this is a copy of the previous analysis on effect of increasing LF. It's pretty moderate, and with 2.446 LF I'd expect to see it end up around 0.8% over the run.
When I started on this aspect, I was just looking to hit 1% false positive rate with like a 50% increase in head size. Looks like this will beat that with a 0% increase in head size.
800k at
0.34% now, 3 minutes behind baseline.evoskuil10:02
Really started to bog down after 800k, but still very respectable. I'm sure that by just splitting the difference on the load factor (once I go back to modulo buckets) we'll hit the simulation run. 2.45 is a pretty high factor and it not only increases the search rate but also the cost (plot above) due to longer exhaustive searches.
The run just completed on the mini in 69 minutes and 18 sec shutdown, (vs 54 min baseline for the 1/500 search, 67 baseline for the 1/250 search) and at an average overall FP rate of
(edited)0.53% , which means probably over 1.0% toward the end. Over 1/100 is a bit too high, but will def come down with the LF.👀 1
evoskuil16:33
On the maxi, fixing the search issue from the previous and increasing the LF 2x resulted in a 51 minute run (vs. 54), which is the same as benchmark on the maxi - with no store size change at all. Same store size, same milestone sync. And this means that the full validation time loses entirely the point table search. I'll take me some time to connect some full validation dots, but I should be able to run a maxi simulation to now give us a new record full validation run.
evoskuil16:45
Also note that the fancy filter is actually running on 4 tables, not jus the point table. Though only the point table is performing duplication detection. This means that validation searches on the other tables (txs, validated_bk, header) are also affected, presumably positively. The former was wasting 3 bytes per bucket, and the others just 1 byte. That's now filter space. Soon the former two tables will become arraymaps, which will eliminate search on them altogether.
🔥 1
evoskuil16:52
So now just need to add the nearly-always-empty point duplicate table, and read it during confirmation, and confirmation will be fully functional with actual performance. But the performance cost of those steps will be zero.
evoskuil16:58
Also note that on the maxi, full validation had gone from 4.4 hrs to 16.3 hrs when dropping to 128GiB RAM. I expect that the RAM impact will now be far lesser on the maxi. I've fired up a full validation from with the 2x LF point header to see if the record time drops, then I'll take a look at lower RAM.
👀 1
Sub 1 hr IBD on a $350 machine anywhere.
💥 1
evoskuil20:57
Almost complete with full validation on the maxi, and it's running almost identical to the record rate (4.4 hrs). Not surprising since the full query method is so efficient when not paging. The real difference will become more apparent with low RAM, as it was with the mini. Next full will be the same full validation run on the mini (will with the high LF).
(edited)It just finished 5 minutes ahead of the previous record (4.37 hours full validation - previous was 4.44 hrs). Shutdown 97 seconds. 🙂
(edited)evoskuil23:46
Here's a much better representation of the false positive rate over the entire range of the chain as it grows. As I had guessed, the late average was over 1% (about 1.1%). The overall average was
0.53% but this better represents the more costly late behavior. It didn't start falling behind the benchmark until around the 0.8% instantaneous false positive rate rate. That many searches leads to thrashing.
Saturday, March 29, 2025
evoskuil00:03
But this is with the 2.446 load factor, which doubles the search cost and increases the fp rate in order to save memory. The 1.223 normal load factor used 8GB extra RAM. I had tested with 4GB extra RAM for the sieve, and that can be achieved at a LF between these two, once I change to modulo buckets. That should not only keep the rate below .8% at the late stage, but will also cut the cost per search in half.
evoskuil04:09
Mini validation is 75% complete and confirmation 50% complete, with validations about 30 minutes behind the times of the record validation only run. In the current config, download is gated on a 5k validation window, but confirmation just fills in as CPU is available (during validation gaps). So I expect validation to continue at the same rate until completion, allowing confirmation all CPU to finish up quickly. I'm estimating that puts the full run at about +1 hour, or 9 hours total. This is with the suboptimal point load factor, so might bog down a bit toward the end, but that primarily affects download/archive rate, which is not the gating factor on validation - that's CPU. Completing 50% of confirmation at only a +30 minute net cost is pretty good, about what I estimated.
(edited)👀 1
I expect archive/validate to continue close to linearly, and for the conformation slope to immediately shallow significantly and proceed linearly until complete.
But archive/validate may bend upward in the 800s as a consequence of the point table load factor.
evoskuil15:15
Finished full validation on the mini (32GB, shani/avx512, Win11) in 9.4 hours. I'm pretty sure I can get this down to 9 hours with the LF change.
This compares to 15 hours for Core. Core on same box with Linux is 10 hours assume valid, and IIRC ~11 full validation.
🎉 1
3 replies · cguida, evoskuil · last Mar 29, 2025
C
cguida16:49
Doing full validation/confirmation faster than Core with assumevalid is a hilarious result
evoskuil17:51
Ha, nice observation. But very true. The most expensive part of validation in Core is not the signature validation, it's the total ordering imposed by the utxo store.
As I predicted with the rapid confirmation. Confirmation is now almost nothing. It's not what's pulling download/validation up, that's the increased point table insert cost (due to duplicate detection). Once validation completes, confirmation races ahead, taking 13 minutes to confirm the last 125k blocks (about 30% of the chain by volume). So confirmation phase cost is really just about 40 minutes, and the other part of the increase is the point table de-duplication (50 minutes).
(edited)👍 1
Also, 6 second shutdown (mini is lower memory, so it dumps a full 32GB of flushed mmap this fast).
🔥 1
This is huge!!
👍🏻 1
evoskuil17:49
Well once it's flushed there's really not much else to do. It's not like individually destructing billions of independent allocations for C++ objects, it's just a few large sheets of RAM. And virtual memory flushing happens continuously in the background, so when there's spare time during the sync, it's getting utilized.
(edited)Sunday, March 30, 2025
evoskuil02:05
Switched the hashmap heads back to modulo truncation today, so got granular control over sizing. Ran a mini milestone run with all hashmaps LF 1.5 (previous points table was 2.446). This change was projected to reduce search to ~25% of previous, and after this run I measured an average rate of
0.14% vs. 0.53% with the higher load factor, so right on. This also drops the late stage LF by the same amount, so from 1.1% of inserts, to 0.29%. This is significant, and all comes at the cost of increasing the heads by 2.2GiB. We won't see the impact of that until tomorrow morning. The total head size for validation will be 18.2GiB, whereas in yesterday's high LF run it was 16.0GiB. The earlier run that bogged down with a 1.22LF was too big, at 24GiB heads. So I'm hopeful that this will be much better, but in any case we should be able to squeeze enough out of the heads to get to yesterday's 16.0GiB if we have to, and that will certainly be good.1 reply · evoskuil · last Mar 30, 2025
evoskuil02:39
Oh, also the above 1.5 LF milestone run not only searched just 25% of the 2.5 LF run, but also finished 5 minutes earlier (64 vs. 69 mins).
🔥 1
evoskuil15:45
Above run finished at 9.7 hours. Started slow and picked up later. Since that LF means search is almost zero early on, it implies that the increase RAM was still an issue. So I change the LF to 2.0, which is a search reduction by 55%, and decreased LF on other tables to 1.25, resulting in the 16GiB head size from the simulations vs. 18.2GiB. This is an increase of the LF from the other tables, from closer to 1.0 with base2 buckets to 1.25, but prior to base2 buckets I always ran at LF 1.5 and the performance was about the same. This will take another 9 hours to run, so should have another point around 9pm ET.
evoskuil15:52
I'm hoping to get rid of most of the archival slope increase resulting from the high LF by keeping the full table FP rate under ~0.8%, as that's where it started to slow down in the milestone runs. This is a memory tradeoff, which is also a performance issue. Too far on either one is suboptimal. So this is just about finding an optimal point for the minimum RAM baseline. Above that the optimal proportion may differ, but the importance is lesser. Once we get to the maxi it barely matters.
evoskuil17:19
It's about 25% complete by volume and is tracking well ahead of the previous 9.7 hr run, about 25 secs ahead of the 9.4 hr run - even with a much higher LF on the other tables. So it's the amount of head space that's controlling at the lower end. As the point table fills up, its search starts to control. So hopefully the drop from 2.45 to 2.0 LF will keep that from climbing. We'll know that when we start to see the current run beating the 9.4 hr run.
👀 1
evoskuil18:39
Now about 30% complete and already almost 10 minutes ahead of the 9.4 run, which should continue to improve in relative terms. So I think this will get full validation under 9 hours, meaning confirmation is only an hour beyond validation on the mini now, vs. 12+.
The times vary between 10-18 minutes ahead because of cycling between validations and long strings of confirms during archive in both the new run and baseline.
(edited)Monday, March 31, 2025
evoskuil02:11
Spent most of the day refactoring some messes I made over the past few weeks. Good list of things to do now:
- do some runtime tests of positive duplicate point detections
- reconnect the confirmation chaser's strong branch logic
- add and integrate the usually-empty
doublestable (point duplicates) - change
Link::terminaland schema to allow for bit-aligned link terminals - update hashmap head sieve integration to support bit-aligned [link | sieve]
The last one will allow me to double the sieve efficiency (cut FP rate in half) by using one bit from the point link value in the hashmap head. It only needs 31 bits but is using 32.
The others will connect all of the moving parts of confirmation, which was a little disjointed due to all of the scenario evaluations.
In the mean time I'll keep running mini mini and reduced RAM maxi full validation runs while tuning and performance analyzing to squeeze this down some more. Should def be able to get this under 9 hrs on the min (it's at 4.4 on the maxi).
👀 1
evoskuil02:43
So just fired up an overnight run with point LF still at 2.0 but other tables moved up from 1.25 to 2.0. This drops 2.4GiB from the head space. So just trying to see which is more sensitive, RAM or the other heads.
evoskuil02:55
Also need to finish up:
- table split for compact filters
because we are splitting the filter body into the validation phase and filter header into the confirmation phase.
evoskuil11:55
With LF 2.0 for all hashmaps completed mini full validation in record 9.16 hrs, with 7 sec shutdown.
💥 1
C
cguida14:52
I wonder if 32gb is the limit with the sieve? Perhaps machines with 16gb could benefit? Because that would be epic 😁
evoskuil18:22
Everything will benefit, but it seems pretty clear to me that this is walking a line between RAM and paging that can't be pushed much further.
💥 1
evoskuil20:24
Note that all hashmaps require body paging to resolve conflicts and read elements. The sieve is only beneficial in preventing such paging when the element does not actually exist in the table. If it is in the table (or might be - this is the false positives), there is no benefit and actually a pretty significant cost in terms of the increased head size.
👍 1
evoskuil21:09
The reason this helps confirmation is that double spends are rare. In our use they consist of conflicting unconfirmed txs, race condition duplicates, valid duplicates (2 from bip30), and actually strong branch invalid block tx duplications (the ones we need to check for). So by recording these rare duplicates we can reduce the double spend query cost to almost zero for block-inclusions.
Compact blocks will absorb existing txs, so they won't benefit from this exclusion (two valid blocks can spend the same tx record). However this is only a performance issue during sync. A single block full double spend query is very fast. And it will continue to work for catch-up sync (i.e. after compacts have come in) as well.
👍 1