After Vaati turns the princess to stone, you must head to the Minish Woods to get the treasure of Deepwood Shrine.
Travel to the Minish Woods
Go east to Lon Lon Ranch, then go south to the Eastern Woods, and from there, south and east to the Minish Woods. The straightforward path through the forest will take you close to the Deepwood Shrine, but before you get there, you hear a voice cry out for help. Before going to investigate the voice, keep going to the left to find a piece of heart.
Now go back to that voice and kill the Octoroks to save the weird green creature, whose name is Ezlo. He wants to follow you around, but he moves so slowly that he decides to hop onto your head, since he is kind of hat-shaped. In fact, he looks a lot like Link's usual green cap. You can get advice from Ezlo if you press Select.
Keep going along the path that you were following before you went back to rescue Ezlo. When you reach a sparkling tree stump, Ezlo tells you that the Picori call themselves Minish, and you can shrink to Minish size if you stand on the tree stump and press R. Do this now.
If you want to return to normal size, stand next to a shrinking portal and press R. Be careful when Minish-sized, because you will drown if you walk into a puddle, and you are more vulnerable to monsters, and grass is too tall for you to walk through. Some floors are too tall for you to go past, also. But while Minish-sized, you can talk to animals. Cats will attack you, though.
Follow the path west through a log. You will reach an area of water with a couple of lilypads floating around. Carefully step onto a lilypad as it passes, then get off at the top side. Take the path up, passing some giant acorns and leaves, and you enter the Minish Village.
Go up and the Minish will approach you. Unfortunately, you don't understand their language. Go north to the house with blue hexagonal roofs, where you meet Festari, the one Minish who speaks human language. He tells you to find a Jabber Nut. Go to the southeast area of town and find the house made out of a barrel, with a bridge leading to the top of it. Inside, go to the top and push the bottom crate to the left or right. Above and to the left is the Jabber Nut. Go up to it and press R to eat it.
Now you can go around to the houses and talk to Minish if you wish. One of them mentions Kinstones, which you will learn more about later. One of the Picori tells you that Master Melari, who lives in the mountains, could reforge the Picori Blade. He says to go to the Elder to find out more.
There is a wooden walkway to the right of the wooden bridge that took you to Festari's abbey. If you follow it, you find a piece of heart.
The Elder's house is in a mushroom house on a log to the west of Festari's abbey. He says that you need the four "elements" to reforge the Picori Blade. He marks on your map where to find all of the elements. He says that the first element can be found in the shrine to the north of Festari's abbey, so go back to the abbey and talk to Festari, who lets you pass.
Back in the woods, still Minish-sized, go straight north through all of the little holes. If you didn't get the piece of heart before, you can't get it at this size; you will need to come back later. You enter Deepwood Shrine.