bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 6쪽 중 2쪽
ation solution. In this protocol, the function is compiled into a circuit
and transmitted to a third-party execution environment where the data will be evaluated using the
circuit. Similar to FHE scheme, it cannot prove that the actual amount of work being done in remote
environment. In addition to that, ZKP simply cannot guarantee the computation is secured from
hacker of malicious party.
3.2.3 zk-SNARK
Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARK) is a protocol which
creates a framework in which a person – called prover – can quickly convince another person –
called verifier – that she or he “knows” a secret without revealing anything about the secret. The
first constructions of SNARK protocols were inspired by the Probabilistically Checkable Proof (PCP)
theorem which shows that (Nondeterministic Polynomial time) NP problems statements have “short”
PCPs[26]. New instantiations were found which allow faster and shorter proofs, when a pre-processing
state is permitted.
zk-SNARKs intend to enhance the privacy of users transacting on the Zcash blockchain. With
cryptocurrencies such as Bitcoin, an individual can identify user addresses and track the movement
of value between transacting parties on the blockchain. In this case, Bitcoin only provides users
with pseudonymous protection, rather than complete anonymity. zk-SNARKs are designed to solve
this problem by completely encrypting user transaction information on the Zcash blockchain. An
abstract zk-SNARK description can be denoted as Alg. 1
Algorithm 1 zk-SNARK
KeyGen: (vk,pk )← KeyGen(circuit C,λ ).
Prover: π← Prover(pk, public input x, secret input w)
Verifier:∃w s.t. C(w,x )← Verifier(π,vk,x )
3.2.4 Trusted Execution Environment (TEE)
Trusted Execution Environment (TEE) is a tamper resistant processing environment that runs on
a separation kernel [2]. It is another trend to solve a secure computation problem. An ideal TEE
guarantees the authenticity of the executed code, the integrity of the runtime states (e.g. CPU
registers, memory and sensitive I/O), and the confidentiality of its code, data and runtime states
5
3 BACKGROUND
stored on a persistent memory. In addition, it shall be able to provide remote attestation that proves
its trustworthiness for third-parties.
Hardware manufacturers are eager to propose their own trusted hardware solutions but lack a
general standard over different platforms. Most prominent process unit designers have embedded
their hardware secure module in their products (Ex. Intel Software Guard Extensions (SGX), ARM
TrustZone, AMD Secure Encrypted Virtualization (SEV) and NVIDIA Trusted Little Kernel (TLK).
Figure 4: Trust Execution Environment
Software Guarded Execution (SGX) is a set of instructions promoted by Intel to enable code
to be run at private region of CPU. The benefit of such implementation is that the application is
secured at hardware level with cost of developing a software. Most solutions to provide privacy to
smart contracts are based on SGX, which was a sensible choice years ago. Several projects existed
are using SGX as off-chain computation solution.
However, recent attacks have proven SGX to be inadequate. This seemingly secure protocol
is, in fact, not secure at all. The remote attestation does not prevent a malicious cloud service
provider from first faithfully responding to remote attestation queries, but then emulate the rest
of the protocol (such as KeyGen and CSR) outside of the enclave. In other words, SGX is not a
protocol designed for “Universal Composition” (UC) where, the real-world behavior and the ideal-
world definition (function) of a protocol are computationally indistinguishable for every adversary-
controlled environment. In simple term, with TEE, one can trust the hardware but not the person
controlling the hardware. Therefore, the SGX stack is best used in a permissioned network[20], where
all nodes are pre-approved and the environment is certified and trusted.
Furthermore, SGX instructions can only be used on Intel’s CPU. In cases like deep learning, where
algorithms are accelerated on GPU, or in situation that Intel is not considered to be trustworthy,
the SGX solution will bear significant risk. In addition, the proper use of TEE is also a nontrivial
work, especially the collaboration of different TEE modules.
6
3 BACKGROUND
3.3 Comparison
3.3.1 Trust Dependency
Privacy-preserving computation can be sorted into two development directions: secure computation
and trusted computation. The prior mainly focuses on the cryptography security brought by hard
problems that are elaborately designed using mathematics. The security is derived purely from the
number theory, which means even with unaffordable computing power, an adversary cannot break
the encryption. The latter one starts from a different point, which tries to enforce the computing
involvement to consistently behave in the expected way. Enforcing the behavior is achieved by
hardware authentication, memory encryption, specific instruction design, etc. These technologies are
always bound to the hardware platform such as the memory storage or processing elements.
Obviously, both Homomorphic Encryption and MPC belong to secure computation, and Trusted
Execution Environment(TEE) is the effort of trusted computation. In brief, secure computation is
more suitable to be used in permissionless network while trusted computation relies more on physical
entities and can be used in a permissioned network such as Hyperledger[38].
3.3.2 Scalability and Flexibility
Given the foundation of mentioned computation methods, it can be observed that one can evaluate
a secure computation on any computing power, either a data center or an edge device such as an
automobile and phone. Due to the TEE’s design methodology, users have to transplant the program
from one platform to another by fitting their work into the safes. This feature makes the TEE less
flexible than the pure protocol solutions. Considering the underlying device independency, MPC or
HE can take advantage of mutual tool chains of hardware manufacturers and have future potentials
for hardware accelerations.
As for different scenarios of computation, MPC can transform into a suitable pattern to make
a trade-off between computation complexity and secureness. The nature of MPC can also satisfy
various data-privacy input conditions. HE may support multiparty input as well by using distributed
encryption and decryption, but the overhead of bootstrapping limits the secure functions evaluated
on the HE.
3.3.3 Practical Efficiency
Thanks to the continuous effort of cryptographers and computer scientists in the last decade, different
frameworks of MPC designed to solve various type of cases have been invented. We will develop a
general purpose MPC network that achieves security in a malicious, dishonest, majority n-party
setup.
Taking Intel SGX[27] as the representative of TEE, the main overhead of SGX, compared with
plaintext manipulating, is caused by fetching input from normal memory to the enclave local memory
that involves encryption. According to the experiments on the enclaves, the Intel enclave instructions
did not achieve the best performance. On the other hand, the optimal algorithm on plaintext cannot
get the same throughput when processing enclave local memory.
For S/FHE and MPC implementation, multiplication over ciphertext is the most frequently called
and fundamental operation. Table 1 lists the state-of-the-art literal performance for both systems.
The final column shows the latency of multiplication for different parameter settings. Although the
diagram compares hardware implementation of SHE[9] with practical software MPC[21], it can be
observed that MPC is 1-2 orders of magnitude faster than SHE. Considering in the future, dedicated
hardware acceleration of MPC building blocks will be developed, and there should be another 10-100
times throughput improvement potential for MPC. Therefore, there exists 3-4 orders of magnitude
of performance gap between HE and MPC. Furthermore, the most expensive operation of FHE is
7
3 BACKGROUND
bootstrapping which enables unlimited multiplication depth is not listed in table. This may bring
another slowdown in FHE computation.
Category Scheme Security parameter Operation
HE
Hardware imple-
mentation n q homomorphic multiplication
YASHE-NTT 4096 125 bits 6.5ms
YASHE-NTT 16384(SIMD) 512 bits 48ms
YASHE-NTT 32768(SIMD) 1228 bits 121ms
MPC
Software implementation Statistical security parameter Mult triples generations
MPC 128 bits 0.23ms
Overdrive: High Gear 128 bits 0.43ms
Overdrive: Low Gear 128 bits 0.067ms
Table 1: Performance Comparison of HE and MPC
3.3.4 Conclusion
In this section we discussed the history of MPC and its cryptographic properties and demonstrated
that it is actually a very good candidate for mutually-distrusted parties to conduct secure computa-
tion together a very similar setting to the blockchain network.
We also visited several technologies currently existing as candidates of secure computation, namely
Homomorphic Encryption, Zero-Knowledge Proof, and Trusted Execution Environment. Our dis-
coveries indicate that, while some technologies have advantage such as computation efficiency, they
are not offering security and features needed in a permissionless network. In essence, we need to
be able to verify the secureness, correctness and privacy-preservingness of computation. Detailed
aspects under consideration are as follows:
Efficiency The speed of computation. Our experiments have found that, TEE is on par with
clear text computation. Followed by MPC, about one magnitude slower, as forementioned. As for
ZK-SNARK, it has around 10 3 times overhead[6]. The least favorable choice in terms of efficiency is
FHE, with about 10 7 to 108 times slower.[9]
Privacy-preserving Privacy-preserving here refers to the capability of evaluating a function on a
dataset, while not revealing the detail to anyone. This is the core of secure computation.
Proof of Correctness Prove that the computation work is actually using the prescribed function.
In a trustless network, it is very important to prove that a certain function is evaluated in a
correct way. In blockchain, it is simply done by repeated computation on every node running the
smart contract. Consensus can be made once every participating node reaches on the same result.
However, in the context of secure computation, computation is not carried out on every node but
delegated to certain node(s) for the task. One needs to submit proof that computation has done the
work with prescribed routine, or the result cannot be trusted.
Proof of Computation Prove the amount of work the participating node has done.
In Bitcoin and other PoW-style blockchain network, participating nodes prove their work by
solving a hard problem (puzzle) and submit the hash value according to the nonce determined at
8
3 BACKGROUND
the beginning of the block. It is trivial work for nodes to verify the result (hash) and prove that
the node has indeed solved the puzzle. In a computation network, it is also important to know how
much work has been done in the computation, so the node can be rewarded with a corresponding
token. In MPC, the amount of computation can be proved by counting the triples consumed during
the computation.
Proof of Secureness Prove that the computation is actually carried out in the secured environ-
ment.
When computation is not repeated on every node, one needs to submit proof that the compu-
tation is carried out in a secured environment. Although this is what TEE is designed for, this
seemingly naive question is actually very hard to prove. As mentioned earlier, secure computation
is a cryptography process that guarantees the computation process is following the protocol or the
result cannot be accepted. But trusted computation, on the other hand, enforces the process to be
consistent with designed security (i.e. run the function) using trusted hardware. Nevertheless, in a
permissionless network, one cannot convince other nodes to trust his result just by claiming it got
remote attestation from a centralized server. Furthermore, even the remote attestation proves the
security of the environment, one cannot prove the code is executed in that trusted environment.
A final conclusion with all facts related to blockchain construction is listed in table 2.
MPC FHE ZK-SNARK TEE
Efficiency Acceptable to Fast Prohibitively Slow Acceptable Fast
Privacy-preserving Yes Yes No No
Trustless Yes Yes No No
Proof of Correctness Yes No Yes No
Proof of Computation Yes No No No
Proof of Secureness Yes Yes No No
Table 2: Secure Computation and Trusted Execution
9
4 SYSTEM OVERVIEW
4 System Overview
The ARPA network is designed with two layers: consensus layer and computation layer. The com-
putation layer is responsible for conducting ARPA’s Multiparty Computation protocol, while the
consensus layer makes sure that transactions and other metadata are recorded and reach consensus.
Each blockchain node is comprised of two layers/services.
The system’s overall design is illustrated in Figure 5.
Figure 5: ARPA overview
Consensus layer ARPA’s network is designed as a permissionless network where participants can
join autonomously, contribute their computation resources, and earn economic return. To achieve
this, we need to faithfully record the transaction information, as well as verification scheme for the
computation. This allows the network to form the quorum based on historical performance (with a
credit system).
The consensus service includes Account Signature, Computation Verification, Node Communi-
cation, Credit system, and Consensus protocol. A decentralized ledger is implemented to record
transnational and stateful data.
We leverage Secret Sharing and Threshold Signature to create decentralized randomness in block
generation. This uncertainty is used to prevent anyone from seizing control of the block by creating
above average probability of block-signing rights.
Computation layer This layer is mainly a protocol for participating nodes to jointly perform
secure Multiparty Computation (MPC) with arandom quorum, additional coordination, model com-
pilation, Secret Sharing, distributed storage, error handling, computation proof generation, decen-
tralized preprocessing, network load-balancing, and other tools to make sure nodes in a quorum can
finish task with designated cryptography features.
The MPC protocol is designed with an economic incentive/penalty so that it will cost a malicious
node more than it can gain from the system.
We will come back to this in Section 7.
10
4 SYSTEM OVERVIEW
4.1 Interoperability
The need for privacy-preserving computation is universal. It would be a greater benefit for other
popular blockchains, such as Ethereum and EOS, to have secure computation capability. Therefore,
APRA’s system is designed to be inter-operable with other blockchain systems, while maintaining
our own chain as a standalone network for secure computation. To be able to conduct off-chain
computation, our network nodes need to monitor smart contract information on other chains, and
act upon requests from these smart contracts. This realization of secure computation is called Private
Smart Contract. This completely obscures the data from the public, while keeping the computation
auditable. Private Smart Contracts will later be described in further detail.
4.2 ARPA Virtual Machine (AVM)
Similar to Ethereum Virtual Machine (EVM), The Arpa Virtual Machine is a Turing Complete
Virtual Machine that can run smart contracts in it. However, to enable secure computation and other
advanced features such as Private Smart Contract, AVM is shipped with a stronger toolset with close
to native performance. To this end, AVM adopts WebAssembly(WASM), a binary instruction for
a stack-based Virtual Machine, which lets us do more with less. WASM brings faster code, smaller
deliverables, and less overhead. The Virtual Machine can execute bytecode compiled from scripting
language, such as JavaScript and Python, for better adoption and less learning curve.
To enable the execution of ”Private Smart Contract”, a smart contract that can protect data
privacy, function privacy, participants’ identify and their state change, the EVM has a built-in
function cryptography library for easier computation dispatch and verification.
AVM also supports native Oracle implementation. External data can be fetched and processed
without the need to setup an oracle server. This will be very handy when the computation verification
package is sent back from the secure computation layer.
11
5 ARPA MULTIPARTY COMPUTATION PROTOCOL
5 ARPA Multiparty Computation Protocol
The protocol implemented in ARPA’s computation network is organized as Figure 6. The procedure
can be viewed as a two-phase protocol: Preprocessing and Computation. The computation phase is
the main procedure that involves secret sharing, function evaluation, and revealing outcomes. On
the other hand, the preprocessing phase is the foundation which provides necessary raw materials for
computation. We separate these two phases apart because preprocessing is independent of both the
function and the data.
Figure 6: ARPA MPC protocol
5.1 Computation Phase
During the computation phase, the main task is to securely evaluate an arbitrary circuit on pri-
vate inputs which is keep secret throughout and reveal the result only when the parties follow the
prescribed protocol. This phase can be concluded as a 3-stage protocol: input, evaluation, output.
After private inputs are provided and secretly shared, all parties perform addition and multiplication
on shared values, collaboratively, according to the arithmetic circuit. Eventually, results are opened
after computing verification.
5.1.1 Sharing secrets
At the beginning of the computation phase, the input needs to be shared among all parties. This
process is called secret sharing. Secret sharing is the method of distributing a secret among a group
of participants, each of whom is allocated a share of the secret. The secret can be revealed only when
a sufficient number of shares are combined together. Individual shares are unreadable ciphertext on
their own.
A secret sharing scheme usually consists of two main functions, Share and Reconstruct.
Share allows one party to share a secret, x, among n parties such that the secret remains secure
against an adversary up tot−1 parties in a (t,n )-threshold scheme. While Reconstruct allows any
group of t or more parties together to open the secrets. In ARPA MPC, we design the secret-sharing
12
5 ARPA MULTIPARTY COMPUTATION PROTOCOL
scheme to work effectively under universally composable security so that the threshold is set to n,
meaning our system is secure up to n− 1 colluded malicious parties.
In the Input step, parties need to use shares of random values: each party Pi holds some ri and
the secret value ri is uniformly random and not known by any party. First, every party sends their
share ri of r to party Pprovider. This is called a ‘partial opening’ because now Pprovider discovers the
value of r by summing the shares. Party Pprovider then broadcasts his input x−r. Party P1 sets its
share of x as x1 =x−r +r1, and for Pi sets its x share of as xi =ri. In practice, it is not always
P1 who does a different computation. Now we turn x into⟨x⟩ and shares are xi.
5.1.2 Evaluating circuits
On ARPA’s MPC framework, the function to be evaluated should be expressed in an arithmetic
circuit representative. A general method to transfer high-level functions into arithmetic circuits are
included in our compiler. which is concretely described in the preprocessing phase in section5.2. This
compilation is done prior to computation phase.
The arithmetic circuit basically consists of addition and multiplication operations. In the eval-
uation step, since the secret sharing scheme is additive and linear, addition can be done via local
computation which has no com프로젝트로 돌아가기