Implementing NiPoPoW algorithm

Question

Hello,

We, a small team, have implemented about 95% of a breakthrough scientific proposal that is describing the NiPoPoW Non-Interactive Proofs of Proof-of-Work. You can find our source code implementation of the NiPoPoW algorithm on our GitHub

During the implementation, we have got a few questions that we were not able to figure out from your breakthrough paper:

I. The WebDollar uses the Mini-Blockchain scheme ( Ethereum alike ) by using Patrica Merkle Trees to store the Balances of every non-zero addresses and Smart contracts. So, in order to validate a balance, we need only SPV hashes from the Patrica Merkle Tree and proofs based NiPoPoW of the last block (which is the last block from the blockchain)… so we believe we don’t require the infix proofs. Am I right? Or do we need the infix or velvet NiPoPoW algorithm?

II. Algorithm 2 Verify

a) We guess that the function validChain will validate π and χ in order to check the interlinks that they point to the genesis block and the hashes are correctly calculated.

b) My first technical question is that we were not able to understand what is the Q predicate used in the Verify Algorithm 2. Is it a “function” that checks and validates the χ (validating a PoW blocks based Target (T), interlinks. I am right? ) or how Q predicate will look like ? What else will the Q predicate do differently than validChain (π, χ)

III. MultiLevel Property

We are not very sure we got the order correctly.

We iterate u' from [0 to all u] and we will check that every u' must hold the property that for any C* included in C that has the property |C∗↑µ'| ≥ k1, C* must have also the last equation. in case C* fails the last equation we return false;

IV. Badness

We were not able to understand the marked C* from the badness function

a. What is the correct order to calculate the expression C↓↑µ−1… first we calculate C↓ and then we calculate based the previous result ↑µ−1?
b. How do we calculate C↓? We couldn’t find any idea of how to calculate C↓ only C’↓ which is downchain definition C’↓ C is defined as C[C’[0] : C’[−1]].
c. Isn’t it C’↓ and not C↓ ?

Thank you!

Answer 1

I. This is almost correct. The only difference is that you still need the χ suffix mentioned in the paper, which includes the most recent |χ| = k blocks of the blockchain. This is because the “last block” is not stable and may be withdrawn (in case another block of the same height happened to be mined at a similar time). You can only deduce the “current” balances as of k blocks ago.

II.
a) This is correct.
b) The predicate “Q” is application-specific. In your case, it could be, for example, a statement that the balance of a specific account holds a certain amount of money at a certain point in time. i.e. Q would be that “Alice holds 5 Ether at block #4,000,091”.

III. This is correct. Generally, unless there is a serious attack against the whole blockchain, this property will not fail to hold (for appropriate δ).

IV.
a) Yes.
b) c) You are correct. The C↓↑µ−1 should in fact be C’↓↑µ−1 instead. I have corrected the error and we will update the paper in the newest version. Many thanks for pointing this out!

Answer credits: Dionysis Zindros