Andrew Miller [ARCHIVE] / is on Nostr

⚠️ This account is not associated with a real person. It's an archival account for mailing list messages.
🗓️ Active from 2012-06-19 to 2018-12-07
💬 Posted a total of 9 messages
📚 Participated in the following categories: Bitcoin-development, bitcoin-dev, Lightning-dev
🔇 Please do not DM this user as it's used for archive purposes only.

Last Notes

2023-06-09 12:45:19

- reply

📅 Original date posted:2015-12-02
📝 Original message:
So, it turns out that a SNARK is overkill for the application in this
thread. It was just a one-off experiment. But the performance estimates
seemed pretty far off compared to what’s reported in in the snark science
papers. So, Sean (a Zcash engineer, in his “20% fun time”) replicated the
experiment from the original post, in libsnark (not snarklib).
First, as a recap, this is the specification of the original post’s SNARK,
summarized in Camenisch-Stadler notation:
ZkPoK{ (R1, R2): H1 = sha256(R1) and H2 = sha256(R2) and R1 = R2 xor X }
In other words: given a statement H1, H2, and X, you can prove that you
know a secret witness R1, and R2, such that the predicate holds (i.e., R1
and R2 are preimages of H1,H2 and are related by X)
This is almost a complete specification of the SNARK: all that’s left is to
choose a representation size for R1 and R2…. here these are forced to be
32-byte strings.
Here are the results for a libsnark implementation of this, ordered up to
the above spec:
https://github.com/ebfull/lightning_circuit/
Most relevant benchmarks:
key generation time: 11.6270s
proof generation time: 3.0968s
verification time: 0.0270s
proof size: ~287 bytes
proving key size: ~12.85 megabytes
verifying key size: ~573 bytes
R1CS constraints: 56612 (mostly sha256-related)
The difference in proof time and proving key size (this is ~3x faster to
prove, with ~10x less key size) might be explained by libsnark having a
more efficient SHA256 implementation. The libsnark one is hand-optimized.
But I don’t have any idea why the OP and snarklib reported such large
verification keys or memory consumption during verification. The verifier
should only have to think of about a kilobyte.
On Tue, Nov 17, 2015 at 4:14 PM, Anthony Towns <aj at erisian.com.au> wrote:
> Hi all,
>
> An obvious privacy limitation with lightning is that even with onion
> routing, differents hops can be associated as being part of the same
> transaction due to sharing a common R value. So if you see a HTLC from
> Alice to Bob, paying $5 to Bob on receipt of R where SHA(R)=12345..;
> and you see another HTLC from Carol to Dave, paying $4.95 to Bob on
> receipt of R under the same condition, SHA(R)=12345..., then you know
> it's part of the same transaction.
>
> If you could change R at each step in the route, this would go away,
> improving payment anonymity and making it harder to attack the system in
> general.
>
> That's hard, because as a forwarding node, if you receive a HTLC payable
> on R1, then to send a HTLC payable on R2, you need to be able to
> calculate R1 from R2 or you'll be out of pocket. But you also can't be
> able to calculate R1 *without* R2, or you could just rip off whoever's
> making the payment. And, of course you have to know SHA(R2) to forward the
> payment at all. And if you only know SHA(R1) and SHA(R2) it's hard to
> say anything at all about R1 and R2 because cryptographic hash functions
> are designed to make any structural relationships go away.
>
> BUT! I think the magic of SNARKs [0] lets you do this!
>
> With a SNARK, you can "prove" that you have some secrets (ie, R1 and R2)
> that satisfy some programmable condition (ie, SHA(R1)=H1 and SHA(R2)=H2
> and R1=R2 XOR X), based on public inputs (H1, H2 and X), without revealing
> those secrets.
>
> I think that's pretty safe, because if you receive an HTLC asking for a
> preimage for H1, along with instructions in the onion saying ask Bob for
> a preimage for H2, and here's X and a proof, then either:
>
> - your forwarded HTLC will fail, and everything's fine
>
> - you'll receive R2, calculate R1=R2 XOR X and see SHA(R1)=H1 as
> expected, and everything's fine
>
> - you'll receive R2, calculate R1=R2 XOR X and see SHA(R1) != H1,
> which is only possible if the cryptography behind SNARKs are broken
>
> - you'll receive RX, such that H2=SHA(RX) but RX being too
> long or too short. If SNARKs aren't broken, this means that you know
> R2alt and someone else knows R2 that are different but hash to the
> same value, meaning SHA has been broken.
>
> It seems like there are research-level tools out there that actually
> make this practical to try out. I've had a go at implementing this using
> snarkfront [1]. Using it looks like:
>
> 1) initial setup of proof/verification keys
>
> $ ./test_lightning -m keygen > keygen.txt # global setup
>
> 2) generate a proof, using a 32 byte secret, and XOR key (64 hex digits)
>
> $ SECRET="the quick brown fox jumps lazily"
> $ XOR=$(echo "she sells sea shells" | sha256sum | head -c64)
> $ cat keygen.txt |
> ./test_lightning -m proof -s "$SECRET" -x "$XOR" > proof.txt
> m: proof.
> f: .
> b: .
> x: 5677d356ccd6ff29b296a697791d109a1703557ecbbcf52b4f38d4b680858912.
> F: 74686520717569636b2062726f776e20666f78206a756d7073206c617a696c79
> B: 221fb676bda3964ad9b6c4e5166a7eba716c2d5ea1c9985b3c18b8d7faece56b
> #F: ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85
> #B: 166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245
> generate proof
> (6) ..................................................
> (5) ..................................................
> (4) ..................................................
> (3) ..................................................
> (2) ..................................................
> (1) ..................................................
>
> 3) Verify the proof:
>
> $ F=ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85
> $ B=166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245
> $ cat keygen.txt proof.txt |
> ./test_lightning -m verify -h "$F" -b "$B" -x "$XOR"
> m: verify.
> f: ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85.
> b: 166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245.
> x: 5677d356ccd6ff29b296a697791d109a1703557ecbbcf52b4f38d4b680858912.
> verify proof (6) (5) (4) (3) (2) (1)
> proof is verified
>
> 4) Verify it doesn't report a valid proof with different inputs:
>
> $ cat keygen.txt proof.txt |
> ./test_lightning -m verify -h "$B" -b "$F" -x "$XOR"
> m: verify.
> f: 166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245.
> b: ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85.
> x: 5677d356ccd6ff29b296a697791d109a1703557ecbbcf52b4f38d4b680858912.
> verify proof (6) (5) (4) (3) (2)
> proof is rejected
>
> Some results:
>
> * the proof/verification key data take up about 100MB -- in theory
> one set of this data can be used by everyone; the only catch is
> that everyone has to trust that nobody has kept the original random
> numbers used to generate it.
>
> * proof/verification key data takes about a minute to generate,
> and about 650MB of RAM.
>
> * the proof data itself (which would need to be sent to the node that's
> going to switch R's) is just 864 bytes; so it'd use up about 5 hops
> worth of onion routing at 192B per hop -- in a 4096 byte packet eg,
> you could have four hops, changing R each time; or you could have 9
> hops, changing R only three times.
>
> * generating the proof data for a given R1,X pair takes about 10
> seconds, and 260MB of RAM
>
> * verifying the proof is quick-ish -- it takes 0.5s on my laptop,
> and uses about 150MB of RAM.
>
> For comparison, that last point makes a SNARK verification 500+ times
> more expensive than an ECDH operation. If I got my maths right, you
> can translate 3c for a linode CPU-hour into 2.5 satoshi for a linode
> CPU-second (at $338/BTC), so you're probably looking at a minimum fee
> of a few satoshi per SNARK verification, but that's still pretty okay
> for transactions of 500 satoshi or more, ie anything more than about a
> fifth of a US cent.
>
> The 10s proof generation time is probably more of a limitation -- though
> you could generate them in advance easily enough and just store them until
> you need to use them, which would avoid lag being a problem at least. But
> even then it's still essentially adding up to 30c of additional costs to
> your transaction (ie 10s cpu time valued at up to 3c/s), which probably
> isn't worthwhile for transactions smaller than a dollar or two.
>
> A drawback is that you'd either (a) have to do all this on the merchant's
> side (not just sending SHA(R) to whoever wants to pay you, but sending
> SHA(R1), SHA(R2), SHA(R3), SHA(R4), X12, X23, X34, and three proofs,
> which would be pretty painful; or (b) you'd have to generate all the
> R secrets as a consumer, and you wouldn't get to use the fact that you
> know R as evidence that you paid the merchant.
>
> Anyway, it's obviously not ready for prime time today: SNARKs are still
> pretty new as a concept; I'm definitely not familiar enough with SNARK
> theory to be sure I'm not misusing the concept somehow; snarkfront may not
> have implemented the theory fully correctly; and I might not have captured
> everything I needed to in order for my "proof" to actually say what I
> want it to. So not a great idea to use this to protect real money today.
>
> But still, this seems like it's not all /that/ far from being practical,
> and if the crypto's not fundamentally broken, seems like it goes a long
> way to filling in the biggest privacy hole in lightning today [3]...
>
> Code is at https://github.com/ajtowns/snarkfront/ or more directly at:
> https://github.com/ajtowns/snarkfront/blob/lightning-sha/test_lightning.cpp
>
> Cheers,
> aj
>
> [0] https://tahoe-lafs.org/trac/tahoe-lafs/wiki/SNARKs
>
> [1] https://github.com/jancarlsson/snarkfront
>
> [2] This would also improve privacy/anonymity for other applications of
> HTLCs, such as atomic swaps across chains:
>
> 1 bitcoin, payable on R1 + Alice's sig or timeout + Bob's sig
> 100 litecoin, payable on R2 + Robert's sig or timeout + Ally's sig
>
> Alice and Bob communicate privately, agreeing to trade 1 BTC for 100
> litecoin and revealing their aliases Robert and Ally; Alice generates
> R1, R2, and reveals SHA(R1), SHA(R2), R1^R2 and the SNARK proof and
> publishes the litecoin payment. Bob verifies the proof, and publishes
> the bitcoin payment. Alice claims the bitcoin payment, revealing R1;
> Bob calculates R2 and claims the litecoin payment. The swap can take
> place trustlessly because Bob knows the only way Alice can claim his
> bitcoin is by revealing enough info so he can claim the corresponding
> litecoin. But there isn't any on-chain information linking the two
> transactions, because R1 and R2 are independent (and could even be
> using different hash functions as well as different preimages).
> After the funds have been claimed, the private communication is
> also completely deniable, since anyone could generate R1^R2 and a
> corresponding SNARK proof just using the info on the blockchain.
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20151202/97972a83/attachment.html>

2023-06-09 12:45:04

- reply

📅 Original date posted:2015-11-24
📝 Original message:
Even though it seems like SNARKs aren't strictly necessary for this
application, it's awesome you tried that out!
So, there are a couple of things that seem off to me about those
performance estimates. I don't know snarklib/snarkfront well so I'm not
sure what would cause this.
But checking a single snark proof should take around 10 milliseconds rather
than 500 milliseconds. And it should only require like a kilobyte of memory
to verify, definitely not 150 MB.
Also when you say that the verification/proving key is 100MB, those are two
very different keys! The verification key should be extremely small, in the
kilobyte range.
When I have some time (hopefully later this week) I'll try to reproduce
this experiment using libsnark and write back in this thread. Some students
at UMD also have a tool for composing circuits that is (arguably) more
user-friendly and complements libsnark, I'm really hoping they release
those open source soon!
On Tue, Nov 24, 2015 at 12:45 AM, Anthony Towns <aj at erisian.com.au> wrote:
> On 24 November 2015 1:30:19 pm AEST, Rusty Russell <rusty at rustcorp.com.au>
> wrote:
> >Anthony Towns <aj at erisian.com.au> writes:
> >> On Fri, Nov 20, 2015 at 12:05:46PM +1030, Rusty Russell wrote:
> >>> With the segregated witness proposal, introducing new opcodes is
> >easy,
> >>> so maybe someone would find a reason to prefer open-coding it like
> >this?
> >>
> >> I don't follow how segregated witness makes new opcodes any easier?
> >
> >I didn't either, and that's because it's slightly orthogonal.
> >
> >The proposal I heard is that the first byte of SW script is a version
> >byte, and if you don't understand that version, the script succeeds.
>
> Ah, I see - it doesn't make OP_CHECK*VERIFY any easier then, but adding
> ops that actually change the contents of the stack becomes a soft fork
> instead of a hard fork. Pretty neat. Don't think that's needed here though.
>
> Cheers,
> aj
>
>
> --
> Sent from my phone.
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20151124/35b6db51/attachment.html>

2023-06-09 12:44:27

- reply

📅 Original date posted:2015-09-18
📝 Original message:
Are there any downsides of the alternative proposed in this paper? There
was a discussion on Bitcoin subreddit but it got derailed
https://m.reddit.com/r/compscipapers/comments/3at959/a_fast_and_scalable_payment_network_with_bitcoin/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20150918/c4acb75b/attachment.html>

2023-06-07 18:15:42

- reply

📅 Original date posted:2018-12-07
📝 Original message:Hi all,
I'm happy to announce the first Cryptocurrency Implementers' Workshop,
cohosted with Financial Crypto.
http://fc19.ifca.ai/ciw/
Now that the BITCOIN cryptocurrency research workshop has been folded
into the main FC conference, it's time to try something new. The goal of
this workshop is to focus on real world experience and engineering efforts.
As such we're soliciting submission of *running code* to give a live demo
at the workshop. Because of the tight timeline, there are only two weeks to
go before the submission deadline, Dec 21. More details below the fold, and
at the website link.
--
Andrew Miller
University of Illinois at Urbana-Champaign
With the inclusion of the BITCOIN: Bitcoin and Cryptocurrency Research
Workshop into the "Blockchain Track" of the Financial Cryptography
conference, we now want to try out an experimental new workshop format,
which focuses on engineering, development, and real world use of
cryptocurrencies and permissionless blockchains.
In this first iteration, the workshop will be a half day, and the program
will consist of two main components:
Invited talks on implementation post mortems:
-----
we will aim to have several talks from developers and engineers that have
led and maintained open source software projects in use by cryptocurrencies
today.
Artifact Evaluation and Demo show and tell:
----
We will have a technical program of demo presentations about open source
software artifacts. Presenters must submit their talk and demo abstract
along with the open source software itself for review. Presentation
abstracts should be no more than 6 pages in LNCS format, or the equivalent
length (no more than 2000 words) of text, Markdown, etc. The write up
should include:
motivation and application,
novelty or differences compared to alternative or related implementations,
challenges faced,
possible evaluation approaches
Submissions must include a software artifact that can be reviewed. It is
expected the review committee will at least be able to run the artifact and
observe the outputs. We recommend including a virtual machine image or
Docker-based build instructions to facilitate this.
Suggested topics
====
The following list is non-exhaustive:
Cryptography implementations, such as digital signatures, ring signatures,
zero knowledge proofs
Proof-of-work consensus protocols
Proof-of-stake consensus protocols
Mining hardware designs
Peer-to-peer networking and broadcast relay code
Full node synchronization
SPV and lightweight clients
Wallets and key management
Security vulnerabilities and defenses
Mining pools
Mining rig controllers
Staking wallets
Important Dates
====
Dec 21: Submission deadline
Jan 7: Presenter notification
Feb 22: Workshop
Submission Instructions
===
The submission website and instructions will be available mid December.
Demos accepted to this program will not be included in any proceedings.
Submission and acceptance in this workshop does not preclude publication
elsewhere.
Submissions may be anonymized at the authors' discretion, but it is not a
requirement.
Program Commitee
====
J. Ayo Akinyele (Yeletech)
Rebekah Mercer (Aarhus)
Pieter Wuille (Blockstream)
Benedikt Bünz (Stanford)
Ethan Heilman (Boston University, Commonwealth Crypto)
Patrick McCorry (Kings College London)
Justin Ehrenhofer (Monero Community WorkGroup)
Jacob Eberhardt (tu-berlin)
... (more to come)
Program Chairs
====
Andrew Miller (UIUC)
Christopher Allen
Contact email address: Andrew Miller <soc1024 at illinois.edu>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20181207/e92b7511/attachment.html>

2023-06-07 18:03:07

- reply

📅 Original date posted:2017-06-12
📝 Original message:Dear bitcoin-dev,
We've put together a preliminary implementation and BIP for
Dandelion, and would love to get your feedback on it. Dandelion is a
privacy-enhancing modification to Bitcoin's transaction propagation
mechanism. Its goal is to obscure the original source IP of each
transaction.
https://github.com/gfanti/bips/blob/master/bip-dandelion.mediawiki
https://github.com/gfanti/bitcoin/tree/dandelion
The main idea is that transaction propagation proceeds in two
phases: first the “stem” phase, and then “fluff” phase. During the
stem phase, each node relays the transaction to a *single* peer. After
a random number of hops along the stem, the transaction enters the
fluff phase, which behaves just like ordinary transaction
flooding/diffusion. Even when an attacker can identify the location of
the fluff phase, it is much more difficult to identify the source of
the stem. Our approach and some preliminary evaluation are explained
in more detail in the BIP. The research paper originally introducing
this idea was recently presented at SIGMETRICS'17.
https://arxiv.org/pdf/1701.04439.pdf
Compared to the original paper, our current proposal includes
several new design ideas, especially:
- Stronger attacker model: we defend against an attacker that
actively tries to learn which nodes were involved in the stem phase.
Our approach is called "Mempool Embargo", meaning a node that receives
a "stem phase" transaction behaves as though it never heard of it,
until it receives it again from someone else (or until a random timer
elapses).
- Robustness. We think the privacy benefit shouldn't come at the
expense of propagation quality. Our implementation is designed so that
if some node drops the transaction (or when Dandelion is adopted only
partially), then the fallback behavior is ordinary Bitcoin
propagation.
We'd especially like feedback on the implementation details related
to the two points above. The mempool embargo mechanism is tricky,
since it hard to rule out indirect behavior that reveals if a
transaction is in mempool. In the BIP we explain one counterexample,
but at least it requires the attacker to get its connections banned.
Are there other ways we haven't thought of? We think the alternative
approach (bypassing mempool entirely) seems even harder to get right,
and foregoes existing DoS protection.
We're currently running in-situ benchmark experiments with this code
on testnet and will report on those in this thread if there's
interest.
Some prior discussion can be found here:
- https://botbot.me/freenode/bitcoin-wizards/2017-03-29/?msg=83181866&page=2
- https://botbot.me/freenode/bitcoin-wizards/2017-01-18/?msg=79578754&page=2
- https://github.com/sbaks0820/bitcoin-dandelion/issues/1 (notes
from gmaxwell that we've mostly incorporated in the current proposal)
Thanks!
-----
Giulia Fanti <gfanti at andrew.cmu.edu>
Andrew Miller <soc1024 at illinois.edu>
Surya Bakshi <sbakshi3 at illinois.edu>
Shaileshh Bojja Venkatakrishnan <bjjvnkt2 at illinois.edu>
Pramod Viswanath <pramodv at illinois.edu>

2023-06-07 17:42:34

- reply

📅 Original date posted:2015-10-06
📝 Original message:Shadow uses virtual time, entirely decoupled from real time. So while it
may slow down your machine, this would not affect the stats collected
(although it does make shadow somewhat unpleasant to run, unless you have a
fast machine, compared to abstract simulators that avoid running the
actual Bitcoin code).
Hi Byron,
I've been using shadow a bit-- I think these simulators are important for
testing, but Shadow, at least, certainly seems to have limitations, in some
crucial respects. Running shadow w Tor (which is only logical, because
many BCT transactions transpire over Tor) is not as 'light' as presented
and slows my own box down quite a bit, so the stats can't possibly be
accurate... I don't know if this answers any questions or if you've had
this experience at all -- perhaps it is negligible on a more powerful
machine than my own-- or perhaps there is an adjustment still unaccounted?
Regards,
Nina K
Sent from my iPhone
On Oct 4, 2015, at 2:04 PM, Byron Gibson via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
Hi all, is anyone using simulators like Shadow (https://shadow.github.io),
BTCSim (https://github.com/btcsuite/btcsim), etc. to test proposed changes
to Bitcoin? I have a few questions about their capabilities and
limitations.
Byron Gibson
http://mirror.co/
https://keybase.io/byrongibson
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev at lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev at lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20151006/4a166b23/attachment.html>

2023-06-07 15:31:41

- reply

📅 Original date posted:2015-03-02
📝 Original message:We (Joseph Bonneau, myself Arvind Narayanan, Jeremy Clark, Ed Felten,
Josh Kroll -- from Stanford, Maryland, Concordia, Princeton) have
written a “systemization” paper about Bitcoin-related research. It’s
going to appear in the Oakland security conference later this year
(IEEE Security and Privacy) but we wanted to announce a draft to this
community ahead of time.
http://www.jbonneau.com/doc/BMCNKF15-IEEESP-bitcoin.pdf
One of the main goals of our work is to build a bridge between the
computer science research community and the cryptocurrency community.
Many of the most interesting ideas and proposals for Bitcoin come from
this mailing list and forums/wikis/irc channels, where many academic
researchers simply don’t know to look! In fact, we started out by
scraping all the interesting posts/articles we could find and trying
to figure out how we could organize them. We hope our paper helps some
of the best ideas and research questions from the Bitcoin community
bubble up and inspires researchers to build on them.
We didn’t limit our scope to Bitcoin, but we also decided not to
provide a complete survey of altcoins and other next-generation
cryptocurrency designs. Instead, we tried to explain all the
dimensions along which these designs differ from Bitcoin.
This effort has roughly been in progress over two years, though it
stopped and restarted several times along the way.
If anyone has comments or suggestions, we still have a week before the
final version is due, and regardless we plan to continue updating our
online version for the forseeable future.

2023-06-07 10:18:34

- reply

📅 Original date posted:2012-06-19
📝 Original message:Alan Reiner wrote:
> A PATRICIA tree/trie would be ideal, in my mind, as it also has a
> completely deterministic structure, and is an order-of-magnitude more
> space-efficient. Insert, delete and query times are still O(1).
> However, it is not a trivial implementation. I have occasionally looked
> for implementations, but not found any that were satisfactory.
PATRICIA Tries (aka Radix trees) have worst-case O(k), where k is the
number of bits in the key. Notice that since we would storing k-bit
hashes, the number of elements must be less than 2^k, or else by
birthday paradox we would have a hash collision! So O(log N) <= O(k).
You're right, though, that such a trie would have the property that
any two trees containing the same data (leaves) will be identical. I
can't think of any reason why this is useful, although I am hoping we
can figure out what is triggering your intuition to desire this! I am
indeed assuming that the tree will be incrementally constructed
according to the canonical (blockchain) ordering of transactions, and
that the balancing rules are agreed on as part of the protocol.
--
Andrew Miller

2023-06-07 10:18:08

- reply

📅 Original date posted:2012-06-19
📝 Original message:> Peter Todd wrote:
> My solution was to simply state that vertexes that happened to cause the
> tree to be unbalanced would be discarded, and set the depth of inbalance
> such that this would be extremely unlikely to happen by accident. I'd
> rather see someone come up with something better though.
Here is a simpler solution. (most of this message repeats the content
of my reply to the forum)
Suppose we were talking about a binary search tree, rather than a
Merkle tree. It's important to balance a binary search tree, so that
the worst-case maximum length from the root to a leaf is bounded by
O(log N). AVL trees were the original algorithm to do this, Red-Black
trees are also popular, and there are many similar methods. All
involve storing some form of 'balancing metadata' at each node. In a
RedBlack tree, this is a single bit (red or black). Every operation on
these trees, including search, inserting, deleting, and rebalancing,
requires a worst-case effort of O(log N).
Any (acyclic) recursive data structure can be Merkle-ized, simply by
adding a hash of the child node alongside each link/pointer. This way,
you can verify the data for each node very naturally, as you traverse
the structure.
In fact, as long as a lite-client knows the O(1) root hash, the rest
of the storage burden can be delegated to an untrusted helper server.
Suppose a lite-client wants to insert and rebalance its tree. This
requires accessing at most O(log N) nodes. The client can request only
the data relevant to these nodes, and it knows the hash for each chunk
of data in advance of accessing it. After computing the updated root
hash, the client can even discard the data it processed.
This technique has been well discussed in the academic literature,
e.g. [1,2], although since I am not aware of any existing
implementation, I made my own, intended as an explanatory aid:
https://github.com/amiller/redblackmerkle/blob/master/redblack.py
[1] Certificate Revocation and Update
Naor and Nissim. 1998
http://static.usenix.org/publications/library/proceedings/sec98/full_papers/nissim/nissim.pdf
[2] A General Model for Authenticated Data Structures
Martel, Nuckolls, Devanbu, Michael Gertz, Kwong, Stubblebine. 2004
http://truthsayer.cs.ucdavis.edu/algorithmica.pdf
--
Andrew Miller