Tradeoffs Discussion: Access pattern hiding / Spicy Printfs

Secret Network
15

Here’s a concept for an alternative approach to SNIP-20 tokens that works by using off-chain compute based on queries. The main idea comes from Gabe, who’s been suggesting to break up potentially very large computations into off chain computations based on queries. Even though queries cannot directly modify the on-chain state, queries can produce output that is authenticated using a MAC or signature. A compute worker (any validator node) can submit the output back to the contract, which checks the MAC before applying the output on-chain. In this case, the computation is a linear scan (naive oram) over the entire array of account balances, and the query output consists of two things: 1) the transaction response (like withdrawals/side effects), which must be submitted back on chain, and 2) the re-encrypted array of account balances, which can be fed into the next query but does not have to be re-stored on chain. Illustration below then more notes and pseudocode.

image
image1658×984 58.3 KB

  • The main drawback is that because this is carried out by off-chain computation, a single transfer takes two transactions, which will typically be separated by 1 or more blocks.

  • The off-chain Queries are not automatically carried out by ordinary SN validator nodes. However, any validator node is capable of carrying it out if they choose to. Given the on-chain contract state, i.e. a checkpoint and a sequence of requests, the sequence of queries and resulting encrypted/MAC’d intermediate states are deterministic.

  • This clearly has a lot in common with L2 rollups/sidechains etc., but it’s not clear the best analogy. Since the off-chain computation is deterministic, this is most similar to off-chain compute systems like Truebit. The use of enclave-based MAC substitutes for a “SNARK”.

  • This is NOT Aepic-safe! The use of a MAC this way could turn a privacy failure into an integrity failure (knowledge of sk would enable fake withdraws). This could be mitigated by adding a Merkle tree proof that the contract checks for each transaction…. Still a gas cost savings relative to running an ORAM client in the contract.

  • This is just a simple example of a token, since it doesn’t aim to provide transaction histories or other features, but the same concept would work for those.

Contract state:
	- checkpoint [ (addr,amt),... ]	// Just balances
	- checkpoint_seqno
	- requests: [ (“xfer”,from,to,amt),.... (“deposit”,addr,amt), (“withdraw”,addr,amt)]
	- uint current_seqno; // This keeps track of the most recent request whose *side effect* (if any) has already been applied.
	- bytes32 sk // Secret key used to encrypt and authenticate balances & to mac the public side effects


handle_deposit(addr,amt):  
	// The “side effect” of deposit occurs when the request is scheduled, unlike withdraw where it is applied when it is finalized
requests.append((“deposit”,addr,amt))
handle_withdraw(addr,amt): requests.append((“widthraw”,addr,amt))
handle_xfer(from,amt,to):wes requests.append();


handle_finalizetx(resp, resp_mac):
        // Verifies the response for the next transaction
	verify_mac(sk, resp_mac, current_seqno+1 || resp) 

       // Only withdrawal responses have a side effect
       If (“withdraw”,addr,amt)) = resp:
    	    addr.send(amt)

        // Update the most recently finalized tx
        current_seqno += 1


query_getcheckpoint(): 
	// Produces an auth’encd copy of the current checkpoint
        return auth_enc(sk, checkpoint_seqno || checkpoint)
	
query_process(encst_inp, &encst_out, &resp, &resp_mac):
	// encst_out will include a re-encrypted version of the balances table.
	//    This could be written back to the checkpoint, but it is not needed
	// resp/resp_mac can be posted to the blockchain to finalize the tx and carry out side effects, in this case just withdrawals

	// Decrypt and authenticate
	(seqno, balances) := auth_decrypt(sk, encst_inp)

	// Get the next command to process
	cmd := requests[seqno]
	if cmd = (“xfer”,from,to,amt):
		snd_bal 
		// Linear scan to read.
		for (addr,bal) in balances: if addr==from: snd_bal := bal
		// If the transaction fails, we still need to update the state
                If (snd_bal < amt) {
  	             Balances’ := balances
                 } else {
		        // Write back
	         	Balances’ := []
 		        for (addr,bal) in balances:
			   If addr == from: balances’.append(addr,bal-amt)
			   If addr == to: balances’.append(addr,bal+amt)
			    Else: balances’.append(addr,bal)
                 }
         	encst_out := auth_enc(sk, seqno+1 || balances’)
		effect_out := ””  // no public side effect for tranfers
		effect_mac := mac(sk, seqno+1 || effect_out)


	If cmd = (“withdraw”,addr,amt):
		// Linear scan to read 
		bal = none
		for (addr’,bal’) in balances: if addr==addr’: bal := bal’


		If (bal < amt) {
			Balances’ := balances
			effect_out := mac(seqno+1,””)
		} else {
	        	// Write back
		        Balances’ := []
		        For (addr’,bal) in balances:
		         	If addr’ == addr: balances’.append(addr,bal-amt)
                                Else: balances’.append(addr’,bal)  
		        Encst_out := auth_enc(sk, seqno+1 || balances’)
		        Effect_out := (“withdraw”,addr,amt)
		        Effect_mac := mac(sk, seqno+1|| effect_out)
		}	


	// Deposit omitted but simpler than withdraw


query_accountbalance(addr, query_permit, seqno, encst):
	// Linear scan to let a user fetch their account balance.
	// Should check that the encrypted state matches the sequence number the user specifies

edit: here’s a gpt4 discussion that expands on the linear scan concept

7 Likes