<p>For context, I am working on an application in an environment where storage is prohibitively expensive (Ethereum smart contract) and I have some odd requirements:</p>
<ul>
<li>I need to store a potentially endless amount of data, while minimizing costs.</li>
<li>Many different sources will unpredictably introduce new data that needs to be stored.</li>
<li>Many different sources will need to prove that data exists. Proving that data exists involves sending a verification request to a verifier. This request is not instant, and can be affected by delays such as network transmission.</li>
<li>There is no need to modify or remove data.</li>
</ul>
<p>I created a data structure to store data that satisfies all of my requirements, with properties that I cannot find evidence of any existing data structure currently having.</p>
<p>This is a summary of the data structure: The structure starts with an empty array of roots and a count of zero elements. The insert function takes a piece of data and hashes it to create a message. We get a 'ruler number', which is the element of the ruler sequence (A007814) at an index of our element count. The message is then hashed again, this time with each of the roots up to the ruler number. The root in our roots array at the index of our ruler number is then set to our final message. Finally, the element count is incremented by 1.</p>
<p>Features:</p>
<ul>
<li>The verifier only needs to store the roots array and count. For the verifier, this data structure has a space-complexity of O(log2 N).</li>
<li>Data exists in either one or two of our roots at a time. As data is added, existing data is pushed to roots of a greater index.</li>
<li>Each root updates at half the frequency of the root at the previous index.
A consequence of the last two points is that if a prover needs to prove data is in the structure by sending a verification request to a verifier, they can wait until the data propagates to a root which the prover is confident won't change before the verifier can process the prover's verification request.</li>
</ul>
<p>Drawbacks:</p>
<ul>
<li>Data can never be modified or removed from the structure</li>
</ul>
<p>A very quick-and-dirty NodeJS implementation with additional functions to verify data exists in the structure is at <a href="https://github.com/bradthomasbrown/Tangle/blob/master/showcase/ADISA.mjs" rel="nofollow noreferrer">https://github.com/bradthomasbrown/Tangle/blob/master/showcase/ADISA.mjs</a></p>
<p>Did anyone discover this concept or a similar concept for a data structure before?</p>
<p>EDIT</p>
<p>pseudocode for data structure and verify function</p>
<pre><code>dataStructure {  
    mapping(uint =&gt; bytes32) roots  
    uint elementCount  
}  
insert(data) {  
    message = H(data)  
    rulerNumber = R(dataStructure.elementCount)  
    for (i = 0; i &lt; rulerNumber; i++)  
        message = H(concat(dataStructure.roots[i], message))  
    dataStructure.roots[rulerNumber] = message  
    dataStructure.elementCount++  
}
</code></pre>

CC BY-SA 4.0
2023-03-06T17:17:32.150Z
From the posted code, it looks like you can `insert`, `proof`, and `verify`. Would you explain what these are supposed to do? And when you say the structure's space complexity is O(log2 N), what is N? (And do you mean $O(\log_2 N)$ or $O(\log^2 N)$? And if the former, does that mean twice-iterated or base 2, the latter being redundant with the $O$?)
Charles
CC BY-SA 4.0
2023-03-06T17:33:28.300Z
It seems, at a glance, that given element and id, `verify(element, proof(id))` is suppose to be (usually?) true if element was the id-th element inserted into the data structure, but (usually?) false if the element was not the id-th element inserted into the data structure. Is this right? If so, what you're claiming is a structure that lets you (stochastically?) query membership if you remember the index.
Charles
CC BY-SA 4.0
2023-03-06T21:48:34.130Z
I notice that the structure also uses the list of elements internally (`let leaves = data`) so not sure what that's for.
Charles
CC BY-SA 4.0
2023-03-07T05:26:11.860Z
I don't understand the data structure.  Suppose $R(i)$ is the $i$th number in the ruler sequence, and $H$ is the hash function.  Can you specify the operation of insert() using pseudocode?  I don't know what "hashed again, this time with each of the roots up to the ruler number" means - I'm not sure what you are hashing, exactly.  I'm not sure what "final message" means.  Can you provide pseudocode for proof() and verify()?  What properties do you require them to satisfy?  Do you require some kind of cryptographic security?
D.W.
CC BY-SA 4.0
2023-03-07T05:27:23.033Z
Cross-posted: https://cstheory.stackexchange.com/q/52558/5038, https://stackoverflow.com/q/75645882/781723.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
CC BY-SA 4.0
2023-03-07T19:23:40.630Z
@Charles
I have updated the code in the repository to more appropriately reflect that there is a prover-verifier relationship. The data structure in question exists with the verifier.
`insert` is a verifier function users can use to insert data into the structure.
`getProof` is a prover function users can use to get a proof that an element exists in the verifier's data structure.
`verify` is a verifier function users can use with a proof obtained from a prover to verify an element exists in the data structure.
The space-complexity of the data structure used by the verifier is log base 2.
Brad Brown
CC BY-SA 4.0
2023-03-07T19:24:57.267Z
@Charles The addition of a prover who holds all of the data elements that have been submitted to a verifier should also clarify that `let leaves = data` is referring to the prover's set of data.
Brad Brown
CC BY-SA 4.0
2023-03-07T19:54:12.243Z
@D.W.
Thank you for the information about cross-posting.
I added pseudocode in an edit to the bottom of the original post for the insert function.
Unfortunately, I don't think I can succinctly describe the getProof() function in pseudocode.
The general idea is that data exists in either 1 or 2 of the roots, which are actually Merkle trees.
The proof contains the element being queried, the index of the root (which Merkle tree to query), and the Merkle proof and leaf index to prove our element is in the chosen root (or Merkle tree).
Brad Brown
CC BY-SA 4.0
2023-03-07T19:56:53.573Z
I thought this was supposed to be a space-saving data structure (like the Bloom filter), but that doesn't seem to be the case if you're holding a copy of the data. I'd like to understand what the operations are intended to do and what performance (space/time/etc.) they have, that would help me determine how they compare to existing algorithms and data structures.
Charles
CC BY-SA 4.0
2023-03-07T20:00:48.740Z
@D.W.
Some requirements: the data inserted must be unique, which can be enforced by the verifier appending a nonce to the end of it. For the hashing function, we just want the chance of a collision to be minimal. My NodeJS example uses SHA-256, the project I'm working on will use KECCAK-256.
Brad Brown
CC BY-SA 4.0
2023-03-07T20:21:56.717Z
@Charles
It might be more accurate to say that the space-complexity is O(N) for the prover and O(log base 2 N) for the verifier. For insertion time-complexities, the best case would be O(1) when R(elementCount) is 0 where R is the ruler function. The worst case would be O(log base 2 N) when R(elementCount) is one less than a power of 2. Time-complexity of building a proof and of verifying are O(log base 2 N).
Brad Brown
CC BY-SA 4.0
2023-03-07T21:21:25.087Z
So in terms of performance, it sounds a lot like a B-tree (except that those can delete). Does your structure have better amortized insert performance? That is, if you insert n items, can you guarantee better than n log n time? (I don't know of a binary search tree that does this.)
Charles
CC BY-SA 4.0
2023-03-07T21:38:54.870Z
Yes, with the exception of insertions of a single item numbered by a power of 2. For example, inserting 1 item, where the item is the first, second, fourth, eighth, etc. item then it is n log n operations. Every other case is faster.
Brad Brown
CC BY-SA 4.0
2023-03-13T17:29:56.307Z
If it takes $n\log n$ operations to insert $n=2^k$ items for each $n$, then the amortized insert performance is $\log n$, regardless of whether $n$ is a power of two or not.
Charles
<ds.data-structures>
Did I discover a new data structure?
Brad Brown
# Did I discover a new data structure?

(Asked by: username_0 on 2023-03-05)

For context, I am working on an application in an environment where storage is prohibitively expensive (Ethereum smart contract) and I have some odd requirements:

I need to store a potentially endless amount of data, while minimizing costs.
Many different sources will unpredictably introduce new data that needs to be stored.
Many different sources will need to prove that data exists. Proving that data exists involves sending a verification request to a verifier. This request is not instant, and can be affected by delays such as network transmission.
There is no need to modify or remove data.

I created a data structure to store data that satisfies all of my requirements, with properties that I cannot find evidence of any existing data structure currently having.
This is a summary of the data structure: The structure starts with an empty array of roots and a count of zero elements. The insert function takes a piece of data and hashes it to create a message. We get a 'ruler number', which is the element of the ruler sequence (A007814) at an index of our element count. The message is then hashed again, this time with each of the roots up to the ruler number. The root in our roots array at the index of our ruler number is then set to our final message. Finally, the element count is incremented by 1.
Features:

The verifier only needs to store the roots array and count. For the verifier, this data structure has a space-complexity of O(log2 N).
Data exists in either one or two of our roots at a time. As data is added, existing data is pushed to roots of a greater index.
Each root updates at half the frequency of the root at the previous index.
A consequence of the last two points is that if a prover needs to prove data is in the structure by sending a verification request to a verifier, they can wait until the data propagates to a root which the prover is confident won't change before the verifier can process the prover's verification request.

Drawbacks:

Data can never be modified or removed from the structure

A very quick-and-dirty NodeJS implementation with additional functions to verify data exists in the structure is at https://github.com/bradthomasbrown/Tangle/blob/master/showcase/ADISA.mjs
Did anyone discover this concept or a similar concept for a data structure before?
EDIT
pseudocode for data structure and verify function
dataStructure {  
    mapping(uint => bytes32) roots  
    uint elementCount  
}  
insert(data) {  
    message = H(data)  
    rulerNumber = R(dataStructure.elementCount)  
    for (i = 0; i < rulerNumber; i++)  
        message = H(concat(dataStructure.roots[i], message))  
    dataStructure.roots[rulerNumber] = message  
    dataStructure.elementCount++  
}

**Tags:** ds.data-structures

> **Comments:**
> **username_1**: From the posted code, it looks like you can `insert`, `proof`, and `verify`. Would you explain what these are supposed to do? And when you say the structure's space complexity is O(log2 N), what is N? (And do you mean $O(\log_2 N)$ or $O(\log^2 N)$? And if the former, does that mean twice-iterated or base 2, the latter being redundant with the $O$?)  
> **username_1**: It seems, at a glance, that given element and id, `verify(element, proof(id))` is suppose to be (usually?) true if element was the id-th element inserted into the data structure, but (usually?) false if the element was not the id-th element inserted into the data structure. Is this right? If so, what you're claiming is a structure that lets you (stochastically?) query membership if you remember the index.  
> **username_1**: I notice that the structure also uses the list of elements internally (`let leaves = data`) so not sure what that's for.  
> **username_2**: I don't understand the data structure.  Suppose $R(i)$ is the $i$th number in the ruler sequence, and $H$ is the hash function.  Can you specify the operation of insert() using pseudocode?  I don't know what "hashed again, this time with each of the roots up to the ruler number" means - I'm not sure what you are hashing, exactly.  I'm not sure what "final message" means.  Can you provide pseudocode for proof() and verify()?  What properties do you require them to satisfy?  Do you require some kind of cryptographic security?  
> **username_2**: Cross-posted: https://cstheory.stackexchange.com/q/52558/5038, https://stackoverflow.com/q/75645882/781723.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  
> **username_0**: @username_1 I have updated the code in the repository to more appropriately reflect that there is a prover-verifier relationship. The data structure in question exists with the verifier. `insert` is a verifier function users can use to insert data into the structure. `getProof` is a prover function users can use to get a proof that an element exists in the verifier's data structure. `verify` is a verifier function users can use with a proof obtained from a prover to verify an element exists in the data structure. The space-complexity of the data structure used by the verifier is log base 2.  
> **username_0**: @username_1 The addition of a prover who holds all of the data elements that have been submitted to a verifier should also clarify that `let leaves = data` is referring to the prover's set of data.  
> **username_0**: @username_2 Thank you for the information about cross-posting. I added pseudocode in an edit to the bottom of the original post for the insert function. Unfortunately, I don't think I can succinctly describe the getProof() function in pseudocode. The general idea is that data exists in either 1 or 2 of the roots, which are actually Merkle trees. The proof contains the element being queried, the index of the root (which Merkle tree to query), and the Merkle proof and leaf index to prove our element is in the chosen root (or Merkle tree).  
> **username_1**: I thought this was supposed to be a space-saving data structure (like the Bloom filter), but that doesn't seem to be the case if you're holding a copy of the data. I'd like to understand what the operations are intended to do and what performance (space/time/etc.) they have, that would help me determine how they compare to existing algorithms and data structures.  
> **username_0**: @username_2 Some requirements: the data inserted must be unique, which can be enforced by the verifier appending a nonce to the end of it. For the hashing function, we just want the chance of a collision to be minimal. My NodeJS example uses SHA-256, the project I'm working on will use KECCAK-256.  
> **username_0**: @username_1 It might be more accurate to say that the space-complexity is O(N) for the prover and O(log base 2 N) for the verifier. For insertion time-complexities, the best case would be O(1) when R(elementCount) is 0 where R is the ruler function. The worst case would be O(log base 2 N) when R(elementCount) is one less than a power of 2. Time-complexity of building a proof and of verifying are O(log base 2 N).  
> **username_1**: So in terms of performance, it sounds a lot like a B-tree (except that those can delete). Does your structure have better amortized insert performance? That is, if you insert n items, can you guarantee better than n log n time? (I don't know of a binary search tree that does this.)  
> **username_0**: Yes, with the exception of insertions of a single item numbered by a power of 2. For example, inserting 1 item, where the item is the first, second, fourth, eighth, etc. item then it is n log n operations. Every other case is faster.  
> **username_1**: If it takes $n\log n$ operations to insert $n=2^k$ items for each $n$, then the amortized insert performance is $\log n$, regardless of whether $n$ is a power of two or not.  

---

## 0 answers

