Scaling Verifiable Computation Using Efficient Set Accumulators
Host
Kyle Hogan
Verifiable outsourcing systems offload a large computation to a remote server,
but require that the remote server provide a succinct proof, called a SNARK,
that proves that the server carried out the computation correctly. Real-world
applications of this approach can be found in several blockchain systems that
employ verifiable outsourcing to process a large number of transactions
off-chain. This reduces the on-chain work to simply verifying a succinct proof
that transaction processing was done correctly. In practice, verifiable
outsourcing of state updates is done by updating the leaves of a Merkle tree,
recomputing the resulting Merkle root, and proving using a SNARK that the
state update was done correctly.
In this work, we use a combination of existing and novel techniques to
implement an RSA accumulator inside of a SNARK, and use it as a replacement
for a Merkle tree. We specifically optimize the accumulator for compatibility
with SNARKs. Our experiments show that the resulting system can dramatically
reduce costs compared to existing approaches that use Merkle trees for
committing to the current state. These results apply broadly to any system
that needs to offload batches of state updates to a remote untrusted server.
Topic: CSAIL Security Seminar
Time: This is a recurring meeting Meet anytime
Join Zoom Meeting
https://mit.zoom.us/j/93005778614
One tap mobile
+16465588656,,93005778614# US (New York)
+16699006833,,93005778614# US (San Jose)
Meeting ID: 930 0577 8614
US : +1 646 558 8656 or +1 669 900 6833
International Numbers: https://mit.zoom.us/u/abt2humbfA
Join by SIP
93005778614@zoomcrc.com
Join by Skype for Business
https://mit.zoom.us/skype/93005778614
but require that the remote server provide a succinct proof, called a SNARK,
that proves that the server carried out the computation correctly. Real-world
applications of this approach can be found in several blockchain systems that
employ verifiable outsourcing to process a large number of transactions
off-chain. This reduces the on-chain work to simply verifying a succinct proof
that transaction processing was done correctly. In practice, verifiable
outsourcing of state updates is done by updating the leaves of a Merkle tree,
recomputing the resulting Merkle root, and proving using a SNARK that the
state update was done correctly.
In this work, we use a combination of existing and novel techniques to
implement an RSA accumulator inside of a SNARK, and use it as a replacement
for a Merkle tree. We specifically optimize the accumulator for compatibility
with SNARKs. Our experiments show that the resulting system can dramatically
reduce costs compared to existing approaches that use Merkle trees for
committing to the current state. These results apply broadly to any system
that needs to offload batches of state updates to a remote untrusted server.
Topic: CSAIL Security Seminar
Time: This is a recurring meeting Meet anytime
Join Zoom Meeting
https://mit.zoom.us/j/93005778614
One tap mobile
+16465588656,,93005778614# US (New York)
+16699006833,,93005778614# US (San Jose)
Meeting ID: 930 0577 8614
US : +1 646 558 8656 or +1 669 900 6833
International Numbers: https://mit.zoom.us/u/abt2humbfA
Join by SIP
93005778614@zoomcrc.com
Join by Skype for Business
https://mit.zoom.us/skype/93005778614