https://blog.chain.link/deco-parsing-the-response/

Author: Siam Hussain

Contributors: Lorenz Breidenbach, Dahlia Malkhi, Alexandru Topliceanu, Xiao Wang, Chenkai Weng, Fan Zhang

In the previous post, we described how the authenticity of the TLS response is verified. In this post, we discuss how to efficiently and reliably parse the response and form claims about it while preserving the privacy of sensitive data within the response.

At the end of the last post, the prover and the verifier held commitment $[R]$ to the authenticated TLS response. The response $R$ is an array of bytes or a string. DECO then enables the prover to convince the verifier that some claim about $R$ is true without leaking sensitive information in $R$. For example, if $R$ is the following JSON document representing the financial report of the prover, she may claim that her bank balance is above $1,000,000 without revealing the exact balance.

{
    "balance": 2000000,
    "account_id": 156461324651,
}

Since the verifier does not see $R$ in plaintext, this creates a security challenge: how to prove that the value about which the claim is made is extracted from the correct context. To be specific, how could the verifier be sure  that the proof is about the “balance” field as opposed to “account_id”. This issue might seem trivial at first glance, since JSON can be parsed in unambiguously. However, the problem is that parsing JSON in ZKP would be prohibitively expensive.

In this post, we discuss efficient ways to parse the claim and prove the correctness of parsing. Specifically, we present a protocol  to extract commitments to particular fields from the commitment to a string. While we focus on JSON, one of the most widely used grammars in API responses, the concepts discussed here also apply to related grammars like XML or YAML.

Challenges in Parsing JSON in ZKP

While parsing a JSON in plaintext is pretty straightforward, it is extremely expensive in ZKP, where the structure of the JSON is hidden from the verifier. To explain this, let us start with a simpler example—the following if-else condition on a secret Boolean $b$.

if (b)
    y = f1(x)
else
   y = f2(x)

Since $b$ is a secret, the verifier does not know which branch to take. Therefore, both $f1()$ and $f2()$ need to be evaluated through the ZKP protocol, and then the value of $y$ is chosen with a multiplexer circuit.

More generally, in the above figure, we show a flow diagram of parsing a JSON document. Starting from the gray node, there are a number of possible branches from each node. Since the verifier does not have access to the JSON document in plaintext, he does not know which branch to take. Therefore, the parser needs to traverse every possible branch. This way, the total number of branches increases exponentially with each character in the string. As a result, a ZKP circuit to parse a JSON document would be too large to handle.

Selective Opening

In practice, however, the structure of the JSON rarely carries any sensitive information. Responses returned by web APIs have similar structures for different users, while the sensitive data items related to a specific user are (typically) the scalar JSON values. In DECO, the prover helps the verifier parse the JSON by partially opening the response to the verifier such that he learns the structure but not the scalars. This enables the verifier to parse the response locally without going through ZKP. At a high level,

• A claim is expressed with a JSON query $q$ in the form $mathcal{F}(eval(R, q))$ where $eval(R, q)$ denotes the result of applying the query $q$ on $R$ and $mathcal{F}$ is a function that returns either $texttt{true}$ or $texttt{false}$. 
• The prover computes (i) a redacted JSON response $R’$ that completely captures the structure of the JSON but has all the scalar values redacted and (ii) an array $Z$ of all the scalars from the JSON. She then sends $R’$ and commitment $[Z]$ to the array $Z$ to the verifier.
• Both parties locally compute an array of indices $J$ in $Z$ such that $Z[J] = eval(R, q)$. Since $R’$ captures the structure of the JSON, the verifier can use it to compute the index of any scalar in $Z$.Finally, they evaluate $mathcal{F}(Z[J])$ through ZKP on the commitment of the array $Z$.

We illustrate the process with the following toy JSON. The prover claims that the second element of the field $texttt{“age”}$ is greater than 18. Using the jq (a JSON query language) syntax, $q = texttt{“.age[1]”}$.

{
    "names": ["Jane", "Mike", "Susan"],
    "age": [30, 17, 22]
}

An honest prover sends the following redacted JSON $R’$ to the verifier.

{
    "names": ["", "", ""],
    "age": ["", "", ""]
}

And commits to the following array of scalars $Z$.

[
    ""Jane"", 
    ""Mike"", 
    ""Susan"",
    "30",
    "17",
    "22"
]

The prover and the verifier both locally compute the array of indices as $J = [4]$. Then they evaluate through ZKP the function $Z[J] > 18$ which returns $texttt{false}$ since $Z[[4]] = 17$ is smaller than 18.

Soundness Checks

Since the verifier relies on the prover to open the response, he also needs to ensure that the prover opened it properly. The verifier does this through a series of three checks as described below.

Check 1

First, the verifier checks if the committed values in the array indeed come from the response. For this, both parties locally compute an array of strings $P$ by splitting the redacted JSON $R’$ at the location of the scalars and removing the scalars themselves.

For the above example, $P$ is as follows.

[
    "{n    "names": [",
    ", ",
    ", ",
    "],n    "age": [",
    ", ",
    ", ",
    "]n}"
]

Recall that the parties already hold commitment $[R]$ to the authenticated response. They now use the commitments $[R]$ and $[Z]$ to evaluate the following reconstruction statement in ZK. $m$ here is the number of scalars, $|$ denotes bit-wise concatenation. 

$big[ R big] = ? big[ P[0] | Z[0] | P[1] | Z[1] | cdots | P[m-1] | Z[m-1] | P[m] big]$

The commitment scheme used in DECO commits to every bit in $R$ and $Z[i]; i = 0, cdots, m-1$ individually. This allows performing the concatenations ($|$) by simply concatenating the committed bits. The only ZKP operation in this step is the bit-by-bit comparison of the left- and right-hand sides. If the prover alters any value in $Z$, this equality check fails.

Check 2

Now the verifier checks if the redacted response $R’$ completely captures the structure of the response $R$. Before presenting how this check works, let us look at an example of how a dishonest prover may cheat by hiding parts of the structure. The dishonest prover may send the following redacted response and array of scalars to the verifier.

{
    "names": ["", ""],
    "age": ["", "", ""]
}

[
    ""Jane", "Mike"", 
    ""Susan"",
    "30",
    "17",
    "22"
]

Notice that the prover did not modify any value from $R$. Instead, she rearranged values between $R’$ and $Z$. Therefore, these $R’$ and $Z$ will still pass check 1 (you can verify this by computing $P$ for this new $R’$ and interleaving it with the new $Z$). However, $Z[[4]]$ is now 22, which is greater than 18 resulting in the ZKP evaluation to return $texttt{true}$. 

To ensure that $R’$ completely captures the structure of $R$, the verifier needs to ensure that the prover is not hiding any of the structure in $Z$. He achieves this by parsing every element in $Z$ as a scalar through ZKP. JSON supports four types of scalars: number, Boolean, string, and null. If for any element of $[Z]$ parsing as a scalar fails, the verifier rejects the claim. In the above example, parsing the first element of the $Z$ as a scalar will fail. Note that parsing as a scalar does not have the branching issue discussed earlier since the presence of any branch results in an invalid scalar.

Check 3

The final check ensures that $R’$ has all the scalar values redacted. Similar to the previous one, we present an example of how the prover can cheat in the absence of this check. The dishonest prover may send the following redacted response and array of scalars to the verifier.

{
    "names": ["Jane", "", ""],
    "age": ["", "", ""]
}

[
    ""Mike"", 
    ""Susan"",
    "30",
    "17",
    "22"
]

Here the prover reveals one of the scalars to again reduce the length of the array $Z$ so that $Z[[4]]$ becomes 22 instead of 17. Note that this would result in incorrect values of the array $P$ in check 1, resulting in that check failing. However, the verifier can catch this even before starting the ZKP protocol. He computes $R’_v$ by redacting the scalars from $R’$. If the prover indeed redacts all scalars in $R’$, $R’$, and $R’_v$ will be identical. If not, they will be different and the verifier rejects the claim even before starting the ZKP evaluations. 

In summary, prover sends a redacted JSON response $R’$ and commitment $[Z]$ to the array of all scalars $Z$ to the verifier such that $R’$ completely captures the structure of the original response $R$. The verifier then verifies the following:

1. Replacing all the redacted values in $R’$ with the corresponding values from $Z$ results in the already authenticated response $R$.
2. Prover did not hide anything other than the scalars in $R’$.
3. Prover did not leave any unredacted scalar in $R’$. 

Check 1 ensures the authenticity of the committed scalars. Check 2 and 3 ensure that $R’$ completely captures the structure of $R$, which in turn ensures correct evaluation of JSON queries. 

This is the third post in a series of DECO research blogs from the Chainlink Labs Research Team. Check out the other posts in the series:

• DECO Research Series #1: An Introduction
• DECO Research Series #2: Provenance and Authenticity

The post DECO Research Series #3: Parsing the Response appeared first on Chainlink Blog.

https://blog.chain.link/optimal-latency-and-communication-smr-view-synchronization/

Authors: Andrew Lewis-Pye (London School of Economics), Dahlia Malkhi (Chainlink Labs), Oded Naor (Technion and Starkware)

A previous post described the Byzantine View Synchronization (“BVS”) problem and why it turned into a bottleneck of leader-based consensus protocols for the partial synchrony setting. That post tackled single-shot consensus, and presented an evolution of BVS solutions (“Pacemakers”) that finally brought BVS communication down to $O(n^2)$ messages—the optimal, according to a known lower bound—in the worst case. 

In this post, we expand the discussion to multi-shot consensus protocols, also known as State-Machine-Replication (SMR). 

Briefly, in the BVS problem, a group of processes enter/leave views until they reach a view (“Synchronized View”) with an honest leader and spend sufficient time in overlap in the view for the leader to drive a consensus decision. The multi-shot setting, that is, SMR, requires solving BVS infinitely many times.

Existing BVS protocols (some of which were described in the previous post), exhibit an undesirable tradeoff in the multi-shot setting: Each time a Byzantine leader is encountered following a succession of honest leaders, protocols either incur a high communication overhead (quadratic), or a high expected latency (linear). 

This post surfaces this problem and presents a new protocol, Lumiere, that quickly recovers (namely, within a constant latency) in case of a Byzantine leader, while retaining optimal communication and latency both in expectation and in the worst case.

Preliminaries

Recall that $n$ is the number of nodes, and that we assume $ngeq 3f+1$, where $f$ is a bound on the number of Byzantine nodes. 

A view $v$ is considered Coordinated when all honest nodes are in the same view for a sufficiently long time $Gamma$ (dictated by the underlying SMR protocol). This is usually achieved when the honest nodes enter view $v$ within some known time bound—typically two network delays—from one another.

A Coordinated View is Synchronized if it has an honest leader. A Pacemaker is a protocol used by the underlying SMR protocol to reach an infinite number of Synchronized Views.

Some Pacemakers (e.g., the Pacemaker solution by Lewis-Pye) incorporate specific view consensus protocols, but generally, the in-view consensus protocol is opaque while always requiring participation by $2f+1$ nodes. For example, in HotStuff, the view protocol consists of all nodes sending votes to the leader, the leader collecting $2f+1$ votes and forming a quorum-certificate (“QC”) which is a threshold aggregate of votes. It then sends the QC back to the nodes. A QC for view $r$ proves that a decision was reached in the consensus protocol in that view. 

It will also be useful to introduce into the discussion two additional parameters: $Delta$ is a parameter known to the protocol and denoted the estimated network delay after GST. The actual network delay is denoted by $delta$. It is assumed that, after GST, $delta leq Delta$. $Gamma$ is the presumed interval needed to reach a decision in single consensus instance within a Synchronized View.  We will assume $Gamma = O(Delta)$.  

The Pacemaker due to Lewis-Pye (2022)

In this section, we describe the Pacemaker protocol by Lewis-Pye (“LP-22”). This Pacemaker achieves optimal worst-case complexity and latency, and is also responsive¹. That is, if there is a sequence of honest leaders once a Synchronized View is reached, then decisions are made at network speed $delta$ until the first occurrence of a Byzantine leader.

The high-level pseudocode of LP-22 is the following. Each sequence of $f+1$ consecutive views $e, dots, e+f$, where $e bmod (f+1)=0$, is called an epoch. If $r=0 bmod (f+1)$, then view $r$ is called an “epoch-view”.

• At any point, if a node is in view $r$ and receives a threshold signature View Certificate (VC) for an epoch-view $r’>r$, then it sends that VC to all nodes and enters view $r’$.
• If a node wishes to enter view $r$, where $r bmod (f+1) = 0$, it performs an “epoch-view” procedure for view $r$:
  • Send (WISH,r) to $f+1$ view leaders in the epoch. 
  • A leader collects $2f+1$ (WISH,r) messages, forms a View Certificate (VC) for view $r$, and sends this to all nodes.
• If a node wishes to enter view $r$, for $r bmod (f+1) neq 0$ (a non epoch-view), it enters.
• A node wishes to enter view $r$ if either:
  • Its view $r-1$ timer expires.
  • The node receives a certified decision (QC) by the leader of view $r-1$.
• If a node enters view $r$ such that $r bmod (f+1) = 0$ at time $s$ (say), it sets a view $r+k$ timer to expire at time $s + (k+1)*Gamma$, for each $k=0, dots ,f$.

LP-22 achieves responsiveness by adding the condition to advance views inside an epoch when receiving a certified decision. By adding this simple condition, a succession of honest leaders in a single epoch can drive progress and make new decisions at network speed. If the actual network speed is faster than the timeout period, then this Pacemaker dramatically improves the actual latency compared to RareSync in runs with no faulty leaders.

Note, though, that if the $k$-th view of an epoch has a faulty leader, then nodes must wait for the predetermined $(k+1) cdot Gamma$ timeout to advance to the next view (see depicted below). This means that even a single Byzantine leader can cause significant delays, especially in views toward the end of the epoch. We will get to this next.

¹A related work named RareSync has an identical approach to LP-22 at a high-level, but employs Bracha-style all-to-all broadcast, rather than using $f+1$ leaders as relays. It also doesn’t have responsiveness.

Lumiere

In a previous post, we saw earlier Pacemaker protocols (like Cogsworth, NK-20, FastSync) that actively synchronize views on a need-only basis, each time a bad leader is encountered. Each synchronization event has only $O(Delta)$ latency, but it might incur quadratic communication cost; hence, the overall worst-case communication cost is $O(n^3)$. 

On the other hand, as we saw above, LP-22/RareSync synchronize views upfront, on an epoch basis, which is not latency-optimal. However, their worst-case communication complexity is optimal (quadratic).  

This seeming tradeoff leaves open the following natural question:

Does a responsive Pacemaker protocol exist that has optimal worst-case communication complexity (quadratic), and allows nodes to progress after a bad leader within $O(Delta)$ latency?

Lumiere answers this question affirmatively. It combines methods from both Cogsworth/NK-20 and LP-22/RareSync; and borrows a technique of advancing clocks forward to provide responsiveness from Fever, which solves view synchronization in a different model, namely, where nodes are synchronized via real-time clocks.

Overview of Lumiere:

In Lumiere, nodes synchronize at the start of each epoch and set view timers $k dot Gamma$ for $k= 1, dots , f+1$ (same as LP-22). 

By default, nodes wish to enter a view (say $r+1$) within an epoch upon expiration of these timers. However, nodes may wish to enter view $r+1$ early upon obtaining a QC in view $r$.

Whenever nodes wish to enter a view $r+1$ within an epoch (potentially early), they re-synchronize entering view $r+1$ via the (linear) procedure below.

To enter view $r+1$, a node performs two actions: 

1. The node sends a view message to the next leader. When a leader collects $f+1$ view messages, it forms a View Vertificate and sends it to all nodes. Upon receiving a VC for any view higher than its current, a node enters the view. 
2. Whenever a node obtains a VC, the node adjusts its future view timers to start now. For example, say that $Gamma/2$ elapsed since the node advanced to view $r$ until it obtained a VC for view $r+1$; see depicted below. Then the node sets the timer for view $r+1$ to expire $3Gamma/2$ after view $r$ was entered, instead of after $2Gamma$ as originally. (If the node obtains a VC for $r + 2$ earlier, it may again adjust its timers and advance to $r+2$ responsively as well, and so on.) 

The figure below depicts the Lumiere protocol. When the epoch begins, there’s an all-to-all synchronization after which each view lasts $Gamma$. Now suppose a QC is received in the first view (orange line).

After the QC and the next VC are received, the timeouts of the succeeding views are adjusted (orange lines).

Pseudocode of Lumiere:

A node in view $r-1$ performs the following actions:

• If the node wishes to enter view $r$, where $r mod (f+1) = 0$, it performs an “epoch-view” procedure for view $r$, as in LP-22/RareSync. As before, VCs for epoch-views require $2f+1$ VIEW messages.
• If a node wishes to enter view r, for $r mod (f+1) neq 0$ (a non-epoch-view):
  • send (VIEW,r) to the leader of $r$
  • a leader that receives $f+1$ VIEW messages for view $r$ forms a threshold signature View Certificate (“VC”) and broadcasts it to all nodes
• A node advances to view $r$, where $r$ is higher than the view the node is currently in, if it sees a VC for view $r$. In this case, suppose the current time is $s$ and proceed as follows. For each view $r’geq r$ in the same epoch, set the timer for view $r’$ to expire at time $s+(r’-r+1)Gamma$. 
• A node wishes to advance to view $r+1$ in the following two cases:
  • The timer for view $r$ expires.  
  • If it obtains a QC for view $r$.

Correctness sketch:

The key insight is that if a view $r$ generates a QC, at least $f + 1$ correct nodes must have entered view $r$ to facilitate progress. Hence, when the first correct node $P$ advances to an early re-synchronization from view $r$ to view $r+1$, there are at least $f$ nodes who will try to enter views $r+1$, $r+2, …, each within a $Gamma$ gap behind $P$. 

Consider the first two consecutive correct leaders, $r’, r’’$, following $r$. There are two cases:

1. If any correct node $P$ expires $r’$ and sends a view message for $r’’$ before the leader of $r’$ sends a VC, $f$ bad nodes can send view messages and enable $P$ to enter $r’’$. However, since the leader of $r’’$ is correct, all nodes enter $r’’$ within $Delta$ of its leader sending a VC. 
2. Otherwise, all correct nodes overlap in $r’$ sufficiently long to form a QC in $r’$.   

Optimistic Asynchronous Atomic Broadcast 

It is worthy of mentioning a different approach for tackling view-change, which was introduced in two recent advances, Ditto-21, BoltDumbo-21. These protocols are not per se partially synchronous; they actually revisit optimistic asynchronous atomic broadcast, an approach which was pioneered in KS-02, RC-05, and generalized in 700bft-10. The idea is to have an optimistic partially synchronous regime achieving optimistically optimal work (linear), and use a quadratic asynchronous protocol as a fallback mechanism during asynchronous periods. 

Since there is no view-change in these solutions, and the fallback regime is fully asynchronous, there is no required view-synchronization per se. This works as follows. 

When a view fails to make progress for $Gamma$, instead of replacing the leader and proceeding with the next leader, nodes fall back to a full-fledged asynchronous consensus protocol. Internally, the quadratic asynchronous regime borrows from VABA. More specifically, it invokes $n$ simultaneous HotStuff consensus instances, one per node acting as candidate leader. After $n-f$ instances complete, it elects in retrospect one node as leader unpredictably and uniformly at random. If the leader is honest, the protocol will have reached a decision by this leader; otherwise, the protocol invokes another wave of $n$ HotStuff instances, each of which orchestrates a view-change from the elected leader. 

Running $n$ simultaneous views, electing a random leader, and orchestrating $n$ view-changes from it to the next instance, incur only a total quadratic cost (relying on the HotStuff linear in-view/view-change regimes). Note, however, that each time a Byzantine leader is elected within the asynchronous consensus protocol the complexity is quadratic, and a fortiori, an unlucky series of $f$ leader failures leads to a worst-case $O(n^3)$ complexity.

Performance of Various Pacemakers

The table below compares the latency and message complexity achieved by state-of-the-art protocols for reaching $n$ consensus decisions after the first synchronization. We consider $n$ consensus decisions, rather than single-shot, because the single-shot figures can often hide what happens in the aggregate. For example, Lumiere has optimal (worst-case) $O(n^2)$ message complexity for reaching a single consensus decision, but also has $O(n^2)$ complexity for reaching $n$ decisions. We consider what happens after first synchronization because the latency and complexity required for the first synchronization are sometimes special cases–the measures shown below aim at presenting what is important in contexts where one must deal with occasional periods of asynchrony but long periods of synchrony are the norm.  

Defining the measures. Intuitively, we are interested in the communication cost and latency incurred in a succession of views reaching $n$ consensus decisions, measured after GST and starting with a synchronized view. In order to provide an apples-to-apples comparison of protocols, we present explicit formulae, parametrized by a random variable $f_m$ denoting the actual number of views with faulty leaders in the succession.

More formally, let $t^{ast}$ be the first synchronization time after GST, i.e. the first time $t^{ast}$ after GST such that all honest players are in the same view with honest leader from time $t^{ast}$ until that view produces a QC. Let $t$ be any time after $t^{ast}$. Let $v$ be the greatest view any honest player is in at $t$. Define $v’$ to be the least view $>v$ such that $n$ views in the interval $[v,v’]$ produce QCs (by some least time $t’$, say), and define $f_m$ to be the number of views in $[v,v’]$ that have faulty leaders. Latency is $t’-t$. Message complexity is the number of messages sent by honest players during  $[t,t’]$. This includes messages sent while carrying out both the View Synchronization protocol and the underlying protocol. Note that $v’$ could potentially be infinite (depending on the protocol), in which case we define $t’=infty$. 

View timer: It is assumed that each protocol has a per-view timer $Gamma$ to expire a view, satisfying $O(Gamma) = O(Delta)$.

Full consensus protocol: When it comes to “pure” View Synchronization methods, e.g., Cogsworth or NK-20, we assume HotStuff is used as the core consensus mechanism.

Insights: Cells marked with a green sparkle () indicate improvement relative to higher rows; a warning sign () indicates trading off some desirable property relative to it. Briefly, the figures shown underscore an evolution as follows:

• The first row considers Cogsworth, which is optimistically communication and latency optimal against benign failures, but each Byzantine leader may inflict $O(n^2)$ communication overhead, hence the worst case is $O(n^3)$. 
• The second row considers NK-20, which improves the expected communication cost inflicted by $f_m$ Byzantine leaders to $(f_m cdot n)$, but a succession of $f_m$ bad leaders can cause $O(n cdot f_m^2)$ communication overhead, and the worst case remains $O(n^3)$.
• The third and fourth rows consider several protocols that employ a quadratic View Synchronization sub-protocol on a need-only basis each time progress is stalled. They are latency optimal: in fail-free executions, they incur $O(n cdot delta)$ latency, and in executions that encounter $f_m$ bad leaders, they incur an extra $O(f_m cdot Delta)$ delay (the optimal).
  However, the downside is that they incur a quadratic communication cost in synchronization overhead each time a bad leader is encountered, i.e., a total of $O(f_m cdot n^2)$ synchronization overhead. The worst-case communication remains $O(n^3)$.
• The fifth row of the table includes the LP-22 and RareSync protocols, which invest a quadratic communication cost upfront, achieving worst-case communication optimality ($O(n^2)$).
  However, waiting for pre-synchronized times has an expected $O(n cdot Delta)$ delay when bad leaders are encountered. Hence, except in fail-free executions, they incur a higher expected latency than previous protocols.
• The sixth row of the table presents a recent protocol named Fever, which retains the good properties of previous protocols but removes the expected $O(n cdot Delta)$ delay of the fifth row. Fever introduces a new requirement, namely that all nodes start the execution at the same time. Because of this assumption, Fever does not rely on epoch synchronizations and does not fall out of sync during periods of asynchrony, a desirable property that is not exhibited in the table below.   
• The seventh row of the table presents the performance measures of the Lumiere protocol. Lumiere keeps the expected $O(Delta)$ latency of Fever without relying on a synchronous start, commencing at the first epoch after communication has stabilized (as defined above), while retaining communication optimality.

The post Optimal Latency and Communication SMR View-Synchronization appeared first on Chainlink Blog.

Pacemaker	Latency	Communication	Live Against Asynchrony	Initial Clock Sync
Cogsworth-19	Expected: $(f_m cdot Delta + n cdot delta)$ Worst case:  $O(f_m^2 cdot Delta + n cdot delta)$	Expected (against benign failures): $O(f_m cdot n + n^2)$ Worst-case (against active Byzantine attack): $O(f_mcdot n^2 + n^2)$	no	Not required
Naor-Keidar-20	same as above	Expected: $O(f_mcdot n+ n^2)$ Worst case: $O(n cdot f_m^2 +n^2)$	same	same
FastSync-20 /  DiemBFT-v4-21 / R-20 / FastHS-20 / Jolteon-21	$(f_m cdot Delta + n cdot delta)$	$O(f_mcdot n^2 + n^2)$	same	same
Ditto-21 / BoltDumbo-21	same as above	same as above	yes	same
RareSync-22 / Lewis-Pye-22	$O(n cdot Delta)$ if $f_m > 0$  $O(n cdot delta$) otherwise	$O(n^2)$	no	same
Fever-23	$(f_m  cdot Delta + n cdot delta)$	same as above	same	Required
Lumiere	same as above	same as above	same	Not required

https://blog.chain.link/deco-provenance-and-authenticity/

Author: Siam Hussain

Contributors: Lorenz Breidenbach, Dahlia Malkhi, Alexandru Topliceanu, Xiao Wang, Chenkai Weng, Fan Zhang

In this post, we describe how the prover convinces the verifier that a TLS response is obtained from a particular server. 

DECO involves three parties: the prover (Alice, “she”), the verifier (Bob, “he”), and the TLS server (Charlie, “it”). In TLS, authentication of the server relies on secret challenges generated by the client (prover in DECO) for every new session. This makes TLS an interactive protocol. Therefore, the verifier needs to be a part of the protocol execution to be able to verify the authenticity of data. He achieves this by working as a proxy between the prover and the server and recording the bytes communicated as part of the TLS protocol. These bytes are later used as the “truth” known by both prover and verifier in the proofs of authenticity. Note that TLS ensures the privacy of data from any eavesdropper, in this case the verifier.

The server is oblivious to its participation in the DECO protocol. This requires the TLS protocol to be executed without any modification, and DECO thus follows steps in the TLS protocol precisely. First, the TLS session keys are generated by the prover. Then the keys are used to decrypt the TLS ciphertext.

TLS Key Agreement and Key Binding Proofs

At the beginning of the TLS protocol, the prover and server generate a TLS session key $K$ using a key exchange protocol, e.g., Diffie–Hellman. The verifier does not learn $K$ (otherwise TLS wouldn’t be secure). However, this creates a security problem — what if the prover later uses a bogus key $K’$ in the subsequent ZKP proofs? This is possible because encryption algorithms in modern TLS are not committing, which means that a ciphertext can be decrypted in multiple ways. This may allow the prover to decrypt the ciphertext to something the server has never sent, causing a soundness violation. The solution in DECO is to ask the prover to show a key binding proof to prove that the commitment $[K]$ to the session key is generated correctly.

The goal of a key binding proof is for the prover to convince the verifier that a session key $K$ is uniquely bound to the session recorded by the verifier. To understand how key binding proofs work, we first need to cover how TLS session keys are generated.

We use a simplified version of TLS 1.3 inspired by [GZBW22] to illustrate the key ideas. (For clarity, we omit certificate verification and we use $K$ to denote multiple keys.) First, the prover and server generate a shared secret (hidden from the verifier) $S$. Then they locally compute the key $K$ based on $S$. In the following protocol, HMAC is a Hash-Based Message Authentication Code, HKDF is HMAC Key Derivation Function, and HASH is, well, a hash function. 

1. Prover and server agree on a generator $g$ and a modulus $p$. 
2. Prover chooses a secret random value $a$ and sends $A = g^a; texttt{mod}; p$ to the server.
3. Server chooses a secret random value $b$ and sends $B = g^b; texttt{mod}; p$ to the server.
4. Prover locally computes $S = B^a = {g^b}^a = g^{ab}; texttt{mod}; p$.
5. Server locally computes $S = A^b = {g^a}^b = g^{ab}; texttt{mod}; p$.
6. $K_1 = texttt{HKDF}(S, 1)$
7. $H_1 = texttt{HASH}(A | B)$
8. $SF = texttt{HMAC}(K_1, H_1)$
9. $H_2 = texttt{HASH}(H_1 | SF)$
10. $K = texttt{HKDF}(S, H_2)$

Among the intermediate values, the server only sends $SF$ to the prover. The prover verifies that the received value of $SF$ matches with the locally computed value. 

The verifier observes and records $A$, $B$, and $SF$ and also knows $g$ and $p$. He cannot compute $K$ since he does not know the secrets $a$ and $b$. A straightforward way to verify the correctness of $[K]$ is the prover committing to the secret $a$ as the private input in ZKP. Then, using the values known to both prover and verifier, they can compute $[K]$ through the ZKP protocol. This approach, while secure, would be expensive since the circuit for public key operations (modular exponentiations to compute $A$ and $S$) includes a large number of AND gates.

[GZBW22] optimizes this circuit by using the collision-resistance property of hash functions. In the optimized version, instead of committing to $a$, the prover commits to $S$ and the ZKP circuit incorporates steps 6 to 10. Since the verifier already records $SF$ as proxy, the prover opens $[SF]$ after step 8 and the verifier matches it with the recorded value. The collision resistance property of hash functions ensures that the prover cannot come up with a fraudulent value of $S neq g^{ab}; texttt{mod}; p$ that will result in the same value of $SF$. With this optimization, we avoid executing public-key operations inside the ZKP protocol and are only left with HMAC and HKDF. The most compute-intensive parts of HMAC and HKDF are multiple hash function evaluations (e.g., SHA-256). The hash function’s circuit is quite large, but can be evaluated in reasonable time thanks to recent progress in interactive ZKP.

Note that a TLS session involves multiple keys, and the number of keys depends on the TLS version. TLS 1.3 has four keys: two in each direction for handshake and appdata. $K$ in step 10 above is the appdata key in the direction of the server to the prover. Steps 6 to 10 are repeated in the other direction. In the following section and the next few posts, we focus on server to prover appdata which is the TLS response. At the end of this series, we discuss the prover to server appdata which is the TLS request. DECO also validates the handshake keys in both directions.

Description of the TLS Transcript

After key agreement, prover and verifier hold commitment $[K]$ to the TLS session key $K$ and the encrypted TLS response $C$ sent by the server. Prover receives $C$ as the TLS client and verifier records it while acting as the proxy. $C$ is used as the truth known to both the prover and the verifier in the proof of authenticity. 

The prover and the verifier first compute a commitment $[R]$ to the TLS response $R$. For this, they need to execute the decryption circuit $R = decrypt(K, C)$ through the ZKP protocol with $[K]$ and $C$ as inputs. TLS supports a number of different cipher suites and the details of $decrypt()$ varies based on the cipher suite chosen for the session. At a high level, $decrypt()$ involves repeated calls to a symmetric cipher (e.g., AES-GCM-128) based on the length of the response. In one of the proof-of-concept applications of DECO with Teller, to decrypt the response (financial report of the prover in this case), around 1700 invocation of AES-128 are required. The AES-128 circuit to decrypt one block (128 bits) consists of 6400 AND gates, which means computing $[R]$ requires computing commitments to more than 10 million AND gate outputs. The memory required to store this many commitments would be prohibitively large. Fortunately, thanks to the ability to forget in commit-and-prove ZKP, we only need enough memory to hold the commitments of a single AES-128 circuit: less than 1GB. More importantly, the memory requirement is independent of the number of invocations of the AES-128 circuit and is thus independent of the size of the TLS response. 

At this stage, prover and verifier hold a commitment $[R]$ to the TLS response. Verifier is convinced that the response is authentic since it is decrypted from the encrypted TLS response $C$ that he recorded as a proxy with the committed key $[K]$ that he verified to be computed properly. In the next post, we will describe parsing the already-authenticated response.

References

[GZBW22] Paul Grubbs, Arasu Arun, Ye Zhang, Joseph Bonneau, and Michael Walfish. “Zero-Knowledge Middleboxes”. In USENIX Security Symposium 2022.

The post DECO Research Series #2: Provenance and Authenticity appeared first on Chainlink Blog.

https://blog.chain.link/deco-introduction/

Author: Siam Hussain

Contributors: Lorenz Breidenbach, Dahlia Malkhi, Alexandru Topliceanu, Xiao Wang, Chenkai Weng, Fan Zhang

DECO enables a user to prove the authenticity of data and claims about it without revealing the data itself. Authenticity, in this context, means that the data is obtained from a specific web server through the TLS protocol. For example, a user can prove that she obtained her financial report from her bank’s website and that, according to this report, her account balance is above a particular amount. However, she does not reveal any other information present in the report, such as her account number or exact balance. 

DECO requires no server side cooperation. The TLS server does not have to be modified or even be aware that it is participating in the DECO protocol, greatly simplifying DECO’s path to adoption. 

With this post, we begin a mini-series of articles describing the challenges in the progress of DECO from an academic publication [ZMMG+20] to a product, how it makes use of an interactive zero-knowledge core, and some of the optimizations aiding its real-life deployment. If you are interested in the motivation behind DECO and its various use cases, this talk is a good place to start. In this introductory post, we provide a brief overview of DECO and one of its key ingredients: zero-knowledge proofs (ZKPs). 

A (Very) Brief Overview of Interactive Zero-Knowledge Proofs (ZKPs)

DECO harnesses the magic of ZKPs to ensure privacy. In TLS, the identity of the server is verified using fresh challenges generated by the client for every session. This makes TLS, and in turn DECO, interactive protocols. Therefore, we use an interactive “commit-and-prove” form of ZKP called VOLE-based ZKP in order to benefit from its higher speed, lower memory footprint, and scalability compared to non-interactive ZKP. We provide a brief overview of the protocol here. Please see our blog series on interactive ZKPs for details. 

Commitments are a cryptographic concept that can be viewed as a locked box. The prover *committing* to a variable $x$ is analogous to putting $x$ in a locked box and sending it to the verifier. The verifier cannot view the committed value but has the guarantee that the prover cannot change it once sent. Later, the prover can send the key to the verifier to *open* the commitment. We denote the commitment to $x$ with $[x]$. 

Given commitments to the inputs of a logic gate (AND/XOR), a commit-and-prove ZKP protocol enables the prover and verifier to compute the commitment to the output. This in turn enables the prover to prove the correct computation of a circuit consisting of these gates through the following steps: 

(i) The prover commits to the inputs of the circuit.

(ii) Together the prover and the verifier compute the commitments to the outputs of the gates going through them in topological order.

(iii) The prover opens the commitments to the outputs of the circuit. 

The commitment scheme used in the DECO ZKP core is additively homomorphic. This means that the commitment to the output of an XOR gate (addition modulo 2) can be computed locally without incurring any communication or computation cost. The cost of evaluating a circuit through the ZKP protocol is thus linear in the number of AND gates. 

Upcoming Posts

Over the next few weeks we will publish a series of blogs under the tag discussing the details of different steps of the DECO protocol. Here is a sneak peek into the upcoming posts: 

• Proving the authenticity of data: In the first step of the DECO protocol, the prover convinces the verifier that a TLS response is obtained from a particular server. This procedure closely follows the steps in the TLS protocol. First, prover and server generate a set of symmetric keys to encrypt the TLS request and response. Then the prover decrypts the ciphertext received from the server to obtain the response. The verifier does not see either the key or the response. However, he actively participates in the protocol to ensure that the prover correctly computes the key, the response, and the ZKP commitments to them. In this post, we describe how the verifier participates in the TLS protocol and verifies the authenticity of the response. 
• Parsing the response: After the verifier is convinced of the authenticity of the response, the next step is to parse the response to retrieve relevant information. The primary challenge in this step is verifying the correctness of parsing without accessing sensitive information in the response. 
• Hiding the length of the sensitive data: The ZKP protocol employed in DECO, and a majority of ZKP protocols in general, hide the values of the private data but not their different lengths. In this post, we describe how DECO enables hiding the lengths of individual secrets within the TLS interaction. 
• Formation of claims: In this post, we discuss how the claims are formed in an unambiguous way. We also discuss how the verifier ensures that the prover commits to the correct secret inputs from the response to these claims without learning their values. 
• Proofs over multiple responses: For some use cases of DECO, the claims involve information retrieved from multiple responses, possibly over multiple TLS sessions (and from multiple sources). In this post, we describe how DECO combines such responses into one coherent proof. 

References

[ZMMG+20] Fan Zhang, Deepak Maram, Harjasleen Malvai, Steven Goldfeder, and Ari Juels. “DECO: Liberating Web Data Using Decentralized Oracles for TLS.” In ACM Computer and Communications Security 2020.

The post DECO Research Series #1: Introduction appeared first on Chainlink Blog.