Explain how to use ZK-STARKs

iaa2005 commented 2 years ago

For example, can I create transaction and make proof and check proof? And how to use Your code in blockchain protocol?

aszepieniec commented 2 years ago

I think the questions you ask are rather broad and and context-specific. Let me reformulate into a specific question with a definite context, and answer that.

(How) Can you use zk-STARKs to prove and verify transactions in a blockchain protocol?

The good news is that the yes-or-no part of the question has a definite "yes" answer. The other good news is that the open-ended part of the question has a long answer.

1. Parameters

You need to determine the arguments to the transaction validity predicate. These are the possible answers to the question why a given transaction is invalid. These could be:

The transaction is not signed, or the signature is not valid. So a parameter to the validity predicate could be a signature.
The transaction does not identify a public key against which the signatures is supposed to be verified.
The transaction does not specify an origin.
The origin does not contain the given amount.

2. Logic

Given the parameters, what logic does the validity predicate compute? For instance, this could be (all of):

For every input, there must be a signature on the whole transaction that is valid under that input's public key.
The total amount of coins does not increase.
No balances are negative.

3. Arithmetization.

The next step is to arithmetize this validity predicate. Specifically, this means finding AIR constraints that capture this logic. These AIR constraints can be plugged into your favorite STARK engine, for instance the Rescue-Prime STARK but exchanging the Rescue-Prime AIRs for the new AIRs.

iaa2005 commented 2 years ago

Ok. But I want to know HOW to use ZK-Starks using python: some example code: Inputs, outputs, pk sk keys etc. Because you wrote only algorithm, not code for transactions of blockchain... If you will can do this, I will be very grateful! ;)

aszepieniec commented 2 years ago

I'm afraid I still don't understand the question. The test_fast_stark() function in test_fast_stark.py shows how to use the interface. What is it that's missing?

Sword-Smith commented 2 years ago

Ok. But I want to know HOW to use ZK-Starks using python: some example code: Inputs, outputs, pk sk keys etc. Because you wrote only algorithm, not code for transactions of blockchain... If you will can do this, I will be very grateful! ;)

Did you read the whole tutorial? The linking of STARKs to a signature scheme is done in https://neptune.cash/learn/stark-anatomy/rescue-prime/#stark-based-signatures. The short version of it is that you prove the correct calculation of a Rescue Prime hash digest using STARKs but you hide the input to the hash function. In other words: A signature scheme that uses STARK can be achieved by just hashing your private key and creating a STARK proof for the calculation of the hash digest.

Edit: You can make a STARK-based signature scheme in multiple ways but the above one I describe is probably the simplest and also the one that is used in this tutorial.

iaa2005 commented 2 years ago

Thank you!

Sword-Smith commented 2 years ago

Thank you!

Pleasure :)

Sword-Smith commented 2 years ago

Thank you!

If you're like me and prefer reading code instead of reading text, you can also have a look at the Python source code where such a STARK signature is generated. You can find it in https://github.com/aszepieniec/stark-anatomy/blob/master/code/rpsss.py

By prepending the proof stream with the message you want to sign, you can get a signature for a specific message using this technique.

aszepieniec / stark-anatomy