[bitcoindev] Shielded CSV: Private and Efficient Client-Side Validation

[bitcoindev] Shielded CSV: Private and Efficient Client-Side Validation

[Jonas Nick]

Hello list,

We (Liam Eagen, Robin Linus, and I) are pleased to announce the release of the
Shielded CSV whitepaper, which describes a private and efficient client-side
validation (CSV) protocol. Shielded CSV builds upon previous work proposed on
this mailing list, including contributions by Peter Todd [0], RGB [1], Taproot
Assets [2], and zkCoins [3].

The whitepaper is available here:
https://github.com/ShieldedCSV/ShieldedCSV/releases/latest/download/shieldedcsv.pdf

Our work differs from previous approaches in two main aspects:
1. Shielded CSV is defined using the "Proof-Carrying Data" abstraction, which
    can be instantiated via recursive zkSNARKs or folding schemes. This provides
    "full" privacy (hiding of the transaction graph) and ensures that coin proofs
    and verification time are independent of the transaction graph.
2. Instead of using Bitcoin transactions for CSV-payments, a Shielded CSV
    payment only requires posting 64 bytes of data to the blockchain (regardless
    of the CSV-transaction size) and a small constant overhead, significantly
    reducing on-chain cost.

The Shielded CSV protocol is currently defined using Rust-based pseudocode. We
believe that Shielded CSV is both a promising candidate for implementation and
provides an extensible framework for further innovation in the CSV space. We
welcome feedback and look forward to discussing and expanding upon this work.

[0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-November/003714.html
[1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/021554.html
[2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020196.html
[3] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-May/021679.html


# Abstract

Cryptocurrencies allow mutually distrusting users to transact monetary value
over the internet without relying on a trusted third party.

Bitcoin, the first cryptocurrency, achieved this through a novel protocol used
to establish consensus about an ordered transaction history. This requires every
transaction to be broadcasted and verified by the network, incurring
communication and computational costs. Furthermore, transactions are visible to
all nodes of the network, eroding privacy, and are recorded permanently,
contributing to increasing storage requirements over time. To limit resource
usage of the network, Bitcoin currently supports an average of 11 transactions
per second.

Most cryptocurrencies today still operate in a substantially similar manner.
Private cryptocurrencies like Zcash and Monero address the privacy issue by
replacing transactions with proofs of transaction validity. However, this
enhanced privacy comes at the cost of increased communication, storage, and
computational requirements.

Client-Side Validation (CSV) is a paradigm that addresses these issues by
removing transaction validation from the blockchain consensus rules. This
approach allows sending the coin along with a validity proof directly to its
recipient, reducing communication, computation and storage cost. CSV protocols
deployed on Bitcoin today~\cite{rgbblackpaper, taprootassets} do not fully
leverage the paradigm's potential, as they still necessitate the overhead of
publishing ordinary Bitcoin transactions. Moreover, the size of their coin
proofs is proportional to the coin's transaction history, and provide limited
privacy. A recent improvement is the Intmax2~\cite{rybakken2023intmax2} CSV
protocol, which writes significantly less data to the blockchain compared to a
blockchain transaction and has succinct coin proofs.

In this work, we introduce Shielded CSV, which improves upon state-of-the-art
CSV protocols by providing the first construction that offers truly private
transactions. It addresses the issues of traditional private cryptocurrency
designs by requiring only 64 bytes of data per transaction, called a
\emph{nullifier}, to be written to the blockchain. Moreover, for each nullifier
in the blockchain, Shielded CSV users only need to perform a single Schnorr
signature verification, while non-users can simply ignore this data. The size
and verification cost of coin proofs for Shielded CSV receivers is independent
of the transaction history. Thus, one application of Shielded CSV is adding
privacy to Bitcoin at a rate of 100 transactions per second, provided there is
an adequate bridging mechanism to the blockchain.

We specify Shielded CSV using the Proof Carrying Data (PCD) abstraction. We then
discuss two implementation strategies that we believe to be practical, based on
Folding Schemes and Recursive STARKs, respectively. Finally, we propose future
extensions, demonstrating the power of the PCD abstraction and the extensibility
of Shielded CSV. This highlights the significant potential for further
improvements to the Shielded CSV framework and protocols built upon it.

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/b0afc5f2-4dcc-469d-b952-03eeac6e7d1b%40gmail.com.

[bitcoindev] Re: Shielded CSV: Private and Efficient Client-Side Validation

[Antoine Riard]

[-- Attachment #1.1: Type: text/plain, Size: 8196 bytes --]

Hi Jonas,

Few remarks from a cursory reading on the abstract, contributions and 
technical overview sections.

As you're underscoring too in the paper, I think one of the main 
scalability bottleneck of the
paper is the 64 byte of data to be written in the blockchain, plus a small 
constant overhead,
that 64 byte be it a plaintext of atomic client-side validation 
transaction, or an aggregation
in some of cryptographically efficient representation such as an 
accumulator.

(The 64 byte of data or whatever the size must be public in the blockchain, 
otherwise a distributed
publication board of the pay-to-contract commitment in the blockchain must 
be available to make the
reveal of the commitment available to CSV clients in a interactively 
mininized fashion).

On the nullifier itself, i.e "Thus far, our protocol lacks a mechanism to 
prevent double spending. To
address this issue, we require that all coins spent in a transaction are 
”nullified” by publishing
a corresponding nullifier on the blockchain". There is a point that Peter 
Todd made me once about
his old tree chain scheme and the probabilistic validation by clients if my 
memory is correct,
where a client does not have to verify the whole of the transactions total, 
where in this proposed
CSV scheme it sounds each nullifier verification participant needs the 
banwidth cost to read the whole
of the blockchain.

Beyond, about the privacy claim, i.e "coin proofs reveal no information 
other than the validity
of the coin and its creation time" there could be a way to hide the coin 
creation time, which
can be a huge factor of deanonymization if you apply cross-layers 
deanonymization techniques,
by using some range proofs like pedersen commitments where the lower and 
upper bound of the
range value are logically ordered on sequence of chain blocks time and 
height (those
maps themselves ordered in a discrete fashion).

Without entering in a debate about perfectly hidding versus perfectly 
binding cryptographic
properties, which can be very quickly degenerates in a debate about axioms 
and corollary
in mathematics, I think such cryptographic structure could have a 
consensus-level usage in
the future, e.g if we extend it as dedicated structure in the taproot 
annex, where the field
is accounted accordingly as witness units.

Best,
Antoine
ots hash: eb285459dacfd0b4b58506f58360fea8b005a66beccc6fdb525ab203341a18c8

Le mardi 24 septembre 2024 à 14:34:15 UTC+1, Jonas Nick a écrit :

> Hello list,
>
> We (Liam Eagen, Robin Linus, and I) are pleased to announce the release of 
> the
> Shielded CSV whitepaper, which describes a private and efficient 
> client-side
> validation (CSV) protocol. Shielded CSV builds upon previous work proposed 
> on
> this mailing list, including contributions by Peter Todd [0], RGB [1], 
> Taproot
> Assets [2], and zkCoins [3].
>
> The whitepaper is available here:
>
> https://github.com/ShieldedCSV/ShieldedCSV/releases/latest/download/shieldedcsv.pdf
>
> Our work differs from previous approaches in two main aspects:
> 1. Shielded CSV is defined using the "Proof-Carrying Data" abstraction, 
> which
> can be instantiated via recursive zkSNARKs or folding schemes. This 
> provides
> "full" privacy (hiding of the transaction graph) and ensures that coin 
> proofs
> and verification time are independent of the transaction graph.
> 2. Instead of using Bitcoin transactions for CSV-payments, a Shielded CSV
> payment only requires posting 64 bytes of data to the blockchain 
> (regardless
> of the CSV-transaction size) and a small constant overhead, significantly
> reducing on-chain cost.
>
> The Shielded CSV protocol is currently defined using Rust-based 
> pseudocode. We
> believe that Shielded CSV is both a promising candidate for implementation 
> and
> provides an extensible framework for further innovation in the CSV space. 
> We
> welcome feedback and look forward to discussing and expanding upon this 
> work.
>
> [0] 
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-November/003714.html
> [1] 
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/021554.html
> [2] 
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020196.html
> [3] 
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-May/021679.html
>
>
> # Abstract
>
> Cryptocurrencies allow mutually distrusting users to transact monetary 
> value
> over the internet without relying on a trusted third party.
>
> Bitcoin, the first cryptocurrency, achieved this through a novel protocol 
> used
> to establish consensus about an ordered transaction history. This requires 
> every
> transaction to be broadcasted and verified by the network, incurring
> communication and computational costs. Furthermore, transactions are 
> visible to
> all nodes of the network, eroding privacy, and are recorded permanently,
> contributing to increasing storage requirements over time. To limit 
> resource
> usage of the network, Bitcoin currently supports an average of 11 
> transactions
> per second.
>
> Most cryptocurrencies today still operate in a substantially similar 
> manner.
> Private cryptocurrencies like Zcash and Monero address the privacy issue by
> replacing transactions with proofs of transaction validity. However, this
> enhanced privacy comes at the cost of increased communication, storage, and
> computational requirements.
>
> Client-Side Validation (CSV) is a paradigm that addresses these issues by
> removing transaction validation from the blockchain consensus rules. This
> approach allows sending the coin along with a validity proof directly to 
> its
> recipient, reducing communication, computation and storage cost. CSV 
> protocols
> deployed on Bitcoin today~\cite{rgbblackpaper, taprootassets} do not fully
> leverage the paradigm's potential, as they still necessitate the overhead 
> of
> publishing ordinary Bitcoin transactions. Moreover, the size of their coin
> proofs is proportional to the coin's transaction history, and provide 
> limited
> privacy. A recent improvement is the Intmax2~\cite{rybakken2023intmax2} CSV
> protocol, which writes significantly less data to the blockchain compared 
> to a
> blockchain transaction and has succinct coin proofs.
>
> In this work, we introduce Shielded CSV, which improves upon 
> state-of-the-art
> CSV protocols by providing the first construction that offers truly private
> transactions. It addresses the issues of traditional private cryptocurrency
> designs by requiring only 64 bytes of data per transaction, called a
> \emph{nullifier}, to be written to the blockchain. Moreover, for each 
> nullifier
> in the blockchain, Shielded CSV users only need to perform a single Schnorr
> signature verification, while non-users can simply ignore this data. The 
> size
> and verification cost of coin proofs for Shielded CSV receivers is 
> independent
> of the transaction history. Thus, one application of Shielded CSV is adding
> privacy to Bitcoin at a rate of 100 transactions per second, provided 
> there is
> an adequate bridging mechanism to the blockchain.
>
> We specify Shielded CSV using the Proof Carrying Data (PCD) abstraction. 
> We then
> discuss two implementation strategies that we believe to be practical, 
> based on
> Folding Schemes and Recursive STARKs, respectively. Finally, we propose 
> future
> extensions, demonstrating the power of the PCD abstraction and the 
> extensibility
> of Shielded CSV. This highlights the significant potential for further
> improvements to the Shielded CSV framework and protocols built upon it.
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/33cd30ab-c5c2-4785-9815-4a2da3c7e267n%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 10578 bytes --]

Re: [bitcoindev] Re: Shielded CSV: Private and Efficient Client-Side Validation

[Jonas Nick]

Hi Antoine,

Thank you for your comments. They are touching on some of the key aspects of the
protocol.

 > in this proposed CSV scheme it sounds each nullifier verification participant
 > needs the banwidth cost to read the whole of the blockchain.

You're correct. Shielded CSV nodes need to have access to the current best
blockchain, similar to regular Bitcoin nodes. Shielded CSV nodes scan for
64-byte nullifiers, verify their half-aggregate signatures and place them in a
data structure we call "nullifier accumulator".

There's potential for a light client scheme, where users don't validate blocks,
but infer the best blockchain via proof-of-work (similar to SPV) and obtain the
corresponding nullifier accumulator value from somewhere. In addition, they
receive a succinct proof that the blockchain is valid and the nullifier
accumulator value is correct.

This model allows the light client to receive transactions. However, to create
transactions, they need to prove inclusion in the nullifier accumulator, which
requires knowledge of the nullifiers in the blockchain. There are some ideas for
how to do this in a relatively light fashion, but nothing concrete yet. It's
certainly an interesting area for further exploration.

 > there could be a way to hide the coin creation time

A coin (the data sent to the recipient) contains the exact location of the
nullifier that created the coin. This is indeed a noteworthy issue and we
discuss the implications in section 6.3 of the paper. In particular, revealing
the nullifier location implies that outputs of the same transaction are
linkable. We therefore suggest that regular wallets should just create a single
output.

A fundamental limitation of the Shielded CSV model appears to be that the sender
must reveal an upper bound on when the coin has been created ("This coin is
older than the block at height..."). Otherwise, the receiver would not know how
long to wait until the coin has sufficient confirmations.

In fact, a previous version of the Shielded CSV protocol did exactly that. But
we moved away from that because it was incompatible with our ideas to support
pruning the wallet state (i.e., removing old transaction history), which is an
important aspect in holistic privacy.

We came up with a version of the protocol that supported prunable wallet state
and only leaked the block in which the coin was created and not the exact
nullifier. However, this version has two drawbacks:
1. The state the wallet needs to keep for the unpruned transaction history is
    larger: 256 bits per received coin (one hash) instead of about 60 bits (the
    blockchain location).
2. The privacy improvement is fuzzy and difficult to understand. In the extreme
    case, such as when there's only one nullifier in the block, there's no
    improvement over the current Shielded CSV version.

But I agree, if possible without significant drawbacks, this privacy leak should
be mitigated.

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/14b8d064-1097-4cc5-a0f4-56bbd4f9417b%40gmail.com.

Re: [bitcoindev] Re: Shielded CSV: Private and Efficient Client-Side Validation

[Weikeng Chen]

[-- Attachment #1.1: Type: text/plain, Size: 4090 bytes --]


I think the main challenge for the protocol is bridging, as the paper 
mentions in Page 4, because without which it might appear that we are just 
using Bitcoin for data availability.

BitVM can help with it, but if we have some upgrades that provide the 
necessary programmability (e.g., a full-fledged SNARK verification opcode) 
then this protocol can be deployed on Bitcoin in no time, and Bitcoin can 
finally have strong privacy.


On Thursday, September 26, 2024 at 5:43:23 PM UTC+3 Jonas Nick wrote:

> Hi Antoine,
>
> Thank you for your comments. They are touching on some of the key aspects 
> of the
> protocol.
>
> > in this proposed CSV scheme it sounds each nullifier verification 
> participant
> > needs the banwidth cost to read the whole of the blockchain.
>
> You're correct. Shielded CSV nodes need to have access to the current best
> blockchain, similar to regular Bitcoin nodes. Shielded CSV nodes scan for
> 64-byte nullifiers, verify their half-aggregate signatures and place them 
> in a
> data structure we call "nullifier accumulator".
>
> There's potential for a light client scheme, where users don't validate 
> blocks,
> but infer the best blockchain via proof-of-work (similar to SPV) and 
> obtain the
> corresponding nullifier accumulator value from somewhere. In addition, they
> receive a succinct proof that the blockchain is valid and the nullifier
> accumulator value is correct.
>
> This model allows the light client to receive transactions. However, to 
> create
> transactions, they need to prove inclusion in the nullifier accumulator, 
> which
> requires knowledge of the nullifiers in the blockchain. There are some 
> ideas for
> how to do this in a relatively light fashion, but nothing concrete yet. 
> It's
> certainly an interesting area for further exploration.
>
> > there could be a way to hide the coin creation time
>
> A coin (the data sent to the recipient) contains the exact location of the
> nullifier that created the coin. This is indeed a noteworthy issue and we
> discuss the implications in section 6.3 of the paper. In particular, 
> revealing
> the nullifier location implies that outputs of the same transaction are
> linkable. We therefore suggest that regular wallets should just create a 
> single
> output.
>
> A fundamental limitation of the Shielded CSV model appears to be that the 
> sender
> must reveal an upper bound on when the coin has been created ("This coin is
> older than the block at height..."). Otherwise, the receiver would not 
> know how
> long to wait until the coin has sufficient confirmations.
>
> In fact, a previous version of the Shielded CSV protocol did exactly that. 
> But
> we moved away from that because it was incompatible with our ideas to 
> support
> pruning the wallet state (i.e., removing old transaction history), which 
> is an
> important aspect in holistic privacy.
>
> We came up with a version of the protocol that supported prunable wallet 
> state
> and only leaked the block in which the coin was created and not the exact
> nullifier. However, this version has two drawbacks:
> 1. The state the wallet needs to keep for the unpruned transaction history 
> is
> larger: 256 bits per received coin (one hash) instead of about 60 bits (the
> blockchain location).
> 2. The privacy improvement is fuzzy and difficult to understand. In the 
> extreme
> case, such as when there's only one nullifier in the block, there's no
> improvement over the current Shielded CSV version.
>
> But I agree, if possible without significant drawbacks, this privacy leak 
> should
> be mitigated.
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/27a7ee92-8c2b-45ca-9e1c-257a32eb3252n%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 4727 bytes --]