---
abstract: 'We present a cryptographic primitive called *WibsonTree* designed to preserve users' privacy by allowing them to demonstrate predicates on their personal attributes, without revealing the values of those attributes. We suppose that there are three types of agents —buyers, sellers and notaries— who interact in a decentralized privacy-preserving data marketplace () such as the Wibson marketplace. We introduce the *WibsonTree* protocol as an efficient cryptographic primitive that enables the exchange of private information while preserving the seller's privacy. Using our primitive, a data seller can efficiently prove that he/she belongs to the target audience of a buyer's data request, without revealing any additional information.'
author:
- |
    Ariel Futoransky\
    Disarmista Carlos Sarraute\
    Wibson & Grandata Ariel Waissbein\
    Disarmista Matias Travizano\
    Wibson Daniel Fernandez\
    Wibson
bibliography:
- '../wibson.bib'
title: 'WibsonTree: Efficiently Preserving Seller's Privacy in a Decentralized Data Marketplace'
---

Introduction
============

In this study, we are interested in the problem of trading real-world private information using only cryptographic protocols and a public blockchain to guarantee honest transactions. Private information in this context refers to attributes or events associated with a single individual (person or organization). In @Travizano2018Wibson the authors introduced the notion of a decentralized Privacy-Preserving Data Marketplace (). A decentralized Data Marketplace () is a Data Marketplace () with no central authority, no central data repository and no central funds repository. Additionally, a allows users to sell private information, while providing them privacy guarantees such as:

-   Participant anonymity: the identities of the Sellers and Buyers are not revealed without their consent. In particular, the identity of the Data Seller is not revealed to the Data Buyer, without the consent of the Data Seller.

-   Transparency over Data usage: the Data Seller always has visibility on how his Data is used by the Buyer.

Here we consider three types of agents interacting in a both privately (through end-to-end communications) and publicly through a permissionless blockchain:

Data Seller:

:   The Seller ${\ensuremath{\mathcal{S}}}$ is the owner and subject of the private information that will be traded. He decides when and if his data is sold.

Data Buyer:

:   The Buyer ${\ensuremath{\mathcal{B}}}$ is interested in acquiring information from Sellers, provided that the information meets the Buyer's quality requirements.

Notary:

:   The Notary ${\ensuremath{\mathcal{N}}}$ has the means to validate information associated with Sellers. He is trusted by Buyers to certify the precision and quality of the data traded. The Notary is the only public player with a formal track record and a public reputation.

The information traded is collected mainly outside of the blockchain. The Notary will typically access the data as part of its business operations with the Sellers. The Buyer understands the value associated with the privileged position of the Notary and knows about the incentives aligned with its reputation.

The design and price of information in data markets is an active field of study @admati1990direct [@bergemann2018markets; @bergemann2018design; @bergemann2015limits]. In the marketplace considered here, Data Sellers are able to participate in a decentralized marketplace that provides both financial incentives and control over their personal information @fernandez2020wibson. In addition, the Wibson platform provides a mechanism for the secure exchange of digital goods @futoransky2019secure and a gas efficient protocol named BatPay for the recurrent micropayment of tokens @batpay2020.

Problem Statement
=================

Precise Information Trading
---------------------------

We would like to construct a platform that allows the trading of personal data with very precise granularity. This means that the amount of information gained by a Data Buyer ${\ensuremath{\mathcal{B}}}$ in each transaction ${\ensuremath{\mathcal{T}}}$ can be properly constrained and narrowed.

In addition, the Data Seller ${\ensuremath{\mathcal{S}}}$ should not gain any information about other Sellers participating in other similar transactions. The Notary that certifies the Seller's Data should gain minimal information as well.

Under some circumstances, it is also required that the Seller should not learn about the Buyer's search criteria.

For example:

-   The Buyer should only learn if the Seller matches its search criteria, and nothing else.

-   If a Seller participates in different transactions with the same Buyer, it should not be able to distinguish if those operations belong to the same agent.

-   The Notary which certifies a Seller's personal information should not learn additional information about the Seller.

Zero Knowledge (ZK) proof systems have been proposed @bitansky2013succinct [@campanelli2017zero] which provide cryptographic tools for these issues. In particular, there are now practical universal solutions such as zk-SNARK and zk-STARK protocols for ZK proofs @ben2013snarks [@sasson2014zerocash; @costello2015geppetto; @ben2018scalable]. However, these ZK proof protocols are still too expensive in terms of computational and storage cost required to generate the proof and, to a lesser extent, to verify it. They are particularly expensive when the algorithms are run in mobile devices with restricted computing and storage capacities.

On the other side, MPC-based solutions like ZKBoo @jawurek2013zero [@giacomelli2016zkboo] are inexpensive in terms of computational cost but their communication requirements render them unacceptable for our application.

Problem Illustration
--------------------

Whenever a Data Buyer ${\ensuremath{\mathcal{B}}}$ specifies a search criterion that will be used to identify potential Sellers, each participant will need to prove that he is a match for the Data Request. But special care has to be taken in order to prevent additional information from leaking. We illustrate this problem with sample requests:

-   Buyer ${\ensuremath{\mathcal{B}}}$: Looking for people age 20-30

-   Seller ${\ensuremath{\mathcal{S}}}_1$: "I am 25"

-   Seller ${\ensuremath{\mathcal{S}}}_2$: "I am in the 20-30 range"

<!-- -->

-   Buyer ${\ensuremath{\mathcal{B}}}$: Looking for people who visited a.com, b.com or c.com

-   Seller ${\ensuremath{\mathcal{S}}}_1$: "I visited a.com"

-   Seller ${\ensuremath{\mathcal{S}}}_2$: "I visited one of those sites"

<!-- -->

-   Buyer ${\ensuremath{\mathcal{B}}}$: Looking for people living inside this particular area (polygon)

-   Seller ${\ensuremath{\mathcal{S}}}_1$: "I live at (latitude, longitude)"

-   Seller ${\ensuremath{\mathcal{S}}}_2$: "I live inside the polygon"

<!-- -->

-   Buyer ${\ensuremath{\mathcal{B}}}$: Looking for people with at least \$10k in the bank

-   Seller ${\ensuremath{\mathcal{S}}}_1$: "I have \$23k"

-   Seller ${\ensuremath{\mathcal{S}}}_2$: "I have at least \$10k"

In these examples, Seller ${\ensuremath{\mathcal{S}}}_1$ is revealing more information than needed, whereas Seller ${\ensuremath{\mathcal{S}}}_2$ is revealing just the right amount of information required in order to participate in the data transaction.

The protocol that we describe in the next sections will allow a Data Seller to respond to a Data Request without revealing any additional information.

A Naive Solution
----------------

A very simple solution can be constructed, wherein Data Buyers request the Notary for signed copies of the information they are looking for. On the other hand, the Data Sellers are consulted just to authorize the transactions.

This scenario has several problems:

-   Operations depend on the availability and scalability of the Notaries.

-   Notaries have excessive control over the marketplace, and can exercise arbitrary blocking on requests from selected Buyers.

-   Notaries would learn a lot about the Data Buyer's search criteria.

-   Notaries would gain a lot of additional information from other Notaries.

A better solution should have Notaries issuing certificates prior to the Buyer's requests. These certificates could be stored by Sellers and used whenever needed to complete orders generated by Buyers. The following protocols implement these ideas in the context of a .

Building Blocks
===============

Match Criterion as Function
---------------------------

The general idea is the following:

1.  The Notary ${\ensuremath{\mathcal{N}}}$ will issue a function $F_{\ensuremath{\mathcal{S}}}$ associated with each Seller ${\ensuremath{\mathcal{S}}}$. This function will take a description of a criterion as argument and return true or false depending on whether the Seller matches the criterion: $$F_{\ensuremath{\mathcal{S}}}(X) \in \{\mathsf{true}, \mathsf{false}\} .$$

2.  The Notary will sign the function: $$\mbox{Sign}_{Notary}(F_{\ensuremath{\mathcal{S}}}).$$

3.  The Buyer ${\ensuremath{\mathcal{B}}}$ specifies a criterion $X_0$.

4.  If the Seller matches the search criterion, he shows that $F_{\ensuremath{\mathcal{S}}}(X_0) = \mathsf{true}$, and that $F_{\ensuremath{\mathcal{S}}}(X_0)$ is a valuation of the same function $F_{\ensuremath{\mathcal{S}}}$ which was signed by the Notary.

5.  For any other $X \neq X_0$, the Buyer does not learn whether $F_{\ensuremath{\mathcal{S}}}(X)$ is true or false.

For example the following functions represent evaluations of different Buyer's criteria for a given Data Seller ${\ensuremath{\mathcal{S}}}$:

– $ \mathsf{ageInRange}_{{\ensuremath{\mathcal{S}}}}(\mbox{minAge}, \mbox{maxAge}) \rightarrow \{\mathsf{true}, \mathsf{false}\} $

:    \
    Returns true if the age of the seller ${\ensuremath{\mathcal{S}}}$ is within the specified minAge and maxAge.

– $ \mathsf{visitedAnySite}_{\ensuremath{\mathcal{S}}}(\mbox{siteList}) \rightarrow \{\mathsf{true}, \mathsf{false}\} $

:    \
    Returns true if the browsing history of the seller ${\ensuremath{\mathcal{S}}}$ contains any of the domains listed as a parameter.

– $ \mathsf{houseInPoly}_{\ensuremath{\mathcal{S}}}(\mbox{polygon}) \rightarrow \{\mathsf{true}, \mathsf{false}\} $

:    \
    Returns true if the home address of the seller ${\ensuremath{\mathcal{S}}}$ is within the specified polygon.

– $ \mathsf{bankBalanceAtLeast}_{\ensuremath{\mathcal{S}}}(\mbox{minBalance}) \rightarrow \{\mathsf{true}, \mathsf{false}\} $

:    \
    Returns true if the bank balance of the seller ${\ensuremath{\mathcal{S}}}$ is at least minBalance.

Ordered Binary Decision Diagrams
--------------------------------

We are going to represent the selected functions as binary decision diagrams (also known as branching programs).

An *Ordered Binary Decision Diagram* (OBDD) is a binary tree that represents a function. Its value can be obtained by traversing a particular path from root to leaf. The input argument is split into bits, where each bit in order is used node by node to decide whether to continue left or right. Finally, on the selected leaf, the output of the function is read.

In addition, the tree could be compressed by representing similar subtrees (different nodes on the same level that produce equivalent results for every input combination) as a single node. This transforms the tree into a *Direct Acyclic Graph* (DAG). But the semantic evaluation of the graph as a function is retained.

\[b\]<span>0.22</span>

\[b\]<span>0.44</span>

\[b\]<span>0.27</span>

This compression enables the representation of functions with larger input sizes. Not all functions can be efficiently expressed in this way, but we found a nice subset of interesting criterion predicates that work well, including:

-   Integer and fixed-point ranges.

-   Strings and Finite state automaton.

-   Matching with string-sets with wildcards.

-   Spatial coordinates, including approximation of convex polygons, and union of convex polygons.

-   Simple logical expressions.

Creating a WibsonTree
=====================

In this section we introduce the *WibsonTree* primitive, which enables the creation of cryptographic commitments for a function $F$, represented as an OBDD. Later, any single path can be opened and verified against the commitment without exposing additional information.

The data structure resembles a sparse Merkle-tree, which includes per-level blinding keys. We use $\mathsf{sha256}$ as the hash function in our implementations, but any other hash primitive can be used.

Given a function $F$ with inputs in ${{\ensuremath{\mathbb{Z}}}_2}^n$, we create $n$ pairs of random keys: $$\{ L_i,  R_i \} \mbox{ for } 0 \leq i < n.$$

A keyed crypto-secure Pseudo-Random Number Generator (PRNG) is used to derive these keys based on a single random seed.

We will then assign a hash $H_{node}$ to every node in the tree.

For every **leaf node** (output node), its hash is: $$H_{node} = {\mathsf{Hash}}( \mbox{Result}_{node}).$$

For any **non-leaf node** at level $i$, whose children hashes are $Child_L$ and $Child_R$, its hash can be calculated as: $$H_{node} = {\mathsf{Hash}}\left( {\mathsf{Hash}}(Child_L \, || \, L_i) \; || \; {\mathsf{Hash}}(Child_R \, || \, R_i) \right)$$

<span>![Assigning a hash to a non-leaf node while creating a WibsonTree.<span data-label="fig:wibsontree2"></span>](WibsonTree4 "fig:"){width="65.00000%"} </span>

In addition, an auxiliary value is calculated for each node: $${\mathsf{Aux}}_{node} = {\mathsf{Hash}}(Child_L \, || \, L_i) \oplus {\mathsf{Hash}}(Child_R \, || \, R_i)$$ The hash for the root node ($H_{root}$) represents the binding commitment for the tree and the associated function.

Opening a Commitment
--------------------

In general, we would like to open a commitment for a single point of the function, while hiding the rest. In the unusual case that the whole function needs to be revealed, the complete set of keys $ \{ L_i, R_i \}_{0 \leq i < n} $ can be shared.

The more usual and interesting case is when a single input $X$ has been specified. In this case, a witness can be created as follows:

First, for each bit $i$ in $X$, depending on the bit value $X_i$, $L_i$ or $R_i$ are revealed. That is, the binary representation of the input is used to alternatively select one of the two keys available for each level: $$\begin{aligned}
    \mbox{If } X_i &= 0  \mbox{:  reveal  } L_i \\
    \mbox{If } X_i &=1 \mbox{:  reveal  } R_i 
    \end{aligned}$$

In addition, for every node $j$ in the path implied by $X$, from root to every intermediate node except the result leaf node, ${\mathsf{Aux}}_j$ is revealed.

For the leaf node, the result is appended to the witness.

Verifying a Commitment
----------------------

To verify a commitment opening, we traverse the path backwards, from leaf to root, using keys and ${\mathsf{Aux}}$ information to reconstruct node hashes, until the root hash has been calculated. If the opening is correct, the root hash should match the original commitment's hash.

For a **leaf node**: $$H_{node} = {\mathsf{Hash}}(\mbox{Result}_{node})$$ For a **non-leaf node** at level $i$ with known child's hash $c$: $$\mbox{If } X_i = 0: H_{node} = {\mathsf{Hash}}(  {\mathsf{Hash}}( c \, || \, L_i ) \; || \; [ {\mathsf{Hash}}( c \, || \, L_i )  \oplus {\mathsf{Aux}}_{node} ] )$$ $$\mbox{If } X_i = 1: H_{node} = {\mathsf{Hash}}(  [ {\mathsf{Hash}}( c \, || \, R_i )  \oplus {\mathsf{Aux}}_{node} ] \; || \; {\mathsf{Hash}}( c \, || \, R_i ) )$$

WibsonTree Efficiency
---------------------

WibsonTrees are created out of Ordered Binary Decision Diagrams. With fixed L/R keys, the calculation of the root hash is not dependent on whether or how the tree has been compressed. An efficient representation of the tree as a DAG will result in an efficient calculation of the root hash. There are many powerful algorithms to produce optimized representations of a branching program.

In addition, the witness generated while opening a commitment is quite compact: 1 hash and 1 key per tree level minus 1. Note that the witness is not dependent on compression, so information about the redundancy of the function is not revealed.

Moreover, the only primitive required to create a Wibson tree is the hash function, which has much less computational cost and complexity than zk-SNARK @ben2013snarks.

Conclusion
==========

In this paper, we presented a cryptographic primitive called *WibsonTree* designed to preserve users' privacy by allowing them to demonstrate predicates on their personal attributes, without revealing the values of those attributes.

This primitive is presented in the context of a decentralized Privacy-preserving Data Marketplace () such as the Wibson marketplace @fernandez2020wibson. In a there are three types of agents: Data Buyers, Data Sellers and Notaries.

The *WibsonTree* protocol that we presented is an efficient cryptographic primitive that enables the exchange of private information while preserving the Data Seller's privacy by using proof-kits previously issued by the Notary. By using our primitive, a Data Seller can efficiently prove (with small computing requirements) that he/she belongs to the target audience of a Buyer's data request, without revealing any additional information.

{'source': 'arXiv_out/2002'}