ARPA 백서

bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 6쪽 중 3쪽

munication cost. Specifically, to compute ⟨a +b⟩ or⟨α·a⟩, each party simply does ai +bi or α·ai. We then get the ⟨a +b⟩ and⟨α·a⟩ in secret shares type. Multiplication on secret values, however, requires some interaction between the parties. Beaver’s triples are used to facilitate the online multiplication. When parties are scheduled to compute ⟨x·y⟩ given⟨x⟩ and⟨y⟩ one available ‘triple’⟨a⟩,⟨b⟩,⟨c⟩, where c =a×b is taken from the pre-processed raw material. Then, by broadcasting xi−ai and yi−bi, each party can compute x−a and y−b. Which now means these intermediates are publicly known. Eventually everyone can locally compute zi = (x−a)(y−b) +xi(y−b) +yi(x−a) +ci, so that they have a secret share of ⟨z⟩. ⟨z⟩ =⟨c⟩ +d·⟨b⟩ +e·⟨a⟩ +d·e =⟨a·b + (x−a)·b + (y−b)·a + (x−a)· (y−b)⟩ =⟨x·y⟩ (1) The upshot is that with enough amount of triples, the MPC engine can perform any multiplication depth computing on secret shared data, and hence we can compute any arithmetic circuit. For the reason that some intermediates like x−a are opened for subsequent procedure, triples cannot be reused because this would reveal information about the secrets. Importantly, it can be observed that triples are independent of not only the input data, but also the circuit to be evaluated. This means that we can generate these triples at any point prior to evaluating the circuit. The value of triples are not known by any parties when generated. Each party only knows a share of each of ‘some values’ for which they are told this relation holds. Moreover, since addition, scalar multiplication, and field multiplication are inexpensive in terms of communication and computation, the computation phase is both highly efficient and information-theoretically secure. With the methodology of addition and multiplication on secret shares, we can build any com- putable functions on arithmetic circuits. Taking an example of secure signed floating number multi- plication like Alg.2 [2] which involves exponents addition, sign bit operation and mantissa multipli- cation. Specifically, multiplication of two floating point numbers ⟨v1,p 1,z 1,s 1⟩ and⟨v2,p 2,z 2,s 2⟩ is performed by first multiplying their mantissa v1 and v2 to obtain a 2l-bit product v. The product then needs to be truncated by either l or l− 1 bits depending on whether the most significant bit of v is 1 or not. In the protocol below, it is accomplished obliviously on lines 2-4. Partitioning this truncation into two steps allows us to reduce the number of interactive operations at a slight increase in the number of rounds. After computing the zero and sign bits of the product (lines 5-6), we obviously adjust the exponent for non-zero values by the amount of previously performed truncation. 13 5 ARPA MULTIPARTY COMPUTATION PROTOCOL Combining the above, we have now established roughly how to evaluate an arithmetic circuit. Algorithm 2 Secure Floating Number Multiplication Require: ⟨[v1], [p1], [z1], [s1]⟩,⟨[v2], [p2], [z2], [s2]⟩ Ensure: ⟨[v], [p], [z], [s]⟩← FLMul(⟨[v1], [p1], [z1], [s1]⟩,⟨[v2], [p2], [z2], [s2]⟩) Method: 1: [v]← [v1][v2]; 2: [v]← Trunc([v], 2l,l− 1); 3: [b]← LT([v], 2l,l + 1); 4: [v]← Trunc(2[b][v] + (1− [b][v],l + 1, 1); 5: [z]← OR([z1], [z2]); 6: [s]← XOR([s1], [s2]); 7: [p]← ([p1] + [p2] +l− [b])(1− [z]); 8: return⟨[v], [p], [z], [s]⟩; 5.1.3 Information Theoretic MAC When using multiplication triples and a linear secret-sharing scheme with threshold t, we obtain a passively secure MPC protocol that tolerates up to t corruptions. In the dishonest majority setting with up to n− 1 corruptions, the most natural secret sharing scheme to use is simple additive secret sharing, where x∈ F is shared between n parties by distributing n random shares xi satisfying x = ∑n1xi. Clearly, any n− 1 shares reveal no information about the secret. However, to achieve active security, this is not enough to guarantee correct opening. Message Authentication Code (MAC) is a value that can be used to confirm a message has been created by a certain party who knows the MAC key, and to detect if a message has been changed. The main tool for achieving active security in modern, secret sharing-based protocols is information- theoretic MAC, as mentioned in the [13] [13]. A typical information-theoretic MAC scheme is listed as Alg.3. Algorithm 3 MAC Check Procedure Require: global MAC key shares αi, public sets of opened values a1,...,a t, associated MAC value shares γ(aj)i Ensure: succeed if MACCheck passed, or ∅ if inconsistant MAC value is found. Method: 1: All parties samples a seed si and ask Commit to broadcast τsi. 2: All parties open τsi and add up to get an agreed seed s. 3: All parties sample random vector r on s 4: Each player computes the public value a← ∑tj=1rj·aj. 5: Playeri computes γ(a)i← ∑tj=1rj·γ(aj)i, and σi←γi−αi·a. 6: Playeri asks Commit to broadcast τσi. 7: Every player open τσi. 8: If σ1 +··· +σn = 0, the players output ∅ and abort. The security requirement is that the verification algorithm should succeed if and only if m is a valid MAC onx, except with negligible probability. The information-theoretic property of the MAC scheme means that security holds even for an unbounded adversary. The MAC scheme we deployed in computation network derives purely from information theory. In other words, it cannot be broken even if the adversary had unlimited computing power. The adversary simply does not have enough information to break the encryption. 14 5 ARPA MULTIPARTY COMPUTATION PROTOCOL MAC plays a crucial role in making MPC verifiable. MAC check scheme makes sure that malicious party in the group can not bypass the security check by blending the verification value into the computation process. 5.1.4 Revealing outcomes Once we have the MAC representations, it is fairly easy to describe the online phase of an MPC pro- tocol in the preprocessing model. Since both of the authenticated secret-sharing methods described are linear, the parties can perform linear computations by simply computing locally on the shares. We can also add a public constant c to a shared value [x] :P1 adds c to her share, and each party Pi adjusts their MAC by c·αi. To multiply two secret-shared values, the parties need a random authenticated multiplication triple from the preprocessing phase. We also need some additional preprocessing data for sharing inputs, in the form of random authenticated masks where only the party providing input knows the value. When outputting a result of the computation the parties must check the MACs using the MAC check procedure described previously, which we denote by ∏MACCheck . In summary, the computation process can be concluded as the protocol Alg.4 Algorithm 4 Computation Phase Protocol Initialize: The parties first invoke the preprocessing to get the shared secret key α , a sufficient number of multiplication triples ( ⟨a⟩,⟨b⟩,⟨c⟩), and random values ⟨r⟩, as well as single random values⟨t⟩,⟨e⟩. Then the below steps are performed according to the compiled function structure. Input: To share secret input x of party Pinput, involved parties take a random value ⟨r⟩. Then do the following: 1. ⟨r⟩ is opened to Pinput. 2. Pinput broadcasts ϵ←x−r. 3. The parties compute ⟨x⟩←⟨ r⟩ +ϵ. Add: To add⟨x⟩,⟨y⟩, the parties locally compute ⟨x⟩ +⟨y⟩ Multiply: To multiply⟨x⟩,⟨y⟩, the parties do the following 1. Sacrifice a) ⟨t⟩ is opened publicly, take two triples for check b) Evaluate t·⟨c⟩−⟨ h⟩− σ·⟨f⟩− ρ·⟨g⟩− σ·ρ, where ρ :=t·c−h,σ :=b−g c) Sacrifice one triple and authenticate the other 2. Multiplication (a) Take one authenticated triple (b) Evaluate ⟨z⟩ =⟨c⟩ +ϵ·⟨b⟩ +δ·⟨a⟩ +ϵ·δ, where ϵ :=x−a,δ :=y−b Output: The parties unite to reveal output y in the presence of ⟨y⟩. Correctness of computation should be checked first. Then do the following: 1. Generate random linear combination coefficient ri = ei. Then compute a = ∑jrjaj, where aj are opened intermediates. 2. Pi commits to ri = ∑jrjγ(aj)i,⟨y⟩,γ (y)i. 3. Open α. 4. Check α·a = ∑iγi,α·y = ∑iγ(y)i. If MAC check passed, output y := ∑i⟨y⟩. 15 5 ARPA MULTIPARTY COMPUTATION PROTOCOL 5.2 Preprocessing Process The preprocessing model began with Beaver’s “circuit randomization” technique, which allows any arithmetic circuit to be securely computed by randomizing the inputs to each multiplication gate, using a multiplication triple, which is a triple of secret shared values ⟨a⟩,⟨b⟩,⟨c⟩ where a and b are uniformly random (in a finite field) and c = a·b. Given this, two secret shared values ⟨x⟩,⟨y⟩ can be multiplied by publicly reconstructing d =x−a and e =y−b and then computing Sincea andb are uniformly random, revealingd ande does not leak any information on the inputs x,y. The key advantage of this approach is that any MPC protocol based on linear secret sharing that operates on circuits in a gate-by-gate manner can now be easily recast in the preprocessing model: the preprocessing phase simply consists of creating many multiplication triples, and in the online phase the circuit is securely evaluated using these triples. Note that additions and linear operations can be evaluated locally because the secret sharing scheme is linear. After evaluating the circuit, each party broadcasts their secret shares of the outputs and reconstructs the result. The preprocessing stage is completely independent of both the inputs to the function being computed and the function itself (apart from an upper bound on its multiplicative size), and creating triples is typically the bottleneck of a protocol. Algorithm 5 Preprocessing Phase Protocol Initialize: generates global MAC key α and distributed key βi 1. The players agree on the public key pk 2. Each Pi generates αi, βi, and define α := ∑iαi 3. Each Pi computes eαi = Enc(αi), eβi = Enc(βi), and zero-knowledge proves on ciphers 4. Compute eα =eα1 ⊞··· ⊞eαn, and DistDec it to each party. Random Values: generates random values for secret sharing 1. Each Pi generates ri, and define r :=ri. 2. Each Pi computes eri = Enc(ri), and zero-knowledge proves on ciphers. 3. Compute er =eri ⊞··· ⊞ern. and DistDec it to each party. Triples: generates multiplicative triples for online computation 1. Each Pi generates ai, bi, and define a := ∑iai, b := ∑ibi. 2. Each Pi computes eai = Enc(ai), ebi = Enc(bi), and zero-knowledge proves on ciphers. 3. Compute ea =eai ⊞··· ⊞ean, eb =ebi ⊞··· ⊞ebn. and DistDec it to each party. 4. Compute ec =ea ⊠eb, and DistDec it to each party. Considering the malicious security model, we introduced two methods to solve the following issues: First, Zero-knowledge is applied to prove that certain values lie within a certain bound in case that the adversaries introduces noise to pollute honest parties’ input. Second, distributed decryption allows corrupted party to add noise in triples, where we use sacrifice to double check triples validation. Circuit used in this paper is the terminology describing evaluation functions in cryptography, but not the hardware circuit. To represent a computation, we can use either Boolean circuits or Arithmetic circuits. The main difference is with respect to their input’s types and their gates types. It is nature to use Boolean notation when processing programs on bits and by Boolean operations, such as XOR, AND. Nevertheless, arithmetic circuits work on inputs in fields F by arithmetic operations, like field additions and multiplications. Figure 7 shows a sample of arithmetic circuit. 16 6 THE SECURE COMPUTATION PROCESSES Figure 7: Sample Arithmetic Circuit 5.2.1 Compiling functions An MPC compiler translates a conventional function into an arithmetic or boolean circuit, in order for it to be accepted in MPC virtual machine. Corresponding to the normal compiler, which transforms high level language to assembly code, The MPC compiler turns the high-level function into MPC- friendly instructions. The difference between arithmetic and Boolean function is not about functionality but the modal- ity. The reason to choose one representative depends on the functions type to perform. Due to the mathematical basis, cryptography tools rely mainly on computation of field elements, which are treated as single input but not a string of bits. Then it makes sense to represent in arithmetic ways. However, many applications involve non-arithmetic operations like integer comparison, which is a basic procedure in many computations. In this case, implementing this non-arithmetic operation as an arithmetic one would be very inefficient, and Boolean circuits are a more natural representation. Circuits Arithmetic Boolean Elements Bit {0,1} / F2 Finite field ( Fpk)s Underlying Operations OR, NOT, AND, XOR Addition, Multiplication Transform Like an Arithmetic Logic Unit in processor 0 as addition neutral 1 as multiplication neutral OR(a,b ) =a +b−a×b Table 3: Circuit Comparison The two representatives of circuits can be transformed to each other by an arbitrary translation shown in Table 3. The computable functions class of Boolean circuits of polynomial size correspond to the class of arithmetic circuits of polynomial size. Actually, we can picture arithmetic circuits as a generalization of Boolean circuits to arbitrary fields. There have been many papers that worked on extending cryptographic methods that work well for computations represented as Boolean circuit to the setting of computations which are best captured by arithmetic circuits, to get efficiency improvements for those circuits, or on bridging between methods adapted to both circuits, to capture computation whose best representation is a mix between the two. 6 The Secure Computation processes The Secure Computation process starts from the application layer, typically by triggering a smart contract. To support off-chain computation, our network will observe smart contract events on a designated blockchain network, execute the computation work on ARPA, then submit results and proofs back to the smart contract. This process consists of 5 steps, as illustrated in Figure 8. 1. On the application layer, a smart contract representing a real-world contractual logic is initiated by a party who wants a heavy computation task or privacy-preserving task to be executed in 17 6 THE SECURE COMPUTATION PROCESSES Figure 8: The Secure computation process the network while keeping the detail in private. The smart contract was created by the data provider (who charges a fee for providing information but doesn’t want to expose the data to the public), or by several parties who want to engage in some private business logic. To support off-chain computation, the smart contract could be one on another blockchain network. Our nodes can optionally observe the particular event defined in smart contract. And the result can be sent back to the smart contract by sending a message to the smart contract. Once the smart contract received the deposit and other necessary information, such as data provider and function to be evaluated, the observing nodes will broadcast the event in the ARPA network, inviting other parties to join the MPC task. 2. All computation nodes who are interested in participating in the computation will start the bidding process. They are asked to deposit minimum required token to be eligible (detailed in Cryptoeconomics section). Next, a group of computation nodes are randomly selected, based on node’s performance and condition, success rate, latency, etc. The random function used in this selection process is a decentralized random function, discussed in subsection 6.2. One thing worth mentioning is that the data provider and data consumer are included in the group, making the computation nodes impossible to collude. This design is required so that at least one party is honest. Because our threshold protocol is secure up to n-1 parties, we can claim that this setup is cryptographically guaranteed to be secure. Once the quorum is determined, all bidding notes will know the result locally. This is a very important feature because even if the bribing attacker exists, he doesn’t know whom to bribe or attack. The selected nodes don’t need to broadcast the fact that they are selected, but instead they hold the cryptographic proof till the end of the process. 3. At the computation layer, the nodes in the pre-selected quorum coordinate together to perform ARPA MPC. As already described in previous section, they first secret-share the data. Then, a compiled function, in the form of boolean/arithmetic circuit is prepared for all parties. For each party, their job is simply to evaluate the function by following the circuit’s instruction. During the computation, the parties actively exchange values on peer-to-peer communication, which is also secured with TLS. When the computation reaches the end, results and computation proofs will be produced. The computation proofs are Information Theoretic MACs produced alongside with the computation, i.e. they generated with the same computation steps as the 18 6 THE SECURE COMPUTATION PROCESSES result, making it impossible to forge. The results and MAC values will be signed with all nodes’ secret keys to prevent forgery. MACs are information-theoretic secure to convey the correctness of computation, so that the computation is verifiable. The validation complexity isO(1), which means it consumes constant time to compute. Therefore it is possible to be executed in any VM. 4. If the verification is passed, the payment will be processed, the gas fee will be distributed, and the meta-data of the transaction will be recorded on the blockchain. The ARPA consensus algorithm is discussed in section 7.6. 5. The result and MACs will also be sent back to smart contract. All nodes running smart contract will validate the authenticity of MACs, and then check the MAC’s correctness. The detail of verification procedure is detailed section 6. If the smart contract is running on another blockchain network, then other nodes will reach consensus by their own consensus algorithm. 6.1 Smart Contract A smart contract is executable code that runs on the blockchain to facilitate, execute and prove an agreement between untrusted parties without the involvement of a trusted third party. The benefit of a smart contract is that it can reliably transfer value, make decisions or perform computation as if there is a trusted third party. It also makes the whole executing process transparent, as anyone on the chain can audit the smart contract code and run the code to verify the results. The data processed or generated by a smart contract is also traceable in the receipt. With many advantages, a smart contract has its limitations. The correctness of the smart contract is based on a network-wide consensus, which naturally requires every validating node to re-run it for verification purpose. This redundancy makes executing the smart contract very expensive, or in another words, the usability of the smart contract is limited. Another concern is privacy, as the smart contract itself and its data are transparent to every node on the blockchain network. Therefore, our approach to support off-chain computation for other chains is using smart contracts to carry the meta operations, including computation initiation, task broadcasting, and validation, so that the blockchain can reach consensus with computation proof. A pseudo-code example is provided to illustrate this concept. All of the heavy-lifting computation, including secret sharing and multiparty computation, are conducted by the MPC network. 1 /* * Written in Solidity - like pseudo - code . */ 2 contract A r p a C o n t r a c t { 3 struct T r a n s a c t i o n { 4 uint256 txnId ; 5 address d a t a C o n s u m e r ; 6 address d a t a P r o v i d e r ; 7 string d a t a A d d r e s s ; 8 uint256 n u m P a r t i c i p a n t s ; 9 uint256 fund ; 10 bool i s F i n i s h e d ; 11 } 12 13 struct M pc Re su lt { 14 // MPC may fail for various reasons , e . g . the fund is not enough to pay 15 // c o m p u a t i o n fee g en er at ed at run - time , or some parties aborted th
프로젝트로 돌아가기