Advanced Blockchains: Overcoming Cryptographic Challenges and Applications
Explore the application of blockchains in overcoming cryptographic impossibility results, including one-time programs and specific blockchain properties. Learn about new proof-of-stake abstractions and defining stake fractions in blockchain systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Lecture 16 Applications of Blockchains - IV
Overcoming Cryptographic Impossibility Results using Blockchains Rishab Goyal and Vipul Goyal TCC 2017 Slides based on Rishab s talk at TCC 17
One-Time Programs [GoldwasserKalaiRothblum08] Can only be executed on single input Input chosen at run-time x x f(x) + f f x x y f f +
One-Time Programs f One-Time Compiler f [GKR 08]: Construction based on tamper- proof hardware tokens
One-Time Programs f One-Time Compiler f [GKR 08]: Construction based on tamper- proof hardware tokens [GG 17]: Software-only construction using blockchains
Main Ingredients: Extractable Witness Encryption (last lecture) Garbled Circuits (today) f Blockchains with specific properties (today)
Recall: Blockchain Properties [GarayKiayiasLeonardos15,PassSeemanShelat16] Chain Consistency: Honest parties agree on all but last blocks Last inconsistent
Recall: Blockchain Properties [GarayKiayiasLeonardos15,PassSeemanShelat16] Chain Consistency: Honest parties agree on all but last blocks Chain Quality: # of blocks mined by honest parties to their voting power (any consecutive blocks)
[GG17]: New Proof-of-Stake Specific Abstractions
Defining Stake Fraction Measure of combined difficulty of POS puzzles solved Mined by A Proved 10% stake Mined by C Proved 15% stake Mined by A Proved 10% stake Mined by B Proved 5% stake
Defining Stake Fraction Measure of combined difficulty of POS puzzles solved Mined by A Proved 10% stake Mined by C Proved 15% stake Mined by A Proved 10% stake Mined by B Proved 5% stake Stake Fraction = 30%
(?,)-Sufficient Stake Contribution Total stake-fraction in last blocks is a (fairly) high fraction ( ?) Stake Fraction ?
(?,)-Bounded Stake Forking No adversary can create a valid fork (length ) with high stake-fraction ( ?) Stake Fraction ?
(?,?,)-Distinguishable Forking Honest chain of blocks can be distinguished from adversarial fork Stake Fraction ? ? < ? Stake Fraction ?
Connection to Previous Properties [GG 17]: If a PoS blockchain satisfies chain consistency and chain quality, then it also satisfies the following properties: sufficient (honest-) stake contribution bounded stake forking distinguishable forking (for some choice of parameters)
[GG17] One-Time Program Compilation: Garbled Circuit G 1. Garble Circuit C Input Key pairs (wi,0wi,1) 2. Witness Encryption Encrypted Input Key pairs (cti,0cti,1)
[GG17] One-Time Program Evaluation steps (informal): 1. Evaluator posts its input x on the blockchain 2. Waits for the blockchain to be sufficiently extended 3. Uses the blockchain state as a witness to decrypt the WE ciphertexts to learn wire keys for x 4. Uses wire keys for x to evaluate the Garbled Circuit G and learn C(x)
[GG17] One-Time Program Compilation{ Garbled Circuit G Garbling WE+ Circuit C Encrypted Input Key pairs (cti,0cti,1) Stake Fraction > 1 Evaluation 2 -------------------- Next Block Next Block New Block Last Block Present Blockchain Post input x Extending Blockchain
[GG17] One-Time Program Compilation{ Garbled Circuit G Garbling WE+ Circuit C Encrypted Input Key pairs (cti,0cti,1) Evaluation Use this as witness -------------------- Next Block Next Block New Block Last Block Present Blockchain Post input x Extending Blockchain
[GG17] One-Time Program Security (informal): To evaluate OTP on any input x, adversary must first post it on the blockchain If adversary posts x x after already posting x, blockchain state will contain both of them Such a blockchain state is not a valid witness (rejected by WE)
WE Ciphertext Use this as witness Hardwired in WE ciphertexts -------------------- Next Block Next Block Next Block New Block Last Block Present Blockchain Post input x Post input x
[GG17] One-Time Program Security (contd): But what if adversary creates a fork from last block and posts x there? To create a valid witness, adversary must extend the fork so that it has stake fraction > 1/2 Any such fork will be distinguishable from real chain due to distinguishable forking property
