Payment verification workflow for SPV with NiPoPoW

[greenhat]

Using NiPoPoW described in KMZ17

Goal

Prove that a payment (ERG and/or tokens) was made on the blockchain.

EDIT: For a recent payment it would be faster to use UTXO proof described in #502

Step 1. Prove that a tx with a given id in a block with a given id exists in the blockchain.

Step 1.1. Prove that a block with a given id exists in the blockchain.

• 1.1.1. Ask proofs from known nodes via /nipopow/proof/{m}/{k}/{headerId} /nipopow/proof REST API endpoint support #545

• 1.1.2. Create NipopowVerifier Rust equvalent and feed all received proofs into NipopowVerifier::process; [1500 SigmaUSD] NiPoPoW proof verification #499

• 1.1.3. Check that verifier.bestProof().suffixHead.id is our block id; [1500 SigmaUSD] NiPoPoW proof verification #499

Step 1.2. Prove that a tx with a given id exists in the blockchain.

• 1.2.1. Ask any node for MerkleProof via /blocks/{headerId}/proofFor/{txId}; [350 SigmaUSD] MerkleProof verification #515
• 1.2.2. Confirm the tx id is in the block with merkleProof.valid(header.transactionsRoot) Rust equivalent; [350 SigmaUSD] MerkleProof verification #515

Step 2. Check the box with the payment

Step 2.1 Get the whole tx for tx id from Step 1

It can either be provided along with the tx id in Step 1 or fetched from the node. It is verified by serializing the tx and calculating its id and then comparing it to the tx id confirmed in Step 1.2.

Step 2.2. Confirm the payment is in this tx

Find the output box protected with a certain script (e.g certain PK) and check that its value and/or tokens are as expected.

[greenhat]

@kushti Could you please confirm the above workflow is correct? Also, I have the following questions:

1. How many nodes should we ask in 1.1.1 to be safe? As I understand even one honest node is enough. I believe we should have a minimum number of nodes which we should not go below.
2. What m and k values are considered safe(defaults) for 1.1.1? I believe k = 6, but what about m? Higher m I believe should grow the proof size (prefix length), but what is a safe minimum m?
3. I found the NipopowVerifier in 1.1.2 does not use passed m and k parameters. Should not we have checked them against proof params?
4. Is it ok to ask any node in 1.2.1? I believe it is, but just to be sure please confirm.

[kettlebell]

I'm just hitting active peer nodes individually for step 1.1 and inspecting the responses, and I can never satisfy 1.1.3. I've been tweaking different values of m and k. Note that the block id I use always appears in the prefix.

For reference I'm just using block #740950: https://explorer.ergoplatform.com/en/blocks/05bf63aa1ecfc9f4e3fadc993f87b33edb4d58e151c1891816d734dd5a0e2e09

[kettlebell]

Just to clarify, when I say that 1.1.3 can't be satisfied I mean that I've yet to run a query that gives me suffix_head == block_id.

[greenhat]

@kettlebell That's interesting. According to https://github.com/ergoplatform/ergo/blob/d6bc943dfa591873dadc509fbb41ab4e5f4385dd/src/main/scala/org/ergoplatform/modifiers/history/popow/NipopowAlgos.scala#L228
the asked block id should be in NipopowProof::suffixHead. Which is supported by the test - https://github.com/ergoplatform/ergo/blob/d6bc943dfa591873dadc509fbb41ab4e5f4385dd/src/test/scala/org/ergoplatform/modifiers/history/PoPowAlgosSpec.scala#L153

Maybe there is an error in our NipopowProof serialization?

[kettlebell]

I double checked things by manually making the GET requests using curl; our serialization is fine.

The suffix that's returned from /nipopow/proof/{m}/{k}/{headerId} always returns the latest k blocks from the chain. I see my mistake now in that I'm trying to query an older block that goes beyond the suffix.

I went back to the KMZ17 paper, and I can see that the code we have in both sigma-rust and the reference node only works for k-suffix-sensitive predicates (definition 5), so we can only verify for recent blocks. It looks like we need to implement the infix proof machinery to have this workflow for arbitrarily-deep blocks. Am I wrong in my reading of this?

[kettlebell]

@greenhat regarding the test you linked at https://github.com/ergoplatform/ergo/blob/d6bc943dfa591873dadc509fbb41ab4e5f4385dd/src/test/scala/org/ergoplatform/modifiers/history/PoPowAlgosSpec.scala#L153, note that the block that's being checked is suffix head of proof0, for k = 6; a recent block. Sorry this is exactly what you said in your comment.

[greenhat]

I double checked things by manually making the GET requests using curl; our serialization is fine.

The suffix that's returned from /nipopow/proof/{m}/{k}/{headerId} always returns the latest k blocks from the chain. I see my mistake now in that I'm trying to query an older block that goes beyond the suffix.

I don't understand. I see here https://github.com/ergoplatform/ergo/blob/d6bc943dfa591873dadc509fbb41ab4e5f4385dd/src/main/scala/org/ergoplatform/modifiers/history/popow/NipopowAlgos.scala#L229 that suffix should be the asked headerId plus (k-1) headers after it. I don't see how the suffix can be the last k blocks if the headerId is passed.

I went back to the KMZ17 paper, and I can see that the code we have in both sigma-rust and the reference node only works for k-suffix-sensitive predicates (definition 5), so we can only verify for recent blocks. It looks like we need to implement the infix proof machinery to have this workflow for arbitrarily-deep blocks. Am I wrong in my reading of this?

Initially, I thought that we need infix proofs but @kushti said prefix proofs should work fine. I don't think we have infix proofs implemented in Scala yet.