“You still need one hash for every non-leaf node, so 30-40 hashes of 256 bits each. What this algorithm saves is 30-40 indices, which is 11 bits each for a 1000-leaf tree. Even aligning to 16 bits it's doesn't seem a great optimization. Unless I misunderstood something and we are not trying to minimize the size of whole proof, but just its structure - but…”
The Bloom Tree
We introduce a data structure that allows for efficient (probabilistic) presence proofs and non-probabilistic absence proofs in a bandwidth efficient and secure way. The Bloom tree combines the idea of Bloom filters with that of Merkle trees. Bloom filters are used to verify the presence, or absence of elements in a set. In the case of the Bloom tree, we are interested to verify and transmit the presence, or absence of an element in a secure and bandwidth efficient way to another party. Instead of sending the whole Bloom filter to check for the presence, or absence of an element, the Bloom tree achieves efficient verification by using a compact Merkle multiproof.
候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“I realize I wasn't clear. I used 2 sqlite databases just to store the article titles and offsets into binary files (<2GB) that had chunks of compressed data. Each chunk contained 10s-100s of stories, so that the decompressed around was around 20megs I believe. I had planned to store everything in sqlite, but there were too many issues. The FTS extension t…”
- The Bloom Tree ↗irwt · 2020-02-11 · 11 分