tag:blogger.com,1999:blog-6422447884695587452024-03-05T13:53:24.578+02:00Garden Path Trajectory Algorithms, Math Education, and the Art of Doing the Dishes Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.comBlogger24125tag:blogger.com,1999:blog-642244788469558745.post-53047571455510795202022-12-30T09:47:00.004+02:002022-12-30T16:17:39.570+02:00McHeron Algorithm for Square Root<h2 dir="ltr" style="text-align: left;">Heron</h2><p dir="ltr" style="text-align: left;">Famously, <a href="https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Heron's_method">Heron's method</a> of computing the square root of a some number x goes like this:</p><p dir="ltr" style="text-align: left;">1. Guess the root, we'll denote the guess by g</p><p dir="ltr" style="text-align: left;">2. Compute the quotient q = x/g</p><p dir="ltr" style="text-align: left;">3. Update your next guess to be the arithmetic mean of q and g. So g := (x/g + g)/2</p><p dir="ltr" style="text-align: left;">4. Goto 2</p><p dir="ltr" style="text-align: left;">This can be viewed as a special case of the <a href="https://en.wikipedia.org/wiki/Newton%27s_method">Newton–Raphson method</a>, and indeed the results become very accurate very fast.</p><h2 dir="ltr" style="text-align: left;">Mckay</h2><div dir="ltr" style="text-align: left;">Somewhat less famous is the anecdote about Mckay's theorem.</div><div dir="ltr" style="text-align: left;">In <a href="https://pubs.nctm.org/view/journals/mt/66/3/article-p229.xml">this paper</a> by Laurence Sherzer, the author tells the story of an 8th grader (in 1973) named Robert Mckay, who suggests a way to find a number that lies between two fractions. Suppose the fractions are a/b and c/d, Mckay's suggestion is to use (a+c)/(b+d).</div><div dir="ltr" style="text-align: left;">This is a mathematical education paper, so it's focus is about how the class and the teacher approached the seemingly weird idea of adding numerators and denominators, and how they explained to themselves why this seems to 'magically' work.</div><div dir="ltr" style="text-align: left;">The short version of the explanation is: this amounts to taking a weighted average of the two fractions, where the weights are the denominators. When the denominators are equal, this is exactly the arithmetic mean. When they differ by a lot - the result is much closer to the fraction with the larger denominator.</div><div dir="ltr" style="text-align: left;"><br /></div><h2 dir="ltr" style="text-align: left;">McHeron?</h2><div dir="ltr" style="text-align: left;">Since taking the mean of two roots, in Heron's method, is annoying at times, why not use Mckay's very simple method instead, dubbing it the <b>McHeron Algorithm</b>?<br />Mathematically, it will give an increasingly better guess in each round, even though it may not be the arithmetic mean.</div><div dir="ltr" style="text-align: left;">How would that look?</div><div dir="ltr" style="text-align: left;">Suppose we want to compute the square root of 2:</div><div dir="ltr" style="text-align: left;">1. Our first guess is 3/2</div><div dir="ltr" style="text-align: left;">2. The quotient is 2/(3/2) which is 4/3 ('just invert and multiply' as they say)</div><div dir="ltr" style="text-align: left;">3. Our next guess needs to be between 3/2 and 4/3, so we use Mckay's method to get 7/5</div><div dir="ltr" style="text-align: left;">4. Our next guess is therefore 7/5</div><div dir="ltr" style="text-align: left;">5. The next quotient is 2/(7/5) which is just 2*5/7 = 10/7</div><div dir="ltr" style="text-align: left;">6. Using Mckay's theorem - our next guess will be (7+10)/(5+7) = 17/12</div><div dir="ltr" style="text-align: left;">7. The next quotient is 2/(17/12) which is just 2*12/17 = 24/17</div><div dir="ltr" style="text-align: left;">8. Using Mckay's - (17+24)/(12+17) = 41/29</div><div dir="ltr" style="text-align: left;"><br /></div><div dir="ltr" style="text-align: left;">And indeed 41/29 = 1.41379...</div><div dir="ltr" style="text-align: left;">Which is approximates the square root of 2 up to 2 decimal points, which is not bad.</div><div dir="ltr" style="text-align: left;"><br /></div><div dir="ltr" style="text-align: left;">Cool, isn't it?</div><div dir="ltr" style="text-align: left;"><br /></div><h2 dir="ltr" style="text-align: left;">But of course, life is never quite so simple</h2><div dir="ltr" style="text-align: left;">I specifically chose a nice example where the algorithm converges relatively fast.</div><div dir="ltr" style="text-align: left;">Had I chosen 715 (whose square root is 26.7394...) as the initial number, it would have taken me a 100 iterations of the algorithm just to get to <span style="background-color: white; color: black; font-size: 14px; white-space: pre-wrap;">26.76... and I will be dealing with denominators with 145 digits by then.</span></div><div dir="ltr" style="text-align: left;"><span style="background-color: white; color: black; font-size: 14px; white-space: pre-wrap;">Why would the algorithm perform so bad?</span></div><div dir="ltr" style="text-align: left;"><span style="background-color: white; color: black; font-size: 14px; white-space: pre-wrap;">Well, remember how Mckay's method introduces a bias for large denominators? The algorithm above scales the quotient's denominator by the the input number, so the larger the input number, the greater the bias toward the quotient will be in the 'Mckay' step of the calculation.</span></div><div dir="ltr" style="text-align: left;"><span style="background-color: white; color: black; font-size: 14px; white-space: pre-wrap;"><br /></span></div><div dir="ltr" style="text-align: left;"><span style="background-color: white;"><span style="color: black;"><span style="font-size: 14px; white-space: pre-wrap;">Heron's algorithm has quadratic convergence (which is amazing), and I don't think showing exactly how bad the convergence of the McHeron algorithm is difficult (I suspect that asymptotically, to get decent results, you'll have to run it as many iterations as the magnitude of the result, so O(2^(n/2)) for an input with n bits, which is terrible), but I should go shopping for the weekend.</span></span></span></div><div dir="ltr" style="text-align: left;"><span style="background-color: white;"><span style="color: black;"><span style="font-size: 14px; white-space: pre-wrap;"><br /></span></span></span></div><h2 dir="ltr" style="text-align: left;">Silver Lining </h2><div dir="ltr" style="text-align: left;">For small numbers (with small denominators) this works nicely for the same reasons, because Mckay's method gives a decent approximation of the arithmetic mean.</div><div dir="ltr" style="text-align: left;"><br /></div><div dir="ltr" style="text-align: left;">That's all, would love to hear thoughts in the comments, or links if you saw this exact method somewhere else, I haven't (and for a good reason, it yields terrible results in most cases).</div><div dir="ltr" style="text-align: left;"><br /></div><div dir="ltr" style="text-align: left;"><h2 dir="ltr">Update: a Twitter Tweak</h2><div>The user <a class="css-4rbku5 css-18t94o4 css-1dbjc4n r-1loqt21 r-1wbh5a2 r-dnmrzs r-1ny4l3l" href="https://twitter.com/k_yaakov" role="link" style="-webkit-box-align: stretch; -webkit-box-direction: normal; -webkit-box-orient: vertical; align-items: stretch; background-color: black; border: 0px solid black; box-sizing: border-box; cursor: pointer; display: inline; flex-basis: auto; flex-direction: column; flex-shrink: 1; font-size: 15px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; list-style: none; margin: 0px; max-width: 100%; min-height: 0px; min-width: 0px; outline-style: none; padding: 0px; position: relative; text-decoration-line: none; z-index: 0;" tabindex="-1"><div class="css-901oao css-1hf3ou5 r-1bwzh9t r-18u37iz r-37j5jr r-a023e6 r-16dba41 r-rjixqe r-bcqeeo r-qvutc0" dir="ltr" style="-webkit-box-direction: normal; -webkit-box-orient: horizontal; border: 0px solid black; box-sizing: border-box; color: #71767b; display: inline; flex-direction: row; font-family: TwitterChirp, -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, Helvetica, Arial, sans-serif; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: 20px; margin: 0px; max-width: 100%; min-width: 0px; overflow-wrap: break-word; overflow: hidden; padding: 0px; text-overflow: ellipsis; white-space: nowrap;"><span class="css-901oao css-16my406 r-poiln3 r-bcqeeo r-qvutc0" color="inherit" style="border: 0px solid black; box-sizing: border-box; display: inline; font: inherit; margin: 0px; min-width: 0px; overflow-wrap: break-word; padding: 0px; white-space: inherit;">@k_yaakov</span></div></a> suggested <a href="https://twitter.com/k_yaakov/status/1608792221196906496">on Twitter</a> to bring the denominators to roughly the same scale through multiplying by the appropriate power of 10. Since determining the correct power of 10 and multiplying by it can be done by counting the number of digits and adding zeros respectively, this is very easy to do in practice. The consequence is that the bias introduced by Mckay's weighted mean is now bounded by 1/10, rendering a significantly better convergence rate.<br />Taking the adversarial example of 715 from before: getting a 2 decimal points precision now requires only <b>17 </b>iterations, compared to <b>over 100</b> iterations in the previous version of McHeron. <b>Very nice!</b></div><div><br /></div></div>Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-42650212214503820862022-01-31T22:39:00.001+02:002022-01-31T22:39:29.018+02:003 Golden Rules<blockquote dir="ltr" style="text-align: left;"><p style="text-align: left;"><i>"Just as I cannot step in the same river twice, <span style="text-align: right;"> the person who created this bug and I are two separate beings in the fabric of the universe. Therefore, I will also not be the one who fixes it."</span></i></p></blockquote><p dir="ltr" style="text-align: left;"><i> <span> </span><span> </span><span style="text-align: right;">Heraclitus of Ephesus, a programmer</span></i></p><p dir="ltr" style="text-align: left;"><span style="text-align: right;"><br /></span></p><p dir="ltr" style="text-align: left;"><span style="text-align: right;">I don't like code manifests.</span></p><p dir="ltr" style="text-align: left;"><a href="https://rinaarts.com/">Rina Artstain</a> once <a href="https://twitter.com/rinaarts/status/1192782835700113408">tweeted</a> that we only think we know certain things about parenting because as luck would have it, we haven't had a child to whom all of them don't apply.<br />That's how I feel about code manifests.</p><p dir="ltr" style="text-align: left;">However, I do have a manifest of my own, short though it may be, so I want to frame it differently. What follows are not the three rules I think everyone should follow to get a "cleaner" code or some other metric of goodness. Rather, these are three things I like when I see in other people's code and annoy me when I see blatantly disregarded. </p><p dir="ltr" style="text-align: left;">Here we go.</p><h2 dir="ltr" style="text-align: left;">1.</h2><p style="text-align: right;"></p><blockquote><p style="text-align: right;"><i>"לֹא עָלֶיךָ הַמְּלָאכָה לִגְמוֹר, וְלֹא אַתָּה בֶן חוֹרִין לִבָּטֵל מִמֶּנָּה."</i></p><p style="text-align: right;"><i>פרקי אבות, ב' טז'</i></p></blockquote><p style="text-align: right;"></p><p dir="ltr" style="text-align: left;"></p><blockquote><p dir="ltr" style="text-align: left;"><i>"It is not incumbent upon you to finish the task, but neither are you free to absolve yourself from it."</i></p><p dir="ltr" style="text-align: left;"><i>Pirkei Avot 2:16</i></p></blockquote><p dir="ltr" style="text-align: left;"></p><p dir="ltr" style="text-align: left;">This is one of the greatest quotes I know and it sounds so much better in Hebrew.</p><p dir="ltr" style="text-align: left;"><br /></p><h2 dir="ltr" style="text-align: left;">2.</h2><p dir="ltr" style="text-align: left;"></p><blockquote><p dir="ltr" style="text-align: left;"><i>"Entities should not be multiplied beyond necessity."</i></p><p dir="ltr" style="text-align: left;"><i>William of Ockham</i></p></blockquote><p dir="ltr" style="text-align: left;"></p><p dir="ltr" style="text-align: left;">Yes, this is the OG Ockham's razor. How amazing it is that a Franciscan friar who lived 700 years ago foresaw the harms of overusing OOP and polymorphism.</p><p dir="ltr" style="text-align: left;"><br /></p><h2 dir="ltr" style="text-align: left;">3.</h2><p dir="ltr" style="text-align: left;"></p><blockquote><p dir="ltr" style="text-align: left;"><i>"Writing good code is superior to writing bad code.<br />Deleting code is superior to writing good code.<br />Superior to all is concluding that some code does not have to be written at all."</i></p><p dir="ltr" style="text-align: left;"><i>Confucius</i></p></blockquote><p dir="ltr" style="text-align: left;"></p><p dir="ltr" style="text-align: left;">Well, not Confucius, but if one wants people to listen, one should attribute their thoughts to someone famous, preferably dead.</p><p dir="ltr" style="text-align: left;">I'm pretty sure Oscar Wilde said that one. </p><div class="separator" style="clear: both; text-align: center;"><a href="https://i.imgur.com/9IvAT.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="363" data-original-width="500" height="363" src="https://i.imgur.com/9IvAT.jpg" width="500" /></a></div><br /><p dir="ltr" style="text-align: left;"><br /></p><div style="text-align: left;"><br /></div>Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-43380746198932495882020-06-23T09:29:00.004+03:002020-06-23T09:29:48.677+03:00Math Shmath - My Podcast<div dir="rtl" style="text-align: right;" trbidi="on">
<div dir="ltr" style="text-align: left;">
During the first COVID-19 days, I had a couple of weeks hiatus between two jobs, which I used to create a popular-math podcast in Hebrew I call "Math Shmath".</div>
<div dir="ltr" style="text-align: left;">
There are only 5 episodes so far, but I hope to get some more in the future.</div>
<div dir="ltr" style="text-align: left;">
The intended audience is people with no formal math background, but through a listeners survey I found that about half of the responders had at least undergraduate level studies in math or sciences.</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: center;">
<img alt="מתמטיקה שמתמטיקה" height="200" src="https://is3-ssl.mzstatic.com/image/thumb/Podcasts123/v4/dd/e6/43/dde643c3-b16d-05a8-a497-f074118f38ef/mza_8238392306408205046.png/600x600bb.jpg" width="200" /></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
The podcast had over 5k downloads so far, and if you are a Hebrew speaker, I suggest you give it a try. It is available on <a href="https://podcasts.apple.com/podcast/id1503017924?ct=podlink&mt=2&app=podcast&ls=1">iTunes</a>, <a href="https://open.spotify.com/show/5sqsuP6caLfJGiLPFyg78k">Spotify</a>, and all the usual places, and I'm told kid with math tendencies at ages 10-15 like it.</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<a href="https://pod.link/1503017924/episode/c2hpcnBlbGVkLnBvZGJlYW4uY29tLzk0MTJlYjA0LWE2ZWQtNWY3Yi1hYTBmLTkyMGU3YzMyYjQxMg==">Episode #1: Zero</a></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<a href="https://pod.link/1503017924/episode/c2hpcnBlbGVkLnBvZGJlYW4uY29tLzQwZTdlYjg5LTM5YzUtNTMzZC04NGZhLWZjNDk1MzkyMjUxMQ==">Episode #2: Combinations</a></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<a href="https://pod.link/1503017924/episode/c2hpcnBlbGVkLnBvZGJlYW4uY29tLzM2ODVjY2I0LWU0ZmQtNTNmNy1iNjkxLTUyMTllOGJlMmM2ZQ==">Episode #3: The Problem With Percentage</a></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<a href="https://pod.link/1503017924/episode/c2hpcnBlbGVkLnBvZGJlYW4uY29tL2RkZGVjZDFmLTIxZTktNWIxMC1hYTQ5LTliMzcyYzIyYWUxMQ==">Episode #4: Algorithms</a></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<a href="https://pod.link/1503017924/episode/c2hpcnBlbGVkLnBvZGJlYW4uY29tL2NjYzFjNDcyLTZmMDMtNTA3Yi04Yjc5LTUyMzE2YTZhYzM0MQ==">Episode #5: An Unfinished Game</a></div>
</div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com1tag:blogger.com,1999:blog-642244788469558745.post-21906421862796301862019-10-26T20:22:00.002+03:002019-10-26T20:22:22.944+03:00Zero Knowledge Proofs Via A Toy Example: An Overdue Video<div dir="rtl" style="text-align: right;" trbidi="on">
<div dir="ltr" style="text-align: left;">
I wrote a hands-on tutorial for Zero-Knowledge proofs more than a year ago on this blog (in four parts: <a href="https://www.shirpeled.com/2018/09/a-hands-on-tutorial-for-zero-knowledge.html">I</a>, <a href="https://www.shirpeled.com/2018/10/a-hands-on-tutorial-for-zero-knowledge.html">II</a>, <a href="https://www.shirpeled.com/2018/10/a-hands-on-tutorial-for-zero-knowledge_2.html">III </a>and <a href="https://www.shirpeled.com/2018/10/a-hands-on-tutorial-for-zero-knowledge_4.html">IV</a>).</div>
<div dir="ltr" style="text-align: left;">
It subsequently turned into a talk at the fifth <a href="https://www.meetup.com/Algorithms-Israel/events/255587067/">Algorithms IL meetup</a>, and it was videoed.</div>
<div dir="ltr" style="text-align: left;">
So here's the video, courtesy of the Algorithms IL team, and Tzipi Zanyovka from Waze, which hosted the event.</div>
<div class="separator" style="clear: both; text-align: center;">
<iframe width="320" height="266" class="YOUTUBE-iframe-video" data-thumbnail-src="https://i.ytimg.com/vi/eVMOUMvWB44/0.jpg" src="https://www.youtube.com/embed/eVMOUMvWB44?feature=player_embedded" frameborder="0" allowfullscreen></iframe></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
</div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-69931252938507829642018-10-04T23:25:00.001+03:002018-10-05T08:49:13.033+03:00 A Hands-On Tutorial for Zero-Knowledge Proofs: Appendix<div dir="rtl" style="text-align: right;" trbidi="on">
<div dir="ltr" style="text-align: left;">
This is the final part of this hands-on tutorial. I will assume from now on that you have read <a href="http://www.shirpeled.com/2018/09/a-hands-on-tutorial-for-zero-knowledge.html">Part I</a>, <a href="http://www.shirpeled.com/2018/10/a-hands-on-tutorial-for-zero-knowledge.html">Part II</a>, and <a href="http://www.shirpeled.com/2018/10/a-hands-on-tutorial-for-zero-knowledge_2.html">Part III</a> of this series.<br />
<br />
As promised, this post will deal with:<br />
<br />
<ol style="text-align: left;">
<li>Some tweaks to the protocol presented in the previous posts.</li>
<li>A complexity analysis of the protocol,</li>
<li>A small optimization.</li>
<li>A few words about modern ZK proving protocols</li>
</ol>
</div>
<div dir="ltr" style="text-align: left;">
<br />
<br /></div>
<h3 dir="ltr" style="text-align: left;">
Lior's Tweaks</h3>
<div dir="ltr" style="text-align: left;">
<br />
A colleague at <a href="https://www.starkware.co/">Starkware</a>, Lior Goldberg, pointed out a caveat in the zero-knowledge aspect, and suggested a nice simplification of the protocol, here they are:<br />
<br />
<h4 style="text-align: left;">
A ZK Fix</h4>
<div>
<br /></div>
Suppose the first two numbers in the problem instance are 5 and 6, and that the random shift $r$ is chosen from the range $0..10$.<br />
Now if the random query $i$ happens to be $1$, then the prover is required to reveal the second and third elements in the witness. If they happen to be 15 and 21, then the verifier knows immediately that 5 and 6 (from the problem instance) belong to the <b>same side </b>in the solution. This violates the zero knowledge property that we wanted.<br />
This happened because we chose uniformly at random from a very small range, and $r$ happened to be the maximal number in that range.<br />
<br /></div>
<div dir="ltr" style="text-align: left;">
There are two ways to solve this. One is by chosing some arbitrary number and doing all computations modulo that number. A simpler way would be chosing $r$ from a huge domain, such as $0..2^{100}$, which makes the probability of getting a revealing $r$ negligible.<br />
<br />
<br />
<h4 style="text-align: left;">
Simplify By Having A Cyclic List</h4>
<div>
<br /></div>
<div>
Our witness originally had $n + 1$ elements such that the first was a random number, and the rest were partial sums of the problem and the assignment dot product (plus the initial random number).</div>
<div>
This meant we had two types of queries, one to check that two consecutive elements in the list differ in absolute value by the corresponding element in the problem list. Another type of query just checked that the first and last element are equal.</div>
<div>
<br /></div>
<div>
As Lior pointed out, it is much more elegant to omit the last element from the witness entirely, and if $i = n$ - check that the first and last elements in the witness differ, in absolute value, by the last element in the problem instance. Essentially, this is like thinking of the witness as cyclic. The nice thing about this is that now we only have one type of queries - a query about the difference between two consecutive elements <b>modulo n </b>in the witness.</div>
<div>
</div>
<div>
<br />
<br /></div>
<h3 style="text-align: left;">
Proof Size / Communication Complexity</h3>
<div>
<br /></div>
<div>
We'd like to analyze the size of the proof that our code generates. This often referred to as <i>communication complexity,</i> because the Fiat-Shamir Heuristic (that was described in <a href="https://www.shirpeled.com/2018/10/a-hands-on-tutorial-for-zero-knowledge_2.html">Part III</a>) transforms messages (from an interactive protocol) to a proof, making these two terms interchangeable in this context.</div>
<div>
<br /></div>
<div>
So, for each query, the proof stores:</div>
<div>
<ul style="text-align: left;">
<li>The value of i.</li>
<li>The value of the $i$-th element in the witness and the $(i \mod n)$-th element.</li>
<li>Authentication paths for both elements.</li>
</ul>
</div>
<div>
The authentication paths here are the heavy part. Each of them is a $\log(n)$-element long list of 256bit values.</div>
<div>
As was discussed in the last post, to get a decent soundness, the number of queries has to be roughly $100n$. </div>
<div>
Putting these two together, the proof size will be dominated by the $~200 \cdot n \cdot \log(n)$ hashes that form the authentication paths.</div>
<div>
So a proof that one knows an assignment to a Partition Problem instance with 1000 numbers, will require roughly $2,000,000$ hashes, which translate to 64 Megabytes of data.<br />
<br /></div>
<br />
<h3 style="text-align: left;">
Small Merkle Optimization</h3>
<div>
<br /></div>
<div>
Since merkle authentication paths, somewhat surprisingly, make up the vast majority of the proof, maybe we can reduce their number by a little.</div>
<div>
<br /></div>
<div>
Note that all queries (except for one) ask about consecutive leaves in the tree. </div>
<div>
Consecutive leaves share, on average, have their LCA (least common ancestor) at height $\frac {\log n} {2}$. Up to the LCA, their authentication paths may differ, but from the LCA up to the root, they're authentication paths are identical, so we're wasting space writing both in the proof.</div>
<div>
Omitting the path from the LCA to the root from one of them will bring the proof size down to $150 \cdot n \cdot \log (n)$, which is a nice 25% improvement.</div>
<div>
<br /></div>
<div>
Implementing this optimization, as well as Lior's tweaks, is left - as they say in textbooks - as an exercise for the reader.</div>
<div>
<br />
<br /></div>
<h3 style="text-align: left;">
Modern Protocols</h3>
<div>
<br /></div>
<div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://www.eltemps.cat/imatges/articles/charles-chaplin-tiempos-modernos.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="619" data-original-width="800" height="247" src="https://www.eltemps.cat/imatges/articles/charles-chaplin-tiempos-modernos.jpeg" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<br /></div>
<div>
<br />
Modern ZK proving protocols, such as ZK-SNARKS, ZK-STARKS, Bulletproof, Ligero, Aurora, and others, are often compared along these four axes:</div>
<div>
<br /></div>
<div>
<ul style="text-align: left;">
<li>What type of statements can be proved using the protocol.</li>
<li>How much space the proof takes up.</li>
<li>How long it takes to create a proof.</li>
<li>How long it takes to verify a proof.</li>
</ul>
<div>
Often the topic of trusted setup is discussed, but we won't get into that here.<br />
<br /></div>
</div>
<div>
Let's see how our toy-protocol fares:</div>
<div>
<br /></div>
<h4 style="text-align: left;">
Which statements can be proved?</h4>
<div>
<br /></div>
<div>
In the toy-protocol, only knowledge of a solution to a Partition Problem instance could be proved. In contrast with most protocols, where one can use the protocol to prove knowledge of an input that satisfies some arbitrary arithmetic circuit, or even that a specific program ran for $T$ steps, and provided a specified output (this is what ZK-STARKS do).<br />
Well, you may say, if you can prove one NP-complete problem (and the Partition Problem is one) - you can prove them all, due to polynomial time reductions. And theoretically speaking you would be right. However, in the practical world of ZK-proofs, all these manipulations have costs of their own, and conversions often incur a blow-up of the problem, since "polynomial reduction" is a theoretical term that can translate to non-practical cost. For this reasons, modern protocols make an effort to take as input more expressive forms (such as arithmetic circuits and statements about computer programs).</div>
<div>
<br /></div>
<h4 style="text-align: left;">
Space</h4>
<div>
<br /></div>
<div>
As the analysis showed, our proof takes up $O(n \log (n))$ space, whereas in most modern protocols, the proof size is somewhere between constant and polylogarithmic in $n$ (e.g. $O(\log ^2 (n))$).<br />
This <b>huge</b> gap is what this makes the proposed protocol nothing more than a toy example, that - while demonstrating certain approaches and tricks - is useless for any real application.<br />
You can trace this gap to the fact we need a <b>linear number of queries</b>, each costing a logarithmic number of hashes (the Merkle authentication paths).<br />
The approach I took was inspired by tricks from the ZK-STARK protocol, that is slightly more expensive than others in terms of proof size, but is expressive, requires relatively short prover time, and very short verifier time. In STARK, indeed the lion share of the proof is comprised of Merkle authentication paths, but great care is taken so that the number of queries will be minuscule. </div>
<div>
<br /></div>
<h4 style="text-align: left;">
Prover Running Time</h4>
<div>
<br /></div>
<div>
In our protocol it is roughly $O(n \log (n))$, which is not far from modern protocols.</div>
<div>
<br /></div>
<div>
<br /></div>
<h4 style="text-align: left;">
Verifier Running Time</h4>
<div>
<br /></div>
<div>
In our protocol it is linear in the proof size, so $O(n \log n)$ which is not so good. Recall that, at least in the context of blockchains, a proof is written once but verified many times (by miners for example). Modern protocols thus strive to make the verifier workload as small as they possibly can without impeding soundness.</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://vignette.wikia.nocookie.net/looneytunes/images/e/e1/All.jpg/revision/latest?cb=20150313020828" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="500" data-original-width="800" height="200" src="https://vignette.wikia.nocookie.net/looneytunes/images/e/e1/All.jpg/revision/latest?cb=20150313020828" width="320" /></a></div>
<h3 style="text-align: left;">
</h3>
<div>
<br /></div>
<div>
This concludes what I hoped to cover in this tutorial. It was fun to write and code. Let's do it again sometime. :)</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
</div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-48470985405085811692018-10-02T23:04:00.001+03:002018-10-04T22:29:17.451+03:00 A Hands-On Tutorial for Zero-Knowledge Proofs: Part III<div dir="rtl" style="text-align: right;" trbidi="on">
<h3 dir="ltr" style="text-align: left;">
A Zero Knowledge Merkle Tree</h3>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
In <a href="http://www.shirpeled.com/2018/10/a-hands-on-tutorial-for-zero-knowledge.html">the second post</a> in this series, I presented the very neat concept of a Merkle Tree, but we ended with the problem that in its standard implementation - while being a powerful commitment scheme - a Merkle Tree is not zero knowledge.</div>
<div dir="ltr" style="text-align: left;">
As it turns out, this is very easy to fix by adding another level to the tree, such that in it, every pair of siblings is comprised of one node associated with actual data, and the other with a random string.</div>
<div dir="ltr" style="text-align: left;">
This is again the notion of mixing real data with randomness in order to obtain zero knowledge.<br />
<br /></div>
<div dir="ltr" style="text-align: left;">
Here's how this will look with our "Yes Sir I Can Boogie" data:</div>
<div class="separator" dir="ltr" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhLgYyuHdsSlZTU4nYsH1TF4KVC6f9Z9bJVl7IQSCOagLmLYeHsEmoXXW7NSfic0EqquJ4ILQaGqBKoaX70YEYFOLbxj1HxjF4WhNJ5MnJ7QR_oo8lKBA1wsX0k-BZkf9kYhw8bmGd1mEdC/s1600/Selection_071.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="793" data-original-width="1482" height="342" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhLgYyuHdsSlZTU4nYsH1TF4KVC6f9Z9bJVl7IQSCOagLmLYeHsEmoXXW7NSfic0EqquJ4ILQaGqBKoaX70YEYFOLbxj1HxjF4WhNJ5MnJ7QR_oo8lKBA1wsX0k-BZkf9kYhw8bmGd1mEdC/s640/Selection_071.png" width="640" /></a></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<br />
This has the desired effect because whenever the prover has to reveal an authentication path for a piece of data - all the hashes revealed are affected by random data, and having been mixed through the Sha256 hash - these hashes appear random, and provide zero knowledge (other than the revelaed leaf node).</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<h3 dir="ltr" style="text-align: left;">
Fixing The Code:</h3>
<div dir="ltr" style="text-align: left;">
Tweaking the MerkleTree class from last time, we get:</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<pre style="background: rgb(255, 255, 255);"><span style="color: maroon; font-weight: bold;">class</span> ZkMerkleTree<span style="color: #808030;">:</span>
<span style="color: dimgrey;">"""</span>
<span style="color: dimgrey;"> A Zero Knowledge Merkle tree implementation using SHA256</span>
<span style="color: dimgrey;"> """</span>
<span style="color: maroon; font-weight: bold;">def</span> <span style="color: #074726;">__init__</span><span style="color: #808030;">(</span>self<span style="color: #808030;">,</span> data<span style="color: #808030;">)</span><span style="color: #808030;">:</span>
self<span style="color: #808030;">.</span>data <span style="color: #808030;">=</span> data
next_pow_of_2 <span style="color: #808030;">=</span> <span style="color: #400000;">int</span><span style="color: #808030;">(</span><span style="color: #008c00;">2</span><span style="color: #44aadd;">**</span>ceil<span style="color: #808030;">(</span>log2<span style="color: #808030;">(</span><span style="color: #400000;">len</span><span style="color: #808030;">(</span>data<span style="color: #808030;">)</span><span style="color: #808030;">)</span><span style="color: #808030;">)</span><span style="color: #808030;">)</span>
self<span style="color: #808030;">.</span>data<span style="color: #808030;">.</span>extend<span style="color: #808030;">(</span><span style="color: #808030;">[</span><span style="color: #008c00;">0</span><span style="color: #808030;">]</span> <span style="color: #44aadd;">*</span> <span style="color: #808030;">(</span>next_pow_of_2 <span style="color: #44aadd;">-</span> <span style="color: #400000;">len</span><span style="color: #808030;">(</span>data<span style="color: #808030;">)</span><span style="color: #808030;">)</span><span style="color: #808030;">)</span>
<span style="color: dimgrey;"># Intertwine with randomness to obtain zero knowledge.</span>
rand_list <span style="color: #808030;">=</span> <span style="color: #808030;">[</span>random<span style="color: #808030;">.</span>randint<span style="color: #808030;">(</span><span style="color: #008c00;">0</span><span style="color: #808030;">,</span> <span style="color: #008c00;">1</span> <span style="color: #44aadd;"><<</span> <span style="color: #008c00;">32</span><span style="color: #808030;">)</span> <span style="color: maroon; font-weight: bold;">for</span> x <span style="color: maroon; font-weight: bold;">in</span> self<span style="color: #808030;">.</span>data<span style="color: #808030;">]</span>
self<span style="color: #808030;">.</span>data <span style="color: #808030;">=</span> <span style="color: #808030;">[</span>x <span style="color: maroon; font-weight: bold;">for</span> tup <span style="color: maroon; font-weight: bold;">in</span> <span style="color: #400000;">zip</span><span style="color: #808030;">(</span>self<span style="color: #808030;">.</span>data<span style="color: #808030;">,</span> rand_list<span style="color: #808030;">)</span> <span style="color: maroon; font-weight: bold;">for</span> x <span style="color: maroon; font-weight: bold;">in</span> tup<span style="color: #808030;">]</span>
<span style="color: dimgrey;"># Create bottom level of the tree (i.e. leaves).</span>
self<span style="color: #808030;">.</span>tree <span style="color: #808030;">=</span> <span style="color: #808030;">[</span><span style="color: #0000e6;">""</span> <span style="color: maroon; font-weight: bold;">for</span> x <span style="color: maroon; font-weight: bold;">in</span> self<span style="color: #808030;">.</span>data<span style="color: #808030;">]</span> <span style="color: #44aadd;">+</span> \
<span style="color: #808030;">[</span>hash_string<span style="color: #808030;">(</span><span style="color: #400000;">str</span><span style="color: #808030;">(</span>x<span style="color: #808030;">)</span><span style="color: #808030;">)</span> <span style="color: maroon; font-weight: bold;">for</span> x <span style="color: maroon; font-weight: bold;">in</span> self<span style="color: #808030;">.</span>data<span style="color: #808030;">]</span>
<span style="color: maroon; font-weight: bold;">for</span> i <span style="color: maroon; font-weight: bold;">in</span> <span style="color: #400000;">range</span><span style="color: #808030;">(</span><span style="color: #400000;">len</span><span style="color: #808030;">(</span>self<span style="color: #808030;">.</span>data<span style="color: #808030;">)</span> <span style="color: #44aadd;">-</span> <span style="color: #008c00;">1</span><span style="color: #808030;">,</span> <span style="color: #008c00;">0</span><span style="color: #808030;">,</span> <span style="color: #44aadd;">-</span><span style="color: #008c00;">1</span><span style="color: #808030;">)</span><span style="color: #808030;">:</span>
self<span style="color: #808030;">.</span>tree<span style="color: #808030;">[</span>i<span style="color: #808030;">]</span> <span style="color: #808030;">=</span> hash_string<span style="color: #808030;">(</span>self<span style="color: #808030;">.</span>tree<span style="color: #808030;">[</span>i <span style="color: #44aadd;">*</span> <span style="color: #008c00;">2</span><span style="color: #808030;">]</span> <span style="color: #44aadd;">+</span> self<span style="color: #808030;">.</span>tree<span style="color: #808030;">[</span>i <span style="color: #44aadd;">*</span> <span style="color: #008c00;">2</span> <span style="color: #44aadd;">+</span> <span style="color: #008c00;">1</span><span style="color: #808030;">]</span><span style="color: #808030;">)</span>
<span style="color: maroon; font-weight: bold;">def</span> get_root<span style="color: #808030;">(</span>self<span style="color: #808030;">)</span><span style="color: #808030;">:</span>
<span style="color: maroon; font-weight: bold;">return</span> self<span style="color: #808030;">.</span>tree<span style="color: #808030;">[</span><span style="color: #008c00;">1</span><span style="color: #808030;">]</span>
<span style="color: maroon; font-weight: bold;">def</span> get_val_and_path<span style="color: #808030;">(</span>self<span style="color: #808030;">,</span> <span style="color: #400000;">id</span><span style="color: #808030;">)</span><span style="color: #808030;">:</span>
<span style="color: dimgrey;"># Because of the zk padding, the data is now at id * 2</span>
<span style="color: #400000;">id</span> <span style="color: #808030;">=</span> <span style="color: #400000;">id</span> <span style="color: #44aadd;">*</span> <span style="color: #008c00;">2</span>
val <span style="color: #808030;">=</span> self<span style="color: #808030;">.</span>data<span style="color: #808030;">[</span><span style="color: #400000;">id</span><span style="color: #808030;">]</span>
auth_path <span style="color: #808030;">=</span> <span style="color: #808030;">[</span><span style="color: #808030;">]</span>
<span style="color: #400000;">id</span> <span style="color: #808030;">=</span> <span style="color: #400000;">id</span> <span style="color: #44aadd;">+</span> <span style="color: #400000;">len</span><span style="color: #808030;">(</span>self<span style="color: #808030;">.</span>data<span style="color: #808030;">)</span>
<span style="color: maroon; font-weight: bold;">while</span> <span style="color: #400000;">id</span> <span style="color: #44aadd;">></span> <span style="color: #008c00;">1</span><span style="color: #808030;">:</span>
auth_path <span style="color: #44aadd;">+</span><span style="color: #808030;">=</span> <span style="color: #808030;">[</span>self<span style="color: #808030;">.</span>tree<span style="color: #808030;">[</span><span style="color: #400000;">id</span> <span style="color: #44aadd;">^</span> <span style="color: #008c00;">1</span><span style="color: #808030;">]</span><span style="color: #808030;">]</span>
<span style="color: #400000;">id</span> <span style="color: #808030;">=</span> <span style="color: #400000;">id</span> <span style="color: #44aadd;">//</span> <span style="color: #008c00;">2</span>
<span style="color: maroon; font-weight: bold;">return</span> val<span style="color: #808030;">,</span> auth_path
<span style="color: maroon; font-weight: bold;">def</span> verify_zk_merkle_path<span style="color: #808030;">(</span>root<span style="color: #808030;">,</span> data_size<span style="color: #808030;">,</span> value_id<span style="color: #808030;">,</span> value<span style="color: #808030;">,</span> path<span style="color: #808030;">)</span><span style="color: #808030;">:</span>
cur <span style="color: #808030;">=</span> hash_string<span style="color: #808030;">(</span><span style="color: #400000;">str</span><span style="color: #808030;">(</span>value<span style="color: #808030;">)</span><span style="color: #808030;">)</span>
<span style="color: dimgrey;"># Due to zk padding, data_size needs to be multiplied by 2, as does the value_id</span>
tree_node_id <span style="color: #808030;">=</span> value_id <span style="color: #44aadd;">*</span> <span style="color: #008c00;">2</span> <span style="color: #44aadd;">+</span> <span style="color: #400000;">int</span><span style="color: #808030;">(</span><span style="color: #008c00;">2</span><span style="color: #44aadd;">**</span>ceil<span style="color: #808030;">(</span>log2<span style="color: #808030;">(</span>data_size <span style="color: #44aadd;">*</span> <span style="color: #008c00;">2</span><span style="color: #808030;">)</span><span style="color: #808030;">)</span><span style="color: #808030;">)</span>
<span style="color: maroon; font-weight: bold;">for</span> sibling <span style="color: maroon; font-weight: bold;">in</span> path<span style="color: #808030;">:</span>
<span style="color: maroon; font-weight: bold;">assert</span> tree_node_id <span style="color: #44aadd;">></span> <span style="color: #008c00;">1</span>
<span style="color: maroon; font-weight: bold;">if</span> tree_node_id <span style="color: #44aadd;">%</span> <span style="color: #008c00;">2</span> <span style="color: #44aadd;">==</span> <span style="color: #008c00;">0</span><span style="color: #808030;">:</span>
cur <span style="color: #808030;">=</span> hash_string<span style="color: #808030;">(</span>cur <span style="color: #44aadd;">+</span> sibling<span style="color: #808030;">)</span>
<span style="color: maroon; font-weight: bold;">else</span><span style="color: #808030;">:</span>
cur <span style="color: #808030;">=</span> hash_string<span style="color: #808030;">(</span>sibling <span style="color: #44aadd;">+</span> cur<span style="color: #808030;">)</span>
tree_node_id <span style="color: #808030;">=</span> tree_node_id <span style="color: #44aadd;">//</span> <span style="color: #008c00;">2</span>
<span style="color: maroon; font-weight: bold;">assert</span> tree_node_id <span style="color: #44aadd;">==</span> <span style="color: #008c00;">1</span>
<span style="color: maroon; font-weight: bold;">return</span> root <span style="color: #44aadd;">==</span> cur</pre>
</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<h3 dir="ltr" style="text-align: left;">
Protocol Summary</h3>
<div dir="ltr" style="text-align: left;">
To summarize the theory, the protocol by which the prover proves knowledge of a satisfying assignment to the Partition Problem is:</div>
<div dir="ltr" style="text-align: left;">
<ol style="text-align: left;">
<li>The prover generates a witness (using get_witness from the <a href="http://www.shirpeled.com/2018/09/a-hands-on-tutorial-for-zero-knowledge.html">first post</a> in this series).</li>
<li>The prover creates a ZK Merkle Tree from the witness, and sends its root-hash to the verifier.</li>
<li>The verifier sends a random number $i$ to the prover.</li>
<li>If $i < n$ then the prover sends to the verifier:</li>
<ol>
<li>The elements in places $i$ and $i + 1$ in the witness.</li>
<li>The authentication paths proving that these answers are consistent with the root sent in step (2).</li>
</ol>
<li>If $i == n$ then the prover sends the first and the last elements in the witness, with the authentication paths etc.</li>
<li>The verifier checks the authentication paths against the root, and the returned numbers against the problem instance, to verify properties (1) and (2) of the witness as they are described in the <a href="http://www.shirpeled.com/2018/09/a-hands-on-tutorial-for-zero-knowledge.html">first post</a>.</li>
<li>The verifier returns true iff everything checks out.</li>
</ol>
<div>
<br /></div>
<h3 style="text-align: left;">
What If The Prover Is Lying?</h3>
<div>
<br /></div>
<div>
Clearly if everything is kosher, the verifier will see that it is (this is called <a href="https://en.wikipedia.org/wiki/Interactive_proof_system">c<i>ompleteness</i></a>).<br />
But what if the prover is dishonest? What is the probability $p$ that the verifier will catch on? (this is called <i><a href="https://en.wikipedia.org/wiki/Interactive_proof_system">soundness</a></i>).<br />
<br />
Suppose the witness is kosher in all but one place, which is clearly the hardest case to catch. This means that in a single query, the verifier has a probability of $\frac 1 {n + 1}$ to expose the prover's deception.</div>
<div>
If we repeat the protocol $k$ times, then the verifier's probability of catching a lying prover grows to $1 - (1 - \frac 1 {n + 1})^k$.</div>
<div>
And if we set $k = 100(n + 1)$ then this is approximately $1 - \frac 1 {e^{100}}$ which is indeed very very very sure.</div>
<div>
To give a sense of how sure that is, the prover's odds of convincing the verifier of a false claim are like odds of flipping a coin and having it land <b>on its edge 12 times in a row</b>.</div>
</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div class="separator" dir="ltr" style="clear: both; text-align: center;">
<a href="https://upload.wikimedia.org/wikipedia/commons/thumb/1/15/Coin_Toss_(3635981474).jpg/800px-Coin_Toss_(3635981474).jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="800" data-original-width="632" height="320" src="https://upload.wikimedia.org/wikipedia/commons/thumb/1/15/Coin_Toss_(3635981474).jpg/800px-Coin_Toss_(3635981474).jpg" width="252" /></a></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<h3 dir="ltr" style="text-align: left;">
Fiat-Shamir Heuristic</h3>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
One must admit that it is somewhat cumbersome to have the prover and the verifier engage in such a long exchange of queries and responses. It means that whenever there's something to prove, both sides need to be available, online, and ready for this ping pong.</div>
<div dir="ltr" style="text-align: left;">
<br />
Luckily, a neat trick by Amos Fiat and Adi Shamir, known as <a href="https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic">Fiat-Shamir Heuristic</a>, allows us to take this protocol, and convert it into a single long proof, that the prover generates once, and that everyone in the world can check afterwards.</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
The heuristic is based on the observation that in many protocols, and specifically in the one described here, the only messages that the verifier ever sends throughout the exchange are random numbers. </div>
<div dir="ltr" style="text-align: left;">
So here's the basic idea:</div>
<div dir="ltr" style="text-align: left;">
<ul style="text-align: left;">
<li>The prover will <b>simulate</b> the verifier's side in the exchange, but will seed the random number generator it uses in a way that is on one hand random "enough", and on the other hand - replicable. </li>
<li>The prover will write down the verifier's queries, and the prover's replies (with the authentication paths and all), one after the other, and documentation of the simulated exchange will be <b>the proof!</b></li>
<li>After the desired number of queries have been simulated - the prover will send this single long proof to the verifier.</li>
<li>On the verifier side - the verifier will simulate the exchange, using the same replicable-randomness mechanism, that will convince the verifier that the queries that the prover asked itself were indeed random.</li>
</ul>
<div>
<br /></div>
<div>
This smells like cheating, I admit. The prover asks itself and answers itself and sends this exchange to the verifier.</div>
<div>
But to our aid comes the fact that hash functions behave, to all cryptographic intents and purposes, as if they were random number generators.</div>
</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
So when the prover needs to simulate the first query - it will feed the problem instance into a hash function, and use that to obtain a random number (e.g. take the hash mod n).</div>
<div dir="ltr" style="text-align: left;">
When the time comes to generate the second query, and all the subsequent queries - the prover will feed the <b>proof that has been written up to that point</b> into the hash function, and use that to obtain a random number.</div>
<div dir="ltr" style="text-align: left;">
Provided that the prover and the verifier agree <b>which</b> hash function they use - this is both random and replicable (since the verifier has the problem instance and the proof, used to seed the randomness) on both sides of the exchange.</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<h3 dir="ltr" style="text-align: left;">
Putting it All Together</h3>
<div dir="ltr" style="text-align: left;">
And here's the code to obtain a proof and to check it:</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<pre style="background: rgb(255, 255, 255);"><pre style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial;"><span style="color: maroon; font-weight: bold;">def</span> get_proof<span style="color: #808030;">(</span>problem<span style="color: #808030;">,</span> assignment<span style="color: #808030;">,</span> num_queries<span style="color: #808030;">)</span><span style="color: #808030;">:</span>
proof <span style="color: #808030;">=</span> <span style="color: #808030;">[</span><span style="color: #808030;">]</span>
randomness_seed <span style="color: #808030;">=</span> problem<span style="color: #808030;">[</span><span style="color: #808030;">:</span><span style="color: #808030;">]</span>
<span style="color: maroon; font-weight: bold;">for</span> i <span style="color: maroon; font-weight: bold;">in</span> <span style="color: #400000;">range</span><span style="color: #808030;">(</span>num_queries<span style="color: #808030;">)</span><span style="color: #808030;">:</span>
witness <span style="color: #808030;">=</span> get_witness<span style="color: #808030;">(</span>problem<span style="color: #808030;">,</span> assignment<span style="color: #808030;">)</span>
tree <span style="color: #808030;">=</span> ZkMerkleTree<span style="color: #808030;">(</span>witness<span style="color: #808030;">)</span>
random<span style="color: #808030;">.</span>seed<span style="color: #808030;">(</span><span style="color: #400000;">str</span><span style="color: #808030;">(</span>randomness_seed<span style="color: #808030;">)</span><span style="color: #808030;">)</span>
query_idx <span style="color: #808030;">=</span> random<span style="color: #808030;">.</span>randint<span style="color: #808030;">(</span><span style="color: #008c00;">0</span><span style="color: #808030;">,</span> <span style="color: #400000;">len</span><span style="color: #808030;">(</span>problem<span style="color: #808030;">)</span><span style="color: #808030;">)</span>
query_and_response <span style="color: #808030;">=</span> <span style="color: #808030;">[</span>tree<span style="color: #808030;">.</span>get_root<span style="color: #808030;">(</span><span style="color: #808030;">)</span><span style="color: #808030;">]</span>
query_and_response <span style="color: #44aadd;">+</span><span style="color: #808030;">=</span> <span style="color: #808030;">[</span>query_idx<span style="color: #808030;">]</span>
query_and_response <span style="color: #44aadd;">+</span><span style="color: #808030;">=</span> tree<span style="color: #808030;">.</span>get_val_and_path<span style="color: #808030;">(</span>query_idx<span style="color: #808030;">)</span>
query_and_response <span style="color: #44aadd;">+</span><span style="color: #808030;">=</span> tree<span style="color: #808030;">.</span>get_val_and_path<span style="color: #808030;">(</span><span style="color: #808030;">(</span>query_idx <span style="color: #44aadd;">+</span> <span style="color: #008c00;">1</span><span style="color: #808030;">)</span> <span style="color: #44aadd;">%</span> <span style="color: #400000;">len</span><span style="color: #808030;">(</span>witness<span style="color: #808030;">)</span><span style="color: #808030;">)</span>
proof <span style="color: #44aadd;">+</span><span style="color: #808030;">=</span> <span style="color: #808030;">[</span>query_and_response<span style="color: #808030;">]</span>
randomness_seed <span style="color: #44aadd;">+</span><span style="color: #808030;">=</span> <span style="color: #808030;">[</span>query_and_response<span style="color: #808030;">]</span>
<span style="color: maroon; font-weight: bold;">return</span> proof
<span style="color: maroon; font-weight: bold;">def</span> verify_proof<span style="color: #808030;">(</span>problem<span style="color: #808030;">,</span> proof<span style="color: #808030;">)</span><span style="color: #808030;">:</span>
proof_checks_out <span style="color: #808030;">=</span> <span style="color: #074726;">True</span>
randomness_seed <span style="color: #808030;">=</span> problem<span style="color: #808030;">[</span><span style="color: #808030;">:</span><span style="color: #808030;">]</span>
<span style="color: maroon; font-weight: bold;">for</span> query <span style="color: maroon; font-weight: bold;">in</span> proof<span style="color: #808030;">:</span>
random<span style="color: #808030;">.</span>seed<span style="color: #808030;">(</span><span style="color: #400000;">str</span><span style="color: #808030;">(</span>randomness_seed<span style="color: #808030;">)</span><span style="color: #808030;">)</span>
query_idx <span style="color: #808030;">=</span> random<span style="color: #808030;">.</span>randint<span style="color: #808030;">(</span><span style="color: #008c00;">0</span><span style="color: #808030;">,</span> <span style="color: #400000;">len</span><span style="color: #808030;">(</span>problem<span style="color: #808030;">)</span><span style="color: #808030;">)</span>
merkle_root <span style="color: #808030;">=</span> query<span style="color: #808030;">[</span><span style="color: #008c00;">0</span><span style="color: #808030;">]</span>
proof_checks_out <span style="color: #44aadd;">&</span><span style="color: #808030;">=</span> query_idx <span style="color: #44aadd;">==</span> query<span style="color: #808030;">[</span><span style="color: #008c00;">1</span><span style="color: #808030;">]</span>
<span style="color: dimgrey;"># Test witness properties.</span>
<span style="color: maroon; font-weight: bold;">if</span> query_idx <span style="color: #44aadd;"><</span> <span style="color: #400000;">len</span><span style="color: #808030;">(</span>problem<span style="color: #808030;">)</span><span style="color: #808030;">:</span>
proof_checks_out <span style="color: #44aadd;">&</span><span style="color: #808030;">=</span> <span style="color: #400000;">abs</span><span style="color: #808030;">(</span>query<span style="color: #808030;">[</span><span style="color: #008c00;">2</span><span style="color: #808030;">]</span> <span style="color: #44aadd;">-</span> query<span style="color: #808030;">[</span><span style="color: #008c00;">4</span><span style="color: #808030;">]</span><span style="color: #808030;">)</span> <span style="color: #44aadd;">==</span> <span style="color: #400000;">abs</span><span style="color: #808030;">(</span>problem<span style="color: #808030;">[</span>query_idx<span style="color: #808030;">]</span><span style="color: #808030;">)</span>
<span style="color: maroon; font-weight: bold;">else</span><span style="color: #808030;">:</span>
proof_checks_out <span style="color: #44aadd;">&</span><span style="color: #808030;">=</span> query<span style="color: #808030;">[</span><span style="color: #008c00;">2</span><span style="color: #808030;">]</span> <span style="color: #44aadd;">==</span> query<span style="color: #808030;">[</span><span style="color: #008c00;">4</span><span style="color: #808030;">]</span>
<span style="color: dimgrey;"># Authenticate paths</span>
proof_checks_out <span style="color: #44aadd;">&</span><span style="color: #808030;">=</span> \
verify_zk_merkle_path<span style="color: #808030;">(</span>merkle_root<span style="color: #808030;">,</span> <span style="color: #400000;">len</span><span style="color: #808030;">(</span>problem<span style="color: #808030;">)</span> <span style="color: #44aadd;">+</span> <span style="color: #008c00;">1</span><span style="color: #808030;">,</span> query_idx<span style="color: #808030;">,</span> query<span style="color: #808030;">[</span><span style="color: #008c00;">2</span><span style="color: #808030;">]</span><span style="color: #808030;">,</span> query<span style="color: #808030;">[</span><span style="color: #008c00;">3</span><span style="color: #808030;">]</span><span style="color: #808030;">)</span>
proof_checks_out <span style="color: #44aadd;">&</span><span style="color: #808030;">=</span> \
verify_zk_merkle_path<span style="color: #808030;">(</span>merkle_root<span style="color: #808030;">,</span> <span style="color: #400000;">len</span><span style="color: #808030;">(</span>problem<span style="color: #808030;">)</span> <span style="color: #44aadd;">+</span> <span style="color: #008c00;">1</span><span style="color: #808030;">,</span> \
<span style="color: #808030;">(</span>query_idx <span style="color: #44aadd;">+</span> <span style="color: #008c00;">1</span><span style="color: #808030;">)</span> <span style="color: #44aadd;">%</span> <span style="color: #808030;">(</span><span style="color: #400000;">len</span><span style="color: #808030;">(</span>problem<span style="color: #808030;">)</span> <span style="color: #44aadd;">+</span> <span style="color: #008c00;">1</span><span style="color: #808030;">)</span><span style="color: #808030;">,</span> query<span style="color: #808030;">[</span><span style="color: #008c00;">4</span><span style="color: #808030;">]</span><span style="color: #808030;">,</span> query<span style="color: #808030;">[</span><span style="color: #008c00;">5</span><span style="color: #808030;">]</span><span style="color: #808030;">)</span>
randomness_seed <span style="color: #44aadd;">+</span><span style="color: #808030;">=</span> <span style="color: #808030;">[</span>query<span style="color: #808030;">]</span>
<span style="color: maroon; font-weight: bold;">return</span> proof_checks_out</pre>
</pre>
</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<h3 dir="ltr" style="text-align: left;">
A Real Live Proof!</h3>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
Running the following short script returns true (as the proof indeed checks out) and prints the proof</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<pre style="background: rgb(255, 255, 255);"><span style="color: maroon; font-weight: bold;">def</span> test<span style="color: #808030;">(</span>q<span style="color: #808030;">)</span><span style="color: #808030;">:</span>
problem <span style="color: #808030;">=</span> <span style="color: #808030;">[</span><span style="color: #008c00;">1</span><span style="color: #808030;">,</span> <span style="color: #008c00;">2</span><span style="color: #808030;">,</span> <span style="color: #008c00;">3</span><span style="color: #808030;">,</span> <span style="color: #008c00;">6</span><span style="color: #808030;">,</span> <span style="color: #008c00;">6</span><span style="color: #808030;">,</span> <span style="color: #008c00;">6</span><span style="color: #808030;">,</span> <span style="color: #008c00;">12</span><span style="color: #808030;">]</span>
assignment <span style="color: #808030;">=</span> <span style="color: #808030;">[</span><span style="color: #008c00;">1</span><span style="color: #808030;">,</span> <span style="color: #008c00;">1</span><span style="color: #808030;">,</span> <span style="color: #008c00;">1</span><span style="color: #808030;">,</span> <span style="color: #44aadd;">-</span><span style="color: #008c00;">1</span><span style="color: #808030;">,</span> <span style="color: #44aadd;">-</span><span style="color: #008c00;">1</span><span style="color: #808030;">,</span> <span style="color: #44aadd;">-</span><span style="color: #008c00;">1</span><span style="color: #808030;">,</span> <span style="color: #008c00;">1</span><span style="color: #808030;">]</span>
proof <span style="color: #808030;">=</span> get_proof<span style="color: #808030;">(</span>problem<span style="color: #808030;">,</span> assignment<span style="color: #808030;">,</span> q<span style="color: #808030;">)</span>
<span style="color: maroon; font-weight: bold;">print</span><span style="color: #808030;">(</span>proof<span style="color: #808030;">)</span>
<span style="color: maroon; font-weight: bold;">return</span> verify_proof<span style="color: #808030;">(</span>problem<span style="color: #808030;">,</span> proof<span style="color: #808030;">)</span></pre>
</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
And this is the proof we get (running "test(4)" for only 4 queries):</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<div style="overflow: scroll; width: 876px;">
<pre style="background: rgb(255, 255, 255);"><span style="color: #808030;">[</span><span style="color: #808030;">[</span><span style="color: #0000e6;">'f9f3b1e40626e906b03eb9fd5428b2f2f801e8f3c23627fe7e52a645c3f32632'</span><span style="color: #808030;">,</span> <span style="color: #008c00;">3</span><span style="color: #808030;">,</span> <span style="color: #008c00;">1</span><span style="color: #808030;">,</span> <span style="color: #808030;">[</span><span style="color: #0000e6;">'1b7f5356d043c6336c6614fcc24cb77f8807cd2f443b1b77e0002be6b96c40b6'</span><span style="color: #808030;">,</span> <span style="color: #0000e6;">'a412af57af0b88cdb5cb3d0cbfcd739ebcc3c6fe0ac364db9490b4a208803101'</span><span style="color: #808030;">,</span> <span style="color: #0000e6;">'9f358dd0980f35ea86070d0fb12b2f5726857031ef56968005095cdb13e0a6f0'</span><span style="color: #808030;">,</span> <span style="color: #0000e6;">'05066ac05f174f1f98226c40889c566775592ec3807fbe080324447616773e18'</span><span style="color: #808030;">]</span><span style="color: #808030;">,</span> <span style="color: #008c00;">7</span><span style="color: #808030;">,</span> <span style="color: #808030;">[</span><span style="color: #0000e6;">'cd6ee891c632e07ad468cd602c8d2d935356ca5901b21a75a2719d164a925382'</span><span style="color: #808030;">,</span> <span style="color: #0000e6;">'4cfc41b83cf64e0cf14a0ea8179aa67c6324699557c508dfc424604674805864'</span><span style="color: #808030;">,</span> <span style="color: #0000e6;">'4efb02f72dbc085ead53657647e893f3ceb29c9f81d411dd817f3be512cad632'</span><span style="color: #808030;">,</span> <span style="color: #0000e6;">'6cd4c16c3d5db473280b64f6b3fce54cb4b6810b46331899f4c07f884fd89aae'</span><span style="color: #808030;">]</span><span style="color: #808030;">]</span><span style="color: #808030;">,</span> <span style="color: #808030;">[</span><span style="color: #0000e6;">'580bd4db1071906bcd101600baf51d33b9930ba6e26853e85634bf38c0acef92'</span><span style="color: #808030;">,</span> <span style="color: #008c00;">6</span><span style="color: #808030;">,</span> <span style="color: #008c00;">16</span><span style="color: #808030;">,</span> <span style="color: #808030;">[</span><span style="color: #0000e6;">'f8b28423de50f3b0cbcf88caacb6d4f6789ba3cecdc7791b38d5bbcd700ecbd2'</span><span style="color: #808030;">,</span> <span style="color: #0000e6;">'5c41ad0b9d813740b516cb61cf9ce06966efcf82e8ee5881ca86d5b18400d03d'</span><span style="color: #808030;">,</span> <span style="color: #0000e6;">'af38f9a1873b70d113dab45d6312e6d2a7f4afa45a8c82ebe788abf63dd85650'</span><span style="color: #808030;">,</span> <span style="color: #0000e6;">'a57a3ccb7cbffdf4d346f1ecf10ead43a4ce1e52b51170789698b7aece6c7687'</span><span style="color: #808030;">]</span><span style="color: #808030;">,</span> <span style="color: #008c00;">4</span><span style="color: #808030;">,</span> <span style="color: #808030;">[</span><span style="color: #0000e6;">'b703a38bb22b758c5c23c08f096b6c3155c56885d57e1280ff521126282fa857'</span><span style="color: #808030;">,</span> <span style="color: #0000e6;">'4e602f00ef1e1de0b733f467de61805f09a1ebee8db72cc64c62dd8d55836de1'</span><span style="color: #808030;">,</span> <span style="color: #0000e6;">'af38f9a1873b70d113dab45d6312e6d2a7f4afa45a8c82ebe788abf63dd85650'</span><span style="color: #808030;">,</span> <span style="color: #0000e6;">'a57a3ccb7cbffdf4d346f1ecf10ead43a4ce1e52b51170789698b7aece6c7687'</span><span style="color: #808030;">]</span><span style="color: #808030;">]</span><span style="color: #808030;">]</span>
</pre>
<div>
<span style="color: #808030;"><br /></span></div>
</div>
</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<h3 dir="ltr" style="text-align: left;">
One More Thing...</h3>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
This series, in accordance with <a href="https://en.wikipedia.org/wiki/Hofstadter%27s_law">Hofstadter's law</a>, turned out to be somewhat longer than I anticipated. However, I left out a few things that are important.<br />
<br /></div>
<div dir="ltr" style="text-align: left;">
Among these are:</div>
<div dir="ltr" style="text-align: left;">
<ol style="text-align: left;">
<li>Off-the-bat optimizations.</li>
<li>Some discussion about proof length, running time, and what modern proof lengths (and running times) look like.</li>
<li>A few simple tweaks, suggested by my colleague at <a href="https://www.starkware.co/">Starkware</a>, Lior Goldberg, to make the protocol truly Zero-Knowledge (because it isn't exactly there yet) and slightly more elegant.</li>
</ol>
</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
So, although I promised a 3-part series, there will be a fourth part. But seeing how all the code is already here, we'll call it an appendix.</div>
</div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com8tag:blogger.com,1999:blog-642244788469558745.post-51481028147632240222018-10-01T22:35:00.002+03:002018-10-03T14:29:05.990+03:00A Hands-On Tutorial for Zero-Knowledge Proofs: Part II<div dir="rtl" style="text-align: right;" trbidi="on">
<div dir="ltr" style="text-align: left;">
In the <a href="http://www.shirpeled.com/2018/09/a-hands-on-tutorial-for-zero-knowledge.html">previous post</a> we developed the <i>witness</i> for our proof. Simply put - it is a piece of data that the prover will claim it has, and the verifier will ask queries about. In this process will develop the machinery required to force the prover to be - if not honest, then at least consistent.<br />
Hopefully, our protocol will be such that the prover cannot make a false claim <b>and</b> be consistent about it.<br />
<div>
<br /></div>
</div>
<div dir="ltr" style="text-align: left;">
<h3 style="text-align: left;">
Where were we?</h3>
</div>
<div dir="ltr" style="text-align: left;">
Recall that in our setting, the prover claims knowledge of a (supposedly secret) satisfying assignment to a known <a href="https://en.wikipedia.org/wiki/Partition_problem">Partition Problem</a> instance. The protocol we developed so far was this:</div>
<div dir="ltr" style="text-align: left;">
</div>
<ol dir="ltr" style="text-align: left;">
<li>The verifier chooses a random value $i$.</li>
<li>According to the value of $i$, the verifier asks for two values from the witness (usually two consecutive values, but sometimes the first and the last).</li>
</ol>
<div dir="ltr" style="text-align: left;">
(check <a href="http://www.shirpeled.com/2018/09/a-hands-on-tutorial-for-zero-knowledge.html">the previous</a> post for exact details).</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
Indeed, if the prover is honest in its answers, and doesn't cheat or make mistakes, then after enough queries - the verifier should be convinced. But hold on, if the prover is honest - why have all this elaborate game of questions and answers? the verifier can just take the prover's word for it, and everyone'll go home early.</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<h4 dir="ltr" style="text-align: left;">
But the prover may be a liar!!!</h4>
<div>
<br /></div>
<div dir="ltr" style="text-align: left;">
The entire raison d'être of ZK proofs is that we assume that the prover may be dishonest. So, assuming that the prover knows the protocol that the verifier is using - it can simply send such queries that will satisfy the verifier. If the verifier asks for two consecutive values, the prover will provide some two random numbers such that their absolute value matches the verifier's expectations (i.e., the corresponding value in the problem instance), and if it asks for the first and last element, the prover will just send some random number twice.</div>
<div dir="ltr" style="text-align: left;">
<br />
<br /></div>
<h3 dir="ltr" style="text-align: left;">
The Commitments</h3>
<div>
<br /></div>
<div dir="ltr" style="text-align: left;">
What we need here is a mechanism that will:</div>
<div dir="ltr" style="text-align: left;">
<ol style="text-align: left;">
<li>Force the prover to write down all of the values of $p$ <b>before</b> the verifier asks about them.</li>
<li>When asked, force the prover to return the required values from this previously written list.</li>
</ol>
<div>
<br />
This is a concept known in the world of cryptography as a commitment scheme.<br />
<br /></div>
</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<img alt="A wonderful movie from 1991, I totally recommend, excellent music." height="179" src="https://m.media-amazon.com/images/M/MV5BNmUzYTYyZmQtNjgxMi00MmE5LTk2NjgtZDcxZTA5OGY1NTUyXkEyXkFqcGdeQXVyNzU1NzE3NTg@._V1_CR0,45,480,270_AL_UX477_CR0,0,477,268_AL_.jpg" title="The Commitments" width="320" /><br />
<br />
<br />
In our case, we're going to work with a 40 year-old commitment scheme, a <a href="https://en.wikipedia.org/wiki/Merkle_tree">Merkle Tree</a>. It is a simple and brilliant idea.<br />
<br />
A <b>Merkle Tree</b> is just a full binary tree, where each node is assigned a string:<br />
<br />
<ol style="text-align: left;">
<li>The leaves contain hashes (we'll use <a href="https://en.wikipedia.org/wiki/SHA-2">Sha256</a>) of the data we'd like to commit to.</li>
<li>Every internal node in the tree is assigned with a string that is a hash of its two children's strings.</li>
</ol>
<div>
<br /></div>
<div>
Suppose we want to commit to this list of four strings: ["Yes", "Sir", "I Can", "Boogie!"].</div>
<div>
The Merkle tree will look something like this:</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh-quqZXNiPqdHhIrajRwl2P7bFB1-UXFv3M07JGtGU8seeSBkHSKPRSb6LzNyvg_8ELssCDRoNzPz8UymxQrxDOu7cuqOC6_osMvX56MrL6mR9oUorGhAsQDkRBmoXj6H2q6LMFTZ9MvvE/s1600/Selection_069.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="751" data-original-width="1417" height="339" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh-quqZXNiPqdHhIrajRwl2P7bFB1-UXFv3M07JGtGU8seeSBkHSKPRSb6LzNyvg_8ELssCDRoNzPz8UymxQrxDOu7cuqOC6_osMvX56MrL6mR9oUorGhAsQDkRBmoXj6H2q6LMFTZ9MvvE/s640/Selection_069.png" width="640" /></a></div>
<div>
<br /></div>
<div>
So node 4 is assigned the hash of the word "Yes", node 5 is assigned the hash of the word "Sir", and so on.</div>
<div>
Also, every node $0 < i < 4$ is assigned the hash of the strings assigned to nodes $2i$ and $2i + 1$, concatenated.</div>
<div>
<br /></div>
<div>
The string assigned to the root of the tree (i.e. node #1) is referred to as <b>the commitment</b>. </div>
<div>
That is because even the slightest change in the underlying data causes the root to change drastically. </div>
<div>
Here's what happens if we omit the exclamation mark from the word "Boogie" (the affected nodes are marked in red):</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiuej0WZbmEpwyj5oErxDn8LnaUpvx9SD-M_bQAhiodttJFZx78IMdIgxcLi43-w3Kk4ha_G1Y9oJGus6D0xM7rS39-ldDeJ-TQYWT-yvxPllD8VzQHcwJnwk3JUDKKjI_lhYBHDsUTSU46/s1600/Selection_070.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="730" data-original-width="1398" height="334" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiuej0WZbmEpwyj5oErxDn8LnaUpvx9SD-M_bQAhiodttJFZx78IMdIgxcLi43-w3Kk4ha_G1Y9oJGus6D0xM7rS39-ldDeJ-TQYWT-yvxPllD8VzQHcwJnwk3JUDKKjI_lhYBHDsUTSU46/s640/Selection_070.png" width="640" /></a></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
An even cooler property of Merkle Trees, is that one can prove that a certain string belongs to the underlying data, without exposing the entire data.</div>
<div>
<br /></div>
<h3 style="text-align: left;">
Authentication Paths</h3>
<div>
<br /></div>
<div>
Suppose I would like to commit to the title of a 1977 song by the Spanish vocal duo <a href="https://en.wikipedia.org/wiki/Baccara">Baccara</a>. The title itself is kept a secret (!), but you can ask me about one of the words in the title (well, I put "I" and "Can" in the same leaf... but let's ignore this fine point).</div>
<div>
To prove that I won't switch songs half way through our game, I send you the hash from the root node of a Merkle Tree I created.</div>
<div>
You now ask me what is the second word in the title, to which I reply "Sir".</div>
<div>
To prove that this answer is consistent with the hash I sent you before, I also send you the hashes of nodes 4 and 3. This is called the <b>authentication path</b> of node 5 (which contains the second word from the title).</div>
<div>
You can now check that I'm not lying by:</div>
<div>
<ul style="text-align: left;">
<li>Computing the hash of node 5 yourself (by hashing the word "Sir").</li>
<li>Using that and the hash I gave you of node 4 to compute the hash of node 2.</li>
<li>Using that and the hash I gave you of node 3 to compute the hash of the root node.</li>
<li>Compare the hash you computed with the one I originally sent you, if they match, it means that I didn't switch song in between the time I sent you the initial commitment, and the time I answered you query about the second word in the title.</li>
</ul>
<div>
<br /></div>
</div>
<div>
It is widely believed that given the Sha256 hash of some string $S_0$, it is infeasible to find another string $S_1 \neq S_0$ that has an identical Sha256 hash. This belief means that indeed one could not have changed the underlying data of a Merkle Tree without changing the root node's hash, and thus Merkle Trees can be used as commitment schemes.</div>
<div>
<br /></div>
<h3 style="text-align: left;">
Let's See Some Code</h3>
<div>
<br /></div>
<div>
Recall that we need this machinery in order to commit to a list of numbers which we dubbed "the witness", and referred to as $p$ in the previous post.</div>
<div>
So we need a simple class with a constructor that gets a list of numbers as input, constructs the necessary Merkle Tree, and allows the user to get the root's hash, and obtain authentication paths for the numbers in the underlying list.</div>
<div>
<br /></div>
<div>
We'll also throw in a function that verifies authentication paths, this function is independent from the class, as this can be done simply by hashing.</div>
<div>
<br /></div>
<div>
Here's a somewhat naive implementation of a Merkle Tree:</div>
<div>
<br /></div>
<div>
<pre style="background: rgb(255, 255, 255);"><span style="color: maroon; font-weight: bold;">import</span> hashlib
<span style="color: maroon; font-weight: bold;">from</span> math <span style="color: maroon; font-weight: bold;">import</span> log2<span style="color: #808030;">,</span> ceil
<span style="color: maroon; font-weight: bold;">def</span> hash_string<span style="color: #808030;">(</span>s<span style="color: #808030;">)</span><span style="color: #808030;">:</span>
<span style="color: maroon; font-weight: bold;">return</span> hashlib<span style="color: #808030;">.</span>sha256<span style="color: #808030;">(</span>s<span style="color: #808030;">.</span>encode<span style="color: #808030;">(</span><span style="color: #808030;">)</span><span style="color: #808030;">)</span><span style="color: #808030;">.</span>hexdigest<span style="color: #808030;">(</span><span style="color: #808030;">)</span>
<span style="color: maroon; font-weight: bold;">class</span> MerkleTree<span style="color: #808030;">:</span>
<span style="color: dimgrey;">"""</span>
<span style="color: dimgrey;"> A naive Merkle tree implementation using SHA256</span>
<span style="color: dimgrey;"> """</span>
<span style="color: maroon; font-weight: bold;">def</span> <span style="color: #074726;">__init__</span><span style="color: #808030;">(</span>self<span style="color: #808030;">,</span> data<span style="color: #808030;">)</span><span style="color: #808030;">:</span>
self<span style="color: #808030;">.</span>data <span style="color: #808030;">=</span> data
next_pow_of_2 <span style="color: #808030;">=</span> <span style="color: #400000;">int</span><span style="color: #808030;">(</span><span style="color: #008c00;">2</span><span style="color: #44aadd;">**</span>ceil<span style="color: #808030;">(</span>log2<span style="color: #808030;">(</span><span style="color: #400000;">len</span><span style="color: #808030;">(</span>data<span style="color: #808030;">)</span><span style="color: #808030;">)</span><span style="color: #808030;">)</span><span style="color: #808030;">)</span>
self<span style="color: #808030;">.</span>data<span style="color: #808030;">.</span>extend<span style="color: #808030;">(</span><span style="color: #808030;">[</span><span style="color: #008c00;">0</span><span style="color: #808030;">]</span> <span style="color: #44aadd;">*</span> <span style="color: #808030;">(</span>next_pow_of_2 <span style="color: #44aadd;">-</span> <span style="color: #400000;">len</span><span style="color: #808030;">(</span>data<span style="color: #808030;">)</span><span style="color: #808030;">)</span><span style="color: #808030;">)</span>
self<span style="color: #808030;">.</span>tree <span style="color: #808030;">=</span> <span style="color: #808030;">[</span><span style="color: #0000e6;">""</span> <span style="color: maroon; font-weight: bold;">for</span> x <span style="color: maroon; font-weight: bold;">in</span> self<span style="color: #808030;">.</span>data<span style="color: #808030;">]</span> <span style="color: #44aadd;">+</span> \
<span style="color: #808030;">[</span>hash_string<span style="color: #808030;">(</span><span style="color: #400000;">str</span><span style="color: #808030;">(</span>x<span style="color: #808030;">)</span><span style="color: #808030;">)</span> <span style="color: maroon; font-weight: bold;">for</span> x <span style="color: maroon; font-weight: bold;">in</span> self<span style="color: #808030;">.</span>data<span style="color: #808030;">]</span>
<span style="color: maroon; font-weight: bold;">for</span> i <span style="color: maroon; font-weight: bold;">in</span> <span style="color: #400000;">range</span><span style="color: #808030;">(</span><span style="color: #400000;">len</span><span style="color: #808030;">(</span>self<span style="color: #808030;">.</span>data<span style="color: #808030;">)</span> <span style="color: #44aadd;">-</span> <span style="color: #008c00;">1</span><span style="color: #808030;">,</span> <span style="color: #008c00;">0</span><span style="color: #808030;">,</span> <span style="color: #44aadd;">-</span><span style="color: #008c00;">1</span><span style="color: #808030;">)</span><span style="color: #808030;">:</span>
self<span style="color: #808030;">.</span>tree<span style="color: #808030;">[</span>i<span style="color: #808030;">]</span> <span style="color: #808030;">=</span> hash_string<span style="color: #808030;">(</span>self<span style="color: #808030;">.</span>tree<span style="color: #808030;">[</span>i <span style="color: #44aadd;">*</span> <span style="color: #008c00;">2</span><span style="color: #808030;">]</span> <span style="color: #44aadd;">+</span> self<span style="color: #808030;">.</span>tree<span style="color: #808030;">[</span>i <span style="color: #44aadd;">*</span> <span style="color: #008c00;">2</span> <span style="color: #44aadd;">+</span> <span style="color: #008c00;">1</span><span style="color: #808030;">]</span><span style="color: #808030;">)</span>
<span style="color: maroon; font-weight: bold;">def</span> get_root<span style="color: #808030;">(</span>self<span style="color: #808030;">)</span><span style="color: #808030;">:</span>
<span style="color: maroon; font-weight: bold;">return</span> self<span style="color: #808030;">.</span>tree<span style="color: #808030;">[</span><span style="color: #008c00;">1</span><span style="color: #808030;">]</span>
<span style="color: maroon; font-weight: bold;">def</span> get_val_and_path<span style="color: #808030;">(</span>self<span style="color: #808030;">,</span> <span style="color: #400000;">id</span><span style="color: #808030;">)</span><span style="color: #808030;">:</span>
val <span style="color: #808030;">=</span> self<span style="color: #808030;">.</span>data<span style="color: #808030;">[</span><span style="color: #400000;">id</span><span style="color: #808030;">]</span>
auth_path <span style="color: #808030;">=</span> <span style="color: #808030;">[</span><span style="color: #808030;">]</span>
<span style="color: #400000;">id</span> <span style="color: #808030;">=</span> <span style="color: #400000;">id</span> <span style="color: #44aadd;">+</span> <span style="color: #400000;">len</span><span style="color: #808030;">(</span>self<span style="color: #808030;">.</span>data<span style="color: #808030;">)</span>
<span style="color: maroon; font-weight: bold;">while</span> <span style="color: #400000;">id</span> <span style="color: #44aadd;">></span> <span style="color: #008c00;">1</span><span style="color: #808030;">:</span>
auth_path <span style="color: #44aadd;">+</span><span style="color: #808030;">=</span> <span style="color: #808030;">[</span>self<span style="color: #808030;">.</span>tree<span style="color: #808030;">[</span><span style="color: #400000;">id</span> <span style="color: #44aadd;">^</span> <span style="color: #008c00;">1</span><span style="color: #808030;">]</span><span style="color: #808030;">]</span>
<span style="color: #400000;">id</span> <span style="color: #808030;">=</span> <span style="color: #400000;">id</span> <span style="color: #44aadd;">//</span> <span style="color: #008c00;">2</span>
<span style="color: maroon; font-weight: bold;">return</span> val<span style="color: #808030;">,</span> auth_path
<span style="color: maroon; font-weight: bold;">def</span> verify_merkle_path<span style="color: #808030;">(</span>root<span style="color: #808030;">,</span> data_size<span style="color: #808030;">,</span> value_id<span style="color: #808030;">,</span> value<span style="color: #808030;">,</span> path<span style="color: #808030;">)</span><span style="color: #808030;">:</span>
cur <span style="color: #808030;">=</span> hash_string<span style="color: #808030;">(</span><span style="color: #400000;">str</span><span style="color: #808030;">(</span>value<span style="color: #808030;">)</span><span style="color: #808030;">)</span>
tree_node_id <span style="color: #808030;">=</span> value_id <span style="color: #44aadd;">+</span> <span style="color: #400000;">int</span><span style="color: #808030;">(</span><span style="color: #008c00;">2</span><span style="color: #44aadd;">**</span>ceil<span style="color: #808030;">(</span>log2<span style="color: #808030;">(</span>data_size<span style="color: #808030;">)</span><span style="color: #808030;">)</span><span style="color: #808030;">)</span>
<span style="color: maroon; font-weight: bold;">for</span> sibling <span style="color: maroon; font-weight: bold;">in</span> path<span style="color: #808030;">:</span>
<span style="color: maroon; font-weight: bold;">assert</span> tree_node_id <span style="color: #44aadd;">></span> <span style="color: #008c00;">1</span>
<span style="color: maroon; font-weight: bold;">if</span> tree_node_id <span style="color: #44aadd;">%</span> <span style="color: #008c00;">2</span> <span style="color: #44aadd;">==</span> <span style="color: #008c00;">0</span><span style="color: #808030;">:</span>
cur <span style="color: #808030;">=</span> hash_string<span style="color: #808030;">(</span>cur <span style="color: #44aadd;">+</span> sibling<span style="color: #808030;">)</span>
<span style="color: maroon; font-weight: bold;">else</span><span style="color: #808030;">:</span>
cur <span style="color: #808030;">=</span> hash_string<span style="color: #808030;">(</span>sibling <span style="color: #44aadd;">+</span> cur<span style="color: #808030;">)</span>
tree_node_id <span style="color: #808030;">=</span> tree_node_id <span style="color: #44aadd;">//</span> <span style="color: #008c00;">2</span>
<span style="color: maroon; font-weight: bold;">assert</span> tree_node_id <span style="color: #44aadd;">==</span> <span style="color: #008c00;">1</span>
<span style="color: maroon; font-weight: bold;">return</span> root <span style="color: #44aadd;">==</span> cur</pre>
</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
A few things to note:</div>
<div>
<br /></div>
<div>
<ul style="text-align: left;">
<li>It being a binary tree, we extend the underlying data to the next power of 2 (by padding with 0s) for it to match the number of leaves of a full binary tree.</li>
<li>We store the root of the tree at index 1 and not 0, and its children at 2 and 3 and so on. This is just so that the indexing will be convenient, and the children of node $i$ will always be $2i$ and $2i + 1$.</li>
<li>This is far from optimal, because for our purposes (a blog post) clarity and brevity are more important.</li>
</ul>
<div>
<br /></div>
</div>
<h3 style="text-align: left;">
What About Zero Knowledge???</h3>
<div>
An observant reader will point out that when we provide the authentication path for node 5, we provide the hash of node 4. </div>
<div>
A snooping verifier may try hashing various words from the titles of songs of the Spanish vocal duo Baccara, and when it gets the hash we sent it as "the hash of node 4", it will have found out a leaf of the tree that we never intended to expose!</div>
<div>
<br /></div>
<div>
In the next post in the series, we'll deal with the ZK issue, using a simple but effective trick to get a Zero Knowledge Merkle Tree. </div>
<div>
Also, we'll hopefully tie everything together to get the proof we originally wanted!</div>
<div>
<br />
<br />
<a href="http://www.shirpeled.com/2018/10/a-hands-on-tutorial-for-zero-knowledge_2.html">Part III</a></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<br />
<br />
<br /></div>
<div dir="ltr" style="text-align: left;">
<br /></div>
</div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com2tag:blogger.com,1999:blog-642244788469558745.post-45366035292411612932018-09-30T22:29:00.000+03:002018-10-04T08:06:54.621+03:00A Hands-On Tutorial for Zero-Knowledge Proofs: Part I
<div dir="rtl" style="text-align: right;" trbidi="on">
<div dir="ltr" style="text-align: left;">
By the end of this series of posts we will have composed some code in Python (roughly 100 lines) that proves the satisfiability of Partition Problem instances with zero knowledge.<br />
<br />
<h3 style="text-align: left;">
Three preliminary notes</h3>
<br />
<ol style="text-align: left;">
<li>I will assume some basic Computer Science background, as well as familiarity with Python, but not much more. </li>
<li>I haven't seen this specific protocol in the literature (because I haven't searched for it), but it is a combination of well-known techniques in well-known ways, so I'm quite sure some variation of it is out there.</li>
<li>For didactic reasons, we'll start with naive and sometimes broken implementations, and improve on them as we go along.</li>
</ol>
<div>
<br /></div>
<br />
<h3 style="text-align: left;">
Background</h3>
<div>
I'm currently working at <a href="https://www.starkware.co/">Starkware</a>, developing some serious zero-knowledge proofs with some brilliant people, based on state-of-the-art research in the field, and we're usually hiring, so drop me a line if you're interested. </div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://www.starkware.co/wp-content/uploads/2018/04/logo.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="62" data-original-width="199" src="https://www.starkware.co/wp-content/uploads/2018/04/logo.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div style="text-align: left;">
<span style="font-weight: normal;">This series, however, will deal with much more basic stuff, essentially Computer Science from the 1980s. For those familiar with contemporary protocols such as SNARKs, Bulletproofs, and STARKs - I am </span><b>not</b> going to present any of them, if you don't know what any of these are - fear not.<br />
What I'm shooting for is less "<i>Cheat sheet for modern ZK proofs</i>" and more "<i>ZK proofs for dummies</i>".<br />
<br />
With that in mind - let's get going.<br />
<span style="font-weight: normal;"><br /></span>
<span style="font-weight: normal;"><br /></span></div>
<h4 style="text-align: left;">
</h4>
<h4 style="text-align: left;">
Zero Knowledge Proofs</h4>
<div>
Zero Knowledge (AKA ZK) proofs are stories of the following type: side A states a claim and proves it to side B, after some deliberation between them, such that:</div>
<div>
<ol style="text-align: left;">
<li>B is sure that the claim is true with 99.99999% certainty.</li>
<li>B has learnt nothing new in the process, other than that the claim is true.</li>
</ol>
<div>
<a href="https://en.wikipedia.org/wiki/Zero-knowledge_proof">This Wikipedia article</a> contains an excellent explanation of the idea, with some concrete examples.</div>
</div>
<div>
In this series I'll deal with <i>ZK arguments of knowledge</i>, which are not exactly the same as proofs, but they're close enough. In short: a ZK proof can be trusted completely, even if the side who's trying to prove their claim (usually referred to as "the prover") has unlimited computational power. ZK argument-of-knowledge can be trusted under the assumption that if the prover indeed tries to cheat, it is polynomialy bounded (if you use credit cards on the internet, then you already assume that, btw). </div>
<div>
In the world of ZK proofs, the other side of the exchange is often called "the verifier". I'll stick to this terminology here.</div>
<div>
<br /></div>
<h4 style="text-align: left;">
The Partition Problem</h4>
<div>
Given a sequence of numbers $a_0, a_1, ..., a_{n-1}$, can one partition this sequence into two subsets that sum up to the same number?</div>
<div>
If the sequence in question is $1, 9, 8, 0, 2, 2$, then the answer is clearly yes since $2 + 9 = 8 + 1 + 2 + 0$.</div>
<div>
However if the sequence is $2, 3, 4, 5, 6, 7$, then the answer is clearly no, since the sum is odd, and therefore there cannot be two subsets summing exactly to half of it each (the numbers are all integers).<br />
While these are simple enough instances, in general <a href="https://en.wikipedia.org/wiki/Partition_problem">this problem is NP-complete</a> (though it has a pseudo-polynomial algorithm).</div>
<div>
<br /></div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://i.stack.imgur.com/TWabQ.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="367" data-original-width="800" height="146" src="https://i.stack.imgur.com/TWabQ.jpg" width="320" /></a></div>
<div>
<br /></div>
<div>
<br /></div>
<h3 style="text-align: left;">
Let's Start Proving!</h3>
<div>
<br /></div>
<div>
Suppose we have a python list $l$ of numbers, that defines our Partition Problem instance. We'll say that another list $m$ is a satisfying assignment if:</div>
<div>
<ol style="text-align: left;">
<li>len(m) == len(l).</li>
<li>All of the elements in $m$ are either $1$ or $-1$.</li>
<li>The dot-product of $l$ and $m$ is 0.</li>
</ol>
<div>
Note that this is equivalent to the statement of the partition problem, if we think of a '1' in $m$ as assigning its corresponding number in $l$ to the left side of the equation, and '-1' as assigning it to the right side.</div>
</div>
<div>
<br /></div>
<div>
Given $l$, a proof for its satisfiability can be given by revealing $m$, but that would violate the ZK requirement.</div>
<div>
<br /></div>
<div>
Let's rewrite $l$ as the partial sum list of its dot product with $m$.</div>
<div>
Mathematically speaking, let $p_i := \sum _{0\leq k<i} l[k] \cdot m[k]$.</div>
<div>
<br /></div>
<div>
So if $l = [4, 11, 8, 1]$, and $m = [1, -1, 1, -1]$, then $p$ will be one element longer: $p = [0, 4, -7, 1, 0]$.</div>
<div>
<br /></div>
<div>
Note that $p$ now has two interesting properties, if $m$ is indeed a satisfying assignment:</div>
<div>
<ul style="text-align: left;">
<li>(property 1 of p) It starts and ends with 0.</li>
<li>(property 2 of p) For every $0\leq i < n$, we have $|l[i]| = |p[i+1] - p[i]|$.</li>
</ul>
<div>
<br /></div>
</div>
<div>
So here's a first draft for a ZK protocol:</div>
<div>
The verifier chooses a random $0 \leq i \leq n$.</div>
<div>
If $i = n$, the verifier asks the prover to provide $p[0]$ and $p[n]$ and checks that they are both 0.</div>
<div>
Otherwise, the verifier asks the prover to provide $p[i]$ and $p[i+1]$ and checks that indeed $|l[i]| = |p[i+1] - p[i]|$ (recall that $l$ is known to the verifier, as part of the claim made by the prover).</div>
<div>
<br /></div>
<div>
<br /></div>
<h3 style="text-align: left;">
What if the prover is lying???</h3>
<div>
The above contains an implicit assumption that when the verifier asks the prover to provide some data, the prover will indeed provide it honestly. We don't want to assume that, but we postpone dealing with this issue to the next post. For now, let's assume everything is kosher.</div>
<div>
<br /></div>
<h3 style="text-align: left;">
This doesn't prove anything!</h3>
<div>
An observant reader will probably point out that asking about a single element doesn't mean much. And that's true, we'd like to ask many queries, and after enough of them - we'll be certain that the claim is true. We'll quantify this more accurately in the third (and last) post.</div>
<div>
<br /></div>
<h3 style="text-align: left;">
This is not Zero-Knowledge!</h3>
<div>
Each query reveals something about $m$, and so it is not zero-knowledge. Consequently, after enough queries - $m$ can be completely revealed. </div>
<div>
That's terrible! Let's fix it.</div>
<div>
<br /></div>
<h3 style="text-align: left;">
Manufacturing Zero-Knowledge </h3>
<div>
Mathematically speaking, we usually say that something provides no new information, if it appears random, or more precisely - if it is uniformly distributed over some appropriately chosen domain. Without getting into the exact definition, this means that to make something ZK, we mix it with randomness. So here's how we do it here.</div>
<div>
<ol style="text-align: left;">
<li>Instead of $m$ as it was given to us, we flip a coin. If it shows heads, we leave $m$ as it is, if it shows tails, we multiply all of $m$'s elements by $-1$. Note that since its elmenets were initially $-1$ and $1$, and its dot product with $l$ was 0, this does not change its dot product with $l$ at all.</li>
<li>We choose a random number $r$ and add it to all the elements of $p$. This does not effect the second property of $p$, but it changes the first property such that the first and last elements of $p$ now may not be zero. However, <b>they must still be identical to one another</b>.</li>
</ol>
<div>
<br /></div>
<div>
Now suppose that before each query - we recompute this randomness (i.e. - flip the coin and change $m$, and choose a random number $r$ and add it to the elements of $p$).</div>
<div>
<br /></div>
<div>
If we choose $r$ carefully, then indeed, every two consecutive elements of $p$ will differ (in absolute value) by the corresponding element in $l$ but look otherwise random. </div>
<div>
<br /></div>
<div>
So, here's the first piece of code we'll need, something that takes a problem (i.e. $l$) and a satisfying assignment (i.e. $m$) and constructs a witness (i.e. $p$) that will attest to the satisfiability of the problem instance:</div>
<div>
<br />
<pre style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial;"><span style="background-color: white;"><span style="color: maroon; font-weight: bold;">import</span> random
<span style="color: maroon; font-weight: bold;">def</span> get_witness<span style="color: #808030;">(</span>problem<span style="color: #808030;">,</span> assignment<span style="color: #808030;">)</span><span style="color: #808030;">:</span>
<span style="color: dimgrey;">"""</span>
<span style="color: dimgrey;"> Given an instance of a partition problem via a list of numbers (the problem) and a list of</span>
<span style="color: dimgrey;"> (-1, 1), we say that the assignment satisfies the problem if their dot product is 0.</span>
<span style="color: dimgrey;"> """</span>
<span style="color: #400000;">sum</span> <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span>
mx <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span>
side_obfuscator <span style="color: #808030;">=</span> <span style="color: #008c00;">1</span> <span style="color: #44aadd;">-</span> <span style="color: #008c00;">2</span> <span style="color: #44aadd;">*</span> random<span style="color: #808030;">.</span>randint<span style="color: #808030;">(</span><span style="color: #008c00;">0</span><span style="color: #808030;">,</span> <span style="color: #008c00;">1</span><span style="color: #808030;">)</span>
witness <span style="color: #808030;">=</span> <span style="color: #808030;">[</span><span style="color: #400000;">sum</span><span style="color: #808030;">]</span>
<span style="color: maroon; font-weight: bold;">assert</span> <span style="color: #400000;">len</span><span style="color: #808030;">(</span>problem<span style="color: #808030;">)</span> <span style="color: #44aadd;">==</span> <span style="color: #400000;">len</span><span style="color: #808030;">(</span>assignment<span style="color: #808030;">)</span>
<span style="color: maroon; font-weight: bold;">for</span> num<span style="color: #808030;">,</span> side <span style="color: maroon; font-weight: bold;">in</span> <span style="color: #400000;">zip</span><span style="color: #808030;">(</span>problem<span style="color: #808030;">,</span> assignment<span style="color: #808030;">)</span><span style="color: #808030;">:</span>
<span style="color: maroon; font-weight: bold;">assert</span> side <span style="color: #44aadd;">==</span> <span style="color: #008c00;">1</span> <span style="color: maroon; font-weight: bold;">or</span> side <span style="color: #44aadd;">==</span> <span style="color: #44aadd;">-</span><span style="color: #008c00;">1</span>
<span style="color: #400000;">sum</span> <span style="color: #44aadd;">+</span><span style="color: #808030;">=</span> side <span style="color: #44aadd;">*</span> num <span style="color: #44aadd;">*</span> side_obfuscator
witness <span style="color: #44aadd;">+</span><span style="color: #808030;">=</span> <span style="color: #808030;">[</span><span style="color: #400000;">sum</span><span style="color: #808030;">]</span>
mx <span style="color: #808030;">=</span> <span style="color: #400000;">max</span><span style="color: #808030;">(</span>mx<span style="color: #808030;">,</span> num<span style="color: #808030;">)</span>
<span style="color: dimgrey;"># make sure that it is a satisfying assignment</span>
<span style="color: maroon; font-weight: bold;">assert</span> <span style="color: #400000;">sum</span> <span style="color: #44aadd;">==</span> <span style="color: #008c00;">0</span>
shift <span style="color: #808030;">=</span> random<span style="color: #808030;">.</span>randint<span style="color: #808030;">(</span><span style="color: #008c00;">0</span><span style="color: #808030;">,</span> mx<span style="color: #808030;">)</span>
witness <span style="color: #808030;">=</span> <span style="color: #808030;">[</span>x <span style="color: #44aadd;">+</span> shift <span style="color: maroon; font-weight: bold;">for</span> x <span style="color: maroon; font-weight: bold;">in</span> witness<span style="color: #808030;">]</span>
<span style="color: maroon; font-weight: bold;">return</span> witness</span></pre>
<br /></div>
<div>
<br />
This post didn't have nearly enough images as a blog post should have. Her'e one to make up for it:<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://worldwideinterweb.com/wp-content/uploads/2014/07/best-picture-on-the-internet.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="540" data-original-width="800" height="216" src="https://worldwideinterweb.com/wp-content/uploads/2014/07/best-picture-on-the-internet.jpg" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<a href="http://www.shirpeled.com/2018/10/a-hands-on-tutorial-for-zero-knowledge.html">Part II</a></div>
<div class="separator" style="clear: both; text-align: left;">
<a href="http://www.shirpeled.com/2018/10/a-hands-on-tutorial-for-zero-knowledge_2.html">Part III</a></div>
<br /></div>
</div>
</div>
</div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com7tag:blogger.com,1999:blog-642244788469558745.post-71081736395298732802018-02-21T22:41:00.000+02:002018-02-21T22:41:11.344+02:00Hierarchical Hierarchical Clustering: A Concept So Nice, We Named It TwiceWhile working at <a href="https://www.resonai.com/">Resonai</a>, I wrote a piece of code that performs <a href="https://en.wikipedia.org/wiki/Hierarchical_clustering">Hierarchical Clustering</a>, in collaboration with <a href="https://www.linkedin.com/in/david-lehavi-418b1a3/">David Lehavi</a>. In addition to various optimizations I won't get into, we applied a nice heuristic that allowed a considerable improvement in the program's memory footprint, as well as the running time. The more formal name we gave it was <i>Spatially Sensitive Hierarchical Clustering</i> (SSHC), but ended up referring to it as <i>Hierarchical Hierarchical Clustering </i>which is funnier, and better reflects what's really going on.<br />
<br />
<h3>
Hierarchical Clustering in a Nutshell</h3>
<div>
The following image, taken from the Wikipedia article on HC, illustrates the basic notion rather well:</div>
<div>
<br /></div>
<div>
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/a/ad/Hierarchical_clustering_simple_diagram.svg/418px-Hierarchical_clustering_simple_diagram.svg.png" /></div>
<div>
<br /></div>
<div>
Suppose we have 6 items that we wish to cluster, and we have some metric that we can compute between subsets of those items. We get a hierarchy of clusters via the following greedy algorithm:</div>
<div>
<ol>
<li>Let each item be a cluster (with a single element)</li>
<li>Let $S$ be the set of all clusters</li>
<li>While $|S| > 1$:</li>
<ol>
<li>Find the closest pair of clusters $X, Y$ in $S$.</li>
<li>Define a new cluster $Z := X \cup Y$</li>
<li>Add $Z$ to $S$, remove $X$ and $Y$ from $S$</li>
</ol>
</ol>
<div>
So the diagram above implies the following possible sequence of cluster unions (it may be slightly different):</div>
</div>
<div>
<ol>
<li>$\{b\} \cup \{c\}$</li>
<li>$\{d\} \cup \{e\}$</li>
<li>$\{d,e\} \cup \{f\}$</li>
<li>$\{b,c\} \cup \{d,e,f\}$</li>
<li>$\{a\} \cup \{b,c,d,e,f\}$</li>
</ol>
<div>
There are a number of obvious optimizations, for example, one does not have to recompute all distances after each creation of a new cluster. Rather - only the distances that involve the new cluster.</div>
<div>
<br /></div>
<div>
<h3>
What is It Good For?</h3>
</div>
<div>
In most of the use cases that we employed, the initial atoms were triangular facets of a <a href="https://en.wikipedia.org/wiki/Polygon_mesh">3D mesh</a>. One such use case is mesh segmentation, that is the process of breaking down a 3D object into meaningful sub-parts. There's a <a href="http://pers.ge.imati.cnr.it/attene/PersonalPage/pdf/TVC06_preprint.pdf">well-known paper from 2006 by Attene et al</a> that describes such an approach. The metric chosen for distance between segments(=clusters) is how much they resemble certain primitive shapes the authors chose in advance (cylinder, cube, sphere, etc.).</div>
<div>
As can be seen in this image taken from the paper, once one has the full hierarchy of segments, this tree can be trimmed according to the number of clusters one wishes.</div>
</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgs4-V0A0V5L708sER6cisBWqoGejmCvb1YdOjCv3BbTQzNfd20fLfqwwQV0tJOZCo8P_IHK9L_9hw_StLGWQi_GrkTY40cAWvsGIEGzwD5Myx8zO_Mo6rwy7L9leWaZi3d9q0CWStBSA9A/s1600/hs_levels.PNG" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="510" data-original-width="824" height="198" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgs4-V0A0V5L708sER6cisBWqoGejmCvb1YdOjCv3BbTQzNfd20fLfqwwQV0tJOZCo8P_IHK9L_9hw_StLGWQi_GrkTY40cAWvsGIEGzwD5Myx8zO_Mo6rwy7L9leWaZi3d9q0CWStBSA9A/s320/hs_levels.PNG" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">source: "Hierarchical mesh segmentation based on fitting primitives" by Attene et al<br /><br /></td></tr>
</tbody></table>
<h3>
The Problem With HC</h3>
<div>
The natural approach we took was to consider this not as atoms where all pairwise distances needed to be considered, but as a graph, where only distances between neighboring vertices had to be considered. In the 3D mesh case - adjacent faces were represented by neighboring atoms in the HC tree. So now we simply put all the edges of the graph (and the respective distances) into a some implementation of a min-heap, and began the simple process of:</div>
<div>
<ul>
<li>Extracting the minimal edge</li>
<li>Uniting the clusters it connected</li>
<li>Updating the graph (and the edges in the heap) accordingly</li>
</ul>
<div>
This became an issue when the number of items stored in the heap was in the millions and tens of millions, which is very much the case when you get a high-quality 3D-scan of a room, for example. It turned out that operations on the heap became unbearably expensive, and the memory footprint was terrible, since we had to store this huge heap in the RAM.</div>
</div>
<div>
<br /></div>
<h3>
The Solution: HHC</h3>
<div>
We realized that changes in the HC tree were almost always very local - one computes the distance between pairs of clusters, which are neighboring nodes in the graph, and sometimes unites them in a way which affects only the neighbors of the united clusters. So why not divide and conquer?</div>
<div>
What we ended up doing is this:</div>
<div>
<ul>
<li>Break down the model very crudely into K parts, by doing something that is not far from just putting it on a grid and taking cubes. Choose K such that each part will have not so many facets in it, but not too little.</li>
<li>Run HC on each part separately until the number of clusters in the part becomes small.</li>
<li>Now unite adjacent parts until the number of clusters in each part is again not too big but not too small.</li>
</ul>
<div>
Note that this is in effect doing a Hierarchical Clustering of the parts, hence the winning name.</div>
</div>
<div>
Also note that it effectively means you work on a number of very small heaps all the time and never on a very large one. This means heap operations are now considerably cheaper, and indeed the memory footprint went down by a factor of 5 or so, and the running time was improved dramatically, on machines with slower hard drives (since less swapping was involved).</div>
<div>
<br /></div>
<h3>
The Price: Accuracy</h3>
<div>
As it often happens, the price of heuristics is that they mess up the algorithm's accuracy. In our case - it means that if the minimal edge happens to connect atoms that lie in different parts - you will get to it much later than you otherwise would have, but the reduction in running time and resource consumption made it worth our while.</div>
<div>
<br /></div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-21291249575078406202017-12-07T10:09:00.000+02:002017-12-07T10:11:51.602+02:00Fun at Work: What to Do When a Colleague Tells a Silly JokeSo, your colleague told a bad joke, and the only proper response is a rim shot sound. However, you have no drum kit within reach, so what you really need is a keyboard shortcut, shall we say Ctrl+Alt+Shift+R to play the following rim shot sound effect.<br />
<div>
<br /></div>
<br />
<audio controls="">
<source src="https://ia800501.us.archive.org/17/items/rimshot_739/rimshot.mp3" type="audio/mpeg"></source>
Your browser does not support the audio element.
</audio>
<br />
<h4>
<br /><br />So, here's how you do it in Ubuntu:</h4>
<br />
<ol>
<li>Download the above effect. Suppose you saved it to ~/rimshot.mp3</li>
<li>Install some shell tool that plays audio files. I use <i>play</i> from the <i>sox</i> package.<br />
<pre style="background-color: #eff0f1; border: 0px; color: #111111; font-family: Consolas, Menlo, Monaco, "Lucida Console", "Liberation Mono", "DejaVu Sans Mono", "Bitstream Vera Sans Mono", "Courier New", monospace, sans-serif; font-size: 13px; font-stretch: inherit; font-variant-numeric: inherit; line-height: inherit; margin-bottom: 1em; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><code style="border: 0px; font-family: Consolas, Menlo, Monaco, "Lucida Console", "Liberation Mono", "DejaVu Sans Mono", "Bitstream Vera Sans Mono", "Courier New", monospace, sans-serif; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline; white-space: inherit;">sudo apt-get install sox
sudo apt-get install sox libsox-fmt-all</code></pre>
</li>
<li>Go to System Settings -> Keyboard -> Shortcuts -> Custom Shortcuts</li>
<li>Click on the '+' sign to add a new one:<br /> <div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipsyYwMbz_XwZ03CLeUvz6GjCPP23D5VxOSmPV7C8lEiWvGtFDVHLtuofhweBieW8HZc_69OKRSP7ooxStPforXEFsv7GqH-ZgROqVw8KmvdUQ_Hj5NpC1-q1OKOeoDekFYVkG38mI7Tb6/s1600/Selection_549.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="216" data-original-width="250" height="172" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipsyYwMbz_XwZ03CLeUvz6GjCPP23D5VxOSmPV7C8lEiWvGtFDVHLtuofhweBieW8HZc_69OKRSP7ooxStPforXEFsv7GqH-ZgROqVw8KmvdUQ_Hj5NpC1-q1OKOeoDekFYVkG38mI7Tb6/s200/Selection_549.png" width="200" /></a></div>
</li>
<li><div class="separator" style="clear: both; text-align: left;">
Pick a name and have it run the command 'play' on your file:</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgpiQpYcVsWsm6mZgAPvBCp8AGk3ytBmhACcAGLkJHiRdgCYnwnTFs53gL1A9ydNtaTTrngaMIEqEctJbXj4n1sfTpBnUO3ARrx2r92PS47Tp4xcGaBQXLmYX56cp1rFgcKyqg5w6REo0ys/s1600/Selection_551.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="195" data-original-width="316" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgpiQpYcVsWsm6mZgAPvBCp8AGk3ytBmhACcAGLkJHiRdgCYnwnTFs53gL1A9ydNtaTTrngaMIEqEctJbXj4n1sfTpBnUO3ARrx2r92PS47Tp4xcGaBQXLmYX56cp1rFgcKyqg5w6REo0ys/s1600/Selection_551.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
</li>
<li><div class="" style="clear: both; text-align: left;">
Click on the word "Disabled at the end of the line of your newly created shortcut, press the key combination you like (e.g. Ctrl+Alt+Shift+R), and your done.</div>
</li>
<li><div class="" style="clear: both; text-align: left;">
Wait for a colleague to tell a silly joke.</div>
</li>
<li><div class="" style="clear: both; text-align: left;">
Hit Ctrl+Alt+Shift+R.</div>
</li>
<li><div class="" style="clear: both; text-align: left;">
Go out on a hight note.</div>
</li>
</ol>
<div>
<br /></div>
<div>
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen="" class="YOUTUBE-iframe-video" data-thumbnail-src="https://i.ytimg.com/vi/1Lkikhfdnew/0.jpg" frameborder="0" height="266" src="https://www.youtube.com/embed/1Lkikhfdnew?feature=player_embedded" width="320"></iframe></div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-76362405911017781842017-11-23T22:17:00.000+02:002017-11-24T21:36:35.794+02:00How to Utilize Computing Power That is Now "Wasted" in BlockchainAs of the time I'm writing this, the Bitcoin network consumes more electricity than 159 of the countries in the world, as pointed out <a href="https://twitter.com/noamr/status/933661809382428677">here</a>.<br />
<div style="text-align: center;">
<img height="204" src="https://pbs.twimg.com/media/DPUIJ_nW4AElZXd.jpg:large" width="400" /></div>
To be clear - all this electricity is wasted by computers trying to solve (via brute-force) some computational problem. The first computer to solve it - is rewarded by the network, transactions are validated, another block is created, and everyone move on to the next problem. Another day on the blockchain.<br />
<br />
And here's the somewhat weird part - nobody cares about the problems or the solutions. The only reason they are of interest, is that we can estimate the difficulty of solving them. <span style="background-color: yellow;">So a huge amount of energy and resources is wasted on solving problems no one cares about</span>.<br />
<br />
<h3>
<b><br /></b></h3>
<h3>
<b>Why Not Solve Important Problems Instead ?</b></h3>
I was thinking about this a few weeks ago when I thought - what if, instead of all this waste, those computers tried to solve hard problems that people <b>do</b> care about?<br />
The famous class of <a href="https://en.wikipedia.org/wiki/NP_(complexity)">NP-complete</a> problems has a few problems in it that are real-world problems (other complexity classes make sense too, of course), for example - the traveling salesman problem (aka <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem">TSP</a>). What if people who had TSP instances, because they are trying to navigate somewhere, or choose a route for some robot running erands in a large warehouse, could submit them to the blockchain and have them solved for them, using all this computing power?<br />
There is an abundance of hard real-world computational problems, many of which arise in Chemistry and Biology. I understand very little about it, but I know researchers who actually send data to be processed for several days on a super-computer, just to get results for their research.<br />
What if an entire blockchain network was, in effect, a crowd-sourcing project to solve hard computational problems? Wouldn't it be nice to put all this computing power to good use? Changing the existing Bitcoin protocol is probably out of the question at this point, but maybe a new crypto-coin, dedicated for that purpose? Maybe a different crypto-coin for different types of computational problems, the options are many, and seem interesting, at least in theory.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><img alt="תוצאת תמונה עבור computation stock photo" src="https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcTQntHhaz7EFELNjraBB-85Aikkd3XNnprKnoNklkuGip9bUc4MzA" style="margin-left: auto; margin-right: auto;" /></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><span style="font-size: xx-small;">An illustration Google image search came up with for "hard computation"</span></td></tr>
</tbody></table>
<h3>
</h3>
<h3>
The Nice Thing About This Idea</h3>
There are a few appealing notions here:<br />
<br />
<ol>
<li>Hard problems are already sorted into complexity classes. This means that hard problems of the same class are convertible to one another. We can decide that the network actually solves <a href="https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability">3SAT</a> instances, and reduce any TSP instance to a 3SAT, and then submit it to the network.</li>
<li>It means hard problems actually have economic value <b>for their hardness</b>, where in the past it was only a <b>cost</b> associated with solving it. Now - solving the problem will oddly be its own reward... which is kind of neat.</li>
<li>Maybe when submitting a problem, one can offer a reward for solving it.</li>
</ol>
<br />
<h3>
Some of The Problems</h3>
<div>
While being a nice idea, it has tons and tons of problems. Here are just a few</div>
<div>
<ol>
<li>One can game the system - submit a problem, already knowing its solution, and collect the reward by solving it. This one is probably not hard to mitigate by scrambling the problem while converting it to the format readable by the network.</li>
<li>A harder issue is how do we know an instance is hard at all to begin with? There are SAT solvers in the world exactly because there are many heuristics that cover some types of instances of the problem.</li>
<li>Do people really need exact solvers? At least for the case of NP problems - for many of them an approximated solution is good enough, so is this really filling a need that people actually have? I don't know.</li>
</ol>
<div>
<br /></div>
</div>
<div>
There are probably many other issues with this idea, but I thought it would be nice to put it out there.</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<h3>
P.S.</h3>
</div>
<div>
The world is a big place, I will be very surprised if I'm the first to come up with this...</div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-11079691894561803282017-04-26T00:16:00.001+03:002017-04-26T00:16:21.981+03:00Solving the Wrong Problem: My Take on 3DOR 2017<span style="font-family: Arial, Helvetica, sans-serif;">This week I attended the 10th <a href="http://liris.cnrs.fr/eg3dor2017/">3D Object Recognition</a> workshop, which was held as preliminary part of <a href="http://www.eurographics2017.fr/">EuroGraphics</a>. To</span><span style="font-family: Arial, Helvetica, sans-serif;"> sum up my impression from the vast majority of the works, I felt that <b>the academia is working on the wrong problems</b>.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Arial, Helvetica, sans-serif;">Specifically - much of the research presented (though not all) dealt with <a href="https://en.wikipedia.org/wiki/Computer-aided_design">CAD</a> models, indexing them, analyzing them, finding similarities, descriptors, and transformations for them. This is, in my opinion, an approach that has lost touch with the actual state of data in the real world, and is driven mostly by cultural reasons such as the existence of previous work to rely on and CAD-based benchmarks to run. </span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEggTZqGPUjp1TQORLWpWjZV0c44rnHDcb7QJwsWta7gHTPbtVlozQVraCgqPm5f8NEZdoOb6ArUKhTyvBJNDg_hVQ5vUH7iaDpXSnRFvH2MVizgUHuhm2zXdhTdC8PBBEmR1zHRgctq3eCj/s1600/scanned_vs_cad.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="185" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEggTZqGPUjp1TQORLWpWjZV0c44rnHDcb7QJwsWta7gHTPbtVlozQVraCgqPm5f8NEZdoOb6ArUKhTyvBJNDg_hVQ5vUH7iaDpXSnRFvH2MVizgUHuhm2zXdhTdC8PBBEmR1zHRgctq3eCj/s320/scanned_vs_cad.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Scanned and CAD chair (not the same chair, of course)</td></tr>
</tbody></table>
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">In the past two years, we have seen an <b>increasing number of 3D scanners and depth cameras</b>, ranging from low quality devices - costing just a few hundreds of dollars - to expensive, high resolution, industrial devices, that produce impressive results. The tables have turned, and scanned data, which was a small minority, can now be easily generated in large quantities. This data ranges from <a href="https://www.cs.york.ac.uk/cvpr/pronto/">lab-scanned toys</a>, to huge urban scenes scanned by drones, nevertheless, the majority of the algorithmic works presented in 3DOR dealt with CAD models. I believe that there are two main reasons for that:</span><br />
<br />
<ol>
<li><span style="font-family: Arial, Helvetica, sans-serif;">There are <b>almost no tagged scanned data sets</b>, and none of substantial size (<a href="http://people.sutd.edu.sg/~saikit/projects/sceneNN/">SceneNN</a>, perhaps the best work so far, has only 100 scenes).</span></li>
<li><span style="font-family: Arial, Helvetica, sans-serif;"> Most existing methods are <b>tailored to CAD</b> models, and are thus sensitive to one or all of the following traits, common in scanned data:</span></li>
<ol>
<li><span style="font-family: Arial, Helvetica, sans-serif;">High-frequency noise due to scanner accuracy issues.</span></li>
<li><span style="font-family: Arial, Helvetica, sans-serif;">Incomplete models due to occlusion or simply unscanned sides of the object.</span></li>
<li><span style="font-family: Arial, Helvetica, sans-serif;">Holes.</span></li>
<li><span style="font-family: Arial, Helvetica, sans-serif;">Open boundaries.</span></li>
</ol>
</ol>
<div>
<span style="font-family: Arial, Helvetica, sans-serif;">Reason (1) becomes even more of an issue to anyone wishing to follow the deep learning trend, as it - as most ML approaches - requires tagged data sets of considerable size. </span></div>
<div>
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiezng8NN6FLAQtK3uraWsSNH_6Iga_HYwT-_bRzc9LRHKGvSwE_-CIx8D0oJPpT6SzkSRiCbyqZgI1vfUY6WQxnEiJMUpCIbiy9goOgl4rKW-vsAF1i8KKGXgvngKciUcsQEdqSNUGnkxB/s1600/049_segmented.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiezng8NN6FLAQtK3uraWsSNH_6Iga_HYwT-_bRzc9LRHKGvSwE_-CIx8D0oJPpT6SzkSRiCbyqZgI1vfUY6WQxnEiJMUpCIbiy9goOgl4rKW-vsAF1i8KKGXgvngKciUcsQEdqSNUGnkxB/s320/049_segmented.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">A scanned scene from SceneNN data set</td></tr>
</tbody></table>
<div>
<br /></div>
<div>
<span style="font-family: Arial, Helvetica, sans-serif;">I believe that there are two types of data the academia should address seriously in the upcoming year or two - scanned small scale data, such as singular models and indoor scenes, and scanned large scale data, such as entire buildings, and streets. With the <a href="https://9to5mac.com/2017/02/21/kgi-oled-iphone-8-to-feature-revolutionary-3d-sensing-front-camera-detect-depth-for-games-and-facial-recognition/">upcoming depth camera in iPhone8</a>, we can expect a proliferation of the former, while the latter will be the result of increasing use of industrial scanners in security, construction, and drones.</span></div>
<div>
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span></div>
<div>
<span style="font-family: Arial, Helvetica, sans-serif;">In my experience, algorithms that worked well with CAD models, more often than not prove to be useless for scanned data. This is bad news for reusing much of previous work as-is, but is also good news, as it brings hope that we'll see exciting new approaches to 3D retrieval and recognition in upcoming years, that will truly have an effect on technology being developed, and thus on people's lives.</span></div>
<br />
<br />Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-55702633417450953592017-03-28T22:51:00.000+03:002017-03-28T22:51:07.218+03:00The UX of Work Emails<span style="font-family: Arial, Helvetica, sans-serif;">The polite way to get a co-worker's attention to discuss an issue without bothering someone, is to send an email or some other form of asynchronous communication.</span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://img.memesuper.com/9a947f55ff60dae6bd7b0c97978469ab_and-now-we-wait-now-we-wait-memes_180-159.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><span style="font-family: Arial, Helvetica, sans-serif;"><img border="0" src="https://img.memesuper.com/9a947f55ff60dae6bd7b0c97978469ab_and-now-we-wait-now-we-wait-memes_180-159.jpeg" /></span></a></div>
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Arial, Helvetica, sans-serif;">In recent years I have found that it is very useful to think, when writing an email, <b>more like a UX designer than a writer</b>. This is because an email is meant to induce behavior, specifically, in addition to getting my message across, I want a quick response.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Arial, Helvetica, sans-serif; font-size: large;">So when composing an email I...</span><br />
<ol>
<li><span style="font-family: Arial, Helvetica, sans-serif;"><b>Use bullet points:</b> they make replying to different points in the email much easier, and requires less explaining when doing so.</span></li>
<li><span style="font-family: Arial, Helvetica, sans-serif;"><b>Highlight important stuff</b>, and in general, make scheming through it easy and informative. </span></li>
<li><span style="font-family: Arial, Helvetica, sans-serif;"><b>Use images when I can</b>, because people love images and respond to them more than to text (as any Facebook page manager will tell you). This is not to say I start digging through image banks, rather - I use plenty of screenshots all the time (I use <a href="http://shutter-project.org/">Shutter</a> on Ubuntu and the <a href="https://support.microsoft.com/en-us/help/13776/windows-use-snipping-tool-to-capture-screenshots">Windows Snipping Tool</a> on Win7). And yes, the occasional meme, if I have a big block of text with no relevant image to accompany it.</span></li>
<li><span style="font-family: Arial, Helvetica, sans-serif;">For a long email - <b>start it with a tl;dr version</b> of it, summarizing the whole thing in a sentence or two. This works in a similar way to a news story's headline - it gives the appropriate framing and context.</span></li>
<li><b style="font-family: Arial, Helvetica, sans-serif;">Use the subject line to help recipients sort through their emails</b><span style="font-family: Arial, Helvetica, sans-serif;">. I believe that the subject line is usually ignored when actually reading an email. It is read when people sort through a long list of emails, or get a notification. It therefore should be short, and useful in reminding the reader how this email differs from others on the list.</span></li>
<li><span style="font-family: Arial, Helvetica, sans-serif;"><b>Use code that looks like code</b>. I use <a href="https://tohtml.com/colorer.php?type=cpp/">this website</a> to format the code parts of an email and make them look like code. It helps readability, and looks cool.<br /><pre style="background: rgb(255, 255, 255);"><span style="color: maroon; font-weight: bold;">int</span> RandomInt<span style="color: #808030;">(</span><span style="color: #808030;">)</span> <span style="color: purple;">{</span>
<span style="color: maroon; font-weight: bold;">return</span> <span style="color: #008c00;">4</span><span style="color: purple;">;</span>
<span style="color: purple;">}</span></pre>
</span></li>
<li><span style="font-family: Arial, Helvetica, sans-serif;"><b>Make it cross-platform. </b>People read their emails on various devices, so I try to be very conservative with attachments, and limit them to PDFs and other easily-read formats, when possible. When I have some 3D model in a proprietary format that illustrates my point - I may send it, but I send an image of it as well, so that colleagues can make sense of it even if they are on the train, using their phone to read emails.</span></li>
</ol>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://www.mememaker.net/static/images/memes/4393744.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="239" src="https://www.mememaker.net/static/images/memes/4393744.jpg" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">An image. Yeah, I know, amazing.</td></tr>
</tbody></table>
<br /><div>
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span></div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-74885750718022218152017-01-31T10:29:00.000+02:002017-03-28T17:41:31.006+03:00Generate a Puzzle for Your Math Class in 5 Minutes<div class="separator" style="clear: both; text-align: center;">
<a href="http://s3.amazonaws.com/tpt-uploads-production/uploads/Untitled-223.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><span style="color: black; font-family: "arial" , "helvetica" , sans-serif;"><img border="0" src="http://s3.amazonaws.com/tpt-uploads-production/uploads/Untitled-223.jpg" height="86" width="320" /></span></a></div>
<br />
<span style="font-family: "arial" , "helvetica" , sans-serif;"><span style="font-family: inherit;">There's a famous puzzle, often referred to as the <a href="https://en.wikipedia.org/wiki/Zebra_Puzzle">Zebra Puzzle</a>. It goes something like this:</span></span><br />
<span style="font-family: "arial" , "helvetica" , sans-serif;"><br /></span>
<br />
<ol>
<li><span style="font-family: "arial" , "helvetica" , sans-serif;">There are five houses.</span></li>
<li><span style="font-family: "arial" , "helvetica" , sans-serif;">The Englishman lives in the red house.</span></li>
<li><span style="font-family: "arial" , "helvetica" , sans-serif;">The Spaniard owns the dog.</span></li>
<li><span style="font-family: "arial" , "helvetica" , sans-serif;">...</span></li>
<li><span style="font-family: "arial" , "helvetica" , sans-serif;">...<br />...</span></li>
</ol>
<span style="font-family: "arial" , "helvetica" , sans-serif;">Here follow many more facts detailing who lives next to whom, and which pets they own and so on, until the final question is given: <b>Who owns the zebra?</b></span><br />
<span style="font-family: "arial" , "helvetica" , sans-serif;"><span style="font-family: inherit;"></span>
</span>
<span style="font-family: "arial" , "helvetica" , sans-serif;">There is no quick and clean solution for this puzzle that involves a single big "Aha!" moment, but rather a series of steps, making ad-hoc assumptions, and trying to see if they sit well with each other and with the facts given, until a solution is found.</span><br />
<span style="font-family: "arial" , "helvetica" , sans-serif;"><br /></span>
<br />
<h3>
<span style="font-family: "arial" , "helvetica" , sans-serif; font-size: large;">Constraint Satisfaction Problems</span></h3>
<div>
<span style="background-color: white; font-family: "arial" , "helvetica" , sans-serif;">This puzzle belongs to a class of problems called </span><a href="https://en.wikipedia.org/wiki/Constraint_satisfaction_problem" style="font-family: arial, helvetica, sans-serif;">Constraint Satisfaction Problems</a><span style="background-color: white; font-family: "arial" , "helvetica" , sans-serif;">, or CSP. </span></div>
<div>
<span style="color: #252525; font-family: inherit;"><span style="background-color: white; font-family: "arial" , "helvetica" , sans-serif;">While CSPs in general are hard to solve, even for computers, small instances of them are both easy to create, and make for popular puzzles. An example of such puzzle is <a href="https://en.wikipedia.org/wiki/Sudoku">Sudoku</a>.</span></span></div>
<div>
<br /></div>
<h3>
<span style="color: #252525; font-family: inherit; font-size: x-small;"><span style="background-color: white; font-family: "arial" , "helvetica" , sans-serif; font-size: large;">Floors Puzzles</span></span></h3>
<div>
<span style="background-color: white; color: #252525; font-family: "arial" , "helvetica" , sans-serif;">Here's a really easy CSP I just came up with:</span></div>
<div>
<ol>
<li><span style="color: #252525; font-family: inherit;"><span style="background-color: white; font-family: "arial" , "helvetica" , sans-serif;">There are 4 floors in the building.</span></span></li>
<li><span style="color: #252525; font-family: inherit;"><span style="background-color: white; font-family: "arial" , "helvetica" , sans-serif;">The rooster does not live on the top floor.</span></span></li>
<li><span style="color: #252525; font-family: inherit;"><span style="background-color: white; font-family: "arial" , "helvetica" , sans-serif;">The cat lives two floors under the lion.</span></span></li>
<li><span style="color: #252525; font-family: inherit;"><span style="background-color: white; font-family: "arial" , "helvetica" , sans-serif;">the dog lives in a lower floor than the rooster.</span></span></li>
</ol>
<div>
<span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif;"><br /></span></div>
<div>
<span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif; font-size: large;"><b>Which animal lives on which floor?</b></span><br />
<span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif;">Spoiler alert: if you like to solve this puzzle, do so now, since the next section will reveal the solution. The puzzle is, by the way, so easy that I suggest you solve it yourself anyway, just to get an understanding of what it feels like.</span></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://previews.123rf.com/images/sarahjanet/sarahjanet1111/sarahjanet111100018/11463867-Colourful-rooster-American-Brown-Leghorn-rooster-on-white-background-Stock-Photo.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><span style="color: black; font-family: "arial" , "helvetica" , sans-serif;"><img border="0" src="http://previews.123rf.com/images/sarahjanet/sarahjanet1111/sarahjanet111100018/11463867-Colourful-rooster-American-Brown-Leghorn-rooster-on-white-background-Stock-Photo.jpg" height="200" width="198" /></span></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><span style="font-family: "arial" , "helvetica" , sans-serif; font-size: small;">An animal that does not live on the top floor</span></td></tr>
</tbody></table>
<div>
<span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif;"><br /></span></div>
<div>
<span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif;">This is a nice puzzle for 10 year old students. A similar puzzle with 3 floors will be suitable for 7 year olds, and naturally, more floors can make it increasingly harder to solve.</span></div>
</div>
<div>
<span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif;"><br /></span></div>
<div>
<span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif;"><br /></span></div>
<h3>
<span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif; font-size: large;">Create Your Own Floors Puzzle in 5 Minutes</span></h3>
<div>
<ul>
<li><span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif;">Choose animals and number of floors. </span></li>
</ul>
<ul>
<li><span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif;">Draw a diagram of which animal goes where, e.g.:</span></li>
</ul>
<ul>
<li><span style="font-family: "arial" , "helvetica" , sans-serif;">Write down rules that describe your building - e.g. "the dog lives 3 floors below the lion".</span></li>
</ul>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjk8loP-Z2jq8zoRJHTuOHfWJW2ONWv9xD3KJMqxnsKXIXzPW7eVEjbg35Gr86sV3OC50tG-21yIbzV5QphRg0chm-kEv7stPmC6ctGFKajezLMxtXw7bvIdPSh2PgYOxh-wv_iaoe-W0y5/s1600/4floors.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><span style="color: black; font-family: "arial" , "helvetica" , sans-serif;"><img border="0" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjk8loP-Z2jq8zoRJHTuOHfWJW2ONWv9xD3KJMqxnsKXIXzPW7eVEjbg35Gr86sV3OC50tG-21yIbzV5QphRg0chm-kEv7stPmC6ctGFKajezLMxtXw7bvIdPSh2PgYOxh-wv_iaoe-W0y5/s200/4floors.jpg" width="150" /></span></a></div>
<div class="separator" style="clear: both; text-align: left;">
</div>
<span style="font-family: "arial" , "helvetica" , sans-serif;"><br /></span>
<br />
<div>
<span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif;"><br /></span></div>
<div>
<span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif;">Over a certain number - some of the rules will be redundant, that is - the puzzle may be solved even if those rules are not given, but don't worry about that. As a rule of thumb - the number of rules should be slightly smaller than the number of floors.</span></div>
</div>
<div>
<br /></div>
<h3>
<span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif; font-size: large;">Checking Solutions</span></h3>
<div>
<span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif;">Note that it may be the case that there will be correct solutions that are not identical to the one you used to write the puzzle, but that's okay, because the puzzle is about finding a solution, not the solution. While it is possible, in principle, to check whether the rules you chose have more than one solution, it will probably take more than the 5 minutes promised in the title of this post... </span><span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif;"></span><br />
<span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif;"><br /></span>
<span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif;">So there you have it - generate a puzzle for your math class in five minutes or less. Enjoy.</span><br />
<span style="font-family: "arial" , "helvetica" , sans-serif;"><span style="color: #252525; font-family: inherit;"><br /></span>
<span style="color: #252525; font-family: inherit;"><br /></span>
<span style="color: #252525; font-family: inherit;"><br /></span>
<span style="color: #252525; font-family: inherit; font-size: large;"><b>P.S.</b></span></span><br />
<span style="color: #252525; font-family: "arial" , "helvetica" , sans-serif;">On a less-practical note, about a year ago I wrote a post tying <a href="http://www.shirpeled.com/2016/01/np-complete-problems-as-online-math.html">"good" puzzles to NP-complete problems</a>, and this current post is really just another example of that.</span></div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-34828382628891561822016-10-05T11:16:00.003+03:002016-10-07T22:09:39.684+03:00Notes from my "Intro to Information Theory" time<br />
For two years, starting October 2010, I was a teaching assistant in the Introduction to Information Theory course at the Hebrew University, which was taught by <a href="http://www.cs.huji.ac.il/~werman/">Prof. Michael Werman</a>, and the following year by <a href="http://www.cs.huji.ac.il/~benor/">Prof. Michael Ben-Or</a>.<br />
During that time, I a weekly two-hour tutorial, which was sometimes an extension of what was discussed in the lecture, and sometimes (as in the case of error correction codes) simply dealt with other topics.<br />
<br />
After writing <a href="http://www.shirpeled.com/2016/09/check-digit-poor-mans-error-correction.html">the previous post on check digits</a>, I dug up the old notes, and found them to be quite helpful in refreshing my memory on the matter.<br />
<br />
So, hoping it will prove helpful to others as well, and under an assumption that I'm not violating anyone's copyrights, here they are:<br />
<br />
<iframe height="480" src="https://drive.google.com/file/d/0B5rBtG_Lw_9lT2NIbFp6LVlyV28/preview" width="480"></iframe>Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-46957606560171235132016-09-27T16:54:00.000+03:002016-09-27T16:56:15.795+03:00Check digit: the poor man's error correction code<h3>
The Israeli ID number and the Luhn Algorithm</h3>
<div>
<br /></div>
The Israeli ID number, assigned to every Israeli resident or citizen, has 9 digits: the left 8 digits are the actual number, whereas the right-most digit is a check digit.<br />
The check-digit is computed using the <a href="https://en.wikipedia.org/wiki/Luhn_algorithm">Luhn algortihm</a> which is:<br />
1. Multiply digits in even places by 2.<br />
2. Add the digits in the odd places (not including the check-digit itself) to the sum of digits of numbers you got in (1).<br />
3. Set the 9th digit to be the number required to complete the sum from (2) to the next multiple of 10.<br />
<br />
<h4>
For example</h4>
<div>
<br /></div>
The number 99035612 will be processed as follows:<br />
9 - odd place, leave as is -> 9<br />
9 - even place, multiply by 2 and take sum of digits -> 18 -> 9<br />
0 - odd place, leave as is -> 0<br />
3 - even place - multiply by 2 -> 6<br />
5 - odd place, leave as is -> 5<br />
6 - even place, multiply by 2 and take sum of digits -> 12 -> 3<br />
1 - odd place, leave as is -> 1<br />
2 - even place, multiply by 2 -> 4<br />
<br />
sum all the above to obtain 37, which requires adding 3 to complete it to the nearest multiple of 10, thus 3 is chosen to be the check digit.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjck0lhgp7zwV91IlPh6XDDqDaRhUGqaCKL4XS0SPW52O7iHX01-xyfxklIUtKdH1AwuspIwfI0hd_ZwRT1_G2bHJEZJSUdFcMhZA-FHc_cl0cdZutuTuXgtR8BkNyP1qPtI-ZXZST-oFHf/s1600/smart+id.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="197" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjck0lhgp7zwV91IlPh6XDDqDaRhUGqaCKL4XS0SPW52O7iHX01-xyfxklIUtKdH1AwuspIwfI0hd_ZwRT1_G2bHJEZJSUdFcMhZA-FHc_cl0cdZutuTuXgtR8BkNyP1qPtI-ZXZST-oFHf/s320/smart+id.jpg" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Had this been a valid ID, the check digit would have been 2 (not 9)<br />
(image source: nbn.org.il)</td></tr>
</tbody></table>
<br />
<h4>
</h4>
<h4>
Why all the fuss?</h4>
<div>
<br /></div>
The most obvious idea for a check digit would be sum of digits modulo 10, so why all this odd-even business? It turns out it is intended to catch the very common transcription mistake of transposing two adjacent digits, and by the by also catches most of the cases of twin digits mistakes (i.e. aa->bb). In addition, it is simple, and therefore realistically usable for clerks in the pre-computers age.<br />
<br />
<br />
<h3>
</h3>
<h3>
</h3>
<h3>
The Luhn Algorithm's "unfixable" fault</h3>
<br />
Interestingly, the Luhn algorithm cannot detect all transpositions of two adjacent digits. Specifically, the sequences 09 and 90 both contribute 9 to the sum computed in step (2) so this transposition will not cause a change in the check digit and will not be detected.<br />
So I grabbed a piece of paper and tried to come up with a similar algorithm that will catch *all* transpositions, only to find out that - if we restrict ourselves to similar algorithms (wanting to preserve the simplicity of the computation) - there is no such solution.<br />
To be precise, let $f:\{0,...,9\}\rightarrow\{0,...,9\}$ be a permutaion, then there exist $a \neq b \in \{0,...,9\}$ such that $f(a) + b \equiv a + f(b) (\textrm{mod} 10)$.<br />
My friend, Lior Yanovski, suggested an elegant proof for this:<br />
Assume, by way of negation, that $a\neq b \Rightarrow f(a) + b \not\equiv a + f(b) (\textrm{mod} 10)$.<br />
It follows that $ f(a) - a \not\equiv f(b) - b (\textrm{mod} 10)$, which means the function $g(x) := f(x) - x (\textrm{mod} 10)$ is a permutation.<br />
If we sum $g(x)$ over $x$ we obtain $\sum_x f(x) - \sum_x x \equiv 0 (\textrm{mod} 10)$ simply because both $f$ and the identity are permutaions adding up to 55. On the other hand, if $g$ is indeed a permutation - summing up its values would give $5 (\textrm{mod} 10)$, i.e., a contradiction!<br />
So if we were to look for a function to replace the "multiply by 2 and take sum of digits" from the Luhn algorithm, while maintaining the rest of the algorithm's structure, and covering all adjacent digits transpositions - we won't find one.<br />
<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhj5y7MDdIWp_VLCVSvdmVPJl63_HWCR9k6H5RNaePXQtfRFF9TVVomZVyI4bnpKL8AunbVRtjpuWDo_I7iyo3IqOZ4GONB8CeZ_dLDmFyP1-X8tu4TOvlxkXkzV7Ft3dch06WvMzVHFLrD/s1600/Hans_Luhn.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhj5y7MDdIWp_VLCVSvdmVPJl63_HWCR9k6H5RNaePXQtfRFF9TVVomZVyI4bnpKL8AunbVRtjpuWDo_I7iyo3IqOZ4GONB8CeZ_dLDmFyP1-X8tu4TOvlxkXkzV7Ft3dch06WvMzVHFLrD/s200/Hans_Luhn.png" width="168" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Hans Peter Luhn 1896-1964<br />
(Image source: asist.org)</td></tr>
</tbody></table>
<h3>
</h3>
<h3>
</h3>
<h3>
<br /></h3>
<h3>
Fix #0: Find only transpositions</h3>
<div>
<br />
We could multiply every digit by its place, and take this sum modulo 10, i.e. define the check digit to be $\sum_{i=1} ^n i \cdot a_i (\textrm{mod} 10)$. This will detect all adjacent transpositions, but it will do a very poor job in detecting single digit errors. Seeing how 10 shares divisors with most of the numbers in $0,...,9$, multiplying by either of them and taking the remainder modulo 10 discards some information. For example $5\cdot x$ will always be either 0 or 5 (assuming $x$ is an integer). This means that a random error in the fifth digit will cause a change in the check digit only 50% of the times, and somewhat similar problems arise with digits in even places.<br />
<br /></div>
<h3>
Fix #1: Abandon base 10</h3>
<br />
A closer inspection would reveal that the proof of the Luhn algorithm's fault relies heavily on the fact that 10 is an even number, since the expression $\sum_{i=1} ^n i (\textrm{mod} n)$ is $\frac n 2$ for even values of $n$ but $0$ for odd values of $n$. If we had used an odd base for this entire computation - things would be different, but perhaps less intuitive to compute by hand.<br />
Indeed, some check digit systems, such as the one used in ISBN 10 (for bank transfers) employ a similar trick with 11 as the base of the modular operations.<br />
<h3>
</h3>
<h3>
</h3>
<h3>
<br /></h3>
<h3>
Fix #2: Abandon simplicity</h3>
<br />
If we allow yet more complex computations, then there are some algorithms that produce a check digit that will detect all single-digit errors as well as all transpositions of adjacent digits. The oldest one probably being <a href="https://en.wikipedia.org/wiki/Verhoeff_algorithm">Verhoeff algorithm</a>, from 1967. Verhoeff, who is now retired and an avid creator of math-inspired sculptures, took an empirical approach, by analyzing data from the Dutch postal service, classifying and counting common errors. He followed to create a code that not only detects all adjacent digits transpositions and single digit errors, but also detects errors based on phonetic similarities in dutch, such as confusing 15 (vijftien) with 50 (vijftig).<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh4AMB_Bd93RwgSamEkOlLoLgXEoCfEFYYcSWs_rtpwYyvKy74AgEEwYXMcQCg4TPD4A0Na9KWzXcV8Yj5D0rwIcEkK4W6z54h7DSm-FE3a896b4IwLB1ckmn8Hib2ZVdeXnM990umD_07Q/s1600/Verhoeff.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh4AMB_Bd93RwgSamEkOlLoLgXEoCfEFYYcSWs_rtpwYyvKy74AgEEwYXMcQCg4TPD4A0Na9KWzXcV8Yj5D0rwIcEkK4W6z54h7DSm-FE3a896b4IwLB1ckmn8Hib2ZVdeXnM990umD_07Q/s320/Verhoeff.jpg" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Jacobus Verhoeff, with his sculptures<br />
(Image source: groene.nl)</td></tr>
</tbody></table>
More recently (2004), <a href="https://en.wikipedia.org/wiki/Damm_algorithm">H. Michael Damm proposed an algorithm</a> that is slightly less complicated (but only very slightly), and has similar qualities.<br />
<br />
<br />
<br />
<h2>
</h2>
<h2>
Some tests</h2>
<div>
<br />
Running some quick scripts in python, I wanted to find out how well the <b>Luhn</b> algorithm, the <b>Damm</b> algorithm (I skipped implementing Verhoeff's) and the algorithm proposed in <b>Fix #0</b> above fare. I also added two more algorithms for fun:<br />
<br /></div>
<div>
<ul>
<li><b>Naive</b> - $|\sum_{i = 1} ^{n - 1} (a_i - a_{i+1})| (\textrm{mod} 10)$.</li>
<li><b>RandomTable</b> - the Damm algorithm is based on using a table of a quasi group of order 10. So I wondered how well a random table would do, so I took 10 random permutations, one above the other, and used it in the same way the Damm algorithm is implemented.</li>
</ul>
<div>
<br />
The errors introduced were:<br />
<br /></div>
</div>
<div>
<ul>
<li>Adjacent transposition: 12345 -> 12435</li>
<li>One-over transposition: 12345 -> 14325</li>
<li>Random 2-digit transposition: 12345 -> 42315</li>
<li>Single digit random error: 12345 -> 19345</li>
<li>Two-digit random errors: 12345 -> 22346</li>
<li>3, 4, 5... 9 random errors.</li>
</ul>
<div>
<br />
The table shows the miss rate. Note that 10% miss rate is the magic number that they all converge to, given enough noise. This is because if we were to choose some random function $f:(0...9)^n\rightarrow\{0...9\}$ then for two random inputs $x \neq y \in (0...9)^n$, clearly $Pr(f(x) \neq f(y)) = 0.9$. A random function on random data has a 10% miss rate, so useful algorithms try to get significantly better than 10% for specific cases, without causing spikes in the miss rate for other errors.<br />
<br /></div>
</div>
<div>
<br /></div>
<style type="text/css">
.tg {border-collapse:collapse;border-spacing:0;border-color:#999;}
.tg td{font-family:Arial, sans-serif;font-size:14px;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:#999;color:#444;background-color:#F7FDFA;}
.tg th{font-family:Arial, sans-serif;font-size:14px;font-weight:normal;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:#999;color:#fff;background-color:#26ADE4;}
.tg .tg-qw6t{font-size:14px;font-family:"Comic Sans MS", cursive, sans-serif !important;;vertical-align:top}
.tg .tg-yw4l{vertical-align:top}
.tg .tg-9hbo{font-weight:bold;vertical-align:top}
</style>
<br />
<table class="tg">
<tbody>
<tr>
<th class="tg-qw6t">error \ algo</th>
<th class="tg-yw4l">Luhn</th>
<th class="tg-yw4l">Damm</th>
<th class="tg-yw4l">Fix #0</th>
<th class="tg-yw4l">Naive</th>
<th class="tg-yw4l">Random</th>
</tr>
<tr>
<td class="tg-9hbo">Adjacent transposition</td>
<td class="tg-yw4l">2%</td>
<td class="tg-9hbo">0%</td>
<td class="tg-9hbo">0%</td>
<td class="tg-yw4l">70%</td>
<td class="tg-yw4l">34%</td>
</tr>
<tr>
<td class="tg-9hbo">One-over transposition</td>
<td class="tg-yw4l">87%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">9%</td>
<td class="tg-yw4l">63%</td>
<td class="tg-yw4l">22%</td>
</tr>
<tr>
<td class="tg-9hbo">Random transposition</td>
<td class="tg-yw4l">45%</td>
<td class="tg-yw4l">8%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">53%</td>
<td class="tg-yw4l">27%</td>
</tr>
<tr>
<td class="tg-9hbo">1-digit error</td>
<td class="tg-9hbo">0%</td>
<td class="tg-9hbo">0%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">67%</td>
<td class="tg-yw4l">36%</td>
</tr>
<tr>
<td class="tg-9hbo">2-digit error</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">44%</td>
<td class="tg-yw4l">25%</td>
</tr>
<tr>
<td class="tg-9hbo">3-digit error</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">27%</td>
<td class="tg-yw4l">18%</td>
</tr>
<tr>
<td class="tg-9hbo">4-digit error</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">17%</td>
<td class="tg-yw4l">14%</td>
</tr>
<tr>
<td class="tg-9hbo">5-digit error</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">12%</td>
<td class="tg-yw4l">11%</td>
</tr>
<tr>
<td class="tg-9hbo">6-digit error</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">11%</td>
</tr>
<tr>
<td class="tg-9hbo">7-digit error</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
</tr>
<tr>
<td class="tg-9hbo">8-digit error</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
</tr>
<tr>
<td class="tg-9hbo">9-digit error</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
<td class="tg-yw4l">10%</td>
</tr>
</tbody></table>
<br />
<div>
<br /></div>
<h2>
</h2>
<h2>
<br /></h2>
<h2>
Error correction codes for edit distance?</h2>
<div>
<br />
So, while this is a pre-computing-age problem, that is <a href="https://www.youtube.com/watch?v=luef1H24hU8">nowadays</a> a toy problem, it highlights an interesting issue: the standard error-correction codes treat a very specific domain, where errors are modeled as noisy coordinates in a vector, and so the notion of distance is just the <a href="https://en.wikipedia.org/wiki/Hamming_distance">Hamming distance</a>. Are there good codes for domains where the distance is more complicated, such as <a href="https://en.wikipedia.org/wiki/Levenshtein_distance">Levenshtein distance</a>?</div>
<div>
<br /></div>
<div>
<br />
It turns out that once we tweak the noise model, we quickly step into the realm of open problems. While for the <a href="https://en.wikipedia.org/wiki/Binary_erasure_channel">Binary Erasure Channel</a>, which models noise as flipping bits, we've known the capacity ever since it was introduced, for the <a href="https://en.wikipedia.org/wiki/Deletion_channel">Deletion Channel</a>, which models noise as removing a bit from the input string, the capacity is still an open problem.</div>
<div>
To summarize - edit distance correction codes are an interesting idea, but I doubt we'll see any progress in them soon, as even the fundamental questions of Information Theory turn out to be extremely challenging in this domain.</div>
<div>
<br /></div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-50876951225348460062016-08-02T08:27:00.000+03:002016-08-02T08:28:41.259+03:00Pokémon GO meets FarmVille: a game pitchSo, here's a sketch for a mobile location-based farming simulation game I thought of:<br />
<br />
<h3>
Elevator pitch:</h3>
<div>
<br /></div>
<b>Pokémon GO meets FarmVille</b>: players walk around in the real world, where real world locations have in-game roles. The players grow crops, and harvest them, and since this is the real world - they can 'own' land.<br />
<br />
<br />
<h3>
Basic principles:</h3>
<br />
<ul>
<li><b>Each player can "own" portions of land</b> in the real world, and use it to grow crops.</li>
<li><b>Crops can be sold in markets,</b> which are also places in the real world (kind of like PokéStops).</li>
<li>Land can be bought and sold, workers can be hired, however, a player <b>must visit his/her land often</b> enough, otherwise <b>it becomes abandoned</b>, in which case other players can buy it cheaply.</li>
</ul>
The latter is crucial to the game, as it plays to users habits (making it easy to buy and maintain land next to home / work, or on the way there), and prevents early adopters from hoarding land.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjGTSZWhoc1CO7SU0NbO9HxqB94ShWV2zqsvHsWg5MGnRDWUcUclg_cbJ-uI4TU6Phn-t87N7gQtF4X1mZbXAK3UCCwNOps8LNnEgrW7CQcDKwHsBXMTNYXIFmybGgDmBkNpKfnFH2nJ4pb/s1600/pokemongomeetsfarmville.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjGTSZWhoc1CO7SU0NbO9HxqB94ShWV2zqsvHsWg5MGnRDWUcUclg_cbJ-uI4TU6Phn-t87N7gQtF4X1mZbXAK3UCCwNOps8LNnEgrW7CQcDKwHsBXMTNYXIFmybGgDmBkNpKfnFH2nJ4pb/s320/pokemongomeetsfarmville.png" width="266" /></a></div>
<br />
<br />
<h3>
Gameplay:</h3>
<div>
<br /></div>
<h4>
Buying land</h4>
Each player starts the game with some in-game money, no workers, and some basic seeds (wheat, corn, or rice, depending on the climate).<br />
Walking around in the real world, the player can see which pieces of land are available for buying, and for how much. Abandoned pieces of land are priced by their size, and the price of land owned by other users is determined by that user, who can also choose "not selling". Any player can bid for any piece of land they pass by, as long as they have the money. Selling land does not require the player to be present at the spot.<br />
<br />
<h4>
Working the land</h4>
Having bought a new piece of land, the player has to work the land and prepare it for seeding. If the player has hired workers - they can be left there to do the job, but otherwise - the player has to stand close to the land for a minute, tapping the screen of the mobile device, thereby "working the land".<br />
<br />
<h4>
Crops </h4>
Seeds for various crops can be bought at any market and planted in the land, requiring the player to visit the land in order to do so. Similarly to FarmVille, the crops take time to grow, and can rot if not harvested in time. Harvesting, like any type of work on the land, can be done by the player standing next to it and tapping the screen, or by workers left there for that purpose.<br />
<br />
<h4>
Markets</h4>
These are places in the real world, that play a part in the game but cannot be bought or sold and are determined by the system, similarly to PokéStops. Standing close to a market, a player can buy seeds, machinery, sell crops, and hire workers (for a predetermined time) with various levels of expertise.<br />
<br />
<h4>
Weather and Location</h4>
Crops can be grown only in places where the weather makes sense for it to happen, or in greenhouses, and real-world weather affects the virtual crops and their prices, so a storm may kill some of the crops, but raise prices.<br />
<br />
<h4>
Advancement</h4>
Players advance through levels through experience points that are gained by playing the game (growing crops, buying land, harvesting, hiring help, etc.).<br />
Various achievements can be unlocked, such as managing 10 workers at once, growing exotic crops, owning a lot of land.<br />
<br />
<h4>
Social aspect?</h4>
Not sure, I haven't thought about it much, since I really don't like the way FarmVille did it...<br />
<div>
<br /></div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com1tag:blogger.com,1999:blog-642244788469558745.post-56953656573030587762016-07-10T08:26:00.000+03:002016-07-10T08:26:24.101+03:00My Perspective on Prisma: It's Burning Money FastFor the past couple of weeks - the photo-processing app Prisma has been gaining huge attention, and rightfully so - they use <a href="https://en.wikipedia.org/wiki/Convolutional_neural_network">CNNs</a> (+3 points for trendy buzz word) and AI (+2.5 points) to process its users' photos and turn them into truly impressive art work, inspired by great artists such as Van Gogh, Picasso, and others (+1.5 points for name dropping).<br />
<br />
Here's what it looks like on the famous Success Kid's image:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiWlLEa2nTJ2RWCsDkUq6J4dttcYi71rHHPnbiTsuwDdhQ63EjcNXmJT4xGGytGwkTVAC1kV5CEbUiRI8qIBEsknNhMhBQmJXep9ecgf6JkNxLKMLKK8r8-jf-xFkOZ_J4Qw_w0ahYJEF4f/s1600/success_prisma1.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiWlLEa2nTJ2RWCsDkUq6J4dttcYi71rHHPnbiTsuwDdhQ63EjcNXmJT4xGGytGwkTVAC1kV5CEbUiRI8qIBEsknNhMhBQmJXep9ecgf6JkNxLKMLKK8r8-jf-xFkOZ_J4Qw_w0ahYJEF4f/s320/success_prisma1.JPG" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
Which is it pretty impressive. As usual with these things, well lit highly contrasted photos work best, and it's loads of fun to play with.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjs8ukSsNLAigVqhvvvxiX2gFFaw6fJQgkCrLWFKSpbLK9Hg8A_FjXHrIMkD388Sm04u7tLi8CpkqUkZmekQT3uExs0O7k6xy27Siv8TMfiH47uejkB6Q0fCsPQaZ1StApmdyl7wBXpUKBF/s1600/success_prisma2.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjs8ukSsNLAigVqhvvvxiX2gFFaw6fJQgkCrLWFKSpbLK9Hg8A_FjXHrIMkD388Sm04u7tLi8CpkqUkZmekQT3uExs0O7k6xy27Siv8TMfiH47uejkB6Q0fCsPQaZ1StApmdyl7wBXpUKBF/s320/success_prisma2.JPG" width="320" /></a></div>
<br />
Since the app is free, it begs the question: <b>how do these people plan to make money?</b><br />
Well, here are a few things to consider:<br />
<br />
<ol>
<li>Some of their filters are branded (e.g. by Palmolive), thus generating revenue through advertising.</li>
<li>Since yesterday, the photos come with a water mark on their bottom-right corner, which I guess won't be there in some premium paid version.</li>
<li>As a friend of mine pointed out: it is very hard to do these computations on the device, and as he found out - indeed when you put your device into airplane mode - the app doesn't work, so the heavy lifting must be done in the cloud. To quote my friend: "this is one free app with a huge AWS bill".</li>
<li>In its <a href="https://www.producthunt.com/tech/prisma-2">Product Hunt thread</a>, one of the Co-founders responded to an inquiry about their business model by promising that the app will always be free:</li>
</ol>
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhDs61xMkA5hfH0CxE9UKeCgts_dhvNskFV2sfv57-koTmvwSHFZiH6lSMHOevmQGL89wkJU6ofe9FlR9-UZ2qL2vIQiVPvmEUzyeCTcpzoxbnikuxyGB0FmhOJbztSnGYABwXied3fI4ju/s1600/Selection_193.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="124" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhDs61xMkA5hfH0CxE9UKeCgts_dhvNskFV2sfv57-koTmvwSHFZiH6lSMHOevmQGL89wkJU6ofe9FlR9-UZ2qL2vIQiVPvmEUzyeCTcpzoxbnikuxyGB0FmhOJbztSnGYABwXied3fI4ju/s320/Selection_193.png" width="320" /></a></div>
<br />
<h3>
Conclusion: smells like trouble</h3>
So while this company is obviously putting out a good product (especially if we ignore the annoying 2-3 seconds wait when applying a filter), I believe balancing their cloud bill with revenue from advertisers seems like a big challenge. Of course, they may be aiming at getting bought quickly by the big guys, but the model of allowing users to heavily drain cloud resources, with a limited ability to monetize (unlike search results, social networks feed, etc.), may mean they won't live long enough for this to happen.<br />
<br />
<br />
<br />Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-89656023637209183332016-07-01T09:35:00.000+03:002016-07-01T21:45:24.208+03:00Deliberate Learning: 3 Tips for Acquiring New SkillsRecently, through <a href="http://freakonomics.com/podcast/peak/">Freakonomics</a>, I came across the notion of deliberate practice. The idea, originally introduced by <a href="http://projects.ict.usc.edu/itw/gel/EricssonDeliberatePracticePR93.PDF">Ericsson et al</a> in 1993, and more notably popularized by Malcolm Gladwell's <a href="http://gladwell.com/outliers/">"Outliers"</a>, is that the contribution of natural talent to greatness in art, science, and sports, is far smaller than we tend to assume.<br />
The tl;dr version of it is: the thing that differentiates the greatest among us from the rest is not their talent, but the manner in which they practice. Specifically, they practice an awful lot, and do so in a <b>reflective process that efficiently translates the invested time to a consistent improvement in performance.</b><br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://upload.wikimedia.org/wikipedia/commons/1/1e/Wolfgang-amadeus-mozart_1.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="200" src="https://upload.wikimedia.org/wikipedia/commons/1/1e/Wolfgang-amadeus-mozart_1.jpg" width="135" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Mozart - a guy who was great at something</td></tr>
</tbody></table>
While I don't expect to become the world's greatest anything, some principles of deliberate practice struck me as familiar, and made me think about the way that I learn. I like learning new things, and having done so in a relatively wide variety of areas (painting, music, education, math, algorithms, poetry, design), I wanted to share what works for me when I come across new stuff to learn. To clarify, this is <b>not </b>deliberate practice. Deliberate practice is about becoming great at something over a long period of time. I want to focus on something much more common and useful for me: becoming reasonably proficient at something quickly.<br />
Let's call it <i>deliberate learning</i>.<br />
<h4>
<br />1. Choose a mentor and follow blindly, for a limited time</h4>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://upload.wikimedia.org/wikipedia/en/9/9b/Yoda_Empire_Strikes_Back.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="200" src="https://upload.wikimedia.org/wikipedia/en/9/9b/Yoda_Empire_Strikes_Back.png" width="173" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">For a limited time, blindly follow you will</td></tr>
</tbody></table>
This seems to me particularly useful, while being quite challenging for anyone with a critical mind. It's also very obvious and most people do it to some extent, but it's a good idea to do so consciously as it allows us to switch it on when we need to learn something, whereas the natural tendency, especially with age, is to do it less and less, mostly due to ego.<br />
The idea is to find a teacher, who may be someone teaching you a course at the university, a colleague at work, or even your superior. This person should be very experienced and much better than you at what you're trying to learn, and should be available to you on a regular basis. You should buy into this person's point of view on the subject you're trying to learn: imitate this person's methods, ask for advice, ask questions, and just believe everything they tell you (professionally). For the limited time that you're adopting this person as your mentor, you should also suspend your disbelief about their professional shortcomings. It is a surprisingly powerful approach, as it let's you really run with ideas and concepts along a path someone else already paved, and with their help. After the limited time has passed (e.g., the university term), you can reevaluate all the stuff you used to embrace, and gradually throw away whatever you disagree with, or adapt it to your own style. One last point: this mentor doesn't have to be a person - it may even be a book.<br />
<br />
<h4>
2. Steer toward the boring and the difficult</h4>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEie_o9QMaWySPm6SCusCnnBNwauINHP9_UXuMuIztm75fzJbUxunEHMuxPe4NtIKRiIVdhH3MAJk-1G5ZBwAIhpWg5gKPyEXBPG_Yf99tLXf6sgTWtmNLjNcY_dgm7DwySHpqH6iuejg8vD/s1600/Imagewilkywonka.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="198" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEie_o9QMaWySPm6SCusCnnBNwauINHP9_UXuMuIztm75fzJbUxunEHMuxPe4NtIKRiIVdhH3MAJk-1G5ZBwAIhpWg5gKPyEXBPG_Yf99tLXf6sgTWtmNLjNcY_dgm7DwySHpqH6iuejg8vD/s200/Imagewilkywonka.jpg" width="200" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Boring <b>and </b>difficult? Do go on!</td></tr>
</tbody></table>
<div>
Like the mentor thing, this is about suspending the self for a while. After you finish your learning period on the subject (I know the common wisdom is one should always be learning, but very rarely can one maintain a state of learning about everything) you'll naturally stay away from the stuff that bores you or that you don't understand well. This means that now is the only time you'll have to gain some ground in these areas. This being a learning period, you're also relatively energetic, and can muster the courage to face those areas, so it is very literally now or never. So be on the lookout for boring or difficult topics, and fearlessly dive into them. Your environment (at work or school) knows you're just learning, so it will be more forgiving to failure, which is inevitable when trying new and difficult things.</div>
<br />
<h4>
3. Get people whose judgement you trust to criticize your work frequently</h4>
<div class="separator" style="clear: both; text-align: center;">
</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://vignette2.wikia.nocookie.net/gameofthrones/images/5/57/Tyrion_4x07.jpg/revision/latest?cb=20160130073841" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="112" src="https://vignette2.wikia.nocookie.net/gameofthrones/images/5/57/Tyrion_4x07.jpg/revision/latest?cb=20160130073841" width="200" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">My work sucks? I demand a trial by combat!</td></tr>
</tbody></table>
This is obviously necessary, and naturally hard on the ego, so encourage yourself with the following as you go:<br />
- Paraphrasing <i><a href="https://www.youtube.com/watch?v=y48hZ_rGsP4">Fight Club</a></i> - you are not your work, so your work can and will suck sometimes, which doesn't mean you, in general, do.<br />
- Going from terrible to okay is way easier than going from good to great, so if your work is shitty, this is good news as it means with little work you can improve a lot.<br />
- Crummy work counts for experience too, so it wasn't a waste of time.<br />
<br />Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-71088956635016219252016-06-07T17:30:00.000+03:002016-06-26T06:14:05.112+03:00The God Awful UX of Israeli Train StationsIt does not take a UX expert to see that the electronic ticket validation system in Israel Railways is poorly designed.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEisdsFRloiCQMO5jAkib9KVa8OFJ4hOT85YG_RmnUIyawOvqE5xOqnG2VAMMNx3o-uP0_ZbhxAHwHfTnC_m2vm4A4QB-dunCyL2iuKNYeE7vY7rwprs3GJFEtJTzdojOeu2jELetToymyX6/s1600/train_israel_1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEisdsFRloiCQMO5jAkib9KVa8OFJ4hOT85YG_RmnUIyawOvqE5xOqnG2VAMMNx3o-uP0_ZbhxAHwHfTnC_m2vm4A4QB-dunCyL2iuKNYeE7vY7rwprs3GJFEtJTzdojOeu2jELetToymyX6/s320/train_israel_1.png" width="320" /></a></div>
<br />
Here's how its designers apparently expect it to be used:<br />
- The passenger walks along the lane (1).<br />
- The rotating bar (2) lies about 70cm above ground, and is locked in position until the ticket is validated.<br />
- The passenger presses the ticket against the screen (3).<br />
- The ticket is successfully validated, the passenger pushes the bar (2) that subsequently rotates to allow the passenger to enter the ramp.<br />
<br />
Well, it doesn't exactly play out that way.<br />
About 50% of the time the ticket isn't validated correctly and the rotating bar is locked in place, leaving the passenger stumbling against it, delaying a group of annoyed people standing behind him or her.<br />
Why isn't the passenger validating again? Well, indeed an error message is shown on the screen, and there's also some kind of beep to indicate something went wrong, but none of this matters because:<br />
1) <b>The ever-so-gentle beeping sound is inaudible</b> in any average train station.<br />
2) <b>The screen is parallel to the passenger's field of vision</b>, so one has to bend backward to see it.<br />
3) <b>The screen is often blocked at this point by the passenger's own hand</b> holding the ticket against it to be validated.<br />
4) <b>The screen is almost always dirty</b> because - again - this is where people stick their hand/wallet to validate.<br />
<br />
All this together means that every other passenger gets stuck in the lane. It takes a couple of seconds to figure out that waiting a bit longer isn't fixing it, thereby delaying all other passengers. To top it all, every subsequent validation attempt takes a couple of seconds more than it should - <u>due to the same design flaws</u>. I get annoyed all over again just writing this!<br />
<br />
Mind you, this is not some ground-breaking product that provides completely new design challenges. It's not as if trains or electronic tickets were invented by Israel Railways. Rather, there are tons of examples to research from all over the world!<br />
<br />
It's one of those cases where poor design makes hundreds of thousands of people's daily routine just that much more annoying, as we are helplessly victimized by the laziness and just general inadequacy of others.Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-76282559871944923552016-05-18T08:10:00.000+03:002016-05-18T08:10:24.183+03:00Triangular numbers, a 3D cube, and the octahedral groupFor some computational geometry project, I had to understand the orbits of the action of the <a href="https://en.wikipedia.org/wiki/Octahedral_symmetry">octahedral group</a> on a 3D cube, and like so many times with math, I did it the hard way only to find out later that a simple observation would have saved me the effort. Well, some of the effort.<br />
<br />
<h4>
tl;dr</h4>
<div>
Upon counting the orbits of the cells of a 3D cube under the octahedral group action, I found out the result is a sum of triangular numbers, which has a very intuitive geometric reason.</div>
<div>
<br /></div>
<h4>
The gory details</h4>
The octahedral group can be thought of as the group of symmetries obtained by applying a series of 90-degree rotations and/or face-parallel reflections to a cube. Another way of thinking about it is this: if the cube is centered at the origin, applying an element of the group to the cube is equivalent to shuffling the coordinates and/or multiplying some of the coordinates by $-1$. Since there are 6 permutations of the coordinates, and 8 choices as to which coordinates to multiply by $-1$, the number of elements in the group is 48.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJj5-kfXUQ26hRu-JDGas5vLEp-oc8_j5iN-8xxAdFTqmW6vkIzBsREp_T6yYsOB9NbNp_4hm63TKwAwBry9FueRBOPqel9rxFZkNVXuc22bMg9XOojKRjIwb7H6fakXK482q1aakXp1Am/s1600/grid.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="193" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJj5-kfXUQ26hRu-JDGas5vLEp-oc8_j5iN-8xxAdFTqmW6vkIzBsREp_T6yYsOB9NbNp_4hm63TKwAwBry9FueRBOPqel9rxFZkNVXuc22bMg9XOojKRjIwb7H6fakXK482q1aakXp1Am/s200/grid.png" width="200" /></a></div>
<br />
For simplicity, let's assume that the 3D cube is actually a discrete object, comprised of $n^3$ cells for some even value of $n$ (having an odd $n$ doesn't change the outcome by a lot, but is a bit different). The group action breaks the cube into orbits, for example, the corner cells form a single orbit of size 8. Note that the group elements can be also thought of as $3\times 3$ matrices, all of whose determinents are $1$ or $-1$ (the latter if the element induces a reflection), and the action thus preserves norms. To put it plainly, the distance of a cell from the cube's center is an invariant of the group action. This observation means that we can think of the cube as comprised of $\frac n 2$ nested hollow cubes of dimensions $n\times n \times n, (n-2)\times(n-2)\times(n-2), ... 4\times 4\times 4, 2\times 2\times 2$, sort of like a matryoshka doll of 3D cubes.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj62ofo912mb_5o_0GW_2TJaXv4TFfBUXV5TdGNApFCiy9Pu4v7GVXe4jrtPqNLXM9X6_ngy5C0nf_ZMVvBtFNLh10XCPVaDrOPlUsSHxKbHOxb2lRjytRIp70uete7QVS08kGlpezObqiE/s1600/Selection_160.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj62ofo912mb_5o_0GW_2TJaXv4TFfBUXV5TdGNApFCiy9Pu4v7GVXe4jrtPqNLXM9X6_ngy5C0nf_ZMVvBtFNLh10XCPVaDrOPlUsSHxKbHOxb2lRjytRIp70uete7QVS08kGlpezObqiE/s1600/Selection_160.png" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Image credit: Wikipedia</td></tr>
</tbody></table>
<br />
It suffices to understand how the group acts only on one of these hollow cubes, so let's examine only the largest one - the $n\times n\times n$ hollow cube.<br />
<br />
<h4>
Classifying orbits</h4>
Suppose the cells are indexed w.r.t. the center of cube, so each cell is indexed by some $i, j, k\in \{-\frac n 2,..., \frac n 2\}\setminus \{0\}$ such that at least one of $i, j, k$ is $\pm \frac n 2$. We omit zero because $n$ is even and no cell is the center cell of the cube.<br />
Observe that using this notation, together with thinking of the group elements as permuting coordinates and/or pointwise multiplying them by $-1$, makes it evident that, up to a permutation, there are only 4 cases, or types of orbits:<br />
<span style="background-color: red;">Case 1</span>: $\frac n 2 = |i| \neq |j|, |i|\neq |k|, |j| \neq |k|$, choosing such indices defines an orbit of size 48, since no permutation of the coordinates or multiplication of them by $-1$ leaves the indices as they were.<br />
<span style="background-color: orange;">Case 2</span>: $i = |j| = |\frac n 2|, |j|\neq |k|$, these are all the cells that lie on the edges of the hollow cube. A cell with such indices is invariant under elements switching $i$ and $j$, so its orbit's size is 24. To be precise, in the case where $j = -i = \pm \frac n 2$, swapping $i$ and $j$ is just like pointwise multiplying both by $-1$, so the orbit is obtained simply by moving $k$ around and pointwise multiplication by $-1$, and indeed the orbit size is 24.<br />
<span style="background-color: yellow;">Case 3</span>: $|i| = |j|, |j| < |k| = \frac n 2$, these are all the cells that lie on the diagonals that run along the face of the hollow cube. For the same arguments as Case 2 - the orbit size here is 24.<br />
<span style="background-color: lime;">Case 4</span>: $|i| = |j| = |k| = \frac n 2$, these are the corner cells. The difference between two corners is only the sign of the coordinates, so the size of such an orbit is 8.<br />
<br />
<h4>
Counting orbits</h4>
It is now left to understand how many orbits there are for each case. We choose a representative for each orbit - $(i, j, k)$, and count those.<br />
<span style="background-color: red;">Case 1</span>: The choice is of some unordered pair of elements from $\{1,2,...,\frac n 2 - 1\}$. The pair is unordered since the group action puts $(i,j,k)$ in the same orbit as $(j,i,k)$, and we omit the negatives since they are obtained via the pointwise multiplication by $-1$. The number of ways to choose such a pair is therefore $\frac 1 2 (\frac n 2 - 1)(\frac n 2 - 2)$.<br />
<span style="background-color: orange;">Case 2</span>: Since $|j|$ and $|i|$ must be equal to $\frac n 2$, the only choice here is of $1\leq k < \frac n 2$ (negative values of $k$ are obtained via the pointwise multiplication by $-1$ of the group action). So clearly there are $\frac n 2 - 1$ of those.<br />
<span style="background-color: yellow;">Case 3</span>: Like Case 2, the only choice here is of $1 \leq |i| < \frac n 2$, which in turn determins $|j|$. So there are $\frac n 2 - 1$ such orbits.<br />
<span style="background-color: lime;">Case 4</span>: This is the corners' orbit, so there is exactly one for a hollow cube.<br />
<br />
Putting it together, a hollow 3D cube of dimension $n$ has $\frac 1 2 (\frac n 2 - 1)(\frac n 2 - 2) + 2 \cdot (\frac n 2 - 1) + 1 = \frac 1 8 (n^2 + 2n)$.<br />
Since the full 3D cube, with an even dimension $s$, is comprised of $\frac s 2$ such hollow cubes, the number of orbits is: $\frac 1 8 \sum _{n=1} ^{\frac s 2} ((2n)^2 + 2(2n))$, which surprisingly gives us a sum of triangular numbers $\sum_{n=1} ^{\frac s 2} \frac {n(n+1)} 2$, which has a nice closed form $\frac {\frac s 2 \cdot (\frac s 2 + 1) \cdot (\frac s 2 + 2)} 6$.<br />
<br />
<h4>
Why triangular numbers?</h4>
This is a satisfyingly clean formula to ed up with, after a tedious computation, and as one would expect, it is so for a reason:<br />
As noted in the previous paragraph, the result is a sum of triangular numbers, which are called thus because they also represent the number of blocks you'd use to construct a triangle where the bottom row has $n$ blocks, the next row has $n-1$ blocks and so on.<br />
The image below shows one representative of each orbit in the outer layer of an $8\times 8 \times 8$ cube. The <span style="background-color: #cc0000;">Case 1</span> representatives are red, <span style="background-color: orange;">Case 2</span> - orange, <span style="background-color: yellow;">Case 3</span> - yellow, and <span style="background-color: lime;">Case 4</span> - green.<br />
<br />
And indeed these representatives form a triangle, and the sum of triangles really represents (sort of) a pyramid that goes from the outer layer of the cube inward, the colorful part of the image below being its base.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi9JnoNeMZm-CzcKXu8OT2UaChw6c5ftRgdJ_b8tnMtPyReB5ICujkfIvtzer_Ora4ZJsdvKkOWtDNmGXjh4VCMoZA66pHlKaMZrn_EmpvyAQ2s8WVKYKW5o9xoBWwiXoUPjIWmLisLwdmW/s1600/Selection_159.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi9JnoNeMZm-CzcKXu8OT2UaChw6c5ftRgdJ_b8tnMtPyReB5ICujkfIvtzer_Ora4ZJsdvKkOWtDNmGXjh4VCMoZA66pHlKaMZrn_EmpvyAQ2s8WVKYKW5o9xoBWwiXoUPjIWmLisLwdmW/s1600/Selection_159.png" /></a></div>
<br />
<div>
<br /></div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-38624263123568195582016-04-28T23:30:00.001+03:002016-04-29T06:34:20.852+03:00Powers of Graphs Are Almost Always Hard<div dir="rtl" style="text-align: right;" trbidi="on">
<div dir="ltr" style="text-align: left;">
Early in 2011, I spent a few months as an exchange student in the University of Melbourne. Although I was writing my thesis at the time, I was looking for topics for a small-scale research, as I had to turn in some written assignment as part of the exchange program. I can't remember why, but I thought a bit about powers of graphs, and pondered about their relation to hardness. Since it turned out to be an easy question to solve, it wasn't enough for the written assignment (let alone a research paper), but I do have a warm spot for it, so here it is:<br />
<br />
(If you are browsing on mobile, switch to desktop view to display the math stuff nicely)</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<h4 style="text-align: left;">
Background: Powers of Graphs </h4>
<div dir="ltr" style="text-align: left;">
Given a <a href="http://mathworld.wolfram.com/SimpleGraph.html">simple graph</a> (we restrict our discussion to this type for brevity) $G(V, E)$, we define $G^2$ by adding an edge between every two vertices $v,j\in V$ if there exists some $w\in V$ such that $\{v, w\} \in E$, and $\{u, w\} \in E$.</div>
<div dir="ltr" style="text-align: left;">
In other words - if there was a path of length 2 between $v$ and $u$ in $G$, then there's an edge between them in $G^2$. This works similarly for $G^3$ (where paths of length 3 or less in $G$ become edges) and so on. </div>
<div dir="ltr" style="text-align: left;">
Clearly, if the longest distance in the graph is of length $d$ (in which case we say that $d$ is the <i>diameter</i> of $G$), then $G^d$ is simply a clique, since all paths in $G$ are at most of length $d$.</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
<h4>
Background - Independent Set</h4>
</div>
<div dir="ltr" style="text-align: left;">
Given a graph $G(V, E)$, an independent set of vertices is some $U\subseteq V$ such that $u,v\in U \Rightarrow \{u,v\}\notin E$. Finding a <i>maximum</i> independent set (i.e. largest in size, not to be confused with <i>maximal</i> which means it is not strictly a subset of any other independent set) in a graph is known to be NP-hard, and also hard to approximate.<br />
<br />
<h4>
So here's the question:</h4>
</div>
<div dir="ltr" style="text-align: left;">
In a clique, every vertex is a maximum (and also maximal) independent set, so for every simple graph $G$ with diameter $d$, solving the independent set problem for $G^d$ is easy: just choose any vertex you like, and you're done. This raises the question - if a problem is in general hard on $G$, but easy on $G^d$, how hard is it for $G^k$ where $k < d$? I mean, at which point does this very hard problem becomes trivial? </div>
<div dir="ltr" style="text-align: left;">
<br /></div>
<div dir="ltr" style="text-align: left;">
I'll save you the suspense - independent set is generally hard on $G^{d-1}$, so the problem is not all that interesting, and the hardness of independent set on powers of graphs is basically: hard, hard, hard, ... , hard, trivial. Not an exciting result, I admit, but let's prove it anyway.<br />
<br /></div>
<div dir="ltr" style="text-align: left;">
<h4>
Proof by Reduction</h4>
<div>
Proof sketch: given a graph $G$, we'll construct a graph $H$, that is only slightly larger than $G$, has the same diameter, and is such that solving the independent set problem for $H^{d-1}$ will give us the solution for $G$.</div>
<div>
<br /></div>
<div>
First, the case of an even $d$, which is simpler:</div>
<div>
Denote $G$'s vertices by $v_1, v_2, ... , v_n$, we construct $H$ by taking $n$ disconnected vertices denoted $u_1, u_2, ..., u_n$ - we'll call those the 'old' vertices - and adding $n\cdot (\frac d 2 - 1)$ 'new' vertices to them in the following manner:</div>
<div>
<b>1.</b> Add one special vertex $c$.</div>
<div>
<b>2.</b> For every $i : 1\leq i \leq n$, connect $u_i$ to $c$ by a path of length $\frac d 2$ using $\frac d 2 - 1$ of the 'new' vertices (all of these paths should be disjoint, and that's okay, since we have exactly $n\cdot (\frac d 2 - 1)$ of these new vertices). Denote the vertices of the path from $c$ to $u_i$: $c\rightarrow u_i ^1 \rightarrow u_i ^ 2 \rightarrow ... \rightarrow u_i ^ {\frac d 2 - 2} \rightarrow u_i ^{\frac d 2 - 1} \rightarrow u_i$.</div>
<div>
<b>3.</b> For every $\{v_k, v_j\} \in E$ that form an edge in $G$, add to $H$ the edge $\{u_k ^1, u_j ^1\}$.</div>
<div>
$H$ is thus sort of a big star graph, having $c$ in the middle, with some additional edges due to step (3) above.</div>
<div>
<br /></div>
<div>
<u>A few observations</u>:</div>
<div>
<b>1.</b> For every two vertices of the original graph $\{v_l,v_t\}\notin E$, the shortest path from $u_l$ to $u_j$ in $H$ goes through $c$ and is of length $d$. It follows that the diameter of $H$ is at least $d$.</div>
<div>
<b>2.</b> In $H^{d-1}$, all of the new vertices form a clique, and each of them is connected by an edge to each of the old vertices. The diameter of $H$ is therefore at most $d$, and so it is exactly $d$. </div>
<div>
<b>3.</b> It follows that a maximum independent set in $H^{d-1}$ cannot contain any of the new vertices.</div>
<div>
<b>4.</b> $\{u_j, u_k\}$ is an edge in $H^{d-1}$ <i>if and only if </i>$\{v_j, v_k\}$ is an edge in $G$, so every independent set in $G$ correlates to an independent set of 'old' vertices in $H^{d-1}$ and vice versa. </div>
<div>
Putting all these observations together boils down to the fact tha every maximum independent in $H^{d-1}$ correlates to a maximum independent set in $G$ and vice versa.</div>
<div>
<br /></div>
<div>
What about an odd $d$? well, instead of a single vertex serving as the center, we use a clique of n vertices that serves as center of $H$, and everything else works very much the same.</div>
<div>
<br /></div>
<div>
Note that a slight tweak can be used to show that $H^{d-2}$ is no easier, and so on.</div>
<div>
<br /></div>
<div>
So, alas, independent set is hard on all but the $d$-th power of a graph, in which case it is trivial.</div>
<div>
<br /></div>
<div>
<br /></div>
</div>
</div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-74385906448609362522016-01-31T15:00:00.002+02:002016-02-01T09:51:29.477+02:00NP-Complete Problems as Repeatable Math Puzzles <div dir="rtl" style="text-align: right;" trbidi="on">
<div dir="ltr" style="text-align: left;">
<br /></div>
<h3 dir="ltr" style="text-align: left;">
Repeatable Puzzles</h3>
<div dir="ltr" style="text-align: left;">
In the 3 years I worked at <a href="https://www.matific.com/">Matific</a>, I was involved in designing all of the mini-games (we called them 'episodes') produced by the company. This meant that I spent a non-negligible part of my time on the hunt for math puzzles that are</div>
<div dir="ltr" style="text-align: left;">
</div>
<ul dir="ltr" style="text-align: left;">
<li>interesting and rewarding to solve</li>
<li>rely only on elementary school math knowledge</li>
<li>worth playing over and over, with respect to the above</li>
</ul>
<div dir="ltr" style="text-align: left;">
Most of the really cool puzzles, such as determining which - out of 12 coins - was fake, using a balance scale and only 3 weighings, fall short of the "worth repeating" notion, as there's no real pleasure or challenge in <a href="http://mathforum.org/library/drmath/view/55618.html">solving</a> them a second time. So googling "Math Puzzles" and reading puzzle books, though fun, was often of little use.</div>
<div dir="ltr" style="text-align: left;">
<br />
As time went by, and development progressed, puzzles turned out to be only a small part of what we did. A typical episode was rather required to help in understanding some deeper principal of a previously taught skill, via hands-on experience, which I think we managed to do well, and that's a topic for another post. </div>
<div dir="ltr" style="text-align: left;">
<br />
Nevertheless, there were some puzzles in the mix, for example: a game where the user is given 4-5 numbers (e.g. 2, 3, 4, 7), and is asked to get to a target number (e.g. 23) using the some of the four operations and each of the initial numbers (e.g. 4/2 + 3*7).<br />
<br /></div>
<div dir="ltr" style="text-align: left;">
Another puzzle, for 1st graders, asked the student to arrange toys on shelves, subject to some constraints, e.g. - the doll must be above the teddybear, the car has to be to the right of the dinosaur, and so on.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgd3zHOh6GEn1qwdqQ0rP1wWoW8S94JG35_joZ9RElCYQo3-4677KlEJ2kGORXKFM1NufvhlIK5lG_MJy1JNTjZ3y6tkL3ArvieCZL1OjQLabQ1wEDOSGvOYN7WfwyN-HjvUkf4CJPHBLOA/s1600/Selection_103.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgd3zHOh6GEn1qwdqQ0rP1wWoW8S94JG35_joZ9RElCYQo3-4677KlEJ2kGORXKFM1NufvhlIK5lG_MJy1JNTjZ3y6tkL3ArvieCZL1OjQLabQ1wEDOSGvOYN7WfwyN-HjvUkf4CJPHBLOA/s320/Selection_103.png" width="320" /></a></div>
<br />
A third puzzle was simply variants of a well known water-pouring puzzle: one has 2-3 containers, each of different volume (e.g. 5L and 3L) and the objective is to obtain another quantity (e.g. 4L) via pouring and filling.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen="" class="YOUTUBE-iframe-video" data-thumbnail-src="https://i.ytimg.com/vi/5_MoNu9Mkm4/0.jpg" frameborder="0" height="266" src="https://www.youtube.com/embed/5_MoNu9Mkm4?feature=player_embedded" width="320"></iframe></div>
<h3 style="text-align: left;">
<br />Starting With the Solution</h3>
As we designed more of those repeatable puzzles, a few common traits emerged:<br />
<br />
<ul style="text-align: left;">
<li> they involved a more than one skill. The pouring puzzles, for example, involves addition, subtraction, understanding of volume, and strategizing.</li>
<li> we had to generate problems with well-tuned difficulty levels.</li>
</ul>
<div>
Let me focus on that last one: When one designs a puzzle, the first instinct may be to randomize the problem (e.g. how much water in each container? what is the target quantity?) and then write a solver that solves it, but that is rarely the right thing to do, for two reasons: 1) This leaves the difficulty level to chance, 2) Sometimes the problem has no quick solver, and the solver will needs to go over all possibilites to find the solution, or reach a conclusion that it has no solution, in which case a new problem has to be generated at random and checked and so on. Our standard strategy, which applied to most of the cases, was starting from the solution. </div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiyAtvicBQfXoSXbjR7Cu5xingBiDPWmdKJ0VqSKsxiRvhT5Mb6uBha112-Z3JZuc9unTosqP6k61UQmjOJxwPmohzg69rtOoupXkmqUb3b_n8OqTqFFMYn6DQzaHclcgJsds5E28PZU3Kf/s1600/Selection_104.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="201" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiyAtvicBQfXoSXbjR7Cu5xingBiDPWmdKJ0VqSKsxiRvhT5Mb6uBha112-Z3JZuc9unTosqP6k61UQmjOJxwPmohzg69rtOoupXkmqUb3b_n8OqTqFFMYn6DQzaHclcgJsds5E28PZU3Kf/s320/Selection_104.png" width="320" /></a></div>
<br />
For example, choose 4 random numbers in some range, e.g. 2, 5, 9, 11, and now choose operations at random, e.g. *, +, -, which gets 2 * 5 + 9 - 11 = 8. And so we present the user with the numbers 2, 5, 9, 11, setting 8 to be the target number. This approach has its drawbacks, such as producing problems using a certain solution while a simpler one exists, but they are less severe, product-wise.<br />
This "start from the solution" approach took us a while to figure out, in which time we tried the naive approach, of randomizing a problem and running a solver. After a few of these, I noticed that we often realize that the problem is NP-hard, or in some cases assume it is so, not being sure how to prove it. A solver for such puzzles is problematic and can't scale to larger instances of the problem, especially seeing how the code had to be very light-weight to run on a browser. Lastly, a crucial part of programming a puzzle is checking the user's solution, which was almost always considerably easier than generating the problem. And so at some point it became clear to me that many of our so-called puzzles, were simply instances of NP-complete problems.<br />
This was neat because it gave us something to draw inspiration from, in addition to poring over puzzle books. <br />
<br />
<h3 style="text-align: left;">
Some Thoughts </h3>
I think that what makes NP-complete problems such useful puzzles is that they somehow seem to come from the real world, at least more than those in harder complexity classes, which means many of them can be explained to a layman in a minute. The NP-completeness also means that there's no trick that the user learns once, and is then bored by subsequent puzzles that are solved using that same trick. Being in NP also means that solutions can be checked easily, so the software can check the user's solution, but also, when the user fails - and the software shows a correct solution, the user can see very quickly that it is correct. Lastly, they encourage a heuristic cross-topical approach to problem solving, which is to say there's no title saying "this is a subtraction problem, solve it using subtraction". Both the method and the tools used by the user (or student) are not part of the problem's definition, and that is how math usually presents itself in real life.</div>
<div dir="ltr" style="text-align: left;">
<br /></div>
</div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0tag:blogger.com,1999:blog-642244788469558745.post-38477344324800474732015-12-23T17:13:00.001+02:002015-12-28T18:52:09.729+02:00Casting to double is faster than Kahan's summation<div dir="rtl" style="text-align: right;" trbidi="on">
<h3 dir="ltr" style="text-align: left;">
A floating problem</h3>
<div dir="ltr" style="text-align: left;">
Floating point precision problems are notoriously annoying, and personally I was somewhat surprised they are still an issue in this day and age, but they are.<br />
For instance, by the end of the following code:</div>
<pre dir="ltr" pre="" style="text-align: left;"><pre><span style="color: maroon; font-weight: bold;">float</span> x <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">float</span> f <span style="color: #808030;">=</span> <span style="color: green;">1e-6</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">for</span> <span style="color: #808030;">(</span><span style="color: maroon; font-weight: bold;">unsigned</span> i <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span> i <span style="color: #808030;"><</span> <span style="color: green;">1e6</span><span style="color: purple;">;</span> <span style="color: #808030;">+</span><span style="color: #808030;">+</span>i<span style="color: #808030;">)</span>
x <span style="color: #808030;">=</span> x <span style="color: #808030;">+</span> f<span style="color: purple;">;</span></pre>
</pre>
<div dir="ltr" style="text-align: left;">
<div style="text-align: left;">
x's value will be 1.00904 and not 1.</div>
<div style="text-align: left;">
Even much simpler code reveals the issue:</div>
</div>
<pre dir="ltr" pre="" style="background: rgb(255, 255, 255); text-align: left;"><span style="color: maroon; font-weight: bold;">float</span> x <span style="color: #808030;">=</span> <span style="color: green;">1e6</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">float</span> y <span style="color: #808030;">=</span> <span style="color: green;">1e-6</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">float</span> z <span style="color: #808030;">=</span> x <span style="color: #808030;">+</span> y<span style="color: purple;">;</span></pre>
<div dir="ltr" style="text-align: left;">
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
z's value here will be exactly 1,000,000 and not 1,000,000.000001.</div>
<div style="text-align: left;">
The reason for this is that 32 bit (the number of bits used for a float type) can represent a number to a limited precision, and so it makes sense to use them for high precision when representing small numbers, and to sacrifice that precision gradually as the integral part of the number increases.</div>
<div style="text-align: left;">
<br /></div>
<h3 style="text-align: left;">
Why use floats when you can use doubles?</h3>
<div style="text-align: left;">
Well, in many cases, doubles simply solve the problem. Double is also a finite representation, but is far more precise than float. The smallest positive number a float can represent is about 1e-38, whereas for a double it's something around 2e-308. To emphasize, the ratio between the two is something like 1e270 which is considerably more than the number of atoms in the universe raised to the third power.<br />
The reason is that floats occupy half the space as doubles, and when writing a code that is meant to be vectorized by the compiler, which one often does in high performance computing, this can translate to a factor of 2 speed up. Additionally, if your data is basically a bunch of real numbers, it would also mean your data in floats is around half the size of your data in doubles, so transmitting it over a network may be twice as fast, and so on.<br />
<br />
<h3 style="text-align: left;">
Kahan's summation algorithm</h3>
<div style="text-align: left;">
For running sums, William Kahan suggested the following algorithm, cleverly using a second variable to keep track of the deviation from the "true" sum (the following snippet is <a href="https://en.wikipedia.org/wiki/Kahan_summation_algorithm">from Wikipedia</a>, and not in C++, but straightforward nevertheless):</div>
<div style="text-align: left;">
<br /></div>
<pre style="background-color: #f9f9f9; border: 1px solid rgb(221, 221, 221); font-family: monospace, Courier; font-size: 14px; line-height: 1.3em; padding: 1em; white-space: pre-wrap;"><b>function</b> KahanSum(input)
<b>var</b> sum = 0.0
<b>var</b> y,t // Temporary values.
<b>var</b> c = 0.0 // A running compensation for lost low-order bits.
<b>for</b> i = 1 <b>to</b> input.length <b>do</b>
y = input[i] - c // So far, so good: <i>c</i> is zero.
t = sum + y // Alas, <i>sum</i> is big, <i>y</i> small, so low-order digits of <i>y</i> are lost.
c = (t - sum) - y // <i>(t - sum)</i> recovers the high-order part of <i>y</i>; subtracting <i>y</i> recovers -(low part of <i>y</i>)
sum = t // Algebraically, <i>c</i> should always be zero. Beware overly-aggressive optimizing compilers!
<b>next</b> i // Next time around, the lost low part will be added to <i>y</i> in a fresh attempt.
<b>return</b> sum</pre>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
And this is, in my opinion, really beautiful. </div>
<div style="text-align: left;">
However, as it turns out:</div>
<h3 style="text-align: left;">
Casting to double is faster</h3>
<div>
As it turns out, the dumber, less beautiful solution, is faster:</div>
<div>
<pre style="background: rgb(255, 255, 255);"><span style="color: maroon; font-weight: bold;">
</span></pre>
<pre style="background: rgb(255, 255, 255);"><pre style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial;"><span style="color: maroon; font-weight: bold;">double</span> x <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">float</span> f <span style="color: #808030;">=</span> <span style="color: green;">1e-6</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">for</span> <span style="color: #808030;">(</span><span style="color: maroon; font-weight: bold;">unsigned</span> i <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span> i <span style="color: #808030;"><</span> <span style="color: green;">1e6</span><span style="color: purple;">;</span> <span style="color: #808030;">+</span><span style="color: #808030;">+</span>i<span style="color: #808030;">)</span> <span style="color: purple;">{</span>
x <span style="color: #808030;">=</span> x <span style="color: #808030;">+</span> f<span style="color: purple;">;</span> <span style="color: dimgrey;">// f is implicitly cast to double here</span>
<span style="color: purple;">}</span></pre>
</pre>
</div>
</div>
<div style="text-align: left;">
<br />
I ran some experiments, and for a very large set of numbers (adding 1e10 numbers, each equal to 1e-7), casting to double was twice as fast as using Kahan's summation algorithm.<br />
A cool algorithm, though.</div>
</div>
</div>
Shir Peledhttp://www.blogger.com/profile/09979031232145173473noreply@blogger.com0