区块链 contracts,区块链snark

近年来，区块链技术及其相关应用正在改变着我们的世界，其中包括智能合约和snark技术。本文将详细介绍这两种技术，以及它们如何影响我们的日常生活。

智能合约

智能合约是一种基于区块链技术的自动执行协议，它可以使双方达成交易协议并自动执行。智能合约可以记录交易双方的权利、义务、条款和条件，并在满足特定条件时自动执行。智能合约的优势在于它可以极大地提高交易的透明度和安全性，可以有效降低交易成本，还可以提高交易的效率。

SNARK

SNARK是一种新型的数字签名技术，它可以用来确认交易的参与者，以及交易的完整性和有效性。SNARK可以帮助参与者确保自己的信息安全，而无需将其明文传输，从而防止他人窃取其信息。此外，SNARK还能够有效地减少交易的计算量，从而提高交易的效率。

总之，智能合约和SNARK技术在区块链应用中发挥着重要作用。它们可以提高交易的安全性和透明度，降低交易成本，提高交易效率，从而改善我们的日常生活。

『一』What is zero-knowledge proof

Zero-knowledge proof in cryptography is to prove one thing without letting the other party know any information. Example It's identification. Or use evolutionary computation to generate a program for judging the endgame of chess. The "product" of evolutionary computation is usually a program (algorithm) that humans cannot understand. If we can know through experiments and probability analysis that this program can The probability is extremely low (perhaps lower than a meteor hitting your house) and the outcome of the endgame is completely correct. Then we can really believe that this program has the ability to judge the endgame, and we can use it in situations where we cannot understand but trust it. According to personal understanding, in layman's terms (personal statement): Guessing the calculation method of an event (cryptographic decryption) without sufficient (or even no) basis. Although it is a guess without any basis, this guess The calculated method is proved to be correct, which is a zero-knowledge proof.

『二』Modern cryptography in blockchain

1983 - Blind signature described by David Chaum
1997 - HashCash (Proof of Work system) invented by Adam Back An example)
2001 - Ron Rivest, Adi Shamir and Yael Tauman proposed ring signatures to the crypto community
2004 - Patrick P. Tsang and Victor K. proposed using a ring signature system for voting and electronic cash ;
2008 - Bitcoin White Paper published by Satoshi Nakamoto
2011 - Analysis of Anonymity in the Bitcoin System, Fergal Reid and Martin Harrigan
2012 - Destination Address Bitcoin Anonymity (in CryptoNote one-time address).

Secure multi-party computation originated from Yao Qizhi’s millionaire problem in 1982. Later Oded Goldreich had a more detailed and systematic discussion.

The Yao Millionaire problem was first raised by Professor Yao Qizhi, a Chinese computer scientist and Turing Award winner. The problem is formulated as follows: Two millionaires, Alice and Bob, want to know which of them is richer, but neither of them wants the other to know any information about their wealth. This problem has some practical applications: Suppose Alice wants to buy some goods from Bob, but the maximum amount she is willing to pay is x yuan; the minimum price Bob wants to sell for is y yuan. Both Alice and Bob really want to know which is bigger, x or y. If x>y, they can all start bargaining; if z
This scheme is used to compare two numbers to determine which one is larger. Alice knows an integer i; Bob knows an integer j. Alice and B0b want to know whether i>=j or j>i, but neither wants the other party to know their own numbers. For simplicity, assume that the range of j and i is [1, 100]. Bob has a public key Eb and a private key Db.

The research on Secure Multi-Party Computation is mainly aimed at the problem of how to safely calculate an agreed function without a trusted third party. Secure multi-party computation is used in electronic elections, electronic It plays an important role in scenarios such as voting, electronic auctions, secret sharing, and threshold signatures.

Homomorphic Encryption is an Open Problem proposed in the cryptography community a long time ago. As early as 1978, Ron Rivest, Leonard Adleman, and Michael L. Dertouzos proposed this concept in the context of banking [RAD78]. Yes, you read that right, Ron Rivest and Leonard Adleman are R and A respectively in the famous RSA algorithm.

What is homomorphic encryption? Craig Gentry, who proposed the first construction of Fully Homomorphic Encryption [Gen09], gave the best intuitive definition: A way to delegate processing of your data, without giving away access to it.
< br /> What does this mean? General encryption schemes focus on data storage security. That is, I want to send an encrypted thing to other people, or I want to store something on a computer or other server. I want to encrypt the data before sending or storing it. Without the key, it is impossible for the user to obtain any information about the original data from the encrypted result. Only users with the key can correctly decrypt and obtain the original content. We noticed that during this process, users cannot do any operations on the encryption results, they can only store and transmit them. Any operation on the encryption result will result in incorrect decryption or even decryption failure.

The most interesting thing about the homomorphic encryption scheme is that it focuses on data processing security. Homomorphic encryption provides a function for processing encrypted data. That is to say, otherEncrypted data can be processed by humans, but the processing does not reveal any of the original content. At the same time, the user who has the key decrypts the processed data and gets exactly the processed result.

A bit abstract? Let’s take a real-life example. A user named Alice bought a large piece of gold, and she wanted workers to make it into a necklace. But workers may steal gold during the building process. After all, even one gram of gold is worth a lot of money... So is there a way for workers to process the gold nuggets (delegate processing of your data), but Not getting any gold (without giving away access to it)? Of course there is a way, Alice can do this: Alice locks the gold in a sealed box, and this box is equipped with a glove. Workers can wear this glove to handle the gold inside the box. But the box was locked, so not only could the workers not get to the gold nuggets, but they also couldn't get to any gold that fell out during processing. After processing is completed. Alice took the box back, opened the lock, and got the gold.

The correspondence here is: Box: Encryption algorithm Lock on the box: User key Put the gold nugget in the box and lock it with a lock: Encrypt the data using a homomorphic encryption scheme : Apply the homomorphic feature to directly process the encryption result under the condition that the data cannot be obtained. Unlock: Decrypt the result and directly obtain the processed result. Where can homomorphic encryption be used? Hasn’t the concept of cloud computing been mentioned in recent years? Homomorphic encryption is almost tailor-made for cloud computing! Let's consider the following scenario: a user wants to process a piece of data, but his computer's computing power is weak. This user can use the concept of cloud computing and let the cloud help him process and get the results. But if the data is handed over directly to the cloud, security cannot be guaranteed! Therefore, he can use homomorphic encryption, and then let the cloud process the encrypted data directly and return the processing results to him. In this way: the user pays the cloud service provider and gets the processing results; the cloud service provider earns the fee and correctly processes the data without knowing the user's data;

Aggregated signature by Boneh et al. proposed to improve the efficiency of signature and verification mainly by aggregating multiple signatures into one signature. To sign data of multiple users, aggregate signatures can greatly reduce the complexity of signature calculations. CL is the aggregate signature.

There are two participants in the zero-knowledge proof process, one is called the prover and the other is called the verifier. The prover holds a secret, and he wants the verifier to believe that he holds the secret, but he does not want to reveal the secret to the verifier.

Both parties follow an agreement and through a series of interactions, the verifier will eventually getCome to a clear conclusion that the prover does or does not know the secret.

For the example of Bitcoin, whether a transfer transaction is legal or not actually only needs to prove three things:

The money sent belongs to the person who sent the transaction
Send The amount sent by the sender is equal to the amount received by the receiver
The sender's money was indeed destroyed
During the entire proof process, the miners do not actually care about the specific amount of money spent, who the sender is, and the recipient Who exactly is it? Miners only care about whether the system's money is conserved.

zcash uses this idea to implement private transactions.

The three properties of zero-knowledge proof correspond to:

(1) Completeness. If both the prover and the verifier are honest, follow every step of the proof process, and perform correct calculations, then the proof must be successful and the verifier must be able to accept the prover.
(2) Rationality. No one can impersonate the prover and make this proof successful.
(3) Zero knowledge. After the proof process is completed, the verifier only obtains the information that "the prover possesses this knowledge", but does not obtain any information about the knowledge itself.

There are only ring members, no managers, and no cooperation between ring members is required. The signer can sign independently by using his own private key and the public keys of other members in the set, without the need for other members. With the help of people, other members of the set may not be aware that they are included.
Ring signatures can be used as a way to reveal secrets, for example, a ring signature can be used to provide an anonymous signature from a "senior White House official" without revealing which official signed the message. Ring signatures are suitable for this application because the anonymity of a ring signature cannot be revoked and because the group used for the ring signature can be created on the fly.

1) Key generation. Generate a key pair (public key PKi, private key SKi)
2) signature for each member in the ring. The signer uses his own private key and the public keys of any n ring members to generate a signature a
for message m
3) Signature verification. The signer verifies whether the signature is signed by a member of the ring based on the ring signature and message m. If valid, accept it; if invalid, discard it.

General process of group signature

Blind digital signature (Blind Signature), referred to as blind signature - is a digital signature method. Before the message content is signed, the signature The content of the message is invisible to the user. In 1982, David Chaum first proposed the concept of blind signature.read. Because of its blindness, blind signature can effectively protect the specific content of the signed message, so it is widely used in fields such as e-commerce and electronic elections.

Analogy example: To sign a document is to put a piece of carbon paper in the envelope. When the signer signs the envelope, his signature is signed on the document through the carbon paper.

The so-called blind signature is to first put the concealed document into an envelope, and the process of removing the blind factor is to open the envelope. When the document is in an envelope, no one can read it. Signing a document is done by placing a piece of carbon paper in the envelope. When the signer signs the envelope, his or her signature is transferred to the document through the carbon paper.

Generally speaking, a good blind signature should have the following properties:

Unforgeable. No one can generate a valid blind signature in his name except the signer himself. This is the most basic property.
Non-repudiation. Once a signer signs a message, he cannot deny his signature on the message.
Blindness. Although the signer signs a message, he cannot obtain the specific content of the message.
Untraceability. Once the signature of a message is made public, the signer cannot be sure when he or she signed the message.
Blind signatures that meet the above properties are considered safe. These four properties are not only the standards we should follow when designing blind signatures, but also the basis for us to judge the performance of blind signatures.

In addition, the operability and implementation efficiency of the solution are also important factors that we must consider when designing blind signatures

. The operability and implementation speed of a blind signature depend on the following aspects:

1. The length of the key;
2. The length of the blind signature;
3. Blind Signature algorithm and verification algorithm.
Specific steps of blind signature
1. The recipient first blindly transforms the data to be signed, and sends the transformed blind data to the signer.
2. After being signed by the signer, it will be sent to the recipient.
3. The receiver performs a blinding transformation on the signature, and the result is the signer's blind signature of the original data.
4. This meets the condition ①. To satisfy condition ②, the signer must not be able to associate the blind signature with the blind data when he sees it afterwards. This is usually achieved by relying on some kind of protocol.