bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 6쪽 중 1쪽
ARPA Whitepaper v0.7
Derek Zhang *, Alex Su *, Felix Xu *, and Jiang Chen *
*Arpachain
about@arpachain.io
Abstract
We propose a secure computation solution for blockchain networks. The correctness of compu-
tation is verifiable even under malicious majority condition using information-theoretic Message
Authentication Code (MAC), and the privacy is preserved using Secret-Sharing. With state-of-
the-art multiparty computation protocol and a layer2 solution, our privacy-preserving computa-
tion guarantees data security on blockchain, cryptographically, while reducing the heavy-lifting
computation job to a few nodes. This breakthrough has several implications on the future of de-
centralized networks. First, secure computation can be used to support Private Smart Contracts,
where consensus is reached without exposing the information in the public contract. Second, it
enables data to be shared and used in trustless network, without disclosing the raw data during
data-at-use, where data ownership and data usage is safely separated. Last but not least, compu-
tation and verification processes are separated, which can be perceived as computational sharding,
this effectively makes the transaction processing speed linear to the number of participating nodes.
Our objective is to deploy our secure computation network as an layer2 solution to any
blockchain system. Smart Contracts[41] will be used as bridge to link the blockchain and compu-
tation networks. Additionally, they will be used as verifier to ensure that outsourced computation
is completed correctly. In order to achieve this, we first develop a general MPC network with
advanced features, such as: 1) Secure Computation, 2) Off-chain Computation, 3) Verifiable
Computation, and 4)Support dApps’ needs like privacy-preserving data exchange.
The remainder of this paper is organized as follows: Section 1 introduces the real world
motivations which inspired us to build a secure computation network. Following motivations, we
highlight our contributions in section 2. We then cover the background of secure computation,
along with a comparison of similar technologies. Our system overview is presented in section 4.
There, we briefly describe our system design and implementation. In section 5-7, we discuss, in
detail, the major components of our multiparty computation protocol, secure computation process,
and considerations in cryptoeconomics. Lastly, we review the implications and applications of the
real world; this includes ecosystem design, business cases, and milestones.
arXiv:1812.05820v1 [cs.CR] 14 Dec 2018
CONTENTS
Contents
1 Motivations 1
1.1 Off-Chain Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Secure Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Centralized Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.4 Data Security in Exchange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Contributions 2
3 Background 3
3.1 Multiparty Computation (MPC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2 Other Candidates of Secure Computation . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2.1 Homomorphic encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2.2 Zero-Knowledge Proof (ZKP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2.3 zk-SNARK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2.4 Trusted Execution Environment (TEE) . . . . . . . . . . . . . . . . . . . . . . 5
3.3 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3.1 Trust Dependency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3.2 Scalability and Flexibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3.3 Practical Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4 System Overview 10
4.1 Interoperability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2 ARPA Virtual Machine (AVM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5 ARPA Multiparty Computation Protocol 12
5.1 Computation Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.1.1 Sharing secrets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.1.2 Evaluating circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.1.3 Information Theoretic MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.1.4 Revealing outcomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.2 Preprocessing Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.2.1 Compiling functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6 The Secure Computation processes 17
6.1 Smart Contract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6.2 Nodes Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.3 Off-Chain Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.4 Computation Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
6.5 MAC with Off-chain computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6.6 Data Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
7 Cryptoeconomics 24
7.1 Economic Rationality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.2 Identity and Reputation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
7.3 Accountable safety . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
7.4 Uncoordinated majority . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
7.5 Bribing attacker model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
7.6 Consensus Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1
CONTENTS
7.6.1 Nakamoto Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
7.6.2 Lottery Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
7.7 Token Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
8 Experiments 30
8.1 Vickrey Auction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
8.2 Deep Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
9 Ecosystem & Applications 32
9.1 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
9.2 Participants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
9.2.1 Computation Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
9.2.2 Data Providers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
9.2.3 Data Consumer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
9.2.4 Model providers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
9.2.5 Data / Model Backers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
9.3 Business Flow for Data Renting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
10 Roadmap 36
2
1 MOTIVATIONS
1 Motivations
1.1 Off-Chain Computation
Current blockchain technology reaches on-chain consensus in such a way that a smart contract [41]
runs on every blockchain node. There is no final authority in a decentralized network, such as
Bitcoin [29], so that every miner has to validate each transaction before accepting and recording it
on the blockchain. In other words, there is no way to verify the result without actually running
it on a trustless network. The most prominent problem is the amount of transaction fee for every
transaction. As the network grows, the amount of computation in the network combined can easily
exceed the gas limit[36], causing more forks and raising more security issues.
Off-chain Computation solves this problem by bringing the computation work off the public net-
work, and by verifying the result in public, only when disputes arise. The key in off-chain computation
is to have verifiable property in the out-sourced computation task. This property effectively solves
the scalability issue[22] on blockchain networks. Therefore, we can achieve the throughput of the
network being linear to the participating notes.
1.2 Secure Computation
One of the ostensible selling points of blockchain technology is its potential to bring greater trans-
parency to financial markets. At its core, blockchain is a means for humans to conduct secure,
verifiable, and recordable transactions online without a centralized party. As consensus is reached in
public and the result is auditable, the blockchain is claimed to be transparent and public-accessible
by design.
However, full transparency can be problematic in the real world. Imagine you opened an account
at a bank and soon find out that its ledgers are public, where anyone can access the transaction
history of your account (and others). Or, if you made a transaction using Bitcoin at an ice-cream
truck and the cashier would be able to know how much money is in your account.
Unfortunately, a privacy feature is not shipped with today’s blockchain technology. The growing
demand for blockchain and smart contract [37, 4, 14] technologies sets the challenge to protect users
from intellectual property theft and other attacks[3]: security, confidentiality and privacy are the key
issues holding back the adoption of blockchain[24].
ARPA is built to provide secure computation capability as an off-chain solution for most blockchain
networks.
1.3 Centralized Dataset
Large internet companies collect data from users’ online activities to train recommendation systems
that predict the customers’ future interest and actions. Health data from different hospitals and gov-
ernment organizations can be used to produce new diagnostic models, while financial companies and
payment networks can combine transaction history, merchant data, and account holder information
to train more accurate fraud-detection engines.
All this data needs to be aggregated from an individual level, but the profits realized from the
data have never been shared with the data contributors. The General Data Protection Regulation
(GDPR[39]) made it clear that data holders have the responsibility to facilitate the portability of the
data. To really enforce this regulation, our data should not be stored at the companys hard drive as
it faces the inevitable risk of being breached.
Unfortunately, companies have found it difficult to protect their critical data from determined
attackers. The convention with data holding is ill-formed in the following ways:
1. Centralized data-at-risk
1
2 CONTRIBUTIONS
2. Unfair value distribution - individual users never get paid for their data
3. Established player dominance creates an unfriendly moat that deters new and innovative chal-
lengers from competing.
4. Talented individuals can’t build a good model without joining the company
We need a decentralized data sharing scheme that enable everyone to build models on it, reward
those who contribute to it, and at the same time keep the data secure.
1.4 Data Security in Exchange
There is a tension that arises when individuals, companies, or governments deal with sensitive data.
On the one hand, data science is a fundamental component of the informational age. We often hear
that data is the new oil: there is immense financial and social value in acquiring raw data. A recent
paper from Google [11] (Figure 1) confirms a well-known fact that data size is positively correlated
to model performance, regardless of model quality. It explains the motivation for companies to
collecting extensive amount of user data.
On the other hand, the more value there is to be gained by piecing data together, the more
cautious everyone has become about data sharing, since data breaches can cause financial, legal, and
political harms. This appears to be a central trade-off: we can share data in order to learn new
insights that benefit the society as a whole, or we can isolate data into protected silos that safeguard
our individual privacy.
Privacy-preserving computation is the solution for this paradox.
Figure 1: Data size and model performance
2 Contributions
Secure Computation Computation is carried out securely so that no participating node can learn
anything more than its prescribed output.
Verifiable Computation Computation can be audited publicly, and its correctness can be proven.
Therefore, it is possible to outsource computation from the blockchain network.
2
3 BACKGROUND
Layer2 Solution Combining secure and verifiable computation, the heavy-lifting work of com-
putation is done off-chain. Essentially, making our secure computation protocol adaptable to any
existing blockchain network.
Scalability ARPA is designed as a Layer2 solution. Because the verification has complexity of
O(1), the on-chain network will never reach its computation (gas) limit. Therefore, we can improve
the computation scalability and TPS(transaction per second) of any network. The computation
capacity is increased linearly to participating nodes.
Efficiency State-of-the-art implementation of MPC protocol is used to speed-up the secure com-
putation.Though this implementation, 5-6 magnitudes of speed improvement are achieved compared
to Fully Homomorphic Encryption (FHE).
Availability World’s first general purpose MPC network for secure computation. With high avail-
ability and low cost, we promote data security and privacy practice that is difficult to achieve other-
wise.
3 Background
3.1 Multiparty Computation (MPC)
Multiparty Computation(MPC) is a way by which multiple parties can compute some function of
their individual secret inputs, without any party revealing anything to the other parties about their
input, other than what can be learned from the output. Unlike traditional cryptographic tasks,
where the adversary is outside the system of sender and receiver, the adversary is a part of the
participants. This model frees the cryptographers from the centralized paradigm to the distributed
paradigm. Many unsolved problems like Yao’s millionaires’ problem [42] or secure auction system
[8] can be perfectly settled. In a sense, MPC is rather a new paradigm than a specific cryptographic
algorithm.
MPC can be considered as a configurable framework with a mixture of crypto tools, which gives
participants the right to organize the specific protocol according to the security level and efficiency
limitation of a scenario. The beauty of multiparty protocols is that they use a rich body of tools
and sub-protocols, some of which have been developed especially for MPC and others previously
developed for the cryptographic non-distributed setting. These tools include zero-knowledge proof
(ZKP) [33], probabilistic encryption, information-theoretic Message Authentication Code (MAC),
various distributed commitment schemes, and oblivious transfer [32]. Most importantly, secret-
sharing [31] and computing with shares of a secret is fundamental to achieving secure multiparty
computation. In particular, the polynomial secret sharing of Shamir [35] in the case of passive
adversary is a cornerstone in multiparty computations, and the verifiable secret sharing [12] plays an
analogous role in the Byzantine adversary case.
There are various MPC protocols built with different assumptions in terms of security models.
For example, Sharemind [7] and VIFF [17] assume a semi-honest scenario where the adversary will
follow the given protocol but only try to reveal others’ private input. Whereas, under malicious
situation the participants will manipulate whatever they need to get the data, including colluding
and/or malicious computation.
With theoretical and practical achievements over the last decade, MPC has finally evolved to a
point where performance shouldn’t be considered the primary impediment to use. With theoretical
constructions going back 35 years, there are substantial improvements in algorithmic and engineering
designs over the past decade to improve performance. The performance of MPC has improved by 4-5
3
3 BACKGROUND
orders of magnitude over the past decade (Figure 2). Both for comparison purposes and to account
for the effects of Moore’s law, we also show the performance of native AES computation over the
same time period.
Figure 2: Efficiency Improvement over MPC
Our goal is to build a MPC network with high availability for the first time, where any business
needs for secure computation can be conducted on the network or by using smart contracts on existing
blockchains such as Ethereum or EOS. This will bring several benefits: 1) MPC computation will be
as simple as plug-and-play. No prior knowledge is needed to set it up correctly. 2) Since dedicated
nodes run MPC, the cost for conducting such work will be much lower. and 3) The MPC ”cloud” can
bring awareness to the business world, as well as the general public, so that more secure computation
can be conducted using MPC.
3.2 Other Candidates of Secure Computation
In the past ten years, several technologies towards practical secure computation protocols have been
proposed and studied. These efforts have been classified into three primary domains, i.e. homomor-
phic encryption (HE), multiparty computation (MPC), and trusted execution environment (TEE).
3.2.1 Homomorphic encryption
Homomorphic Encryption(HE) is a form of encryption that allows computation on ciphertext, gener-
ating an encrypted result which, when decrypted, matches the result of the operations as if they had
been performed on the plaintext. With such a tool, one could outsource storage and/or computation
without endangering data privacy. Because HE allows calculation on encrypted data while remaining
encrypted, it has been extensively researched as a candidate for secure computation.
Figure 3: Homomorphic Encryption
The first concrete HE scheme was proposed in 2009, according to the work of Gentry. It introduced
an interesting structure, as well as, a nice trick called bootstrapping to reduced the inherent noise
4
3 BACKGROUND
that accompanied the running of additions and multiplications. This allowed practical somewhat
homomorphic encryption (SHE) to develop into fully homomorphic encryption (FHE).
Nevertheless, cutting-edge homomorphic schemes cannot provide an efficient way to compute large
depth arithmetic circuits due to the following constraints. First, “bootstrapping” adds an extra cost
to an already quite heavy process. Currently, practical use of HE focuses mainly on optimization of
an evaluated function, which avoids expensive processes by limiting the circuit multiplication depth.
In addition, using HE schemes will lead to a huge ciphertext expansion, by the overhead from 2,000 to
500,000 or even 1,000,000 (times) according to the scheme and the targeted security level. This is due
to the fact that homomorphic schemes must be probabilistic to ensure semantic security, and to the
particular underlying mathematical structures. As we can see, SHE schemes are the most promising
today in HE variants, and it will be utilized in our secure computation program mentioned later.
3.2.2 Zero-Knowledge Proof (ZKP)
Zero-Knowledge Proof (ZKP) is a method by which one party (the prover Peggy) can prove to another
party (the verifier Victor) that she knows a value x, without conveying any information apart from
the fact that she knows the value x. Recent blockchain project was developed to leverage ZKP as
a trusted off-chain comput프로젝트로 돌아가기