DECO

AbstractThanks to the widespread deployment of TLS, users can access private data over channels with end-to-end confidentiality and integrity. What they cannot do, however, is prove to third parties the provenance of such data, i.e., that it genuinely came from a particular website. Existing approaches either introduce undesirable trust assumptions or require server-side modifications. As a result, the value of users' private data is locked up in its point of origin. Users cannot export their data with preserved integrity to other applications without help and permission from the current data holder. We propose DECO (short for decentralized oracle to address the above problems. DECO allows users to prove that a piece of data accessed via TLS came from a particular website and optionally prove statements about such data in zero-knowledge, keeping the data itself secret. DECO is the first such system that works without trusted hardware or server-side modifications. DECO can liberate data from centralized web-service silos, making it accessible to a rich spectrum of applications. To demonstrate the power of DECO, we implement three applications that are hard to achieve without it: a private financial instrument using smart contracts, converting legacy credentials to anonymous credentials, and verifiable claims against price discrimination.
Year2019
Link to the paperhttps://www.deco.works/
Relevance scoreVery relevant
Quality score5
LabelsImplementationsLegacy compatibleManagement of credentialsPossible tool in larger solutionSybil resistance insights

TL;DR

DECO is a protocol that enables users to prove (potentially in zero-knowledge) to a verifier that he pulled a piece of data from a certain web server via a TLS channel. Unlike Town Crier or TLS-N, it works without trusted hardware or modification on the server side.

The main idea is to share the client keys among the prover and the verifier so that they can jointly act as a single client like in a standard TLS protocol. Note that a server cannot distinguish whether it interacts with a client of a TLS session or a tuple of prover and verifier in a DECO protocol.

Preliminary

Roles

Notation

Transport Layer Security (TLS) protocol

Source: https://www.ssl2buy.com/wiki/wp-content/uploads/2021/02/ssl-tls-handshake.png Figure 1. This figure depicts the general workflow of a TLS handshake.

  1. The client sends “client hello” to the server, along with TLS type, and cipher suite with a random rcr^c generated by the client.
  1. The server receives the data, and sends “server hello” to the client, along with a certificate, cipher suite with a random rsr^s generated by the server, and the server’s public key KsK^s.
  1. The client receives the data, and generates a random premaster secret rpsr^{ps}, encrypts it with KsK^s, and sends it to the server.
  1. The server using the secret key decrypts the message and obtains rpsr^{ps}. For both server and client, the session key is rc+rs+rpsr^c+r^s+r^{ps}.
  1. The server uses the session key with symmetric encryption to encrypt the handshake completes the message and sends it to the client. TLS handshake complete.

DECO Protocol

Source: https://arxiv.org/abs/1909.00938 Figure 2. This figure depicts an overview of DECO protocol. It is achieved in three phases, i.e. three-party handshake, query execution, and proof generation.

Trigger:

  • Verifier (V\mathcal{V}) is asked for off-chain data,
  • V\mathcal{V} generates a session ID (sidsid), a query template (QueryQuery), and a statement (StmtStmt) to be proven.
  • V\mathcal{V} sends (sid,Query,Stmt)(sid, Query,Stmt) to P\mathcal{P}.

Three-party handshake

The goal of the three-party handshake is to run a TLS handshake protocol, which for the server (S\mathcal{S}) side is just following the standard TLS protocol, but the prover (P\mathcal{P}) and verifier (V\mathcal{V}) use a separated key which can be combined to communicate with the server. (All additions and multiplications are Elliptic Curve operations)

  1. P\mathcal{P} sends “client hello” to S \mathcal{S}, along with TLS type, cipher suite with a random rcr_c generated by P\mathcal{P}.
  1. S\mathcal{S} receives the data, sends “server hello” to P\mathcal{P}, along with certificate certcert, cipher suite with a random rsr_s generate by the server, and server’s public key YSY_S and a signature σ\mathcal{\sigma} over (rc,rs,YS)(r_c, r_s, Y_S).
  1. P\mathcal{P} verifies that certcert is valid and σ\mathcal{\sigma} is valid over (rc,rs,YS)(r_c, r_s, Y_S), then sends (rc,rs,YS,σ,cert)(r_c, r_s, Y_S,\mathcal{\sigma},cert) to V\mathcal{V}. Then V\mathcal{V} checks the same thing also.
  1. P\mathcal P and V\mathcal V jointly generate a private key:
    1. V\mathcal{V} generates a secret svs_v, calculates the verifier premaster key YV=svGY_V=s_v*G, and sends YVY_V to P\mathcal{P}.
    1. P\mathcal{P} generates a secret sps_p, calculates the prover premaster key YP=spGY_P=s_p*G, runs the key exchange procedure, and sends YP+YVY_P+Y_V to S\mathcal{S} after encrypting with YSY_S.
    1. P\mathcal P an V\mathcal V run ECtFECtF to compute a sharing of x-coordinate of YP+YVY_P+Y_V, denoted as zPz_P and zVz_V.
      Source: https://arxiv.org/abs/1909.00938
    1. P\mathcal P and V\mathcal V send zPz_P  and zVz_V to F2PChs\mathcal F_{2PC}^{hs} (see below figure) to compute (kEnc,rk,rm)(k^{Enc},r_k,r_m) and (rkkMAC,rmm)(r_k⊕k^{MAC},r_m⊕m), send to P\mathcal P and V\mathcal V respectively, which is (kEnc,kPMAC,mP)(k^{Enc},k^{MAC}_{\mathcal{P}},m_{\mathcal{P}}) and (kVMAC,mV)(k^{MAC}_{\mathcal{V}},m_{\mathcal{V}}).
      Source: https://arxiv.org/abs/1909.00938
    1. P\mathcal{P} computes a hash hh of the handshake messages, and runs a 2PC-PRF with V\mathcal{V} to compute sp=PRF(mPmV,s_p=PRF(m_{\mathcal{P}}⊕m_{\mathcal{V}},client finished”,h),h), sends to S\mathcal{S}.
    1. S\mathcal{S} computes ss=PRF(mPmV,s_s=PRF(m_{\mathcal{P}}⊕m_{\mathcal{V}},server finished”,h),h), sends it to P\mathcal{P}, then P\mathcal{P} and V\mathcal{V} recompute and check if ss=PRF(mPmV,s_s=PRF(m_{\mathcal{P}}⊕m_{\mathcal{V}},server finished”,h),h), and abort if not. Three-party handshake complete.

Note that at the end of the three-party handshake,

  • PP obtains kPMACk^{MAC}_{P} and kEnck^{Enc},
  • VV obtains kVMACk^{MAC}_{V}.

Query execution

  1. P\mathcal{P} constructs the query using the template Q=Query(θs)Q=Query(θ_s), θsθ_s is some secret parameter stored in P\mathcal{P}, e.g. API key, password, etc.
  1. P\mathcal{P} invokes 2PC-HMAC with V\mathcal{V} to compute a tag τ\mathcal{τ} which signs the query message QQ, sends (sid,Q^=Enc(kEnc,Qτ)(sid, \hat{Q}=Enc(k^{Enc},Q||τ) to S\mathcal{S}. (The goal of this step is to ensure that the content of the query is not been manipulated by P\mathcal P).

    The goal of 2PC-HMAC is to compute HMACH(kMAC,m)HMAC_H(k^{MAC},m), which is the following equation, where opadopad is 0101110001011100 repeated and ipadipad is 0011011000110110 repeated.

    HMACH(kMAC,m)=H((kMACopad)H((kMACipad)m))HMAC_H(k^{MAC},m)=H((k^{MAC}⊕opad)||H((k^{MAC}⊕ipad)||m))
    1. P\mathcal{P} and V\mathcal{V} input kPMACk^{MAC}_{\mathcal{P}} and kVMACk^{MAC}_{\mathcal{V}} to run a 2PC to compute s0=f(IV,kMACipad)s_0=f(IV,k^{MAC}⊕ipad), and reveal s0s_0 to P\mathcal{P}, where ff denotes a compression hash function of SHA256 and IVIV is an initialization vector. Note that s0s_0 is computed once in a TLS session.
    1. P\mathcal{P} computes the inner hash hi=f(s0,Q)h_i=f(s_0,Q), which represents H((kMACipad)Q)H((k^{MAC}⊕ipad)||Q) in the above equation.
    1. P\mathcal{P} inputs kPMACk^{MAC}_{\mathcal{P}}, hih_i and V\mathcal{V} inputs kVMACk^{MAC}_{\mathcal{V}} to run a 2PC to compute H((kMACopad)hi)H((k^{MAC}⊕opad)||h_i), which outputs ττ.

Commit and verify:

  1. P\mathcal{P} sends (sid,Q^=Enc(kEnc,Qτ)(sid, \hat{Q}=Enc(k^{Enc},Q||τ) to S\mathcal{S}.
  1. S\mathcal{S} responds to P\mathcal{P} with (sid,R^)(sid, \hat R),
    1. P\mathcal{P} sends (sid,R^,kPMAC)(sid, \hat R,k^{MAC}_{\mathcal P}) to V\mathcal{V}, (note that now V\mathcal{V} has the R^\hat{R}, so it cannot be altered)
    1. then V\mathcal V sends back (sid,kVMAC)(sid,k^{MAC}_{\mathcal V}).
  1. P\mathcal{P} computes kMAC=kPMAC+kVMACk^{MAC}=k^{MAC}_{\mathcal P}+k^{MAC}_{\mathcal V}, decrypts Rτ=Dec(kEnc,R^)R||τ=Dec(k^{Enc},\hat R), and verifies ττ with kMACk^{MAC}

Proof generation

  1. Define b=Stmt(R)b=Stmt(R) which is a statement about the response RR (e.g: “Alice has more than $3000 in the bank balance”), x=(kEnc,θs,Q,R)x=(k^{Enc},θ_s,Q,R), w=(Q^,R^,kMAC,b)w=(\hat Q, \hat R, k^{MAC},b), P\mathcal{P} sends (sid,prove",x,w)(sid,``prove",x,w) to ZKP function FZK\mathcal{F}_{ZK}.
  1. FZK\mathcal{F}_{ZK} constructs a relation π(x,w){0,1}π(x,w)∈\left\{ {0,1}\right\}, which is 11 if and only if:
    1. Q^\hat Q and R^\hat R are the ciphertexts of QQ and RτR||τ under kEnck^{Enc} and kMACk^{MAC}.
    1. Query(θs)=QQuery(θ_s)=Q
    1. Stmt(R)=bStmt(R) = b
  1. FZK\mathcal{F}_{ZK} sends (sid,"proof",π,(Q^,R^,k^MAC,b))(sid,"proof",π,(\hat Q, \hat R, \hat k^{MAC},b)) to V\mathcal V.
  1. V\mathcal V checks if k^MAC=kVMAC+kPMAC\hat k^{MAC}=k^{MAC}_\mathcal V+k^{MAC}_\mathcal P, and verifies the proof π\pi.

Assessment

DECO would allow a user to prove, in zero-knowledge, that some information comes from a specific TLS session with a specific server, and further that this information is taken from the right context. If such a tool were implemented, it would be of paramount importance for the transport of Web2 data to Web3. We label it as very relevant.

References